Transcript Functional programming

Functional programming in Scheme
The plan
LISP
A summary of Scheme
A session with Scheme
More on Scheme
Simple data structures
Compound data structures
Evaluating a function
List construction, access to elements
Function expressions, definitions of functions
Control
Higher-order functions
CSI 3125, Scheme, page 1
LISP
• Functional programming began in the late 1950s
(please read section 2.4 again). There were many
dialects, starting with LISP 1.5 (1960), through
Scheme (1975) to Common LISP (1985).
[LISP = LISt Processor]
• Other important functional programming
languages are Hope, ML, Miranda, Haskell.
• The mathematical basis of many functional
programming languages is -calculus. It allows
expressions that have functions as values.
CSI 3125, Scheme, page 2
LISP (2)
• LISP has very few control mechanisms:
– function application,
– function composition,
– conditional expressions,
– recursion.
[We will soon see them all in action.]
•
Data structures are also very simple:
– atoms (symbols and numbers),
– lists that consist of atoms and nested lists.
CSI 3125, Scheme, page 3
LISP (3)
• Programs and data in functional programming
languages have the same syntax.
– We write function applications, function
composition and conditional expressions as lists,
in a parenthesized prefix form.
– Context helps distinguish program and data.
• This uniformity of data and programs gives functional
languages their flexibility and expressive power:
programs can be manipulated dynamically.
• A one-page interpreter of LISP in LISP was the basis
of the first ever bootstrapping implementation of a
programming language (a very powerful technique).
CSI 3125, Scheme, page 4
LISP (4)
LISP has only five primitive functions, two of them
with Boolean values:
• cons
—
build a list
• car
—
the head of a list
• cdr
—
the tail of a list
• eq
—
are two atoms equal?
• atom
—
is this an atom?
There are two other essential mechanisms:
– evaluate an expression,
– apply a function to evaluated arguments
(several auxiliary mechanisms help handle
argument lists and conditional evaluation).
CSI 3125, Scheme, page 5
LISP (5)
• LISP is typically used interactively, like Prolog.
– There is no main program.
– A LISP program is a collection of functions that may
be called, directly or indirectly, from the top level.
– The top-level loop evaluates an expression for its
value or for its side-effects such as input/output
(expressions can invoke very complicated functions).
• Expressions are evaluated: you must ask LISP to leave
something unevaluated (quoted).
• An atom is treated literally: it stands for itself, and has no
value other than its name.
CSI 3125, Scheme, page 6
LISP (6)
LISP 1.5 has several major weaknesses:
• Awkward—though elegantly uniform—syntax.
• Dynamic scope rule. [We will return to that later.]
• Inconsistent treatment of functions as
arguments—because of dynamic scoping.
CSI 3125, Scheme, page 7
A summary of Scheme
• Scheme is a small but well-designed subset of LISP.
• It distinguishes numbers and symbols.
• It has lexical scope.
• It correctly treats functional arguments,
thanks to lexical scoping.
– Functions are first-class objects: they
can be created, assigned to variables,
passed as arguments, returned as values.
• Data structures in Scheme are simple, uniform and
versatile.
CSI 3125, Scheme, page 8
The Scheme system for this course
Connect (via ssh) to site1, and type scm at the prompt.
% scm
SCM version 5d3, Copyright (C) 1990-1999 Free Software Foundation.
SCM comes with ABSOLUTELY NO WARRANTY; for details type `(terms)'.
This is free software, and you are welcome to redistribute it
under certain conditions; type `(terms)' for details.
;loading /usr/local/lib/slib/require
;done loading /usr/local/lib/slib/require.scm
;loading /usr/local/lib/scm/Transcen
;done loading /usr/local/lib/scm/Transcen.scm
;Evaluation took 50 mSec (0 in gc) 15992 cells work, 4000 env,
17604 bytes other
>
Now you are talking to the top-level interactive loop. You can, for
example, type (terms) or (exit) or (quit), or proceed...
CSI 3125, Scheme, page 9
A session with Scheme
% scm
> '( ( person Jack ( married Jill ) )
( person Jim
( single ) )
( person Jerry ( alimony 800 ) )
)
((person jack (married jill)) (person jim
(single)) (person jerry (alimony 800)))
> ( cons 'alpha '( beta ) )
(alpha beta)
> ( symbol? 'alpha )
#t
> ( symbol? '( alpha ) )
#f
CSI 3125, Scheme, page 10
A session with Scheme (2)
> ( null? 'alpha )
#f
> ( null? () )
#t
> ( number? 'alpha )
#f
> ( number? 23 )
#t
> ( symbol? alpha )
ERROR: unbound variable: alpha
; in expression: (... alpha)
; in top level environment.
CSI 3125, Scheme, page 11
A session with Scheme (3)
> ( define alpha 5 )
#<unspecified>
> ( number? alpha )
#t
> ( symbol? alpha )
#f
> ( cdr ( cons 'x '( y z ) ) )
(y z)
> ( cons 'x ( cdr '( y z ) ) )
(x z)
> ( + 1 2 )
3
CSI 3125, Scheme, page 12
A session with Scheme (4)
> ( define ( addOne x )
( + x 1 )
)
#<unspecified>
> ( addOne ( addOne 15 ) )
17
> ( define ( myAnd x y )
( if x y #f )
)
#<unspecified>
> ( myAnd ( symbol? '(a) ) ( eq? 'a 'a ) )
#f
> ( and ( symbol? '(a) ) ( eq? 'a 'a ) )
#f
CSI 3125, Scheme, page 13
A session with Scheme (5)
> ( define ( myOr x y )
( if x #t y )
)
#<unspecified>
> ( myOr ( symbol? '(a) ) ( eq? 'a 'a ) )
#t
> ( or ( symbol? '(a) ) ( eq? 'a 'a ) )
#t
> ( eq? 'a 'a )
#t
> ( eq? 'a 'b )
#f
> ( eq? '( a ) '( a ) )
#f
CSI 3125, Scheme, page 14
A session with Scheme (6)
>
( define ( numberList? x )
( if ( not ( list? x ) )
#f
( if ( null? x )
#t
( if ( not ( number? ( car x ) ) )
#f
( numberList? ( cdr x )
) )
)
)
)
#<unspecified>
> ( numberList? ' ( 1 2 3 4 ) )
#t
CSI 3125, Scheme, page 15
A session with Scheme (7)
>
( define ( numberList? x )
( cond
( ( not ( list? x ) ) #f )
( ( null? x ) #t )
( ( not ( number? ( car x ) ) ) #f )
( else ( numberList? ( cdr x ) ) )
) )
> ( numberList? ' ( 1 2 3 4 ) )
#t
> ( numberList? ' ( 1 2 3 bad 4 ) )
#f
CSI 3125, Scheme, page 16
A session with Scheme (8)
>
( define ( eqExpr? x y )
( cond
( ( symbol? x ) ( eq? x y ) )
( ( number? x ) ( eq? x y ) )
; x must be a list now:
( ( null? x ) ( null? y ) )
; x must be a non-empty list now:
( ( not ( list? y ) ) #f )
( ( null? y ) #f )
( ( eqExpr? ( car x ) ( car y ) )
( eqExpr? ( cdr x ) ( cdr y ) ) )
( else #f )
) )
> ( eqExpr?
#t
> ( eqExpr?
#f
'( a b ( c d ) )
'( a b ( c d ) )
'( a b ( c d ) )
'( a b ( c d e) )
)
)
CSI 3125, Scheme, page 17
A session with Scheme (9)
> ( define ( member? K L )
( cond
( (null? L ) #f )
( ( eqExpr? K ( car L ) ) #t )
( else ( member? K ( cdr L ) ) )
) )
#<unspecified>
> ( member? 'aa '( bb cc aa ee rr tt ) )
#t
> ( member? 'aa '( bb cc (aa) ee rr tt ) )
#f
> ( member 'aa '( bb cc aa ee rr tt ) )
(aa ee rr tt)
> ( member 'aa '( bb cc (aa) ee rr tt ) )
#f
CSI 3125, Scheme, page 18
A session with Scheme (10)
> ( define ( append L1 L2 )
; built-in!
(if ( null? L1 )
L2
( cons ( car L1 )
( append ( cdr L1 ) L2 ) )
) )
WARNING: redefining built-in append
#<unspecified>
> ( append '( ab bc cd )
'( de ef fg gh ) )
(ab bc cd de ef fg gh)
> ( exit )
;EXIT
CSI 3125, Scheme, page 19
Simple data structures
• Numbers are as usual—integers and floats.
• A variable is a name bound to a data object, for
example:
(define pi 3.14159)
• A variable has an implicit type, depending on its
value. It can be assigned a value of a new type:
(set! pi 3.141592)
(set! pi 'alpha)
(set! pi (cons pi '(rho)))
• A symbol is a name that has no value other
than itself.
CSI 3125, Scheme, page 20
Compound data structures
The general form of a list:
(E1 E2 ...... En)
where Ei are any data structures.
Depending on context, a list is treated literally (as
a piece of data), for example,
((William Shakespeare)
(The Tempest))
or as a function application with arguments
passed by value, for example,
(append x y)
CSI 3125, Scheme, page 21
Compound data structures (2)
A “dotted” pair (seldom used in practice) underlies
the structure of lists. A dotted pair is produced by
cons:
cons( ) returns ( . )
A list (E1 E2 ...... En) is represented internally as
(cons E1 (cons E2 ......
(cons En ()) ...... ))
that is, as
(E1 . (E2 ...... (En . ( )) ...... ))
CSI 3125, Scheme, page 22
Evaluating a function
• Given: a list (E0 E1 ... En)
• Step 1
Evaluate E0 to get V0,
Evaluate E1 to get V1,
......,
Evaluate En to get Vn.
V0 must be a function,
V1, ..., Vn are data objects.
• Step 2
Apply V0 to V1, ..., Vn, that is,
compute V0(V1, ..., Vn).
CSI 3125, Scheme, page 23
Quoting
• Evaluation can be suppressed by quoting:
(quote pi)
or, more conveniently,
'pi
• Let us have this definition:
(define pi 3.141592)
• Examples:
(* 2.0 pi)
(* 2.0 'pi)
('* 2.0 'pi)
(write 'pi)
(write pi)
gives 6.283184
has a wrong argument
has a wrong function!
outputs the symbol pi
outputs 3.141592
CSI 3125, Scheme, page 24
List construction
and access to elements
• A list is defined recursively:
An empty list is (),
A non-empty list is
(cons  x)
where x is a list.
• The head and the tail of a list:
(car (cons  x)) equals 
(cdr (cons  x)) equals x
(car ()) and (cdr ()) are incorrect
CSI 3125, Scheme, page 25
More access to elements
A notational convention for accessing further
elements of a list:
(caar x)  (car (car x))
(cdadr x)  (cdr (car (cdr x)))
For example, consider this 4-step evaluation:
(caadar '((p ((q r) s) u) (v)))
(caadr '(p ((q r) s) u))
(caar '(((q r) s) u))
(car '((q r) s))
'(q r)
The second element of list x—if it exists—is
(cadr x)
The third, fourth, ... elements—if they exist—are
(caddr x), (cadddr x), etc.
CSI 3125, Scheme, page 26
Primitive functions
• car, cdr, cons are the primitive functions
that ensure all the necessary access to lists.
Three other primitives are predicates: functions
that return #t or #f.
• (symbol? x)
– true if and only if x is a symbol,
• (number? x)
– true if and only if x is a number,
• (eq? x y)
– true if and only if the values of x and y are
symbols and are identical.
CSI 3125, Scheme, page 27
Other very common functions
Other commonly used functions
(they can be defined using the primitive six):
(equal? x y) is true if the values
of x and y are the same object, maybe not atomic.
(null? x) is true if x is (), the empty list.
(append x y) concatenates the lists x and y.
CSI 3125, Scheme, page 28
Defining functions
A definition binds a function expression to a name:
(define (square x) (* x x))
or, equivalently,
(define square
(lambda (x) (* x x)))
A function expression has a value:
> square
#<CLOSURE (x) #@lambda (* x x)>
Function expressions do not need a name!
> ((lambda (x) (* x x x)) 3)
27
CSI 3125, Scheme, page 29
Control
Control structures in Scheme, as in LISP, are very
simple. There are no loops—but we have recursion.
We have function application, the conditional schema,
and the sequence. The latter is a concession to the
programming habits of people trained on imperative languages.
> (begin (print 'okay) (print '(great)))
okay
(great)
;Evaluation took [...]
(great)
The value of (begin ...) is the value of the last element.
CSI 3125, Scheme, page 30
The conditional schema
(cond (C1 E1)
(C2 E2) ......
(Cn En)
(else En+1))
• The last part, (else En+1), is optional.
• (Ci Ei) represents one condition-expression pair.
Pairs are evaluated left-to-right. We stop when we
have found a true Ci (its value is #t ). We return Ei
as the value of the whole conditional schema.
• else evaluates to #t.
CSI 3125, Scheme, page 31
A special case: if
(cond (C1 E1) (else E2))
can be abbreviated as
(if C1 E1 E2)
It is a matter of taste -- or readablility -- which form
to use. The shorter, the better. The if form is good
when there is little nesting.
CSI 3125, Scheme, page 32
More examples of functions
(define (same_neighbours? l)
(cond
((null? l) #f)
((null? (cdr l)) #f)
((equal? (car l)(cadr l)) #t)
(else
(same_neighbours? (cdr l)))
) )
CSI 3125, Scheme, page 33
Stack operations in Scheme
(define (empty? stack)
(null? stack)
)
(define (push el stack)
(cons el stack)
)
(define (pop stack)
(if (empty? stack)
stack
(cdr stack)
) )
(define (top stack)
(if (empty? stack)
()
(car stack)
) )
CSI 3125, Scheme, page 34
Minimum of a list
(define (minL Lst)
(if (null? Lst)
Lst
(minL-aux (car Lst)(cdr Lst))
) )
(define (minL-aux Elt Lst)
(cond
((null? Lst) Elt)
((> Elt (car Lst))
(minL-aux (car Lst)(cdr Lst)))
(else (minL-aux Elt (cdr Lst)))
) )
CSI 3125, Scheme, page 35
MinL-aux, a variant with local scope
(define (minL-aux Elt Lst)
(if (null? Lst)
Elt
(let
((carl (car Lst))
(cdrl (cdr Lst)))
(if
(> Elt carl)
(minL-aux carl cdrl)
(miny-aux Elt cdrl)
) )
) )
CSI 3125, Scheme, page 36
More on local scope
>
(define (quadruple x)
(let ((double (lambda (x) (+ x x))))
(double (double x))
) )
#<unspecified>
> (quadruple 8)
32
> (double 8)
unbound variable: double
; in expression: (... double 8)
; in top level environment.
CSI 3125, Scheme, page 37
More on local scope (2)
>
(define (quadruple x)
(define (double x) (+ x x))
(double (double x))
)
#<unspecified>
> (quadruple 8)
32
> (double 8)
unbound variable: double
; in expression: (... double 8)
; in top level environment.
CSI 3125, Scheme, page 38
Higher-order functions
A function can have functions as arguments.
> (define (combine Fun1 Fun2 X)
(Fun1 (Fun2 X))
)
> (combine (lambda (x) (+ 1 x))
(lambda (x) (* 2 x))
6)
> (combine (lambda (x) (* 2 x))
(lambda (x) (+ 1 x))
6)
Also possible:
> ((lambda (x) (+ 1 x)) ((lambda (x) (* 2 x)) 6))
> ((lambda (x) (* 2 x)) ((lambda (x) (+ 1 x)) 6))
CSI 3125, Scheme, page 39
Higher-order functions (2)
The classic example is map, the operation of applying
a function to a list and returning a list of values:
(E1 E2 ...... En)  ((f E1) (f E2) ...... (f En))
(define (map F Lst)
(if (null? Lst)
Lst
(cons (F (car Lst))
(map F (cdr Lst)))
) )
For example, this gives (2 3 4):
(map (lambda(x) (+ x 1)) '(1 2 3))
CSI 3125, Scheme, page 40
Higher-order functions (3)
A version of map which does something for all
elements, without creating a list of results:
(define (do-for-all F L)
(if (null? L)
L
(let ((dummy (F (car L))))
(do-for-all F (cdr L))
) ) )
For example:
(do-for-all write '(1 2 3))
CSI 3125, Scheme, page 41
Higher-order functions (4)
Let's try a small puzzle:
(define (f) (lambda (x) (+ 1 x)))
What is the value of this function?
CSI 3125, Scheme, page 42
Reducers
Let F be a binary operation, that is, a two-argument
function. Let F0 be a constant. We want to express the
following transformation:
(E1 E2 ...... En) 
(F E1 (F E2 (F ...... (F En F0) ...... )))
This is better written with F as an infix operator:
(E1 E2 ...... En)  E1 F E2 F ...... F En F F0
CSI 3125, Scheme, page 43
Reducers (2)
Examples:
(E1 E2 ...... En)  E1 + E2 + ...... + En + 0
(E1 E2 ...... En)  E1 * E2 * ...... * En * 1
(define (reduce F F0 L)
(if (null? L)
F0
(F (car L)
(reduce F F0 (cdr L)))
) )
CSI 3125, Scheme, page 44
Reducers (3)
> (reduce + 0 '(1 2 3 4))
> (reduce * 1 '(1 2 3 4))
> (reduce (lambda (x y) (+ x y 1))
8 '(1 2 3))
> (reduce cons () '(1 2 3 4))
> (reduce append () '((1) (2) (3)))
CSI 3125, Scheme, page 45
Some built-in names
List manipulation
Defining things
car
define
cdr
lambda
cons
append
list
length
caar, cadr, cdar, cddr,
...,
caaaar, ..., cddddr
CSI 3125, Scheme, page 46
Some built-in names (2)
Control
Logic
if
cond
else
let
begin
not
and
or
#t
#f
Arithmetics and comparison
+
*
/
max
min
<
>
<=
>=
=
CSI 3125, Scheme, page 47
Some built-in names (3)
Predicates
I/O functions
symbol?
number?
integer?
real?
list?
null?
eq?
equal?
procedure?
write
display
print
read
Miscellaneous
load
map
quote
set!
CSI 3125, Scheme, page 48
More built-in things
(for another course)
strings
(and lots of functions on strings)
characters
(and functions on characters)
vectors
(and even arrays)
arithmetics and functions on integers
mathematical functions
(trigonometry and so on)
serious I/O handling
CSI 3125, Scheme, page 49