Lambda Calculus Lambda Calculus is the simplest general purpose programming lang
ID: 3833200 • Letter: L
Question
Lambda Calculus
Lambda Calculus is the simplest general purpose programming language. It is composed of general function abstractions known as lambda abstractions, variables, and function applica- tions. A lambda term may look as follows: (x.x) y. Computation is done with what is known as -reduction. In this case the y variable gets substituted in for x in the term inside of the parentheses wherever it occurs, in this case the one place, so we get the following (x.x) y y. If x occured multiple times in the lambda abstraction inside of the parenthesis we would get something different. For example (x.x x) y y y. To illuminate what is going on with this -reduction let us take a look at what is known as the parse trees for these expressions. We will use for lambda abstractions, A for applications, and the variables characters for the variables.
(x.x x) y
A
Ly
xA
xx
The reduction takes the y variable on the right part of top application (A), and substitutes it in for the variable x on wherever it occurs in the sub tree to the right of the L, so it would then output the following tree:
A
yy
1
2 Assignment
For this assignment, I want you to take in two lambda expressions from command line using the following syntax:
•
• (space applications) @
• variables characters from [a-z] • parens parens
So for some examples:
• x.x x x . x @ x
• (x.xx)y(x. x@x)@y
• (x.(y.y))z (x . (y . y)) @ z
It will then parse them into trees as seen on the first page.
If the first lambda expression given has a L, I want you to peform a reduction as if the second term is being applied to it, it will then output the lambda expressionto the command line:
Input:
x . x @ x y
Output: y@y
Explanation / Answer
In a functional program the result of a function call is uniquely determined by the actual values of the function arguments. No assignments are used, so no side-effects are possible. As a consequence, it makes no difference where and under what conditions a function is called. The result of a function will, under all conditions, be determined solely by the value of its arguments. For instance, in the program below the value printed will be 42 in both cases.
It is much easier to reason about the result produced by a function that has no side-effects than about the result of an imperative procedure call with side-effects.
Advantages of functional programming languages
So perhaps a functional programming style is important and side effects, and hence the assignment statement, should be abandoned. But why should we use a functional programming language? Is it not possible to use the familiar languages? The common imperative languages also have functions, so why not restrict ourselves and only use the functional subset of for instance C, Algol or Modula2?
Well, one can use the functional subset of imperative languages (i.e. only using functions and leaving out the assignment), but then one is deprived of the expressive power of the new generation of functional languages that treat functions as "first class citizens". In most imperative languages functions can only be used restrictively. An arbitrary function cannot be passed as an argument to a function nor yielded as result.
Functional programming languages have the advantage that they offer a general use of functions which is not available in classical imperative languages. This is a fact of life, not a fundamental problem. The restricted treatment of functions in imperative languages is due to the fact that when these languages were designed people simply did not know how to implement the general use of functions efficiently. It is also not easy to change the imperative languages afterwards. For instance, the type systems of these languages are not designed to handle these kinds of function. Also the compilers have to be changed dramatically.
Another advantage is that in most modern functional programming language(s) (FPLs) the functional programming style is guaranteed: the assignment statement is simply not available (like GOTOs are not available in decent modern imperative languages). FPLs in which there are no side-effects or imperative features of any kind are called pure functional languages. Examples of pure functional languages are Miranda, LML (Augustsson, 1984), HOPE (Burstall et al., 1980), Haskell (Hudak et al., 1992) and Concurrent Clean (Nöcker et al., 1991b). LISP (McCarthy, 1960) and ML (Harper et al., 1986) are examples of well known functional languages which are impure. From now on only pure aspects of FPLs are considered.
In functional programming the relevant notion of imperative programming are absent (or, in case they are present, have a different meaning).
In fact, the relevant notions of functional programming are:
In pure FPLs the programmer can only define functions that compute values uniquely determined by the values of their arguments. The assignment statement is not available, and nor is the heavily used programming notion of a variable as something that holds a value that is changed from time to time by an assignment. Rather, the variables that exist in purely functional languages are used in mathematics to name and refer to a yet unknown constant value. This value can never be altered. In a functional style a desired computation is expressed in a static fashion instead of a dynamic one. Due to the absence of side-effects, program correctness proofs are easier than for imperative languages (see Section 11). Functions can be evaluated in any order, which makes FPLs suitable for parallel evaluation (see Section 6). Furthermore, the guaranteed absence of side-effects enables certain kinds of static analysis of a program. analysis.
Besides the full availability of functions, the new generation functional languages also offer an elegant, user-friendly notation. Patterns and guards provide the user with simple access to complex data structures; basically one does not have to worry about memory management any more. Incorrect access of data structures is impossible. Functional programs are in general much shorter than their conventional counterparts and thus in principle easier to enhance and maintain.
The question arises, is it possible to express any possible computation by using pure functions only? Fortunately, this question has already been answered years ago. One of the greatest advantages of functional languages is that they are based on a sound and well-understood mathematical model of computation: the -calculus (Church, 1932; 1933).
One could say that functional languages are sugared versions of this calculus. The -calculus was introduced at approximately the same time as the Turing model (Turing, 1937). Church’s thesis (Church, 1936) states that the class of effectively computable functions, i.e. the functions that intuitively can be computed, is the same as the class of functions that can be defined in the -calculus. Turing formalized machine computability and showed that the resulting notion of Turing computability is equivalent to -definability. So the power of both models is the same. Hence any computation can be expressed using a functional style only.
Disadvantages of functional programming languages
The advantages mentioned above are very important. But although functional languages are being used more frequently, in particular as a language for rapid prototyping and as a language in which students learn how to program, functional languages are not yet commonly used for general purpose programming. The two main drawbacks lie in the fields of
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.