Project 3b

In this project you will explore functional programming and extend a generator of graph input files.

Also, for bonus marks, your can extend the current LISP code base.

Important note

  1. In the following, if I say "and test files etc showing it working", I expect to find "eg/it.li"and "eg/it.lisp.want" (for the expected output). There may also be, where appropriate, a "eg/it.dat" file containing a sample input file. That is, if you submit right, I should be able to test that part of the code using: 
    make X=it
  2. The following assignment defines 13 deliverables for a standard assignment plus several tasks that could earn bonus marks. Since not everyone may be doing all the bonus points, I need to know what to look for in your code. So, include in your directory "expect.txt" which just lists the deliverables I should look for. This is a very simple file containing one number per line: 
    1
2
3
4
5
6
7

    Note that everyone has to do "1 2 3 4" but after that, your numbers may change.

Setting up

Downloads

cd $HOME
mkdir -p cs310
svn export http://unbox.org/wisp/var/timm/09/310/lib/proj3 proj3b
cd proj3b
chmod +x lisps
./lisps eg/random.lisp

Tests

If the above works, you should see something like this: 

(0 0 0 0 0 0 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 4
 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 7 7 7
 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9)

How to submit

make submit

Background

The following grammar is a partial description of one of the graph input files: 

(defparameter *graph-spec*
  '((?spec    -> (?labels ?widths ?heights ?datas))
    (?labels  -> (label ?words nl))
    (?words   -> ?word (?word ?words))
    (?word    -> foo bar blah slug)
    (?widths  -> (width ?num nl))
    (?num     -> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
    (?heights -> (height ?num nl))
    (?datas   -> ?datums2 (?datums2 ?datas))
    (?datums2 -> (?datums1 ?datums1))
    (?datums1 -> (?num ?num ?symbol nl))
    (?symbol  -> \* \# \+)
))

In this notation:

By randomly selecting from the disjunctions, it is possible to generate any number of graph input files; e.g. after doing the above set up, you should get: 

     1
     2  ---| grammar.lisp |-----------------------------------------
     3
     4
     5
     6  label blah
     7  width 15
     8  height 14
     9  6 7 + 11 16 + 14 8 # 6 17 # 15 10 + 15 3 # 1 19 # 5 1 + 8 7 + 9 9 *
    10
    11  label blah
    12  width 11
    13  height 18
    14  16 20 + 15 9 * 19 8 * 8 3 #
    15
    16  label foo
    17  width 17
    18  height 3
    19  15 14 # 20 16 # 19 10 + 9 6 # 20 1 + 5 3 +
    20
    21  label bar
    22  width 10
    23  height 3
    24  17 7 # 11 17 # 20 16 + 3 20 #
    25
    26  label bar foo slug bar blah
    27  width 15
    28  height 2
    29  19 5 + 4 17 #
    30
    31  label slug
    32  width 11
    33  height 2
    34  19 3 + 20 3 #
    35
    36  label bar blah
    37  width 19
    38  height 14
    39  18 4 # 17 8 * 18 10 * 8 15 * 9 1 + 17 9 *
    40
    41  label slug
    42  width 20
    43  height 15
    44  2 3 * 19 11 #
    45
    46  label foo slug
    47  width 17
    48  height 16
    49  19 3 * 3 7 #
    50
    51  label foo
    52  width 9
    53  height 18
    54  15 3 + 2 14 +

Running the code

As before, there is a file "lisps" that loads all the .lisp files (listed in alphabetically order) into a lisp shell.

If you add arguments to "lisps", you can customize the behavior:

Note that, as before, the standard Makefile commands still run such as 

make                      --> runs one test
make X=grammar.lisp run   --> runs one test
make X=grammar.lisp cache --> runs one test, caches the results
make tests                --> runs all tests
make score                --> scores the tests.

If your run "make score" you'll see that there is something wrong with the code: 

 make score
*** - no handler for label
*** - no handler for bottom
*** - no handler for label
*** - no handler for label
*** - no handler for label
*** - no handler for label
*** - no handler for label
*** - no handler for label
*** - no handler for label
  12 FAILED
   6 PASSED

What is going on here is that the LISP code I have supplied can not (yet) draw graphs. For bonus marks, you might choose to fix that.

What to do

There are several things wrong with the above that you must fix:

Easy Stuff (5 marks)

  1. The grammar does not describe all the possible graph data inputs (e.g. bottom ticks, amongst other things). Fix that. Note: the grammar can be found around line 100 of grammar.lisp.
  2. The grammar does not handle data lines properly

Harder stuff (5 marks)

Both the following require problems require a recursive walk through a nested list structure. In LISP, such a recursive descent looks like this: 

(defun countr (x l)
  (cond ((null l)  0)                  ; case 1) empty list  
	((atom l)  (if (eql x l) 1 0)) ; case 2) not a list
	(t                             ; case 3) isa list so ...
	 (let ((n 0))
	   (dolist (one l n)           ; we recurse
	     (incf n                   
		   (countr x one)))))))
  1. The grammar needs a syntax checker. The following checks can be implemented as a recursive walk through the grammar:
  2. The grammar output needs a sanity check. For example, when you code "bottom ticks" using "?num" it is possible to get crazy stuff like xmin values that are greater than the xmax values. This can be implemented as a recursive descent through the output of "(generate '?spec)", coded as follows: 
    (dotimes (i 20)
   (let ((spec (generate '?spec)))
      (if (sane spec)
          (spec->lines spec))))

    Note that not all the specs will be printed. So if your call this with "(dotimes (i 20) .." it is well possible you will only see, say, 18 specs. <6l>

  3. WHAT TO SUBMIT: (7) a file sanity.lisp, that implements the checker; (8) test files eg/sanity.lisp , etc.

Bonus Stuff (20 marks)

  1. (5 marks) Adjust the grammar to generate science fiction stories of the form described in http://www.yorku.ca/srowley/g_wilson_computer.jpg . To demonstrate this:
  2. (5 marks) Add probabilities to each rule. Right now, disjunctions are chosen at random. This is not approrpirate for some applications- sometimes you want to run some things more often than others. Add a number at the rhs of the production showing the probability of that production firing. Skew the firing according to those numbers. The cheat's way of doing this is to input the productions+probabilities and output a new grammar with certain production copied multiple times. Then the above grammar will pick according to your probabilities.
  3. (5 marks) Take the output to test your Smalltalk code. Here, you succeed if you can (a) do the systems work of automatically passing the LISP output to the Smalltalk and (b) show that you can break the Smalltalk code (some stack dump).
  4. (5 marks) The code I've given you implements a skeleton of the graph generator in LISP. Code it up and show that you can get "18 PASSED" from "make scores".