Another approach is based on the idea that the problems mentioned above are fundamental problems that cannot be solved unless a totally different approach is used and hardware and software are designed with a completely different model of computation in mind.

2.  An imperative programming style

   Most computer programs are written in an imperative programming language in which algorithms are expressed by a sequence of commands.
These languages, such as FORTRAN, C, Algol, COBOL, PL/1 and Pascal, are originally deduced from (and form an abstraction of) the computer architectures they are running on. These computer architectures, although different in detail, are all based on the same architecture: the Von Neumann computer architecture. The Von Neumann computer architecture is based on the mathematical model of computation proposed by Turing in 1937: the Turing machine.

Imperative programming languages are those based on the Turing-machine model of computation.
The fundamental concepts in imperative programming languages (coming from the Turing Machine model) are:

• store
• variable - something it is possible to modify ("memory cell")
• assignment
• iteration

   The great advantage of the Turing model and hence of the corresponding phisical architectures is that they are extremely simple. The Von Neumann architecture consists of a piece of memory that contains information that can be read and changed by a central processing unit (the CPU). Conceptually there are two kinds of information: program instructions in the form of machine code, information that is interpreted by the CPU and that controls the computation in the computer; and data, information that is manipulated by the program.
   This simple concept has made it possible to make efficient realizations in hardware at a relatively low cost. In the beginning of the computer era, the ‘high-level’ imperative programming languages were designed to provide a notation to express computations in a machine-independent way. Later on, one recognized the importance of expressing computations such that programs are understandable for the human being and their correctness can be proven. It became clear that, in order to make it possible to reason about programs, not every machine instruction should have a direct equivalent in the high-level programming language. For instance, it is common knowledge that with the use of GOTO statements, which are the direct abstraction of the branch and jump instructions that are available on any computer, programs can be written in such a way that reasoning about them is almost impossible (Dijkstra, 1968). We strongly believe that a similar kind of problem is caused by the assignment statement.

Consider the following example written in an imperative programming style:

BOOLEAN even := TRUE;
…
PROCEDURE calculate (INTEGER value) : INTEGER;
BEGIN
 even := NOT even;
 IF even
  THEN value + 1
  ELSE value + 2
 ENDIF
END;
…
print(calculate (6));
…
print(calculate (6));

One of the most important drawbacks of an imperative programming style is that an imperative program consists of a sequence of commands of which the dynamic behaviour must be known to understand how such a program works. The assignment causes problems because it changes the value (and often even the meaning) of a variable. Owing to side-effects it can happen that evaluating the same expression in succession produces different answers. Reasoning about the correctness of an imperative program is therefore very difficult.

Furthermore, because of the command sequence, algorithms are more sequential than is necessary. Therefore it is hard to detect which parts of the algorithm can or cannot be executed concurrently. This is a pity, since concurrent evaluation seems to be a natural way to increase execution speed.
A conjecture adopted by many researchers nowadays is that the software crisis and the speed problem are inherent to the nature of imperative programming languages and the underlying model of computation. Therefore, other styles of programming, such as object oriented, logical and functional styles of programming are investigated.

3.  A functional programming style

   John Backus (1978) pointed out that the solution for the software problems has to be found in using a new discipline of programming: a functional programming style instead of an imperative one.
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.

FUNCTION increment (INTEGER value) : INTEGER;
BEGIN
value + 1
END;
…
print(increment (41));
…
print(increment (41));

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 wellknown 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:

• expression
• recursion - different from the notion of iteration
• evaluation - different from the notion of execution (when we evaluate a mathematical expression we do not modify anything)
• variable - intended in a mathematical sense (unknown entity, abstraction from a concrete value)

   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

4.  Functions in mathematics and functions as programs

   In mathematics, there are several ways to define a function. The type of a function can be specified separately from the function definition. One way to define a function is by explicit enumeration of all objects in the domain on which the function is defined with their corresponding images. An example of this is the following partial function (domain names Z and N are used for the domains of integers and natural numbers).

abs: Z → N
abs(–1) = 1
abs( 0) = 0
abs( 1) = 1

   Another way to define functions is by using definitions that consist of one or more (recursive) equations. For example, with this method the abs-function above can easily be defined as a total function, applicable for all objects in the domain. Of course, the functions and operators used on the right-hand side must be defined on the appropriate domains.

abs: Ζ → Ν
abs(n) = n, n > 0
          = 0, n = 0
          = –n, n < 0

A function like factorial can be defined as follows:

fac: Ν → Ν
fac(n) = 1, n = 0
fac= n * fac (n – 1), n > 0

or an alternative definition method is:

fac: Ν → Ν
fac(n) = if (n=0) then 1 else n * fac (n – 1)

   A mathematician would consider the definitions above as very common, ordinary function definitions. But these examples are also perfect examples of function definitions in a functional programming language. Notationally a function definition in a functional language has many similarities with a function definition in mathematics. However, there is an important difference in objective. The objective in a functional language is not only to define a function, but also to define a computation that automatically computes the image (result) of a function when it is applied to a specific object in its domain (the actual argument of the function).
Some function definitions, well-defined from a mathematical point of view, cannot be defined similarly in a functional language, because the images of some functions are very difficult to compute or even cannot be computed at all.

Consider, for example, the following function definition:

halting: All_Programs → Ν
halting(p) = 1, if the execution of p will stop
                       0, otherwise

The halting function as indicated above is a problem that is not computable, and therefore an attempt to express it will not produce the desired computation. Suppose that a function in an FPL would try to calculate the image of the halting function for an arbitrary program. The only way of doing this is more or less running the program. But then the function would simply not terminate if the argument program does not terminate, in which case the result 0 would never be produced.

For another example, consider:

f: R → R ,   g: R -> R
f '' - 6g' = 6 sen x
6g'' + a² f ' = 6 cos x
f(0) = 0,  f '(0) = 0,  g(0) = 1,  g'(0) = 1

The equations for f, g and their derivatives f ', f '', g' and g'' are solvable, but it is not easy to compute such functions.

    Some special purpose programming languages are able to calculate functions by applying special purpose calculation techniques (symbolic computation using computer algebra techniques or formula transformations). But a general purpose functional programming language uses a very simple model of computation, based on substitution. So when functions are defined in an FPL a computation through substitutions is defined implicitly (see Section 6).

In a sense, a function definition in a FPL, besides identifying a precise mathematical functions, implicitely describes a way to compute it (an algorithm).

5.  Functional programs

A program written in a functional language consists of a collection of function definitions, possibly recursive, and an initial expression that has to be evaluated.

From now, for our running examples, we shall use the functional programming language SCHEME.

In Scheme a function definition consists in an expression of the form

(define (function-name arg1 .. argn) body)

(f a)

(define (ident x)  x)   
;; the identity function on numbers

(define (alwaysseven x) 7)  
;;  a function from num to num that yields 7, 
;; independent of arg. x

(define (inc x) (+ x 1))  
;;  a function that returns the value of its arg. + 1

(define (square x) (* x x))  
;; square function

(define (squareinc x) (square (inc x)))     
;; square increment of argument

(define (fac x) (if (= x 0) 1 (* x (fac (- x 1)))))   
;; the factorial function

(+ 2 3)

(squareinc 5)

6.  The evaluation of a functional program

   The execution of a functional program consists of the evaluation of the initial expression in the context of the function definitions the program is made of, such a context is called the environment.

   An example of functional program: a set of function definitions and an initial expression.

(define (ident x)  x)   

(define (inc x) (+ x 1)) 

(define (square x) (* x x)) 

(define (squareinc x) (square (inc x))) 

(squareinc 7)

> (squareinc 7)
64
> 

   For instance, given the function definitions above (the environment), the initial expressions below can be evaluated (reduced) as follows. In the examples the redex that will be reduced has been underlined.

(ident 42) → 42

(square (+ 1 2)) → (square 3 3) → (* 3 3) → 9

(squareinc 7) → (square (inc 7) → (square (+ 7 1)) → (square 8) → (*8 8) → 64

However, the initial expression may not have a normal form at all. As a consequence, the evaluation of such an initial expression will not terminate. In some functional languages (not in Scheme), infinite computations may produce partial results that will be printed as soon as they are known.

Example of a non-terminating reduction. Take the following definition:

(define (inf x) (inf x))

7.  The order of evaluation

   Because there are in general many redexes in one expression, one can perform rewrite steps in several orders. The actual order of evaluation is determined by the reduction strategy which is dependent on the kind of language being used. A reduction strategy is a policy used by an interpreter to choose the next redex to be reduced among the many possible ones.

   There is a very important things to know about the ordering of reduction steps. Due to the absence of side-effects, the result of a computation does not depend on the chosen order of reduction. If all redexes are vanished and the initial expression is in normal form, the result of the computation (if any) will always be the same: the normal form is unique (see The Confluence Property and its Corollary, in Section 13, for a formal proof of this fact).
For instance, one can compute one of the previous expressions in a different order, but the result is identical:

(square (+ 1 2)) → (* (1 + 2) (1 + 2)) → (* 3 (1 + 2)) → (* 3 3) → 9

   It is sometimes even possible to rewrite several redexes at the same time. This forms the basis for parallel evaluation.
Reducing several redexes at the same time:

(square (+ 1 2)) → (* (+1 2) (+1 2)) → (* 3 3) → 9


   However, the order is not completely irrelevant. Some reduction orders may not lead to the normal form at all. So a computation may not terminate in one particular order while it would terminate when the right order was chosen.

Example of a non-terminating reduction order.
Assume that the following (recursive) functions are defined:

(define (inf x) (inf x))

(define (alwaysseven x) 7)

   The reduction strategy followed by the interpreter depends on the kind of Functional Programming Language. In some languages, e.g. LISP, ML and HOPE, the arguments of a function are always reduced before the function application itself is considered as a redex. These languages are called eager or strict languages. The reduction strategies they use are called call-by-value strategies.
In most recent FPLs, e.g. Miranda and Haskell, the rewriting is done lazily. In lazy functional languages the value of a subexpression (redex) is calculated if and only if this value must be known to find the normal form. The lazy evaluation order will find the normal form if it exists. The strategies used by such languages belong to the class of call-by-name strategies.

Illustrating lazy rewriting:

(alwaysseven (inf 2)) → 7


   A more complex example to illustrate lazy evaluation is shown below. It is the sort of evaluation that is performed by interpreters like the one of Haskell.
The predefined conditional function demands the evaluation of its first argument to make a choice between the then and else parts possible. The equality function forces evaluation in order to yield the appropriate Boolean value. Multiplication and subtraction are only possible on numbers; again evaluation is forced.

(fac 2)
→ (if (= 2 0) 1 (* 2 (fac (- 2 1))))
→ (if FALSE 1 (* 2 (fac (- 2 1))))
→ (* 2 (fac (- 2 1)))
→ (* 2 (if (= (- 2 1) 0) 1 (* (- 2 1) (fac (- (- 2 1) 1)))))
→ (* 2 (if (= 1 0) 1 (* (- 2 1) (fac (- (- 2 1) 1)))))
→ (* 2 (if FALSE 1 (* (- 2 1) (fac (- (- 2 1) 1)))))
→ (* 2 (* (- 2 1) (fac (- (- 2 1) 1))))
→ (* 2 (* 1 (fac (- (- 2 1) 1))))
→ (* 2 (*1 (fac (- (- 2 1) 1)))))
→ (* 2 (*1 (if (= (- (- (- 2 1) 1)) 0) 1 (* (- (- 2 1) 1) (fac (- (- (- 2 1) 1) 1)))))))
→ ... → (* 2 (* 1 1)) → (* 2 1) → 2

   Scheme is a strict language. It evaluates expressions using a call-by-value reduction strategy, that means that the application of a function to an argument is a redex only if the argument is a value.
Let us see how the Scheme interpreter evaluates the expression (fac 2).

(fac 2)
→ (if (= 2 0) 1 (* 2 (fac (- 2 1))))
→ (if FALSE 1 (* 2 (fac (- 2 1))))
→ (* 2 (fac (- 2 1)))
→ (* 2 (fac 1))
→ (* 2 (if (= 1 0) 1 (* 1 (fac (- 1 1)))))
→ (* 2 (if FALSE 1 (* 1 (fac (- 1 1))))))
→ (* 2 (* 1 (fac 0)))
→ (* 2 (* 1 (if (= 0 0) 1 (* 0 (fac (- 0 1)))))))
→ (* 2 (* 1 (if TRUE 1 (* 0 (fac (- 0 1)))))))
→ (* 2 (* 1 1)))
→ (* 2 1) → 2

Notice how, also in languages like Scheme, the arguments of the conditional operator if, are not both evaluated before the application of if, since otherwise the computation would never stop.

8.  Recursion

   In imperative languages the most relevant control structure is iteration. In functional languages, instead, it is recursion that gives computational power to programs. Without recursion we could compute almost nothing in pure functional languages.

Recursion is a naturally applied process to define functions on recursively defined data (called also inductively defined data or algebraic data).

Defining recursive functions, rough intuition: A rough idea of how we can look at a recursive function definition is the following one.
When we define a function by recursion we first try to look at the elements of the domain as "built" out of "simpler" parts (or you can think about it in terms of "smaller" parts). Then we try to express the value of the function on a generic element in terms of the value of the function on its "simpler" parts.
We need also to provide the value of the function on the "simplest" ("smallest") elements.
We must also be sure that, starting from a generic element, it is not possible to go on getting simpler and simpler (smaller and smaller) elements for ever.

   The easiest inductive data are obviously the natural numbers: a natural number is zero or the successo of a natural number (you see, a recursively define data type). So Natural Numbers have only one base element (zero) and a unary constructor (the successor operator).

   Let us define a simple recursive function on numbers, which sums up all the natural numbers from n downto 0.

(define (sumdowntozero n)
      (if (= n 0)
          0
          (+ n (sumdowntozero (- n 1)))))

   You notice that the base case is 0, but it could be different, like in this other example, where we sum up all the numbers in the interval [from..to], starting from the bigger one.

(define (sumdownto from to)
      (if (= from to)
          from 
          (+ to  (sumdownto from (- to 1)))))

   Notice that we have always in mind that a recursive function must have the recursive calls performed on "smaller elements". For numerical inputs this means "smaller numbers".

But then, what about the following function, which returns the same result as the previous function?

(define (sumfromupto from to)
      (if (= from to)
          to
          (+ from (sumfromupto (+ from 1) to))))

Well, it works. And it is still true that recursive calls are on "smaller" elements down to the base case. It is just that now the relation of "smaller" is not the usual one on natural numbers (actually is the opposite relation). We could be more precise if we studied well-founded sets.

9.  Higher-order functions

   Compared with the traditional imperative languages, which normally allow also the declaration of functions, functional programming languages have a more general view of the concept of functions: they are treated as ‘first-class citizens’, i.e. functions are treated just like other objects in the language. As a consequence, functions can have functions as arguments and as results.

Functions that have functions as actual arguments or yield a function as result are called higher-order functions, in contrast to first-order functions, which have only non-function values as argument or as result.

Example of a higher order function that takes a function as argument:

(define (atzero f) (f 0))

   In order to better understand the notion of higher-order functions, let us see a few functions that take functions as arguments.
Let g be a function on natural numbers, g: N -> N, which we assume to be computed by a Scheme function called G already defined.
We want to write a program that takes a natural number n as input and computes the sum, for i = 1... n, of the g(i)'s.

(define (SG n) 
    (if (= n 0) 
        0 
        (+ (G n) (SG (- n 1)))))

   The program PG that, instead, computes the product of the elements g(i)'s, will be:

(define (PG n) 
    (if (= n 0) 
        1 
        (* (G n) (PG (- n 1))))) 

   Both the above programs can be generalized. Let us define the functions Sgen and Pgen that, besides taking as input a natural number n, take also the function on which the sums or the products are performed.

(define (Sgen f n) 
    (if (= n 0) 
        0 
        (+ (f n) (Sgen f (- n 1))))) 

(define (Pgen f n) 
    (if (= n 0) 
        1 
        (* (f n) (Pgen f (- n 1))))) 

Now, to compute the sum or the product of g(i) for i =1 ...10, we have simply to evaluate the initial expression (Pgen G 10) or (Sgen G 10).

   We try now to generalize further, so we abstract both from the binary function applied to the various f(i)'s, and from the base index. (Example: the computing F for i=3..5 of f(i) corresponds to F(F(f(3),f(4)),f(5))   the following function do it in general)

(define (Ftoria F f b n) 
    (if (= n b) 
        (f b) 
        (F (f n) (Ftoria F f b (- n 1)))))

   Now with this new function at hand we can easily define Sgen and Pgen as follows

(define (Sgen f n) 
    (Ftoria + f 0 n)) 

(define (Pgen f n) 
    (Ftoria * f 0 n))

   We could also generalize Ftoria further, by abstracting on the predecessor function for the linear order over the finite set over which f is defined, and over the equality relation on the element of the set:

(define (FtoriaOrd F f low up pred eq) 
    (if (eq up low) 
        (f up) 
        (F (f up) (Ftoria F f low (pred up) eq)))) 

Well... maybe with FtoriaOrd we have gone a bit too far with the generalization... but you have noticed how very general functions can be defined and how other functions can be easily defined out of them.

   It is possible to have functions in which both arguments and result are functions.
One example is the function compose: it takes two functions as input and returns their compositions.
Notice that in order to define the function compose we need to be able to write expression representing a function, without having to give a name to it. That is we need to be able to describe anonymous functions, functions without a name.
In Scheme the syntax for anonymous functions is the following one:

(lambda (arg1...argn) body)

We can now easily define the compose function

(define (compose f g)
  (lambda (x) (f (g x))))

   By means of anonymous functions we are also able to define Sgen using FtoriaOrd, in the following way.

(define (Sgen f n) 
    (FtoriaOrd + f 1 n (lambda (x)(- x 1)) =))

   One more example: we define a higher-order function returning a function (from natural numbers to natural numbers) identical to the one given as argument, but in a point, for which a new value is provided.

(define (change-value-at-n  f  n  new-value)
    (lambda (x)
        (if (= x n)
            new-value
            (f x))))

Definitions
   Up to now we have used the define-expressions to define functions. Actually the keyword 'define' can be used in general to associate, in the environment, a name to any value of Scheme.

(define a (+ 3 4))

(* a 2)

(define name expr)

(define (function-name arg1 .. argn) body)

(define function-name (lambda (arg1 .. argn) body))

10.  Data Structures: Lists

   In imperative languages one can define global data structures that are globally accessible for reading and writing during execution. Since this is not possible in functional languages, the use of data structures in these languages is quite different. After creation of a data structure, the only possible access is read access. Data structures cannot be overwritten. Furthermore, data structures are not globally available but they must always be passed as arguments to the functions that need them. Modern functional languages allow the definition of complex data structures.
In this section we treat list. Lists is a data structure which is predefined in all the functional programming languages. Lists are recursive data structures, in fact the definition of list is recursive: A list is either the empty list or it is formed by an element followed by a list. It is then obvious that lists, since they are a recursively defined data structure, can be easily handled by means of recursion, the main control mechanism of functional languages.
In Scheme lists are not uniform, i.e. it is possible to have lists of elements of different types, unlike many other functional languages, like Haskell.

   Lists, like any data structure in an FPL, are built using data constructors. Lists are constructed using two data constructors. A constant data constructor denoting the emplylist: empty (in certain implementation we can also denote the emptylist with '() ), and a constructor, cons that, taken a value v and a list L returns the list formed by v followed by L.

The expression

(cons 1 (cons 2 (cons 3 empty)))

(cons #t (cons #t (cons #f (cons #t empty))))

(cons #t (cons 2 (cons #f empty)))

(list 1 2 3)

(list #t #t #f #t)

(list #t 2 #f)

(cons 3 (cons (cons 2 (cons #t empty)) (cons #f empty)))

(list 3 (list 2 #t) #f)

   Of course we can give names to lists by means of define-expressions

(define Karaosmanglu 
   (cons 3 (cons (cons 2 (cons #t empty)) (cons #f empty))))

(define Pamuk (list #t 2 #f))

   We can "build" list by means of constructors, but if we wish them to be of any use we need to be able to handle the parts they are made of. For these purpose there are the following predefined selectors: car and cdr.
car is an operator that takes a list in input and returns its first element. cdr takes a list and returns a list like the one in input, but without the first element.

(car (list 1 2 3 4 5 6))

(car Pamuk)

(cdr Pamuk) 

This way of handling lists is very user-friendly. One does not need to worry about ‘memory management’ nor about ‘updating pointers’.

In order to handle lists in programs, we need also predicates on them.
A predicate is a function that returns boolean values (by notational convention in Scheme the name of a predicate always terminates with the character '?'). In Scheme the predefined predicate on lists is null?. When applied to a list it returns #t if and only if the argument is the emptylist. It will be very useful in defining recursive functions on lists.

Let us now write a few recursive programs dealing with lists.

Recursion on (flat) lists

    By a flat list we mean a list were no element in it is a list.

Let us see the apnd function that concatenates two lists given in input (we call it "apnd" since the function "append" is predefined in most Scheme implementations).

 (define  apnd (lambda ( ls1 ls2 )
     ( if  (null? ls1)
           ls2
           ( cons (car ls1) (apnd (cdr ls1 ) ls2)) )))

Exercise: Program the reverse function.

The apnd function is an example of function defined by recursion on the lenght of the list, this informally means that the recursive calls are on shorter lists than the input one.

Let's define the function (predicate) member?. It checks whether a number is in the list of numbers given as input. .

(define (member? elem ls)
    (if (null? ls)
        #f
        (if (= elem (car ls))
            #t
           (member? elem (cdr ls)))))

(define (member? elem ls)
   (and (not (null? ls)
        (or (= elem (car ls))
            (member? elem (cdr ls))))))
 

(define (Sumlist ls)
     (if (null? ls)
         0
         (+ (car ls) (Sumlist (cdr ls)))))

(define (Sumlistweird ls)
     (cond ((null? ls) 0)
           ((= (car ls) 0) (Sumlistweird (cdr ls)))
           (else (+ 1 
	            (Sumlistweird (cons (- (car ls) 1) 
		                        (cdr ls)))))))

(define (Sumlistlist lsls)
    (if (null? lsls)
        0
        (if (null? (car lsls))
            (Sumlistlist (cdr lsls))
            (+ (caar lsls) 
	       (Sumlistlist (cons (cdar lsls) 
	                           (cdr lsls)))))))

(define (Sumlslsweird ls)
   (cond ((null? ls) 0)
         ((null? (car ls)) (Sumlslsweird (cdr ls)))
         ((= (caar ls) 0) (Sumlslsweird (cons (cdar ls) 
	                                      (cdr ls))))
         ( else (+ 1 
	        (Sumlslsweird (cons (cons (- (caar ls) 1) 
		                          (cdar ls)) 
                                    (cdr ls)))))))

(define (genmember? elem ls)
    (if (null? ls)
         #f
        (if (list? (car ls))
            (or (genmember? elem (car ls))
                (genmember? elem (cdr ls)) )
            (or (eqv? elem (car ls))
                (genmember? elem (cdr ls))))))

(define (Gensumls llss)
    (if (null? llss)
        0
        (if (list? (car llss))
            (+ (Gensumls  (car llss))
               (Gensumls  (cdr llss)) )
            (+ (car llss) (Gensumls  (cdr llss))))))
 

(define (tower-of-hanoi n peg1 peg2 peg3)
   (if (= n 0)
       '()
       (append (tower-of-hanoi (- n 1) 
                               peg1 
			       peg3 
			       peg2)
               (cons (list peg1 peg3) 
                     (tower-of-hanoi (- n 1) 
		                     peg2 
				     peg1 
				     peg3)))))

 (define (fact n) 
     (if (= n 0) 
         1 
         (* n (fact (- n 1))))) 

(define (f x) ((if (fac (list x x)) 5 #t)))

(define (g x) ((if (> x 4) 5 #t)))