/LMAR=0/XLINE=3/FONT#0=BAXL30[FNT,CLT]/FONT#1=BAXM30/FONT#2=BAXB30[FNT,CLT]/FONT#5=NGR25/FONT#3=SUB/FONT#4=SUP/FONT#7=SYMB30[FNT,CLT]

␈↓ ↓H␈↓␈↓ ∧+COMPUTER SCIENCE DEPARTMENT
␈↓ ↓H␈↓␈↓ ¬πSTANFORD UNIVERSITY
␈↓ ↓H␈↓CS206  ␈↓ βZCOMPUTING WITH SYMBOLIC EXPRESSIONS  ␈↓ 
SPRING 1978

␈↓ ↓H␈↓α␈↓ ¬FTERM PROJECTS

␈↓ ↓H␈↓        A␈αterm␈αproject␈αis␈αnot␈αrequired␈αin␈αorder␈αto␈αpass␈αCS206␈αor␈αeven␈αto␈αget␈αa␈αgrade␈αof␈αB␈αif␈αyour
␈↓ ↓H␈↓homework␈α
and␈α
exams␈αare␈α
good␈α
enough.␈α However,␈α
if␈α
you␈α
wish␈αto␈α
get␈α
some␈αflavor␈α
of␈α
A␈αthen␈α
doing
␈↓ ↓H␈↓a␈αgood␈α
term␈αproject␈αis␈α
necessary.␈α Term␈α
projects␈αwill␈αbe␈α
due␈αon␈α
the␈αday␈αof␈α
the␈αfinal␈α
exam.␈α Any
␈↓ ↓H␈↓term project turned in ahead of time will be likely to get a more thorough reading.

␈↓ ↓H␈↓        The␈αterm␈αproject␈αis␈αyour␈αopportunity␈αto␈αdirect␈αyour␈αattention␈αto␈αand␈αget␈αexperience␈αin␈αsome
␈↓ ↓H␈↓area␈α
that␈α
interests␈αyou.␈α
  Briefly␈α
the␈αpossibilities␈α
include␈α
writing␈αand␈α
documenting␈α
an␈αsubstantial
␈↓ ↓H␈↓LISP␈α∞program,␈α∞proving␈α∞the␈α∞correctness␈α∞of␈α∞a␈α∞moderate␈α∞sized␈α∞LISP␈α∞program␈α∞using␈α∞FOL␈α∞and␈α
the
␈↓ ↓H␈↓techniques␈α
of␈α
Chapter␈αIII,␈α
or␈α
to␈α
join␈αan␈α
on␈α
going␈α
project␈αand␈α
write␈α
code␈α
for␈αsome␈α
piece␈α
of␈αa␈α
larger
␈↓ ↓H␈↓system.␈α∂ (Richard␈α∂Weyrauch(RWW)␈α∂and␈α∂Bob␈α∂Filman(REF)␈α⊂at␈α∂the␈α∂AI␈α∂Lab␈α∂are␈α∂willing␈α⊂to␈α∂have
␈↓ ↓H␈↓students␈αjoin␈αprojects␈αthey␈αare␈αworking␈αon␈αat␈αthe␈αlab␈αor␈αprovide␈αguidance␈αin␈αsome␈αother␈αprojects.
␈↓ ↓H␈↓Such projects these are by references to RWW and REF.)

␈↓ ↓H␈↓        The␈α
write␈α
up␈α
of␈α
your␈α
project␈α
is␈α
the␈α
main␈α
thing␈α
that␈α
will␈α
get␈α
graded␈α
so␈α
it␈α
should␈α
be␈α
clear␈α
and
␈↓ ↓H␈↓carefully␈α∂done.␈α∂ It␈α∂should␈α∂include␈α∞a␈α∂brief␈α∂description␈α∂of␈α∂what␈α∂you␈α∞set␈α∂out␈α∂to␈α∂do␈α∂and␈α∂what␈α∞you
␈↓ ↓H␈↓accomplished.␈α∞ If␈α∞you␈α
write␈α∞a␈α∞progam,␈α
you␈α∞should␈α∞give␈α
a␈α∞description␈α∞of␈α
how␈α∞it␈α∞works␈α∞and␈α
why,
␈↓ ↓H␈↓including␈α∞a␈α∞description␈α∂of␈α∞the␈α∞data␈α∂structures␈α∞it␈α∞is␈α∂acting␈α∞on␈α∞and␈α∂the␈α∞basic␈α∞operations␈α∂on␈α∞these
␈↓ ↓H␈↓structures.␈α∂ The␈α∂code␈α∂for␈α∂the␈α∂program␈α∂should␈α∂be␈α∂included␈α∂with␈α∂brief␈α∂comments␈α∂in␈α∂appropriate
␈↓ ↓H␈↓places␈αto␈αguide␈αthe␈αreader.␈α Some␈αsample␈αruns␈αshould␈αalso␈αbe␈αincluded.␈α If␈αyou␈αdo␈αa␈αformal␈αproof,
␈↓ ↓H␈↓you␈α∩should␈α∩include␈α∩a␈α∩brief␈α∩description␈α∪of␈α∩the␈α∩program(s)␈α∩you␈α∩are␈α∩proving␈α∩things␈α∪about,␈α∩an
␈↓ ↓H␈↓informal proof mentioning the key steps, and the formal proof (which can be generated by FOL).

␈↓ ↓H␈↓        The␈α∞following␈α∞are␈α
some␈α∞ideas␈α∞for␈α∞term␈α
projects.␈α∞ You␈α∞may␈α∞choose␈α
one␈α∞of␈α∞these,␈α∞or␈α
design
␈↓ ↓H␈↓your own project.


␈↓ ↓H␈↓αLISP programs

␈↓ ↓H␈↓1. Improve the LCOM4 compiler.  Some possibilities are to modify LCOM4 to:

␈↓ ↓H␈↓        1.1. compile  ␈↓↓label.␈↓
␈↓ ↓H␈↓        1.2. handle the ␈↓αprog␈↓ and related features.
␈↓ ↓H␈↓        1.3. handle functions as arguments (as for ␈↓↓mapcar)␈↓ .
␈↓ ↓H␈↓        1.4. recognize iteration and compile it with loops.
␈↓ ↓H␈↓        1.5. produce more efficient arithmetic code.
␈↓ ↓H␈↓        1.6. generate more efficient code in other cases where you might have noticed inefficiencies.
␈↓ ↓H␈↓        1.7. compile additional features such as "while's" or "do's" etc..

␈↓ ↓H␈↓2.␈α
Write␈α
a␈α
program␈α
that␈α
converts␈α
a␈α
function␈α
definition␈α
in␈α
to␈α
an␈α
iterative␈α
form␈α
for␈α
some␈α
class␈α
of
␈↓ ↓H␈↓definitions,␈α
or␈α
improves␈α
the␈αefficiency␈α
of␈α
some␈α
class␈α
of␈αprograms.␈α
 For␈α
example␈α
consider␈α
the␈αtwo
␈↓ ↓H␈↓definitions of ␈↓↓factorial␈↓

␈↓ ↓H␈↓␈↓ ∧H␈↓↓fact n ← ␈↓αif␈↓↓ n=0 ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ n ␈↓π*␈↓↓ fact n-1␈↓
␈↓ ↓H␈↓and
␈↓ ↓H␈↓␈↓ ¬K␈↓↓fact n ← facti[n,1] ␈↓
␈↓ ↓H␈↓where
␈↓ ↓H␈↓␈↓ ∧→␈↓↓facti[n,m]← ␈↓αif␈↓↓ n=0 ␈↓αthen␈↓↓ m ␈↓αelse␈↓↓ facti[n-1,n␈↓π*␈↓↓m]␈↓
␈↓ ↓H␈↓␈↓ εH␈↓ 92


␈↓ ↓H␈↓the␈α∂latter␈α∂is␈α∞form␈α∂is␈α∂␈↓↓iterative␈↓␈α∞and␈α∂could␈α∂easily␈α∂be␈α∞expressed␈α∂as␈α∂a␈α∞loop.␈α∂ More␈α∂impressive␈α∂is␈α∞the
␈↓ ↓H␈↓saving␈αwhen␈αyou␈αtransform␈αthe␈αobvious␈αdefinition␈αof␈αthe␈αfunction␈αto␈αcompute␈αFibonacci␈αnumbers
␈↓ ↓H␈↓into iterative form.

␈↓ ↓H␈↓␈↓ βy␈↓↓fib n ← ␈↓αif␈↓↓ n=0∨n=1 ␈↓αthen␈↓↓ 1 ␈↓αelse␈↓↓ [fib n-1] + [fib n-2]␈↓
␈↓ ↓H␈↓vs
␈↓ ↓H␈↓␈↓ ¬O␈↓↓fib n ← fibi[n,1,1]␈↓
␈↓ ↓H␈↓where
␈↓ ↓H␈↓␈↓ βv␈↓↓fibi[n,k,l] ← ␈↓αif␈↓↓ n=0∨n=1 ␈↓αthen␈↓↓ l ␈↓αelse␈↓↓ fibi[n-1,l,k+l]␈↓

␈↓ ↓H␈↓The first version makes O(␈↓↓fib n␈↓) calls to itself while the latter makes only O(␈↓↓n␈↓).

␈↓ ↓H␈↓        For␈α∂ideas␈α⊂on␈α∂improving␈α∂efficiency␈α⊂consider␈α∂the␈α∂various␈α⊂definitions␈α∂of␈α∂␈↓↓reverse␈↓␈α⊂and␈α∂␈↓↓fringe␈↓
␈↓ ↓H␈↓given in Chapter I.

␈↓ ↓H␈↓3.␈α⊃Extend␈α⊃the␈α⊃notion␈α⊃of␈α⊂purifiable␈α⊃LISP␈α⊃term␈α⊃in␈α⊃some␈α⊂useful␈α⊃and␈α⊃non-tirival␈α⊃way.␈α⊃ Write␈α⊂a
␈↓ ↓H␈↓program␈αthat␈α
tests␈αfor␈αpurifiability.␈α
Write␈αa␈αprogram␈α
that␈αproduces␈αpure␈α
terms␈αfrom␈αpurifiable␈α
(in
␈↓ ↓H␈↓the extended sense) ones.  (See Chapters IV and V.)

␈↓ ↓H␈↓4.␈αImprove␈αMACLISP␈αat␈αLOTS.␈α The␈αidea␈αhere␈α
is␈αto␈αwrite␈αa␈αprogram␈αto␈αhelp␈αpeople␈α
use␈αLISP.
␈↓ ↓H␈↓For example

␈↓ ↓H␈↓        4.1.␈α
Write␈α∞a␈α
LISP␈α∞tutor.␈α
 This␈α
would␈α∞be␈α
a␈α∞program␈α
that␈α
could␈α∞be␈α
loaded␈α∞into␈α
MACLISP
␈↓ ↓H␈↓and␈α
would␈αexplain␈α
some␈αof␈α
the␈αfeatures␈α
of␈αLISP␈α
and␈αthen␈α
ask␈αthe␈α
user␈αquestions␈α
and␈α
check␈αthe
␈↓ ↓H␈↓answers.␈α Choose␈αa␈αfew␈αfeatures␈αthat␈αinterest␈αyou␈αand␈αdo␈αthem␈αthoroughly,␈αor␈αget␈αtogether␈αwith␈αa
␈↓ ↓H␈↓group␈α
of␈α
students␈α
and␈α
divide␈α
up␈α
the␈α
work.␈α
 In␈α
the␈α
latter␈α
case␈α
it␈α
should␈α
be␈α
clear␈α
who␈α∞did␈α
which
␈↓ ↓H␈↓pieces, although co-operation is essential.

␈↓ ↓H␈↓        4.2.␈α Write␈αa␈αHELP␈αprogram␈α
that␈αwould␈αallow␈αthe␈αuser␈α
to␈αask␈αfor␈αHELP␈αon␈αsome␈α
collection
␈↓ ↓H␈↓of␈α
topics␈α
and␈αgive␈α
useful␈α
information␈αon␈α
those␈α
topics.␈α The␈α
topics␈α
might␈αinclude␈α
a␈α
partial␈α
list␈αof
␈↓ ↓H␈↓available functions, i/o conventions, debugging facilities, etc.

␈↓ ↓H␈↓        4.3.␈α⊂ Write␈α⊂some␈α⊂editing,␈α⊃file␈α⊂manipulating,␈α⊂i/o␈α⊂or␈α⊂other␈α⊃programs␈α⊂to␈α⊂do␈α⊂the␈α⊃things␈α⊂you
␈↓ ↓H␈↓wanted to be able to do but couldn't when you started using MACLISP at LOTS.

␈↓ ↓H␈↓        The␈α∞tutor␈α∂and␈α∞HELP␈α∞programs␈α∂will␈α∞require␈α∞a␈α∂lot␈α∞of␈α∞thought␈α∂and␈α∞understanding␈α∂of␈α∞how
␈↓ ↓H␈↓LISP␈α
works␈α
and␈α
knowing␈α
what␈α
is␈α
really␈α
useful,␈α
but␈α
the␈α
actual␈α
programming␈α
should␈α
not␈α
be␈α
very
␈↓ ↓H␈↓difficult.␈α Any␈α
good␈αprojects␈α
of␈αthe␈αabove␈α
nature␈αcould␈α
be␈αcompiled␈αand␈α
put␈αon␈α
the␈αsystem␈αfor␈α
the
␈↓ ↓H␈↓benefit of future users.

␈↓ ↓H␈↓5. Write a program to play a game.  Some possible games are:

␈↓ ↓H␈↓        5.1. 3-dimensional Tic Tac Toe (See Chapter II for 2-D version)
␈↓ ↓H␈↓        5.2. Solitare
␈↓ ↓H␈↓        5.3. Go (RWW and REF have ideas for interesting projects)

␈↓ ↓H␈↓    Be␈α⊂sure␈α⊂to␈α⊂hold␈α⊂individual␈α⊂test␈α∂runs␈α⊂to␈α⊂a␈α⊂few␈α⊂seconds.␈α⊂ It␈α∂is␈α⊂easy␈α⊂to␈α⊂use␈α⊂large␈α⊂amounts␈α∂of
␈↓ ↓H␈↓computer time in such projects.
␈↓ ↓H␈↓␈↓ εH␈↓ 93


␈↓ ↓H␈↓αIdeas for projects emphasizing proving.

␈↓ ↓H␈↓1.␈α⊃Prove␈α⊃the␈α⊃correctness␈α⊃or␈α⊃other␈α⊃interesting␈α⊃property␈α⊃of␈α⊃a␈α⊃moderate␈α⊃size␈α⊃LISP␈α∩function␈α⊃and
␈↓ ↓H␈↓formalize␈αyour␈αproof␈αusing␈α FOL.␈α  For␈αexample␈αExercise 3␈αof␈αChapter III␈αwould␈αbe␈αsuitable.␈α Or
␈↓ ↓H␈↓you␈αmay␈αwrite␈αyour␈αown␈αfucntion␈αand␈αspecifications.␈α(See␈αAppendix␈αA␈αfor␈αan␈αexample␈αof␈αa␈αFOL
␈↓ ↓H␈↓proof.)

␈↓ ↓H␈↓2.␈α Develop␈αthe␈αtheory␈αof␈αre-entrant␈α
list␈αstructures.␈α (see␈αChapter␈αIV.)␈αDecide␈αon␈α
a␈αrepresentation
␈↓ ↓H␈↓of␈α∀such␈α∃structures␈α∀as␈α∀ordinary␈α∃lists␈α∀(say␈α∃with␈α∀pointers␈α∀and␈α∃labels).␈α∀ Define␈α∃some␈α∀primitive
␈↓ ↓H␈↓operations␈α(for␈αexample:␈α␈↓↓car␈αcdr␈αcons␈αpoint␈αcut␈↓).␈α Write␈αprograms␈αto␈αgo␈αfrom␈αone␈αrepresentation␈αto
␈↓ ↓H␈↓the␈α∂other.␈α∂ Write␈α∞an␈α∂equality␈α∂predicate␈α∂in␈α∞for␈α∂structures␈α∂in␈α∞your␈α∂representation.␈α∂  Work␈α∂out␈α∞an
␈↓ ↓H␈↓induction␈α∂schema␈α∂to␈α∞allow␈α∂you␈α∂to␈α∂tell␈α∞when␈α∂programs␈α∂on␈α∞such␈α∂structures␈α∂will␈α∂terminate.␈α∞ Write
␈↓ ↓H␈↓some interesting programs on such structures and prove some facts about them.


␈↓ ↓H␈↓αWork on the FOL project

␈↓ ↓H␈↓        (See RWW or CLT for more details or ideas)

␈↓ ↓H␈↓1.  DEFINITIONS: Implement commands to make and unmake definitions.
␈↓ ↓H␈↓2.  DECISION PROCEDURES:
␈↓ ↓H␈↓        2.1. real closed fields
␈↓ ↓H␈↓        2.2. word problem for semigroup semi-decider.
␈↓ ↓H␈↓        2.3. decide plane geometry.
␈↓ ↓H␈↓3.  WFF MANIPULATION:
␈↓ ↓H␈↓        3.1. conjunctive normal form
␈↓ ↓H␈↓        3.2. disjunctive normal form
␈↓ ↓H␈↓        3.3. prenexization
␈↓ ↓H␈↓        3.4. recognize well-formedness in a particual environment
␈↓ ↓H␈↓        3.5. prefix complexity minimalization???
␈↓ ↓H␈↓4.  ARITHMETIC EXPRESSION SIMPLIFICATION:
␈↓ ↓H␈↓        4.1. define a normal form and write code that puts a term in this form
␈↓ ↓H␈↓        4.2. reduction of an "=" or "≤" term to simpler form
␈↓ ↓H␈↓        4.3. rewriting and "=" or "≤" term using a list of facts which have the same form.
␈↓ ↓H␈↓5.  STATISTICAL ROUTINES FOR FOL:
␈↓ ↓H␈↓        5.1. frequency of GC
␈↓ ↓H␈↓        5.2. memory management statistics
␈↓ ↓H␈↓        5.3. record of usage
␈↓ ↓H␈↓6.  LAMBDA EXPRESSION MANIPULATION



␈↓ ↓H␈↓αOther projects to join.

␈↓ ↓H␈↓1.␈α Document␈α
compiler.␈α REF␈α
has␈αprimitive␈αroutines␈α
and␈αideas␈α
for␈αwriting␈α
a␈αdocument␈αcompiler␈α
in
␈↓ ↓H␈↓LISP␈α∩(PUB␈α∩POX␈α∩RUNOFF␈α∩are␈α∩document␈α∩compilers).␈α∩ RWW␈α∩also␈α∩has␈α∩ideas␈α∪about␈α∩writing
␈↓ ↓H␈↓document compilers.  Pieces of this would make an interesting project.

␈↓ ↓H␈↓2.␈α
 RWW␈α
and␈α
CLT␈α
and␈α
others␈α
are␈α
working␈αon␈α
a␈α
music␈α
compiler␈α
in␈α
LISP.␈α
 If␈α
you␈α
are␈αinterested␈α
in
␈↓ ↓H␈↓computer music there are pieces of this that would make interesting term projects.