This page is kept for historical purposes only. Please see the home page for my current situation. —Luca Saiu.

DLL: TP 2 - More advanced aspects of Scheme programming

This afternoon you will learn some more advanced features of the Scheme language; those features are useful and contribute to make the language powerful, but by themselves they are not particularly deep or difficult to understand; anyway you must have understood the lesson about Scheme and what you saw in the first TP before doing this. If the last time you didn't understood something but you didn't tell me, please tell me now.

Today's TP is divided into three parts: some more exercises on what we saw the last time, an introduction to some new language features, and one long exercise in which you'll use today's new features.

If you already know ML then the first TP has been just a review for you. Some of today's tasks, by contrast, will begin to show you what makes Scheme different from the other languages - ML included.

When you work at the Institut Galilée labs, before starting, you have to execute the following line on every terminal you use:

source ~10706282/add-prefix ~10706282/usr
That is for using the software I have installed in my home directory on the machines at Institut Galilée; I don't have administrator privileges on the lab machines, so I have installed everything in my home directory.

Of course you don't need to do anything similar at home if you have installed everything correctly, because you are the administrator of your own machines.

You can find some practical suggestions at the bottom of the first TP page.



Task 0: Subscribe to the mailing list

I've seen that very few people subscribed to the mailing list, so chances are that you didn't; please do it now.
A student noticed that the page may ask you to accept certificates. Don't worry, the server is at LIPN, Université Paris 13; it's perfectly safe.


Task 1: Another exercise on recursion

You can skip this if you think you're already good at writing recursive functions.

The predefined function iota takes as its single parameter a natural number n, and it returns the list of n naturals from 0 to n - 1, in order. So for example (iota 5) returns the list (0 1 2 3 4).
Implement the same functionality in a function called my-iota. You can test your function with the code:

(display (my-iota 0)) ; it should print ()
(newline)
(display (my-iota 3)) ; it should print (0 1 2)
(newline)

A useful variant of iota is called range and takes two arguments, a minimum and maximum bound. Let's say they are both strict, so that for example (range 2 4) returns the list (2 3 4).

Define range as a recursive function, and test it.

Now, define range using iota and map (you saw map in the first TP), without directly using recursion. You will need a lambda.
Test this second definition of range.

Last week a student asked me how to write for loops, and I answered him that it's best to avoid them. I think now you can better understand the reason: it's very easy to use map or iterate with iota and range; this is similar to what one obtains with for loops in other languages, but in a functional style.

For those who know ML: there is also an equivalent of fold in Scheme which of course is more general, but I will not cover it. If you are interested, look for reduce and reduce-right in the Guile manual.


Task 2: logical quantifiers as higher-order function on lists

Again, you can skip this if you think you're already good at writing higher-order recursive functions.

Write a function called for-any? taking two parameters: another function of one parameter (let's call it p?; we say it's a "predicate" and we give it a name ending with a question mark because it's result is a boolean), and a list (let's call it xs). for-any? should return #t if the predicate p? returns #t when applied to some element of xs; if no such element exists then for-any? should return #f. for-any? should not examine all the elements of xs unless it's needed.

Here's a nice way to test it. As you may imagine even? returns #t if its argument is even, #f if it's odd, and it fails if the argument is not a number:

(display (for-any? even? '(1 3 5 7 9))) ; it should print #f
(newline)
(display (for-any? even? '(1 3 5 42 9))) ; it should print #t
(newline)
(display (for-any? even? '(1 3 5 42 foo))) ; it should not fail
(newline)
You should have understood that for-any? represents the existential quantifier ∃: it checks whether there exists some element in the list on which the predicate is true.

Now implement a similar function called for-all?, which represents the universal quantifier ∀: for-all? checks whether the predicate is true on all the elements of the list.
You can write the testing code above by yourself, modifying the testing code for for-any?.

It's quite normal in functional programming to use functions such as for-any? and for-all? instead of loops or explicit recursion. Higher-order functions help to make your program very compact.


Task 3: variadic functions

By now you should have already discovered that the function + works on any number of parameters, rather than only with two of them. Test the following expressions in interactive mode:

(+)         ; zero arguments. What's the result?
(+ 20)      ; one argument
(+ 1 2)     ; two arguments. Ok, this is not surprising
(+ 1 2 3 4) ; four arguments

Nice! It's much more convenient to simply write (+ a b c d) rather than, for example, (+ (+ a b) (+ c d)). Some other functions you already know, such as the predefined version of append, are also variadic.

Functions such as +, which work on an arbitrary number of optional parameters (but in some cases may have some obligatory parameters: + has only optional parameters, since it also works with zero parameters) are called variadic functions.

In the C library there are some predefined variadic functions: the classic example is printf(). You can also define variadic functions yourself in C, but it's very clumsy and hard to do in a safe way; and in other languages it's simply impossible. In Scheme it's actually very easy.

Optional: why + and append are particularly good candidates to be variadic? What makes them easy to understand when used with varying numbers of parameters? A particular mathematical property holds on them... Which one? Tell me if you know.

When I spoke about parameter specifications in lambda and the compact version of define in the first lesson, I only mentioned lists of symbols. For example, you know that

(lambda (a b)
  (/ (+ a b) 2))
is a function of exactly two parameters, called a and b. You can say the same about the function defined in
(define (average a b)
  (/ (+ a b) 2))
, because you know that the whole definition is just an abbreviation of
(define average
  (lambda (a b)
    (/ (+ a b) 2)))
.

What I have told you the first time is correct, but it's not the whole story; there is one more syntactic case in lambda (and define) which you don't know yet: a parameter specification can also be a symbol. Let's give a more formal definition by induction:

A parameter specification may be:

In the compact form of definitions, (define (name . PARAMETER-SPECIFICATION) BODY) is an abbreviation of (define name (lambda PARAMETER-SPECIFICATION BODY)).

The second case (in red) is new; you already knew the first and the third one, even if I didn't explicitly speak about conses in the context of the syntax of lambda. In order to make the definition clear, let's look again at the example above.

The function

(lambda (a b)
  (/ (+ a b) 2))
has the parameter specification (a b), which is an abbreviation of (a . (b . ())): the function has one obligatory parameter called a, then another obligatory parameter called b, then no more parameters. Easy! Of course we didn't use the second case, because the function has no optional parameters.

As an example of variadic function in Scheme let's examine the predefined function list: list takes any number of parameters, and returns the list of them. For example (list) returns the empty list (), (list 1 2) returns (1 2) and (list 1 (+ 2 3) 10) returns (1 5 10). [Notice that the parameter expression (+ 2 3) is evaluated: the language is still call-by-value, which has nothing to do with variadic functions.]

list is predefined because it's often useful, but it's really easy to re-implement. Its definition is just

(lambda all-parameters  ;; no parentheses around all-parameters
  all-parameters)
. Using the second rule, we see that the parameter specification says that there is any number of parameters; the list of all of them is bound to the variable all-parameters in the body; the body is just the variable all-parameters. This is what we want, because list must return exactly the list of its parameters. That's all.

Looking at the last part written in green, you see that the compact form of a function definition for list is

(define (my-list . all-parameters)  ;; notice the dot
  all-parameters)
, which of course is just an abbreviation of
(define my-list
  (lambda all-parameters  ;; no parentheses around all-parameters
    all-parameters))
. If you don't understand the reason for the dot, read again the part in green. Notice that we have only optional parameters here, and not one obligatory parameter!

To sum up: if a function has some obligatory parameters, say a, b and c, and then optional parameters, the parameter specification will look like (a . (b . (c . rest))), which in compact notation is written as (a b c . rest); so an anonymous function with that parameter specification will look like (lambda (a b c . rest) BODY). In the body rest is bound to the list of all optional parameters.
A definition in compact form will look like (define (function-name a b c . rest) BODY).
Notice that optional parameters can only be at the end.

Exercise: define a variadic function called average for computing the average of one or more arguments (it makes no sense to compute the average of zero numbers). If you want you can call the function average-of-list which you wrote during the first TP from the body of your new function.

Test code:

(display (average 42)) ; it should print 42
(newline)
(display (average 3 5)) ; it should print 4
(newline)
(display (average 1 2 3 4)) ; it should print 5/2
(newline)
(display (average)) ; it should fail

Optional: write a variadic version of the function compose, which I showed on the blackboard during the first lesson. The non-variadic two-parameter version, which I'm now calling binary-compose, was:

(define (binary-compose f g)
  (lambda (x)
    (f (g x))))
Tell me if you do this.


Task 4: more syntactic sugar: let*

When explaining let in class I didn't explicitly specify the visibility rule. Well, it's simple: if you bind several variable in a let, all bindings are visible in the body, but each bound expression does not "see" the variables which have been previously bound in the same let. For example:

(let ((a 1)
      (b 2)
      (c a)) ;; error, unless a is defined out of the let
  42)

;;; Let's define a globally:
(define a 10)

;;; And now let's temporarily bind some variables, including a:
(let ((a 1)  ; this will shadow the global binding in the body...
      (b 2)
      (c a)) ; ...but not here: this a is the global one
  (cons a c)) ;; the whole let returns (1 . 10)
Sometimes this kind of block is called, with a term I personally dislike, "parallel".

The behavior above is often useful, but sometimes you want to use a variable you have just bound in the next binding of the same block. If you want to do that you have to use let* instead of let:

;;; Let's define a globally:
(define a 10)

;;; And now let's temporarily bind some variables, including a:
(let* ((a 1)  ; this will shadow the global binding in the body...
       (b 2)
       (c a)) ; ...and also here
  (cons a c)) ;; the whole let* returns (1 . 1)

The block introduced by let* is called, again with a term I personally dislike, "sequential".

Ask me if you don't understand the difference between let and of let*.

It is quite obvious that let* is in fact syntactic sugar: a let* block is easy to expand into nested let blocks:

(let* ((a 1)
       (b a)
       (c b))
  (+ a b c))
is exactly the same as
(let ((a 1))
  (let ((b a))
    (let ((c b))
      (+ a b c))))
and you already know that let is in its turn syntactic sugar.

Exercise: take the longest function definition you have written until this moment. Can you improve its readability with let*?


Task 5: more syntactic sugar: case

Another sort of conditional expression consists in discriminating on some expression, and returning something different according to its value. This is similar to Pascal's case..of and C's switch (but without the fall-through rule which often forces you to add break statements).

The syntax is very simple. Informally: (case DISCRIMINAND (VALUES BRANCH) .. (VALUES BRANCH)) where DISCRIMINAND is the expression which is evaluated once and whose value is compared with all the values in the lists VALUES (the elements of VALUES are not evaluated); if the value of DISCRIMINAND is equal to one of the values in VALUES, then the whole case expression evaluates to the corresponding BRANCH expression. The last VALUES may be the symbol else instead of a list; in that case the last clause acts as a default.

Example:

(define (number->description n)
  (case n
    ((0)          '(no))
    ((1 2)        '(one or two))
    ((3 4 5)      '(a few))
    ((6 7 8 9 10) '(a bunch of))
    (else         '(many))))

case can be regarded as syntactic sugar, even if there are good reasons for it to be implemented differently from other conditionals, because of performance concerns.

Exercise: write a function days taking the name of a month in English as a symbol, and returning the number of its days. Assume the year is not leap.

Thirty days hath September,
April, June and November,
All the rest have thirty one,
Except February alone
(Which has twenty eight days clear,
and twenty nine in each leap year)

Testing code:

(display (days 'September)) ;; it should print 30
(newline)
(display (days 'January)) ;; it should print 31
(newline)

Optional: also support leap years, adding a second optional boolean parameter. Also check that no more than two parameters are given. Tell me if you do that.


Task 6: quasiquoting

Sometimes you need to return a big complicated data-structure which is nearly all constant, except for some small part. For example let's say you want to represent English sentences as lists of symbols. You would like to build a list such as (hello my friend ! my name is name) where only the last occurrence of name (shown in green for clarity) represents the value of a variable, but all the rest is constant. Quoting by itself will not suffice: the best you can do with what you know up to this point is something like

(append '(hello my friend ! my name is)
        (list name))
which doesn't look very nice. And what if the non-constant part is in the middle?
(append '(your name is)
        (list your-name)
        '(and my name is)
        (list my-name))
This works but is very ugly (and it would be even uglier if we didn't have variadic functions: notice how we call append sometimes with two parameters, sometimes with four). What we would like is a way of saying that an expression is quoted, except for the parts where we explicitly say it's not.

Such a notation exists in Scheme and is called, quite intuitively, quasiquoting (quasi means nearly). The whole expression must be prefixed by a backquote ` and the parts to be unquoted must be prefixed by a comma ,

So our two examples above can be rewritten as

`(hello my friend ! my name is ,name)
and
`(your name is ,your-name and my name is ,my-name)
Much better! Now only the second occurrence of name, your-name and my-name are evaluated, and this is now very easy to see (and change, if needed: just move some commas).

An alternative unquoting prefix which is sometimes useful is the so-called unquote-splicing ,@: the expression which is prefixed by ,@, which must evaluate to a list, is "spliced" within the enclosing quasiquoted list element-by-element:

(define x '(1 2 3))
`(a ,x b)  ;; evaluates to (a (1 2 3) b)
`(a ,@x b) ;; evaluates to (a 1 2 3 b)

Notice that you can unquote even deep within a very big quasiquoted structure:

(define x '(1 2 3))
`(a (((((b c ,x d))))) (,x) b)   ; evaluates to (a (((((b c (1 2 3) d))))) ((1 2 3)) b)
`(a (((((b c ,x d))))) (,@x) b)  ; evaluates to (a (((((b c (1 2 3) d))))) (1 2 3) b)
If you don't use , or ,@ within the quasiquoted structure, then quasiquoting behaves just like quoting:
`foo            ; evaluates to foo
`(a . b)        ; evaluates to (a . b)
`(a #t c)       ; evaluates to (a #t c)
`((a (1)) . c)  ; evaluates to ((a (1)) . c)
Quasiquoting is syntactic sugar, even if, as you may guess, it's quite complicated to systematically rewrite a quasiquoted expression into something which doesn't use quasiquoting. It's complicated, but there are algorithms for doing it.

Another example. Notice how the result of (number->description book-no), which is a list, is spliced into the result:

(define (number->description n)
  (case n
    ((0)          '(no))
    ((1 2)        '(one or two))
    ((3 4 5)      '(a few))
    ((6 7 8 9 10) '(a bunch of))
    (else         '(many))))

(define (number->sentence book-no)
  `(i have ,@(number->description book-no) books))

(number->sentence 7)  ; this returns (i have a bunch of books)

Where in the first TP could you have used quasiquoting? I can think of at least one place where it would have made things easier to understand. But quasiquoting becomes much more useful in complex code. You'll see.


Task 7: symbolic derivative

Write a function derivative of two parameters; the first parameter is an expression [in Scheme notation; for example (+ a (* x (sin x)))], and the second is a variable name [a Scheme symbol]. The function should return an expression, in Scheme notation, which corresponds to the derivative of the first parameter according to the second parameter. The result must be correct but it doesn't need to be minimal, or even "short" in any sense. For example (derivative '(+ a (* x (sin x))) 'x) may return (+ 0 (+ (* 1 (sin x)) (* x (cos x)))).

I just require you to support addition, subtraction, multiplication, division (all of them with only two parameters), sine, cosine and tangent.

Hints: this of course requires recursion; for example, the derivative of a sum is the sum of derivatives... But what is the derivative of a product? You can find a complete table here with much more information than you need. Remember to pay attention to the chain rule. If you want to compare two symbols you can use the eq? function, or case. let* will make your task much easier. Any reasonable solution will also use the function list or, much better, quasiquoting.


Task 8: expression normalizer

Do this only if you finished with the previous task.

Write a "normalizer" function which takes an expression with n-ary addition, subtraction, multiplication, division, and returns an equivalent expression using only binary operations.


Suggestions and Useful resources



Notes for myself, in case of problems with the SERCAL installation or with student accounts:
The emergency machine has IP 194.254.173.145 .
My id is 10706282 .



Back to my home page...


Luca Saiu
Last modified: 2010-09-27
Copyright © 2010 Luca Saiu
Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.