COMP1811 Paradigms of Programming
Elements of Functional Programming in Scheme
Lambda forms, High Order Programming
Copyright By PowCoder代写 加微信 powcoder
• Lambda calculus: Historical notes
• High-order programming
– Functions as first-class values – Functions as parameters
– Functions as results
– Partial application
• Key concepts
– Side effect free.
• Equational reasoning (context independent).
– High-order:
• Functions as arguments
– Partial application of arguments • Currying
– 1930 . Model of Computation
• Stateless
• symbolic approach. – Syntax
• Variables: 𝑥, 𝑦, 𝑧
• Abstraction: 𝜆𝑥. 𝑒
• Application: (e1 e2)
– Reduction Rules:
• Alpha reduction (renaming):
𝜆𝑦.𝑦 →𝜆𝑥.𝑥
• Beta reduction ( application): 𝜆𝑦. 𝑦+1 1 →1+1
• Scheme is not based in lambda-calculus, (rather list processing)
• Scheme may have side-effects.
• It can emulate other features, though.
Emulation <> implementation!
Historical notes
𝜆-calculus
• lambda is a predefined symbol/word
• p1…pn are identifiers (parameters…)
• exp can be
• either atom
• or S-Expression
• exp can refer to any
global symbol and/or parameters
parameters
Lambda forms (I)
First-class values
(lambda (p1…pn) exp1)
Mind the number of parameters it applies to.
• As procedures, they can apply on parameters.
• So many parameters as enclosed on after lambda
• See how parameters are replaced.
Lambda forms (II)
• As first-class values, they can be given a name
• Application as ordinary functions
Lambda forms (III)
• A functional takes a function (or several) as parameter.
See how the parameter f applies on the rest of parameters
Functions as parameters
• You may abstract a recursive algorithm.
• Then, define multiple instances, saving coding!.
Generalize to boolean predicate
Functions as parameters
High-order plus recursion
• A lambda form is returned
• n is bound on calling time.
• As a first-class value, it is
applicable
Functions as result
• Partial application (Advanced):
– Being arity n, you can provide m parameters, m