Lambda — λ

Alonzo Church attempted to use functions as a foundation for logic. This did not work out as planned but his book has nonetheless had great impact on math and computer science. In the book he borrows and adapts a function notation from Whitehead and Russell’s “Principia Mathematica”. Perhaps first in LISP and then later more faithfully in Scheme Church’s notation and notions blossomed into a full-fledged foundation for computation.

The CS ‘closure’ notion is closely associated with the first class function. (elaborate!)

The first Fortran provided only a few built in functions such as square root. The Fortran programmer had to pass arguments and results in global variables and arrange to do a computed return in order to define his own function. Fortran II allowed the programmer to define a function with real parameters and to return an answer using the same invocation syntax as the square root function.

Here are three significant features of functional programming:

  1. Nested scoping wherein the definition of a function can be nested in a scope whose local variables are accessible in the body of the function definition.
  2. Permanency wherein a function remains invocable even after the environment where it was born has been retired, such as by returning from a routine whose local variables are referenced by the function.
  3. Anonymous functions which need no name, just as the value 5 needs no name in the expression (2+3)*7.
Common LISP, Scheme, OCaml, JavaScript all provide all three. Feature 2 is difficult or impossible without some sort of garbage collection, but see block below. The language C has none of these features but gcc and a few followers have nested functions which give you feature 1. Algol, Pascal, PL/I and gcc all provide feature 1. Algol 68 provides 1 and 3.

Apple blocks provides the functionality of all three features without garbage collection, but with a somewhat awkward syntax and semantics.

Here are three small programs that both gcc 4.2.1 and clang 3.0 approve of: 

#include <stdio.h>
int main(){int x = 123;
void(^p)(int) = ^(int y){printf("%d %d\n", x, y);};
p(456);
return 0;}

#include <stdio.h>
int main(){int x = 123;
(^(int y){printf("%d %d\n", x, y);})(456);
return 0;}

#include <stdio.h>
typedef void t(int);
t^ u;
void r(int y){int x = 123; u = ^(int y){printf("%d %d\n", x, y);};}
int main(){r(42); u(456); return 0;}
They all print “123 456”. x is read-only in the inner scopes however, unlike nested functions. I wish I knew what ‘^’ means! Perhaps it is a throwback to the notation “x̂(x+2)” of Principia Mathematica which means λx(x+2). The last example returns a routine via the global variable u, but cannot return a function the normal way: 
#include <stdio.h>
typedef void t(int);
t r(int y){int x = 123; return ^(int y){printf("%d %d\n", x, y);};}
int main(){t e = r(42); e(456); return 0;}
Both gcc and clang recoil at a function returning a function. I can’t imagine why.

You can pass a block as argument between these two separately compiled routines: 

typedef void(^p)(int);
void rou(p u){u(3);}

#include 
typedef void(^p)(int);
void rou(p);
int main(){rou(^(int y){printf("%d\n", y);});
  return 0;}