Functional Languages and Lisp
=============================

		
Lambda Calculus
--------------


+ In classical LISP, expressions are of two types: atoms and lists (aka s-experressions).
+ In classical LISP,  _t_ and _()_ stand for true and false.
+ The functions in the core of classical LISP are _quote_, _atom_, _eq_, _car_, _cdr_ , _cons_, _cond_. 
    + _cons_ pushes expressions to the front of a list. So to make
	   a new list _(cons something ())_.
	+ __cond__ controls conditional execution. 
	
	
_cond_  evaluates the `act`
	  of the first item whose `test` is true:
	

        ; general form
        (cond (test1 act1)
              (test2 act2)
        	  ...)
        	
        ; example
        (cond ((> age 120) 'dead)
              ((> age 50) 'oldMan)
        	  ((> age 20) 'youndNDumb)
        	  ((> age 10) 'veryAnnoying)
        	  ((> age 0)   'cuteAsApuppy))

Note in the above the quote mark notation. The LISP reader is
smarter than the lis.py reader so in real LISP we
can write _'x_ instead of the more tedious _(' x)_.

Functions are actually recursive interpretations of lambda bodies,
with local vars inside the lambda getting pointed to the passed
in arguments:

    ; call 1
    ((lambda (x) (cons x '(b))) 
     'a)
	; returns (a b)
    
    ; call 2
    ((lambda (x y) (cons x (cdr y)))
     'z
     '(a b c))
	; returns (z b c)
    
    ; call3 (quite tricky)
    ((lambda (f) (f '(b c)))
     '(lambda (x) (cons 'a x)))
    ; returns (a b c)
 

In LISP, the _environment_ is a set of name:binding pairs. In lis.py, these are handled by the hash tables in the _Env_ class.
In classical LISP, there are no hash tables and the new binds a
added to the front of the old bindings. Then, a left to right search
across the list will find the newer bindings before the old.

Stepping through that:

    (eval '((lambda (x y) (cons x (cdr y)))
           'a
    	   '(b c d))
    	   oldenv)

	   
calls the body of the lambda with the args of the lambda bound
to the pass arguments

    (eval '(cons x (cdr y))
          '((x a) (y (b c d)) oldenv))

[Eval in LISP](http://ep.yimg.com/ty/cdn/paulgraham/jmc.lisp).

LISP is Functional, But What is a Functional Language?
------------------------------

Functional languages contain functions. Functions generate output from input.
The output is determined solely by the inputs (no globals, no side effects).

A functional program consists of an expression E (representing both
the algorithm and the input). This expression E is subject to some
rewrite rules.
 
Reduction consists of repl acing some part P of E by another expression
P' according to the given rewrite rules. ... This process of reduction
will be repeated until the resulting expression has no more parts that
can be rewritten.

Functional programming is characterized by the programming with
values, functions and functional forms.

Keywords and phrases: Lambda calculus, free and bound variables,
environment, functional programming, 
recursive functions, functional, curried function.

Functional programming languages are the result of both abstracting
and generalizing the data type of maps. Recall, the mapping m from
each element x of S (called the domain) to the corresponding element
m(x) of T (called the range) is written as:

    m : S --> T


For example, the squaring function is a function of type:

     sqr : Num --> Num


and may be defined as:

    sqr where x |--> x*x

A linear function f of type


    f : Num --> Num

may be defined as:

    f where x |--> 3*x + 4

Functional programming is based on the mathematical concept of a function and functional programming languages include the following:

+ A set of primitive functions.
+ A set of functional forms.
+ The application operation.
+ A set of data objects and associated functions.
+ A mechanism for binding a name to a function.

LISP, FP, Scheme, ML, Miranda and Haskell are just some of the languages to implement this elegant computational paradigm.

The basic concepts of functional programming originated with LISP.

Why Bother?
-----------

Functional programming languages are important for the following reasons.

+ Functional programming dispenses with the assignment command freeing the programmer from the rigidly sequential mode of thought required with the assignment command.
+ Functional programming encourages thinking at higher levels of abstraction by providing higher-order functions -- functions that modify and combine existing programs.
+ Functional programming has natural implementation in concurrent programming.
+ Functional programming has important application areas. Artificial intelligence programming is done in functional programming languages and the AI techniques migrate to real-world applications.
+ Functional programming has a close relationship to computer science theory. Functional programming is based on the lambda-calculus which in turn provides a framework for studying decidability questions of programming. The essence of denotational semantics is the translation of conventional programs into equivalent functional programs.
+ Functional programming is useful for developing executable specifications and prototype implementations.


        n :: Int
        n = 1000
        main = do
        print $ length [(a,b,c) | a<-[1..n],b<-[1..n],c<-[1..n],a^2+b^2==c^2]

and appropriate C version:
	
	#include <stdio.h>
	
	int main(void)
	{
	    int a,b,c, N=1000;
		int cnt = 0;
			
		for (a=1;a<=N;a++)
		    for (b=1;b<=N;b++)
			    for (c=1;c<=N;c++)
					if (a*a+b*b==c*c) cnt++;
	    printf("%d\n", cnt);
    }


What is functional programming good for?
----------------------------------------

Functional programming, like any good programming technique, is a
useful tool in your armory for solving some classes of problems. It's
very good for callbacks, which have multiple uses from GUIs through to
event-driven loops. It's great for expressing generic
algorithms. List.map is really a generic algorithm for applying
functions over any type of list. Similarly you can define generic
functions over trees. Certain types of numerical problems can be
solved more quickly with functional programming (for example,
numerically calculating the derivative of a mathematical function).

Pure and impure functional programming
--------------------------------------

A pure function is one without any side-effects. A side-effect really
means that the function keeps some sort of hidden state inside
it. strlen is a good example of a pure function in C. If you call
strlen with the same string, it always returns the same length. The
output of strlen (the length) only depends on the inputs (the string)
and nothing else. Many functions in C are, unfortunately, impure. For
example, malloc - if you call it with the same number, it certainly
won't return the same pointer to you. malloc, of course, relies on a
huge amount of hidden internal state (objects allocated on the heap,
the allocation method in use, grabbing pages from the operating
system, etc.).

ML-derived languages like OCaml are "mostly pure". They allow
side-effects through things like references and arrays, but by and
large most of the code you'll write will be pure functional because
they encourage this thinking. Haskell, another functional language, is
pure functional. OCaml is therefore more practical because writing
impure functions is sometimes useful.

There are various theoretical advantages of having pure functions. One
advantage is that if a function is pure, then if it is called several
times with the same arguments, the compiler only needs to actually
call the function once. A good example in C is:


    for (i = 0; i < strlen(s); ++i)
      {
          // Do something which doesn't affect s.
      }

		
If naively compiled, this loop is O(n^2) because strlen (s) is called
each time and strlen needs to iterate over the whole of s. If the
compiler is smart enough to work out that strlen is pure functional
and that s is not updated in the loop, then it can remove the
redundant extra calls to strlen and make the loop O(n). Do compilers
really do this? In the case of strlen yes, in other cases, probably
not.



Lisp
----

'nough said.

Lis.py
------

Ditto

Clojure
-------

New-generation Lisp, purely functional language, compiles down to the Java virtual machine.

Scheme
------

Scheme, a descendent of LISP, is based on the
lambda-calculus. Although it has imperative features, in this section
we ignore those features and concentrate on the lambda-calculus like
features of Scheme. Scheme has two kinds of objects, atoms and
lists. Atoms are represented by strings of non-blank characters. A
list is represented by a sequence of atoms or lists separated by
blanks and enclosed in parentheses. Functions in Scheme are also
represented by lists. This facilitates the creation of functions which
create other functions. A function can be created by another function
and then the function applied to a list of arguments. This is an
important feature of languages for AI applications.

### Syntax

Expressions are atoms which are variables or constants, lists of
arbitrary length (which are also function applications),
lambda-abstractions of one or more parameters, and other built-in
functions.

Scheme provides a number of built in functions among which are +, -,
*, /, <, <=, =, >=, >, and not. Scheme provides for conditional
expressions of the form (if E0 E1 E2) and (if E0 E1). Among the
constants provided in Scheme are numbers, #f and the empty list ()
both of which count as false, and #t and any thing other than #f and
() which count as true. nil is also used to represent the empty list.

### Definitions

Scheme implements definitions with the define keyword.

### Lists with nil, cons, car and cdr

The list is the basic data structure with nil repesenting the empty
list. Among the built in functions for list manipulation provided in
Scheme are cons for attaching an element to the head of a list, car
for extracting the first element of a list, and cdr which returns a
list minus its first element. The following code contains an example
of stack operations writtem in Scheme. The code illustrates
definitions, the conditional expression, the list predicate null? for
testing whether a list is empty, and the list manipulation functions
cons, car, and cdr.

    
    ( define empty_stack 
       ( lambda ( stack ) ( if ( null? stack ) \#t \#f )))
    
    ( define push
       ( lambda ( element stack ) ( cons element stack ) ))
    
    (define pop
       ( lambda ( element stack ) ( cdr stack )))
    
    (define top
       ( lambda ( stack ) ( car stack )))

OCaml
-----

LISP and Scheme are "old school". There is much more modern interest in F#, Haskell, and OCaml. Here's a OCaml example example:


    # let double x =
        x * 2
      in
      List.map double [ 1; 2; 3 ];;
    - : int list = [2; 4; 6]


The function double takes an argument x and returns x * 2. Then map
calls double on each element of the given list ([1; 2; 3]) to produce
the result: a list with each number doubled.

map is known as a higher-order function (HOF). Higher-order functions
are just a fancy way of saying that the function takes a function as
one of its arguments. The same thing in LISP would be:


    (defun doubler ()
      #'(lambda (x) (* x 2)))
    
    (mapcar (doubler) '(1 2 3))
    
    ==>

    (2 4 6)

If you're familiar with C/C++ then this looks like passing a function
pointer around. Java has some sort of abomination called an anonymous
class which is like a dumbed-down, slow and long-winded closure. If
you know Perl then you probably already know and use Perl's closures
and Perl's map function, which is exactly what we're talking
about. The fact is that Perl is actually quite a good functional
language.

Closures are functions which carry around some of the "environment" in
which they were defined. In particular, a closure can reference
variables which were available at the point of its definition. Let's
generalise the function above so that now we can take any list of
integers and multiply each element by an arbitrary value n:

    let multiply n list =
      let f x =
        n * x
      in
      List.map f list
      ;;

Hence:

    # multiply 2 [1; 2; 3];;
    - : int list = [2; 4; 6]
    # multiply 5 [1; 2; 3];;
    - : int list = [5; 10; 15]

The important point to note about the multiply function is the nested
function f. This is a closure. Look at how f uses the value of n which
isn't actually passed as an explicit argument to f. Instead f picks it
up from its environment - it's an argument to the multiply function
and hence available within this function.

This might sound straightforward, but let's look a bit closer at that
call to map: List.map f list.

map is defined in the List module, far away from the current code. In
other words, we're passing f into a module defined "a long time ago,
in a galaxy far far away". For all we know that code might pass f to
other modules, or save a reference to f somewhere and call it
later. Whether it does this or not, the closure will ensure that f
always has access back to its parental environment, and to n.

In LISP, the same example would be:
    
    (defun multn (n) 
       #'(lambda (x) (* x n)))
    
    (mapcar (multn 2) (1 2 3 4))
    ==>
    (2 4 6 8)
    
    (mapcar (multn 5) (1 2 3 4))
    ==>
    (5 10 15 20)

As with the OCAML solution, the agument to multn gets stuck in a closure and is carried around the data structure.

The same technique in LISP is

    
    (defparameter *grammar*
      '((Sentence -> Noun VerbPhrase )
        (VerbPrase -> runs quickly)
        (VerbPhase -> walks slowley)))
    
    (defun lhs (g)
      (let (all)
        (mapc #'(lambda (one)
                     (setf all (lhs1 (first one) all)))
              g)
        all))
    
    (defun lhs1 (item all)
      (if (member item all)
          all
          (cons item all)))

    ;e.g. (lhs *grammar*)

Partial function applications and currying
------------------------------------------

Let's define a plus function which just adds two integers:

    let plus a b =
      a + b
      ;;

Some questions for people asleep at the back of the class.

1. What is plus?
2. What is plus 2 3?
3. What is plus 2?

Question 1 is easy. plus is a function, it takes two arguments which are integers and it returns an integer. We write its type like this:


    plus : int -> int -> int


Question 2 is even easier. plus 2 3 is a number, the integer 5. We write its value and type like this:


    5 : int


But what about question 3? It looks like plus 2 is a mistake, a
bug. In fact, however, it isn't. If we type this into the OCaml
toplevel, it tells us:

    
    # plus 2;;
    - : int -> int = <fun>

This isn't an error. It's telling us that plus 2 is in fact a function, which takes an int and returns an int. What sort of function is this? We experiment by first of all giving this mysterious function a name (f), and then trying it out on a few integers to see what it does:

    
    # let f = plus 2;;
    val f : int -> int = <fun>
    # f 10;;
    - : int = 12
    # f 15;;
    - : int = 17
    # f 99;;
    - 
: int = 101

In engineering this is sufficient proof by example for us to state that plus 2 is the function which adds 2 to things.

Going back to the original definition, let's "fill in" the first argument (a) setting it to 2 to get:
   
    let plus 2 b =       (* This is not real OCaml code! *)
      2 + b
      ;;

You can kind of see, I hope, why plus 2 is the function which adds 2 to things.

Looking at the types of these expressions we may be able to see some rationale for the strange -> arrow notation used for function types:

    
    plus : int -> int -> int
      plus 2 : int -> int

plus 2 3 : int

This process is called currying after Haskell Curry.  Currying is a
technique to pass multiple arguments to a function when the language
only allows one argument and one return value. Suppose you have a
function _f_ which takes arguments _a_ and _b_. You call _f_ with argument 
_a_
and instead of doing anything, it returns a function which takes a
second argument. You pass the second argument to that function, and
then you get your result.


Here's a little example of currying in Python

    def double1(l):
       "standard mapping"
       return map(lambda x:x*2,l)
    
    print double1([1,2,3])
    
    def mult(n):
        "return something that multiplies something by n"
        return lambda x: n*x
    
    def doubler():
    	"special form of mult: just double"
        return mult(2)
    
    def double2(l):
        "but does it work?"
        return map(doubler(),l)
    
    print double2([1,2,3])


Note that, in Python (and LISP), extra syntax is needed for currying.
Currying is so useful that in better functional languages, such
extras are not required. 

For example, in OCAML,
remember our double and multiply functions from earlier on? multiply
was defined as this:

    let multiply n list =
      let f x =
        n * x
      in
      List.map f list
      ;;

We can now define double, triple functions very easily just like this:


    let double = multiply 2;;
    let triple = multiply 3;;


You can  also use partial application directly 
(without the intermediate f function) like this:

    # let multiply n = List.map (( * ) n);;
    val multiply : int -> int list -> int list = <fun>
    # let double = multiply 2;;
    val double : int list -> int list = <fun>
    # let triple = multiply 3;;
    val triple : int list -> int list = <fun>
    # double [1; 2; 3];;
    - : int list = [2; 4; 6]
    # triple [1; 2; 3];;
    - : int list = [3; 6; 9]

In the example above, ((*) n) is the partial application of the (*)
(times) function. Note the extra spaces needed so that OCaml doesn't
think (* starts a comment.

Note that LISP can be streched to handling currying. But there is
something fundamentally more elegant about OCAML (no annoying
brackets!). Also, there is more current work on optimizing modern
functional langauges that old horses like LISP.


Haskell
-------

See _Seven Programing Languages in Seven Weeks_.
