[plt-scheme] The Lambda Calculus behind functional programming

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