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


I can show you my solutions, now that the deadline has expired. They're here.

DEVL 2009 - Fifth TP (2009-10-19)

Last week a student asked me to give more time to finish the projects at home or in the university labs, and I've talked with a couple of others who would have really liked to work together.
Ok, they're very reasonable suggestions and I'm happy to accept them. As a consequence this week's project is potentially more complex and a good solution can win you a very high bonus. Of course it's still possible to submit simpler solutions for a lower bonus.

In the lab at Institut Galilée you have to use the usual small hack to add my customized paths to $PATH, so that you can use the version of Guile that I have installed in my home directory:

source ~saiu/add-prefix ~saiu/usr

You have to execute the command line above in each terminal you use, before being able to execute guile or guile-network-game.

Notice that this week's task requires guile-network-game: you can't use guile-with-graphics any longer, because you need the new text support. Don't worry if you've already learned the old system: guile-network-game has more features than guile-with-graphics but it should be 100% compatible with it.

I've not written a web page for guile-network-game yet, but you can use it just like guile-with-graphics. If you work at home, notice that guile-network-game requires the SDL_ttf library. I have already installed the library into my home directory at the lab, as usual.

Notice that guile-network-game has a couple of new demo programs showing the new features.

Box-and-pointer diagrams

Box-and-pointer diagrams are a useful graphic representation of the structure of an s-expression, where the cons hierarchy is made explicit.

You shouldn't really have any problem with box-and-pointer diagrams at this moment, as I've always used them at the blackboard. Anyway, here are some other examples from SICP: Figure 2.2, Figure 2.3, Figure 2.4.

Your task

You must write a function of one argument taking an s-expression and drawing a box-and-pointer diagram representing it on the graphic window. You can assume that the window doesn't contain anything else; you can use all the space of the window if you want.

Your solution must support the following s-expression cases:

As you may guess there are some other s-expression cases in Scheme that I have not spoken about, but you are not compelled to support them. In particular I don't require you to support vectors and arrays, unless you want to do something more challenging for a very high bonus, after you've finished the rest.
If all or part of the s-expression received by your function belongs to a case that you don't support, you can simply display the text #<unknown>.

You can also assume that the s-expression you receive is always non-circular.

SICP figures draw arrows with a full circle at tail and an oriented arrow head. Thet looks good, but you're not compelled to do it.

Of course, make your code readable. I don't want you to waste time in commenting trivial stuff, but please use reasonable names for functions and parameters, structure your code well and use comments for explaining the non-obvious points.


The captions of the SICP figures may be slightly misleading as they don't always make an explicit distinction between an s-expression as a data structure and the s-expression as a piece of program which will build the data structure when evaluated: for example Figure 2.2 shows a box-and-pointer diagram for (1 . 2), which is built by evaluating (cons 1 2).
Just to be explicit: your function should draw a figure similar to Figure 2.2 when it receives the cons of the two numbers 1 and 2, and not a list of the symbol cons, the number 1 and the number 2.
The potential ambiguity is due to the fact that SICP introduces the notation for conses in a later chapter, after the compact notation for lists, so it has no way of textually representing (1 . 2) in Chapter 2.

There is an elegant way of obtaining the text representation of any s-expression, using open-output-string, write and get-output-string - however, you are not obliged to use those functions.

Notice that the predicate for checking whether an object is a cons is called pair? rather than cons?.

I've found let* to be very useful for this task. Give a good comprehensible name to your temporary values, it will help you.

You will need the Guile manual.

The new demo scm/demos/text-demo.scm shows how to render text in the graphic window.

There are many possible algorithms for doing this. I have implemented two solutions: the first one, of which a screen capture is shown below in the first figure, is about 100 lines long and took me less than 10 minutes to write. I've spent more than an hour for the second one, shown in the second figure. At 300 lines of code it can't be called big, but its algorithm is a lot more complex; the result is also much better. The main idea of the algorithm used in the first solution should be very evident from the figure -- and no, sorry, it won't yield a very good bonus.

If you want a high bonus for this task you need to find an elaborate strategy for placing the objects on the window, producing a readable result which looks good at least "most of the times". Write a glorious hack. Surprise me.


The next screen capture shows the effect of calling the function on the s-expression (a b c d), which can also be written as (a . (b . (c . (d . ())))):

This shows one of the box-and-pointer diagrams for ((a . #f) b) rendered by my second solution. Of course ((a . #f) b) is exactly the same as ((a . #f) . (b . ())).

There are many possible solutions of varying complexity and power; I will take both point of views in consideration when assigning your bonus. Pay attention to copyright and license headers.

Back to my home page...

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