Scheme and Functional Programming

Pure Scheme is a "functional" language. Rather than using assignment statements to modify "variables", a Pure Scheme program calls functions, which return values WITHOUT modifying the values of ANY variables.

  1. Easy to document and understand what each function does -- it returns a value which depends only on its arguments, which retain the same values they had before the function was called. So (msort L) = M, where {m in M} = {l in L}, and M[I-1] <= M[I]. A non-pure function (sort! L) exists which modifies its argument list L into sorted order. Its mathematical description is more complex.
  2. Allows Scheme to pass large structures "by value", without copying them (a slow operation). All Scheme arguments are evaluated, and a pointer to the evaluated argument is passed to the called function. This is in effect "call by reference", but because the called function can't change its arguments, it has the effect of call by value.
  3. Arrays in the conventional sense (an area of memory whose pieces can be changed by assignment) are not possible. However, one can write some functions that give the same effect as C array operations. This is done by returning a new array, with embedded modifications, whenever a C assignment to the array is to be emulated:

    4. (assgn A N x) returns an array B which agrees with A, except that B[N]=x:
    (define (assgn A N x) ( cond
    ( (= N 0) (cons x A) )
    ( else (cons (car A) (assgn (cdr A) (- N 1) x)) )
    ))

    [assgn isn't complete -- it should handle an array A with fewer than N elements reasonably -- often, by adding new null elements to A.]

    assgn, and its companion function (select A N), which returns the N-th element of array A, are slow. More complex structures for an array, such as a binary tree instead of a linear list, could speed up access and modification operations.

  4. Iteration is usually not present in functional languages, apparently because C-like iteration repeatedly sets an iteration variable to successive values of the iterate, and such "variable modification" isn't "functional". Recursion is used to allow repetitive execution of code.

Scheme is Turing Complete

A Turing Complete language is one that can express a program to compute any computable function. The following sketched procedure will develop a Scheme program to duplicate the computation of any C function subprogram (with arguments and results integers):

  1. Hand translate the C program into one that uses only if statements, goto statements, assignments, and function definitions and calls.
  2. Label every statement in the resulting program, P.

The Scheme program will define one function for each label in P. Function Ln will take as arguments every variable of P. Ln() will return the result P would return, if P were started at Ln, with each variable set to the values given by the arguments to Ln(). The construction is based on a case analysis, together with knowledge of which statement in P is the "successor" of every statement Li of P. Let V represent a list of every variable in P, and let V[x \ E] represent V, with E replacing the element corresponding to variable x in V:
  1. If Ln is "x = E( V )", and Li follows Ln in P, then
    (define (Ln V) (Li V[x \ (E V) ] ))

    2.  

  2. If Ln is "if T(V) then Li … else Lj", then
    (define (Ln V) (cond ((T V) (Li V)) (else (Lj V))))
  3. If Ln is "return y"
    (define (Ln V) y)

This construction works more simply, if Scheme is told to use "dynamic non-local reference resolution", which resolves a name y in function f() which is not the name of a parameter of f() to the binding of y most recently done dynamically. Then the vector V need list only the names of variables which are assigned to in the function being defined.

Example: Nth Fibbonacci number:

int Fibb(int N) {

int x, y;

L0: x=y=1;

L1: if (N==0) L2: return x;

else {

L3: t = x+y;

L4: y = x;

L5: x = t;

L6: N = N-1;}

goto L1;

}

Scheme version:

(define (fibb N) (L0 N))

(define (L0 N) (L1 N 1 1))

(define (L1 N x y) (cond ((= N 0) x) (else (L3 N x y)) ))

(define (L3 N x y) (L4 N x y (+ x y)))

(define (L4 N x y t) (L5 N x x t))

 

(define (L5 N x y t) (L6 N t y))

(define (L6 N x y) (L1 (- N 1) x y))

A simpler Scheme version:

(define (fibb N) (L1 N 1 1))

(define (L1 N x y) (cond

( (= N 0) x )

( else (L1 (- N 1) y (+ x y)) )

))

This version can be derived by grouping several C statements together, wherever a sequence of assignment statements occur which all depend on the common values of inputs to the group of statements. [None of these programs has been tested.]