Theoretical Basics of Lambda Functions

Question

Hi all,

I was just wondering where I could find some language-agnostic tutorials for what lambda functions are, what their use is, and rough equivalents in languages that don't support them.

I would especially love any information on common notations.

Thanks! Please let me know if I can elaborate on this at all.

EDIT: Oh hey I forgot something.

Just in terms of terminology, what's the difference between a lambda expression or function, an anonymous/delegate function, and a closure?

Answer 1

You probably don't want to be referred to Alonzo Church's lambda calculus.

By far the most common notation for lambda functions is LISP.

Abelson & Sussman "Structure and Interpretation of Computer Programs" is probably the most accessible text that covers the subject, along with applications.

If you want to see where it started, dig out McCarthy's "Recursive Functions of Symbolic Expressions and Their Computation By Machine, Part I".

Answer 2

Learn a dialect of Lisp (Scheme is currently quite popular). In fact I afree with John's recommendation to read "Structure and Interpretation of Computer Programs" and learn Lisp along the way.

Lisp started out not as a programming language but a mathematical notation to describe computing. It was designed as something better to teach students than Turing machines (and if you've ever worked on a Turing machine you'd know how much they suck). The fact that Lisp code can be compiled and executed was an accident. The fact that Lisp is very close to lambda calculus (which was a different branch of mathematics) was also an accident (it was proven only much later after the language was designed).

Most of Lisp's abilities were not really "designed" into the language, not the same way as other language copying Lisp. They emerge out of the few simple rules Lisp was based on - just like theorems in math emerge out of the rules numbers are based on.

Answer 3

Have you looked at the Wikipedia page on Lambda calculus yet? It's heavier on math theory but eventually does get to more practical issues once you hit first class functions.

Answer 4

Asking for a language-agnostic treatment is a very severe restriction. I can recommend a couple of tutorials on the lambda calculus:

• A tutorial by R. Rojas focuses on getting quickly to the point of programming with lambda calculus.

• A tutorial by Prakash Panangden goes into a little more technical depth and ends by showing how you can simulate recursion using a fixed-point combinator.

If you want to understand the use of lambda and higher-order functions in programming, I think you are better off abandoning your agnosticism. A great paper for the ML/Hope/Miranda/Haskell family of languages is

• Why Functional Programming Matters by John Hughes. Hughes will show you some interesting use cases of higher-order functions and in general will do a good job helping you understand why people are interested in all this lambda stuff in the first place.

Answer 5

Just in terms of terminology, what's the difference between a lambda expression or function, an anonymous/delegate function, and a closure?

Regarding terminology:

• A lambda expression is the original way of writing an anonymous function invented by Alonzo Church for the lambda calculus. In the lambda calculus, all functions are pure: there are never any side effects.

  The lambda expression was adopted by McCarthy for LISP as (lambda (arguments ...) body), which is spelled "lambda". Sussman and Steele later made the semantics more faithful to Church's original. The expression was also adopted by Haskell as \ arguments ... -> body, and the backslash intended to look like a lambda, but the Haskell committee used a right arrow instead of a dot because they wanted the dot for function composition. The expression was adopted by Robin Milner for ML but is spelled even more strangely: fn args => body. All these expressions are properly called lambda expressions, and all represent anonymous functions. Only in Haskell are the functions pure; Lisp, ML, and Scheme all permit body to have side effects.

• A closure is what you get when you evaluate a lambda expression or other kind of nested function. The closure contains not just the compiled code for the lambda expression but also information about the free variables. (In Lisp and Scheme, the closure stores the locations of the free variables; in Haskell and ML, the closure stores the values of the free variables.)

• An anonymous function is a more general concept and need not be restricted to a simple binding and body. For example, in Smalltalk a "block" represents an anonymous function, but the body of a block is a sequence of statements, so it is definitely not the same as a lambda expression.

I'm afraid I can't help you with "delegate function;" in my world, that term is used to describe something else entirely.

Answer 6

You won't get too far into Lambda calculus without running into the related SKI combinator calculus, so you might as well dip your toe into that and get it over with. The delightful and strange To Disect a Mockingbird is, if not the best place to start, possibly the oddest. Your brain will feel like it's being rewired by an alien. Really.

Some crazy person implemented a language for the SKI calc., and it makes brainfsck seem like the best sex you ever had, by comparison anyhow. Here's an Unlambda program to print the Fibonacci numbers:

```s``s``sii`ki
  `k.*``s``s`ks
 ``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
  `k``s`ksk

Hey, don't blame me. I didn't invent it.

Things got even stranger when it was shown that a Perl regular expression in a loop could implement the SKI calculus, and therefore, that Perl regular expression in a loop is Turing complete.