Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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.

share|improve this answer

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.

share|improve this answer

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. :)

share|improve this answer
Y-combinator does not need to be an atomic primitive. – SK-logic Feb 18 '11 at 12:24
@SK-logic: I never said it did. The only atomic primitive I'm talking about is the Lambda. – greyfade Feb 18 '11 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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