Value-level programming: Encyclopedia II - Value-level programming - Connection with Lambda Calculus languages

Value-level programming - Connection with Lambda Calculus languages

Lambda calculus-based languages (such as Lisp, ISWIM, and Scheme) are in actual practice value-level languages, although they are not thus restricted by design.

To see why typical lambda style programs are primarily value-level, consider the usual definition of a value-to-value function, say

f = λx.E

here, x must be a value variable (since the argument of f is a value by definition) and E must denote a value too (since f's result is a value by definition). Typically, E is an expression involving the application of value-forming functions to value variables and constants; nevertheless, a few value-forming functions having both function and value arguments do exist and are used for limited purposes.

If the term values is defined to include the value variables themselves, then the value-level view of programming is one of building values by the application of existing programs (value-forming operations/functions) to other values. What lambda-style programming does, is to build a new program from the result-value by lambda-abstracting the value variables.

Adapted from the Wikipedia article "Connection with Lambda Calculus languages", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki