I can show you my solutions, now that the deadline has expired. They're here.
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:
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 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.
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:
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.