Functional Programming and Scheme
CMPSC 461
Programming Language Concepts Penn State University
Fall 2020
Church Encoding Natural numbers
n≜ λ𝑓𝑧.𝑓!𝑧
PLUS ≜ λ𝑛” 𝑛#. (𝑛” SUCC 𝑛2)
Definition
2
Church Encoding: Example Natural numbers
n≜ λ𝑓𝑧.𝑓!𝑧
MULT ≜
Definition
3
Multi-Argument Functions
SUCC≜λn𝑓𝑧. 𝑓 𝑛𝑓𝑧 PLUS ≜ λn1 𝑛2. 𝑛1 SUCC 𝑛2
Currying: every function is treated as one that takes at most one parameter at one time
(𝜆𝑥”𝑥#…𝑥!.𝑒)isthesameas𝜆𝑥”. 𝜆𝑥#. … 𝜆𝑥!.𝑒 so
(𝜆𝑥 𝑦.𝑡) 𝑡” 𝑡# is the same as 𝜆𝑥. 𝜆𝑦.𝑡 𝑡” 𝑡#
4
Named Functions Usedefinition SUCC≜λn𝑓𝑧. 𝑓 𝑛𝑓𝑧
in term (SUCC (SUCC 1 ))?
Syntax: let name = def in body (or, let (name def) body)
E.g.,letSUCC=(λn𝑓𝑧. 𝑓 𝑛𝑓𝑧 )in(SUCC(SUCC 1 ))
let name = def in body is just a shorthand for
(λname. body) def
5
Pure vs. Applied λ-Calculus Pure λ-Calculus: the calculus discussed so far
Applied λ-Calculus:
• Built-in values and data structures (e.g., 1, 2, 3, true, false, (1 2 3))
• Built-in functions (e.g., +, ∗, /, and, or)
• Named functions • Recursion
All features can be encoded in the pure λ-Calculus!
6
Functional Languages
Lisp
Common Lisp
Scheme
ML
Haskell
SML
OCaml
7
Running Scheme Racket: a Scheme-based language
https://racket-lang.org
DrRacket: IDE for Racket
8
Scheme
We focus on the non-imperative subset of Scheme (no assignments, whiles)
Syntax:
• Atoms: e.g., 3, #t, #f, “abc”
• Lists: (3 #t “abc”)
• Functions: (sqrt 2), (+ 1 2 4)
• Comments: (+ 1 2) ; evaluate to 3
Read-Eval-Print Interpreter
• (sqrt 2) is the same as (eval ‘(sqrt 2))
Prefix form
9
Parenthesis in Scheme
In Scheme, () is used for lists, and both code
and data are lists
• (+ 2 3) • (2 3 4)
Function is a first-class value
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)
10