TITLE: Programming Challenges
AUTHOR: Eugene Wallingford
DATE: November 10, 2007  4:21 PM
DESC: 
-----
BODY:
Gerald Weinberg's recent blog
<A HREF="http://weinbergonwriting.blogspot.com/2007/09/setting-and-character-goldilocks.html">
   Setting (and Character): A Goldilocks Exercise</A>
describes a writing exercise that I've
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2005-12.html#e2005-12-21T17_07_00.htm">
   mentioned here</A>
as a programming exercise, a pedagogical pattern many call
<A HREF="http://www.cs.uni.edu/~wallingf/patterns/pedagogical/three-bears.html">
   Three Bears</A>.
This is yet another occurrence of a remarkably diverse pattern.

Weinberg often describes exercises that writers can use to
free their minds and words.  It doesn't surprise me that
"freeing" exercises are
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2005-03.html#e2005-03-30T10_44_45.htm">
   built on constraints</A>.
In one post, Weinberg describes
<A HREF="http://weinbergonwriting.blogspot.com/2006/04/writing-exercise-1-missing-letter.html">
   The Missing Letter</A>,
in which the writer writes (or rewrites) a passage without
using a randomly chosen letter.  The most famous example of
this form, known as a lipogram, is <EM>La disparition</EM>,
a novel written by Georges Perec without an using the letter
'e' -- except to spell the author's name on the cover.

When I read that post months ago, I immediately thought of
creating programming exercises of a similar sort.  As I quoted
someone in a
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-08.html#e2007-08-08T15_40_18.htm">
   post on a book about Open Court Publishing</A>,
"Teaching any skill requires repetition, and few great works
of literature concentrate on long 'e'."  We can design a set
of exercises in which the programmer surrenders one of her
standard tools.  For instance, we could ask her to write a
program to solve a given problem, but...
<UL>
<LI> <STRONG>with no <TT>if</TT> statements</STRONG>.  This is
     exactly the idea embodied in the
     <A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2005-01.html#e2005-01-24T10_01_44.htm">
        Polymorphism Challenge</A>
     that my friend
     <A HREF="http://csis.pace.edu/~bergin/">
        Joe Bergin</A>
     and I used to teach a workshop at SIGCSE a couple of years
     ago and which I often find useful in helping programmers
     new to OOP see what is possible.

<LI> <STRONG>with no <TT>for</TT> statements</STRONG>.  I took
     a big step in understanding how objects worked when I
     realized how the internal iterators in Smalltalk's collection
     classes let me solve repetition tasks with a single message
     -- and a description of the action I wanted to take.  It
     was only many years later that I learned the term "internal
     iterator" or even just "iterator", but by then the idea was
     deeply ingrained in how I programmed.

     Recursion is the usual path for students to learn how to
     repeat actions without a <TT>for</TT> statement, but I
     don't think most students get recursion the way most folks
     teach it.  Learning it with a rich data type makes a lot
     more sense.

<LI> <STRONG>with no <TT>assignment</TT> statements</STRONG>.
     This exercise is a double-whammy.  Without assignment
     statements, there is no call explicit sequences of
     statements, either.  This is, of course, what pure
     functional programming asks of us.  Writing a big app in
     Java or C using a pure functional style is wonderful
     practice.

<LI> <STRONG>with no base types</STRONG>.  I nearly wrote about
     this sort of exercise a couple of years ago when discussing
     the OOP anti-pattern
     <A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2005-05.html#e2005-05-31T16_58_16.htm">
        Primitive Obsession</A>.
     If you can't use base types, all you have left are instances
     of classes.  What objects can do the job for you?  In most
     practical applications, this exercise ultimately bottoms out
     in a domain-specific class that wraps the base types required
     to make most programming languages run.  But it is a worthwhile
     practice exercise to see how long one can put off referring
     to a base type and still make sense.  The overkill can be
     enlightening.

     Of course, one can start with an language that provides only
     the most meager set of base types, thus forcing one to build
     up nearly all the abstractions demanded by a problem.  Scheme
     feels like that to most students, but only a few of mine seem
     to grok how much they can learn about programming by working
     in such a language.  (And it's of no comfort to them that
     Church built everything out of functions in his lambda calculus!)
</UL>

This list operates at the level of programming construct.  It is
just the beginning of the possibilities.  Another approach would
be to forbid the use of a data structure, a particularly useful
class, or an individual base type.  One could even turn this idea
into a naming challenge by hewing close to Weinberg's exercise
and forbidding the use of a selected letter in identifiers.
As an instructor, I can design an exercise targeted at the needs
of a particular student or class.  As a programmer, I can design
an exercise targeted at my own blocks and weaknesses.  Sometimes,
it's worth dusting off an old challenge and doing it for it's
own sake, just to stay sharp or shake off some rust.
-----