k\input texinfo

by Tim Menzies

LCSEE, WVU, Spring 2011

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License (http://creativecommons.org/licenses/by-sa/3.0/), Copyright © 2011, Tim Menzies.

Contents
========

Change history:
===============

Jan 5, 2010
     Released:

       * 1. Syllabus

       * 2.1 Lectures: what is the best programming language?

       * 3.0, 3.1, 3.2, 3.3, 3.4, 3.4.1: project set up and first homework

Syllabus
********

Overview
========

  * Course name: CS310, Principles of Programming Languages

  * Effective data of syllabus: Jan 11, 2011

  * Site: LCSEE, WVU

  * Course number: 10961

  * Pre-requisite: successful completion of CS 111, Data Structures

  * Course format: 3 credit hours 3 hr lectures, exams, weekly homework

  * Textbook:

       - Michael L. Scott, Programming Language Pragmatics (3rd edition) http://goo.gl/Vzku5.

       - Paul Graham, ANSI Common LISP http://goo.gl/lDSVp.

  * Schedule : Tuesday, Thursday, 1530-1645

  * Location : ESB G39

  * Instructor name: Tim Menzies Ph.D. ESB 841a, tim@menzies.us. Note: please use this email for private messages. For most of the class traffic, use the class discussion list (https://groups.google.com/group/cs310/topics?hl=en)

  * Consultation times : Tuesday, Thursday 1645 to 1745 or by appointment

Objectives
==========

Overview of different paradigms of programming languages. Detailed studies in  object-oriented, functional, and logic programming. Theoretical aspects of programming languages including basic language translation, virtual machines, abstraction mechanisms, declarations and types.

Topics
======

  * Week 1: Overview (1, a)

  * Week 2: Grammars (1, a)

  * Week 3,4: Functional programming  (2, a, b, c, k)

  * Week 5: Abstraction Mechanisms (1, a)

  * Week 6: Declarations and Types (1, a)

  * Week 7,8:Object-oriented programming (1, a, b, c)

  * Week 9: Basic language translation (1, a, b)

  * Week 10: Virtual machines (1, a, b)

  * Week 11,12: Logic Programming (a, b, c, k)

  * Week 13,14: special topics (a, k)

Note that all the case studies involve translating and executing a high-level specification, written as a variant of an attributed EBNF grammar. Hence, they all contribute to b, c

ACM curriculum:

  * 1 core

  * 2 elective A

LCSEE computer science program objectives:

  * a Be exposed to a variety of programming languages and systems, and will be proficient in programming in at least two languages.

  * b Have the knowledge of the basic principles and methods of programming language translation.

  * c Have knowledge of the basic principles of data structures, discrete mathematics and algorithms, and be able to apply this knowledge to problem solving in relevant application areas.

  * k Be familiar with advanced concepts of several specialized computer science areas.

Expected Workload
=================

You MUST be prepared to dedicate AT LEAST 5-8 working hours a week to this class (excluding the time spent in the classroom). A minimal prerequisite for the successful completion is good understanding of programming concepts. You should have gained these in the prerequisite class, CS 111. Familiarity with a high level programming language is assumed (as taught in CS 111). Laboratory instruction is not included in CS 310. You will be given class accounts on CS Department machines and all assignments will have to be submitted and run there. Please note that a Linux server can be accessed from any PC using a secure connection service, such as SSH (explanation to be provided in class).

All students will commit their work to an on-line repository, supplied by the lecturer.

This is a tools-based subject and it is required that students learn those tools (Ssh, Emacs, Subversion, LISP).

Assessment
==========

  * Mid-term: 18 marks

  * Final exam: 40 marks

  * Three projects, 16 marks each.

       * These projects will be called 1,2,3

       * Each will have weekly deliverables a,b,c,d where a,b,c is worth 2 mark each and d is worth 10 marks.

       * Each project will end with a live demo in front of a tutor where groups will lose marks if:

            * The day before the demo, each student member did not fill out and email the group peer assessment form (studentPeerEvaluation.doc) to the tutor.

            * Members do not attend,

            * or if the required functionality is not demonstrable,

            * or if they cannot explain randomly selected line of codes.

Final Grades
------------

  * A : 90 - 100

  * B : 80 - 89

  * C : 70 - 79

  * D : 60 - 69

  * F : otherwise

See also, below, for how to lose marks due to poor attendance.

Attendance Policy
-----------------

Lectures: Students are expected to regularly attend lectures. After three noted absences, students will lose two points per absence. After three noted lated arrivals, students will lose one point per late arrival. If you have another commitment that requires you to be consistently late, you should drop the class.

Exams: Consistent with WVU guidelines, students absent from regularly scheduled examinations because of authorized University activities will have the opportunity to take them at an alternate time. Make-up exams for absences due to any other reason will be at the discretion of the instructor.

Late Work
---------

There are no late marks; i.e. late homeworks score zero marks.

Total student marks add up to 18+40+16*3 = 106.

That is, you can skip any 3 of the (a,b,c) homeworks and get full marks.

The wise student will hoard all their ``skip'' marks and use them only for sickness.

However, all students homeworks must be submitted prior to worked solutions being released. So if you are skipping you still have to hand in one sheet of paper saying "skipping"".

Special Consideration
---------------------

See me at start of semester advising planned absences or if you need other special considerations.

Timetable
=========

Homework due: weeks 2,3,4,5,6, then 8,9,10,11,12,13,14

Mid-session test: week 7

Final exams: as per university timetable.

Social Justice Statement
========================

West Virginia University is committed to social justice. I concur with that commitment and expect to foster a nurturing learning environment based upon open communication, mutual respect, and non-discrimination. Our University does not discriminate on the basis of race, sex, age, disability, veteran status, religion, sexual orientation, color or national origin. Any suggestions as to how to further such a positive and open environment in this class will be appreciated and given serious consideration.

If you are a person with a disability and anticipate needing any type of accommodation in order to participate in this class, please advise me and make appropriate arrangements with Disability Services (293-6700).

Statement of Academic Integrity
===============================

The integrity of the classes offered by any academic institution solidifies the foundation of its mission and cannot be sacrificed to expediency, ignorance, or blatant fraud. Therefore, I will enforce rigorous standards of academic integrity in all aspects and assignments of this course.

For the detailed policy of West Virginia University regarding the definitions of acts considered to fall under academic dishonesty and possible ensuing sanctions, please see the Student Conduct Code at http://www.arc.wvu.edu/admissions/integrity.html. Should you have any questions about possibly improper research citations or references, or any other activity that may be interpreted as an attempt at academic dishonesty, please see me before the assignment is due to discuss the matter.

Lecture notes
*************

What is the best programming language?
======================================

     [file bestlang.texi not included]

     [file grammar.texi not included]

     [file grammar1.texi not included]

Yet More on Pattern-Drive Programming
=====================================

Rule-based programming (rules.pdf)

Example rule-base (usedcar_clips.txt).

     [file functional.texi not included]

     [file gold.texi not included]

     [file oo.texi not included]

     [file abstract.texi not included]

     [file virtual.texi not included]

     [file translate.texi not included]

     [file logic.texi not included]

Student projects
****************

Students will work in groups of three. Group membership will be randomly assigned. All group members will have the same mark, except (at the discretion of the tutor) if the the group peer assessment forms (studentPeerEvaluation.doc) show uneven effort by group members.

Overview
========

In these projects, students will write their own domain-specific language for generating science fiction stories.  This new language will be coded in three ways: functional, object-oriented, and logical.  In doing the same task, three ways, students will be learn how to compare, contrast, mix, and match language paradigms.

Example stories that might be generated are:

  * Earth scientists invent giant bugs who want Our Women,  And Take A Few And Leave

  * Earth is Attacked By tiny lunar superbeings who  Under Stand and Are Not radioactive and can not be killed by the Navy but They Die From Catching A Cold

  * Earth scientists invent enormous bugs who are Friendly and and They Get Married And Live Happily Forever After

To code the stories, we will use a stochastic grammar engine based on Gahan Wilson's generalization of SF stories. A story is any one path (selected at random) through the following structure:

Groups
======

Students will work in groups of three.

1 : jlake8 adolby rdurst1

2 : lmazza mchicoin jdelong

3 : dparks2 jharpel oaragon

4 : ssimons1 porsinge acline3

5 : dringer2 tmolina cmcgee1

6 : adanie11 jyaworsk kcruse1

7 : pprince mgrubb1 nbolyard

8 : jsatter5 jingram3 tmille42

9 : rmccorm8 plewis2 mcorum

10 : jvaughn1 cgutshal pkirkpat

11 : jsteve14 amorga25 agilber3

12 : ckorb rmoneype jmckowen

13 : msidatt jbrenwal lblake2

14 : smatchet dbenne14 cpetrosk

15 : lcorcuer alamb3 mgharee2

16 : nclay1 barmstr2 rgross4

17 : bokanyme nyanak kdavis10

18 : dswisher jsteele9 pshahan

19 : kphilyaw eiannell mcheeks1

20 : khebert anoore1 jcanady1

21 : thitrik ashepard mkobe

22 : jbreyer jcoope30 dwilli40

23 : swhite24 chinkle2 swelsh4

24 : ccover cmetz7 rrush4

25 : rrawling mphares2 ekrimcha

26 : qwu1 yding

27: jcraig6 wklingel

FYI: students were assigned to groups, at random, using this script:

cat names |
gawk '{N[rand()]=$0}
  END {for(i in N) print N}'

Setting up
==========

Initial Set up
==============

Before doing the regular weekly setups, perform the following one-time steps.

Setting up Subversion
---------------------

  * Find out your group number (XX)

  * Run these commands:
     cd ~/
     mkdir  svns
     cd svns
     svn co  https://websvn.lcsee.wvu.edu/cs310gpXX 310

Setting up Lisp
---------------

Edit the file $HOME/.emacs and add this line:
(load  "/home/timm/etc/dotemacs.lisp")

Weekly set up
=============

Say you are setting up for project 1, homework a.

One person in the group  run these commands
cd ~/svns/310
svn mkdir 1
cd 1
svn export http://unbox.org/wisp/var/timm/11/310/src/1/a a
cd ~/svns/310
svn commit -m 'project 1a created'

Then, everyone else runs these commands on their accounts:
cd ~/svns/310
svn update

Now, everyone in the group can edit and share the same files.

Submitting
==========

If you've exported my files to your directories, then you should see at least the following files:

$ ls go*
go*     go_bash*    go_lisp

To run your system, you must edit a file boot.lisp that loads your lisp system. This file is called by go_lisp in the following script (the contents of which, you can ignore):

#|
exec sbcl --noinform --load $0 --end-toplevel-options "$@"
|#
(load "boot.lisp")
(quit)

Now go_lisp is called by go which looks like this:
[ -f go_bash ] && bash go_bash
nice -n 20 sh go_lisp
[ -f stop_bash ] && bash stop_bash

Note that before and after we call go_lisp, we look for any shell commands in go_bash or stop_bash. So, if you want to show your source code, you could edit go_bash:

cat aa.lisp bb.lisp cc.lisp

Or, if you want to show what output files were generated by your lisp code, you could edit stop_bash:

cat out.txt

To prepare your weekly handin, one member of your group must run the following command:
 ~timm/bin/handin homeWorkNumber groupNumber lastname1 lastname2 lastname3...
where homeWorkNumber is something like 2c and lastname is the last name of each member of the group. For example:

~timm/bin/handin 2a 22 zedong washington

This command generates a file ~/tmp/2print.pdf in your tmp directory. This file stores a pretty print of what happens when the go command (mentioned above) is executed.  Here's a sample file (2print.pdf) (and a real one would have much more content).

To hand in your homework, print out ~/tmp/2print and hand it in to the box outside 841a before the Tuesday class. Note that:

  * These homeworks will not be collected at the lectures.

  * If you do not staple your file, it will not be marked.

  * These homeworks will be collected and marked at 3:30 so do not be late.

Project1: Functional
====================

In this project you will use a functional language (LISP) to implement a random story generator using a BNF-like grammar.

Functional languages: set up
----------------------------

How to hand in
==============

Following the Submitting instructions, edit the file ~/svns/310/1/a/go_bash to include the lines

report() {
       for i in $*; do
              echo ""
              echo "=====|  $i |============================"
              cat $i
       done
}

report boot.lisp repl.txt keystrokes.txt log.txt

Then following the following steps to generate the report files.

Finally, run the handin code (described in Submitting).

Setting up
==========

Follow the initial set up instructions.

Perform the weekly set up instructions for project 1, homework a.

Exercise 1: Learning Emacs
==========================

Open Emacs using emacs boot.lisp. You should see two buffers: one with boot.lisp and one with the REPL (the interactive read-eval-print loop of LISP).

In the REPL,  work out what one plus one equals.

In the file boot.lisp, add a format statement on the last line saying "COBOL is the bestish language in the whoooole world...NOT":

(format t "COBOL is the bestish language in the whoooole world...NOT")

Save the file (using C-xC-s) then load it from the REPL:

(load "boot.lisp")

Now you should see in the REPL lines that look like this:

; SLIME 2009-09-08
CL-USER> (+ 1 1)
2
CL-USER> (load "boot.lisp")
;tricks.lisp
LITHP ITH LITHTENING
COBOL is the bestish language in the whoooole world...NOT
T
CL-USER>

Save the REPL buffer to a file (using C-xC-x) called ~/svns/310/1/a/repl.txt.

Exercise 2: Learning more Emacs
===============================

Write down a file ~/svns/310/1/a/keystrokes.txt that shows what keystrokes in Emacs:

  * Save a file

  * Open a new file

  * Split a buffer in two, vertically

  * Split a buffer in two, horizontally

  * Start a shell in a buffer (hint: is it  M-x eshell?)

Hint: http://www.columbia.edu/acis/publications/emacs.html.

Exercise 3: Sing a song together
================================

Take the West Virginia fight song (http://lyricsondemand.com/miscellaneouslyrics/fightsongslyrics/westvirginiafightsonglyrics.html) and break it up between all group members.

In the directory ~/svns/310/1/a, every member of the group write a file lastname.lisp that prints their bit of the entire song. e.g.

(format t "Let's give a rah for West Virginia~%")
(format t "And let us pledge to her anew,~%")
(format t "Others may be black or crimson,~%")
(format t "but for us it's Gold and Blue.~%")

Then, edit boot.lisp so that it loads every one's file.

Finally, make sure the whole song prints:

bash go_lisp

Exercise 4: Learning Subversion
===============================

Run this command :
cd ~/svns/310/1/a
svn log > log.txt

Edit that file. Write a comment at the end describing what you see.

Functional languages: Lisp101
-----------------------------

Setup
=====

Perform the weekly set up instructions for project 1, homework b.

What to hand in
===============

Report (a) all the lisp functions you've written and (b) a file containing your deftests and (c) repl.txt coming from you saving the REPL showing these all running.

Basic LISP
==========

Write LISP functions  to implement the following:

(deftest !count-of ()
	(test 3
		(count-of 'a '(a b  (c d  a) (e a)))))

(deftest !sum-of ()
	(test 28
		(sum-of '(1 2  (3 4 5) (6 7)))))

(deftest !oddd-of ()
	(test 4
		(odd-of '(1 2  (3 4 5) (6 7)))))

Note for the above:

  * First code the easy case (when the list has no sub-lists). Then go to recursive lists.

  * For odd-of   there is a function call (oddp num) that returns true if num is an odd number.

(deftest !odd-arr ()
	(test '(1 3 5 7)
		(odd-of '(1 2  (3 4 5) (6 7)))))

Make a Story
============

Load 1/b/boot.lisp into lisp and run (!generate1). To understand what is going on here, look at 1/b/grammars.lisp.

Write a new set of rules into 0/b/grammars called *grammar3* that describes different menus at Bits 'n Bites. No more than 5 rules. Using those rules, generate some meals.

Functional languages: Second-stage Lisp
---------------------------------------

Setup
=====

Perform the weekly set up instructions for project 1, homework c.

What to hand in
===============

Report (a) all the lisp functions you've written and (b) a file containing your deftests and (c) repl.txt coming from you saving the REPL showing these all running.

Exercise 1: Left symbols
========================

Write code to find the list of left-hand-side symbols in the rules

(deftest !lefties ()
	(test
		'(sentence noun-phrase verb-phrase ; you fill in the rest
		(lefties *grammar1*))))

Exercise 2: Right symbols
=========================

Write code to find the list of right-hand-side symbols in the rules

(deftest !righties ()
	(test
		'(Article Adj* Noun ; you fill in the rest
		(righties *grammar1*))))

Exercise 3 : Terminals
======================

Write a deftest that reports the terminals of a grammar (terminals are righties that are not lefties).

Exercise 4 : Lint
=================

Write a deftest showing code that reports lefties that are never righties (this is an error: exception, each grammar has one top-most start symbol. So we will say that the first lefty is the start symbol and exempt from this check).

Note that, to test this code, you'll have to invent a grammar that has these problems.

Functional languages: Story Generation
--------------------------------------

Setup
=====

Perform the weekly set up instructions for project 1, homework d.

What to hand in
===============

Report (a) all the lisp functions you've written and (b) a file containing your deftests for all parts of the following and (c) repl.txt coming from you saving the REPL showing these all running.

Exercise 1 : Write a Sci Story Generator (warning: slow)
========================================================

Convert the file 1/d/scifi.txt into a grammar.

Run your terminal and lint tools over the result and show that your grammar is looking good. Fix any errors you find.

Exercise 2 : Generate 10 Sci Story (easy)
=========================================

Write a deftest that generates 10 scifi stories.

Exercise 3: Caching Rewrites (hard)
===================================

The current grammar is stupid. Once it chooses a rewrite, then that rewrite is forgotten. So if it chooses  a Boy's name to be  John then it instantly forgets it and the next reference to Boy might be John or Pima.  For example, look at the mixed up sentences in the following:
(!generate2)

(
   (JOHN RUNS VERY VERY VERY QUICKLY SLOWLY WITH JOHN) ; ok
   (AJIT WALKS VERY VERY VERY VERY QUICKLY SLOWLY WITH JOHN) ; mixed up
   (JOHN WALKS VERY QUICKLY SLOWLY WITH AJIT) ; mixed up
   (JOHN WALKS QUICKLY SLOWLY WITH AJIT)      ; mixed up
   (JOHN RUNS QUICKLY SLOWLY WITH JOHN)       ; ok
   (AJIT WALKS QUICKLY SLOWLY WITH JOHN)      ; mixed up
   (AJIT RUNS QUICKLY SLOWLY WITH JOHN)       ; mixed up
)
This came from following grammar
(defparameter *grammar2*
	'((Sentence -> (Nounphrase Verbphrase))
	 (Nounphrase -> (Boy))
	 (Nounphrase -> (Girl))
	 (Boy -> john ajit)
	 (Girl -> pima barkha)
	 (Verbphrase -> (Verb Modlist Adverb with  Nounphrase))
	 (Verb -> runs  walks )
	 (Modlist ->  () (very Modlist))
	 (Adverb -> (quickly  slowly))))
Fix this. Rewrite 1/d/story.lisp such that for a set of pre-defined lefties (in our case Boy and Girl), once they are rewritten they always rewrite to the same thing. If you succeed then each generated sentence should never mix two boy or two girl names.

Test this caching version of 1/d/story.lisp on *grammar2*.

Project2: Objects
=================

In this project you will build an object-oriented language and use it to specialize the grammar of Project1.

The particular OO language used is documented in Graham's chapter on OO (grahamOO.pdf). This is a 100 lines of LISP (http://j.mp/gtxG3L) that implements methods, class, multiple inheritance, instance creation, etc etc. Since it is written in LISP, we also get garbage collection for free.

Specially, in this specialized grammar:

  * Productions have side-effects:

       * Whether or not a rewrite is cached is decided at the local production level.

       * Sounds are played as we enter some productions.

  * Productions read-write to a working memory of lists of lists.

  * Productions have pre-conditions that check for items in the working memory.

  * Productions have post-conditions that assert items to the working memory

OO languages: set up
--------------------

Setup
=====

Perform the weekly set up instructions for project 2, homework a.

What to hand in
===============

Report (a) all the lisp functions you've written and (b) a file containing your deftests for all parts of the following and (c) repl.txt coming from you saving the REPL showing the dance hall walking and running (defined below).

Exercise 1: RT*M
================

Read the user guide (http://www.csee.wvu.edu/~timm/cs310/cs310_6.html#GOLD) for GOLD.

IMPORTANT: for this week, you do NOT need to know the internal details of how GOLD is implemented (http://www.csee.wvu.edu/~timm/cs310/grahamOO.pdf). If you want, you can read that code (heh, its only a 100 lines). And we'll be walking through that implementation in class, later in the semester.

Exercise 2: Implement a dance hall
==================================

Let *Person* be a sub-class of *Object* with arms, feets, head, and an urge to dance and jump.

     Person                (has "dob", does "walk")
          Male             (does "jump")
               OldMale     (does "dance" by  calling jump twice)
               YoungMale   (does "dance" by calling jump 10 times)
          Female           (does "dance" and "jump")
     Note:  old men jump the same way young men do (just not as often).

The examples section of the user guide (http://www.csee.wvu.edu/~timm/cs310/cs310_6.html#GOLD) offers examples of how to (i) create a class, (ii) create an instance, (iii) define a method, and (iv) define an initialization method (don't worry about extending a super-class method: we'll get to that later). Write one deftest for (i,ii,iii,iv) showing that for *Person* you can code all that.

  * Define the classes and methods needed to code the dance hall (note that for "walking", "dancing'' and "jumping", just print "X am waking" "X am dancing!" and "X  am dancing!" where "X" is one of old man, young man, woman).

  * To show this working, create a list of 5 young men and 5 old men and 10 women. Run over the list, sending the message "walk" then "dance" to each item

OO languages: Death to If Statements
------------------------------------

Motivation
==========

In an OO system, control is a polymorphic thing. Messages are sent to different objects and what happens depends on the class of the receiver.

That is, in pure-OO, we never case on type. Rather, we are clever when creating our instances such that, at runtime, everyone knows how to handle themselves.

Usual Stuff
===========

Setup
-----

Perform the weekly set up instructions for project 2, homework b. If you find that you are missing any files, copy them over from 2/a.

CAUTION: do not cp 2/a/* as that may copy the magic .svn directory into 2/b (thus messing up your repo). Copy them over the old-fashioned way (e.g. cp ../a/gold.lisp .)  then svn add them.

What to hand in
---------------

Report:

  * All the lisp functions you've written;

  * The repl.txt coming from your REPL session where you run (main) (described below);

  * Your svn log showing all the commits generated as part of this week's homework.

  * A file containing your deftests for all parts of the following;

What deftests? you might ask. This code generates output. What can we deftest?

We'll if you really understand the following, you'll see lots of little tasks that require lots of little tests. When co-ordinating between team members, you divide up functionality, commit changes, then email your colleagues "hey, XYZ is working, see !thisTest". So deftest becomes your communication tool.

So I want you to show me that you actually have some team skills. I want to see at least one file per team member (with your name on it) and each file contains at least five deftests. And I want to see in the svn log statements like "hey guys! deftest XYZ is working- check it out", or "I found a bug in your deftest and wrote another deftest to show you where it crashes".

Our Class Hierarchy
===================

*object*
   *phrase* (does "act", has "$head")
      *rule* (does "register", has "$body")
      *terminal*
Note that:

  * For graduates of Mr. Morehead's 210 subject, this is the composite pattern.

  * The above list of methods and instance variables is incomplete. You have to work out what is missing.

Here, *rule*s and *terminal*s both have "$head"s but only *terminal*s have a "$body".

"Act" is different in *rule*s and *terminal*s:

  * For *rule* it recurses over the "$body" and calls recursively on the stuff found in the "$body". Note that, in this design, much of the functionality of   generate becomes methods inside *rule*.

  * For *terminal*, it just prints the head.

So the way this runs is that some clever function inputs the rules of your current grammars (a -> b c ) and outputs a hash table of *phrase* instances, indexed by their "$head" (don't know how to do hash-tables in LISP? see section 4.8 of Graham's text). This function returns the first phrase in the grammar.

Then, the message act is sent to the first rule in the grammar. After than, act rampages round the instances, recursing deeper and deeper into the structure.

What to do
==========

  * Implement the class hierarchy shown above

  * Move the generate functionality of homework one into the above classes.

  * Write the instance generation function described above. It will work something like this:
     ; warning: written, not tested
     (defun phrases->instances (all universe)
            (mapcar #'(lambda (one)
                            (phrase->instance one universe))
                      (cdr all))
            (phrase->instance (car all) universe))

     (defun main (all)
            (let* ((universe (make-hash-table))
                   (start    (phrases->instances all universe)))
              (act start universe)))

     (defun phrase->instance (rule universe)
        "returns an instance of class phrase"
        (let ((head (first rule))
              (body (cdr (cdr rule)))
              (phrase (inst *phrase*)))
          (setf (gethash head universe) phrase) ; store phrase
          ...; fill in phrase
          phrase ; return phrase
        ))

  * Test the above on a tiny grammar (two or three phrases). Make sure your grammar has "ands" and "or" in the body.

OO languages: Dramatic Chord
----------------------------

Motivation
==========

OO's systems should be very easy to customize.  Ideally, centralized controllers are verboten. If there are special cases, they need to be specializations in leaf classes.

So, this week, we'll try to specialize the processing you wrote to last year.

Usual Stuff
===========

Setup
-----

Perform the weekly set up instructions for project 2, homework c. If you find that you are missing any files, copy them over from 2/b.

CAUTION: do not cp 2/b/* as that may copy the magic .svn directory into 2/b (thus messing up your repo). Copy them over the old-fashioned way (e.g. cp ../a/gold.lisp .) then svn add them.

What to Hand In
---------------

Report:

  * All the lisp functions you've written;

  * The repl.txt coming from your REPL session where you run (main), this time with the "dramatic chords" you code below;

  * Your svn log showing all the commits generated as part of this week's homework;

  * A file containing your deftests for all parts of the following. At least five tests per team member spread out if files with member names.

Background
==========

Consider the following list of atoms in the sci fi grammar:

->                      Understand              extraGalactic
AndAre                  WantSomething           extraterestrial
AndTakeAFewAndLeave     WantWomen               fallsIntoSun
AndThen                 Which                   freezes
Attack                  WhichEtc                giant
Beings                  Whichetc                hungry
ButEtc                  aCrowdOfPeasants        invent
Catestrophe             aCuteLittleKidConvinces isAttackedBy
Catestrophes            aPriestTalksToThemOfGod isRescuedBy
Collision               almostEverybody         isStruckByAGiant
Denomument?             and                     killed
Denoument               andAre                  lookUponUsAsASourceOfNo
Denoument?              andAreNot               lunar
DenoumentOrHappyEnding  andIsDestroyed          martian
Dine                    andMagicallySaved       misunderstandUs
DoSomething             andTheyDie              not
Earth                   andTheyGetMarriedAndLiv radioactive
EndSadOrHappy           andTheyLeave            reptiles
Ending                  andTheyTurnIntoDisgusti scientists
Extraterestrial         areFriendly             soScientistsInventAWeap
Floater                 asteroid                soTheyEatUs
GoOn                    be                      soTheyKillUs
HappyEnding             blobs                   soTheyPutUsUnderABenign
Hungry                  bugs                    somePeople
IsStressed              burnsUp                 superbeings
Killer                  but                     the
Killers                 butIsSaved              theAirForce
PossibleMegaDeath       butIsSavedBy            theArmy
Rescued                 butMisunderstood        theAtomBomb
Resuced                 butTheyDieFromCatchingA theCoastGuard
Saved                   by                      theMarines
Science                 can                     theNavy
SeEtc                   cloud                   theyFallInLoveWithThisB
Sizes                   comet                   tiny
SoEtc                   dies                    understandUsAllTooWell
Some                    discover                us
SomeOne                 earth                   wantOurWomen,
SomeSaved               eat                     whichFails
Start                   enormous                whichKillsThem
TryToKill               everybody               whichTurnsThemIntoDisgu
UnderStand              everybodyDies           who
Note that if some of these atoms are used in any Hollywood blockbuster, there there will be  side-effects. For example:

  * whichTurnsThemIntoDisgustingLumps: there is an "ooohhh.... yuck" sound.

  * PossibleMegaDeath: "oh no!!! (screaming)".

  * butTheyDieFromCatchingACold "ah, tissue! (thud)".

  * aCuteLittleKidConvincesThemPeopleAreOk "Gee Mr alien, sometimes I get scared when I meet knew people too, like one time, when I went to a new school... I kinda peed my pants. But the teacher was real nice about it  and now I have fun there. So I'm sorry we blew up your breeding colony and killed 1,000,000,000 of your relatives and all the royal eggs but we're real sorry and if you gave us half a chance I'm sure we can be friends".

Your job is to code up those side-effects, in an object-oriented manner.

What to do
==========

  * Register a side-effect for 20 of the above atoms. Use LISP's property lists (which lets you assign something to a field of a symbol):
     (defun sidefx (sym fx)
            (setf (get sym 'fx) fx))
     ;e.g.
     (sidefx 'butTheyDieFromCatchingACold "ah, tissue! (thud)")
     (sidefx 'PossibleMegaDeath}: "oh no!!! (screaming)")
     Now you can check if a symbol has side effects;
     (defun sidefxp (sym)
            "if no sidefex, just return empty string"
            (or (get sym 'fx nil)
                ""))

  * Create sub-classes of *terminal* for *humble* and *loud* (the difference being that only *loud* instances hold the side effects).

  * Modify your phrase->instance function that generates either *loud* or *humble* instances. Yes, this code will need an "if" statement but "if"s outside of OO land are unavoidable.

  * Test the above on a tiny grammar (two or three phrases). Make sure your grammar has "ands" and "or" in the body.

OO languages: The Full story
----------------------------

This week, you will complete your OO story generation:

  * Add the cache functionality from 1/d

  * Code up the entire scifi grammar and generate a complete story.

Usual Stuff
===========

Setup
-----

Perform the weekly set up instructions for project 2, homework d If you find that you are missing any files, copy them over from 2/c.

CAUTION: do not cp 2/c/* as that may copy the magic .svn directory into 2/d (thus messing up your repo). Copy them over the old-fashioned way (e.g. cp ../c/gold.lisp .) then svn add them.

What to Hand In
---------------

Report:

  * All the lisp functions you've written;

  * The repl.txt coming from your REPL session where you run (main), this time with 10 samples of your sci fi stories with the "dramatic chords" you code below;

  * Your svn log showing all the commits generated as part of this week's homework;

  * A file containing your deftests for all parts of the following. At least five tests per team member spread out if files with member names.

What to do
==========

  * Add a "$cache" variable and a "$cachep" flag to *rule* such that if the phrase is referenced more than once, the first time you "act" to find the rewrite and add it to the "$cache". Subsequently, you just return the contents of "$cache".  Note that:

       * In project1, this special case meant changing some  global procedure. Here, the change is localized to a leaf class.

       * You're probably going to need one "if" statement in *rule* to hand this caching.

  * Using the 2/c code, add side-effects to a third of the atoms in the story.

  * Code up the entire scifi story as instances of sub-classes of *phrase*.

  * Generate 10 stories, at random, with caching and side effects.

  * (Optional) sell your masterpiece to Spielberg and cut your old lecturer in for his usual 10%.

Project3: Logic
===============

In this project you will work with three very similar versions of the same file. Standard mistake: editing the wrong file! Do not let it happen to you!

Logic languages: set up
-----------------------

Set Up
======

Perform the weekly set up instructions for project 3, homework a.

What to hand in
===============

A file answers.txt with answers to the following questions.

 1. What does this return: (match '?x 1 nil)?

 2. The function data1 includes a predicate sameSex that matches to two persons. Except for gender, every other field has a suffix that is either "1" or "2". Does gender need a suffix? Why or why not?

 3. Why does the match function return two values?

 4. Give an example of the kind of structure that would satisfy var?.

 5. Give an example of the kind of structure that would not satisfy var?.

 6. Why does binding call itself recursively before it looks at the cdr of the current binding?

A revised form of 15.lisp with:

  * A deftest function that uses with-answer to return the sum of everyone's age.

  * A fix to the predicate hates (currently the !one function prints nothing).

Logic 101
---------

Set up
======

Perform the weekly set up instructions for project 3, homework b.

What to hand in
===============

A file answers.txt with answers to the following questions.

 1. Why does prove-simple use mapcan as the list mapping operator? Hint: "nil".

 2. The following functions all return lists of multiple bindings: prove-simple,  prove-and, prove-or, prove-not. Why don't we just return one binding?

 3. Given an example of "r" before and after it is processed by change-vars.

 4. The function prove-code evals a structure called code that creates a let statement which defines some vars (local variables) then calls some code expr. What is going on here?

A revised form of 15.lisp with:

  * Code for test ">" into the prove function. With that extension, you can have sub-goals in clauses that look like this: "(> ?age1 ?age2)". Hints:

       * use prove-code.

       * Add more entries to the top of the "case" statement in  prove. Remember to return (list binds).

       * If ">" is not true, just return nil.

  * A  deftext function that uses with-answer to find the oldest person amongst a group of people. Use the following logic:

       * The oldest person is the person for which not other person has an older age.

Logic languages: Second-stage
-----------------------------

Set up
======

Perform the weekly set up instructions for project 3, homework c.

What to hand in
===============

A file answers.txt with answers to the following questions.

 1. In 3/c/15.lisp, the data3 function defines an equality test in a funny way: (<- (= ?x ?x)). Is that a typo? Should not the second "?x" be different to the first? And should there be a body to the rule?

A revised version of 15.lisp that supports and the code in the younger predicate of data3:

  * More numeric comparisons: specifically "<";

  * Procedural attachment:  the command (do (print ?x)) replaces "?x" with its current binding and prints it.

  * Print statements: the command (say str args) is defined in 3/c/tricks.lisp and I want to be able to call say very simply from within my rules. For an example of that call, see the younger predicate of data3.

Note that if all the above works, then the !three deftest should now work.

Tips and Hints
**************

Slime short cuts
================

Slime selector
==============

C-c s calls the slime-selector function:
Select Methods:

4:     Select in other window
?:     Selector help buffer.
c:     SLIME connections buffer.
d:     *sldb* buffer for the current connection.
e:     most recently visited emacs-lisp-mode buffer.
i:     *inferior-lisp* buffer.
l:     most recently visited lisp-mode buffer.
n:     Cycle to the next Lisp connection.
q:     Abort.
r:     SLIME Read-Eval-Print-Loop.
t:     SLIME threads buffer.
v:     *slime-events* buffer.

(BTW, my favorite SLIME short-cut is C-c s r- which jumps me back to the SLIME repl.

Finding definitions
===================

M-.
     Edit the definition of the function called at point.

M-,
     Pop the definition stack to go back from a definition.

Programming aids
================

C-c TAB
     Complete the Lisp symbol at point. (Also M-TAB.)

C-c RET
     Macroexpand once.

C-c M-m
     Macroexpand all.

Cross-referencing
=================

C-c C-w c
     WHO-CALLS a function.

C-c C-w r
     WHO-REFERENCES a global variable.

C-c C-w s
     WHO-SETS a global variable.

C-c C-w b
     WHO-BINDS a global variable.

C-c C-w m
     WHO-MACROEXPANDS a macro.

C-M-.
     Goto the next reference source location. (Also C-c C-SPC)

Documentation commands
======================

C-c C-d
     Describe symbol.

C-c C-a
     Apropos search.

C-c M-d
     Disassemble a function.

Evaluation commands
===================

     C-M-x Evaluate top-level from containing point.

C-x C-e
     Evaluate sexp before point.

C-c C-p
     Evaluate sexp before point, pretty-print result.

Bibliography
************

A to F
======

stuff

G to M
======

stuff

 Menzies90

 Menzies90

N to T
======

stuff

U to Z
======

stuff