This document contains a minimal overview of the language CAT, the
(almost pure) functional language used to implement BADNOP.

First of all, this language is almost the same as Joy, with a slightly
different syntax and some extensions that make it easier to apply to
practical problems. You can find more information about Joy at:

	http://www.latrobe.edu.au/philosophy/phimvt/joy.html 

1. basic ideas
--------------

CAT is a language which bridges functional programming and imperative
programming. In essence, CAT is a functional language, which means it
has no 'real' assignments. Because of its concatenative nature, it can
be read as an imperative language like forth.

However, CAT does have emulated assignments, or 'functional
assignments'. It is possible to assign values to names. More
specificly, hierarchical names. Programs are just values in that
sense. 

The main difference between a pure imperative language is that these
assignments do not use mutation. An assignment updates the purely
functional data structure (tree) representing the name space, but
preserves it indefinitely.  Practically, untill it is no longer
accessible in which case it is garbage collected.

A consequence if this is that in any case, a function invocation can
be made in such a way that side effects (changed values associated to
names) are guaranteed not to occur as a net result. However, nothing
prevents a function to make a copy of the environment and change it
temporarily.

This illustrates the most important difference between Joy and CAT. In
joy, symbol bindings are permanent. Before a program runs, all symbol
bindings are known. In a CAT program, new values can be assigned
(temporarily) to names using the '!' word.

The exception is that I/O in CAT is not functional, and is implemented
as permanent side effects. In that sense CAT is more like Scheme than
Haskell. I am not getting into monads yet. This is mainly a practical
issue to keep some things simple.



2. help
-------

CAT is interpreted. Code is stored symbolicly. This enables it to be
self documenting to a large extent. To see a list of commands, type

     words p

The command 'words' stores on top of the parameter stack a list of all
names in the current environment, and the word 'p' prints the element
on the top of the parameter stack. The parameter stack is thus used to
pass data frome one piece of code to another.

To look at the implementation of a word, type something like

     (2dup) see

This result in a printout of the code implementing the word '2dup',
which is '2dup --> over over'. It is possible to put more than one
word in the list, like

     (2dup nip) see

Which prints out the previous code, and the code for 'nip'. If the
word is documented, you can access its documentation as

     (nip) help

This gives a description in the form: 
<input arguments> <output arguments> <comment>


3. semantics
------------

CAT uses the same data types as the underlying language Scheme. As a
matter of fact, the Scheme interpreter is still available. Try this:

     (+ 1 2) eval-scheme p

The semantics of the language is very simple. All symbols are
substituted by the subprogram they refer to, and executed. A subprogram
is stored either in symbolic form, like the 'see' instruction showed
in the previous section, or as a Scheme function. For example the word
'dup' is primitive in CAT, so '(dup) see' will tell you exactly that.

All non--symbols are copied to the top of the parameter stack. There
is only one way to 'quote' a symbol, meaning to not have it execute
code but just load it on the stack as a data value. This is to put it
in a list, and then take it out of the list like

     (symbol) car

The result of that code puts a single symbol 'symbol' on the top of
the parameter stack. You can inspect this stack by typing 'ps', which
in this case yields

     <1> symbol

The number indicates the number of elements. The elements are listed
with the topmost element to the right side. Entering '123' followed by
'ps' again thus gives:

     <2> symbol 123

There is no special syntax to quote only a single symbol, so a lot of
functions which operate only on a single symbol which has a tendency
to occur as a literal value, like 'see', actually operate on each
symbol in a list, whenever that makes sense.


4. abstraction
--------------

The way to abstract functionality is to give it a single name. This is
done using the function ':', which takes a single list as an
argument, and interprets the first element as a name, and the rest as
code implementing the action associated to that name. For example

     (count 1 +) :

will define a function named 'count' which performs the action of
incrementing the number on the top of the data stack. To see that it
works try '123 count p' and '(count) see'.



5. high level programming
-------------------------

Since code is data until you 'run' it, this creates a lot of
possibilities of passing functions to functions at runtime. This
approach is ubiquitous in functional programming, and CAT is no
exception. For example, conditional execution works like this

     (judge    10 < ("small" p) ("large" p) ifte) :

creates a word 'judge' that when given a number, will judge wether it
is small or large according to some arbitrary criterion. Try '4 judge'
and '13 judge'.

The function 'ifte' takes 3 arguments: a truth value, and two
programs, of which the first is executed when the value is true, and
the second is executed when the value is false.

Treating code as data as long as possible creates a lot of
flexibility. For example try

     ("yes!" p) dup concat run

This loads a simple program on the stack, duplicates it, concatenates
the two copies and then runs the resulting program.

The two words 'for-each' and 'map' use the same principle to perform
iteration over lists. The code used in the iteration is passed as data
on the stack. For example

     (1 2 3 4) ("number:" p p cr) for-each

This applies the code to each of the items in the list. The first 'p'
prints the string, while the second 'p' prints the number taken from
the list and passed as an argument by 'for-each'. The word 'map' does
something similar, but it modifies each element in place, try

     (1 2 3 4) (10 +) map p


6. memory model
---------------

CAT's memory (state) is organized as a tree, resembling a directory
structure. To inspect this tree you can use the word 'ls'

	   () ls

Each node in the tree is just a variable. The top level node is a
variable containing a dictionary. If a variable contains a dictionary,
it can be seen as a directory. For example, the variable '(core)'
contains the dictionary of core words. To see it try
   
           (core) ls

So variables are accessed hierarchically by lists of symbols. The
words '@' and '!' respectively fetch from and store to a variable.

Code is stored in variables too: the value is a program body, which is
a list of symbols and data items. Try

           (core unswons) @ p cr

Compare this to '(unswons) see'.