Re: CAS, Lambda Calculus, Continuation and Functional Programming

From: John Creighton (JohnCreighton__at_hotmail.com)
Date: 03/15/05 

Date: 15 Mar 2005 13:00:38 -0800

JohnCreighton_@hotmail.com (John Creighton) wrote in message
Jerzy Karczmarczuk <karczma@info.unicaen.fr> wrote in message news:<d16ac7$p6$1@elingue.unicaen.fr>...
> John Creighton wrote:
> > First I would like to say that I am not alone in partly classifying
> > the programming style of symbolic math packages as partly functional
> > programming.
>
> First, I would like to underline that ALL LANGUAGES have some functional
> layer. This doesn't mean too much. Anyway, a discussion about what is
> and what isn't FL quickly becomes a religious one, I propose to stop.
Practically it is generally easier for people to focus on a Narrow
field and learn that well. However, with such a narrow focus the
bigger picture is often missed. I understand it is a challenge for
someone with a non computer science background to gain an appreciable
understanding of where various computer science techniques fit within
the bigger picture of programming paradigms, however that is a
challenge I am willing to take.

I wish to understand how things in general fit together. I have
studied philosophy and economics in some of my past electives to gain
a wider picture of human thought. I have an undergraduate degree in
physics and one in electrical engineering as well with a better
background in mathematics then most students who graduated with
undergraduate degrees from either of those departments.

During my studies in electrical engineering I focused on signal
processing and control systems because the mathematics within those
two fields generalizes a large variety of problems and thus adds a
very important pillar of understanding to my repertoire. Thus you can
see that I strive to learn the language which we use to understand the
world and solve problems. Rather then the facts I pursue the ideas and
the methodologies.

Mathematics contains the richest and most abstract ideas but lacks the
application to understanding the world or solve problems. Physics
teaches as about the world in terms of its most fundamental
principles, engineering teaches us how to use the principles of
physics to our benefit and computer science gives us a language and
methodology to apply the knowledge of math physics and engineering in
a manner that is much more powerful then was possible prior to the
dawn of the computer. I recall reading that longest ever hand
calculation took 10 years to complete and it was to deduce the orbit
of another planet from the deviations in the orbit of Jupiter. Today
given our ability to mechanize symbolic and numeric calculations such
a computation would be considerably less burdensome.

> In the quotations below there is plenty of very dubious statements.
>
> > "LISP is a functional programming language. This means it is based on
> > the use of expressions. The readers may be familiar with Pascal, C, or
> > FORTRAN, which are all classified as imperative programming languages.
>
> > 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.
> > ... 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 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). In functional programming the
programmer is often forced to formulate problems in a recursive
fashion. 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. Is there anything that would
prohibit using the same optimizations in an imperative language.

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.
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.
> In the
> > Thus from these pararagrh one may conclude that Maple contains
> > attributes of functional programming.
>
> Sure, as every other programming language. Nobody would call Matlab
> a functional language. But the dialog with the interface may be
> expression-oriented. There is a possibility to parameterize a
> procedure with another one, so you have higher-order functions. The
> Matlab object system permits to implement a kind of closures. So
> what?
> Maple has anonymous functions (unapply beast; x -> x*sin(x); etc.).
> Thus, you have your beloved lambdas. So what?
By now you know my knowledge is rather limited on these topics. But
from what I read I don't think the above example completely
constitutes lambda calculus. If I evaluate the expression:
&#61656; ((x,y)->x^2+y)(2,1);
I get
 
But if I evaluate

&#61656; ((x,y)->x^2+y)(2);

I get

Error, (in unknown) unknown uses a 2nd argument, y, which is missing

When I should get
y->4+y
Thus it doesn't seem to me that lambda calculus if fully implemented
in Maple. Or if by definition this is considered a full implementation
of lambda calculus then the Maple implementation of lambda calculus is
considerably more awkward then in Haskel. I noticed from the Lisp
primmer which apparently wasn't that good that Lisp supports lambda
calculus. I wonder if the implementation of Lambda calculus in Lisp is
closer to that of Haskel or Maple.

> Lambdas you have. Higher order functions as well (apply, etc.).
> You have composition: @, and its iterator @@.
> You have the 'curry' contraption.

Relevant Pages

  • Re: CAS, Lambda Calculus, Continuation and Functional Programming
    ... There are no expressions in Fortran or Pascal??! ... expressions are programming language constructs that return a value. ... > languages don't have recursion. ...
    (sci.math.symbolic)
  • 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: object system...
    ... for that you need machine language. ... isn't even as fast as other systems programming languages. ... Stroustrup's stated design goal was to enable ... all manner of elegance or abstraction can be sacrificed for speed, ...
    (comp.object)
  • 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: DirectX in HLA
    ... I guess that you have a great knowledge of DirectX ... > understanding by looking at them in assembly language... ... > actually represents, really, is a means to "undo" the OOP so ... > is NOT an "OOPL" (object-orientated programming language), ...
    (comp.lang.asm.x86)
Loading