% This file is part of Oaklisp.
%
% This program is free software; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% (at your option) any later version.
%
% This program is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.
%
% The GNU GPL is available at http://www.gnu.org/licenses/gpl.html
% or from the Free Software Foundation, 59 Temple Place - Suite 330,
% Boston, MA 02111-1307, USA


\chapter{Language}

This document is a description of one particular implementation of
Oaklisp, and therefore contains information that is subject to change
and may not be significant to users in any case.  For a description of
the language that does not contain a lot of arbitrary distinctions,
refer to \emph{The Oaklisp Language Manual}.

\section{Special Forms}

These special forms all work by magic, and can't be redefined or
shadowed.

\sform{\%quote}{x}
\doc{Does what you would expect.}

\sform{\%if}{predicate consequent alternative}
\doc{Does what you would expect.}

\sform{\%labels}{\lpar\lpar variable value\rpar\ldots\rpar form}
\doc{If all references to the labels are calls from tail recursive positions,
this is compiled using jumps. Otherwise, it is rewritten using
\df{let} and \df{set\protect\bang}.}

\sform{native-catch}{variable \dt body}
\doc{Evaluates \emph{body} within the lexical scope of \emph{variable},
which is bound to a catch tag that is valid within the dynamic scope
of this form.  This is actually macro expanded to something pretty
wierd.}

\sform{\%add-method}{\lpar operation \lpar type \dt ivarlist\rpar \dt
arglist\rpar form}
\doc{Yields the specified method object.}

\sform{\%make-locative}{variable}
\doc{Returns a locative pointing to \emph{variable}.}

\sform{\%block}{\dt forms}
\doc{Making this a primitive special form simplifies the compiler.}


\section{Macros}

Most constructs that users think of as primitive are actually macros.
This simplifies the compiler by both reducing the number of special
forms to be handled and eliminating the need for the compiler to check
whether special forms it encounters are syntactically correct.

\mc{quote}{x}
\doc{\macdef{}{(\%quote \emph{x})}}

\mc{add-method}
{\lpar operation \lpar type \dt ivar-list\rpar \dt arg-list\rpar \dt body}
\doc{This turns into \df{\%add-method}, filling in the default type and
putting a block around the body if necessary.}

\mc{lambda}{arglist \dt body}
\doc{\macdef{}{(add-method ((make operation) \dt \emph{arglist}) \dt
\emph{body})} Functions are made by hanging methods off of \df{object}.
There is an optimization in the compiler that expands car-position
lambdas inline.}

\mc{catch}{var \dt body}
\doc{\macdef{}{(native-catch \emph{x} (let ((\emph{var} (lambda
(\emph{y}) (throw \emph{x} \emph{y})))) \dt \emph{body}))}}

\mc{define}{symbol value}
\doc{\macdef{}{(set!\ \emph{symbol value})}}

\mc{define}{\lpar\texttt{fluid} symbol\rpar value}
\doc{\macdef{}{(set!\ (fluid \emph{symbol}) \emph{value})}}

\mc{define}{\lpar variable \dt arglist\rpar \dt body}
\doc{\macdef{}{(set!\ \emph{variable} (lambda \emph{arglist} \dt \emph{body}))}}

\mc{set\protect\bang}{symbol value}
\doc{\macdef{}{(set!\ (contents (make-locative \emph{symbol}))
\emph{value})}}

\mc{set\protect\bang}{\lpar op $a_1 \ldots a_n$\rpar value}
\doc{\macdef{}{((setter \emph{op}) $a_1 \ldots a_n$ \emph{value})}}

\mc{set}{location value}
\doc{An obsolete form with semantics identical to \df{set\protect\bang}.}

\mc{make-locative}{symbol}
\doc{\macdef{}{(\%make-locative \emph{symbol})}}

\mc{make-locative}{\lpar op \dt args\rpar}
\doc{\macdef{}{((locater \emph{op}) \dt \emph{args})}}

\mc{if}{test thenform}
\doc{\macdef{}{(\%if \emph{test} \emph{thenform} (undefined-value))}}

\mc{if}{test thenform elseform}
\doc{\macdef{}{(\%if \emph{test} \emph{thenform} \emph{elseform})}}

\mc{fluid}{symbol}
\doc{\macdef{}{(\%fluid (quote \emph{symbol}))}}

\mc{bind-error-handler}{}
\doc{See the language manual for a semantic definition.}

\mc{catch-errors}{}
\doc{Implemented with \df{bind-error-handler} and \df{native-catch}.}

\mc{bind}{\lpar\lpar\lpar\texttt{fluid} symbol\rpar\ value\rpar \ldots
\rpar \dt body}
\doc{Implemented using \df{let} and \df{set\protect\bang}.  Hacks to
\df{native-catch} and \df{call/cc} are also necessary.  Essentially,
the bindings are pushed onto \df{fluid-bindings-alist} for the dynamic
scope of the \df{bind}.  For details, see Section~\ref{fluid-impl}.}

\mc{wind-protect}{before form after}
\doc{\macdef{} {(dynamic-wind (lambda () \emph{before}) (lambda ()
\emph{form}) (lambda () \emph{after}))}}

\mc{funny-wind-protect}{before abnormal-before form after abnormal-after}
\doc{A \df{wind-protect} evaluates \emph{before}, \emph{form}, and \emph{after},
returning the value of \emph{form}.  If \emph{form} is entered or exited
abnormally (due to \df{call/cc} or \df{catch}) the \emph{before} and
\emph{after} forms, respectively, are automatically executed.
\df{funny-wind-protect} is the same except that different guard forms
are evaluated depending on whether the dynamic context is entered or
exited normally or abnormally.}


The following macro definitions may be found in \emph{The Revised$^3$
Report on Scheme} \citep{R3RS}.

\mc{let}{}
\mc{let*}{}
\mc{cond}{}
\mc{or}{}
\mc{and}{}


\section{Primitive Types}

The following types are \emph{immediates}.  They have no instance
variables, occupy no heap storage, and are directly manipulated by the
micro-engine.  Their references have special tag bits.  See section
\ref{immtags}.

\ty{fixnum}
\ty{character}
\ty{locative}


\section{Open-Coded Operations}

Because arithmetic on \df{fixnum}s is so common, a special mechanism
is used to perform operations for which byte-codes exist.  When the
compiler sees one of these operations in a program, it emits the
corresponding byte-codes inline. At run-time, the micro-engine checks
the tag-bits of the operands to verify that they are \df{fixnum}s.  If
they are, the arithmetic is performed immediately.  Otherwise, a
hardware trap occurs which causes the usual search up the type
hierarchy to find the appropriate method to perform the operation.
The only restriction this places on the full generality of the usual
method system is that new methods cannot be defined for the simple
arithmetic operations on \df{fixnum}s.

The operations which fall under this restriction are the following:

\op{zero?}{number}
\op{{\protect\bang}=}{number1 number2}
\op{*}{number \ldots}
\op{+}{number \ldots}
\op{-}{number1 number2 \ldots}
\op{1+}{number}
\op{<}{number1 number2}
\op{<=}{number1 number2}
\op{=}{number1 number2}
\op{>}{number1 number2}
\op{>=}{number1 number2}
\op{ash-left}{integer1 integer2}
\op{ash-right}{integer1 integer2}
\op{bit-and}{integer1 integer2}
\op{bit-andca}{integer1 integer2}
\op{bit-equiv}{integer1 integer2}
\op{bit-nand}{integer1 integer2}
\op{bit-nor}{integer1 integer2}
\op{bit-not}{integer}
\op{bit-or}{integer1 integer2}
\op{bit-xor}{integer1 integer2}
\op{object-unhash}{integer}
\op{positive?}{number}
\op{quotient}{number1 number2}
\op{rot-left}{fixnum1 fixnum2}
\op{rot-right}{fixnum1 fixnum2}
\op{minus}{number}
\op{modulo}{number1 number2}
\op{negative?}{number}


The following operations are also open-coded and take type-mismatch
traps if necessary.  They can be add-method'ed to, but only for types
that are not handled by the microcode.  It should be clear from the
discussion below which types the bytecode expects.

\op{throw}{tag value}
\doc{Causes control to return from the \df{native-catch} form that
generated \emph{tag}.}

\lo{contents}{locative}
\doc{Dereferences \emph{locative}. \texttt{((setter contents)
\emph{locative} \emph{value})} puts \emph{value} in the cell pointed to by
\emph{locative}.}

\op{object-unhash}{fixnum}
\doc{Returns the object that the weak pointer \emph{fixnum} points to,
or \df{\#f} if the object has been reclaimed by the garbage collector.}






The following operations are open-coded, and the microcode can handle
objects of any type, so they can't be \df{add-method}'ed.

\op{get-type}{object}
\doc{Returns the type of \emph{object}.}

\op{eq?}{x y}
\doc{Determines whether \emph{x} and \emph{y} are the same object.
Implemented by checking if the references are identical.}

\op{object-hash}{x}
\doc{Returns a ``weak pointer'' to \emph{x}.}

\op{cons}{x y}
\doc{Conses \emph{x} onto \emph{y} in the usual lisp fashion.}

\op{identity}{x}
\doc{Returns \emph{x}.}

\op{list}{\dt args}
\doc{Constructs a list; \macdef{(list \emph{a} \emph{b} \emph{c})}{(cons
\emph{a} (cons \emph{b} (cons \emph{c} '()))).}  Actually, the \df{list}
operation is open coded and has \df{backwards-args-mixin} mixed into
the type, so its arguments are pushed onto the stack in left to right
order.  The code emitted for the operation itself is just a {\tt
(load-reg nil)} followed by a bunch of \df{reverse-cons} instructions,
one for each argument.}

\op{list*}{$a_1 \ldots a_n$}
\doc{\macdef{}{(cons $a_1 \ldots$ (cons $a_{n-1}$ $a_n$) $\ldots$).}
This is open coded in nearly the same way as \df{list}.}

\op{not}{x}
\doc{\macdef{}{(eq?\ \emph{x} \#f)}}

\op{null?}{x}
\doc{\macdef{}{(eq?\ \emph{x} '())}}


\op{second-arg}{x y \dt rest}
\doc{Returns \emph{y}.  Remember, Oaklisp does not guarantee any
particular order of evaluation of arguments.}



The following operations are open-coded, but the microcode traps out
if the arguments are not simple cons cells.  They can not be
\df{add-method}'ed to for the type \df{cons-pair}.

\lo{car}{pair}
\lo{cdr}{pair}
\lo{caar}{pair}
\lo{cadr}{pair}
\lo{cdar}{pair}
\lo{cddr}{pair}
\lo{caaar}{pair}
\lo{caadr}{pair}
\lo{cadar}{pair}
\lo{caddr}{pair}
\lo{cdaar}{pair}
\lo{cdadr}{pair}
\lo{cddar}{pair}
\lo{cdddr}{pair}
\lo{caaaar}{pair}
\lo{caaadr}{pair}
\lo{caadar}{pair}
\lo{caaddr}{pair}
\lo{cadaar}{pair}
\lo{cadadr}{pair}
\lo{caddar}{pair}
\lo{cadddr}{pair}
\lo{cdaaar}{pair}
\lo{cdaadr}{pair}
\lo{cdadar}{pair}
\lo{cdaddr}{pair}
\lo{cddaar}{pair}
\lo{cddadr}{pair}
\lo{cdddar}{pair}
\lo{cddddr}{pair}


\section{Subprimitives}

The following operations should be used only deep within the system.
Unless otherwise noted below, when a subprimitive encounters a domain
error normal Oaklisp code is not trapped to.  Rather, you're lucky if
the system dumps core.


\op{\%assq}{object alist}
\doc{Does the usual association list lookup, but assumes that \emph{alist}
is made out of simple cons pairs.  Passing it lazy lists or things
like that will crash the system.}

\oop{\%big-endian?}
\doc{Returns {\tt\#t} or {\tt\#f} depending on whether instructions
are ordered starting at the high half of a reference or the low half
of a reference, respectively.  On all machines that I know of, this
is the same as the endianity of bytes.}

\op{\%continue}{stack-photo}
\doc{Resumes \emph{stack-photo}, abandoning the current stack.}

\op{\%fill-continuation}{empty-stack-photo}
 \doc{Fills in the template stack snapshot \emph{empty-stack-photo}
with the appropriate information, copying sections of the stack into
the heap where necessary, and returns its argument.}

\op{\%filltag}{empty-catch-tag}
\doc{Fills in \emph{empty-catch-tag} with the current stack heights.}

\op{\%crunch}{data tag}
\doc{Returns a reference with the data portion \emph{data} and a tag
of \emph{tag}.  Traps if either argument is not a fixnum.}

\op{\%data}{x}
\doc{Returns the non-tag field of \emph{x} as a fixnum.}

\op{\%tag}{x}
\doc{Returns the tag of \emph{x} as a fixnum.}

\oop{\%gc}
\doc{Forces an immediate normal garbage collection.}

\oop{\%full-gc}
\doc{Forces an immediate full garbage collection.  At the end of the
full garbage collection, new space size is set back to its original
value.}


\op{\%get-length}{x}
\doc{Returns the number of storage cells occupied by \emph{x}.  Zero
for immediates.}

\op{\%increment-locative}{locative n}
\doc{Returns a locative to the cell \emph{n} beyond the cell pointed
to by \emph{locative}.}

\lo{\%load-bp-i}{n}
\doc{Loads the contents of self's instance variable number \emph{n}.
Not for the squeamish, as who is really ``self'' and who would be self
except that the compiler is compiling away intermediate lambdas is
very implementation specific.}

\op{\%make-cell}{value}
\doc{Returns a locative to a new cell containing \emph{value}.  Could
be defined with \texttt{(define (\%make-cell x) (make-locative x))}.}

\op{\%make-closed-environment}{$a_1 \ldots a_n$}
\doc{Returns a new environment containing $a_1 \ldots a_n$.  At least
one object is required.  To get an empty environment, look in
\df{\%empty-environment}.}


\op{\%print-digit}{n}
\doc{Prints \emph{n} as a single decimal digit to \df{stdout}.  Used
to indicate various error conditions during the boot process.}

\op{\%push}{\dt args}
\doc{Pushes \emph{args} onto the stack, returning (so to speak) the
leftmost argument.  This would be about the same as \texttt{values}, if
we had multiple value return.}

\oop{\%read-char}
\doc{Returns a character read from \df{stdin}.  No buffering.  For
use by the cold load stream.}

\oop{\%return}
\doc{Generates the \df{return} bytecode.  Doesn't push anything onto
the stack.  Will corrupt the stack unless you really know what you are
doing.}

\op{\%allocate}{type size}
\doc{Allocates a block of storage \emph{size} long, filling in the
type field with \emph{type}.  \emph{Type} should not be variable
length.}

\op{\%varlen-allocate}{type size}
\doc{Allocates a block of storage \emph{size} long, filling in the
type field with \emph{type} and the size field with \emph{size}.
\emph{Type} should be a variable length type.  Using this instead of
\df{\%allocate} where appropriate avoids a window of gc
vulnerability.}

\op{\%write-char}{char}
\doc{Writes the character \emph{char} to \df{stdout}.  No buffering or
anything.}

\op{\%{\protect\upar}super-tail}{type operation object}
\doc{Generates the \df{{\protect\upar}super-tail} bytecode, passing it
appropriate arguments.  This is used only used in the implementation
of \df{{\protect\upar}super}.  Once the compiler is modified to handle the
\df{{\protect\upar}super} construct directly this will no longer be needed.}





\section{Defined Types}

The following types are completely defined in Lisp.

\ty{object}
\doc{This type is the top of the inheritance hierarchy.
Ordinary functions are installed as methods for this type.}

\ty{type}
\doc{New types are generated by instantiating this type.}

\ty{variable-length-mixin}
\doc{This mixin allows each instance of a type to have a vector of anonymous
cells tacked  on the end. It also provides several low-level methods for
indexed references into such vectors.  Currently, the only variable-length
types are \df{vector}, \df{\%code-vector} and \df{\%closed-environment}.}

\ty{open-coded-mixin}
\doc{If this is mixed in to an operation, the compiler will send it a
\df{get-byte-code-list} message, and use the result instead of a regular
function call whenever the operation appears in a program.}


\ty{pair}
\ty{cons-pair}
\ty{null-type}
\ty{vector}
\ty{operation}
\ty{settable-operation}
\ty{locatable-operation}
\ty{\%method}
\ty{\%code-vector}
\ty{\%closed-environment}
\ty{locale}
\ty{general-error}
\ty{foldable-mixin}




\section{Defined Operations}

The methods for these operations are written in low level Oaklisp.

\op{apply}{operation $a_1 \ldots a_n$ arglist}
\doc{Calls \emph{operation} with arguments $a_1 \ldots a_n$ and the
contents of \emph{arglist}.  For instance, \evto{(apply + 1 2 '(3
4))}{10}.}

\op{make}{type \dt args}
 \doc{Returns a new instance of \emph{type} that has been initialized
by sending it an \df{initialize} message with the extra arguments
\emph{args} passed along.}

\op{\%install-method-with-env}{type operation code-body environment}
\doc{Adds the specified method to the search table of \emph{type}.  It
returns \emph{operation}, since this is what some instances of
\df{add-method} are compiled into.  Methods that don't close over
anything can refer to \df{\%empty-environment}, whose value is an
environment object whose vector portion has length zero.  It takes
care of instance variable mapping conflicts.}

\op{initialize}{object}
\doc{Returns \emph{object}.  This no-op is what is shadowed when you
define \df{initialize} methods for new types.  \texttt{(initialize
\emph{type} \emph{supertype-list} \emph{ivar-list})} does the work involved in
making a new type.  The list of supertypes is used to make a list of
all ancestors that is searched at run time to find methods for
operations. The ancestor tree is considered to be ordered from bottom
to top and from left to right while constructing this list, and
duplicates are removed.  An error is generated if more than one
top-wired type is found in the resulting ancestor list.  The
instance-variable map of the type is created, with any top-wired type
appearing at the beginning, and \df{variable-length-mixin} appearing
at the end if it is present.  Any method you define to handle
an \df{initialize} message should return \df{self}.}

\op{dynamic-wind}{before-op main-op after-op}
\doc{Calls the operation \emph{before-op}, calls the operation
\emph{main-op}, calls the operation \emph{after-op}, and returns the value
returned by \emph{main-op}.  If \emph{main-op} is exited abnormally,
\emph{after-op} is called automatically on the way out.  Similarly, if
\emph{main-op} is entered abnormally, \emph{before-op} is called
automatically on the way in.}

\op{call-with-current-continuation}{operation}
\doc{Calls \emph{operation} with one argument, the current
continuation.  The synonym \df{call/cc} is provided for those who feel
that \df{call-with-current-continuation} is excessively verbose.}