Which FP language follows lambda calculus the closest?

functional-programming, lambda-calculus

Solution

This might not be a real answer, it's more of a guess about what you actually want.

In general, there's very little in the lambda calculus -- you basically need (first-class) functions, function applications, and variables. These days you'll have hard time finding a language that does not provide you with these things... However, things can get confusing when you're trying to learn about it -- for example, it's very easy to just use plain numbers and then get them mixed up with church numerals. (I've seen this happen with many students, adapting to the kind of formal thinking that you need for this material is hard enough that throwing encodings onto the pile doesn't really help...)

As Don said, Scheme is very close to the "plain" untyped lambda calculus, and it's probably very fitting in your case if you're going through The Little Schemer. If you really want to use a "proper" LC, you need to make sure that you use only functions (problems as above); but there are some additional problems that you'll run into, especially when you read various other texts on the subject. First, most texts will use lazy evaluation which you don't get in Scheme. Second, since LC has only unary functions, it's very common to shorten terms and use, for example, `λxyz.zxy` instead of the "real" form which in this case is `λx.(λy.(λz.((z x) y)))` or `(lambda (x) (lambda (y) (lambda (z) ((z x) y))))` in Scheme. (This is called Currying.)

So yes, Scheme is pretty close to LC, but that's not saying much with all of these issues. Haskell is arguably a better candidate since it's both lazy, and does that kind of currying for multiple arguments to functions. OTOH, you're dealing with a typed language which is a pretty big piece of baggage to bring into this game -- and you'll get in some serious mud if you try to do TLS-style examples...

If you do want to get everything (lazy, shorthands, untyped, close enough to Scheme), then Racket has another point to consider. At a high-level, it's very close to Scheme, but it goes much farther in that you can quickly slap up a language that is a restriction of the Racket language to just `lambda` expressions and function applications. With some more work, you can also get it to do currying and you can even make it lazy. That's not really an exercise that you should try doing yourself at this point -- but if it sounds like what you want, then I can point you to my course (look for "Schlac" in the class notes) where we use a language that is doing all of the above, and it's extremely restricted so you get nothing more than the basic LC constructs. (For example, `3` is an unbound identifier until you define it.) Note that this is not some interpreter -- it's compiled into Racket code which means that it runs fast enough that you can even write code that uses numbers. You can get the implementation for that language there too, and once you install that, you get this language if you start files with `#lang pl schlac`.

Problem

Original source