CS320 Notes on Functional Programming

 http://www.csci.csusb.edu/dick/cs320/notes/15.html
Also see
 http://www.csci.csusb.edu/dick/samples/lisp.html

Contents

	 Background
	 15.1 Mathematical Functions
	 15.1.1 Simple functions.
	 15.1.2 Functional Forms
	 15.2
	 15.3 LISP: context, data, and interpreter.
	 15.3.1 AI and List processing
	 15.3.2 McCarthy!
	 15.3.3 Data Structures.
	 15.3.5
	 15.3.9
	 15.3.10
	 15.4 LISP as a Language.
	 Note: Possible error in Book

Background

We are studying three language paradigms:
	Procedural		Algol, Pascal, C, C++
	Functional		LISP, SML, FP,...
	Logic			Prolog
	Object Oriented		Simula, Smalltalk, Java, ...

The long term impact of a language a language like LISP
is that writing the code develops a way of thinking about 
programs.  This leads to a methods for designing programs.  And finally 
into new ways of developing software and understanding problems.
We call this "a new Programming Paradigm".

Being able to think and understand things according to the different
paradigms is a valuable skill.  More valuable than being a language expert!

LISP lead directly to functional programming.  Christopher 
Strachey's 1966 scientific American paper clearly presents ideas that are 
named functional decomposition.
Functional decomposition was the dominant method of
program design from about 1975 to 1985.  

In the late 1980s - following Backus's endorsement
it has undergone a rebirth and several new languages have become widespread.
We will use LISP as a vehicle for practicing functional programming.

The book shows you a mathematical notation for FP (Functional Programming).
I will introduce you to an extended EBNF notation for expressing the 
mathematics in ASCII below.

Only recently have object-oriented
methods started to enter the mainstream.  Notice that inside
objects and classes there are functions.... and so functional
programming is not gone... it is just a part of a larger scheme
of things.

15.1 Mathematical Functions

15.1.1 Simple functions.

Note. It has become common practice in ASCII to show Greek letters as a back-
slash(\) plus their English name. This comes from the TeX language of Knuth.
        \alpha, \beta, ...\lambda.

EBNF Extended  becomes XBNF. XBNF can define functions:
	For x:real, square(x) ::= x.
See
	http://www.csci.csusb.edu/dick/maths/intro_function.html

Some examples -- defining the function that cubes a number.

        For x:real, cube(x)::=x*x*x.
The above says:   for all real values x, the cube of x is equal to x*x*x;

Or we have a \lambda like notation:
      cube = fun[x:real](x*x*x).

In general, if f is a function then
		f=fun[x](f(x)).
So
		(fun[x](E))(e) = `replace x by e throughout E`

15.1.2 Functional Forms

Functions can be combined:

For f,g:functions, 
	f o g::= ` The composition of g and f`.
	For all x, (f o g)(x)=f(g(x)).
        f o g ::= fun[x]f(g(x)).
	f o g = f(g((_)))

We can add a rule that we can use functions in expressions:
	f(g) ::=(f o g).
If we use (_) for the identity function then we can define `cube` by:
	cube = (_)*(_)*(_).

15.2

How do you do FP?

Its very like learning to program all over again. Skill comes from practice.
There are few tricks... but here are some useful hints:
	(1) Work top down, breaking down each function into
		other functions using conditionals, composition and
		predefined functions.

	(2) Use a conditional to separate out the simple cases and
		work these out first.  Keep looking for special
		cases with simple expressions.  Watch out for a
		smaller version of the same problem, or the re-appearance
		of another function.

	(3) Always use the form of the input to determine the conditions,
		but the form of the result guides the compositions applied.

For example, consider:   For x:list, reverse(c)::=`x backwards`...

	Clearly
		reverse(()) = ()

		reverse((x))= (x)

		reverse(x,...)=cons(reverse(...), x)

So define three cases x=NIL, cdr(x)=NIL, and other:
	For x:list, reverse(x) ::= (x=NIL->NIL | cdr(x)=NIL -> x
				else-> `put car(x) at end of reverse(cdr(x))`)
So the LISP is

	(define (reverse x)
		(cond 
			((null x) NIL)
			((null (cdr x)) x)
			( T (append (rev (cdr x)) (cons (car x) NIL )) )
	))

The typical LISP function has a definition like this
	(define (name arguments)
		(cond
			( (null argument)  simple_case )
			( (atom argument)  simple_case )
			...
			( T  (complex case))
		)
	)

The best way to learn is by doing it in the laboratory.

15.3 LISP: context, data, and interpreter.

15.3.1 AI and List processing

IPL :-(!
I have studied the IPL-V manual and it is probably the only language that is
worse than an assembler language.

15.3.2 McCarthy!

        Pure LISP
You have access to a modern and highly impure LISP system(xlisp). In class and
in homework and in quiz you should learn to stay within the Pure Subset.

15.3.3 Data Structures.

The book does not stress a key fact.

A LISP structure is defined to be (1) an atomic symbol, or (2) empty(NIL), or
(3) a pair of two lists, the first called the 'car' and the second called the
'cdr'. In short a list (if not NIL or atomic) is a pointer to a record:

Semantics of a List in C:
	typedef struct LIST
		{ enum{null,atom,pair} type;
		  union{
			char * null;
			char * atom;
			struct{ struct LIST * car, *cdr} list; 
		  }data;
	       	} * list;
Syntax of a List
	list::="NIL"|string|"(" car "." cdr ")" | "(" car cadr caddr cadddr...")"

A structure like (A B C) is encoded so that:

        (A B C).car=A,
        (A B C).cdr.car=B,
        (A B C).cdr.cdr.car=C,
        (A B C).cdr.cdr.cdr.car=NIL.
	car[(A B C)] = A.    (CAR (QUOTE ( A B C)))=A.
	cadar::=car;cdr;car.

	cons(x,y)::='construct pair with car=x and cdr=y'.

15.3.5

	\lambda done using (LAMBDA (args) expression) in our LISP
	::= done using (DEFINE (function args) expression) in our LISP.

15.3.9

	higher order functions
		Take functions and make new functions out of them.

15.3.10

	are we having FUNARG yet?

15.4 LISP as a Language.

The book does not emphasize 'Cambridge Polish Notation' used in LISP S
expressions. This is designed to make it easy to write the LISP interpreter.

You either learn it or have problems.

        expression::="(" function # actual_parameter ")" | atom|"NIL".
	actual_parameter::=expression.

        conditional::="(" "COND" #pair ")",

        pair::="("predicate expression")",

        predicate::=expression `that sometimes returns the value T`

Our LISP has been modified to have a scheme like syntax.
It originally only had the Common LISP form(DEFUN).

DEFINE is a common way to define a function.
        "(" DEFINE "(" name arguments")" expression")"

(DEFINE (FACTORIAL N)
 (COND ((EQ N 0) 1)
       (T (* N (FACTORIAL (- N 1))))
 )
)

'xlisp' also will ignore case outside strings so the following is easier to 
read:

(define (factorial n)
 (cond ((eq n 0) 1)
       (t (* n (factorial (- n 1))))
 )
)


(define (enigma n)
   (cond ( (evenp n) (/ n 2) )
	 ( T         (+ 1 (* 3 n)))
   )
)

Note: Possible error in Book

I'm not sure that APL is really a functional language.