Path: utzoo!utgpu!attcan!uunet!mcvax!ukc!etive!lfcs!sean
From: sean@lfcs.ed.ac.uk (Sean Matthews (AI))
Newsgroups: comp.lang.forth
Subject: Re: Functional Programming
Keywords: What is it?
Message-ID: <823@etive.ed.ac.uk>
Date: 7 Oct 88 18:48:53 GMT
References: <180@kadsma.kadsm> <628@sas.UUCP>
Sender: news@etive.ed.ac.uk
Reply-To: sean@lfcs.ed.ac.uk (Sean Matthews (AI))
Organization: Laboratory for the Foundations of Computer Science, Edinburgh U
Lines: 105

In article <628@sas.UUCP> bts@sas.UUCP (Brian T. Schellenberger) writes:
>In article <180@kadsma.kadsm> brunjes@kadsma.UUCP (Roy Brunjes) writes:
>|I have seen several postings lately talking about functional programming and
>|how suitable Forth is for that.  My question is, I hope, more simple.  What
>|IS functional programming?  
>
>Functional program is where you program without side effects.  That is, 
>whenever you call something, it only returns information and does not
>set global variables and so on.  It is most commonly associated with LISP.

It is rather more than that in most cases.  Most good functional
programming languages are a lot more flexible than lisp (unless you
think of scheme--- and even there only by pushing *hard*).

Yes, basically a functional programming language is one without side
effects, but people who use them associate them at least as much with
what are called higher order functions; i.e., a functional programming
language does not treat a piece of code any differently from any other
data object (apart from the obvious distinctions---equivalence on
functions is not decidable, for instance).  The provenance of Fuctional
programming languages is therefore the same as Lisp --- lambda
calculus and combinatory logic, but they share very little to nothing
today.

a very small example:

if we define the fuctions inject and map:

   inject f terminal  nil        = terminal;
   inject f terminal [head|tail] = f head (inject terminal tail).

   map f nil         = nil;
   map f [head|tail] = [(f head)|(map f tail)].

then it is possible to write a lot of powerful functions in one line.

   sum  = inject plus 0.
   prod = inject times 1.
   inc  = plus 1.
   inc-list = map inc.
are two simple examples, then we can say:

  sum [1 2 3] = 6.
  prod [1 2 3] = 6.
  inc 1 = 2.
  inc-list [1 2 3] = [2 3 4].

or more complex:

  length list = sum (map \x.1 list).

/* \x.foo is a function lambda abstracted on x */

then:

  length [1 2 3 4 5] = 5.

the strength of functional programming languages is in the simplicity,
once you grasp the idiom, of programs, especially where very complex
programs are being written.  The point is rather lost in these short
examples (it is possible using a standard set of higher order functions---
like map and inject---to write a lot of algorithms with *no* explicit
control structure.  I can write quicksort in two lines.

They are very good for prototyping and for one off progams.

They are one popular suggestion for a suitable style of language
for very parallel computers.

They are very bad where a lot of calculation has to be done or
when the program is mostly i/o.

Having said this I once used a functional programming language as
a specification language rather than as a programming language and 
described a simple full screen editor in about 100 lines.  (it was
a bity slow but it did clear up a lot of problems that would otherwise
only have come to light *much* later).

If you want to get some idea of what they involve then I suggest you try
the ML programming book in Prentice Hall International (the series edited
by Tony Hoare).

And for a description of a particulary radical language, John Backus's
ACM Turing lecture (I cant remember the title, it is something like:
`can programming be liberated from the Von Neumann bottle neck'.

The best fuctional programming language I know is standard ML, (the fact
that it was invented here is of course irrelevant), unfortunately the
compliler I use, which is *very* fast needs a sun-3 with approx 16meg
of real memory to work properly so is is not going to move into the forth
community in the immediate future.
(ML is essentially a syntactically sugared version of the typed lambda
calculus with lots of bells and whistles).

As for forth as a fuctional programming language, forget it.  This would be
like OOprogramming in Fortran, it could I suppose be done, the language
does have a stack, but the effort would not repay itself.

After all you can do fuctional programming on a Turing Machine, all it
would involve would be a little programming to prepare the ground.

I do not subscribe to this group, I fell into this  discussion while browsing
so if you object violently to any of the above mail me at home.

Se\'an.