Which FP language follows lambda calculus the closest? [closed]

Question

Which FP language follows lambda calculus the closest in terms of its code looking, feeling, acting like lambda calculus abstractions?

Answer 1

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.

Answer 2

Lambda calculus is a very, very restricted programming model. You have only functions. No literals, no built in arithmetic operators, no data structures. Everything is encoded as functions. As such, most functional languages try to extend the lambda calculus in ways to make it more convenient for everyday programming.

Haskell uses a modern extension of lambda calculus as its core language: System F, extended with data types. (GHC has since extended this further to System Fc, supporting type equality coercions).

As all Haskell can be written directly in its core language, and its core language is an extension of typed lambda calculus (specifically, second-order lambda calculus), it could be said that Haskell follows lambda calculus closely, modulo its builtin operators for concurrency; parallelism; and memory side effects (and the FFI). This makes development of new compiler optimizations significantly easier, and also makes the semantics of a given program more tractable to understand.

On the other hand, Scheme is a variant of the untyped lambda calculus, extended with side effects and other non-lambda calculus concepts (such as concurrency primitives). It can be said to closely follow the untyped lambda calculus.

The only people that this matters to are: people learning the lambda calculus; and compiler writers.