For example:

(define fact
    (lambda (n)
        (if (< n 2) 1 (* n (fact (- n 1)))))

How is this an example of applied lambda calculus? I tried to read the Steele paper (or for that matter, the Peyton-Jones paper), but got confused when they made the jump from the description of lambda calculus to the application thereof in Scheme.


1 Answer 1


The terms of the lambda calculus essentially represent a subset of scheme terms. For instance, most people would agree that

(lambda (x) (x x))

is a term in the lambda calculus and also in scheme, and also that they mean "similar" things. When it comes to evaluation things get a bit more interesting; the lambda calculus, in its purest form, consists of a single rule (beta) that can be applied in arbitrary locations, whereas scheme--as an eager, call-by-value language--applies the beta rule only in certain locations.

Sounds like you should ask follow-up questions?

  • $\begingroup$ As I understand it, lambda calculus allows us to abstract functions into a one-variable, generic, no-name entity -- which I can sort of see with your example. But my factor example, well, obviously doesn't do currying, but it does go into recursion and multiplication, which seems to be "jumping ahead" of any sort of pure lambda calculus I've seen. Obviously, Scheme isn't doing pure lambda calculus to get the answer. So what about Scheme is lambda calculus? $\endgroup$
    – 147pm
    Feb 12, 2015 at 0:38
  • $\begingroup$ I think the best answer here is simply: scheme implements a superset of the lambda calculus. When you say "doing lambda calculus", I think you mean "rewriting terms using the beta rule (and maybe others)." The connection here is that scheme respects the lambda calculus, in the sense that if you're careful to apply the rules only in certain contexts (cf. Felleisen & evaluation contexts), the lambda calculus will "produce" the same set of values that scheme's evaluation function does. Please forgive me for being only as formal as I choose to be... $\endgroup$ Feb 12, 2015 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.