HOP exercises

Exercises on HOP

Exercise 1

Assuming the following excerpt:

(define *names* '("Alice" "Bob" "Charly" "Devil" "Ernest" "..."))
(define-service (ubi-8)
  (let ( (lines (<DIV>)) )
     (<HTML>
      (<BODY>
       ~(define (next)
                <ti be defined> )
       ~(define (show v r)
           (dom-append-child! $lines (<DIV> "result for " v " is " r)) )
       (<BUTTON> "Next" :onclick ~(next))
       lines ))))

Complete the definition of the function next so that it prints successively all the elements of the list names.

Exercise 2

In the previous examples, the list names is shared by all clients. How to change the code so that each client receives its own private copy of that list.

Exercise 3

Instead of traversing a flat list as previously we would like to traverse a tree. For that the server has to store the position of the last leaf sent back to the client. Using call/cc a tree traversal can be implemented as:

(define (walk l)
  (call/cc (lambda (return)
              (define (subw l)
                 (if (not (pair? l))
                     (call/cc (lambda (k)
                                 (return (cons l (service () (k 'continue))))))
                     (begin (subw (car l))
                            (subw (cdr l)) )))
              (subw l) )))

However this function cannot be used as is. Why?

Exercise 4

Re-write the function walk in CPS with an explicit continuation and complete the definition of the service so that it displays successively all the leaves of the tree.

(define *tree* '(("Alice" ("Bob") ("Charly" "Devil") "Ernest") "..."))
(define-service (ubi-11)
  (let ( (lines (<DIV>)) )
     (<HTML>
      (<BODY>
       ~(define *cur* $(service () (cps-walk *tree* (lambda () "..."))))
       ~(define (next)
           <to be defined> )
       ~(define (show v r)
           (dom-append-child! $lines (<DIV> "result for " v " is " r)) )
       (<BUTTON> "Next" :onclick ~(next))
       lines ))))

Exercise 5

Read the documentation of the Hop DOM API (available from http://hop.inria.fr, the client side function). Write a function that inserts a border around all the HTML elements contained in the object it receives as parameter.

Solutions by Cyprien

First of all, Hop is build on top of Bigloo, a R5Rs Scheme compiler and interpreter. There is no need to know this, but you can find examples of Scheme code, and the complete function reference here : http://www-sop.inria.fr/mimosa/fp/Bigloo/doc/bigloo-7.html . Some function are not documented, because they belong to the R5Rs (Revised(5) Report on the Algorithmic Language Scheme), you can find it at the following address : http://www-sop.inria.fr/mimosa/fp/Bigloo/doc/r5rs.html (Chapter 6: Standard Procedures).

You don't have to know all that, but I give you these references if you want to look for some documentation about particular functions.

About exercise 1 :

There are two different things to do here, first one: to go through a list, in a iterative way. The second is to make a service doing the first part.

Let's start by a remainder about Lists. Scheme is a derivative of Lisp. Lisp was designed as a LISt Processor, that's way lists are a first-class object. Moreover, any Lisp (and Scheme) program is a List itself. So you can process any Scheme program as you process a List (or a Tree, which is a List of Lists). So in Scheme, any Scheme-expression (often called sexpr) is a list/tree.
As instance, (+ 1 2) is the tree having + as root, and 1 and 2 as sons, it is also the list, which first element is +, and the rest is (1 2).

A list is compound or pairs, or couples. Each couple is build by the ‘cons; function. (cons 1 2) will produce the pair (1 . 2).
The dot is used as a separator between the car and the cdr.
A pair can be split using the functions `car’ and ‘cdr’.

(car (cons 1 2)) => 1
(cdr (cons 1 2)) => 2

A List, is either the empty list, denoted by '() (the quote is mandatory), or a pair of which the ‘cdr’ is a list.
So if you want to build the list (1 2 3), you may use either:

(cons 1 (cons 2 (cons 3 '())))
(list 1 2 3)

The cdr of that list will be (2 3), while the car will be 1.

You may ask, where is the dot separator ? Well, the list (1 2 3) can be written as (1 . (2 . (3 . ()))). But to easier readbility, there is the dot-paren convention, saying if, in a pair, the dot is followed by an opening parenthesis, we don't display the dot, the opening parenthesis, and the corresponding closing parenthesis.

An improper-list is a list which the last cdr is not the empty list.

I will stop here for this reminder about lists ;)

So, given a list, let us say '(a b c d e), how to iterate through the element of the list ?
I use the quote here, because otherwise, as list ARE sexpressions, the interpreter will look up for a function a, and will try to resolve the variables b c d e to their values, but there are not assigned, and we don't want to "eval" the content of the list)

First, the list as to be assiged to a reference, that is to say, a variable, or a memory cell, choose whatever you want, we use define for that purpose.

(define mylist '(a b c d e)) ; now the symbol mylist will be linked with the list (Note that ‘;’ is used to introduce comments)

(define *names* '("Alice" "Bob" "Charly" "Devil" "Ernest" "..."))
; And now, the iterator, at each call the function `next' will return the next first element of the list
(define (next)
 (if (pair? *names*)
  (let ((first (car *names*)))
    (set! *names* (cdr *names*))
    first)
  "List is empty"))

First, we check is the list is a pair, using the standard library function ‘pair?’ (almost every predicate in scheme, i.e function which always return a boolean value, have there name ending with an exclamation mark).
If the list is a pair, so we can use ‘car’ and ‘cdr’ functions, otherwise we cannot, as this will trigger an error.
The ‘let’ syntax is used to "store" the value of the first element of the list, into a variable named ‘first’. Then we modify the stored list, by replacing it by the cdr, which is the same list, without the first element. The exclamation mark is here to say "Hey! Be careful, this function provides side effects, you should know what you're doing", well this is Scheme philosophy. A purely functional language should not come with assignments :).
Then, after the assignment is done, we return the stored value. Note we had to call ‘car’ before ‘set!’ as the list has changed during the call to ‘set!’, so calling car here would return a different value from the previous one.

At last, if the list is empty (the empty list is not a pair), well, we had to return something. Here I use an explanation string, one could put any scheme value, a number, #f to mean false, either nothing (which is bind to #unspecified, not standard, it is bigloo specific). even the empty list, whatever ;)

Now, we want to put this function in the client side, and keeping the list in the server side. We had to create a service, and invoke it using the ‘with-hop’ syntax.

The changes are small, but we have to handle the return result of the service:

~(define (next)
(with-hop ($(service ()
 (if (pair? *names*)
  (let ((first (car *names*)))
    (set! *names* (cdr *names*))
    first)
  "List is empty")))
(lambda (h) (show "next" h))))

So, the function body is put into a (service () …) block, hence the service is created. We add the $ sign to tell to the compiler the following code has to be compiled on the server side. The first ~ is here to say the definition of the next function will be put in the client side. Last, the code ‘(lambda (h) (show "next" h))’ is just here to handle the return value, h, of the service. The called to ‘show’ will be run on the client, as we are out of the scope of the $ sign.

Note, the ($(service … may look strange. In fact, (service …) create a Service objet, the first opening parenthesis is here to say we "invoke" the service, or we "call" the function produced by the (service ) construction. The $ sign is put between the two parentheses as the (service …) has to be build on server side, and the call on the client side.

As a conclusion, you may know that the (service …) call well be made each time one client request the page, so this will create different anonymous services for each client. But, the *names* symbol is global, and thus shared between the clients. This may not be trivial to understand.

So we are on the way to exercise 2.. As we create an anonymous service for each client, we can make a copy of the list for each of them, using the standard ‘let’ form.

~(define (next)
(with-hop ($(let ((names *names*))
 (service ()
 (if (pair? names)
  (let ((first (car names)))
    (set! names (cdr names))
    first)
  "List is empty"))))
(lambda (h) (show "next" h))))

Here, in the first let, I make a copy of the ‘*names*’ list into a local variable ‘names’. Manuel uses * to name global variables, it is somehow a convention, but not so widely used. So we have to change the references to ‘*names*’ by simply ‘names’ in the body of the service.

Exercise 3

The problem here, is that we don't have any way to know when the walk is finished or not.

There is another reason, which require a deep understanding of continuation, that I didn't have before I asked one of my coworker a few minutes ago… (half of his thesis is about Continuations…).

In this particular case, an error is raised. I don't want to go in explaining the error, as I am not sure of the real reason, and well, the error message is totally weird…

Exercise 4

First, a few words about CPS.

Try to take the CPS-factorial function that Bernard wrote in his slides, then try to compute it by hand, with n = 4 or 5. We can discuss this tomorrow if you don't see well what is happening.

For the conversion from call/cc to CPS, this is a kind of recipe, which don't work in some case, but the main idea is here.

Let's take some habits, add a k argument to each function containing a call/cc in his own body (not for function which define functions using a call/cc, and remove the (call/cc (lambda (…) things, and add the argument where it is needed, here we come:

(define (walk l k1)
 (define (subw e k2)
   (if (not (pair? e))
       (*return* (cons e (service () (*k* 'continue))))
       (begin
          (subw (car e) k2)
          (subw (cdr e) k2))))
 (subw l k1))

Now, we have to get rid of the *return* and *k* functions, which will be replace using k1 and k2, as k2 take the value of k1, we don't really need to return from the function, the new code will be smaller, and I hope simpler:

(define (walk l k1)
 (define (subw e k2)
   (if (not (pair? e))
       (cons e (service () (k2)))
       (begin
          (subw (car e) k2)     ; Let call it E1
          (subw (cdr e) k2))))  ; then E2
 (subw l k1))

Remember that k1 and k2 have to be functions, so we can then define an anonymous service which will invoke the function k2. If you remember the example of the CPS-fac, given by Bernard, the explicit continuation (that the name given to k1 and k2) have generally to be augmented.

For a tree walk, once you have visited the first child of a node (the car), you will have next to visit the other children (cdr) of the list. In other words, when you have finished exploring the first child, you will continue by visiting the others.

So the expression E2 *continues* the tree walk after E1. Hey! We now know what will be the continuation. E2 is the continuation of E1, now we have to put a lambda somewhere, to realise this. As intuition, the only parameter we can play with, and which is a function is k2.

So the block:

(begin ;
  (subw (car e) k2)
  (subw (cdr e) k2))

I remind that the ‘begin’ construct is only used when there is more than one expression in a branch of a if, so we can get rid of it

becomes:

(subw (car e) (lambda () (subw (cdr e) k2)))

When ‘subw’ will finished to walk through (car e), it will walk through (cdr e).

So, the overall code is now:

(define (cps-walk l k1)
  (define (subw e k2)
     (if (not (pair? e))
         (cons e (service () (k2)))
         (subw (car e) (lambda () (subw (cdr e) k2)))))
  (subw l k1))

And the associated (next) function, but in client side:

~(define (next)
   (with-hop (*cur*)
      (lambda (h)
          (when (pair? h)
             (show "next" (car h))
             (set! *cur* (cdr h))))))

And it works.

So, the sub-function ‘subw’ takes now two arguments, e, which is the element currently examined by the algorithm, and ‘rest’, which is a list containing the element that has not been examined at the moment. So, when BOTH ‘e’ and ‘rest’ will be empty, then we would know that the walk is finished.

The main structure of the program is similar to the call/cc version, except I renamed the ‘l’ variable to ‘e’ to distinguish them. There were two ‘l’ variable is the code of Exercise 3, if you don't notice that, well, that does not matter, do not care about that ;).

At initialization, we set ‘e’ to the tree to walk through, and ‘rest’ to the empty list.

Then, same check, is ‘e’ is a pair (or a couple), or not.

Let's start by the recursive call, so if ‘e’ is a pair, then we make a recursive call on the first element of ‘e’, (car e), and we add the rest of the list, (cdr e) the the ‘rest’ variable, using the built-in function ‘append’, which is used to concatenate two lists.

If ‘e’ is not a pair, it may be a leaf, or being null, the empty list.

If it is a leaf, then, like in the call/cc walk, we return a new pair, which first element is the leaf, and the second is a way to continue the walk. We obtain that behavior by calling once again (subw rest '()), like during the initialization.

If ‘e’ is not a leaf, then we look at the ‘rest’ variable, to see if there is another elements to walk through. If Yes, then we make a recursive call, using rest as first argument, and the empty list for the second. If Not, then there is nothing else to walk through, so we return a value, which MUST NOT be a pair, but which can be anything else. I used the special value #unspecified, one can use #f for false, the symbol 'end, a string value "No element left", whatever…

Exercise 5

Given a node, you can use (node-style-set! node prop value) to add a style to the ‘node’ element given as a parameter as instance, (node-style-set! node "border" "1px black solid") will had a solid (continuous) border, with black color, and 1 pixel thickness, the order of the values don't matter if I remember well. But that is CSS, not Hop…

The other interesting function is (dom-child-nodes node), which returns a list of all the child elements of the given ‘node’.

You can take example of the previous exercise to do it (I think this is the idea of this exercise, but now we don't have to create services.

Unclear, need to ask the teachers, since most is obviously derived works.