Functional Programming and Scheme
CMPSC 461
Programming Language Concepts Penn State University
Fall 2020
Parenthesis in Scheme
In Scheme, () is used for lists, and both code
and data are lists • (+ 2 3)
• (2 3 4)
Lists are evaluated as function calls
• (+ 2 3) Evaluates to 5
• ((+ 2 3)) Exception: 5 is not a procedure • (2 3 4)
Exception: 2 is not a procedure
Lists w/o evaluation: use apostrophe (’)
• ’(234)
Returns (2 3 4)
2
Expressions Arithmetic:
Relational: Conditional: Type test:
(* 1 2 3 4)
(+ (* 1 2) (* 2 4))
(< (* 1 2) (+ 1 1))
(and (> 2 4) #f)
(if (< 2 3) 1 (+ 2 3))
(* 2 (if (< 3 5) 3 “abc”))
(number? 2) (number? #f)
(string? “a”) (string? 1)
(boolean? #t) (boolean? 1)
3
Environment
Environment binds identifiers to values
• +,*,-,/ are identifier bound to values • Functions are values in Scheme
Built-in identifiers in initial environment
• +, sqrt, positive?, max, ...
Add bindings to the environment • Key word: define
4
Definition Built-in identifiers
(max 1 2 3)
“define” introduce global identifiers
(define pi 3.14159)
(define radius 2)
(* pi (* radius radius))
(define circumference (* 2 pi radius))
circumference
5
Local Definition Let Expr.:
(let ((x 3)
(y (sqrt 7)))
(+ x y))
(let ((x1 exp1)
(x2 exp2)
...
(xn expn))
body_exp)
General form:
x1,x2,...,xn can be used in body_exp
6
Local Definition Let* Expr.:
(let* ((x 3)
(y x))
(+ x y))
(let* ((x1 exp1)
(x2 exp2)
...
(xn expn))
body_exp)
General form:
x1 can be used in exp2, exp3, ..., body_exp x2 can be used in exp3, exp4, ..., body_exp ...
7
Anonymous Function
Anonymous functions are introduced by lambda
Example
(lambda (x y z) expr)
parameters func. body
((lambda (x) x) 1)
((lambda (x y z) (+ x y z)) 1 2 3)
((lambda (f) (f 2)) (lambda (x) (* 2 x)))
8
Named Function
(define pi 3.14159)
In Scheme, function is a first-class value, so similarly, we can define named functions
(define f (lambda (x) (+ x 1)))
(f 1)
(let ((f (lambda (x) (+ x 1)))
(g (lambda (y) (* y 2))))
(+ (f 1) (g 2)))
9
Named Function
In Scheme, named functions can be introduced in a more concise way:
(define (f x) (+ x 1))
func. name parameter
is the same as
(define f (lambda (x) (+ x 1)))
10
Named Function
Common use:
Name Parameter
(define (sqr x) (* x x))
(sqr 5)
(define (area x y) (* x y))
(area 5 10)
(define (f x y z)
(let ((x1 exp)
(x2 exp))
f’s body))
11
Function Examples
(define (test x)
(cond ((number? x) "num")
((string? x) "str")
((list? x) "list")
(else "other")))
(define (abs x)
(cond ((< x 0) (- x))
(else x)))
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
12
Scheme: Key Points
Evaluation of expressions
(e0 e1 e2 e3)
define, if, cond, ‘
Key words
No static type system
(define (f x) (+ x “abc”))
(* 2 (if (< 3 5) 3 “abc”))
13
Scheme: Key Points
No assignments, no iterations (loops)
All variables are immutable (mathematical symbols)
14