Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
add comment

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.

share|improve this answer
add comment

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
add comment

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
1  
@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
add comment

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
add comment

Your Answer

 
discard

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.