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

This project is now expired and I won't accept any more submissions for it.
If you want to submit a project for the rattrapage session you will have to work on the new rattrapage project [now also expired, of course].
Please note that I will not accept group projects for the rattrapage session. You will have to work alone.

Luca Saiu - Teaching - DEVL 2008 - Final TP


[turtle graphics screenshot]
(load "useful-macros.scm")

(define circle
  (lambda (size)
    (n-times 360
             (move size)
             (left 1))))

(let ((angle 15)
      (rounds 5))
  (for-step i 0 (* 360 rounds) angle
            (circle (/ i 1000))
            (left angle)))

News


The software you will work on

Turtle is a simple turtle-graphics software for Scheme, implemented in C. You will need to know both C and Scheme to work on the project.

I've implemented turtle in the course of just one night, hence it can't be a mature full-featured implementation; it's relatively usable, but it can be extended in many ways: your project consists in modifying it and making it better.

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

turtle
Copyright © 2008 Luca Saiu
turtle 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 turtle, 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 turtle: you can simply execute it from your working directory as

./turtle

, of course with optional parameters.

There is no documentation for turtle: 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: less than 1000 lines including comments. Don't panic.


Rules

You can choose from a list of tasks of widely varying difficulty to extend some part of turtle. There are tasks suitable for every student, including beginners. Notice that I also evaluate your coding style; make your code understandable, use reasonable identifiers and write comments where needed.

Bonuses and submission

I will give you a very substantial bonus on your final mark (possibly even greater than 15 points out of 20) if you correctly complete one of the hard tasks. Simpler tasks yield smaller bonuses; tasks marked as "trivial" don't buy you a bonus, they are just for helping you to start and understand the software.
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 turtle 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.

Maximum group size: two people. I prefer individual projects, and I give higher bonuses in that case, even if more submissions mean more work for me.

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. We're going to speak about these isssues in the lesson about copyright and licenses.

As a final notice, I hope that not everybody works on the same few tasks. I might "retire" some tasks whose solution becomes too widely known -- after an explicit announcement on the mailing list, allowing some days for people who have already started the soon-to-be-retired task to complete. For each task the first submission may get an higher bonus.

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 each member of your group (or you alone, if you are not part of a group) to participate in a short one-on-one 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.


Tasks

Before choosing a task you should play with the system, run the examples and try to get at least a first understanding of the source. I recommend to start reading sources from the examples (examples/*.scm) and from the headers (src/*.h). You should try to understand the examples, possibly with one exception: the Scheme file with macro definition is for your convenience only; I've not talked about macros and quasiquoting in class, hence you are not required to understand it. 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, and the first student to submit a correct solution for it is still eligible for the higher bonus.

In the following list tasks are ordered by difficulty.

Difficulty
Title
Comments
Trivial Easy Wrap-around coordinates For example, if the window has size 640x480, you can allow the system to draw a pixel at coordinates 1000x2000; replace the x and y coordinates with their modulo by the screen width and height. This task is C only. I recommend this as a first task just to understand the system. Probably it's too easy for a bonus. Ok, I will give a small bonus for it: it's slightly harder than I thought.
Easy Add simple "reflective" primitives There is currently no obvious way, from Scheme, to know the position, orientation, pen-downness, visibility of the turtle. Add functions callable from Scheme which return such information.
Easy Sierpinski carpet, with recursion Write a Scheme program to draw the Sierpinski carpet, stopping at some given depth. This task is Scheme-only, you don't need to touch the C part. Don't use iteration: this must be solved with recursion only, except in the graphic primitives (it's permitted to use iteration to draw squares).
Easy Add simple color support to the Scheme primitives For example you could add a primitive called set-color, taking the three RGB components as parameters. Don't define new types visible from Scheme, you just need numbers. This task is easy because color support is already implemented in C: you just have to make the existing code usable from Scheme. For some weird reason, I have received two three submissions for this task which permit to use only the predefined colors, and only allow 0 or 1 as the values of each component. We support RGB, as three float components between 0.0 and 1.0 included: if the user wants to draw in something like very dark orange, he/she should be able to do it! This is both more general and easier to implement.
Easy/Medium Sierpinski triangle, with recursion Write a Scheme program to draw the Sierpinski triangle, stopping at some given depth. This task is Scheme-only, you don't need to touch the C part. Don't use iteration: this must be solved with recursion only, except in the graphic primitives (it's permitted to use iteration to draw triangles).
Easy/Medium Towers of Hanoi Implement a solver for the Towers of Hanoi in Scheme using only recusion (no iteration), and display the state of the towers with graphics at each step. You will probably need to add at least some minimal color support accessible from Scheme to be able to "delete" what you have already drawn. This is nearly Scheme-only; the C part can be made trivial.
You can use iteration for the graphics part; you will essentially need a Scheme procedure to draw a rectangle, which is allowed to be iterative.
Not hard, but it may be long; this will teach you to write good Scheme code.
Easy/Medium Add clean color support to the Scheme primitives Like in the task above about colors, but a color should now be a new Scheme type, defined by you, and printable; you must use a SMOB (see the Guile manual) for that. You need a primitive to build a color, and three more primitives to extract their RGB components.
Medium Add the read-pixel primitive read-pixel takes two coordinates, and returns the color of the referreed pixel (or fails if the coordinates are out of the string). Implmenting this in a clean way requires a little sophistication (just a little, don't be scared), but less beautiful solutions are easier. This is mostly a C task, the part of interfacing to Scheme is trivial.
Medium Display a picture file on the "Turtle Graphics" window Add a function, usable from Scheme, for displaying a picture stored in a file; you can support any picture file format you like by either implementing the support yourself in Scheme or C (easy for some image formats, hard for others) or by using a library (much easier). If you use a library pay attention to its license, of course. Your new Scheme function should take as parameters a file name string and the coordinates at which to display the picture's top left angle.
Medium Optimize the system Make turtle run at least ten times faster: I'll use circles.scm as a benchmark (excluding the sleep call, of course). The system must remain clean, safe and compatible with existing examples. There are several ways; the hardest part is discovering a problem, not making changes.
Medium Multiple turtles* Add new primitives, or modify the existing ones, so that you can use more than a turtle, and switch between them at runtime. You can invent the interface and break compatibility. The C support is mostly there, the biggest problem here is making a reasonable Scheme interface.
Medium/hard Save a rectangular portion of the "Turtle Graphics" window into a picture file This is related to Display picture files in the "Turtle Graphics" window. Write a function which saves as a picture file the content of the screen in a given rectangle. Your function, which of course should be callable from Scheme, should take five parameters: either a file name string and four coordinates or a file name string, two coordinates, a width and a height. You can choose the file format, implement everything yourself in C or Scheme if you want, or use a library (pay attention to its license). This requires read-pixel.
Medium/Hard Flood-fill Implement a flood-fill operation, optionally with a tolerance. This requires read-pixel. After read-pixel is available, flood-fill can be implemented either in C or in Scheme. You can use any flood-fill algorithm you like.
Medium/Hard Transparency* Add a new attribute to the turtle: its transparency, represented as a float in [0,1], just like a color component. Of course the transparency must be settable by the user with a new primitive. This task essentially requires to implement read-pixel, because you have to update a pixel reading also its current value, not just overwrite it. The hard part is C, Scheme support is trivial.
Medium/Hard (at least) Antialiased lines* Make turtle draw lines with antialiasing. This may require transparency support and read-pixel to be done correctly, but (for a sligtly lower bonus) you can also ignore the problem of re-drawing over non-black pixels.
You can use any anti-aliasing technique you like.
Medium/Hard Load/save Implement support for saving to and reloading from a file the complete status of the turtle and the window contents. You can use whatever file format you want.
There are several solutions, mostly-Scheme and mostly-C.
Medium/Hard (at least) Make turtle easier to interrupt* As of now you cannot kill a turtle process while it's drawing without using a SIGKILL. Modify turtle so that you can kill it as easily as Guile itself, with a simple SIGINT or SIGTERM, or by pushing the close button on the title bar of the "Turtle graphics" window.
Hard Reimplement cursor support* Drawing the turtle cursor is currently inefficient, and implemented in an ugly way. Find and implement a clean solution.
Hard Replace SDL with OpenGL (2D graphics)* Re-implement graphics.c, keeping it as compatible as possible with the SDL implementation, so that it uses OpenGL instead of SDL. Just 2D graphics.
Very hard Fix the refresh problem* As of now, if you hide a part of the turtle window and then you re-expose it, the content will not be redrawn until a graphic primitive is executed. Find a fix for it. The best solution I can think is complex and requires threads. Consider that we must keep the Guile REPL working!
Another solution (still not easy, but deserving a smaller bonus), would be to accept the Scheme input from the SDL window; this in fact would be a re-implementation of the REPL.
Very hard Replace SDL with OpenGL (3D graphics) Re-implement graphics.c to use OpenGL instead of SDL: make the turtle draw in 3D. You can keep the camera static, but graphics must be rendered either in perspective or in axonometry. Add the Scheme primitives you need, or extend the existing ones; for example, you will likely need a way to control spherical angles.
This is the hardest task I've though: the bonus for any reasonably clean solution is 20/20. Only for really strong programmers.
???
Fix a bug If you are the first one to find any bug in turtle (typos or spelling errors don't count) and to send me a correct and clean fix, you very probably deserve a bonus.
???
Other ideas? If you think you have an idea for a good task tell me, we can discuss about it and about the bonus. I'm open to suggestions for new tasks.

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.


This project is now expired and I won't accept any more submissions for it.
If you want to submit a project for the rattrapage session you will have to work on the new rattrapage project [now also expired, of course].
Please note that I will not accept group projects for the rattrapage session. You will have to work alone.

Back to my home page...


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