Re: CAS, Lambda Calculus, Continuation and Functional Programming

From: Joachim Durchholz (jo_at_durchholz.org)
Date: 03/16/05 

Date: Wed, 16 Mar 2005 13:20:00 +0100

John Creighton wrote:

>>>These languages are statement-oriented, the programs consisting of a
>>>sequence of statements. LISP programs, as originally defined, were
>>>specified entirely as expressions.
>>
>>Mhm. There are no expressions in Fortran or Pascal??! I understand the
>>shortcut, but such passages in a *primer* (of Colin Allen & Maneesh
>>Dhagat) ere simply harmful for the reader.
>
> What would be an expression in FORTRAN? The condition of an if
> statement? I am unclear on the difference. I must do more reading.

Fortran may handle these things a bit differently, but in general,
expressions are programming language constructs that return a value.
(The antonym is that of "statement", which changes the state of the
program. "a + b" is an expression, "c := a + b" is a statement
containing, among other things, an expression.)

>>>... Due to their regular, recursive structure, LISP programs tend to be short
>>>and elegant. But also, to be able to program effectively in LISP, a
>>>different kind of thinking is required; one must learn to think
>>>recursively. This is very different from statement-oriented thinking
>>>required for languages such as Pascal, C, or FORTRAN.
>>
>>This is of course rubbish. There are recursive statements, procedural
>>calls. The major part of complicated structure in LOGO is recursive
>>*and* imperative. Some days ago Richard Fateman issued a warning that
>>some people 'here' say whatever. Unfortunately, many "primers",or
>>"tutorials" on the Web are to be avoided, or at least to mistrust...
>
> To be fair to the author I don't think he said that imperative
> languages don't have recursion. However, I think programmers who use
> imperative language usually avoid recursive techniques to solve
> problems. Partly because they can, partly because a non recursive
> solution is easier in many problems and partly for reasons of speed
> and memory usage.

This is true, at least to a significant extent. (There are imperative
programmers who do a lot of recursion, but neither these personalities
nor the scenarios where recursion is the best solution are very common.)

To quote the exception that establishes the rule, there is a very famous
algorithm that's both inherently recursive and imperative: Quicksort.

> This is contrasted with the philosophy of a functional programming
> language where speed of implementation is much more important then how
> fast the program runs or how much memory it uses (the whole only 20%
> of the program needs to be fast).

That's simply wrong. Space and time efficiency *is* taken very seriously
in the FPL community. In fact there has been just a
Sieve-of-Erasthothenes contest where C++ was beaten both by OCaml and
Haskell, even though OCaml and Haskell do array bounds checking while
the C++ version does not :-) (before boasting with that result, one
should also state that while all three program versions have been
optimized as optimize can, the people who're doing this shootout may be
better optimization experts for Haskell resp. OCaml than for C++).

As the various ICFP contests have shown, the performance level of
functional language programs is comparable to that of C and C++ (this is
in line with the sieve benchmarks quoted above).

> In functional programming the
> programmer is often forced to formulate problems in a recursive
> fashion.

Not really. Most problems are just iterating over a data structure (or a
series of values that's being computed in an iterative fashion). For
these, higher-order functions exist that conveniently wrap the recursion
and let the programmer think about what to do at each iteration.

> For someone coming from an engineering background this
> bothers me. If I am forced to define a loop recursively I know in C,
> Java and Matlab this could lead to the stack over flowing. I am
> wondered what optimizations compilers of functional programming
> languages do to rectify this problem.

Recursion that's equivalent to loops can always be optimized back into
loop form when it comes to emitting code. This is not a problem with any
single functional programming language that I know.

The technique is called "tail call elimination", in case you wish to
google for it.

> Is there anything that would
> prohibit using the same optimizations in an imperative language.

Partly. Imperative aspects of a language may require global program
analysis to make sure that a tail call can indeed be eliminated, and
that makes tail call elimination less attractive for compiler writers.
I don't recall the full range of things that can prevent tail call
elimination, but the two that I do recall are exception handling and
setjmp/getjmp. I dimly recall that there were also issues with
destructors in C++, but I may be confusing things here.

> Thus a programmer in a functional programming language is more
> concerned about the mapping between the input and output of a function
> then the set of instructions needed to perform a task. Maple however
> was originally conceived to use less memory and be faster then the
> other CAS of the time of its conception. Thus at least within the
> software environment efficiency was an important design priority.

I'd rather say that functional languages might not have been efficient
enough at the time that Maple was designed. However, those pseudo
assignments discussed earlier seem to be abominations even for an
imperative language, so the differences are probably more due to Maple &
friends being domain-specific languages, than due to any efficiency
concerns.

> However, the efficiency objective of Maple is partly constrained since
> the only practically why to to store expressions is within an
> operation tree. Such a try must be explored in a recursive fashion
> from the root to the leaves. Thus although Maple was conceived to be
> more space efficient and speed efficient it is still heavily tied to
> recursive processing which is a dominate feature of a functional
> programming style.

Recursive programming isn't inefficient. It's less efficient than loops,
provided (a) you have only iterative data structures to operate on
(expressions aren't iterative, they are recursive), and (b) the compiler
isn't smart enough to properly optimize iterative (aka linear) recursion.

Disclaimer: this all being written from a CS background. Which is rather
inappropriate for symbol manipulation: different conventions, different
issues.
Despite being called "functional languages", these languages aren't
particularly geared towards symbol manipulation or other mathematical
activities (though they happen to be quite good at it - but the main
point of using a functional language isn't that it's mathematically
inclined, it's other properties like referential transparency, closures,
and higher-order functions that make these languages valuable for a
programmer).

Regards,
Jo

Relevant Pages

  • Re: This one goes to 11
    ... programming language and have it immediately executed during debugging. ... and especially tail recursion. ... Common Lisp cover all the important cases in a convenient, ...
    (comp.lang.lisp)
  • Re: Interesting article by Joel Spolsky: The Perils of JavaSchools
    ... > recursion to define an ordered set, that does not imply (as you imply ... programming in something like Java. ... >>> abandon Java in favour of a toy language that is limited to them and no ...
    (comp.programming)
  • Re: Statically AND Dynamically Typed Language ??
    ... I haven't been able to do even that in my daily programming ... That's a strange claim - the old default ranking for Pentium 4 seems ... on tail recursion, simple vectorization etc. ... If the language implementation doesn't provide a way to use simple ...
    (comp.lang.misc)
  • Re: CAS, Lambda Calculus, Continuation and Functional Programming
    ... >> the programming style of symbolic math packages as partly functional ... see that I strive to learn the language which we use to understand the ... languages don't have recursion. ... Thus it doesn't seem to me that lambda calculus if fully implemented ...
    (sci.math.symbolic)
  • C++ program as a Lisp expression
    ... The language includes lists, as ... Lisp, but it also has records and tuples (I think this makes it more ... clear what the expressions mean). ... operators to mimic common programming notations. ...
    (comp.lang.lisp)