Transcript Functional Programming COMP2003

Some non-recursive tricks.
The Lambda expression.
More on Let, Let*, apply and funcall
The apply-append trick
• Suppose we have a list L of lists and we wish to
join all the lists in L end-to-end. For example
suppose L is:
( (a f g) (c d) ( ) (p q r))
and we want a function that will essentially
“remove the first-level brackets” to give:
(a f g c d p q r)
All we need is:
(apply #’append L)
LAMBDA
1.
2.


So far, we have seen two places in which a symbol can
be used to refer to a function:
As the first item in a list representing a function call:
(append x 12)
With (function …) wrapped round it when acting as the
argument to another function: (apply #’* (find-numbers))
What can actually appear in these positions is either a
symbol which is the name of a function or a description
of an unnamed function. The latter effect is achieved
using a lambda definition. A lambda definition is just like
an ordinary function definition, except that:
There is no function name specified
The word lambda is used instead of defun
LAMBDA
(lambda (L) (first (rest L))
> ((lambda (L) (first (rest L))) ‘(a b c d e))
b
>(funcall #’(lambda (L) (first (rest L))) ‘(a b c d e))
b
>(apply #’(lambda (L) (first (rest L))) ‘((a b c d e)))
b
Note:
1. The #’ is not part of the lambda definition, but has to be stuck
on the front just when the lambda expression is being passed as
an argument to another function
2. When the lambda expression appears in the privileged first
position, it does not need the #’, just as the symbolic name of a
function does not need it; however, when the lambda expression
appears as an argument to another function, it does need the #’.
> ((lambda (A B) (* (+ A B) (-A B) ) ) 10 3)
91
> (funcall #’(lambda (A B) (* (+ A B) (-A B) ) ) 10 3)
91
> (apply #’(lambda (A B) (* (+ A B) (-A B) ) ) ‘(10 3))
91
What is lambda for:
1. When the function definition is specific to a particular
situation, and so can be defined and used in just one
place. Usually the motive for forming the computation
into a function is that it is being passed in as argument to
some other functions which will use that computation in
various ways, probably applying it repeatedly
2. When there is a need to manipulate variable names so
that certain variables are “in scope” at the right time
3. When a function is constructing a function which it will
then return as its result; that is, the result of some
computation is not merely a data-structure, but is a new
function definition which can then be passed on and
used.
Consider this EXAMPLE:
This function returns a
function as its answer!!!!!
(defun fncomp (fn1 fn2)
#’(lambda (val)
(funcall fn1 (funcall fn2 val))
)
g is now the function
)
returned by fncomp
>(setf g (fncomp #’first #’rest))
> (funcall g ‘(a b c d))
b
g = #’(lambda (val)
(funcall #’first (funcall #’rest val))
Reminder: LET
• Although strict functional programming does not allow the
use of assignment to local variables, Common Lisp has a
command which gives a limited (but very useful) kind of
variable declaration and initialization which does not
violate the principles of functional programming.
• The let command:
– Declares one or more local variables
– Optionally gives them initially values
– Executes a sequence of S-expressions using these settings
The general format of LET command:
( let ( (<variable-1> <value-1>)
(<variable-2> <value-2>)
…
(<variable-N> <value-N>)
)
<S-expression-1>
<S-expression-2>
…
<S-expression-K>
)
EXAMPLE
A function to work out (factorial x) + y(factorial x)
(defun example(x y)
(let ( (a (factorial x))
)
( + a (power y a))
)
)
Because we have to use the
factorial value twice, we use a
let to hold that value in a
variable called a.
LET and LAMBDA
• A LET command can be thought of as directly equivalent
to the use of a lambda expression. A LET statement,
introduces variables, gives them initial values, evaluates
some expressions, then discards the variables; this is
essentially what happens when a lambda function is
defined and then used immediately
• Compare:
( let ((x 3) (y 4))
(+ (*x y) (+ x y))
With:
((lambda (x y) (+ (*x y ) (+ x y))) 3 4)
Example with Lambda
A function to work out (factorial x) + y(factorial x)
(defun example(x y)
( (lambda(a) ( + a (power y a)))
(factorial x)
)
Because we have to use the factorial
)
value twice, define a lambda function
and give it (factorial x) as its
argument. That argument can then be
used inside the lambda function twice.
• Hence, using LET does not go beyond the
principles of functional programming, since it is
simply a handy notation for defining and then
immediately using a LAMBDA expression.
• However, do not use LAMBA function calls simply
to introduce and bind local variables – the
examples here are merely to illustrate a
conceptual point. The natural way to introduce
local variables and give them initial values is the
LET command; trying to do it with LAMBDA will
be rather complicated.
LET = simultaneous assignment
• In the LET command the initial values of variables are all
assigned simultaneously, so the initialization of one
variable cannot assume the value of one of the other
variables in the same header. Hence in:
(let ( (x (rest y))
(z (first x))
)
…
)
The expression (first x) will refer to some x which is available,
outside the LET command, not to the x which is alongside it
in the LET statement
LET*
• The LET* introduces and initializes the variables one after
another (sequentially) so that variables can be used as
soon as they are set up, even in further initializations:
> (setf x 3)
3
> (let ((a x) (x 5) (b x)) (list a x b))
(3 5 3)
> (let* ((a x) (x 5) (b x)) (list a x b))
(3 5 5)
Bound and free variables:
• The LET & LAMBDA constructs are examples of
statements which can introduce new variables
with a clearly defined (and limited) scope.
• A variable is said to be bound within the area of
program to which it belongs; in the case of LET
command, that area is what is called the “body”
of the LET command.
• Any variable mentioned in a piece of program
which is not “bound”within that piece of program
text is said to be free in that text.
• For example consider the following function:
(defun example(x y)
(let ( (a (factorial x))
)
( + a (power y a))
)
)
If we were to consider the LET block in isolation, the
variable x is free with respect to that block.
However, x is bound with respect to the function
example. (its bound in the argument to the function)
LEXICAL SCOPING
• Common Lisp relies on what is known as lexical
scoping which means, roughly, that a variable
may be referred to at any point in the program
which is textually enclosed by the construct
which introduced the variable. If there are several
enclosing statements and if two of these have
introduced variables with the same name, it is the
innermost one which is taken as being referred
to.
• Try the next examples:
> (let ((x 6) (y 7))
print is a built in lisp
(print x)
function that prints
(print y)
something directly on
the console, rather than
(let ((x 10) (z 8))
returning it as a value. I
(print x)
just use it here to make
(print y)
a point.
(print z)
Notice that when we first print x,
)
we get 6 (inside the outer let), but
(print x)
when we next print x (inside the
inner let) we get 10. Finally, when
)
> 6 7 10 7 8 6
we print x in the outer let again, we
get 6 again
Similar nesting rules apply if there is a lambda function
inside another lambda function