DLL Project: collaborative development

You have to collaborate with your course colleagues and, together, write a turtle-graphics system entirely in Scheme. The resulting software must be free software and run on Guile on (at least) GNU/Linux systems.
Make sure you correctly deal with legal issues such as copyright and license notices; you can reuse any piece of free software you like, as long as you respect its license. The finished combined software must be a clean source tarball, with clear authorship, copyright and license information.

Collaboration and communication is essential: you must subscribe to the mailing list, and use it for communicating: I will evaluate you according to what you do, and what you do is always shown on the list, as attached files or patches. I have set up a Bugzilla installation for tracking bugs; everybody is expected to use it. If you only have Internet access at the university lab, that will be enough.

Even if that's not realistic for large free software projects, for simplicity I allow you to write mailing list messages in French rather than in English (if you want). Variable names, comments and documentation must be in English; I'm not asking you to write great literature; let's say that your English should be at least as good as my French.

You have to use bzr for getting the latest sources -- I manage the central repository for you, but you can maintain your branches is you want. I try not to participate too much in development; I can help you, but you have to write the code.

The minimum requirements are easy to satisfy: any fourth-year student should be able to write a simple turtle-graphics system satisfying the minimum requirements, even alone. But together you can make something powerful and exciting.

Do a glorious hack. Surprise me.

Rules

• Each "group" must be made of one or two people. If you have particular problems with your group partner please tell me.
  Groups must be formed in advance: I will not accept new people suddenly popping up and joining a person who has already done all of the work. Parasitism will not be tolerated.
• Like Wikipedians say, be bold: if you have a nice idea then bring it forward immediately and discuss it in the mailing list; if others disagree with you but you are strongly convinced that you're right, do what you planned to do anyway, and show it to the list. Maybe you will convince the others; or maybe you want to fork the project, make it different and become a competitor of the others: that's also fine.
  If you think you can implement something beautiful, do it: I will judge you by your contributions.
• Your code does not need to be exactly compatible with the examples I show here; you can invent your own interfaces.

• The project should have enough documentation (in English) for somebody not following DLL to be able to use it; of course the documentation must be written in some reasonable format supported by free software; I strongly recommend Texinfo; in any case, absolutely not OpenOffice, or any other "office" thing: we're writing software documentation, and serious software documentation is written in appropriate systems. Of course LaTeX is also OK, but it's much harder to use than Texinfo.

  Normally every code contribution introducing some feature should also include documentation about it (for example, a section to be added to the Texinfo manual), written by the same author who wrote the code; but it is also acceptable to have a group working on the documentation only. In this case, however, whoever writes the documentation must perfectly understand the code she deals with: the exercise becomes one about code comprehension -- of course you can ask questions to the authors.
  Excuses such as I can't program, so I will write the documentation instead won't work: you're a Master-level student, and this is a course about development. If you can't program, you will fail.

• The sources should look clean and familiar to somebody used to work with source tarballs; we should have README and INSTALL files, a file containing the license, examples, sources with readable comments.
  We're using Guile for the implementation: is there some convention to follow for projects written in Guile? If so, we should follow it.
• Deadline: 2012-02-03 (two weeks before the jury).
  [Extended on 2012-01-27] Deadline: 2012-02-10 (one week before the jury).
• Copying code from the net or submitting anything not written by you is cheating: don't even think of doing that; it makes me very angry.

Basic turtle graphics ideas

Here I've drawn in green the image borders, and I've used a green triangle for representing the turtle, "pointing" in the appropriate direction. The point shown within the triangle is the turtle position; the initial position is identified by a green cross; the initial orientation is "up". Here I use red for showing lines traced by the turtle. Of course, these conventions are just for helping you in understanding the ideas: your software only needs to produce what here is shown in red.

Initial state

So, here is the initial state. At the beginning the turtle is at the center of the image, pointing "up":

Rotate and go forward

By executing the code in the picture below from the initial state, we obtain the shown effect. First the turtle rotates left by 45 degrees, then it advances by 70 pixels in the direction it's facing, tracing a line. Notice that 70 pixels is the length of the line, not the length of the line projections on the x or y axis.

Also notice that rotation does not cause the turtle to draw anything.

The pen state

Again starting from the initial state, here we show the effect of the code below.

You can think of the turtle as holding a pen which is by default "down" (touching the paper the turtle is moving on); with the command (pen-up!) we can lift the pen, so that from that point on the turtle can move without drawing. Calling (pen-down!) will lower the pen back to its "down" position, to let the turtle start drawing again when moving.

In the sample code below, first we lift the pen; then we advance by 70 pixels in the current direction (which is up); and now of course this movement does not trace a line. Then we lower the pen again, we turn left by 90 degrees, and we advance again by 70 pixels; since the pen is now "down", this movement traces a line. Notice that the effect would be the same if we moved the (pen-down!) line after the (left 90) line.

The predicate pen-up?, of zero parameters, returns #t if the pen is currently up and #f if it's currently down; hence at the end of the sample code above

(pen-up?)

would return #f.

(pen-up?) has no side effects and does not draw anything.

---

Minimal requirements

2011-12-01 update: tasks have been in Bugzilla for a while now; you will find many more ideas to develop there, and theirs status will be up-to-date. The list on this page will not be updated.

Implement a Turtle graphics system using Scheme only, running on Guile on (at least) GNU/Linux.

You have to write the code for manipulating data structures representing a picture and a turtle. I'm not asking you to write a Logo interpreter: of course we have Scheme, and we can use it as a language!

For example, a user of your software could write this simple procedure definition for drawing a square using your forward and left procedures.

      (define (square side)
        (forward side)
        (left 90)
        (forward side)
        (left 90)
        (forward side)
        (left 90)
        (forward side)
        (left 90))

      (square 100) ;; draw a square with a 100-pixel side
      (square 30)  ;; draw a smaller square *inside* the bigger one

• The system does not need to draw anything on the screen: you just need to maintain a data structure in memory (a list of points, a matrix, or something like that) and you must provide procedures for loading (from image file to data structure) and saving (from data structure to image file).
  You can use any standard image file format which can be accessed with free software, but I recommend using a textual Netpbm format, because it is particularly easy.
• Use a fixed-size image; support two colors only (for example, black and white): only one pen size, one pixel wide.
• Implement the commands forward, backward, left, right, go-home, clear, pen-up!, pen-down!, pen-up?.

This requires only simple trigonometry and some debugging capacity; it's easy. Any Master-level student must be able to do this, even alone: even if all the other people were pathetic incompetents (and I've already seen they are not) you could do all the work yourself. In practice, you will only have to do part of the work.

Reminder: I'm asking the whole DLL class to only build one turtle graphics system, working in a collaborative way. But if there are strong disagreements, or conflicts, or some ambitious group wants to fork we can also do that, and split the project: but please ask me before. I will participate and I want to be informed of any problem.

Simple example

About the image: made in 2008 by Luca Saiu. I, the author, hereby disclaim any copyright interest and place the image into the public domain.

This is the Scheme code I used to draw the picture on the left in my implementation. Your code does not necessarily need to be compatible with mine, but you should provide all the functionalities reqired for examples such as this one. Notice that n-times and for-step are non-standard macros that I wrote myself for the 2008 project. (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)))

Slightly more advanced tasks

2011-12-01 update: tasks have been in Bugzilla for a while now; you will find many more ideas to develop there, and theirs status will be up-to-date. The list on this page will not be updated.

Make the graphic system more powerful. Here are some ideas:

• Support multiple colors, using RGB in some form. For example (here I have used color coordinates in the range [0,1], but you can do something different):

            (set-color! 1 0 0) ;; set default color to red: 100% Red, 0% Green, 0% Blue
            (forward 100)      ;; draw a 100-pixel red line

  If you prefer you can also add colors as optional parameters for drawing primitives. For example:

            (forward 50)       ;; draw a 50-pixel line using the default color
            (forward 50 0 0 1) ;; draw a 50-pixel blue line, without changing the default color

• Support some form of transparency. If would be nice, for example, to have a "50% transparent" pen, not completely overwriting the pixels it draws upon.

            (set-transparency! 0.5)  ;; set default transparency to 50%
            (forward 50)             ;; draw 50%-transparent line

  Again, you can make transparency an optional parameter of drawing primitives if you want.
• This page contains some beautiful pictures rendered with turtle graphics; generate something similar with our software, to be distributed as examples.
• Support more than one turtle. Again, you should add procedures for creating new turtles, and procedures for "setting the default turtle"; and you can also add a turtle as an optional parameter to other procedures (not only drawing procedures this time: also left, for example, could be applied to any turtle.
• Support more than one image. You can have multiple Scheme data structures representing images, and possibly have procedures to merge them, if you want with transparency support. Turtle-graphics drawing primitives would get the image as an additional parameter (optional, if you want; the "default" window might be the first created window, or the last used one, or whatever you want); for example:

            (define first-window (make-window 800 600))  ;; here make-window takes width and height as parameters
            (define second-window (make-window 800 600))
            (forward 100 first-window) ;; draw a 100-pixel line in the first window
            (left 45 second-window)    ;; turn left the turtle in the second window

• Implement flood fill.

• Text-drawing support. As a minimal solution I'm only asking you to draw text on the image in one single font, one single size; you have to support non-accented Latin letters, numbers, and some punctuation.

  You can write everything yourself in Scheme (but it's not a smart solution: supporting all characters is a lot of work), or write C code for interfacing with some powerful library (it's ok to also write C code for this task); but I think the simplest solution is doing what I did in an old project of which I am co-auhtor: you can figure out how to reuse this data file (pay attention to its license; hint: is it code linked from the program?).

Advanced tasks

2011-12-01 update: tasks have been in Bugzilla for a while now; you will find many more ideas to develop there, and theirs status will be up-to-date. The list on this page will not be updated.

Not everybody needs to do these: we just need one or two strong groups working on the implementation and maintaining (a reasonable degree of) interface compatibility, so that all the others can benefit.

• 3D support. We can keep compatibility with the old turtle graphics procedures, but also adding a new rotation procedure in the three-dimensional space. There are two reasonable ways of drawing 3D objects in a 2D image (you only need to implement one):
  • using axonometry;
  • using perspective: the result is more realistic and possibly of greater artistic value, but the technique involves somewhat more complicated Mathematics.
  This requires some algebra. For the mathematically inclined.

  Here's Cheloniidae, another example of a 3D turtle-graphics system (it's free software, but unfortunately it's written in Java; it will be hard to reuse anything from it). Of course your system doesn't need to be as complex as Cheloniidae, but maybe you can be inspired by some solution it adopts.

• Native graphics support: instead of using image files, you can directly use a graphic window on the screen. Doing graphics this way will be faster and more convenient to use and debug.
  For this you need to call some library, typically written in C, and write some C code (it's ok for this task). You can write your binding from scratch or reuse code written by others, included by me, but of course you have to respect the license.

  All the interfaces you need to use are well-documented, but this task requires some low-level programming.

• The mailing list we use for discussing the project, coordinate, show what we have done and brag. I will use your participation to the mailing list as one measure of what you did in the project: You must subscribe if you want to pass the exam.
• Our Bugzilla installation. You also have to make a bugzilla account before submitting bugs. This is important! We will always refer bugs only by number; all the information is in Bugzilla.

• You have read-only access to our bzr server: I will be the only one with commit permission, and I will accept or refuse your patches. (at least, this is what I have planned: if one expert student wants to be the bzr administrator instead of me, I will be very happy: tell me. But you must be very strong with the command line and have experience with bzr or git for doing this)

  You can access it by HTTP at the address [not available any longer] . (I shouldn't need to say this, but of course you have to use the bzr client and not a web browser)

  New as of 2011-12-23: I have created two new repositories which you can also write:

  • bzr+ssh://dllstudent@ageinghacker.net/home/dllstudent/playground (for learning and playing with)
  • bzr+ssh://dllstudent@ageinghacker.net/home/dllstudent/dll-experimental (your collective experimental branch, not managed by me)
  You have received the password for the new repositories in a mailing list message.

  The "official" repository remains [not available any longer] and is read-only for you.

  If you want to maintain a branch then ask me, I can easily create it and let you be its administrator. That is not a problem, because it does not bother the other groups who work on the trunk or on other branches.

Documentation

Possibly the hardest part in this project is to familiarize yourself with the software we use. You have an opportunity of learning something you will use again in the future; or if not, you will at least learn to learn quickly, and to use the documentation -- this is really important.

• The excellent Guile documentation. This is probably the most important item. Pay attention to the version you are using;
• The Bzr documentation.
• The also excellent Texinfo documentation (just to be clear: it's documentation about the system for writing documentation).
• I have also referred some beginner documentation in the main course page. I sincerely hope you don't need it.

Hints

Here are some suggestions:

• I use the command-line program display (part of ImageMagick) for displaying image files; if you use the predefined Guile procedure system it is easy to call display from Scheme programs.

  From the command line, if you have a file named boo.pnm in the current directory, you can display by typing:

  display boo.pnm

• The 2008 project of our Développement de Logiciels Libres course also involved turtle graphics, but it was very different from the current project. In particular, the turtle graphics engine had been written by me in C, and interfaced with Guile. It will be hard to recycle code from the 2008 project, but you can get inspiration anyway. You can find the specification of the 2008 project, including the source code I distributed, here. Of course you must do the 2011 project, not the old one; but you might be able to reuse something if you respect the license, and the thing might be useful as an inspiration.
• When working at the Institut Galilée labs, you will need to run the usual hack described at the beginning of TP pages: I have installed Guile, bzr and Texinfo in my home directory, and running the line written in red will let you access my directories.
  Of course you don't need that if you work on your computer: if you have root privileges you can install everything system-wise.

Back to my home page...