[plt-scheme] The Lambda Calculus behind functional programming

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Wed Aug 29 14:46:20 EDT 2007

On Aug 29, 2007, at 2:27 PM, Grant Rettke wrote:

> 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?

A working programmer should have seen:
  -- syntax
  -- reductions (eval is a function via Church Rosser)
  -- scope vs de Bruijn indices
  -- beta vs beta-value, normal form [relevant in math] vs value  
[relevant in cs]
  -- basic denotational semantics (typed PCF suffices)
  -- typed lc plus type system, SNF
  -- extended with some amount of fancy type system stuff (say  
explicit polymorphism)

That's approx 10 weeks worth of course material. Or 2 weeks of self- 
study with a one-hour lunch break.


> What would you tell folks about who have never looked at FP when they
> ask you about lambda calculus?

Engineers study calculus and some analysis plus physics so that they  
can build cars, bridges, etc and predict their behavior.

Software engineers study lambda calculus so that they can build small  
software systems (apps, single programmer) and predict their behavior.

-- Matthias



Posted on the users mailing list.