I'm trying to make a new functional language and it's interpreter for practice. As I know most basic building block is only a lambda function, and it's just a closure. I'm not understanding them well, so I want to ask about I'm right or what's wrong?

4 Answers 4


I would take a look at SIOD (Scheme in one Defun) and some of the more stripped down versions of scheme and lisp. It is amazing just how small scheme really is. You need a function construction and about 5 special forms and you have a lisp interpreter. (It won't be a fast one but it will work)

And of course take a look at SICP (Structure and Interpretation of Computer Programs) You can find it online at the mitpress website.


If you want an absolutely minimal set of primitives, use SK calculus, see the Unlambda language.

Otherwise, a simple term-rewriting engine implementing a basic lambda calculus will be sufficient.

Update: forgot to mention - both ways will not introduce closure as an atomic primitive.


In the purest lambda calculus, the only thing that is required to perform any computation is the lambda function. Alonzo Church described one possible encoding of numbers, with which the mere application of a specially-formed lambda performs work.

Even in Lisp, the entirety of the language can be constructed from lambdas. The workhorse is the Y combinator (PDF warning). With it, you can implement anonymous recursive functions; within the scope of which you can construct all of the forms needed to implement the most basic Lisp dialect.

Honestly, it's all quite a bit over my head, and I'm still trying to wrap my head around it, so I hope I haven't horribly butchered this. :)

  • Y-combinator does not need to be an atomic primitive.
    – SK-logic
    Feb 18, 2011 at 12:24
  • 1
    @SK-logic: I never said it did. The only atomic primitive I'm talking about is the Lambda.
    – greyfade
    Feb 18, 2011 at 16:03

As I understand it, closure is not absolutely necessary. Closures are convenient because they "fix" a lexical environment. A closure sent as an argument includes its bound variables so they don't need to be sent as well. Any task that can be accomplished with a closure can be accomplished without one by explicitly sending both the function and variables as arguments. Think of the power of combinators.

Lambdas and closure make a language easier to use or more expressive. Just don't forget first class functions in your new language.

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.