Before teaching OCaml

Before teaching OCaml

[David Teller]

  Dear list,

 I'm going to start teaching OCaml soon and I'm fishing for ideas and
suggestions. I hope this list is the right place to ask.

 Within a few weeks, I'll be teaching OCaml to a class of second-year
students in _mathematics & informatics_. The bad part is that their
knowledge of computer science is limited to 3 term-long lectures of
"algorithmics" (read "Java under Windows"), and that they have nil
knowledge of Unix/Cygwin or Makefiles, or even Emacs or command-lines.
The good part is that a number of them consider Java "not mathematical
enough", so they may be good candidates for functional programming.

 I'm planning to base my lecture roughly on part 1 of _Developing
applications with Objective Caml_, perhaps replacing the chapter devoted
to Graphics with the use of LablGTK. Then again, perhaps not. Some
low-level graphics might be interesting for them. I also intend to give
them a term-long project to work on and develop.

Right now, I see the following difficulties:

* the environment -- under Windows, is there any viable alternative to
Emacs + the MinGW-based port ? 

* the Makefile -- I've found OCamlMakefile [1] but I haven't tried it
yet, hopefully it's simple enough for my students to use without too
many arcane manipulations

* the task -- for the moment, I have no interesting idea of OCaml-based
projects. Perhaps something like finding the shortest path along
subway/train lines ?


Thanks for any idea/suggestion/comment,
 David,
  And a Happy New Year


[1] http://www.ocaml.info/home/ocaml_sources.html

Re: [Caml-list] Before teaching OCaml

[Dan Hipschman]

On Sun, Jan 07, 2007 at 07:15:22PM +0100, David Teller wrote:
> * the environment -- under Windows, is there any viable alternative to
> Emacs + the MinGW-based port ? 

OK, I'm pretty much totally new to OCaml, but maybe that's good
considering you're going to be teaching to people that are new to it,
too.

I've never used any of them, but Googling "OCaml IDE" without the quotes
brings up something called Camelia, Eclipse (they might be used to that
if they used if for Java), and Camelion.  Personally, I use Emacs, but
if you do that make sure they have Tuareg-mode installed.  I've noticed
that a lot of people who haven't used Emacs before find using the
toplevel from Emacs confusing, and usually just run ocaml as a separate
process and copy / paste code into it.  If this is the case, ledit is a
must.

> * the Makefile -- I've found OCamlMakefile [1] but I haven't tried it
> yet, hopefully it's simple enough for my students to use without too
> many arcane manipulations

Using OCamlMakefile is a no-brainer, at least for the smaller projects
I've done.

> * the task -- for the moment, I have no interesting idea of OCaml-based
> projects. Perhaps something like finding the shortest path along
> subway/train lines ?

I've only done a few projects in OCaml so far.  It's very good for
writing compilers / interpreters.  I find ocamllex and ocamlyacc much
friendlier than lex and yacc, and the type system makes building
abstract syntax trees a breeze.  I've been working on a mini-Prolog
interpreter for the past few weeks, and something like that might make a
good project (although, my code is on my website, so I wouldn't do that
exactly as they could easily copy it).  Before that, I implemented a
type inference system as a class project.  The professor gave us a
mini OCaml interpreter that he wrote, but removed the type inference
part of it.  It took a few weeks to do.  Since you mentioned graphics,
and OCaml is so good at writing interpreters, a thought that occurred to
me was that you could have them develop a small GUI description language
and write an interpreter for it that creates the user interface from it.
For example, something like the .rc resource files on Windows, or .glade
files (but XML is kind of boring, IMO).  The next project I am planning
to do is to write a chess playing engine, although I haven't even
decided if I'm going to use OCaml for that.  Still, alpha-beta pruning
and stuff like that should be fun to do in OCaml, although chess is a
bit complicated.  If you came up with something simpler (like checkers),
they could have their programs compete with each other (extra credit for
the winner?).

Anyway, these are just some ideas (which you asked for), that I know can
be done since I'm rather new to OCaml myself and have done or thought
about them already.  If you decide to go with one of them, you can, of
course, simplify or complicate to suit what your students can handle.

HTH :-)

Re: Before teaching OCaml

[Sylvain Le Gall]

Hello,

On 07-01-2007, David Teller <David.Teller@univ-orleans.fr> wrote:
>   Dear list,
>
>  I'm going to start teaching OCaml soon and I'm fishing for ideas and
> suggestions. I hope this list is the right place to ask.
>
>  Within a few weeks, I'll be teaching OCaml to a class of second-year
> students in _mathematics & informatics_. The bad part is that their
> knowledge of computer science is limited to 3 term-long lectures of
> "algorithmics" (read "Java under Windows"), and that they have nil
> knowledge of Unix/Cygwin or Makefiles, or even Emacs or command-lines.
> The good part is that a number of them consider Java "not mathematical
> enough", so they may be good candidates for functional programming.
>
>  I'm planning to base my lecture roughly on part 1 of _Developing
> applications with Objective Caml_, perhaps replacing the chapter devoted
> to Graphics with the use of LablGTK. Then again, perhaps not. Some
> low-level graphics might be interesting for them. I also intend to give
> them a term-long project to work on and develop.
>
> Right now, I see the following difficulties:
>
> * the environment -- under Windows, is there any viable alternative to
> Emacs + the MinGW-based port ? 
>
> * the Makefile -- I've found OCamlMakefile [1] but I haven't tried it
> yet, hopefully it's simple enough for my students to use without too
> many arcane manipulations
>
> * the task -- for the moment, I have no interesting idea of OCaml-based
> projects. Perhaps something like finding the shortest path along
> subway/train lines ?
>
>
> Thanks for any idea/suggestion/comment,
>  David,
>   And a Happy New Year
>

Well, you can try :
http://www.librecours.org/

There is some lecture about OCaml. Maybe you'll find your answer in this
(already done) lecture ?

Regards,
Sylvain Le Gall

Re: [Caml-list] Before teaching OCaml

[Aleksey Nogin]

On 07.01.2007 10:15, David Teller wrote:

> * the Makefile -- I've found OCamlMakefile [1] but I haven't tried it
> yet, hopefully it's simple enough for my students to use without too
> many arcane manipulations

Have you looked at OMake - http://omake.metaprl.org/ ?

For simple OCaml projects, the OMakefile would be 1 line:

.DEFAULT: $(OCamlProgram prog_name, module1 module2 module3)

It's easy to install on Windows and it is self-contained (you do not
need GNU Make).

Aleksey

Re: [Caml-list] Before teaching OCaml

[Richard Jones]

On Sun, Jan 07, 2007 at 07:15:22PM +0100, David Teller wrote:
> and that they have nil
> knowledge of Unix/Cygwin or Makefiles, or even Emacs or command-lines.

You might want to avoid the whole build issue by providing them with
all the makefiles, etc. and just telling them to drop their ML file in
there and (at most) type 'make'.

Rich.

-- 
Richard Jones
Red Hat UK Limited

Re: [Caml-list] Before teaching OCaml

[skaller]

On Sun, 2007-01-07 at 19:15 +0100, David Teller wrote:
>   Dear list,
> 
>  I'm going to start teaching OCaml soon and I'm fishing for ideas and
> suggestions. I hope this list is the right place to ask.

> Right now, I see the following difficulties:
> 
> * the environment -- under Windows, is there any viable alternative to
> Emacs + the MinGW-based port ? 

Emacs? Gak! You want them to waste the whole semester
learning an editor? Notepad is perfectly acceptable.
There's probably a version of gedit that runs on Windows.

The Windows native port is fine, but you do need the 
MS assembler and compiler executables (and ml.err, the
assembler error file). 

> * the Makefile

Why not just show them how to write out a script by giving them 
a simple example to edit, something like:

ocamlc -c file1.mli
ocamlc -c file2.mli
ocamlopt -c file1.ml
ocamlopt -c file2.ml
ocamlopt file1.cmx file2.cmx -o program

and explain the ordering requirements. 

There are several auto-makers for Ocaml (as mentioned in other
emails) .. but using these hides understanding of how the
ocaml tools work.

> * the task -- for the moment, I have no interesting idea of OCaml-based
> projects. Perhaps something like finding the shortest path along
> subway/train lines ?

I would tend to provide a simple but not trivial problem,
and get them to write it in a familiar procedural style .. then
show how to convert it to a functional style, and what the
advantages are. So you'd want to pick a problem which is 
amenable to both kinds of solution.

EG .. convert loops to tail recursions, convert inner 
recursions to tail recursions, replace variables
with arguments, continuation passing, HOFs, etc.

One possible project is a small interpreter .. it has 
plenty of scope for variations, and has the advantage
of being interactive without requiring graphics.


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Before teaching OCaml

[robert]

> I would tend to provide a simple but not trivial problem,
> and get them to write it in a familiar procedural style .. then
> show how to convert it to a functional style, and what the
> advantages are. So you'd want to pick a problem which is
> amenable to both kinds of solution.
>
> [...]
>
> One possible project is a small interpreter .. it has
> plenty of scope for variations, and has the advantage
> of being interactive without requiring graphics.
>
This was actually going to be my suggestion.  I'd suggest a very
toned-down version of a mathematics interpreter (think of a baby
Mathematica).  That's the kind of problem that will play well to Ocaml's
strengths, and since you're looking at math-oriented problems, it'd be
reasonably forward.

It'd be really fun to do this post-abstract algebra.  Define Rings and
that kind of stuff as functors, and then go to town.  :-D

~~ Robert Fischer.
Fischer Venture Management Corp

Re: [Caml-list] Before teaching OCaml

[Jacques Carette]

robert@fischerventure.com wrote:
> This was actually going to be my suggestion.  I'd suggest a very
> toned-down version of a mathematics interpreter (think of a baby
> Mathematica).  That's the kind of problem that will play well to Ocaml's
> strengths, and since you're looking at math-oriented problems, it'd be
> reasonably forward.
>
> It'd be really fun to do this post-abstract algebra.  Define Rings and
> that kind of stuff as functors, and then go to town.  :-D
>   
You would think so - and then when actually doing it, realize that it 
doesn't *quite* work.  See for example
http://focal.inria.fr/site/images/stories/articles/boulme_rr00b.ps.gz
i.e.

@TECHREPORT{BoulmeRR00b,
  AUTHOR = {Sylvain Boulm\'e and Th\'er\`ese Hardin and Renaud Rioboo},
  TITLE = {Polymorphic Data Types, Objects, Modules and Functors: is it too much?},
  INSTITUTION = {LIP6},
  TYPE = {Research report},
  YEAR = 2000,
  NOTE = {Available on \url{http://www.lip6.fr/reports/lip6.2000.014.html}{http://www.lip6.fr/reports/lip6.2000.014.html}},
  KEYWORDS = {classes, modules, functors, objects, types, polymorphism, functionnal programming, Computer Algebra, specification, library},
  ABSTRACT = {Abstraction is a powerful tool for developers and it is offered by numerous features such as polymorphism, classes, modules and functors, ... 
                      A working programmer may be confused with this abundance. We develop a computer algebra library which is being certified. Reporting this experience made with a
                      language (Ocaml) offering all these features, we argue that they are all needed together. We compare several ways of using classes to represent algebraic concept, 
                      trying to follow as close as possible mathematical specification. Then we show how to combine classes and modules to produce code having very strong properties. 
                      Currently, this library is made of one hundred units of functional codes and behaves faster than analogous ones such as Axiom}
}

To really make it 'work', you need quite a bit of technology.  You can do a toy version without getting too fancy, but you have to be careful because so many different extensions you might want to implement do not *quite* work.

I have also seen a "baby Maple" written in Haskell -- the level of necessary technology is also quite high.

Jacques

Re: [Caml-list] Before teaching OCaml

[robert]

Alright, then I recommend staying to the simple stuff (and away from
Abstract Algebra) for the sake of the class.  I stand by the simple
mathematical interpreter as a good example, though.

The nice thing about mathematics is that one can assume a rather universal
"intuitive" understanding with this class, so the instructor wouldn't need
to get into syntax definitions or the like.  And the project doesn't
require any mucking about with GUIs, which is a lot of time dedicated to
little learning return.

Thanks for the paper reference, BTW.

~~ Robert.
Fischer Venture Management Corp

>> This was actually going to be my suggestion.  I'd suggest a very
>> toned-down version of a mathematics interpreter (think of a baby
>> Mathematica).  That's the kind of problem that will play well to Ocaml's
>> strengths, and since you're looking at math-oriented problems, it'd be
>> reasonably forward.
>>
>> It'd be really fun to do this post-abstract algebra.  Define Rings and
>> that kind of stuff as functors, and then go to town.  :-D
>>
> You would think so - and then when actually doing it, realize that it
> doesn't *quite* work.  See for example
> http://focal.inria.fr/site/images/stories/articles/boulme_rr00b.ps.gz
> i.e.
>
> @TECHREPORT{BoulmeRR00b,
>   AUTHOR = {Sylvain Boulm\'e and Th\'er\`ese Hardin and Renaud Rioboo},
>   TITLE = {Polymorphic Data Types, Objects, Modules and Functors: is it
> too much?},
>   INSTITUTION = {LIP6},
>   TYPE = {Research report},
>   YEAR = 2000,
>   NOTE = {Available on
> \url{http://www.lip6.fr/reports/lip6.2000.014.html}{http://www.lip6.fr/reports/lip6.2000.014.html}},
>   KEYWORDS = {classes, modules, functors, objects, types, polymorphism,
> functionnal programming, Computer Algebra, specification, library},
>   ABSTRACT = {Abstraction is a powerful tool for developers and it is
> offered by numerous features such as polymorphism, classes, modules and
> functors, ...
>                       A working programmer may be confused with this
> abundance. We develop a computer algebra library
> which is being certified. Reporting this experience
> made with a
>                       language (Ocaml) offering all these features, we
> argue that they are all needed together. We compare
> several ways of using classes to represent algebraic
> concept,
>                       trying to follow as close as possible mathematical
> specification. Then we show how to combine classes
> and modules to produce code having very strong
> properties.
>                       Currently, this library is made of one hundred units
> of functional codes and behaves faster than
> analogous ones such as Axiom}
> }
>
> To really make it 'work', you need quite a bit of technology.  You can do
> a toy version without getting too fancy, but you have to be careful
> because so many different extensions you might want to implement do not
> *quite* work.
>
> I have also seen a "baby Maple" written in Haskell -- the level of
> necessary technology is also quite high.
>
> Jacques
>

Re: [Caml-list] Before teaching OCaml

[Jacques GARRIGUE]

From: David Teller <David.Teller@univ-orleans.fr>
>  I'm going to start teaching OCaml soon and I'm fishing for ideas and
> suggestions. I hope this list is the right place to ask.
[..]
>  I'm planning to base my lecture roughly on part 1 of _Developing
> applications with Objective Caml_, perhaps replacing the chapter devoted
> to Graphics with the use of LablGTK. Then again, perhaps not. Some
> low-level graphics might be interesting for them. I also intend to give
> them a term-long project to work on and develop.
For the graphics, I would rather suggest lablTk. It is much easier to
use for beginners. And you can even work interactively using the
Tk.update command.

> * the environment -- under Windows, is there any viable alternative to
> Emacs + the MinGW-based port ? 

For writing programs, emacs helps a lot. In particular, the possibility
to execute phrases in the toplevel while editing a file makes things
much easier. Emacs looks scary, but for this specific case you only
need a limited number of key combinations :-)
Once you've installed Tcl/Tk (required for LablTk), then you can use
ocamlbrowser. It can be helpful too, particularly for browsing the
library.

(These are very personal suggestions...)

Jacques Garrigue

Re: [Caml-list] Before teaching OCaml

[Oliver Bandel]

On Mon, Jan 08, 2007 at 08:17:44AM +0900, Jacques GARRIGUE wrote:
> From: David Teller <David.Teller@univ-orleans.fr>
> >  I'm going to start teaching OCaml soon and I'm fishing for ideas and
> > suggestions. I hope this list is the right place to ask.
> [..]
> >  I'm planning to base my lecture roughly on part 1 of _Developing
> > applications with Objective Caml_, perhaps replacing the chapter devoted
> > to Graphics with the use of LablGTK. Then again, perhaps not. Some
> > low-level graphics might be interesting for them. I also intend to give
> > them a term-long project to work on and develop.
> For the graphics, I would rather suggest lablTk. It is much easier to
> use for beginners. And you can even work interactively using the
> Tk.update command.
[...]


Or writing converter code, that produces postscript-output.
Somethinglike a graphics language as project.
Similarmaybe to graphviz or troff's graph-preprocessor or
maybe a thing like gnuplot.
Providing different output formats are IMHO nice field for
learning. And you have the interpreter-task and also
something that can be viewed.

Ciao,
  Oliver

Re: [Caml-list] Before teaching OCaml

[Jon Harrop]

On Sunday 07 January 2007 18:15, David Teller wrote:
>   Dear list,
>
>  I'm going to start teaching OCaml soon and I'm fishing for ideas and
> suggestions. I hope this list is the right place to ask.
>
>  Within a few weeks, I'll be teaching OCaml to a class of second-year
> students in _mathematics & informatics_.

We have created quite a bit of free educational material about OCaml/F# and 
aimed broadly at scientists. I'm sure you'll get some inspiration from our 
work.

> The bad part is that their 
> knowledge of computer science is limited to 3 term-long lectures of
> "algorithmics" (read "Java under Windows"),

That isn't good but mathematicians should be able to learn the basics of 
asymptotic algorithmic complexity in an hour. My book "OCaml for Scientists" 
contains an ideal mathematical explanation of this topic, using ipow and a 
case study and plotting the real and asymptotic complexities as well as the 
measured time taken.

> and that they have nil 
> knowledge of Unix/Cygwin or Makefiles, or even Emacs or command-lines.

I use Emacs under Debian linux. The syntax highlighting (of mli, ml but also 
mll and mly files) is great and autoindentation is indispensable for me. 
However, there is a bit of a learning curve here, especially if they have to 
install the software themselves. Also, I'm not sure how well it works under 
Windows.

If you're using Windows then I highly recommend the related language F# and 
Visual Studio 2005. The IDE does color syntax highlighting for .fs and .fsi 
(equivalent to .ml and .mli) files. As a .NET language, you get instant 
access to all of the functionality provided by .NET, such as database and web 
connectivity.

> The good part is that a number of them consider Java "not mathematical
> enough", so they may be good candidates for functional programming.

Excellent. There are many programs that they will probably jump at. You might 
like to start with a logic problem, like solving Sudoku puzzles:

  http://www.ffconsultancy.com/free/sudoku/

The core of the program is simply this:

let rec search ?(x=0) ?(y=0) f accu = match x, y with
    9, y -> search ~x:0 ~y:(y+1) f accu (* Next row *)
  | 0, 9 -> f accu
  | x, y ->
      if m.(y).[x] <> '0' then search ~x:(x+1) ~y f accu else
        fold (fun accu n ->
                let n = Char.chr (n + 48) in
                if invalid x y n then accu else
                  (m.(y).[x] <- n;
                   let accu = search ~x:(x+1) ~y f accu in
                   m.(y).[x] <- '0';
                   accu)) accu 1 10

We've also written a GUI version in F# using Windows Forms, threads and other 
features:

  http://www.ffconsultancy.com/dotnet/fsharp/sudoku/

>  I'm planning to base my lecture roughly on part 1 of _Developing
> applications with Objective Caml_,

If you're interested in teaching functional programming more than other 
aspects (e.g. interoperability) then you might also consider the freely 
available first chapter of my book:

  http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html

> perhaps replacing the chapter devoted 
> to Graphics with the use of LablGTK.

I recommend using OpenGL with OCaml/Linux or DirectX with Windows.

The OpenGL examples from my book are freely available here:

  http://www.ffconsultancy.com/products/ocaml_for_scientists/visualisation/

The minimal demo is just this:

let () =
  let argv' = Glut.init Sys.argv in
  ignore (Glut.createWindow ~title:"OpenGL Demo");
  GlClear.color (0.1, 0.3, 0.1);
  Glut.displayFunc ~cb:(fun () -> GlClear.clear [ `color ]; Gl.flush ());
  Glut.mainLoop ()

Here is a DirectX demo for F#:

  http://www.ffconsultancy.com/dotnet/fsharp/teapot/

I have just finished writing a minimal scene graph library for F# for my 
forthcoming book "F# for Scientists". This defines a variant type 
representing nested transforms, groups and primitives. When the top-level 
(called the F# interactive mode) sees one of these it automatically spawns a 
visualisation window. This is ideal for educational purposes as the students 
are freed from the burden of rendering contexts, device losses, double 
buffering and so on.

> Then again, perhaps not. Some 
> low-level graphics might be interesting for them.

Creating graphics with OpenGL and DirectX is easy enough that the immense 
gratification given by the result make it worthwhile. I strongly recommend 
using graphics on a teaching course.

> I also intend to give 
> them a term-long project to work on and develop.

As other people have suggested, some form of interpreter or compiler is ideal 
here. I think such a project would be greatly improved with the addition of 
graphics commands into the language. So a Logo, BASIC or Mathematica 
implementation would be ideal.

Given that they are mathematicians, perhaps a mini Mathematica implementation 
is an ideal project? This has the interesting property of being a rewrite 
system (expr -> expr) rather than a conventional interpreter (expr -> value). 
A Mathematica implementation simply replaces input expressions according to a 
built-in set of rewrite rules (pattern matches). A simple Mathematica 
implementation can be written in well under 1,000LOC, including lexer and 
parser.

> Right now, I see the following difficulties:
>
> * the environment -- under Windows, is there any viable alternative to
> Emacs + the MinGW-based port ?

The commercial version of Visual Studio is the only other IDE that I know of 
under Windows.

> * the Makefile -- I've found OCamlMakefile [1] but I haven't tried it
> yet, hopefully it's simple enough for my students to use without too
> many arcane manipulations

Make is really only useful for final, production builds in the context of 
OCaml. OCaml is very brittle with respect to changes but it is very fast to 
compile, so it is an ideal candidate for simple compilation from a bash 
script.

> * the task -- for the moment, I have no interesting idea of OCaml-based
> projects. Perhaps something like finding the shortest path along
> subway/train lines ?

The travelling salesman problem is one of the examples from the final chapter 
of my book:

  http://www.ffconsultancy.com/products/ocaml_for_scientists/complete/

It would be much more compelling with real-time graphics. I'll address that in 
my next book...

We also have many other OCaml examples, including a minimal Mandelbrot 
renderer:

  http://www.ffconsultancy.com/free/fractal/

A simple ray tracer:

  http://www.ffconsultancy.com/free/ray_tracer/languages.html

A maze generator:

  http://www.ffconsultancy.com/free/maze/

and so on.

HTH!

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Before teaching OCaml

[Oliver Bandel]

On Sun, Jan 07, 2007 at 07:15:22PM +0100, David Teller wrote:
>   Dear list,
[...]
> * the task -- for the moment, I have no interesting idea of OCaml-based
> projects. Perhaps something like finding the shortest path along
> subway/train lines ?
[...]


"realworld task": spamfilter.

Then, if thisfits the needs of the mathematical
teaching during the time they are studying, can
be very interesting.
Starting with string-comparisons on fixed strings
from a list (file based), which seem to be definitely
spam, can be changed to strings or patterns that are
often inside spam, soyou can use probabilistic methods.
Later you can try neural nets and support vector machines.

Also the filter can have an inputlanguage 8domain specific language)
so that the global/general behaviour can be controled by the
admin (fuzzy logicrules for the filtering and configuration
of any kind) and does not depend on the mathematical built
in's only.

The module system can be very helpful in combining the approaches.

If the sources will be published, also other peoplewould have a benefit,
and maybe some students will use it and developing it maybe late
after finishing studying there...


Best wishes,
      Oliver Bandel

Re: [Caml-list] Before teaching OCaml

[Andrej Bauer]

I teach theory of programming languages with ocaml on Windows. The path 
of least resistance seems to be ocaml + XEmacs + tuareg + premade make 
files (although omake sounds like a good option). It takes one lecture 
(45 minutes) to explain the setup, and the first homework is "install 
everything and compile helloWorld.ml".

If you're teaching math students who think that "java is not 
mathematical" enough, then you could offer mathematical projects, 
possibly involving graphics, such as:

1) A program that plots the graph of a function. This would involve 
parsing the function, so you'd have to teach basic lexing and parsing 
techniques. Or you can provide the lexer and parser and have them extend 
it with more functions.

For extra credit: a program that plots surfaces in 3D.

2) A program for drawing graphs in the plane. The layout of a graph is 
computed with one of many algorithms, e.g. a spring embedder. You can 
reuse the graph data structure to develop other things (shortest path 
etc.) You can have a graph drawing competition. You can have them draw 
graphs with 10000 vertices.

I once "won over" several math students from the Dark Side++ by showing 
them how to define the datatype of finite graphs and implement basic 
constructions, including computing Cayley's graph and finding the 
chromatic numbers (by a brute force method). They were convinced because 
the source code was "mathematically clean" and something like 5 times 
shorter than corresponding C++ would be.

3) This is shameless self-propaganda, but several people used random art 
as a fun project, see e.g. Assignment 2 at
http://www.cs.hmc.edu/courses/2005/fall/cs131/homework/index.html
(and compare with the "real thing" at http://www.random-art.org). In 
this project you can avoid writing parsers, while still having abstract 
syntax and an interpreter, or even a compiler/optimizer.

4) If your students are very mathematical, something like the tiling 
examples from "Developing applications in Ocaml" might interest them.

Best regards,

Andrej