[plt-scheme] The Lambda Calculus behind functional programming

From: Chris Stephenson (cs at cs.bilgi.edu.tr)
Date: Thu Aug 30 12:20:03 EDT 2007

My 2 cents from practical experience:

"Starting with the lambda calculus" would not be a very bright way to
introduce students to programming.

However, for students who have been through HtDP, done some more
advanced programming, then as part of a more advanced language course,
the lambda calculus both shows where some fundamental ideas come from
and also, because of its simplicity, enables students to write some
neat, but short programs to see those ideas in practice.


Write a program that takes a lambda expression  and converts it to
DeBruijn notation. That is part of what a compiler does.

Write a program that does beta reduction of a Lambda expression (as it
stands, or in DeBruijn notation)

These are nice little programs to write that also give a lot of

I use an hour a week on lambda calculus as a parallel strand in a
languages course where the other two hours of the course look at
interpreting bigger languages. My experience is that this works well.

In this context normal vs applicative order and laziness, dynamic and
static scope, make more sense as there is a network of analogies - the
students can bring the two strands  together.

If we want, we could set all of Computer Science down as a formal tract
starting with a Turing Machine or the Lambda Calculus. That is  not the
right order to teach it. Understanding is a more subtle process. You
need to have written quite a few programs before you can really make
sense of the reason for formalisations like LC and what we gain from
studying them. You need to be able to come in at topics from more than
one direction.

That is what works for me.

Chris Stephenson

Corey Sweeney wrote:
> On 8/29/07, Jos Koot <jos.koot at telefonica.net> wrote:
>> For me discovering Lambda Calculus (and combinatory logic) was fabulous in
>> itself. It is beauty.
>> Whether or not it makes you a better programmer. I am inclined to think so, but
>> I don't have any kind of evidence,
>> Anyway, when my friends ask me what I am doing these days, I have much trouble
>> making an understandable answer.
>> My conclusion:
>> 1: Lambda calculus is not the starting point of learning programming, I think.
> I personally would tend to disagree with the idea of lambda calucus
> not being a good starting point.  (well, technically typing would be
> the starting point :) .  Why do you think it's not a good starting
> point?  Is it the lack of a good IDE?  (which by the way, i have a
> solution for ;) .   I would agree that paper and pencil is not a good
> way to start.  But for the motivated learner, I think that the lambda
> calculus with a few moddification could be a near optimal environment.
> What are other peoples thoughts?
> Corey
>> 2: At some stage you wonder: what are the essential principles of programming.
>> 3: At that point lambda Calculus may be an answer.
>> 4: Wait for your students to ask the question before answering it
>> 5: Not all of us can claim to be as clever as Socrates, but asking questions is
>> a good method to make your students ask the right questions.
>> 6: I know I have failed on this many times
>> Jos Koot
>> ((((lambda(x)((((((x x)x)x)x)x)x))
>>    (lambda(x)(lambda(y)(x(x y)))))
>>   (lambda(x)(write x)x))
>>  'greeting)
>> ----- Original Message -----
>> From: "Grant Rettke" <grettke at acm.org>
>> To: "PLT Scheme" <plt-scheme at list.cs.brown.edu>
>> Sent: Wednesday, August 29, 2007 8:27 PM
>> Subject: [plt-scheme] The Lambda Calculus behind functional programming
>>> When I tell people that I'm learning Scheme the first thing they ask
>>> me is "So have you learned lambda calculus?". I've learned enough to
>>> say the words "lambda calculus" and that everyone says that lambda
>>> calculus is the theoretical backbone of functional programming; but
>>> that is it.
>>> The following question is a simple one, it makes no attempt to
>>> generalize whether anything is worth learning, I think you get the
>>> idea.
>>> So to revisit this again, what do you need to learn of the lambda
>>> calculus relative to FP?
>>> What would you tell folks about who have never looked at FP when they
>>> ask you about lambda calculus?
>>> _________________________________________________
>>>  For list-related administrative tasks:
>>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>> _________________________________________________
>>   For list-related administrative tasks:
>>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 252 bytes
Desc: OpenPGP digital signature
URL: <http://lists.racket-lang.org/users/archive/attachments/20070830/28b65228/attachment.sig>

Posted on the users mailing list.