What language features can't be defined in terms of lambda?

Question

It seems like lambda can be used for almost anything (even if it seems more complicated), but it does have its limitations.

What are some use cases not covered by lambda?

Answer 1

A lambda (i.e. a function) by itself is not very interesting. Here's a function in JavaScript:

function id(x) {
    return x;
}

What does this JavaScript program do? Nothing.

However, functions have a dangerous property of being invokable.

When invoked, a function can potentially do anything (conditions apply):

authorize_nuclear_attack(launch_codes); // oops

Hence, trivially a lambda can potentially do anything.

Think about it, every C program is a function called main.

But Aadit, you would need some other language feature to implement the body of a lambda.

1. How would you declare, define, update and valuate variables?
2. How would you make decisions without using an if statement?
3. How would you repeat a block of code an arbitrary number of times without a for loop?
4. How would you write a sequential block of code without a sequencing operator?
5. How would you add two numbers without using a primitive + operator?

How?

Indeed. The power to create new functions (i.e. lambda abstraction) and the power to invoke functions (i.e. lambda application) is not enough to write entire programs.

However, it's pretty darn close to enough.

The only other language feature that we absolutely require to write any program (and I do mean any program) is the power to get the value of a variable (i.e. valuation).

Every other language feature is:

1. Either inherent in one of these three features.
2. Or can be derived from these three features.

Let's consider:

1. The power to declare variables is inherent in lambda abstraction:

   function id(x) { // declare variable x
       return x;    // valuate variable x
   }
   

2. The power to define variables (and update viz-a-viz recursion) is inherent in lambda application:

   id(something);   // let x := something in the body of the function id
   

3. The power to make decisions can be derived from lambda abstraction and selective valuation:

   function boolean_true(then_branch, else_branch) {
       return then_branch;
   }
   
   function boolean_false(then_branch, else_branch) {
       return else_branch;
   }
   
   function if_statement(boolean_condition, then_branch, else_branch) {
       return boolean_condition(then_branch, else_branch);
   }
   

4. The power to repeat can be derived by “eating your own tail” as follows:

   function dragon(dragon) {
       return dragon(dragon); // infinite loop
   }
   
   dragon(dragon);
   

   I am of course referring to the ouroboros dragon:

   

   Imagine the dragon spinning like a wheel forever, trying to eat its own tail. An infinite loop.

   It's also possible to create a terminating loop using selective valuation (a.k.a. branching).

5. The power to sequence operations can be derived by composing functions:

   function substitution(f, g) { // S combinator from SKI combinator calculus
       return function (x) {
           return f(x, g(x));
       };
   }
   
   // substitution(f, g) is equivalent to (statement g; statement f)
   // where the semicolon is the sequencing operator like in C
   

6. The power to add two numbers can derived by encoding numbers as functions:

   function zero(f, x) {         // 0
       return x;
   }
   
   function add1(n) {            // n + 1
       return function (f, x) {
           return f(n(f, x));
       };
   }
   
   function add(m, n) {          // m + n
       return function (f, x) {
           return m(f, n(f, x));
       };
   }
   

To reiterate, the power to create new function (i.e. lambda abstraction), the power to invoke functions (i.e. lambda application) and the power to get the value of a variable (i.e. valuation) together allow you to write every possible program that you can write using any other language such as C or Java.

Lambda calculus captures the notion of computability.

This means that every algorithm or semi-algorithm can be expressed in the lambda calculus (i.e. the solution of every problem that can be solved or the partial solution of every problem that can be partially solved can be expressed in the lambda calculus).

It seems like lambda can be used for almost anything (even if it seems more complicated), but it does have its limitations.

The only limitation of the lambda calculus is that you can't express solutions to problems for which there are no solutions (not even partial solutions). An example of such a problem is, “given a program P does P halt on all inputs?”

In other words, it is impossible to write a function H such that H(P) = true if P halts on all inputs, and H(P) = false otherwise. If you do manage to write the function H then it would always be incorrect for the following program:

function P(x) {
    return H(P) ? P(x) : x;
}

If H thinks that P always halts then P goes into an infinite loop.

If H thinks that P doesn't always halt then it always halts.

What are some use cases not covered by lambda?

The only use case not covered by the lambda calculus is being able to compute uncomputable functions. However, because uncomputable functions are a tad bit uncomputable I would say that there are no use cases which are not covered by the lambda calculus.

That being said, nobody uses the lambda calculus to do any actual programming (just like nobody uses a Turing machine as an actual computer). Both the lambda calculus and Turing machines are equal in power. However, they are very different beasts.

Most imperative programming languages like C and Java are based on the Turing machine. Most functional programming languages like Haskell and OCaml are based on the lambda calculus. A good programmer is an expert at either one but not the other. A great programmer is comfortable with both.