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.

0.1 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

1 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 (see 1, a)

   * Week 2: Grammars (see 1, a)

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

   * Week 5: Abstraction Mechanisms (see 1, a)

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

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

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

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

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

   * Week 13,14: special topics (see 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.

2 Lecture notes
***************

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

History of programming languages
--------------------------------

So many languages:

   * list of 2500 past and present
     (http://people.ku.edu/~nkinners/LangList/Extras/langlist.htm).

   * Rosetta stones:
        *  Very short (http://www.lurklurk.org/rosetta.html);

        * Extensive (http://rosettacode.org/wiki/Main_Page);

   * History From Fortran to the present day
     (http://www.levenez.com/lang/lang_a4.pdf).

   * See also Appendix A, Scott

   Why so many?

   Which language is best?

   (From LtU Classic Archives
(http://lambda-the-ultimate.org/classic/message4521.html))

   Does the controversial Sapir-Whorf Hypothesis or theory of
"linguistic relativity" that has been proposed for human languages hold
for programming languages and the programmers who use them?

   "Linguistic relativity" is the...

     "proposal that the particular language one speaks influences the
     way one thinks about reality"... According to the theory, "people
     who speak different languages perceive and think about the world
     quite differently"...

     "The Sapir-Whorf Hypothesis is the most famous. Benjamin Whorf's
     hypothesis had two interpretations, the first is called
     determinism ["people's thoughts are determined by the categories
     made available by their language"], and the second is labeled
     relativism ["differences among languages cause differences in the
     thought of their speakers"..... "

   Do the language features of the programming languages a programmer
uses as a computer science student determine the ideas that a
programmer is able to use and understand as a professional programmer?

   Kenneth E. Iverson, the originator of the APL programming language,
believed that the Sapir-Whorf hypothesis applied to computer languages
(without actually mentioning the hypothesis by name). His Turing award
lecture (http://elliscave.com/APL_J/tool.pdf), "Notation as a tool of
thought", was devoted to this theme, arguing that more powerful
notations aided thinking about computer algorithms. The essays of Paul
Graham (http://www.paulgraham.com/avg.html) explore similar themes,
such as a conceptual hierarchy of computer languages, with more
expressive and succinct languages at the top.

   I used to believe in Sapir-Whorf and wrote a lot about
domain-specific programming languages
(http://www.paulgraham.com/avg.html) where the language was tuned to
the idioms of the local experts. Years later, I have yet to see the
evidence that it is indeed a productive approach (indeed, other factors
may be far more important (http://menzies.us/index.php?news=7070)). For
example, if we ask the question "which language is fastest to run or
easiest to use?", we get contradictory answers. It turns out that
"fastest" and "easiest" are almost mutually exclusive (faster languages
are longer to write and vice versa):

(Data from benchmarks at the Great Language Shootout
(http://shootout.alioth.debian.org/u32/benchmark.php?test=all&lang=sbcl&lang2=python3)).

   Note the trade-off between lines of code of the function and its
runtime: halving the lines of code (from two KB to one) can increase the
runtimes by an order of magnitude, or more.

   Perhaps we should not ask what language is best. In terms of earning
a pay cheque, a more important question is "what language will someone
else pay me to use?".

   Depending on how you ask this question, you get different answers.
The TIOBE web site
(http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html) has
has its own magic indexes for comparing languages.

(The May'04 Java dip is due to a Google purge of suspect sites from its
web indexes. In response, TIOBE added other search engines to its
sampling.)

   Note that:

   * No language is in the majority

   * The "best" language (JAVA) only scores under 25% on their scale;

   * While the trend is not clear, one reading on the above plot is
     that the dominant three languages (JAVA, C++, C) are losing their
     dominance.
   The method used to generate the above ratings have been seriously
questioned
(http://blog.timbunce.org/2008/04/12/tiobe-or-not-tiobe-lies-damned-lies-and-statistics/).
We need not explore those issues here except to say that comparatively
assessing different languages is a very difficult (?impossible).

   Anyway, one thing is clear: on the balance of probabilities, you
will not be spending your professional life working on one language.
Rather, you will be using any number of languages during your career.
For example, here's a recent chat I had with someone working in a
Silicon Valley start-up:

     Today was spent refactoring some RUBY to provide a simple
     interface... was doing this yesterday too... luckily I was rescued
     by a PROLOG problem which came up... then back to RUBY and finally
     diverted by a problem which superfisherly (sic) looks like a
     PROLOG problem but is actually a C crap problem

   This is why this subject is important. Here, we try to teach general
principles that apply to multiply languages. Hopefully this means that,
in the future, you will be able to learn new languages, as required.

Brief survey of programming paradigms
-------------------------------------

Imperative:
   * Central features are variables, assignment statements, and
     iteration.

   * Include scripting/visual languages.

   * Examples: C, Java, Perl, JavaScript, Visual BASIC .NET, C++

   * Includes object-oriented languages:
        * uses "objects" and their interactions to design applications
          and computer programs.

        * Programming techniques may include features such as
          encapsulation, modularity, polymorphism, and inheritance.

        * Examples: RUBY, C++.

   Functional programming:

   * a programming paradigm that treats computation as the evaluation
     of mathematical functions and avoids state and mutable data.

   * It emphasizes the application of functions, in contrast with the
     imperative programming style which emphasizes changes in state.

   * Examples: Scheme, Ocaml, Haskell, LISP(ish).

   Logic programming:

   * Purely declarative representation language, and a theorem-prover
     or model-generator is used as the problem-solver.

   * The problem-solving task is split between the programmer, who is
     responsible only for ensuring the truth of programs expressed in
     logical form, and the theorem-prover or model-generator, which is
     responsible for solving problems efficiently.

   * Examples: PROLOG

   The projects of this subject are  divided up into the above
paradigms.

2.2 Grammars
============

Syntax
======

   * Syntax: the form or structure of the expressions, statements, and
     program units

   * Semantics: the meaning of the expressions, statements, and program
     units

   Definitions
   * A "sentence" is a string of characters over some alphabet

   * A "language" is a set of sentences

   * A "lexeme" is the lowest level syntactic unit of a language (e.g.,
     *, sum, begin)

   * A "token" is a category of lexemes (e.g., identifier)

   Context-Free Grammars
   * Developed by Noam Chomsky in the mid-1950s

   * Language generators, meant to describe the syntax of natural
     languages Define a class of languages called context-free languages

   Backus-Naur Form (1959)
   * Invented by John Backus to describe Algol 58

   * BNF is equivalent to context-free grammars

   Example:
<program> ==> <stmts>
  <stmts> ==> <stmt> | <stmt> ; <stmts>
   <stmt> ==> <var> = <expr>
   <var>  ==> a | b | c | d
   <expr> ==> <term> + <term> | <term> - <term>
   <term> ==> <var> | const
 Example derivation:
<program> => <stmts>  => <stmt>
                      => <var> = <expr>
                      => a = <expr>
                      => a = <term> + <term>
                      => a = <var> + <term>
                      => a = b + <term>
                      => a = b + cons

Regular Expressions/
====================

Specifies tokens. One of:

   *         A character

   * 	The empty string, denoted ε

   * 	Two regular expressions next to each other, meaning any
     string generated by the first one followed by (concatenated with)
           any string generated by the second one

   * 	Two regular expressions separated by a vertical bar (|),
      meaning any string generated by the first one or any string
       generated by the second one

   * 	 A regular expression followed by a star "*",          meaning
     the concatenation of zero or more strings          generated by
     the expression in front of the star

   *          A regular expression followed by "?" meaning the
     concatenation of zero or one of strings generated          by the
     expression in from of the "?"

   *          A regular expression followed by "+" meaning the
     concatenation of one or more of strings generated          by the
     expression in from of the "+"

   Parentheses are used to avoid ambiguity about where the various
sub-expressions start and end.

   Consider, for example, the syntax of numeric constants accepted by a
simple hand-held calculator:
<number>   => <integer> | <real>
<integer>  => <digit> <digit> *
<real>     => <integer> <exponent> | <decimal> ( <exponent> | ε )
<decimal>  => <digit> * ( . <digit> | <digit> . ) <digit> *
<exponent> => ( e | E ) ( + | - | ε ) <integer>
<digit>    => 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Finite State Automata
=====================

A regular expression can be viewed as a finite state  automota (FSA)
that recognizes (or generates) a valid sentence in a language.
   * An FSA may be either deterministic (DFSA or DFA) or
     non-deterministic (NFSA or NFA).

   * An FSA is deterministic if its behavior during recognition is
     fully determined by the state it is in and the symbol to be
     consumed.  I.e., given an input string, only one path may be taken
     through the FSA.

   * Conversely, an FSA is non-deterministic if, given an input string,
     more than one path may be taken through the FSA.  One type of
     non-determinism is e-transitions, i.e. transitions which consume
     the empty string (no symbols).

   FSAs can be represented as transitions between states

Parser generators build these state transition tables (so that
subsequent processing a programming language is very fast).

Parse tree
==========

A hierarchical representation of a derivation
                    <program>
                        |
                     <stmts>
                        |
                     <stmt>
                    /  |   \
                   /   |    \
                  /    |     \
              <var>   "="    <expr>
                |           /  |   \
              "a"     <term>  "+"   <term>
                        |             |
                      <var>         const
                        |
                       "b"
 A grammar is "ambiguous" if and only if it generates a sentential form
that has two or more distinct parse trees
   * Example: <expr> ==> <expr> <op> <expr>  |  const
     <op>   ==> /  |  -

   *                <expr>                      <expr>
                   /   \   \                   /   |    \
                  /     \   \                 /    |     \
     	  <expr>   <op>  <expr>    <expr>  <op>   <expr>
           /  |   \       \      |          |      |    |  \   \
          /   |    \       |     |          |      |    |   \    \
         /    |     \      |     |          |      |    |    \     \
     <expr> <op>  <expr>   |     |          |      |   <expr> <op> <expr>
       |      |     |      |     |          |      |      |     |     |
     const   "-"   const   "/"  const     const   "-"   const  "/"   const

   Fix: If we use the parse tree to indicate precedence levels of the
operators, we cannot have ambiguity
   * Example: <expr> ==> <expr> - <term>  |  <term>
     <term> ==> <term> / const| const

   *          <expr>
             /   |   \
        <expr>  "-"  <term>
           |         |  \  \
           |         |   \  \
           |         |    \  \
        <term>    <term> "/"  const
           |         |
        <const>   <const>
   Operator associativity can also be indicated by a grammar
<expr> ==> <expr> + <expr> |  const  (ambiguous)
<expr> ==> <expr> + const  |  const  (unambiguous
 Parse:
                 <expr>
                /  |   \
          <expr>  "+"   const
        /   |   \
  <expr>   "+"   const
     |
   const

Attributed Grammars
===================

Grammars  generate all properly formed expressions in some language
but says nothing about their meaning. To tie these expressions to
mathematical concepts  we need additional notation.

   The most common is based on attributes. In our expression grammar,
we can associate a val attribute with each E, T, F, and const in the
grammar.

   The intent is that for any symbol S, S.val will be the meaning, as
an arithmetic value, of the token string derived from S. We assume that
the val of a const is provided to us by the scanner.

   We must then invent a set of rules for each production, to specify
how the vals of different symbols are related. The resulting _attribute
grammar_ (AG) for a simple calculator is shown here:

Object Grammars
===============

Going one step further, the "Parse tree" is a nested set of objects. In
this design, each non-terminal is some instance of sub-class of
"Grammar". Once a language is parsed, an OO interpreter can execute the
parse tree, with each non-terminal handling the specific processing
associated with that node.

   For example, an if-test would create and instance of class "If" with
slots for "expr" and then "then" and "else" actions.
<if> => if <expr> then <action> else <action> fi
 To interpret this, the OO interpreter just sends the message "evaluate"
to this instance which, in turn, sends "evaluate" to "expr". If that
returns true, then the "then" action is messaged with "evaluate". Else,
we "evaluate" the "else".

2.3 Grammars Hacking: Example
=============================

Lex
===

C-based tool for building compilers.

   Generic approach to recongizing parts of an input stream, then
performing specific actions for certain sections.

   Guard action pairs. Guards defined  by regular expressions:
   * `x*' = zero or more

   * `x+' = one or more

   * `[abc]' =  "or". Anyone of "a" or "b" or "c"

   * `\n' = new line

   * `\t' = new line

%{
#include <stdlib.h>
#include "calc3.h"
#include "y.tab.h"
void yyerror(char *);
%}

%%

[a-z]       {
                yylval.sIndex = *yytext - 'a';
                return VARIABLE;
            }

0           {
                yylval.iValue = atoi(yytext);
                return INTEGER;
            }

[1-9][0-9]* {
                yylval.iValue = atoi(yytext);
                return INTEGER;
            }

[-()<>=+*/;{}.] {
                return *yytext;
             }

">="            return GE;
"<="            return LE;
"=="            return EQ;
"!="            return NE;
"while"         return WHILE;
"if"            return IF;
"else"          return ELSE;
"print"         return PRINT;

[ \t\n]+        ;       /* ignore whitespace */

.               yyerror("Unknown character");
%%
int yywrap(void) {
    return 1;
}

Gawk
====

Regular expression extensions:

   * `[^abc]' = negation. Not one of "a" or "b" or "c";

   * `^' = start of line;

   * `$' = end of line;

   * `.' = any character;

   * `\x' = escaped character. E.g. ""`\.'" is the period character,
     not any characer.

Gawk & Gender Recognition
-------------------------

Scott Pakin. Regular Expressions and Gender Guessing. In Computer
Language Magazine, 8(12):pp. 59-68, December 1991.

                                          { sex = "m" }  # Assume male.
/^.*[aeiy]$/                              { sex = "f" }  # Female names endng in a/e/i/y.
/^All?[iy]((ss?)|z)on$/                   { sex = "f" }  # Allison (and variations)
/^.*een$/                                 { sex = "f" }  # Cathleen, Eileen, Maureen,...
/^[^S].*r[rv]e?y?$/                       { sex = "m" }  # Barry, Larry, Perry,...
/^[^G].*v[ei]$/                           { sex = "m" }  # Clive, Dave, Steve,...
/^[^BD].*(b[iy]|y|via)nn?$/               { sex = "f" }  # Carolyn,Gwendolyn,Vivian,...
/^[^AJKLMNP][^o][^eit]*([glrsw]ey|lie)$/  { sex = "m" }  # Dewey, Stanley, Wesley,...
/^[^GKSW].*(th|lv)(e[rt])?$/              { sex = "f" }  # Heather, Ruth, Velvet,...
/^[CGJWZ][^o][^dnt]*y$/                   { sex = "m" }  # Gregory, Jeremy, Zachary,...
/^.*[Rlr][abo]y$/                         { sex = "m" }  # Leroy, Murray, Roy,...
/^[AEHJL].*il.*$/                         { sex = "f" }  # Abigail, Jill, Lillian,...
/^.*[Jj](o|o?[ae]a?n.*)$/                 { sex = "f" }  # Janet, Jennifer, Joan,...
/^.*[GRguw][ae]y?ne$/                     { sex = "m" }  # Duane, Eugene, Rene,...
/^[FLM].*ur(.*[^eotuy])?$/                { sex = "f" }  # Fleur, Lauren, Muriel,...
/^[CLMQTV].*[^dl][in]c.*[ey]$/            { sex = "m" }  # Lance, Quincy, Vince,...
/^M[aei]r[^tv].*([^cklnos]|([^o]n))$/     { sex = "f" }  # Margaret, Marylou, Miriam,...
/^.*[ay][dl]e$/                           { sex = "m" }  # Clyde, Kyle, Pascale,...
/^[^o]*ke$/                               { sex = "m" }  # Blake, Luke, Mike,...
/^[CKS]h?(ar[^lst]|ry).+$/                { sex = "f" }  # Carol, Karen, Sharon,...
/^[PR]e?a([^dfju]|qu)*[lm]$/              { sex = "f" }  # Pam, Pearl, Rachel,...
/^.*[Aa]nn.*$/                            { sex = "f" }  # Annacarol, Leann, Ruthann,...
/^.*[^cio]ag?h$/                          { sex = "f" }  # Deborah, Leah, Sarah,...
/^[^EK].*[grsz]h?an(ces)?$/               { sex = "f" }  # Frances, Megan, Susan,...
/^[^P]*([Hh]e|[Ee][lt])[^s]*[ey].*[^t]$/  { sex = "f" }  # Ethel, Helen, Gretchen,...
/^[^EL].*o(rg?|sh?)?(e|ua)$/              { sex = "m" }  # George, Joshua, Theodore,..
/^[DP][eo]?[lr].*se$/                     { sex = "f" }  # Delores, Doris, Precious,...
/^[^JPSWZ].*[denor]n.*y$/                 { sex = "m" }  # Anthony, Henry, Rodney,...
/^K[^v]*i.*[mns]$/                        { sex = "f" }  # Karin, Kim, Kristin,...
/^Br[aou][cd].*[ey]$/                     { sex = "m" }  # Bradley, Brady, Bruce,...
/^[ACGK].*[deinx][^aor]s$/                { sex = "f" }  # Agnes, Alexis, Glynis,...
/^[ILW][aeg][^ir]*e$/                     { sex = "m" }  # Ignace, Lee, Wallace,...
/^[^AGW][iu][gl].*[drt]$/                 { sex = "f" }  # Juliet, Mildred, Millicent,...
/^[ABEIUY][euz]?[blr][aeiy]$/             { sex = "m" }  # Ari, Bela, Ira,...
/^[EGILP][^eu]*i[ds]$/                    { sex = "f" }  # Iris, Lois, Phyllis,...
/^[ART][^r]*[dhn]e?y$/                    { sex = "m" }  # Randy, Timothy, Tony,...
/^[BHL].*i.*[rtxz]$/                      { sex = "f" }  # Beatriz, Bridget, Harriet,...
/^.*oi?[mn]e$/                            { sex = "m" }  # Antoine, Jerome, Tyrone,...
/^D.*[mnw].*[iy]$/                        { sex = "m" }  # Danny, Demetri, Dondi,...
/^[^BG](e[rst]|ha)[^il]*e$/               { sex = "m" }  # Pete, Serge, Shane,...
/^[ADFGIM][^r]*([bg]e[lr]|il|wn)$/        { sex = "f" }  # Angel, Gail, Isabel,...
                                          { print sex }  # Output prediction

Gawk & Domain-Specific Language
-------------------------------

Input langauge
label here's some stuff
bottom ticks 1 5 10
left ticks 1 2 10 20
range 1 1 10 22
height 10
width 30
1 2 *
2 4 *
3 6 *
4 8 *
7 14 +
8 12 +
9 10 +
mb 0.9 11 =
 Output example:
      |----------------------|
20    -                 = =  =
      |       = =  = =       |
      =  = =         +  +    |
10    -                   +  |
      |    *  *              |
      |  *                   |
2     *---------|------------|
     1         5            10
         here's some stuff

   The code is here (http://awk.info/?dsl/graph). Note the use of guard
action pairs, where the guards are regular expressions.

Fast and Slow Regular Expression Processing
===========================================

(From a page by Russ Cox (http://swtch.com/~rsc/regexp/regexp1.html).)

   Strange to say, many modern languages use a simplistic recursive
descent test for regular expressions.
   * Dumb way (Ruby, Python, Perl): if one pattern fails, then the
     processor goes all the way back to the start of the pattern.

   * Smarter way (Awk): parallel traversal of all pathways

e.g. Lets build two finate state automoa for the patterhn `abab|abbb'
and run it the string `abbb'.

   First, the dumb way:

A more efficient but more complicated way to simulate perfect guessing
is to guess both options simultaneously. In this approach, the
simulation allows the machine to be in multiple states at once. To
process each letter, it advances all the states along all the arrows
that match the letter.

Note that this second way was first implemented by Ken Thompson
introduced the multiple-state simulation approach in his 1968 paper.
The full source code (http://swtch.com/~rsc/regexp/) (under 400 lines)
and the benchmarking scripts are available online

   Thompson introduced his regualr expression to programmers in his
implementation of the text editor QED for CTSS. Dennis Ritchie followed
suit in his own implementation of QED, for GE-TSS. Thompson and Ritchie
would go on to create Unix, and they brought regular expressions with
them. By the late 1970s, regular expressions were a key feature of the
Unix landscape, in tools such as ed, sed, grep, egrep, awk, and lex.

Welcome to the 21st Century
===========================

Remember that OCaml language? That was strongly typed (at compile time,
you know if a variable is a string, number, whatever) and supported
type inferencing (so you can check if you are doing dumb things like
adding a number to a string).

   Well, OCaml supports recursive type definitions?  So that OCaml's
_type_s are a grammar.
type paragraph =
    Normal of par_text
  | Pre of string * string option
  | Heading of int * par_text
  | Quote of paragraph list
  | Ulist of paragraph list * paragraph list list
  | Olist of paragraph list * paragraph list list

and par_text = text list

and text =
    Text of string
  | Emph of string
  | Bold of string
  | Struck of par_text
  | Code of string
  | Link of href
  | Anchor of string
  | Image of img_ref

and href = { href_target : string; href_desc : string; }

and img_ref = { img_src : string; img_alt : string; }

   The Ulist and Olist constructors take the first item followed by a
(possible empty) list of items, to prevent empty lists -- this way,
there's at least one element.

   So eigenclass.org
(http://eigenclass.org/R2/writings/fast-extensible-simplified-markdown-in-ocaml)
uses the above to define a cool generator for HTML pages using a set of
short-cuts:

   * any character can be escaped with \,

   * emphasis is done with __ (less prone to accidental use than _) and
     bold text with *,

   * typographical abuses like bold emphasized text are not allowed,

   * headers are done with !level1 header, !!level2 header, etc.,

   * the # character is thus free and can be used for numbered lists,
     replacing 1.,

   * pre-formatted code is done with {{
       whatever
     }}

   * it is possible to extend the markup with custom processors, using
     `{{extension-name' blocks; for instance, raw HTML is inserted with {{html
       <b> whatever </b>
     }}
      (before you try to inject arbitrary HTML in the comments: this
     extension is only enabled in the main text).
   The above grammar is the core of a parser that generates HTML. And,
interestingly, in this ultra-high level language, this parse runs very
very fast.
                                      runtimes                       memory
                                      -----------------------------  -------------
                          LoCs        README.1  README.8  README.32  README.32 MEM
discount         C        ~4500                 0.016s    0.063s     2.8MB
Bluecloth        Ruby     1100        0.130s    2.16s     30s        31MB
markdown         Perl     1400        0.068s    0.66s     segfault   segfault
python-markdown  Python   1900        0.090s    0.35s     2.06s      23MB
Pandoc           Haskell   900 + 450  0.068s    0.55s     2.7s       25MB
----------------------------------------------------------------------------------
Simple_markup    OCaml    313 + 55              0.012s    0.043s     3.5MB
 So, in the 21st century, you can have you cake and eat it too:
   *  High-level descriptions.

   * Tiny code.

   * Fast runtimes.

Summary
=======

   * Regular expressions are cool!!

   * Regular expressions are a core technology in defining new
     languages.

   * Regular expression processing (can be) very fast.

   * Regular expressions have a mathematical structure- which is
     exploited by modern languuages.

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

Rule-based programming (rules.pdf)

   Example rule-base (usedcar_clips.txt).

2.5 Functional Languages and Lisp
=================================

Sources (and further reading):
   * Scott, chapter 10

   * http://www.ocaml-tutorial.org/functional_programming

   * Paul Graham's article: The Roots of Lisp
     (http://unbox.org/wisp/var/timm/10/310/share/pdf/graham02.pdf)

   * Tutorial on LISP: 1
     (http://cs.gmu.edu/~sean/lisp/LispTutorial.html) and 2
     (http://cs.gmu.edu/~sean/lisp/LispTutorial2.html) and 3
     (http://cs.gmu.edu/~sean/lisp/LispTutorial3.html).

Wht is a Functional Language?
=============================

A functional program consists of an expression E (representing both the
algorithm and the input). This expression E is subject to some rewrite
rules.

   Reduction consists of replacing some part P of E by another
expression P' according to the given rewrite rules. ... This process of
reduction will be repeated until the resulting expression has no more
parts that can be rewritten.

   The expression E* thus obtained is called the normal form of E and
constitutes the output of the functional program -H. P. Barendregt

   Functional programming is characterized by the programming with
values, functions and functional forms.

   Keywords and phrases: Lambda calculus, free and bound variables,
scope, environment, functional programming, combinatorial logic,
recursive functions, functional, curried function.

   Functional programming languages are the result of both abstracting
and generalizing the data type of maps. Recall, the mapping m from each
element x of S (called the domain) to the corresponding element m(x) of
T (called the range) is written as:
m : S --> T

   For example, the squaring function is a function of type:
sqr : Num --> Num
 and may be defined as:
sqr where x |--> x*x
 A linear function f of type
f : Num --> Num
 may be defined as:
f where x |--> 3*x + 4

   Functional programming is based on the mathematical concept of a
function and functional programming languages include the following:

   * A set of primitive functions.

   * A set of functional forms.

   * The application operation.

   * A set of data objects and associated functions.

   * A mechanism for binding a name to a function.

   LISP, FP, Scheme, ML, Miranda and Haskell are just some of the
languages to implement this elegant computational paradigm.

   The basic concepts of functional programming originated with LISP.

Why Bother?
===========

Functional programming languages are important for the following
reasons.

   * Functional programming dispenses with the assignment command
     freeing the programmer from the rigidly sequential mode of thought
     required with the assignment command.

   * Functional programming encourages thinking at higher levels of
     abstraction by providing higher-order functions - functions that
     modify and combine existing programs.

   * Functional programming has natural implementation in concurrent
     programming.

   * Functional programming has important application areas. Artificial
     intelligence programming is done in functional programming
     languages and the AI techniques migrate to real-world applications.

   * Functional programming is useful for developing executable
     specifications and prototype implementations.

   * Functional programming has a close relationship to computer
     science theory. Functional programming is based on the
     lambda-calculus which in turn provides a framework for studying
     decidability questions of programming. The essence of denotational
     semantics is the translation of conventional programs into
     equivalent functional programs.

What is functional programming good for?
========================================

Functional programming, like any good programming technique, is a useful
tool in your armoury for solving some classes of problems. It's very
good for callbacks, which have multiple uses from GUIs through to
event-driven loops. It's great for expressing generic algorithms.
`List.map' is really a generic algorithm for applying functions over
any type of list. Similarly you can define generic functions over
trees. Certain types of numerical problems can be solved more quickly
with functional programming (for example, numerically calculating the
derivative of a mathematical function).

Pure and impure functional programming
--------------------------------------

A pure function is one without any side-effects. A side-effect really
means that the function keeps some sort of hidden state inside it.
`strlen' is a good example of a pure function in C. If you call
`strlen' with the same string, it always returns the same length. The
output of `strlen' (the length) only depends on the inputs (the string)
and nothing else. Many functions in C are, unfortunately, impure. For
example, malloc - if you call it with the same number, it certainly
won't return the same pointer to you. malloc, of course, relies on a
huge amount of hidden internal state (objects allocated on the heap,
the allocation method in use, grabbing pages from the operating system,
etc.).

   ML-derived languages like OCaml are "mostly pure". They allow
side-effects through things like references and arrays, but by and
large most of the code you'll write will be pure functional because
they encourage this thinking. Haskell, another functional language, is
pure functional. OCaml is therefore more practical because writing
impure functions is sometimes useful.

   There are various theoretical advantages of having pure functions.
One advantage is that if a function is pure, then if it is called
several times with the same arguments, the compiler only needs to
actually call the function once. A good example in C is:

for (i = 0; i < @code{strlen} (s); ++i)
  {
    // Do something which doesn't affect s.
  }

   If naively compiled, this loop is O(n^2) because `strlen' (s) is
called each time and `strlen' needs to iterate over the whole of s. If
the compiler is smart enough to work out that `strlen' is pure
functional and that s is not updated in the loop, then it can remove
the redundant extra calls to `strlen' and make the loop O(n). Do
compilers really do this? In the case of `strlen' yes, in other cases,
probably not.

Lisp
====

In 1960, John McCarthy published a remarkable paper: "Recursive
Functions of Symbolic Expressions and Their Computation by Machine Part
I" Communications of the ACM 3:4 April 1960 pp184-195

   In this paper, he did for programming something like what Euclid did
for geometry. He showed how, given a handful of simple operators and a
notation for functions, you can build a whole programming language. He
called this language Lisp, for "List Processing," because one of his key
ideas was to use a simple data structure called a list for both code and
data.

   It's worth understanding what McCarthy discovered, not just as a
landmark in the history of computers, but as a model for what
programming is tending to become in our own time. It seems to me that
there have been two really clean, consistent models of programming so
far: the C model and the Lisp model. These two seem points of high
ground, with swampy lowlands between them. As computers have grown more
powerful, the new languages being developed have been moving steadily
toward the Lisp model. A popular recipe for new programming languages in
the past 20 years has been to take the C model of computing and add to
it, piecemeal, parts taken from the Lisp model, like runtime typing and
garbage collection.

Sample LISP program:
--------------------

(defun fib (n)
    (if (<  n 2  )
        1
        (+ (fib (- n 1))
           (fib (- n 2))))))
(fib 20)

Note that define is setting the vale "fib" to be a list whose first
item is "lambda". This is the internal representation of LISP code.

Atoms and Lists
---------------

Lisp evaluates expressions, which can be simple (atoms) or compound
(lists).

   An atom is a string of characters, which can be letters, digits, and
most punctuation; the characters may -not- include spaces, quotes,
parentheses, brackets, '.', '#', or ';' (the comment character). In
this Lisp, case is significant ( X is different from x ).

   * Atoms: atom 42 1/137 + ok? hey:names-with-dashes-are-easy-to-read

   * Not atoms: don't-include-quotes (or spaces or parentheses)

   A list is a '(', followed by zero or more objects (each of which is
an atom or a list), followed by a ')'.

   * Lists: () (a list of atoms) ((a list) of atoms (and lists))

   * Not lists: ) ((()) (two) (lists)

   The special object nil is both an atom and the empty list. That is,
nil = (). A non-nil list is called a -pair-, because it is represented
by a pair of pointers, one to the first element of the list (its
-car-), and one to the rest of the list (its -cdr-). For example, the
car of ((a list) of stuff) is (a list), and the cdr is (of stuff). For
another example, the list (42 69 613) looks like this:

(Geek detail: It's also possible to have a pair whose cdr is not a
list; the pair with car A and cdr B is printed as (A . B).)

Lambda
------

A function is expressed as (lambda (p1 ... pn) e) where "p" is an atom
(called parameters) and "e" is an expressions. An expression whose
first element is such an expression

((lambda (p1 ... pn) e) a1... an)
 is called a function call and its value is computed as follows. Each
expression "a" is evaluated. Then "e" is evaluated. During the
evaluation of "e" the value of any occurrence of one of the "pi" is the
value of the corresponding "ai" in the most recent function call. For
example:
> ((lambda (x) (cons x '(b))) 'a)
(a b)

> ((lambda (x y) (cons x (cdr y)))
    'z
     '(a b c))
(z b c)
 There is another notation for functions that enables the function to
refer to itself, thereby giving us a convenient way to define recursive
functions. The notation
(label f (lambda (p1 .. pn) e))
 denotes a function that behaves like (lambda (p1 .. pn) e), with the
additional property that an occurrence of "f" within e will evaluate to
the label expression as if f were a parameter of the function.

   For example, suppose we want to define a function (subst x y z)
which takes an expression "x" an atom "y" and a list "z" and returns a
list like "z" but with each instance of "y" at any depth of nesting in
"z" replaced by "x".
>
(subst 'm 'b '(a b (a b c) d))
(a m (a m c) d)
 We can denote this function as
(label subst (lambda (x y z)
				(cond ((atom z)
				       (cond ((eq z y) x)
			                 ('t z)))
                      ('t (cons (subst x y (car z))
                                (subst x y (cdr z)))))))
 We will abbreviate `f = (label f (lambda (p1 ... pn pn) e))' as
(defun f (p1 ... pn) e)
 so

(defun subst (x y z)
   (cond ((atom z)
          (cond ((eq z y) x)
                ('t z)))
         ('t (cons (subst x y (car z))
                   (subst x y (cdr z)))))))

Interpretation
--------------

That's the syntax of programs and data. Now let's consider their
meaning. You can use Lisp like a calculator: type in an expression, and
Lisp prints its value. If you type 25, it prints 25. If you type (+ 2
2), it prints 4. In general, Lisp the LISP VM translates a particular
expression in a particular environment (set of variable bindings) by the
following algorithm (in the following, some of the details of the
operator names are specific to a particular Lisp interpreter called
awklisp- but their operations are the same in all Lisps):

   * If the expression is a number, return that number.

   * If the expression is a non-numeric atom (a -symbol-), return the
     value of that symbol in the current environment. If the symbol is
     currently unbound, that's an error.

   * Otherwise the expression is a list.
        * If its car is one of the symbols: quote, lambda, if, begin,
          while, set!, or define, then the expression is a -special-
          -form-, handled by special rules (discussed below):

        * Otherwise it's just a procedure call, handled as below.

   Here are the evaluation rules for procedure calls:

   * Evaluate each element of the list in the current environment, and
     then apply the operator (the value of the car) to the operands
     (the values of the rest of the list's elements). For example, to
     evaluate (+ 2 3), we
        * First evaluate each of its subexpressions:
             * The value of + is (at least in the initial environment)
               the primitive procedure that adds numbers
                  * Note: that value can change as we move into other
                    environments.

                  * So, in LISP, you can re-define "+", if you want to.

             * the value of 2 is 2,

             * the value of 3 is 3.

        * Then we call the addition procedure with 2 and 3 as
          arguments, yielding 5.
     For another example, take (- (+ 2 3) 1):
        * Evaluating each subexpression gives the subtraction
          procedure, 5, and 1.

        * Applying the procedure to the arguments gives 4.

   * A user-defined procedure is represented as a list of the form
     (lambda <parameters> <body>), such as (lambda (x) (+ x 1)). To
     apply such a procedure:
        * Evaluate its body in the environment obtained by extending
          the current environment so that the parameters are bound to
          the corresponding arguments. Thus, to apply the above
          procedure to the argument 41:
             * evaluate (+ x 1) in the same environment as the current
               one except that x is bound to 41.

        * If the procedure's body has more than one expression - e.g.,
          (lambda () (write 'Hello) (write 'world!)) - evaluate them
          each in turn, and return the value of the last one.

   We still need the rules for special forms. They are:
   * The value of (quote <x>) is <x>. There's a shorthand for this
     form: '. E.g., the value of '(+ 2 2) is (+ 2 2), -not- 4.

   * (lambda <parameters> ) returns itself: e.g., the value of (lambda
     (x) x) is (lambda (x) x).

   * To evaluate (if <test-expr> <then-exp> <else-exp>):
        * first evaluate <test-expr>. If the value is true (non-nil),
          then return the value of <then-exp>.

        * Otherwise return the value of <else-exp>.

        * (<else-exp> is optional; if it's left out, pretend there's a
          nil there.) Example: (if nil 'yes 'no) returns no.

   * To evaluate (progn <expr-1> <expr-2>...):
        * evaluate each of the subexpressions in order

        * returning the value of the last one.

   * To evaluate (while <test> <expr-1> <expr-2>...):
        * first evaluate <test>. If it's nil, return nil.

        * Otherwise, evaluate <expr-1>, <expr-2>,... in order,

        * and then repeat.

   * To evaluate (setf <variable> <expr>):
        * Evaluate <expr>, and then set the value of <variable> in the
          current environment to the result.

        * If the variable is currently unbound, that's an error. The
          value of the whole set! expression is the value of <expr>.

   It's possible to define other special forms. Common special forms
are:
   * (let ((<var> <expr>)...)
       <body>...)
      Bind each <var> to its corresponding <expr> (evaluated in the
     current environment), and evaluate <body> in the resulting
     environment.

   * (cond (<test-expr> <result-expr>...)... (else <result-expr>...))
      where the final else clause is optional. Evaluate each
     <test-expr> in turn, and for the first non-nil result, evaluate
     its <result-expr>. If none are non-nil, and there's no else
     clause, return nil.

   * (and <expr>...)
     @end vertbatim
     Evaluate each <expr> in order, until one returns nil; then return nil. If none are nil, return the value of the last <expr>.
     @item
     @verbatim
     (or <expr>...)
      Evaluate each <expr> in order, until one returns non-nil; return
     that value. If all are nil, return nil.

Lisp in Lisp
------------

Here's the original 1960 LISP interpreter, written in LISP.
; The Lisp defined in McCarthy's 1960 paper, translated into CL.
; Assumes only quote, atom, eq, cons, car, cdr, cond.
; Bug reports to lispcode@paulgraham.com.

(defun null. (x)
  (eq x '()))

(defun and. (x y)
  (cond (x (cond (y 't) ('t '())))
        ('t '())))

(defun not. (x)
  (cond (x '())
        ('t 't)))

(defun append. (x y)
  (cond ((null. x) y)
        ('t (cons (car x) (append. (cdr x) y)))))

(defun list. (x y)
  (cons x (cons y '())))
 These next couple are going to take a little explaining.

   `(pair x y)' takes two lists of the same length and returns a list
of two-element lists containing successive pairs of an element from
each.
(defun pair. (x y)
  (cond ((and. (null. x) (null. y)) '())
        ((and. (not. (atom x)) (not. (atom y)))
         (cons (list. (car x) (car y))
               (pair. (cdr x) (cdr y))))))
 `(assoc x y)' takes an atom x and a list y of the form created by
pair.. and returns the second element of the first list in y whose
first element is x.
(defun assoc. (x y)
  (cond ((eq (caar y) x) (cadar y))
        ('t (assoc. x (cdr y)))))
 This next one is needed to evaluate cond statements It works its way
through the cluases recursively, looking for the one in which the first
element returns "t" (the it returns the value of the second element).
(defun evcon. (c a)
  "eval (cond ((a b) (c d) ...))"
  (cond ((eval. (caar c) a)
         (eval. (cadar c) a))
        ('t (evcon. (cdr c) a))))
 There is a lot of nested list accessing in the above. In summary:
(caar x)        = (car (car x))
(cdar x)        = (cdr (car x))
(cadar x)       = (car (cdr (car x)))
(caddr x)       = (car (cdr (cdr x)))
(caddar x)      = (car (cdr (cdr (car x))))
 So much for the primitives. Here's the main engine. It takes two
arguments: "e" is the expression to be evaluated and "a" are the atoms
known in the current envrionment; (and was generated by the pair.
function). All the variables and all the pre-defined functions are
stored in that second argument.
(defun eval. (e a)
  (cond
    ((atom e) (assoc. e a))
    ((atom (car e))
     (cond
       ((eq (car e) 'quote) (cadr e))
       ((eq (car e) 'atom)  (atom   (eval. (cadr e) a)))
       ((eq (car e) 'eq)    (eq     (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'car)   (car    (eval. (cadr e) a)))
       ((eq (car e) 'cdr)   (cdr    (eval. (cadr e) a)))
       ((eq (car e) 'cons)  (cons   (eval. (cadr e) a)
                                    (eval. (caddr e) a)))
       ((eq (car e) 'cond)  (evcon. (cdr e) a))
       ('t (eval. (cons (assoc. (car e) a)
                        (cdr e))
                  a))))
    ((eq (caar e) 'label)
     (eval. (cons (caddar e) (cdr e))
            (cons (list. (cadar e) (car e)) a)))
    ((eq (caar e) 'lambda)
     (eval. (caddar e)
            (append. (pair. (cadar e) (evlis. (cdr e) a))
                     a)))))

(defun evlis. (m a)
  (cond ((null. m) '())
        ('t (cons (eval.  (car m) a)
                  (evlis. (cdr m) a)))))
 The most complex part of the above is the lambda call. So
(eval.  '(f '(b c))
        '((f (lambda (x) (cons 'a x)))))
 turns into
(eval. '((lambda (x) (cons 'a x)) '(b c))
        '((f lambda (x) (cons 'a x))))
 which returns (a b c).

But What Does it All Mean?
--------------------------

Now that we understand how eval works, let's step back and consider
what it means. What we have here is a remarkably elegant model of
computation. Using just quote, atom, eq, car, cdr, cons, and cond, we
can define a function eval, that actually implements our language, and
then using that we can define any additional function we want.

   There were already models of computation, of course- most notably
the Turing Machine. But Turing Machine programs are not very edifying
to read. If you want a language for describing algorithms. you might
want something more abstract. and that was one of McCarthy's aims in
defining Lisp.

   The language he defined in 1960 was missing a lot. It has no
side-effects, no sequential execution (which is useful only with side
effects anyway), no practical numbers, and dynamic scope. But these
limitations can be remedied with surprisingly little additional code.
Steele and Sussman show how to do it in a famous paper:
   * Guy Lewis Steele, Jr. and Gerald Jay Sussman. The Art of the
     Interpreter of, the Modularity Complex (Parts Zero, One, and Two).
     MIT AI Lab. AI Lab Memo AIM-453. May 1978.
   If you understand McCarthy's eval, you understand more than just a
stage in the history of languages. These ideas are still the semantic
core of Lisp today. So studying McCarthy's original paper shows us, in
a sense, what Lisp really is. It's not something that McCarthy designed
so much as something he discovered. It's not intrinsically a language
for AI or for rapid prototyping, or any other task at that level. It's
what you get (or one thing you get) when you try to axiomatize
computation.

   Over time, the median language, meaning the language used by the
median programmer, has grown consistently closer to Lisp. So by
understanding eval you're understanding what will probably be the main
model of computation well into the future.

   But we don't need to look too closely at the magic of all this. The
main point is that here that functional languages like LISP are a
natural tool for defining simple, yet incredibly powerful, recursive
explorers of nested structures.

Other Functional Languages
==========================

Scheme
------

Scheme, a descendent of LISP, is based on the lambda-calculus. Although
it has imperative features, in this section we ignore those features
and concentrate on the lambda-calculus like features of Scheme. Scheme
has two kinds of objects, atoms and lists. Atoms are represented by
strings of non-blank characters. A list is represented by a sequence of
atoms or lists separated by blanks and enclosed in parentheses.
Functions in Scheme are also represented by lists. This facilitates the
creation of functions which create other functions. A function can be
created by another function and then the function applied to a list of
arguments. This is an important feature of languages for AI
applications.

Syntax
......

Expressions are atoms which are variables or constants, lists of
arbitrary length (which are also function applications),
lambda-abstractions of one or more parameters, and other built-in
functions.

   Scheme provides a number of built in functions among which are +, -,
*, /, <, <=, =, >=, >, and not. Scheme provides for conditional
expressions of the form (if E0 E1 E2) and (if E0 E1). Among the
constants provided in Scheme are numbers, #f and the empty list () both
of which count as false, and #t and any thing other than #f and ()
which count as true. nil is also used to represent the empty list.

Definitions
...........

Scheme implements definitions with the `define' keyword.

Lists with nil, cons, car and cdr
.................................

The list is the basic data structure with nil repesenting the empty
list. Among the built in functions for list manipulation provided in
Scheme are cons for attaching an element to the head of a list, car for
extracting the first element of a list, and cdr which returns a list
minus its first element. The following code contains an example of
stack operations writtem in Scheme. The code illustrates definitions,
the conditional expression, the list predicate null? for testing
whether a list is empty, and the list manipulation functions cons, car,
and cdr.

( define empty_stack
   ( lambda ( stack ) ( if ( null? stack ) \#t \#f )))

( define push
   ( lambda ( element stack ) ( cons element stack ) ))

(define pop
   ( lambda ( element stack ) ( cdr stack )))

(define top
   ( lambda ( stack ) ( car stack )))

OCaml
-----

LISP and Scheme are "old school". There is much more modern interest in
F#, Haskell, and OCaml. Here's a OCaml example example:

# let double x =
    x * 2
  in
  List.map double [ 1; 2; 3 ];;
- : int list = [2; 4; 6]

   The function double takes an argument x and returns x * 2. Then map
calls double on each element of the given list ([1; 2; 3]) to produce
the result: a list with each number doubled.

   map is known as a higher-order function (HOF). Higher-order
functions are just a fancy way of saying that the function takes a
function as one of its arguments. The same thing in LISP would be:
(defun doubler ()
	#'(lambda (x) (* x 2)))

(mapcar (doubler) '(1 2 3))

==>
(2 4 6)

   If you're familiar with C/C++ then this looks like passing a
function pointer around. Java has some sort of abomination called an
anonymous class which is like a dumbed-down, slow and long-winded
closure. If you know Perl then you probably already know and use Perl's
closures and Perl's map function, which is exactly what we're talking
about. The fact is that Perl is actually quite a good functional
language.

   *Closures* are functions which carry around some of the
"environment" in which they were defined. In particular, a closure can
reference variables which were available at the point of its
definition. Let's generalise the function above so that now we can take
any list of integers and multiply each element by an arbitrary value n:

let multiply n list =
  let f x =
    n * x
  in
  List.map f list
  ;;

   Hence:
# multiply 2 [1; 2; 3];;
- : int list = [2; 4; 6]
# multiply 5 [1; 2; 3];;
- : int list = [5; 10; 15]

   The important point to note about the multiply function is the
nested function f. This is a closure. Look at how f uses the value of n
which isn't actually passed as an explicit argument to f. Instead f
picks it up from its environment - it's an argument to the multiply
function and hence available within this function.

   This might sound straightforward, but let's look a bit closer at
that call to map: List.map f list.

   map is defined in the List module, far away from the current code.
In other words, we're passing f into a module defined "a long time ago,
in a galaxy far far away". For all we know that code might pass f to
other modules, or save a reference to f somewhere and call it later.
Whether it does this or not, the closure will ensure that f always has
access back to its parental environment, and to n.

   In LISP, the same example would be:

(defun multn (n)
	#'(lambda (x) (* x n)))

(mapcar (multn 2) (1 2 3 4))
==>
(2 4 6 8)

(mapcar (multn 5) (1 2 3 4))
==>
(5 10 15 20)

   As with the OCAML solution, the agument to multn gets stuck in a
closure and is carried around the data structure.

   The same technique in LISP is

(defparameter *grammar*
  '((Sentence -> Noun VerbPhrase )
    (VerbPrase -> runs quickly)
    (VerbPhase -> walks slowley)))

(defun lhs (g)
  (let (all)
    (mapc #'(lambda (one)
                 (setf all (lhs1 (first one) all)))
          g)
    all))

(defun lhs1 (item all)
  (if (member item all)
      all
      (cons item all)))

;e.g.
;(lhs *grammar*)

Partial function applications and currying
..........................................

Let's define a plus function which just adds two integers:

let plus a b =
  a + b
  ;;

   Some questions for people asleep at the back of the class.
What is plus?
What is plus 2 3?
What is plus 2?
 Question 1 is easy. plus is a function, it takes two arguments which
are integers and it returns an integer. We write its type like this:
plus : int -> int -> int

   Question 2 is even easier. plus 2 3 is a number, the integer 5. We
write its value and type like this:
5 : int
 But what about question 3? It looks like plus 2 is a mistake, a bug.
In fact, however, it isn't. If we type this into the OCaml toplevel, it
tells us:
# plus 2;;
- : int -> int = <fun>
 This isn't an error. It's telling us that plus 2 is in fact a
function, which takes an int and returns an int. What sort of function
is this? We experiment by first of all giving this mysterious function
a name (f), and then trying it out on a few integers to see what it
does:
# let f = plus 2;;
val f : int -> int = <fun>
# f 10;;
- : int = 12
# f 15;;
- : int = 17
# f 99;;
- : int = 101
@end verbtim
In engineering this is sufficient proof by example for us to state that plus 2 is the function which adds 2 to things.

Going back to the original definition, let's "fill in" the first argument (a) setting it to 2 to get:
@verbatim
let plus 2 b =       (* This is not real OCaml code! *)
  2 + b
  ;;

   You can kind of see, I hope, why plus 2 is the function which adds 2
to things.

   Looking at the types of these expressions we may be able to see some
rationale for the strange -> arrow notation used for function types:
  plus : int -> int -> int
  plus 2 : int -> int
plus 2 3 : int
 This process is called currying (or perhaps it's called uncurrying, I
never was really sure which was which). It is called this after Haskell
Curry who did some important stuff related to the lambda calculus.
Since I'm trying to avoid entering into the mathematics behind OCaml
because that makes for a very boring and irrelevant tutorial, I won't
go any further on the subject. You can find much more information about
currying if it interests you by doing a search on Google.

   Remember our double and multiply functions from earlier on? multiply
was defined as this:
let multiply n list =
  let f x =
    n * x
  in
  List.map f list
  ;;

   We can now define double, triple &c functions very easily just like
this:
let double = multiply 2;;
let triple = multiply 3;;
 They really are functions, look:
# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]
 You can also use partial application directly (without the
intermediate f function) like this:
# let multiply n = List.map (( * ) n);;
val multiply : int -> int list -> int list = <fun>
# let double = multiply 2;;
val double : int list -> int list = <fun>
# let triple = multiply 3;;
val triple : int list -> int list = <fun>
# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]
 In the example above, ((*) n) is the partial application of the (*)
(times) function. Note the extra spaces needed so that OCaml doesn't
think (* starts a comment.

   Note that LISP can be streched to handling currying. But there is
something fundamentally more elegant about OCAML (no annoying
brackets!). Also, there is more current work on optimizing modern
functional langauges that old horses like LISP:

2.6 GOLD: Graham's Object Language Definition
=============================================

This document:
   * Describes an object-oriented language called _GOLD_.  Originally
     defined in Paul Graham's chapter on OO (grahamOO.pdf), _GOLD_
     contains some extensions by Tim Menzies (http://menzies.us).

   * Is a description of the upper layers of _GOLD_. For full details
     on all layers of _GOLD_, see Graham's text (grahamOO.pdf).

   The point of _GOLD_ is that a non-trivial OO language can be defined
in just a few dozen lines of LISP. For example, _GOLD_ supports:
   * classes;

   * instances;

   * methods;

   * extending methods by calling super-class methods;

   * and multiple inheritance.
   Amusingly, this help file is actually _longer_ that the source code
that implements _GOLD_.

Installation
============

_GOLD_ is at least files:
   * `oo.lisp': Graham's original OO code (plus a few bug fixes);

   * `gold.lisp': Some extensions, listed below.

   * `xxx.lisp': Some class files.

Extensions
==========

   * _GOLD_ defines a root object called _*object*_

   * _GOLD_  changes the `inst' creation function such that all objects
     get sent the `init' message, immediately on creation.

   * _GOLD_ adds a "do nothing" method `init' to _*object*_ (so if your
     class does not have an `init' method, then it still can be created
     without a crash.

   * _GOLD_ lets you distinguish instance variables from method names
     using a `$prefix'.

   * _GOLD_ defines an accessor that returns all the slots in an object:
     `zlots'.

   * _GOLD_ defines an iterator over all slots in an object:
     `with-zlots'.

Examples
========

Subclassing
-----------

Something is a subclass of `*object*' with methods `area,volume' and
instance variables `$height'.
(klass (*object*) area $height volume)
 Note: in _GOLD_, everything has to be a subclass of `*object*'.

Creating a Global Class
-----------------------

(defparameter *body* (klass (*object*) area $height volume))
 As a side-effect of the above call, set and get methods are defined for
all the `$variables'. So, after that call, it is possible to call:
($height abody)
(setf ($height abody) 1)

Creating an Instance
--------------------

Example:
(inst *body*)

   Note: `inst' is defined in terms of a lower-level `inst0' function:
(defun inst (parent)
  (let ((obj (inst0 parent)))
    (init  obj)
    obj))
 So, if you want to turn off auto-initialization, then use the
lower-level command `inst0'.

Define a method
---------------

Methods are just like LISP functions, with at least one argument (the
instance being processed).
(defmeth volume *body* (me)
         (* ($height me) (area me)))
 Note: if you get this error:
Can't set #<FUNCTION (LAMBDA (U)) {10043C9DA9}>
    of #1=#((#2=#((#3=#)
               #(INIT
                 WITH-ZLOTS
                 ZLOTS
                 AREA
...
 then have called `defmeth' on a method name _not_ listed in the call
to `klass' that defined this class.

Defining an Initialization Method
---------------------------------

(defmeth init *body* (me)
         (setf ($height me) 1))

Note that such methods are _optional_. All sub-classes of `*object*'
inherit a default, do nothing, initialization method.

Extending a Super-class Method
------------------------------

Methods in sub-classes can access method definitions in super-classes
via the `next' function.

   For example, suppose a `*body*' has a default `init' action which a
sub-class called `*tube*' wants to access:
(defmeth init *body* (u)
         (setf ($height u) 1))

(defmeth init *tube* (u)
         (next u)
         (setf ($radius u) 10))

Worked Example
==============

Bodies have a default height of one and a volume equal to their area
times their height.  Tubes are a sub-class of bodies whose area is
their radius times pi, squared. Tubes initialize themselves as an
extension to body's initialization.
(defparameter *body* (klass (*object*) area $height volume))
(defparameter *tube* (klass (*body*) $radius))

(defmeth init *body* (u)
         (setf ($height u) 1))

(defmeth area *tube* (u)
         (* pi (expt ($radius u) 2)))

(defmeth volume *body* (u)
         (* ($height u) (area u)))

(defmeth init *tube* (u)
         (next u)
         (setf ($radius u) 10))

(defun !tube ()
  (let ((tub (inst *tube*)))
    (format t "~a~%" (volume tub))
    (with-zlots tub
      #'(lambda (prop value)
          (if (dollarp prop)
              (format t "~a = ~a~%" prop value))))))
 Note the functions `with-zlots' and `dollarp' in the `!tube' function.
The former loops through all slot names while the latter selects
anything that starts with a `$' sign. This function just prints out all
the instance variables (skipping over the functions).

Hints
=====

Functions that are generic to all objects can be written to `*object*'
methods.  For example:
(defmeth zlots *object* (self)
            (coerce (layout (parents self)) 'list))

(defmeth with-zlots *object* (self fn)
         (dolist (zlot (zlots self))
           (funcall fn zlot (lookup zlot self))))

Bugs
====

If `*print-array*' is non-nil, then display a class will lead to an
infinite loop (since the first field contains a pointer back to itself,
so a full print takes never terminates).

   `GOLD''s source code sets `*print-array*'. However, in some obscure
debugging scenarios, this is not enough to stop the infinite loop.
Therefore,  if your code just hangs, restart LISP and make sure
`*print-array*' is nil.

For More
========

See GOLD1 and 2 (http://unbox.org/wisp/var/timm/11/310/lisp/gold.html);
and GOLD3 (http://unbox.org/wisp/var/timm/11/310/lisp/gold3.html); and
GOLD4 (http://unbox.org/wisp/var/timm/11/310/lisp/gold4.html).

2.7 OO programming
==================

Smalltalk: an Example OO Language
=================================

The following notes introduce OO using the Smalltalk language.  After
programming in LISP, you may be very happy with  Smalltak- often the
code has no brackets!

   Until 5 years ago, I would have said that Smalltalk is was an
historical language (something to be studied by ancient scholars).
Now, maybe not (see all the interest in Seaside and GNU Smalltalk).

   Anyway, we don't study it to program in it. Rather, we use it to
define an abstract spec of what an OO language should look like. From
that, we will then audit _GOLD_- an OO language written in 100 lines of
LISP.

History
=======

Smalltalk was developed at Xerox Parc in the 1970s by a team that
included Alan Kay, Dan Ingalls, Adele Goldberg, Ted Kaehler, Scott
Wallace, and others.  Alan Kay is famous for saying

     The best way to predict the future is to invent it.
   He wasn't kidding.  Smalltalk is famous for creating the bitmapped
multi-windowed mouse-driven environment that inspired Steve Jobs to
create the first Macintosh.  Up until the iPhone/iPad, the Smalltalk
interfaces were the dominant influence on our vision of a computer.
Consider the following images from the Sept 1977 Scientific American
Article, "Microelectronics and the Personal Computer" pp. 230-244, by
Alan Kay.  Note the definition of some core ideas:

     "Windows," display frames within the larger display screen, enable
     the user to organize and edit information at several layers of
     refinement. Once the windows are created they overlap on the
     screen like sheets of paper. Images with various degrees of
     symbolic content can be display simultaneously.

But What are Objects?
=====================

Lets take a moment to review the seven main buzzwords of OO:

   *  Classes

   * Instances

   * Attributes

   * Operations

   * Inheritance

   * Classification

   * Encapsulation

   * Polymorphism

   Classes make instances and, usually, distinction is as follows:

   * Design time: classes

   * Runtime: instances

   (By the way, here's something really cool. Everything in Smalltalk
is an instance, including classes:
   * The class of the instance "3" is "Integer".

   * And "Integer" is an instance of the class "Class".

   * And "Class" is an instance of the class "MetaClass".

   * And the buck stops here: "MetaClass" is an instance of the class
     "MetaClass".)

   Instances have attributes, operations, identity, and associations.
   * Attributes (state, data)

   * Operations (behavior, function, code), which Smalltalk calls
     methods. For example, an "Account" object might comment on its own
     status: ! Account methods !
     inTheRed
     	^balance < 0
     !!

   * Identity (uniqueness, memory location)

   * Associations (who you talk too).

   Instances can use inheritance, classification, encapsulation and
polymorpishm:
   * Inheritance (ask your father). For example: old mean jump the same
     way young men do (just not as often).  Person                (has "dob", does "walk")
          Male             (does "jump")
               OldMale     (does "dance", and calls jump a little)
               YoungMale   (does "dance", and calls jump a lot)
          Female           (does "dance" and "jump")

     (Aside: do Males have a "dob"? How do "OldMale"s jump?)

   * Classification (factory, stencil)
        * Classes store our knowledge of instances.

        * For example, they can tune instance creation. Here are
          "Account" class methods that return specially tuned "Account"
          instances (don't worry about the syntax details, we'll get
          back to those later.  ! Account class methods !
          bigAccount
          	^self new minBalance: 1000000
          !
          smallAccount
          	^self new maxBalance: 20000
          !!

   * Encapsulation (border guards)
        * Hide what you can, reveal only what you need.

   * Polymorphism (polly wanna cracker and don't care how you do it)
        * E.g. "Circle", "Triangle" and "Square" all draw themselves
          different ways but they all might respond to the message
          "draw". E.g. All our "Person"s, above, respond to "dance",
          but all do it differently.

        * So polymorphism means same interface, different internal
          behavior.

For Example
-----------

For example, you could be modeled as a network of associations between
instances of the class "Body", "Arm", and "Leg":

   * "Body" is a container instance containing 2 "Arms", 2 "Legs", and
     one "Head".

   * "Body" has core attributes "age", "spouse", "address", as well as
     other attributes to store pointers to the "Arms", "Legs", and
     "Head".

   * "Body" has operations: jump, talk, dance etc.

   Note classic newbie OO mistake: associations is not inheritance;
   * Just because "CarYards" have "Cars", does not mean that "CarYards"
     isa "Car";

   * Just because dogs can access cats, does not mean dog isa cat (but
     it might be true that they share some super class; e.g. "Dog" isa
     "Pet" and "Cat" isa "Pet").
   So it is not true that "Arm" isa "Body". Rather, "Body" uses "Arm".

   For another example, "Fraction" contains two integers: the
"Numerator" and the "Denominator". "Fraction" is not a sub-class of
"Integer"- but it does use Integers.

   Lesson: a working OO system is a conversation between networks of
objects.

Talking from Sub to Super
=========================

Let's say that we've got an `Account' class:

Object subclass: #Account
          instanceVariableNames: 'balance'
          classVariableNames: ''
          poolDictionaries: ''
          category: nil !

!Account methods !
spend: amount
     balance := balance - amount
!
deposit: amount
     balance := balance + amount
!
init
      balance := 0
!!
 This last `init' method initializes the hidden variable "balance"
(actually called an instance variable ) to zero, which makes sense for
an account balances.

   We can create the `Savings' class as a subclass of `Account'. It
holds money, just like an `Account', but has an additional property
that we will model: it is paid interest based on its balance.
Account subclass: #Savings
   instanceVariableNames: 'interest'
   classVariableNames: ''
   poolDictionaries: ''
   category: nil !

   The instance variable "interest" will accumulate interest paid.
Thus, in addition to the "spend:" and "deposit:" messages which we
inherit from our parent, `Account', we will need to define a method to
add in interest deposits, and a way to clear the interest variable
(which we would do yearly, after we have paid taxes). We need to define
a method for allocating a new account - we need to make sure that the
interest field starts at 0.
!Savings methods !
init
     interest := 0.
     ^super init
!!
 Can you guess what `super init' does? Its the sub-class method calling
the parent.  It is like saying "do my own initializations for my own
variables (`interest') then go away and do whatever you need to do to
initialize my inherited properties.

   While this is a trivial example, such definitions-via-extension are
very useful when dealing with (say) complex interface classes where
super-classes have some intricate initialization sequence. Subclasses
need not understand that initialization sequence, all they need to do
is to call daddy and ask him to run that complex code.

   One of our challenges for _GOLD_ is to handle such super-class calls.

Singletons
----------

As an aside (and this is a concept we will return too in later lectures)
is that one thing you want to with initialization control is handle
_singletons_; i.e. classes for which there should only be one instance,
and provide a global point of access to it.

   Why singletons? Well, often, a system only needs to create one
instance of a class, and that instance will be accessed throughout the
program. Examples would include objects needed for logging,
communication, database access, etc. You could pass such an instance
from method to method, or assign it to each object in the system.
However, this adds a lot of unnecessary complexity.

   Singletons are most appropriate for services that do not change
their nature based on their invocation context. A singleton can be
created at startup based on context or be reset for larger scale state
transitions

   Simply put: _singletons make it easy to compose a program from
different components_.  Singletons do not create unnatural
interdependencies made by passing a context object around, where every
piece of code will bind to everything in the context object.
Singletons stand alone.

   Examples:
   * One "cut" buffer shared by all instances of a text editor (so you
     can cut, copy, paste between any text editing sessions).

   * One random number stream, shared by all parts of the program.

   * One logging stream, that everyone writes too.

   * (Esoteric) Languages that initialize all their globals as single
     instances of some class. e.g. in Smalltalk:
        *  "true", "false", "nil"

        * are singletons of the classes "True", "False" and
          "UndefinedObject", respectively (aside: so, unlike in LISP,
          "nil" is an object with customizable properties).
How to do it in Smalltalk?

   Step 1: add a _ClassVariable_ to a class.

Account subclass: #Database
   instanceVariableNames: ''
   classVariableNames: 'CurrentDatabaseConnection'
   poolDictionaries: ''
   category: nil !!

   Step 2: change the _new_ method that only returns the same instance,
over and over again.
!Database class methods!
new
	CurrentDatabaseConnection isNil ifTrue:[
		CurrentDatabaseConnection := super new].
	^CurrentDatabaseConnection
!!

   That's it!  Now, whenever we create a "new" instance of this class,
we just use the same one over and over again.

   Note that there is a much much much more elegant way to create
Singletons (see the uber-elegant way Io does it
(http://media.pragprog.com/titles/btlang/lo.pdf), on p72-74-  which
we'll explore in later lectures).

What Makes OO Exceptional: Distributed Control
==============================================

In the above example, we could specialize instance creation by writing
a new "new" method, that runs just for one exceptional class
(DataBase's singleton method).

   That's OO- everything is exceptional. Polymorphism means that
general procedures that can specialized for particular objects
_without_ mucking up the centralized controller.

   To illustate that point, we  take a look at how procedural control
can be defined in an OO system.

Blocks
------

Before doing that, we have to know about "Blocks" which is Smalltalk's
version of lambda bodies.
|x y z|
x := [3 > 7].
y := [:a | a > 7].
z := [:a :b | a > b].

x value.              "Returns true"
y value: 10           "Returns false"
z value: 10 value: 20 "Returns false"

Distributed if-then-else
------------------------

All control in Smalltalk is based on blocks. The message
3 > 7 ifTrue: [Transcript printOn: 'yes'].
 The way this works is that: `3 > 7' evaluates to some subclass of
`Boolean':
   * In Smalltalk, `true' is the single instance of the class _True_
     and `false' is the single instance of the class _False_.

   * So the message `ifTrue:' with the argument `[Transcript printOn:
     'yes']' is handled by either a method of the class _True_ or
     _False_.
   The code for those methods is shown below:
! True methods !
ifTrue: trueBlock
	^trueBlock value "We are true -- evaluate trueBlock"
!!

! False methods !
ifTrue: trueBlock
	^nil "We are false -- do nothing"
!!
 Note that this is an example of pure OO: the object-oriented message
system is being enlisted to replace procedural if-then-else.

Distributed Enumeration Control
-------------------------------

Using Blocks, trick, we can also implement for-loops. Here's the
equivalent of LISP's `dotimes' macro:
! Number methods !
to: stop do: aBlock
        | i |
        i := self.
        [i <= stop] whileTrue: [ "whileTrue is a built-in"
                aBlock value: i.
                i := i + 1
        ]
        ^stop
!!
 For example:
1 to: 5 do: [:i|
   Transcript printOn: i]
 And here the equivalent of LISP's _dolist_ macro:
! SequenceableCollection methods !
do: aBlock
    1 to: (self size) do: [:i |
           aBlock value: (self at: i)]
!!
 For example:
'this is a string' do: [:char|
   Transcript printOn: char]

Why Bother?
-----------

Now consider the advantages of such distributed control structures:
   *  If, in "C", you wanted to define a new kind of for-loop, you'd
     need to change the "C" compiler and optimizer. Not a task for the
     feint-hearted.

   * On the other hand, in Smalltalk, it is just a matter of writing
     just another method.
   Which means, extending the language to bury away common processing
constructs inside higher-level commands is _much_ easier than in "C".

   So there is a whole industry in building domain-specific languages.
For example, here's a state machine language, written in Smalltalk.
Each machine contains states (e.g. _#start, #run_) which are connected
by transitions (e.g. if happiness < 2 then go to #run).
! Factory methods !
worksIn: factory
    factory
       machine: (self new: 'party boy');
       go: #start   to: #run     then:  [The machine talks: 0];
       go: #run     to: #oddHaHa then:  [The machine talks: 1];
       go: #run     to: #even    then:  [The machine talks: 2];
       go: #oddHaHa to: #oddHaHa then:  [The machine
                                            drinks;
                                            talks: 3];
       go: #oddHaHa to: #run     if:    [The machine happiness < 2 ]
                                 then:  [The machine
                                            talks: 4;
                                            talks: 'Too drunk to stay awake.'];
       go: #even    to: #run;
       go: #run     to: #endF    if:    [App random next > 0.9]
                                 then:  [The machine
                                            talks: 5;
                                            talks: 'that is all folks'.
                                         The yourself oo.
                                         The state oo.
                                         The next oo.
                                         The machine oo.
                                         The factory oo].
!!
 For more on this language, see the agent-ready
(http://code.google.com/p/agent-ready/source/browse/trunk/lib/) code
base.

   For more on domain-specific languages see my notes on that topic
(http://courses.ece.ubc.ca/571f/lectures.html).

2.8 Abstraction
===============

A Little History
================

(note: for pedagogical reasons, the following tale is a little
chronologically tangled.)

   Once apon a time, a long time ago, in a galaxy far far away, memory
was a set of bits. Programmers wrote little notes to themselves that
bits 0 to 6 held a "name", that the next 32 bits were a pointer and the
rest was an image bit map.

   Then, at the end of WWII, Grace Hopper asked herself "for tools are
needed to make programs easier to write?". Her answer was "the
compiler", a tool that translates instructions written in a programming
language into the binary coding of machine language (where the
programming language was written in some kind of subset of English that
anyone could read).  Memory was no longer a string of bits, but
"records" with "fields"; e.g.

;; COBOL records
FD Employee-File
     RECORD CONTAINS 65 CHARACTERS
     DATA RECORD IS Employee-Rec.

01 Employee-Rec.
   02 Employee-ID PIC X(10).
   02 Employee-Name.
      03 Last-Name PIC X(20).
      03 First-Name PIC X(12).
      03 Middle-Init PIC X.
   02 Position.
      03 Job-Code PIC X(4).
      03 Department PIC X(3).
      03 Manager-ID PIC X(10)
   02 Hourly-Pay PIC 9(3)V99.

   And so was born abstraction.  It was realized that different records
had similar fields (e.g. numbers, strings, dates) and each of these
"types" came with a set of constraints.  Some simple types can be built
into the compiler (e.g. Integer, Real) and some others might be
domain-specific. So compilers got augmented with type definitions:

/* types in pascal */
type
  Boolean= (true, false);
  Char = 'a' .. 'z';
  Letter = (draft,sending,sent);
var
  r: Real;
  i: Integer;
  c: Char;
  b: Boolean;
  t: Letter;
  e: (apple, pear, banana, orange, lemon);
 Then it was realized that some types are complex combinations of
simple types:
type
  a = Array [1..10] of Integer;
  b = record
        x: Integer;
        y: Char
      end;
  c = File of a;
  Nodeptr = ^Node;
  Node = record
        a: Integer;
        b: Char;
        c: Nodeptr
      end;
 (In the above, the notation "^Node" is a special PASCAL type for
"pointers").

   Here's another example:

(* complext types in OCAML *)

type paragraph =
    Normal of par_text
  | Pre of string * string option
  | Heading of int * par_text
  | Quote of paragraph list
  | Ulist of paragraph list * paragraph list list
  | Olist of paragraph list * paragraph list list

and par_text = text list

and text =
    Text of string
  | Emph of string
  | Bold of string
  | Struck of par_text
  | Code of string
  | Link of href
  | Anchor of string
  | Image of img_ref

and href = { href_target : string; href_desc : string; }

and img_ref = { img_src : string; img_alt : string; }

   Then it was realized that the types can be augmented with operations
that apply just to those types.

 -- complex numbers in LUA

 complex = {}

    function complex.new (r, i) return {r=r, i=i} end

    -- defines a constant `i'
    complex.i = complex.new(0, 1)

    function complex.add (c1, c2) return complex.new(c1.r + c2.r, c1.i + c2.i) end

    function complex.sub (c1, c2) return complex.new(c1.r - c2.r, c1.i - c2.i) end

    function complex.mul (c1, c2)
      return complex.new(c1.r*c2.r - c1.i*c2.i,
                         c1.r*c2.i + c1.i*c2.r)
    end

    function complex.inv (c)
      local n = c.r^2 + c.i^2
      return complex.new(c.r/n, -c.i/n)
    end

    return complex

   -- example
   c = complex.add(complex.i, complex.new(10, 20))

   Then it was realized that packages of operations and types can units
of parrallelism and concurrecny (it you pick up "X", you get all "X"'s
internal state and operations).  And that gave us simulation languages
like Simula.

   Then it was realized that types can have sub-types that specialize
the operations (welcome to polymorphism and inheritance).

   And some argued that should be no "primitive types" pre-defined and
unalterable by the compiler- that everything should be customizable
(welcome to Smalltalk)

   And all through this sequence, the compilers got smarter and smarter
about types and abstraction: if we know that only _these_ operations
are valid for this variable in this memory location, then we can block
the application of the wrong operations to the wrong memory location.

   Note that if we try to infer as much as possible about the space of
what types are touched by some variable (of some other type), then we
can detect programming errors before we run the program.

   Which takes us to the modern functional languages that view runtime
operations as the conversion of type1 to type2 (and, it type2 is some
error type then "type checking" is still type conversion).

   But the notion of types and abstraction applies to more than just
OCaml, Haskell, etc. As shown below, this sequence of named memory
locations of certain types prevades all modern languages.

   So too our list of "what is common across all languages", we now add
"types" and "abstraction" (and the rest of the list is "tests,
paradigms" and, for some languages "closures" (a.k.a. lambda bodies)).

   So lets go back to basics.

What is Abstraction
===================

The ability to abstract and to generalize is an essential part of any
intellectual activity. Abstraction and generalization are fundamental to
mathematics and philosophy and are essential in computer science as
well.

   The importance of abstraction is derived from its ability to hide
irrelevant details and from the use of names to reference objects.
Programming languages provide abstraction through procedures,
functions, and modules which permit the programmer to distinguish
between _what_ a program does and _how_ it is implemented. The primary
concern of the user of a program is with what it does. This is in
contrast with the writer of the program whose primary concern is with
how it is implemented. Abstraction is essential in the construction of
programs. It places the emphasis on what an object is or does rather
than how it is represented or how it works. Thus, it is the primary
means of managing complexity in large programs.

   Of no less importance is generalization. While abstraction reduces
complexity by hiding irrelevant detail, generalization reduces
complexity by replacing multiple entities which perform similar
functions with a single construct. Programming languages provide
generalization through variables, parameterization, generic and
polymorphism. Generalization is essential in the construction of
programs. It places the emphasis on the similarities between objects.
Thus, it helps to manage complexity by collecting individuals into
groups and providing a representative which can be used to specify any
individual of the group.

   Abstraction and generalization are often used together. Abstracts are
generalized through parameterization to provide greater utility. In
parameterization, one or more parts of an entity are replaced with a
name which is new to the entity. The name is used as a parameter. When
the parameterized abstract is invoked, it is invoked with a binding of
the parameter to an argument.

   Exercise: draw a mammal that is not a dog, cat, bear, human, etc...

     Principle of Abstraction An abstract is a named entity which may
     be invoked by mentioning the name.
   An object is said to be fully abstract if it can be understood
without reference to any thing external to the object. So a fully
abstract concept is a complete thing unto itself and can be studied
seperately to the rest of the universe

   Among the various terms for abstracts found in other texts are
module, package, library, unit, subprogram, subroutine, routine,
function, procedure, abstract type, object.  So, as you can see,
_abstraction_ is a core concept to many languages.

   Terminology. The naming aspect of abstraction is captured in the
concepts of binding, definition and declaration while the hiding of
irrelevant details is captured by the concept of encapsulation. A
binding is an association of two entities:

   *  A definition is a binding of a name to an entity;

   *  A declaration is a definition which binds a name to a variable;

   *  An assignment is a binding of a value and a variable.
   We could equally well say identifier instead of name:
   * Names are bound to variables in declaration statements.

   *  A variable is an entity whose value is not fixed but may vary.

Binding
-------

The concept of binding is common to all programming languages. The
objects which may be bound to names are called the bindables of the
language. The bindables may include: primitive values, compound values,
references to variables, types, and executable abstractions. While
binding occurs in definitions and declarations, it also occurs at the
virtual and hardware machine levels between values and storage
locations.

Encapsulation
-------------

The abstract part of a binding often contains other bindings which are
said to be local definitions. Such local definitions are not visible or
available to be referenced outside of the abstract. Thus the abstract
part of a binding involves "information hiding". This hidden
information is sometimes made available by exporting the names.

   A module system provides a way of writing large program so that the
various pieces of the program don't interfere with on another because
of name clashes and also provides a way of hiding implementation
details. ... A module generally consists of two parts, the export part
and the local part. The export part of a module consists of language
declarations for the symbols available for use in either part of the
module and in other modules which import them and module declaration
giving the symbols from other modules which are available for use in
either part of the module and in other modules which import them. The
local part of a module consists of language declarations for the
symbols available for use only in this part. TGPL-Hill and Lloyd

-- exporting names in LUA
    local P = {} -- shorthand for "complex"... save LOTS of typing
    complex = P

    local function checkComplex (c)
      if not ((type(c) == "table")
         and tonumber(c.r) and tonumber(c.i)) then
        error("bad complex number", 3)
      end
    end

    local function new (r, i) return {r=r, i=i} end

    local function add (c1, c2)
      checkComplex(c1);
      checkComplex(c2);
      return new(c1.r + c2.r, c1.i + c2.i)
    end

      ...

    complex = {
      new = new,
      add = add,
      sub = sub,
      mul = mul,
      div = div,
    }
 To fully understand the LUA you ahve to understand that "new = new"
binds a novel symbol to an existing symbol inside the package. Its hard
to get your brain around but simple enough to do in LUA.

   Here's packages in SWI-PROLOG. You don't need to understand the
language- the only important detail here is that if someone else loads
the following file, all they can call is something called "reverse"
that takes two arguments. Any lower-level stuff (e.g. the fact that
there is some sub-routine called "rev") is hidden away.
% packages in swi prolog
:- module(reverse, [reverse/2]).

reverse(List1, List2) :-
        rev(List1, [], List2).

rev([], List, List).
rev([Head|List1], List2, List3) :-
        rev(List1, [Head|List2], List3).
 And in case you missed it- you've been using packages in LISP from
day1. Ever noticed the prompt on the REPL?
CL-USER>
 That says that you are working in the common-lisp user package. Every
symbol (which includes variables and functions) in LISP exists in one
package. Symbols from other packages can be imported .  And this lets
us divide up large stuff into smaller chunks with well-defined
interfaces.
CL-USER> (in-package :com.gigamonkeys.email-db)
#<The COM.GIGAMONKEYS.EMAIL-DB package>
EMAIL-DB>
EMAIL-DB> (defun hello-world () (format t "hello from EMAIL-DB package~%"))
HELLO-WORLD
EMAIL-DB> (hello-world)
hello from EMAIL-DB package
NIL
EMAIL-DB> (in-package :cl-user)
#<The COMMON-LISP-USER package>
CL-USER>
CL-USER> (hello-world)
hello, world
NIL
 While the concept of modules is a useful abstraction, the full
advantages of modules are gained only when modules may be written,
compiled and possibly executed separately. In many cases modules should
be able to be tested independently of other modules.

   Advantages
   * reduction in complexity

   * team programming maintainability

   * re-usability of code project management
   Implementation
   * common storage area - Fortran

   * include directive - C++

   * subroutine library
   Typical applications:
   * subroutine packages - mathematical, statistical etc

   * ADTs

Abstract Data Types
===================

An abstract data type (ADT) is a mathematical model for a certain class
of data structures that have similar behavior; or for certain data types
of one or more programming languages that have similar semantics.

   An abstract data type is defined indirectly, only by the operations
that may be performed on it and by mathematical constraints on the
effects (and possibly cost) of those operations.  For example:

   *  an abstract stack data structure could be defined by two
     operations:  push, that inserts some data item into the structure,
     and pop, that  extracts an item from it; with the constraint that
     each pop always  returns the most recently pushed item that has
     not been popped yet.

   * When analyzing the efficiency of algorithms that use stacks, one
     may also specify that both operations take the same time no matter
     how many items have been pushed into the stack, and that the stack
     uses a constant amount of storage for each element.

 -- complex numbers in LUA

 complex = {}

    function complex.new (r, i) return {r=r, i=i} end

    -- defines a constant `i'
    complex.i = complex.new(0, 1)

    function complex.add (c1, c2) return complex.new(c1.r + c2.r, c1.i + c2.i) end

    function complex.sub (c1, c2) return complex.new(c1.r - c2.r, c1.i - c2.i) end

    function complex.mul (c1, c2)
      return complex.new(c1.r*c2.r - c1.i*c2.i,
                         c1.r*c2.i + c1.i*c2.r)
    end

    function complex.inv (c)
      local n = c.r^2 + c.i^2
      return complex.new(c.r/n, -c.i/n)
    end

    return complex

   -- example
   c = complex.add(complex.i, complex.new(10, 20))

Weak vs Strong Types
--------------------

Weakly typed programming languages support either implicit type
conversion:

;; e.g. Perl, Rexx
a = 2
b = '2'

concatenate(a, b) # Returns '22'
add(a, b)         # Returns 4

   Stong typing:

;; e.g. JAVA, Python
a = 2
b = '2'

concatenate(str(a), b) # Returns '22'
add(a, int(b))         # Returns 4
concatenate(a, b)     # Type Error
add(a, b)             # Type Error

   If you are not weak, you are strong:
   * Strong guarantees about the run-time behavior of a program before
     program execution, whether provided by static analysis, the
     execution semantics of the language or another mechanism.

   * Compile-time checks for type constraint violations. That is, the
     compiler ensures that operations only occur on operand types that
     are valid for the operation.

   * At compile or run time you can  rejection operations or function
     calls which attempt to disregard data types.

   * Fixed and invariable typing of data objects. The type of a given
     data object does not vary over that object's lifetime. For
     example, class instances may not have their class altered.

   * A complex, fine-grained type system with compound types.

   The object-oriented programming languages Smalltalk, Ruby, Python,
and Self are all "strongly typed" in the sense that typing errors are
prevented at runtime and they do little implicit type conversion, but
these languages make no use of static type checking: the compiler does
not check or enforce type constraint rules.

   * The term _duck typing_ is used to describe the dynamic typing
     paradigm used by the languages in this group.

   Standard ML, Objective Caml and Haskell have purely static type
systems, in which the compiler automatically infers a precise type for
all values. These languages (along with most functional languages) are
considered to have stronger type systems than Java, as they permit no
implicit type conversions. While OCaml's libraries allow one form of
evasion (Object magic), this feature remains unused in most applications

Dynamic vs Static Typing
------------------------

A programming language is said to be dynamically typed when the majority
of its type checking is performed at run-time as opposed to at
compile-time.

   In dynamic typing, values have types but variables do not; that is,
a variable can refer to a value of any type.

   Dynamically typed languages include APL, Erlang, Groovy, JavaScript,
Lisp, Lua, MATLAB/GNU Octave, Perl (with respect to user-defined types
but not built-in types), PHP, Prolog, Python, Ruby, Smalltalk and Tcl.

   Compared to static typing, dynamic typing can be more flexible
(e.g., by allowing programs to generate types and functionality based
on run-time data), though at the expense of fewer a priori guarantees.
This is because a dynamically typed language accepts and attempts to
execute some programs which may be ruled as invalid by a static type
checker.

   e.g. Caml is expression-based, there are no pure "commands" like in
Java/C++; instead, commands are also expressions, they return values.
# (if (2=3) then 5 else 6) + 1;;
- : int = 7
 One sometimes annoying consequence of the above is the two branches of
the if need to return the same type.
if (2=3) then 5 else 6.5;;
Characters 21-24:
 This expression has type float but is here used with type int

   Dynamic typing may result in runtime type errors—that is, at
runtime, a value may have an unexpected type, and an operation
nonsensical for that type is applied. This operation may occur long
after the place where the programming mistake was made—that is, the
place where the wrong type of data passed into a place it should not
have. This may make the bug difficult to locate.

Iterators
---------

Q: If we break things up into seperate bits, each with invariants and
internal details, how do we run over them all? Keeping internals
private?

   A: Iterators. Generic looping constructs that return "next" or "nil".
   * While next not nil

   * Process the next

   Example (if you understand the following, then you understand
closures- a.k.a.  lambda bodies- and you understand that LUA uses
closures):
-- LUA: return an iterator for  all items in a table of size table.getn(t)
  function list_iter (t)
      local i = 0
      local n = table.getn(t)
      return function ()
               i = i + 1
               if i <= n then return t[i] end
             end
  end

  t = {10, 20, 30}
  for element in list_iter(t) do
      print(element)
  end
 Note: in LUA, the "for" keyword knows about iterators.

   A more complex example: returns all words in a file.
   -- LUA
   function allwords ()
      local line = io.read()  -- current line
      local pos = 1           -- current position in the line
      return function ()      -- iterator function
        while line do         -- repeat while there are lines
          local s, e = string.find(line, "%w+", pos)
          if s then           -- found a word?
            pos = e + 1       -- next position is after this word
            return string.sub(line, s, e)     -- return the word
          else
            line = io.read()  -- word not found; try next line
            pos = 1           -- restart from first position
          end
        end
        return nil            -- no more lines: end of traversal
      end
    end
 The main part of the iterator function is the call to string.find. This
call searches for a word in the current line, starting at the current
position. It describes a "word" using the pattern '%w+', which matches
one or more alphanumeric characters. If it finds the word, the function
updates the current position to the first character after the word and
returns that word. (The string.sub call extracts a substring from line
between the given positions). Otherwise, the iterator reads a new line
and repeats the search. If there are no more lines, it returns nil to
signal the end of the iteration.

   Despite its complexity, the use of allwords is straightforward:
    -- LUA
    for word in allwords() do
      print(word)
    end
 This is a common situation with iterators: They may be difficult to
write, but are easy to use. This is not a big problem; more often than
not, end users programming in Lua do not define iterators, but only use
those provided by the application.

Block structure
===============

A block is a construct that delimits the scope of any definitions that
it may contain. It provides a local environment i.e., a opportunity for
local definitions. The block structure (the textual relationship between
blocks) of a programming language has a great deal of influence over
program structure and modularity. There are three basic block
structures-monolithic, flat and nested.

   A program has a monolithic block structure if it consists of just
one block. This structure is typical of BASIC and early versions of
COBOL. The monolithic structure is suitable only for small programs.
The scope of every definition is the entire program. Typically all
definitions are grouped in one place even if they are used in different
parts of the program.

Flat Blocks
-----------

A program has a flat block structure if it is partitioned into distinct
blocks, an outer all inclosing block one or more inner blocks i.e., the
body may contain additional blocks but the inner blocks may not contain
blocks. This structure is typical of FORTRAN and C. In these languages,
all subprograms (procedures and functions) are separate, and each acts
as a block. Variables can be declared inside a subprogram are then
local to that subprogram. Subprogram names are part of the outer block
and thus their scope is the entire program along with global variables.
All subprogram names and global variables must be unique. If a variable
cannot be local to a subprogram then it must be global and accessible
by all subprograms even though it is used in only a couple of
subprograms.

Nested Blocks
-------------

A program has nested block structure if blocks may be nested inside
other blocks i.e., there is no restriction on the nesting of blocks
within the body. This is typical of the block structure of the
Algol-like languages. A block can be located close to the point of use.
In blocks visibility is controlled by nesting.  All names are visible
(implicitly exported) to internally nested blocks.  No names are
visible (exported) to enclosing blocks.  In a block, the only names
visible are those that are declared in all enclosing blocks or are
declared in the block, but not those declared in nested blocks.

   In this example, procedure:
   * P2 is called only by P1 , and need not be visible outside. It is
     therefore declared inside P1 , limiting its scope (its region of
     visibility) to the portion of the program shown here.

   * In a similar fashion, P4 is visible only within P1 , P3 is visible
     only within P2 , and F1 is visible only within P4 .

   * Under the standard rules for nested scopes, F1 could call P2 , and
     P4 could call F1 , but P2 could not call F1 .

   * Though they are hidden from the rest of the program, nested
     subroutines are able to access the parameters and local variables
     (and other local objects) of the surrounding scope(s).

   * In our example, P3 can name (and modify) A1 , X , and A2 , in
     addition to A3 .

   * Because P1 and F1 both declare local variables named X , the inner
     declaration hides the outer one within a portion of its scope.

   * Uses of X in F1 refer to the inner X ; uses of X in other regions
     of the code shown here refer to the outer X.
   Note that
   * A local name is one that is declared within a block for use only
     within that block.

   * A global name is a name that when referenced within a block refers
     to a name declared outside the block.

   * An activation of a block is a time interval during which that
     block is being executed (and an _activation block_ stores the
     local variables)

   The three basic block structures are sufficient for what is called
programming in the small (PITS). These are programs which are
comprehensible in their entirety by an individual programmer. However,
they are not general enough for very large programs. Large programs
which are written by many individuals and which must consist of modules
that can be developed and tested independently of other modules. Such
programming is called programming in the large (PITL).

Scope Rules
-----------

The act of partitioning a program raises the issue of the scope of
names. Which objects with in the partition are to be visible outside
the partition? The usual solution is to designate some names to be
exported and others to be private or local to the partition and
invisible to other partitions. In case there might be name conflict
between exported names from partitions, partitions are often permitted
to designate names that are to be imported from designated partitions
or to qualify the name with the partition name.  The scope rules for
modules define relationships among the names within the partitions.
There are four choices.

   * All local names visible globally.

   * All external names visible locally.

   * Only local explicitly exported names visible globally.

   * Only external names explicitly imported are visible locally.

   * Name conflict is resolved via qualification with the partition
     name.
   Internally, this means that the symbols are stored in a tree
structure and when looking up a definition, you look locally in your
branch and upwards:

Bindings and Binding Times
--------------------------

Bindings may occur at various times from the point of language
definition through program execution. The time at which the binding
occurs is termed the binding time. Four distinct binding times may be
distinguished.
  1. Language design time. Much of the structure of a programming
     language is fixed and language design time. Data types, data
     structures, command and expression forms, and program structure
     are examples of language features that are fixed at language
     design time. Most programming languages make provision for
     extending the language by providing for programmer defined data
     types, expressions and commands.

  2. Language implementation time. Some language features are
     determined by the implementation. Programs that run on one
     computer may not run or give incorrect results when run on another
     machine. This occurs when the hardware differs in its
     representation of numbers and arithmetic operations. For example,
     the maxint of Pascal is determined by the implementation. The C
     programming language provides access to the underlying machine and
     therefore programs which depend on the characteristics of the
     underlying machine may not perform as expected when moved to
     another machine.

  3. Program translation time. The binding between the source code and
     the object code occurs at program translation time. Programmer
     defined variables and types are another example of bindings that
     occur at program translation time.

  4. Program execution time. Binding of values to variables and formal
     parameters to actual parameters occur during program execution.
        Early binding often permits more efficient execution of
programs though translation time type checking while late binding
permits more flexibility through program modification a run-time.

Misc Topics
===========

Exception Classes
-----------------

Here's one version of the  Smalltalk class hierarchy. Note that in 116
Objects, nearly a  third are OO models of errors.

     1	Object	                  | one ring to rule then all
     2	    Behavior
     3	        ClassDescription
     4	            Class                | Class is an instance of MetaClass
     5	            Metaclass            | MetaClass is an instance of itself
     6	    BlockClosure                 | e.g. [30 > 3]
     7	    Boolean
     8	        False                    | has one instance: false
     9	        True                     | has one instance: true
    10	    Directory
    11	    FilePath
    12	        File                     | File
    13	    Iterable
    14	        Collection
    15	            Bag                  | when  adding, inc counts
    16	            HashedCollection
    17	                Dictionary       | Set of Associations (key/value pairs)
    18	                        ...
    19	                             SystemDictionary | one instance: Smalltalk
    20	                    LookupTable
    21	                        IdentityDictionary    | fast. uses == for equality
    22	                Set                           | unordered, no repeats
    23	                    IdentitySet               | fase. uses == for equality
    24	            SequenceableCollection
    25	                ArrayedCollection
    26	                    Array                     | fixed size, can't grow
    27	                    CharacterArray
    28	                        String
    29	                            Symbol            | memory effecient Strings
    30	                        UnicodeString
    31	                    Interval                  | start to stop by step
    32	                LinkedList                    | an old friend
    33	                    Semaphore
    34	                OrderedCollection             | closest thing we have to a list
    35	                    SortedCollection          | sort as a side effect of addition
    36	        Stream                                | pointers into a Collection
    37	            FileDescriptor
    38	                FileStream
    39	            Generator
    40	            PeekableStream
    41	            PositionableStream
    42	                ReadStream
    43	                WriteStream
    44	                    ReadWriteStream | toss of the coin
    45	            Random
    46	            RoundRobinStream
    47	    Magnitude               | anything that can be compared with "<"
    48	        Character
    49	            UnicodeCharacter
    50	        Date
    51	            DateTime
    52	        LookupKey
    53	            Association
    54	        Number
    55	            Float
    56	            Fraction   | uses two intergers
    57	            Integer
    58	                LargeInteger
    59	                    LargeNegativeInteger
    60	                    LargePositiveInteger
    61	                        LargeZeroInteger
    62	                SmallInteger
    63	        Time
    64	            Duration
    65	    Point
    66	    Regex
    67	    Signal    | OO error handling
    68	        Exception
    69	            Error
    70	                ArithmeticError
    71	                    ZeroDivide
    72	                InvalidValue
    73	                    EmptyCollection
    74	                    InvalidArgument
    75	                        AlreadyDefined
    76	                        ArgumentOutOfRange
    77	                            IndexOutOfRange
    78	                        InvalidSize
    79	                        NotFound
    80	                            PackageNotAvailable
    81	                    InvalidProcessState
    82	                    NotIndexable
    83	                    ProcessTerminated
    84	                    ReadOnlyObject
    85	                    WrongClass
    86	                        MustBeBoolean
    87	                MessageNotUnderstood
    88	                MutationError
    89	                NotEnoughElements
    90	                NotImplemented
    91	                    NotYetImplemented
    92	                    ShouldNotImplement
    93	                        SubclassResponsibility
    94	                        WrongMessageSent
    95	                VMError
    96	                    BadReturn
    97	                    NoRunnableProcess
    98	                    PrimitiveFailed
    99	                        CInterfaceError
   100	                        FileError
   101	                        WrongArgumentCount
   102	                    SecurityError
   103	                    UserInterrupt
   104	                    VerificationError
   105	            Halt
   106	            Notification
   107	                EndOfStream
   108	                PackageSkip
   109	                ProcessBeingTerminated
   110	                Warning
   111	            UnhandledException
   112	    UndefinedObject     | one instance: nil

Signatures
----------

A _type signature_ defines the inputs and outputs for a function,
subroutine or method.

   A type signature includes at least the function name and the number
of its arguments.

   In some programming languages, it may also specify the function's
return type, the types of its arguments, or errors it may pass back.

// Ocaml
#let rec fib n =
   if n < 2 then 1 else fib(n-1) + fib(n-2);;
val fib : int -> int = <fun>

Pre-conditions, Post-conditions
-------------------------------

decrement is  -- Decrease counter by one.
     require
             item > 0           -- pre-condition
     do
            item := item - 1
     ensure
            item = old item - 1 -- post-condition
     end

Types as Conditions.
--------------------

Descend the hierarchy, make the types more specific, covers few examples
(e.g. mammals -> dogs).

   Acsend the hierachy, make the types more general, cover more examples
(e.g. OldMan -> Man -> Object).

   Note: another way to write pre- post- conditions is to strengthen and
weaken signatures
   * e.g. weaken pre-condition: make the input types less specific
     (higher in the class hierarchy)

   * e.g. strengthen post-condition: make the return class more
     specific (lower in the type hierarchy)

Liskov substitution principle
-----------------------------

If S is a subtype of T, then:
   *  Objects of type T may be replaced with objects of type S (i.e.,
     objects of type S may be substitutes for objects of type T),

   * without altering any of the desirable properties of that program
     (correctness, task performed, etc.).

   A.k.a. _strong behavioural subtyping_

   * It is a semantic rather than merely syntactic relation;

   * Intends to guarantee semantic interoperability of types in a
     hierarchy, object types in particular.

   * Formally:
        * Let q(x) be a property provable about objects x of type T.

        * Then q(y) should be true for objects y of type S where S is a
          subtype of T.

   Example of violation:
   * Square isa Rectangle

   * Rectanlge has getter and setter methods exist for both width and
     height.

   * Square always assumes that the width is equal with the height.

   * But someone uses the settings inherited from Rectangle to make the
     Square oblong.

   * Note: hard to fix:
        *  If we can modify the setter methods in the Square class so
          that they preserve the Square invariant (i.e. keep the
          dimensions equal) ...

        * ... then these methods will weaken (violate) the
          postconditions for the Rectangle setters, which state that
          dimensions can be modified independently.

        * Mutability is a key issue here. If Square and Rectangle had
          only getter methods (i.e. they were immutable objects), then
          no violation of LSP could occur.

   Hard to prove (to say the least):
   * If q is the property "method for always terminates", then it is
     impossible for a program (compiler) to verify that it holds true
     for some subtype S of T even if q does hold for T.

   * The principle is useful however in reasoning about the design of
     class hierarchies:
        * Preconditions cannot be strengthened in a subtype.

        * Postconditions cannot be weakened in a subtype.

        * Invariants of the supertype must be preserved in a subtype.

Modules
-------

A module is a program unit which is an (more or less) independent
entity.  A module consists of a number of definitions (of types,
variables, functions, procedures and so on), with a clearly defined
interface stating what it exports to other modules which use it.
Modules have a number of advantages for the construction of large
programs.
   * Modules facilitate parallel and independent development

   * Modules facilitate separate compilation

   * Modules facilitate code reuse
   Modules are used to construct libraries, ADTs, classes, interfaces,
and implementations.  A module is the compilation unit. A module which
contains only type abstractions is a specification or interface module.

   In program construction the module designer must answer the
following questions.
   * What is the module's purpose?

   * How does it achieve that purpose?
   Programming in the large is concerned with programs that are not
comprehensible by a single individual and are developed by teams of
programmers. At this level programs must consist of modules that can be
written, compiled, and tested independently of other modules. A module
has a single purpose, and has a narrow interface to other modules. It
is likely to be reusable (able to be incorporated into may programs)
and modifiable with out forcing changes in other modules.

   Modules must provide answers to two questions:
   * What is the purpose of the module?

   * How does it achieve that purpose?
   The what is of concern to the user of the module while the how is of
concern to the implementer of the module.

   Functions and procedures are simple modules. Their signature is a
description of what they do while their body describes how it is
achieved. More typically a module encapsulates a group of components
such as types, constants, variables, procedures, functions and so on.

   To present a narrow interface to other modules, a module makes only
a few components visible outside. Such components are said to be
exported by the module. The other components are said to be hidden
inside the module. The hidden components are used to implement the
exported components.

   Access to the components is often by a qualified name - module name.
component name. When strong safety considerations are important,
modules using components of another module may be required to
explicitly import the required module and the desired components.

2.9 Virtual Machines
====================

There are no compilers or interpreters. In reality, there are only
translators that convert one form into another.

   * Sometimes, the next form is shorter than the one before, so 2+2
     becomes 4, That is typically called evaluation.

   * Sometimes, the next form is longer than the one before when all
     the details of the input are added to the output. This is
     typically called translation. Sometimes, translation is followed
     by some clever reorganizations (e.g. for optimization).
   For example, this is a language called "C" that computes the
greatest common divisor:
unsigned int gcd (unsigned int a, unsigned int b)
{
    if (a == 0 &&b == 0)
        b = 1;
    else if (b == 0)
        b = a;
    else if (a != 0)
        while (a != b)
            if (a <b)
                b -= a;
            else
                a -= b;
    return b;
}

   And this another language, called the "WATCOM C/C++ v10.0a
assembler" that is generated by a "C" to "assembler" translator:
 gcd:   mov     ebx,eax
        mov     eax,edx
        test    ebx,ebx
        jne     L1
        test    edx,edx
        jne     L1
        mov     eax,1
        ret
 L1:    test    eax,eax
        jne     L2
        mov     eax,ebx
        ret
 L2:    test    ebx,ebx
        je      L5
 L3;    cmp     ebx,eax
        je      L5
        jae     L4
        sub     eax,ebx
        jmp     L3
 L4:    sub     ebx,eax
        jmp     L3
 L5:    ret
 Sometimes translation + optimization takes so long, that it is worth
while caching the translated form (so if we ever need it again, we just
run the cached form). This is called compilation

   Every translation is ready by an interpreter. Some interperators are
actual silicon hardware. If we translate down to this form, our binary
code it sloshes around, and gets translated into (say) changes to
pixels on the screen or changes to the contents of a file.

   We call silicon interpreters actual machines and the all the other
interpreters that read all the other non-binary translations virtual
machines (VM). And any computation is really a sequence of translations
down a hierachy of virtual machines; e.g. example:

requirements document # translated by "human" into ..
deisgn notation       # e.g. UML, translated to "C++" by "CAD tool"
"c++"                 # older versions of "c++" translated to "c"
"c"                   # and so it goes on
assembler
machine code
binary                # and finally...
-------
silicon

Examples of virtual machines
============================

   * The lambda calculus: the grand-daddy of them all: now 90+ years
     old. The core of LISP.

   * Resolution: the basis of logic programming. The code of Prolog.

   * The Smalltalk VM, which is quite old (1970s) and was useful for
     debugging VM technology.

   * The JAVA virtual machine which has been used to implement over 60
     languages (http://en.wikipedia.org/wiki/List_of_JVM_languages)
     including JAVA (naturally), Awk, TCL, JavaScript, Ruby, Lua,
     Scheme, PHP, Pythom.

   * Parrot VMwhich has been used to implement over 50 langauges
     (http://trac.parrot.org/parrot/wiki/Languages) including Tcl,
     Java, Javascript, Ruby, Lua, Scheme, PHP, Python, and Perl.

   * VirtualBox, VMware, etc that let you run one operating system
     inside another. For example, here is LINUX running VISTA:

   The advantages list of pros and cons of virtual machines is based on
some excellent article by Wellie Chao
(http://www.devx.com/vmspecialreport/Article/30383).

VM: Disadvantages
=================

Runtimes
--------

Every layer of translation slows down the computer. This is less of a
problem these days (faster CPUs, better optimizers) but it is something
to bear in mind.

Security
--------

I'm going to let you run any old program inside a VM on my hardware?
And that program could (say) launch a denial of service of attack on
China without me knowing about it? And, if that program breaks through
the walls around the virtual machine, it could take all the data on my
machine?

   Yeah, right, that'll work.

Trust
-----

Now, my business critical apps are running on someone else's machines.
I do not control my own infrastructure. Can I live with that?

VM: Advantages
==============

Mobility
--------

To run N languages on P platforms, just port take a VM that runs the N
languges, then port it once for each platform.

   Heck, some one has probably done this already if it is a common
language (like JAVA) or a poplular plaform (like Windows, Linux, Mac).
Which means that, to run your code on many platforms, just make it
compatiable with a VM that runs on those platforms.

   Most of the virtual machine software on the market today stores a
whole disk in the guest environment as a single file in the host
environment. Snapshot and rollback capabilities are implemented by
storing the change in state in a separate file in the host information.

Isolation
---------

Running everything on one machine would be great if it all worked, but
many times it results in undesirable interactions or even outright
conflicts. The cause often is software problems or business
requirements, such as the need for isolated security. Virtual machines
allow you to isolate each application (or group of applications) in its
own sandbox environment. The virtual machines can run on the same
physical machine (simplifying IT hardware management), yet appear as
independent machines to the software you are running.

   If one virtual machine goes down due to application or operating
system error, the others continue running, providing services your
business needs to function smoothly.

Ease of Testing
---------------

Virtual machines let you test scenarios easily. Most virtual machine
software today provides snapshot and rollback capabilities. This means
you can stop a virtual machine, create a snapshot, perform more
operations in the virtual machine, and then roll back again and again
until you have finished your testing.

CLoud Computing
---------------

Once you can run N copies on P platforms, why keep P small? Why not,
instead, keep hopping your applciations around to any space CPU,
whereever it appears?

   VMs make it very easy for someone to sell your their spare CPU. They
don' have to deal with the details of your application (which can be
quirky++). Instead, they just have to advertise that they handle a
small number of virtual machines.

Reality Check
=============

Data Consistency Properties and the Trade-offs in Commercial Cloud
Storages: the Consumers' Perspective
(http://www.nicta.com.au/research/research_publications/show?id=4341),
Zhao Liang, Liu Anna, Keung Jacky, Asia Pacific Software Engineering
Conference, Dec 2010

   Expected behavior: cloud scales to handle more http requests, as
needed.

   Actual (observed on Amazon Web Services Google App Engine, Microsoft
Windows Azure):

   Lesson: cloud _can_ be good, but current commercial servings _could_
be improved.

2.10 Translation
================

(This lecture comes from the excellent lectures of Anthony A. Aaby).

   A computer constructed from actual physical devices is termed an
actual computer or hardware computer. From the programming point of
view, it is the instruction set of the hardware that defines a machine.
An operating system is built on top of a machine to manage access to
the machine and to provide additional services. The services provided
by the operating system constitute another machine, a virtual machine.

   A programming language provides a set of operations. Thus, for
example, it is possible to speak of a Java computer or a Haskell
computer. For the programmer, the programming language is the computer;
the programming language defines a virtual computer. The virtual
machine for Simple consists of a data area which contains the
association between variables and values and the program which
manipulates the data area.

   Between the programmer's view of the program and the virtual machine
provided by the operating system is another virtual machine. It
consists of the data structures and algorithms necessary to support the
execution of the program. This virtual machine is the run time system
of the language. Its complexity may range in size from virtually
nothing, as in the case of FORTRAN, to an extremely sophisticated
system supporting memory management and inter process communication as
in the case of a concurrent programming languages.

   User programs constitute another class of virtual machines.

   A language translator is a program which translates programs from
source language into an equivalent program in an object language. The
source language is usually a high-level programming language and the
object language is usually the machine language of an actual computer.
From the pragmatic point of view, the translator defines the semantics
of the programming language, it transforms operations specified by the
syntax into operations of the computational model--in this case, to
some virtual machine. Context-free grammars are used in the
construction of language translators. Since the translation is based on
the syntax of the source language, the translation is said to be
syntax-directed.

   A compiler is a translator whose source language is a high-level
language and whose object language is close to the machine language of
an actual computer. The typical compiler consists of an analysis phase
and a synthesis phase.

   In contrast with compilers an interpreter is a program which
simulates the execution of programs written in a source language.
Interpreters may be used either at the source program level or an
interpreter may be used it interpret an object code for an idealized
machine. This is the case when a compiler generates code for an
idealized machine whose architecture more closely resembles the source
code.

   There are several other types of translators that are often used in
conjunction with a compiler to facilitate the execution of programs. An
assembler is a translator whose source language (an assembly language)
represents a one-to-one transliteration of the object machine code.
Some compilers generate assembly code which is then assembled into
machine code by an assembler. A loader is a translator whose source and
object languages are machine language. The source language programs
contain tables of data specifying points in the program which must be
modified if the program is to be executed. A link editor takes
collections of executable programs and links them together for actual
execution. A preprocessor is a translator whose source language is an
extended form of some high-level language and whose object language is
the standard form of the high-level language.

   The typical compiler consists of several phases each of which passes
its output to the next phase

   * The lexical phase (scanner) groups characters into lexical units
     or tokens. The input to the lexical phase is a character stream.
     The output is a stream of tokens. Regular expressions are used to
     define the tokens recognized by a scanner (or lexical analyzer).
     The scanner is implemented as a finite state machine.

   * The parser groups tokens into syntactical units. The output of the
     parser is a parse tree representation of the program. Context-free
     grammars are used to define the program structure recognized by a
     parser. The parser is implemented as a push-down automata.

   * The contextual analysis phase analyzes the parse tree for
     context-sensitive information often called the static semantics.
     The output of the contextual analysis phase is an annotated parse
     tree. Attribute grammars are used to describe the static semantics
     of a program.

   * The optimizer applies semantics preserving transformation to the
     annotated parse tree to simplify the structure of the tree and to
     facilitate the generation of more efficient code.

   * The code generator transforms the simplified annotated parse tree
     into object code using rules which denote the semantics of the
     source language.

   * The peep-hole optimizer examines the object code, a few
     instructions at a time, and attempts to do machine dependent code
     improvements.

   (BTW, contrast the complexity of the above with the simplicity of
LISP for defining new languages. When is the above complexity required?
Avoidable?)

The Scanner
===========

The scanner groups the input stream (of characters) into a stream of
tokens (lexeme) and constructs a symbol table which is used later for
contextual analysis. The lexemes include
   * Key words,

   * identifiers,

   * operators,

   * constants: numeric, character, special, and Witem comments.
   The lexical phase (scanner) groups characters into lexical units or
tokens. The input to the lexical phase is a character stream. The
output is a stream of tokens. Regular expressions are used to define
the tokens recognized by a scanner (or lexical analyzer). The scanner
is implemented as a finite state machine.

   Lex and Flex are tools for generating scanners is C. Flex is a
faster version of Lex.

   Example Lex file

   INPUT:

abc123z.!&*2ghj6

   ANALYZER
/*** Definition section ***/

%{
/* C code to be copied verbatim */
#include <stdio.h>
%}

/* This tells flex to read only one input file */
%option noyywrap

%%
    /*** Rules section ***/

    /* [0-9]+ matches a string of one or more digits */
[0-9]+  {
            /* yytext is a string containing the matched text. */
            printf("Saw an integer: %s\n", yytext);
        }

.       {   /* Ignore all other characters. */   }

%%
/*** C Code section ***/

int main(void)
{
    /* Call the lexer, then quit. */
    yylex();
    return 0;
}
 OUTPUT:
Saw an integer: 123
Saw an integer: 2
Saw an integer: 6

The Parser
==========

The parser groups tokens into syntactical units. The output of the
parser is a parse tree representation of the program. Context-free
grammars are used to define the program structure recognized by a
parser. The parser is implemented as a push-down automata.

   Yacc and Bison are tools for generating bottom-up parsers in C.
Bison is a faster version of Yacc. Jack is a tool for generating
scanners and top-down parsers in Java.

   Example parse tree for a simple English sentence

Symbol Tables and Error Handlers
================================

In addition to a data stream passing through the phases of the
compiler, additional information acquired during a phase may be needed
by a later phase. The symbol table is used to store the names
encountered in the source program and relavant attributes. The
information in the symbol table is used by the semantic checker when
applying the context-senitive rules and by the code generator. The
error handler is used to report and recover from errors encountered in
the source.

Contextual Checkers
===================

Contextual checkers analyze the parse tree for context-sensitive
information often called the static semantics. The output of the
semantic analysis phase is an annotated parse tree. Attribute grammars
are used to describe the static semantics of a program.

   This phase is often combined with the paser. During the parse,
information concerning variables and other objects is stored in a
symbol table. The information is utilized to perform the
context-sensitive checking.

Intermediate Code Generator
===========================

The data structure passed between the analysis and synthesis phases is
called the intermediate representation (IR)of the program. A well
designed intermediate representation facilitates the independence of
the analysis and syntheses (front- and back-end) phases. Intermedate
representations may be
   * assembly language like or

   * be an abstract syntax tree.

Code Optimizer
==============

Restructuring the parse tree to reduce its size or to present an
equivalent tree from which the code generator can produce more
efficient code is called optimization.

   It may be possible to restructure the parse tree to reduce its size
or to present a parse to the code generator from which the code
generator is able to produce more efficient code. Some optimizations
that can be applied to the parse tree are illustrated using source code
rather than the parse tree.

Loop-Constant code motion
-------------------------

From:
       while (count < limit) do
          INPUT SALES;
          VALUE := SALES * ( MARK_UP + TAX );
          OUTPUT := VALUE;
          COUNT := COUNT + 1;
       end;
 to:
       TEMP :=  MARK_UP + TAX;
       while (COUNT < LIMIT) do
          INPUT SALES;
          VALUE := SALES * TEMP;
          OUTPUT := VALUE;
          COUNT := COUNT + 1;
       end;

Induction variable elimination
------------------------------

Most program time is spent in the body of loops so loop optimization
can result in significant performance improvement. Often the induction
variable of a for loop is used only within the loop. In this case, the
induction variable may be stored in a register rather than in memory.
And when the induction variable of a for loop is referenced only as an
array subscript, it may be initialized to the initial address of the
array and incremented by only used for address calculation. In such
cases, its initial value may be set

   From:
       For I := 1 to 10 do
          A[I] := A[I] + E
 to:
       For I := address of first element in A
             to address of last element in A
             increment by size of an element of A do
          A[I] := A[I] + E

Common subexpression elimination
--------------------------------

From:
      A := 6 * (B+C);
      D := 3 + 7 * (B+C);
      E := A * (B+C);
 to:
      TEMP := B + C;
      A    := 6 * TEMP;
      D    := 3 * 7 * TEMP;
      E    := A * TEMP;

Mathematical identities
-----------------------

      a*b + a*c --> a*(b+c)
      a - b --> a + ( - b )

Code Generator
==============

The code generator transforms the intermediate representation into
object code using rules which denote the semantics of the source
language. These rules are define a translation semantics.

   The code generator's task is to translate the intermediate
representation to the native code of the target machine. The native
code may be an actual executable binary, assembly code or another
high-level language. Producing low-level code requires familiarity with
such machine level issues such as

   * data handling

   * machine instruction syntax

   * variable allocation

   * program layout

   * registers

   * instruction set

   The code generator may be integrated with the parser.

   As the source program is processed, it is converted to an internal
form. The internal representation in the example is that of an implicit
parse tree. Other internal forms may be used which resemble assembly
code. The internal form is translated by the code generator into object
code. Typically, the object code is a program for a virtual machine.
The virtual machine chosen for Simp consists of three segments. A data
segment, a code segment and an expression stack.

   The data segment contains the values associated with the variables.
Each variable is assigned to a location which holds the associated
value. Thus, part of the activity of code generation is to associate an
address with each variable. The code segment consists of a sequence of
operations. Program constants are incorporated in the code segment
since their values do not change. The expression stack is a stack which
is used to hold intermediate values in the evaluation of expressions.
The presence of the expression stack indicates that the virtual machine
for Simp is a "stack machine".

Statement translation
=====================

The assignment, if, while, read and write statements are translated as
follows:

Peephole Optimizer
==================

Peephole optimizers scan small segments of the target code for standard
replacement patterns of inefficient instruction sequences. The peephole
optimizer produces machine dependent code improvements. It works by
recognising sets of instructions that don't actually do anything, or
that can be replaced by a leaner set of instructions.

Strength folding
----------------

Replace slow operations with faster ones. E.g.
   * Replace "2*x" with "x+x".

   * Replace "2x" with "shift left x"

Constant folding
----------------

   * Replace "I := 4 + J - 5" with "I := J - 1"

   * Replace "I := 3; J := I + 2" with "I := 3; J := 5"

Remove redundant code:
----------------------

 a = b + c;
 d = a + e;

is straightforwardly implemented as
MOV b, R0  # Copy b to the register
ADD c, R0  # Add  c to the register, the register is now b+c
MOV R0, a  # Copy the register to a
MOV a, R0  # Copy a to the register
ADD e, R0  # Add  e to the register, the register is now a+e [(b+c)+e]
MOV R0, d  # Copy the register to d

   but can be optimised to

MOV b, R0 # Copy b to the register
ADD c, R0 # Add c to the register, which is now b+c (a)
MOV R0, a # Copy the register to a
ADD e, R0 # Add e to the register, which is now b+c+e [(a)+e]
MOV R0, d # Copy the register to d
 In essence, why move "a" around? Just use it in place.

   Furthermore, if the compiler knew that the variable a was not used
again, the middle operation could be omitted.

Combine Operations
------------------

Replace several operations with one equivalent.

Algebraic Laws
--------------

Use algebraic laws to simplify or reorder instructions.

Special Case Instructions
-------------------------

Use instructions designed for special operand cases.

Address Mode Operations
-----------------------

Use address modes to simplify code.

WARNING
-------

Note: peephole optimization can be very machine dependent!

2.11 Logic Programming
======================

_ (Credits: This material comes from Markus Triska and Thorsten
Joachims and John Fisher, with extensions by Tim Menzies. We also use
material from www.dataminingtools.net. )_

   The language Prolog is the Fortran of logic programming: it was the
first of its kind, it was much criticized, and it is still widely used.

   George Santayana: "Those who do not remember the past are condemned
to repeat it."

   Tim Menzies: "Those who do not study Prolog are condemned to repeat
it."

Prolog: Yet Another Paradigm
============================

In LISP, everything is a _lambda body_ and computation is evaluation
within the environment of the current lambda.

   In Smalltalk, everything is an _object_ (even _Object_) and
computation is message sends between objects.

   In OCAML, everything is a _type_ and computation is a process of
converting between types.

   In Prolog, everything is a _predicate_ and computation is a process
of recursively matching to predicates (possibly, with side-effects).

Predicates
==========

While functions map inputs to outputs...
   * predicates define constraints on variables.

   * So functions _run_ but predicates _match_.
   And while functions return some output, predicates only return yes
or no. If "yes", then as a side effect, they may add bindings to
variables.

Terms
=====

Predicates are build from _terms_:

   Terms are are either _variable_ or _nonvar_.  Nonvars are either
_compound_ or _atomic_ (and these divide into _atoms_ or _numbers_).

Term
   Variable
   NonVar
      Compound
      Atomic
         Atom
         Number

   Variables are empty slots- boxes, waiting to be filled.

   Terms have an _functor_ and an _arity_. E.g. the following term has
a functor/arity of emp/3:

emp(tim,30,male).

   Terms contain terms (recursively), one for each arity; e.g.
emp(name(tim), age(30), sex(male))
 Here:
   * Argument three is a term of arity one with a functor of "sex":
     sex(male);

   * Recursively, that term has an arity of one:
        * whose first argument is a term with arity zero: male.

   Terms with an arity of zero are _atoms_.  For example, in the above,
the atoms are:

emp
name
tim
age
sex
male
 The other atomic terms are numbers (integers or floats).

Predicates = Trees of Terms
===========================

emp(tim, 23, male)
    emp/3
        tim
        23
        male
 2+3
    (+)/2
        2
        3

   (note : some unary and binary functors can be written in a prefix or
infix notation. e.g. `2+3' is shorthand for `+(2,3)'.)

   10-10*3

    -/2
        10
            * / 2
                10
                3
 - x
    -/1
        x
 + y
    +/1
        y
 age(Dob,Age) :- now(Now), Age is Now - Dob.
    :-/2
            age/2
                A
                B
            ,/2
                    now/1
                        C
                    is/2
                        B
                            -/2
                                C
                                A
 :- now(Now), print(Now))

    :-/1
            ,/2
                    now/1
                        A
                    print/1
                        B

The Standard "Family" Database Example
======================================

(Adapted from Robert F. Rossa: rossa [at] csm.astate.edu).

   Prolog programs as databases

   We show below a Prolog program consisting entirely of simple clauses
or facts. This set of facts is a database about a family. Note that all
the gender facts are grouped together, then all the father facts, then
all the mother facts. Many versions of Prolog demand that similar
clauses be grouped together.

/* family.pl - a simple database for a family */
gender(al,male).
gender(anne,female).
gender(arthur,male).
gender(amber,female).
gender(boris,male).
gender(barbara,female).
gender(betty,female).
gender(buck,male).
gender(carla,female).
gender(charles,male).
gender(cora,female).
gender(cuthbert,male).
gender(cecilia,female).
gender(calvin,male).

father(arthur,buck).
father(al,buck).
father(amber,buck).
father(anne,boris).
father(barbara,charles).
father(betty,cuthbert).
father(boris,charles).
father(buck,calvin).

mother(al,barbara).
mother(anne,betty).
mother(arthur,barbara).
mother(amber,barbara).
mother(boris,carla).
mother(barbara,carla).
mother(betty,cora).
mother(buck,cecilia).
 We can load this database into a Prolog interpreter.
swipl -f family.pl
 The interpreter waits for queries. Every query must end with a period.
When we query the interpreter, it will give us the first answer it
finds, based on the facts in the database. If we want more answers, we
enter a semicolon. If we don't want any more answers to that query, we
just enter a carriage return. Thus consider the sequence that follows.
?- father(X,Y).
X=arthur,
Y=buck;

X=al,
Y=buck;

X=amber,
Y=buck;

X=anne,
Y=boris;

X=barbara,
Y=charles;

X=betty,
Y=cuthbert;

X=boris,
Y=charles;

X=buck,
Y=calvin

no
?-
 The "no" simply indicates that there were no more answers. Prolog will
answer "yes" or "no" depending on the truth or falsehood of a simple
query. Thus:
?- mother(al,betty).
no
?- mother(al,barbara).
yes
?-
 We can build more complex queries like the following, to find a
grandmother of al.
?- mother(al,X),mother(X,Y).
X=barbara,
Y=carla

yes
?-
 By now you have observed that identifiers that start with an upper
case letter are variables, and those that start with lower case letters
are constants.  Rules

   We can add some intelligence to our facts by adding a clause that
tells how to figure out from the simple clauses whether Y is a parent
of X. The rules we add are
parent(X,Y) :- father(X,Y).
parent(X,Y) :- mother(X,Y).
 The symbol ':-' should be read as "if". Now we can query as follows.
?- parent(al,Y).
Y=buck;

Y=barbara

yes
?-
 We can now build a rule that uses the parent rules.  grandfather(X,Y)
:- parent(X,Z),father(Z,Y).  and ask questions like
?- grandfather(anne,Y).
Y=charles;

Y=cuthbert;

no
?-
 The scope of variables is one clause; there is no such thing as a
global variable.

Backtracking
============

When Prolog tries to answer a query, it goes through a matching
process. It tries to match the predicates on the right-hand side of the
rule from left to right, binding variables when it finds a match. If a
match fails, it may be because of the bindings in matches to the left.
In that case, the interpreter backtracks - it returns to the nearest
previous binding and tries to find a different match. If that fails, it
backtracks some more.

   Now we can use the builtin trace predicate to see what happens as
one of our rules is matched.
% swipl -f family.pl  -g true
/Users/timm/svns/wisp/var/timm/10/310/src/prolog/4/a/family.pl compiled 0.00 sec, 4,872 bytes
?- spy(grandfather).
% Spy point on grandfather/2
true.

[debug]  ?-  grandfather(al,X).
   Call: (7) grandfather(al, _G313) ? creep
   Call: (8) parent(al, _L175) ? creep
   Call: (9) father(al, _L175) ? creep
   Exit: (9) father(al, buck) ? creep
   Exit: (8) parent(al, buck) ? creep
   Call: (8) father(buck, _G313) ? creep
   Exit: (8) father(buck, calvin) ? creep
   Exit: (7) grandfather(al, calvin) ? creep
X = calvin ;
   Redo: (8) parent(al, _L175) ? creep
   Call: (9) mother(al, _L175) ? creep
   Exit: (9) mother(al, barbara) ? creep
   Exit: (8) parent(al, barbara) ? creep
   Call: (8) father(barbara, _G313) ? creep
   Exit: (8) father(barbara, charles) ? creep
   Exit: (7) grandfather(al, charles) ? creep
X = charles.

[debug]  ?-
 Note that rules in the database are tried in the order they appear in
the database.

   We can make Prolog print out all the answers to a question by
deliberately making it fail, using the fail predicate.

?- grandfather(X,Y),write('X='),write(X),write(', Y='),write(Y),nl,fail.
X=arthur, Y=calvin
X=al, Y=calvin
X=amber, Y=calvin
X=anne, Y=charles
X=al, Y=charles
X=anne, Y=cuthbert
X=arthur, Y=charles
X=amber, Y=charles
fail
?-

Negation as Failure
===================

It is important to realize that in a goal ?-not(g), if g has variables,
and some instance of these variables lead to satisfaction of g, then
?-not(g) fails. For example, consider the following 'bachelor program:
bachelor(P) :- male(P), not(married(P)).

male(henry).
male(tom).

married(tom).
 Then
?- bachelor(henry).
yes
?- bachelor(tom).
no
?- bachelor(Who).
Who= henry ;
no
?- not(married(Who)).
no.
 The first three responses are correct and as expected.  The answer to
the fourth query might have been unexpected at first.  But consider that
the goal `?-not(married(Who))' fails because for the variable binding
`Who=tom, married(Who)' succeeds, and so the negative goal fails. Thus,
negative goals `?-not(g)' with variables cannot be expected to produce
bindings of the variables for which the goal g fails.

List Processing
===============

Prolog lists have heads and tails (think "car" and "cdr").

   [a, b, c]

    . / 2
        a
            . / 2
                b
                    . / 2
                        c
                        []
 So we can write a list member predicate as follows:
member(A, [A|_]).
member(A, [_|B]) :-
        member(A, B).
 So, of course,...
?- member(a,[c,b,a]).
true
 But Prolog can backtrack to find all repeated members of a list:
?-    member(a,[c,a,b,a]).
true ;
true
 Also, we can find all members of a list:
?- member(X,[a,b,c]).
X = a;
X = b;
X = c
 Also, Prolog is a relational language. Variables are not inputs and
outputs but concepts woven together by constraints. Also, we only need
to partially specify the I/O to query those constraints:
?-  member(name=What, [age=20,shoesize=12,name=tim]).
What = tim .
 (If this is causing stress, just chant to yourself: in Prolog, we
don't code; rather, we draw the shape of the solution.)

   This can get really funky. Here's the standard definition of how to
append two lists:
append([], A, A).
append([A|B], C, [A|D]) :-
        append(B, C, D).
Which works in the expected way:
@verbatim
?- append([a,b,c],[d,e,f],Out).
Out = [a, b, c, d, e, f].
 But any of these arguments can be left unspecified to achieve neat
results:
; find the third thing in a list
?- append([ _, _, Third], _, [alice,john,mike,tim,veronica,wendy]).
Third = mike

; find the list before "tim"
?- append(Before, [tim | _], [alice,john,mike,tim,veronica,wendy]).
Before = [alice, john, mike]

; find the list after "tim"
?- append(_, [tim | After], [alice,john,mike,tim,veronica,wendy]).
After = [veronica, wendy]
 You can even write "member" using "append":
member1(X,L) :- append(_,[X|_],L).

?- member1(a,[b,c,a]).
true .

?- member1(X,[b,c,a]).
X = b ;
X = c ;
X = a ;
fail.

Prolog Speaks English
=====================

Prolog has a shorthand for writing grammar rules:
sentence         -->  nominal_phrase, verbal_phrase.
verbal_phrase    -->  modlist,verb.
nominal_phrase   -->  article, noun.
article          -->  [the].
noun             -->  [dog].
verb             -->  [runs].
verb             -->  [barks].
modlist          -->  [].
modlist          -->  [sadly], modlist.
 (Note that modlist is zero or more "sadly"s.).

   If we load this into PROLOG, we get
swipl -f english.pl
?- listing(sentence).
sentence(A, C) :-
	nominal_phrase(A, B),
	verbal_phrase(B, C).

true.

?- listing(verb).
verb([runs|A], A).
verb([barks|A], A).

true.

?-
 That is, PROLOG interprets grammars as rules. Terminals (like runs)
are assumed to be members of a list.

   We can ask PROLOG now, what sentences are valid in this grammar:
?- sentence(X,[]).
X = [the, dog, runs] ;

X = [the, dog, barks];

no
?-
 We can also ask, is a sentence valid:
?- sentence([the,dog,runs],X).
X = []
.

?- sentence([the,dog,sadly,sadly,sadly,runs],X).
X = []
.

?- sentence([the,dog,flies],X).
false.

?-

Prolog Speaks any Language you Like
===================================

Here is an embedded ALGOL-like language in Prolog. By Maud Dib
(http://muaddibspace.blogspot.com/2008/03/embedded-algol-like-language-in-prolog.html).

   Managing state:
change_member(_, N, [], [N]).
change_member(O, N, [O|XS], [N|XS]).
change_member(O, N, [X|XS], [X|YS]) :- change_member(O, N, XS, YS).
Define the language:
@verbatim
:- op(900, xfy, :=).
:- op(100, fx, [if, then, else]).
:- op(125, fx, [while,  return]).
:- op(125, yfx, do).
 Running a block:
run({Block},EnvI, O, Ret) :-
  run(Block, EnvI, O, Ret).
Do things, return the result of doing the last one:
@verbatim
run((First; Second), EnvI, O, Ret) :-
  run(First, EnvI, M, _),
  run(Second, M, O, Ret).
Do assignment.
@verbatim
run(Place := Expr, EnvI, O, void) :-
  eval(Expr, Value, EnvI),
  change_member(Place = _, Place = Value, EnvI, O), !.
 Do if-then-else..
run(if(Cond) then {This} else {That}, EnvI, O, Ret) :-
  eval(Cond, Value, EnvI),
  ( Value = true -> Body = This ; Body = That ),
  run(Body, EnvI, O, Ret).
 Do while.
run(while(Cond) do {Body}, EnvI, O, Ret) :-
  eval(Cond, Value, EnvI),
  ( Value = true ->
    run(Body, EnvI, M, _),
    run(while(Cond) do {Body}, M, O, Ret)
  ; O = EnvI, Ret = void
  ).
 Do a return value.
run(return Value, EnvI, O, Ret) :-
  eval(Value, Ret, EnvI), O = EnvI.
 Evaluate stuff
eval(Var,   Val,   Env) :- member(Var = Val, Env), !.
eval(Num,   Num,   _  ) :- number(Num), !.
eval(true,  true,  _  ).
eval(false, false, _  ).

eval(X + Y, Z, Env) :-
	eval(X, XV, Env),
	eval(Y, YV, Env),
	Z is XV + YV.
eval(X - Y, Z, Env) :-
	eval(X, XV, Env),
	eval(Y, YV, Env),
	Z is XV - YV.
eval(X * Y, Z, Env) :-
	eval(X, XV, Env),
	eval(Y, YV, Env),
	Z is XV * YV.
eval(X / Y, Z, Env) :-
	eval(X, XV, Env),
	eval(Y, YV, Env),
	Z is truncate(XV / YV).
eval(X = Y, B, Env) :-
	eval(X, XV, Env), eval(Y, YV, Env),
  	( XV = YV -> B = true ; B = false ).
eval(X < Y, B, Env) :-
	eval(X, XV, Env), eval(Y, YV, Env),
  	( XV < YV -> B = true ; B = false ).
eval(X > Y, B, Env) :-
  	eval(X, XV, Env), eval(Y, YV, Env),
  	( XV > YV -> B = true ; B = false ).
eval(not(P), B, Env) :- eval(P, PV, Env),
  	( PV = true -> B = false ; B = true ).
 factorial
factorial(N, {i := 1;
              n := N;
              while(n > 0) do {
                i := i * n;
                n := n - 1
              };
              return i}).

%% ?- factorial(5, P), run(P, [], _, X).
%% X = 120
 fibonacci
fibonacci(F, {i := 1; a := 1; b := 1;
              while(not(i = F)) do {
                a := a + b;
                b := a - b;
                i := i + 1
              };
              return b}).

%% ?- fibonacci(7, P), run(P, [], _, X).
%% X = 13
 pow2
pow2(N, {i := N;
         n := 1;
         while(not(i = 0)) do {
           i := i - 1;
           n := n * 2
         };
         return n}).

%% ?- pow2(8, P), run(P, [], _, X).
%% X = 256
 gcd
gcd(X, Y,
    {x := X;
     y := Y;
     while(not(x = 0)) do {
       if(x < y) then {
         y := y - x
       }
       else {
         x := x - y
       }
     };
     return y}).

%% ?- A is 2*2*5*7*13, B is 5*13*7*7, gcd(A, B, P), run(P, [], _, X).
%% A = 1820,
%% B = 3185,
%% X = 455
 isqrt
isqrt(N, {q := N; p := (q + N / q) / 2;
          while(q > p) do {
            q := p;
            p := (q + N / q) / 2
          };
          return p}).

%% ?- isqrt(81, P), run(P, [], _, X).

3 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:

3.1 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}'

3.2 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.

3.3 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.

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

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

3.4.1 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.

3.4.2 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 `deftest's 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.

3.4.3 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 `deftest's 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.

3.4.4 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 `deftest's 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*'.

3.5 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

3.5.1 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 `deftest's 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

3.5.2 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 `deftest's 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.

3.5.3 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 `deftest's 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.

3.5.4 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 `deftest's 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%.

3.6 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!

3.6.1 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 `person's. 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).

3.6.2 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.

3.6.3 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.

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

4.1 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.

5 Bibliography
**************

5.1 A to F
==========

stuff

5.2 G to M
==========

stuff

   Menzies90

   Menzies90

5.3 N to T
==========

stuff

5.4 U to Z
==========

stuff