|
Let expressions
Study in your Scheme manual the precise syntax of let expressions
(let ((d 5)) (+ d 2)) is exactly the meaning of
((lambda (d) (+ d 2)) 5) Another example: the value of
(let ((a 3)
(b 5))
(- b a))
is exactly the same of
(lambda (a b) (- b a)) 3 5) This holds even when we define functions, like in
(let ((a 3)
(inc (lambda (x) (+ 1 x))))
(inc a))
The value of this expression is exactly the same as
((lambda (a inc) (inc a)) 3 (lambda (x) (+ 1 x))) Its evaluation corresponds to evaluating the body of the function in which we substitute 3 for a and (lambda (x) (+ 1 x)) for inc, that is
((lambda (x) (+ 1 x)) 3) Now we can go on with the evaluation, obtaining (+ 1 3) and then 4. It is possible to have nested let-expressions:
(let ((a 3)
(fun (let ((a 5))
(lambda (x) (+ a x)))))
(fun a))
This expression, whose value is 8, can be looked at as sintactic sugar for
((lambda (a fun)
(fun a)) 3
((lambda (a)
(lambda (x) (+ a x))) 5))
The semantics we have provided for the let expressions shows also that, given the following definition
(define x 2) the value of
(let ((x 3)
(y (+ x 2)))
(* x y))
is 12 and not 15 as somebody could think. To be sure of it, evaluate the expression with the given semantics. By the given semantics it is clear that the body of the let is evaluated in the enviroment in which the whole let is evaluated, but with the new associations (local-variable, value). Higher-order functions We can define functions taking other functions as arguments or functions returning functions as results (these functions are also called "higher order functions). This fact it no surprise at all, since functions are values for Scheme. An example is the function which takes two functions as input, returns their compositions.
(define (compose f g) (lambda (x) (f (g x))))
We consider now a function on natural number g: N -> N which we assume to be computed by a Scheme function called G.
(define (SG n)
(if (= n 0)
0
(+ (G n) (SG (- n 1)))))
(we recall that (define (SG n)... stands for (define SG (lambda (n)... ) The program PG that, instead, computes the product of the elements g(i)'s, will be:
(define (PG n)
(if (= n 0)
1
(* (G n) (PG (- n 1)))))
Both the programs can be generalized: Let us define the functions Sgen and Pgen that, besides taking as input a natural number n, take also the function on which the sums or the products are performed.
(define (Sgen f n)
(if (= n 0)
0
(+ (f n) (Sgen f (- n 1)))))
(define (Pgen f n)
(if (= n 0)
1
(* (f n) (Pgen f (- n 1)))))
Now, to compute the sum or the product of g(i) for i =1 ...10, we can evaluate the expression (Pgen G 10) or (Sgen G 10). We try now to generalize further and we abstract both from the binary function applied to the various f(i)'s, and from the base index. es. F for i=3..5 of f(i) = F(F(f(3),f(4)),f(5))
(define (Ftoria F f b n)
(if (= n b)
(f b)
(F (f n) (Ftoria F f b (- n 1)))))
Now with this new function at hand we can easily define Sgen and Pgen as follows
(define (Sgen f n)
(Ftoria + f 0 n))
(define (Pgen f n)
(Ftoria * f 0 n))
We could also generalize Ftoria further, by abstracting on the predecessor function for the linear order over the finite set over which f is defined, and over the equality relation on the element of the set:
(define (FtoriaOrd F f low up pred eq)
(if (eq up low)
(f up)
(F (f up) (Ftoria F f low (pred up) eq))))
How can Sgen be defined out of FtoriaOrd?
(define (Sgen f n)
(FtoriaOrd + f 1 n (lambda (x)(- x 1)) =))
Well... maybe with FtoriaOrd we have gone a bit too far with the generalization... but you have noticed how very general functions can be defined and how other functions can be easily defined out of them. Take the insert function, a function that takes a number and put it in the right place in a list of numbers already ordered in increasing order.
(define (insert el ls)
(cond ((null? ls) '())
((> el (car ls))
(cons (car ls)
(insert el (cdr ls))))
(else (cons el ls))))
Well we could write this function in order to work on list of elements belonging to any set over which a total ordering relation is defined.
(define (geninsert el ls greater)
(cond ((null? ls) '())
((greater el (car ls))
(cons (car ls)
(geninsert el (cdr ls) greater)))
(else (cons el ls))))
You see, now the previous insert could be simply defined as
(define (insertnum el ls) (geninsert el ls >)) Exercise: write the sorting functions on lists, using the total ordering relations as input. Let us see an example of a function that returns a function as output. We define a higher order function returning a function (from natural numbers to natural numbers) identical to the one given as argument, but in a point, for which a new value is provided.
(define (change-value-at-n f n new-value)
(lambda (x)
(if (= x n)
new-value
(f x))))
Let see an example of how we can define a higher-order function by recursion "on functions"
(define (F f)
(if (= 0 (f 3))
f
(F (lambda (n)
(cond ((= n 5) (+ (f 5) 2))
((= n 3) (- (f 3) 1))
(else (f n) ))))))
You see, the one above is a possible (complex) way to define the following higher-order function
(define (F f)
(lambda (n) (cond ((= n 5) (+ (f 5) (* (f 3) 2)))
((= n 3) 0)
(else (f n) ))))
change-value-at-n can be used to define the following function
(define strange-sqrt (change-value-at-n sqrt 81 'cucu)) we can evaluate
> (strange-sqrt 9) 3 > (strange-sqrt 81) cucu > From the above example you can see that owing to the lack of any type check on the arguments (no types is Scheme, only run-time checks on the predefined functions and constants), we can create functions returning values not belonging to the the codomain. This possibility can raise several problems. Exercise: let us consider the following Scheme function
(define (X-recursion f)
(let ((at-41 (f 41)))
(lambda (x)
(if (= 0 at-41)
(f 103)
(+ 3
((X-recursion
(change-value-at-n
f
41
(- at-41 1))) x) )))))
We can now evaluate the following expression (see section Curryfication below for currify):
> ((X-recursion ((currify + 2) 3)) 3) 238
Why the X-recursion function terminates? Curryfication We talked about curryfication in theory, let us see an example in Scheme. Now we can write the curryfied version of compose
(define (currified-compose f)
(lambda (g)
(lambda (x)
(f (g x)))))
we can use the power of the higher order functions to define a function taking a function of 4 arguments and returning its curryfied version.
(define (currify-fun-4-arg f)
(lambda (x)
(lambda (y)
(lambda (z)
(lambda (t)
(f x y z t))))))
as example of application of the above function we define
(define (=4 a b c d)
(and (= a b)
(= a c)
(= a d)))
if we evaluate (=4 1 1 1 1) we get #t,
(define currified-=4 (currify-fun-4-arg =4) ) now we can generalize by determining a generic "curryfier" taking a function, a number n less than or equal to its number of arguments and returning the partial curryfication (or total if n is equal to its number of arguments of the function).
(define (currify f n)
(letrec ((currl (lambda (f n ls)
(if (= n 0)
(apply f ls)
(lambda (x)
(currl f
(- n 1)
(cons x ls) ))))))
(currl f n '())))
It is important to emphasize the use of the local function currl and of the apply function (apply takes a function of k arguments, a list of lenght k and applies the function on the elements of the list.) Now we can do the following evaluations
> (((((currify =4 4) 1) 1) 1) 1) #t > (((currify + 2) 2) 3) 5
Why is not possibile to define currify without using a local function ? |