Session 12 : Function Programming Language

Mathematical Functions

A mathematical function is a mapping of members of one set, called the domain set, to another set, called the range set. One of the fundamental characteristics of mathematical functions is that the evaluation order of their mapping expressions is controlled by recursion and conditional expressions, rather than by the sequencing and iterative repetition that are common to the imperative programming languages. Another important characteristic of mathematical functions is that because they have no side effects and cannot depend on any external values, they always map a particular element of the domain to the same element of the range. However, a subprogram in an imperative language may depend on the current values of several nonlocal or global variables. This makes it difficult to determine statically what values the subprogram will produce and what side effects it will have on a particular execution. A mathematical function maps its parameter(s) to a value (or values), rather than specifying a sequence of operations on values in memory to produce a value.

Lambda Expression

A lambda expression specifies the parameters and the mapping of a function. The lambda expression is the function itself, which is nameless.

example:

(

(l (x)x * x * x)(2)

 which results in the value 8.

Lambda expressions, like other function definitions, can have more than one parameter.

Functional Form

A higher-order function, or functional form, is one that either takes one or more functions as parameters or yields a function as its result, or both.

One common kind of functional form is function composition, which has two functional parameters and yields a function whose value is the first actual parameter function applied to the result of the second. Function composition is written as an expression, using ° as an operator, as in

h º f ° g

For example, if

f(x) º x + 2

g(x) º 3 * x

then h is defined as

h(x) º f(g(x)), or h(x) º (3 * x) + 2

Apply-to-all is a functional form that takes a single function as a parameter. 1 If applied to a list of arguments, apply-to-all applies its functional parameter to each of the values in the list argument and collects the results in a list or sequence. Apply-to all is denoted by a. Consider the following example:

Let

h(x) º x * x

then

a (h, (2, 3, 4)) yields (4, 9, 16)

The First Functional Programming Language: LISP

*LISP Data Types and Structures

There were only two categories of data objects in the original LISP: atoms and lists. List elements are pairs, where the first part is the data of the element, which is a pointer to either an atom or a nested list. The second part of a pair can be a pointer to an atom, a pointer to another element, or the empty list. Elements are linked together in lists with the second parts. Atoms and lists arenot types in the sense that imperative languages have types. In fact, the original LISP was a typeless language. Atoms are either symbols, in the form of identifiers, or numeric literals. Internally, a list is usually stored as linked list structure in which each node has two pointers, one to reference the data of the node and the other to form the linked list. A list is referenced by a pointer to its first element. Note that the elements of a list are shown horizontally. The last element of a list has no successor, so its link is nil. Sublists are shown with the same structure.

*LISP Interpretation

The original intent of LISP’s design was to have a notation for programs that would be as close to Fortran’s as possible, with additions when necessary. This notation was called M-notation, for meta notation. There was to be a compiler that would translate programs written in M-notation into semantically equivalent machine code programs for the IBM 704.

Lambda notation is used to specify functions and function definitions. Function applications and data have the same form.

            e.g., If the list (A B C) is interpreted as data it is

            a simple list of three atoms, A, B, and C

            If it is interpreted as a function application,

            it means that the function named A is

            applied to the two parameters, B and C

Scheme

*Origins of Scheme

The Scheme language, which is a dialect of LISP, was developed at MIT in the mid-1970s (Sussman and Steele, 1975). It is characterized by its small size, its exclusive use of static scoping, and its treatment of functions as first-class entities. As first-class entities, Scheme functions can be the values of expressions, elements of lists, passed as parameters, and returned from functions. Early versions of LISP did not provide all of these capabilities.

As an essentially typeless small language with simple syntax and semantics, Scheme is well suited to educational applications, such as courses in functional programming, and also to general introductions to programming.

Most of the Scheme code in the following sections would require only minor modifications to be converted to LISP code.

*The Scheme Interpreter

A Scheme interpreter in interactive mode is an infinite read-evaluate-print loop (often abbreviated as REPL). It repeatedly reads an expression typed by the user (in the form of a list), interprets the expression, and displays the resulting value. This form of interpreter is also used by Ruby and Python. Expressions are interpreted by the function EVAL. Literals evaluate to themselves. So, if you type a number to the interpreter, it simply displays the number. Expressions that are calls to primitive functions are evaluated in the following way: First, each of the parameter expressions is evaluated, in no particular order. Then, the primitive function is applied to the parameter values, and the resulting value is displayed. Scheme programs that are stored in files can be loaded and interpreted. Comments in Scheme are any text following a semicolon on any line.