Transcript function

CHAPTER EIGHT
Functional
Programming
Programming Languages – Principles and Paradigms
by Allen Tucker, Robert Noonan
Background:
• Functional programming originated in the
1960s to support research in AI and symbolic
computing.
• The first functional language was Lisp created
by John McCarthy.
• Other languages have followed, such as
Scheme, Miranda, NL, and Haskell.
• Functional languages continue to be heavily
used in applications such as theorem proving,
rule-based systems, and natural language
processing.
Characteristics:
• In functional programming computation is
viewed as a mathematical function mapping
inputs to output.
• There is no implicit notation of state.
• In “pure” functional languages there is no
assignment statement.
• Loops are modeled by recursion.
• Most functional languages do provide
assignment statements and loop constructs
since they are useful (even to theoreticians).
Functions & The Lambda Calculus:
• Consider the mathematical square function:
Square(n) = n * n
• The function provides a mapping from the set
of real numbers (its domain) to the set of real
numbers (its range):
Square: R  R
• In the lambda calculus the square function can
be expressed as:
(x • x*x)
• Application of the lambda expression is given:
((x • x*x)2)
Pure Lambda Calculus Defined:
Alonzo Church, in 1941, defined a pure lambda
calculus as follows:
• Any identifier is a lambda expression.
• If M and N are lambda expressions, then the
application of M to N, written (MN), is a lambda
expression.
• An abstraction, written (x • M), where x is an
identifier and M is a lambda expression, is also
a lambda expression.
The Lambda Calculus:
• In the lambda expression (x • M) the
identifier x is said to be bound in the
subexpression M.
• Any identifier not bound is said to be free.
• Bound identifiers are placeholders that can
be renamed using any identifier free in M
without changing the meaning of the
expression.
• Free identifiers are defined as:
free(x) = x
free(MN) = free(M)  free(N)
free(x • M) = free(M) – {x}
The Lambda Calculus:
A substitution of an expression N for an identifier
(variable) in M, written M[N/x], can be defined
as:
1. If the free variables of N have no bound
occurrences in M, then the term M[N/x] is formed
by replacing all free occurrences of x in M by N.
2. Otherwise, assume that the variable y is free in N
and bound in M. Consistently replace the binding
and the corresponding bound occurrences of y in M
by a new variable (say u). Repeat renaming bound
variables in M until the condition in step 1 applies,
then proceed with step 1.
Beta-reductions:
• The meaning of a lambda expression is defined
by the following rule:
((x • M)N)  M[N/x]
• If P is a lambda expression, then a redux of P is
any subexpression obtained by a beta-reduction.
• A lambda expression that does not containing a
function application is called a normal form.
• An example of an evaluation:
((y • ((x • xyz)a))b)  ((a • ayz)b)  (abz)
Functional Programming Languages:
• A functional programming language is an
applied lambda calculus with constant values and
functions built in.
• Some evaluate all function arguments at call
time (eager evaluation) and some do not (lazy
evaluation).
• Some functions can’t be safely defined using
eager evaluation:
(if (= x 0) 1 (/ 1 x))
• Haskell uses lazy evaluation while Scheme uses
eager evaluation (why?).
Scheme:
• Scheme is based on Lisp and is one of the two
major variants of Lisp still in widespread use.
• Scheme is a statically scoped dialect of Lisp
invented by G. L. Steele Jr. and Gerald Sussman.
• The text uses a subset of Scheme that lacks an
assignment statement and can be viewed as a
“pure” functional language.
• Programs are written as recursive functions on
input values which produce output values.
• Input values are not modified.
Scheme Expressions:
Expressions in Scheme use Cambridge-prefix
notation:
(+ 2 2)
; evaluates to 4
(+)
; evaluates to 0
(+ 5)
; evaluates to 5
(+ 5 4 3 2 1)
; evaluates to 15
(*)
; evaluates to 1
(* 5)
; evaluates to 5
(* 1 2 3 4 5)
; evaluates to 120
Scheme Expressions:
• Complex expressions are built by nesting:
(+ (* 5 4) (- 6 2))  5*4 + (6 – 2)
• Global variables are defined using the define
function:
(define f 120)
• The define function changes the environment
and can be treated as an assignment statement.
• There is also a set! statement that is a true
assignment statement (which we will ignore).
Expression Evaluation:
• Names of symbols are replaced with their
current bindings:
f
(+ f 5)
; evaluates to 120
; evaluates to 125
• Lists are evaluated as function calls:
(+ 5 4 3 2 1)
(+ (5 4 3 2 1))
(f)
; call with 5 arguments
; error, 5 isn’t a function
; error, f isn’t a function
• Constants evaluate to themselves:
5
Nil
#t
; evaluates to 5
; evaluates to nil, predefined
; true, also predefined
Expression Evaluation:
• Quote or an “’” is used to prevent list evaluation:
(define colors (quote (red yellow green)))
(define colors ‘(red yellow green))
• You can also quote symbols:
(define x f)
(define x ‘f)
(define acolor ‘red)
(define acolor red)
; defines x to be value of f
; defines x to be the symbol f
; defines acolor to be red
; error, symbol red not defined
Lists:
• Lists are the fundamental data type of Scheme,
used for both commands and for data.
• Scheme lists always end in nil, a special
predefined constant.
• A list that doesn’t properly end with a nil will be
displayed like this:
(0 2 4 6 . 8)
• This type of structure is abnormal but can be
formed using some of the list manipulation
functions provided in the language.
• Nil can be thought of as a null pointer…
Structure of a
List in Scheme
(a)
Correct!
Figure 8.1
(b)
Wrong!
Basic Functions:
• The basic list construction function is cons:
(cons 8 nil)
(cons 6 (cons 8 nil)
(cons 4 (cons 6 (cons 8 nil)))
; gives (8)
; gives (6 8)
; gives (4 6 8)
• A scheme list has two parts, a “head” and the
rest of the list or “tail”. The car and cdr functions
return the head and tail:
(define evens ‘(0 2 4 6 8))
(car evens)
(cdr evens)
(car (cdr evens))
(cadr evens)
(cdr (cdr evens)
(cddr evens)
; gives 0
; gives (2 4 6 8)
; gives 2
; gives 2
; gives (4 6 8)
; gives (4 6 8)
More Basic Functions:
• You can use the list function for building lists:
(list 1 2 3 4)
(list ‘(1 2) ‘(3 4) 5)
(list evens ’(10 12))
; gives (1 2 3 4)
; gives ((1 2) (3 4) 5)
; gives ((0 2 4 6 8) (10 12))
• To concatenate two lists use append:
(append ‘(1 2) ‘(3 4))
(append ‘(7 8) ‘())
(append evens ‘(10 12))
; gives (1 2 3 4)
; gives (7 8)
; gives (0 2 4 8 10 12)
•To add a single number to the front of a list use
the cons function:
(cons 10 evens)
; gives (10 0 2 4 6 8)
See the book’s overview for may others.
Defining Functions:
• The define function is used to define functions.
(define name (lambda (arguments) function-body)
for example:
(define min (lambda (x y) (if (< x y) x y)))
• An alternate way of writing defines is:
(define (name arguments) function-body)
for example:
(define (abs x) (if (< x 0) (- 0 x) x))
and
(define (factorial n)
(if (< n 1) 1 (* n (factorial (- n 1)))
))
Next time…
Haskell