Transcript functions - Computer Science and Engineering

Functional Programming
A functional program: Collection of functions
A function just computes and returns a value
No side-effects
In fact: No program variables whose values change!
A function body: Mainly calls to other functions
Languages: LISP, Scheme, ML, Haskell, ...
CSE 3341/655; Part 4
55
Logic Programming
Program just says what is needed, not how to compute it
The “system” figures out the how
DB systems are (sort of) logic programming systems
Languages: Prolog
Logic programming is not very popular except as DBs
CSE 3341/655; Part 4
56
Functional Languages (Chap. 10)
Must provide:

Suitable data types

Set of primitive functions

A notation for calling functions

Way to construct new functions by composing existing
ones in different ways
CSE 3341/655; Part 4
57
Lisp/Scheme Data Types


Data Types:
Atomic and non-atomic S-expressions (“symbolic exps.”)
Atoms:
 Numbers (we use only integers)


Strings: “xyz”, “34” etc.
Symbols (i.e., identifiers): XYZ, AB12, + etc.
Some important symbols:
#t (denotes true ; written T in Lisp)
#f (denotes false ; written NIL in Lisp)
CSE 3341/655; Part 4
58
Lisp/Scheme Data Types (contd.)




Non-atomic S-expressions:
If s1 and s2 are s-expressions, so is (s1 . s2)
Important primitive functions:
 cons[ s1, s2] = (s1 . s2)
 car[ (s1 . s2) ] = s1
 cdr[ (s1 . s2) ] = s2
 cadr[ s ] = car[ cdr[ s ] ]
cadar[ s ] = car[ cdr[ car[ s ] ] ]
Important: Everything in LISP/Scheme is an s-exp.
Important: Best to think in terms of how s-exps are
stored internally: binary trees (using pointers)
CSE 3341/655; Part 4
59
List Notation
List Notation:
( ) denotes NIL
(6) denotes (6 . NIL)
(6 5) denotes (6 . (5 . NIL))
(6 5 5) denotes (6 . (5 . (5 . NIL)))
((1 . 2) 3) denotes ((1 . 2) . (3 . NIL))
((1 . 2) (3 . 4)) denotes ((1 . 2) . ((3 . 4) . NIL))
In general:
(s1) denotes (s1’ . NIL) [s1’ : "dot version" of s1 ]
(s1 s2) denotes (s1’ . (s2’ . NIL))
(s1 s2 s3 ... ) denotes (s1’ . (s2’ . (s3’ . NIL))) etc.
CSE 3341/655; Part 4
60
List Notation (contd.)


The Scheme/LISP interpreter converts everything to “dot”
notation; list notation is only for input/output
Convert:




((1 . 3) 2 4)
(1 . (2 . NIL))
(1 . (2 . 3))
((1 . 3) (2 . 4))
((1 . 3) (2 4))
((1 . NIL) . (2 . NIL))
((1 . 2) . NIL)
((1 3) (2 4))
Consider car, cdr, cddr etc. of ((1 . 2) (3 . 4)),
((1 . 2) . (3 . 4)) etc.
car, cdr, cons are best understood in terms of how they
manipulate s-expressions internally.
CSE 3341/655; Part 4
61
Built-in Functions
More functions:
 eq?[ x, y ] : returns #t or #f if x, y are/are not same atom
eq?[ #t, #f ] = #f
eq?[ #f, #f ] = #t
eq?[ #f, 5 ] = #f
: arguments to eq? must be atoms


pair?[
pair?[
pair?[
pair?[
pair?[
x ] : returns #t if x is a "pair"; #f otherwise
(2 . 3) ] = #t
(2 . #t) ] = #t
#t ] = #f
() ] = #f
null?[ x ] : returns #t if x is (); #f otherwise
CSE 3341/655; Part 4
62
Built-in Functions (contd.)
Standard math functions (arguments must be numbers):
 +[ 10, -5 ] = 5
 -[ 10, -5 ] = 15
 *[ 10, -5 ] = -50
 /[ 10, 5 ] = 2
/[ 10, 7 ] = 10/7
 >[ 10, -5 ] = #t
 =[ 10, -5 ] = #f
 ... many others; but we won't use most of them
***Introduce actual notation at this point; don't use design
notation***
Important: We have not yet seen any Scheme programs
The above are just meanings of these built-in functions
CSE 3341/655; Part 4
63
Atoms, Parameters, Arguments
Important: Atoms are used for three purposes:
 Constants: numbers, #t, #f (we won't use string consts.)
 Function names: car, cdr, eq?, +, >, ...
 Function parameters (in function definitions)
Important:
Distinction between parameters and arguments
(also: "formal parameters" and "actual arguments")
CSE 3341/655; Part 4
64
Defining New Functions





addUpList[ L ] : return sum of nos. in L (a list of nos.)
addUpList[ L ] ::
; "design notation", not Lisp/Scheme
[ null?[ L ]  0
| #t  +[ car[L], addUpList[ cdr[L] ] ] ]
addUpList[ (2 3 4) ] : returns 9; how does it work?
nNil[ n ] : if n is 4 return (NIL NIL NIL NIL)
nNil[ n ] ::
[ =[ n, 0]  NIL
| #t  cons[ NIL, nNIL[ -[n, 1] ] ] ]
doubleUp[ s ] :: cons[ s, s ] ; what does it do?
length[ L ] :: ; should return length of list L
mystery[L] :: nNil[ length[ L ] ] ; what does it do?
CSE 3341/655; Part 4
65
Scheme/Lisp "Programs"


Starting Scheme (on stdlinux):
% scheme48
... welcome, ...
Type ,? for help
; type in a Scheme expression; the interpreter evaluates
; it, outputs the value, waits for the next Scheme exp.
> ,exit
Simplest Scheme expression: constant atoms:
% scheme48
> 655
655
CSE 3341/655; Part 4
66
Scheme/Lisp Expressions

Function application:
F[a1, a2, a3, ..., an]  (F a1 a2 a3 ... an)
The interpreter *evaluates* a1, a2, ..., an;
binds the resulting values to p1, p2, ..., pn, the pars of F;
then it evaluates the body of F (as a Scheme exp)
> (+ (+ 2 3) (* 5 6) )
; evaluates (+ 2 3), (* 5 6), binds to pars of +, then
; evaluates body of + [using values bound to pars when
; needed]
> (cons (+ 2 3) (* 5 6) ) ; similar; result:
(5 . 30)
> (cons A B) ; error! "unbound A, B"
> (cons #t #f) ; okay! #t, #f evaluate to #t, #f
CSE 3341/655; Part 4
67
Quoted expressions
> (quote A) ; Don't evaluate A
A
(quote ...) looks like a function call; but it is not; it can't be!
It is a form [also "special form"]; only three special forms
> (cons (cdr (A . B) ) (car (A . B) ) ) ; Error!
> (cons (cdr (quote (A . B)) ) (car (quote (A . B)) ) )
(B . A)
> (cons (quote (cdr (A . B)) ) (quote (car (A . B)) ) )
???
CSE 3341/655; Part 4
68
Conditional expressions (Another Special Form)
(cond (b1 e1) (b2 e2) ... (bn en) )
: each bi, ei is a Scheme/Lisp expression
To evaluate:
Evaluate b1; if value is #t, evaluate e1, return that value
if b1 value is #f, evaluate b2; if #t, eval e2, return that val
if b2 value is #f, evaluate b3; if #t, eval e3, return that val
...
if b(n-1) value is #f, eval bn; if #t, eval en, return that val
else ... error!
(cond
( (> 5 3) 3 )
( #t (3 . 5) ) )
(cond
( (> 3 5) (cons 3 5) )
69
( #t (cons 5 3) ) ) CSE 3341/655; Part 4
Function Definitions (Sp. Form)
(define (F p1 p2 ... pn) ..body (Scheme exp.).. )
> (define (silly p1 p2) 5)
..okay.. [or some such acknowledgment]
> (silly 10 20)
5
> (silly (10 . 20) (20 . 30))
Error!
> (silly (cons 10 20) (cons 20 30))
5
> (silly (quote (10 . 20)) (cons 20 30))
5
CSE 3341/655; Part 4
70
Defining new functions (contd)
xmemb[x, list] :: ; is x a member of list?
[ null?[list]  #f
| eq?[x, car[list]]  #t
| #t  xmemb[x, cdr[list]] ]
>(define (xmemb x list) ; is x a member of list?
(cond
( (null? list) #f )
( (eq? x (car list)) #t ) ; quote list?
( #t (xmemb x (cdr list) ) ) ) )
; no values returned
>(xmemb 3 (quote (2 3 4)) )
#t
CSE 3341/655; Part 4
71
Function Definitions (contd.)
equal[ x, y ] :: ; x and y may not be atoms
[ pair?[x]  [pair?[y] 
[equal[car[x],car[y]]  equal[cdr[x],cdr[y]]
| #t  #f]
| #t  #f ]
| pair?[y]  #f ; why?
| #t  eq?[x,y]]
> (define (equal x y)
(cond ( (pair? x)
(cond ... ) )
( (pair? y) #f )
( #t (eq? x y)) ) )
> (define (atom? x) ...) ???
CSE 3341/655; Part 4
72
Defining new functions (contd)
xunion[s1, s2] :: ; union of atomic lists, less duplicates
[ null?[s1] --> s2
| null?[s2] --> s1
| #t --> [ xmemb[car[s1],s2] --> xunion[cdr[s1], s2]
| #t --> cons[ car[s1], xunion[cdr[s1], s2] ] ] ]
; better:
xunion[s1, s2] ::
[ null?[s1] --> s2
| null?[s2] --> s1
| xmemb[car[s1],s2] --> xunion[cdr[s1], s2]
| #t --> cons[ car[s1], xunion[cdr[s1], s2] ] ]
CSE 3341/655; Part 4
73
Function Definitions (contd.)
addUpList[ L ] ::
[ null?[ L ]  0
| #t  +[ car[L], addUpList[ cdr[L] ] ] ]
> (define (addUpList L)
(cond
( (null? L) 0 )
( #t (+ (car L) (addUpList (cdr L) ) ) ) ) )
.. okay ..
> (addUpList (2 3 4) )
Error!
> (addUpList (quote (2 3 4) ) )
9
; but how does it work?
CSE 3341/655; Part 4
74
Function Definitions (contd.)
nNil[ n ] ::
[ =[ n, 0]  NIL
| #t  cons[ NIL, nNIL[ -[n, 1] ] ] ]
> (define (nNil n)
(cond
((= n 0) (quote ()) ) ; why?
(#t (cons '() (nNil (- n 1))) ) ) )
doubleUp[ s ] :: cons[ s, s ]
(define (dUp s) (cons s s) ) ; need to quote s?
CSE 3341/655; Part 4
75
Different styles in Lisp
maxList[L] ::
; returns max of number in non-empty list L
; Functional:
[ null?[cdr[L]] --> car[L]
| >[car[L], maxList[cdr[L]] --> car[L]
| #t --> maxList[cdr[L]] ]
; Functional but better:
[ null?[cdr[L]] --> car[L]
| #t --> bigger[ car[L], maxList[cdr[L]]] ] ; define bigger
; imperative:
maxList[L] = max2[car[L], cdr[L]]
max2[x, L] ::
[ null?[L] --> x
| >[x, car[L]] --> max2[x, cdr[L]]
| #t --> max2[ car[L], cdr[L] ] ]
CSE 3341/655; Part 4
76
More functions

How do you obtain first element of a list?

How do you obtain the last element? [watch out!]

How do you append two lists? [No, not just cons!]

How do you reverse a list? [best: use imperative trick]
(Maybe do this on Piazza?)
CSE 3341/655; Part 4
77
How Lisp interpreter works
Five types of Lisp expressions ("programs"):
 Constants: 4, 5, #t etc.: Evaluate to themselves [4, 5 etc]


Symbols: X, Y, etc.
Look them up on the "association" list [a-list].
Scope rule: Lisp vs. Scheme
Function application: (F a1 a2 a3 ... an)
F is a (built-in or user-defined) function that expects
n parameters; each ai is a Lisp expression;
Evaluate each ai; bind that value aiv to pi, the
corr. parameter, by adding (pi . aiv) to the a-list;
then evaluate the body of F
CSE 3341/655; Part 4
78
Lisp Exps./How they are eval'd (contd)



Quoted exp: (QUOTE s) : where s is any s-exp;
evaluates to s
Conditional: (COND (b1 e1) (b2 e2) ... (bn en) )
b1, b2, ... and e1, e2, ... are all Lisp expressions;
eval. b1, b2, ... to find the first bj that eval's to non-NIL;
eval corr. ej & return its value; if all bi's eval to NIL, error!
Fn. def.: (DEFINE (F p1 ... pn) fe) : F is new fn., p1, ..., pn
its parameters, fe the body; save def. on "d-list".
CSE 3341/655; Part 4
79
Lisp Interpreter (partial) (*in* Lisp!)
Three key functions:
 eval: evaluates a Lisp-exp.

evcon: evaluates a conditional Lisp-exp.

apply: applies a function to given set of arguments
interpreter[exp, dList] = eval[exp, NIL, dList] ; why?
evcon[pairs, aList, dList] =
[ null?[pairs] --> "error"!
| eval[caar[pairs],aList,dList] --> eval[cadar[pairs],aList,dList]
| #t --> evcon[cdr[pairs], aList, dList] ]
CSE 3341/655; Part 4
80
Lisp Interpreter (partial) (contd.)
eval[ exp, aList, dList] =
[ atom?[exp] --> [ int?[exp]
--> exp
| eq?[exp,#t] --> #t
| eq?[exp,#f] --> #f
| in?[exp,aList] -->getVal[exp,aList]
| #t --> "unbound variable!" ]
| atom?[car[exp]] -->
[ eq?[car[exp],QUOTE] --> cadr[exp]
| eq?[car[exp],COND] -->
evcon[cdr[exp], aList, dList]
| #t --> apply[car[exp],
evlis[cdr[exp],aList,dList],
aList, dList] ]
CSE 3341/655; Part 4
81
Scheme vs. LISP
Differences (with LISP):




#t and #f : for "true" and "false" [Lisp uses T, NIL for this]
NIL always written as () and is not a normal atom;
In fact, Scheme talks of "pairs" vs. "non-pairs",
not "atoms" and "non-atoms"
Scope rule
 What "scope rule" means
 How it works in Lisp/Scheme
Elimination of some imperative features
CSE 3341/655; Part 4
82