CSI 3120
Functional programming in Scheme
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 1
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 S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 2
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, F#.
• The mathematical basis of many functional programming languages is -calculus. It allows expressions that have functions as values.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 3
•
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.
•
LISP (2)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 4
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).
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 5
LISP has only five primitive functions, two of them with Boolean values:
• cons
• car
• cdr
• eq
— — — — —
– evaluate an expression,
– apply a function to evaluated arguments (several auxiliary mechanisms help handle argument lists and conditional evaluation).
• atom
There are two other
build a list
the head of a list
the tail of a list
are two atoms equal? is this an atom? essential mechanisms:
LISP (4)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 6
• 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.
LISP (5)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 7
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.
LISP (6)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 8
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 named values, passed as arguments, returned as values.
• Data structures in Scheme are simple, uniform and versatile.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 9
The Scheme system for this course
Dr. Racket (available at https://racket-lang.org/)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 10
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.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 11
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)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 12
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 . ( )) …… ))
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 13
Evaluating a function
• Given: a list (E0 E1 … En) • Step1
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. • Step2
Apply V0 to V1, …, Vn, that is, compute V0(V1, …, Vn).
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 14
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
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 15
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
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 16
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.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 17
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 ofxandyare
symbols and are identical.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 18
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.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 19
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
#
Function expressions do not need a name!
> ((lambda (x) (* x x x)) 3) 27
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 20
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.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 21
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. S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 22
A special case: if
(cond (C1 E1) (else E2)) can be abbreviated as
(if C1 E1 E2)
It is a matter of taste — or readability — which form to use. The shorter, the better. The if form is good when there is little nesting.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 23
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)))
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 24
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
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 25
> ( null? ‘alpha )
#f
> ( null? () )
#t
> ( number? ‘alpha )
#f
> ( number? 23 )
#t
> ( symbol? alpha )
ERROR: unbound variable: alpha ; in expression: (… alpha)
; in top level environment.
A session with Scheme (2)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 26
A session with Scheme (3)
> ( define alpha 5 )
#
> ( number? alpha )
#t
> ( symbol? alpha )
#f
> ( cdr ( cons ‘x ‘( y z ) ) ) (y z)
> ( cons ‘x ( cdr ‘( y z ) ) ) (x z)
>(+12)
3
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 27
A session with Scheme (4)
> ( define ( addOne x )
(+x1) )
#
> ( addOne ( addOne 15 ) )
17
> ( define ( myAnd x y )
( if x y #f ) )
#
> ( myAnd ( symbol? ‘(a) )
#f
> ( and ( symbol? ‘(a) ) ( eq? ‘a ‘a ) )
#f
( eq? ‘a ‘a ) )
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 28
A session with Scheme (5)
> ( define ( myOr x y )
( if x #t y ) )
#
>(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
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 29
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 ) )))))
#
> ( numberList? ‘ ( 1 2 3 4 ) )
#t
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 30
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
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 31
A session with Scheme (8)
>
( define ( eqExpr? x y )
( cond
((symbol?x) (eq?xy)) ((number?x) (eq?xy))
; 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? ‘(ab(cd)) ‘(ab(cd)) ) #t
>(eqExpr? ‘(ab(cd)) ‘(ab(cde)) ) #f
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 32
A session with Scheme (9)
> ( define ( member? K L )
( cond
((null?L) #f) ((eqExpr?K(carL)) #t) (else (member?K(cdrL)))
))
#
> ( 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
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 33
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 #
> ( append ‘( ab bc cd )
‘( de ef fg gh ) )
(ab bc cd de ef fg gh)
> ( exit )
;EXIT
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 34
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) ))
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 35
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)))
))
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 36
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)
(minL-aux Elt cdrl)
))))
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 37
More on local scope
>
(define (quadruple x)
(let ((double (lambda (x) (+ x x))))
(double (double x))
)) #
> (double 8)
unbound variable: double
; in expression: (… double 8)
; in top level environment.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 38
More on local scope (2)
>
(define (quadruple x)
(define (double x) (+ x x))
(double (double x))
)
#
> (quadruple 8)
32
> (double 8)
unbound variable: double
; in expression: (… double 8)
; in top level environment.
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 39
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))
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 40
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))
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 41
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))
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 42
Higher-order functions (4)
Let’s try a small puzzle:
(define (f) (lambda (x) (+ 1 x)))
What is the value of this function?
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 43
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
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 44
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)))
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 45
> (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)))
Reducers (3)
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 46
List manipulation
Defining things
Some built-in names
car define cdr lambda cons
append
list
length
caar, cadr, cdar, cddr,
…,
caaaar, …, cddddr
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 47
Some built-in names (2)
Control
Logic
if not cond and else or let #t begin #f
Arithmetics and comparison
+< -> * <= / >= max = min
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 48
Some built-in names (3)
Predicates
symbol?
number?
integer?
real?
list?
null?
eq?
equal?
procedure?
I/O functions
write
display
print
read
Miscellaneous
load
map
quote
set!
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 49
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
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 50
CSI 3120
Functional programming in Scheme
S. Szpakowicz, N. Japkowicz, R. Falcon
CSI 3120, Scheme, page 51