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

Luca Saiu - Teaching - DEVL 2008 - Rattrapage project

Please note that I will not accept group projects for the rattrapage session. You will have to work alone.

News


The software you will work on

guile-with-graphics is a simple binding of SDL usable from Guile, useful for writing graphic applications or games in Scheme. The software is implemented in C and Scheme, and is based on turtle; however there are some significant differences: graphics is much more efficient in guile-with-graphics (but lower-level: screen refreshing must be performed manually), colors work in a different way, and there is support for SDL events such as key presses and key releases; support for other peripherals such as the mouse is easy to add.

I've implemented this program quite rapidly, hence it can't be a mature full-featured implementation; it's relatively usable, but it's only documented in comments, and some parts of the code may not be clean. I've also used some Scheme features which I have not explained in class: it's up to you to read the Guile documentation and learn them (this is the typical situation when you work with free software: you have to look for information and learn by yourself, it's always unlikely that you have followed some course teaching you everything: free software projects tend to evolve very fast.

Here's guile-with-graphics. I've written it for you students, but I seize this occasion to also release it to the general public. Have fun with it.

guile-with-graphics
Copyright © 2008, 2009 Luca Saiu
guile-with-graphics is free software, released under the GNU General Public License.
It comes with absolutely no warranty.

Please use the latest version if you have not started yet; if you have already started then you can safely continue to use the version you have. All changes are only in the build system; if the version you started with worked, it's ok to go on and simply ignore newer releases.

The software runs on GNU/Linux (with any processor, as far as I know; tested on x86, x86_64 and PowerPC) and requires Guile and SDL, of course including the library headers: your GNU/Linux distribution should typically have separate packages for headers, often with names ending in -dev or -devel.

Everything should be already setup for working in the lab, with my usual hack: execute

source ~saiu/add-prefix ~saiu/usr

, then download the tarball, uncompress it in your home, and compile it. Of course you don't need to execute the line above starting with source if you work on your own computer. Everything should be explained in the INSTALL text file, but you don't need to install the software: you can simply execute it from your working directory as

./guile-with-graphics

, with optional parameters (--debug is particularly useful) and with an optional Scheme file name to execute; for example you can try the demo file scm/interactive-demo.scm with the command line:

./guile-with-graphics --debug scm/interactive-demo.scm

There is no documentation: you have to learn from the provided examples and especially from the sources; this is an important ability that you must develop.
Compared to a real-life situation, this project is very simplified; you have the author available for any question, the code is readable and, most importantly, ridiculously short: about 1000 lines including comments. Don't panic.


How to proceed

I recommend to start running the demos in the scm/ directory (see the README file), trying to understand them, and then to play with them by modifying them. The Scheme part is easier to understand than the C part.

For working with the C part read the code starting from the header files (the .h files). Note that some parts of the code are quite different from turtle.

Some of the tasks are Scheme-only, others are C-only, still others require you to use both languages; anyway if you don't know Scheme you won't get far with this project. If you don't know it yet you really have to learn the language.

Resources

You will need some documentation, in particular:

Of course you can write to the mailing list or to me if you have questions.


Rules

You can choose from a list of tasks of varying difficulty. Notice that I also evaluate your coding style; make your code understandable, use reasonable identifiers and write comments where needed. And of course keep copyright and license headers correct.

Bonuses and submission

You can submit any number of tasks, and of course you can and should also work at home. If you have any setup problem with guile-with-graphics or with GNU/Linux, the mailing list is the right place to ask.

Don't submit your projects to the mailing list. Send them to me personally instead. Please send me the whole modified sources, or a patch file. Don't send sources in strange formats like PDF (some students did it in the past): sources are also meant to be compiled and run, not only to be read.

Another important (and new) rule: no group projects: you have to work alone, even if this means more work for me. I have found that it's practically impossible to allow group projects while avoiding parassitism, and anyway working alone is much more instructive for you.

This is a course on free software: keep copyright headers correct when you modify something, and add a short comment near the top of a file saying who wrote what.

Obvious rules

In any case, but particularly with difficult tasks, you have to show me that you understand what you have written; at my discretion I may ask you to come to my office for a short discussion just to convince myself that you're really the author of your project. Don't worry about that, you don't have to "study": you just have to be able to explain, in detail, what you have done.

Please don't feel offended if I have to say this, but in the past not all students have behaved like the responsible adults they were supposed to be:

I won't tolerate cheating. Don't even try.

Sharing ideas with your friends is ok, submitting the same code (or very similar code) is not.


Tasks

Before choosing a task you should play with the system, run the demos and try to get at least a first understanding of the source. I recommend to start reading sources from the demos (scm/*-demo.scm) and from the headers (src/*.h). You should try to understand the examples, possibly with one exception: the macro definitions in scm/utility.scm are for your convenience only; I've not talked about macros and quasiquoting in class, and you are not required to understand them. Of course you can use the macros I have defined in your tasks.

Descriptions of retired tasks are striken-thru, new task descriptions are written in green, information added after the initial publication of this page is written in red. A red asterisk near a task name (*) means that I have not yet received any correct submission for it (just to satisfy your curiosity: this time I will not give any special bonus to the first submitter of a task solution; a student wrote in the feedback questionnaire that such a policy encouraged a spirit of unhealthy competition among students, which I think may be true).

The bonus points shown below are for a good solution; bugs, bad coding style and wrong copyright or license headers will lower your bonus. On the other hand an exceptionally good solution may deserve an higher bonus.

Note that interactive programs such as games (I'm talking about real games with at least one player here; Life and Wireworld of course are not interactive) must run at the same speed on any computer (with a faster computer the animations may be more fluid, but objects must not move faster): you can see a clean way to do this in the demo scm/interactive-demo.scm. If your computer is slow setting tick-length to an higher value will make the system more usable (at the price of a worse fluidity).

Bonus
Title
Comments
+2+5 Life from random configuration* Implement Conway's Game of Life, starting from a random initial configuration. This is Scheme only.
+4+8 (+2+3 if you also submitted the random initial configuration version) Life from saved configuration Implement Conway's Game of Life, starting from a configuration loaded from a file. You can invent the file format, but it must be human-readable (that's easy in Scheme). This is Scheme only.
Hint: an easy way to do this is by using load...
+4+7 Wireworld (simple) Write a simple Wireworld simulator, starting from a configuration which is read from a file (you can invent the file format, but it must be human-readable). Don't worry about efficiency.
This is Scheme-only.
+5 Mouse support Add mouse support (usable from Scheme) to the system, so that usable mouse events (move with coordinates, button down/button up with button identifier) are generated. This is C-only.
at least +6+9 (or at least +2 if you also submitted the simple version) Wireworld (optimized)* Write a fast Wireworld simulator, starting from a configuration which is read from a file (you can invent the file format, but it must be human-readable). The program must be reasonably efficient, but it must be written in Scheme only (you can't use C for the simulation logic).
This is Scheme-only.
+7 Turtle graphics* Implement a simple turtle graphics system similar to turtle, using only Scheme.
I only require that you implement move, left, right, home, go-to, pen-up, pen-down and reset: all such primitives must be compatible with turtle's version.
There must be an oriented triangular cursor, but you can draw it in a style different from turtle.
This is Scheme only (you're not allowed to modify the C part for this task).
+7 Understand interactive.scm* Read and understand the file scm/interactive.scm. I (intentionally) wrote no comments for the procedures handle-all-enqueued-events and interactive-game; explain those two procedures in every detail, in French (or English if you prefer; the bonus is the same); in particular, I want you to say how interactive-game allows a game to run at the same speed on every computer.
This requires no programming, but you need to understand some relatively difficult (even if clean) code not written by you.
I have just noticed (on 2009-03-25) that there are a couple of style problems in interactive-game. Instead of fixing them in the code, I will give a higher bonus to the students who correctly identify them.
+8 Two-player Pong Write a simple two-player Pong game, where the two players use the same keyboard. This is Scheme-only.
+10 (or +2 if you also submitted the two-player version) One-player Pong Write a simple Pong game where one player plays against the computer. This is Scheme-only.
at least +10 Box-and-pointer diagrams* Write a program which reads an s-expression from the terminal (you can use read) and then draws it on the graphic window as a box-and-pointer diagram, in a format similar to these figures from SICP: Figure 2.2, Figure 2.3, Figure 2.4.
You can do this even if you didn't implement the text support, for a lower bonus; just don't show the text.
This is Scheme-only.
at least +10 Text support Add support (usable from Scheme) for writing text in the graphics window. There are many possible solutions, of widely different complexity and power. Some solutions are Scheme-only, some are C only, some involve using external libraries (you can use external libraries if you want, but pay attention to licenses!).
Another solution: you can also write a tool (in any language with a free software implementation, but different from C and Scheme if you want; I also want to see your tool's source) to translate an existing font into a new simple format invented by you, and then use the simple format from Scheme.
A possible reasonable interface is a procedure write-text which takes three parameters: x and y coordinates, and a string. Of cours much more powerful interfaces are possible: for example the font name could be a parameter. But write-text as outlined above is enough if the code is clean.
+12 Tetris Write a simple Tetris clone. This is Scheme-only.
+15 Sprite support* Add efficient support (of course usable from Scheme) for sprites, and write a short demo program in Scheme using them. The hard part is in C, and requires you to learn some more advanced features of SDL (and possibly of Guile, depending on your solution).
+15~20 Arkanoid* Write an Arkanoid/Breakout clone, with levels represented in a reasonable format which is easy to edit (I'm not asking for an editor program, but for an intuitive data format; that's easy in Scheme). Of course I will give a higher bonus if you submit a more advanced and complex solution.
Pay attention to efficiency: the software must be usable on my machine (which however is very fast, don't worry), and this task may not be completely trivial to implement in an efficient way.
This is Scheme-only.
+3+5 Function plotter* Write a simple function plotter which displays the graph of a given one-argument function on the carthesian plane. The funciton must be entered by the user (you can use read) in Lisp notation: for example the user will write (lambda (x) (sin x)), or also simply sin, to indicate the sine function.
You should use primitive-eval to evaluate the s-expression which was given by the user and obtain a function which you can call.
Don't worry about making the graphic window refresh itself when the program is waiting for user input from the terminal; it's very hard (but you get a +20 bonus if you do it (you can use C for that)).
This is Scheme-only, except for the optional part worth a +20 bonus.
+1.5+3.5 Numeric derivative* You must have finished function plotter before starting this.
Modify your function plotter solution so that your program also plots an approximation of the derivative of the function, in a different color.
Hint: the definition of derivative involves a limit of a quantity tending to 0: what if instead of really computing the limit you just take a very small number for the quantity?
This is Scheme-only.
+8 Symbolic derivative* You must have finished function plotter before starting this.
The problem is similar to numeric derivative, but you must not use an approximation here: you have to compute the analythic expression of the derivative, display it on the terminal (you can use display), and then plot it.
I just require you to support addition, subtraction, multiplication, division (all of them with only two parameters), sine, cosine and tangent.
If lambda notation in the input bothers you, you can assume that the parameter is always called x so that, for example, that (+ x 1) means (lambda (x) (+ x 1)).
Hint: this 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.
This is Scheme-only.
+9 (alone, without considering symbolic derivative) Expression simplifier* You should (but it's just a suggestion) have done at least the non-graphic part of symbolic derivative before starting this.
The derivative expressions you obtain from symbolic derivative are correct, but not minimal or "beautiful": for example, the expression (+ (* 0 (sin x)) (cos x)) could be written more simply as (cos x).
Write an expression simplifier, taking as input an expression and returning an equivalent but simplified expression.
You only have to support the expressions supported by symbolic derivative.
This is Scheme-only. You can also ignore graphics here.
+4 complementary-color Write a function (in Scheme) called complementary-color and taking one color object as parameter, which returns the complementary color of the given color. Your function must work for any valid color, not only for primary or secondary colors.
Your function must take a color and return another color: it must not modify its parameter.
This is Scheme only.
+7 complement-color!* Add a new primitive, usable from Scheme, called complement-color! and taking one color object as parameter. Your primitive must modify its parameter and turn it into its complementary color. Your primitive must work for any valid color, not only for primary or secondary colors. It must return SCM_UNSPECIFIED.
Make sure that you correctly modify the color: you have to understand how color SMOBs work from the C source code.
This is C only.
+4 Speculate about the efficiency of complementary-color and complement-color!* Answer the following two questions, in French or in English (the bonus is the same):
  • Which of complementary-color and complement-color! is faster, and why?
    Hint: there are two important reasons I can think of.
  • Let's say that you also have another primitive complementary-color-c, which is exactly like complementary-color but implemented in C. Which of the three is the fastest, and why?
It is highly recommended, even if not compulsory, that you have solved the other two mentioned tasks before doing this.
This task does not require any coding.
from +2 to +10 for correct solutions Benchmark two primitives * You have to compare the efficiency of draw-line and draw-rectangle, when called with the same paramters 0 0 100 100 yellow:
  • (draw-line 0 0 100 100 yellow)
  • (draw-rectangle 0 0 100 100 yellow)
How many times per second can you execute each of the calls above on your machine? Show me the code you have used for computing this result (it must work, I'm not asking for just a sketch), and write a short text in French or English (the bonus is the same) justifying your solution.
Don't refresh: we don't want to measure how fast refreshing is.
You can do research on the Internet for a good way to do a benchmark, and maybe you should read some benchmarking code written by others.
There are many solutions, of widely varying effectiveness.
+5 read-pixel * Add a new primitive function, usable from Scheme, called read-pixel, with two parameters, x and y, which returns the color of the graphic window at the given coordinates. Note that you must return a color object, not just three numbers, so you have to understand how color SMOBs work from the C source code.
This is C only.
+8 Scaling support * Add a new primitive function, usable from Scheme, called draw-stretched-rectangle, with eight parameters:
  • source x0, y0, width, and height
  • target x0, y0, width, and height
The primitive should draw a "stretched" copy of the given rectangle into another rectangle (on the same graphic window: it is very hard in SDL to work with more than one graphic window). You should report an error (look at the Guile manual for the way of doing this) if the two given rectangles overlap.
This is C only.
+8 if you also solved Scaling support; +16 otherwise Scaling support with overlapping rectangles * Exactly like Scaling support, but the primitive must not fail when rectangles overlap: the target rectangle should just (sometimes partially) overwrite the source rectangle so that the new rectangle contains a scaled version of the whole, original, source rectangle. You will find this markedly more difficult than Scaling support.
This is C only.

For more information

Of course you can write to
the mailing list or contact me personally for any question.

Again, I strongly suggest all students to subscribe to the mailing list. The linked page contains all the information.


Back to my home page...


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