It lives!

[sod] / sod.tex

\documentclass[noarticle]{strayman}

\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
\usepackage{syntax}
\usepackage{sverb}
\usepackage{at}
\usepackage{mdwref}

\title{A Sensible Object Design for C}
\author{Mark Wooding}

\def\syntleft{\normalfont\itshape}
\let\syntright\empty

\def\ulitleft{\normalfont\sffamily}
\let\ulitright\empty

\let\listingsize\relax

\let\epsilon\varepsilon

\atdef <#1>{\synt{#1}}
\atdef "#1"{\lit*{#1}}
\atdef `#1'{\lit{#1}}
\atdef |#1|{\textsf{#1}}

\def\Cplusplus{C\kern-1pt++}
\def\Csharp{C\#}
\def\man#1#2{\textbf{#1}(#2)}

\begingroup\lccode`\~=`\
\lowercase{
\endgroup
\def\prog{%
  \sffamily%
  \quote%
  \let\oldnl\\%
  \obeylines%
  \tabbing%
  \global\let~\\%
  \global\let\\\textbackslash%
}
\def\endprog{%
  \endtabbing%
  \global\let\\\oldnl%
  \endquote%
}}

\begin{document}

\maketitle

\include{sod-tut}

%%%--------------------------------------------------------------------------
\chapter{Internals}

\section{Generated names}

The generated names for functions and objects related to a class are
constructed systematically so as not to interfere with each other.  The rules
on class, slot and message naming exist so as to ensure that the generated
names don't collide with each other.

The following notation is used in this section.
\begin{description}
\item[@<class>] The full name of the `focus' class: the one for which we are
  generating name.
\item[@<super-nick>] The nickname of a superclass.
\item[@<head-nick>] The nickname of the chain-head class of the chain
  in question.
\end{description}

\subsection{Instance layout}

%%%--------------------------------------------------------------------------
\section{Syntax}
\label{sec:syntax}

Fortunately, Sod is syntactically quite simple.  I've used a little slightly
unusual notation in order to make the presentation easier to read.
\begin{itemize}
\item $\epsilon$ denotes the empty nonterminal:
  \begin{quote}
    $\epsilon$ ::=
  \end{quote}
\item $[$@<item>$]$ means an optional @<item>:
  \begin{quote}
    \syntax{$[$<item>$]$ ::= $\epsilon$ | <item>}
  \end{quote}
\item @<item>$^*$ means a sequence of zero or more @<item>s:
  \begin{quote}
    \syntax{<item>$^*$ ::= $\epsilon$ | <item>$^*$ <item>}
  \end{quote}
\item @<item>$^+$ means a sequence of one or more @<item>s:
  \begin{quote}
    \syntax{<item>$^+$ ::= <item> <item>$^*$}
  \end{quote}
\item @<item-list> means a sequence of one or more @<item>s separated
  by commas:
  \begin{quote}
    \syntax{<item-list> ::= <item> | <item-list> "," <item>}
  \end{quote}
\end{itemize}

\subsection{Lexical syntax}
\label{sec:syntax.lex}

Whitespace and comments are discarded.  The remaining characters are
collected into tokens according to the following syntax.

\begin{grammar}
<token> ::= <identifier>
\alt <reserved-word>
\alt <string-literal>
\alt <char-literal>
\alt <integer-literal>
\alt <punctuation>
\end{grammar}

This syntax is slightly ambiguous.  The following two rules serve to
disambiguate:
\begin{enumerate}
\item Reserved words take precedence.  All @<reserved-word>s are
  syntactically @<identifier>s; Sod resolves the ambiguity in favour of
  @<reserved-word>.
\item `Maximal munch'.  In other cases, at each stage we take the longest
  sequence of characters which could be a token.
\end{enumerate}

\subsubsection{Identifiers} \label{sec:syntax.lex.id}

\begin{grammar}
<identifier> ::= <id-start-char> <id-body-char>$^*$

<id-start-char> ::= <alpha-char> $|$ "_"

<id-body-char> ::= <id-start-char> $|$ <digit-char>

<alpha-char> ::= "A" $|$ "B" $|$ \dots\ $|$ "Z"
\alt "a" $|$ "b" $|$ \dots\ $|$ "z"
\alt <extended-alpha-char>

<digit-char> ::= "0" $|$ <nonzero-digit-char>

<nonzero-digit-char> ::= "1" $|$ "2" $| \cdots |$ "9"
\end{grammar}

The precise definition of @<alpha-char> is left to the function
\textsf{alpha-char-p} in the hosting Lisp system.  For portability,
programmers are encouraged to limit themselves to the standard ASCII letters.

\subsubsection{Reserved words} \label{sec:syntax.lex.reserved}

\begin{grammar}
<reserved-word> ::=
"char" $|$ "class" $|$ "code" $|$ "const" $|$ "double" $|$ "enum" $|$
"extern" $|$ "float" $|$ "import" $|$ "int" $|$ "lisp" $|$ "load" $|$ "long"
$|$ "restrict" $|$ "short" $|$ "signed" $|$ "struct" $|$ "typename" $|$
"union" $|$ "unsigned" $|$ "void" $|$ "volatile"
\end{grammar}

Many of these are borrowed from~C; however, some (e.g., @"import" and
@"lisp") are not, and some C reserved words are not reserved (e.g.,
@"static").

\subsubsection{String and character literals} \label{sec:syntax.lex.string}

\begin{grammar}
<string-literal> ::= "\"" <string-literal-char>$^*$ "\""

<char-literal> ::= "'" <char-literal-char> "'"

<string-literal-char> ::= any character other than "\\" or "\""
\alt "\\" <char>

<char-literal-char> ::= any character other than "\\" or "'"
\alt "\\" <char>

<char> ::= any single character
\end{grammar}

The syntax for string and character literals differs from~C.  In particular,
escape sequences such as @`\textbackslash n' are not recognized.  The use
of string and character literals in Sod, outside of C~fragments, is limited,
and the simple syntax seems adequate.  For the sake of future compatibility,
the use of character sequences which resemble C escape sequences is
discouraged.

\subsubsection{Integer literals} \label{sec:syntax.lex.int}

\begin{grammar}
<integer-literal> ::= <decimal-integer>
\alt <binary-integer>
\alt <octal-integer>
\alt <hex-integer>

<decimal-integer> ::= <nonzero-digit-char> <digit-char>$^*$

<binary-integer> ::= "0" $($"b"$|$"B"$)$ <binary-digit-char>$^+$

<binary-digit-char> ::= "0" $|$ "1"

<octal-integer> ::= "0" $[$"o"$|$"O"$]$ <octal-digit-char>$^+$

<octal-digit-char> ::= "0" $|$ "1" $| \cdots |$ "7"

<hex-integer> ::= "0" $($"x"$|$"X"$)$ <hex-digit-char>$^+$

<hex-digit-char> ::= <digit-char>
\alt "A" $|$ "B" $|$ "C" $|$ "D" $|$ "E" $|$ "F"
\alt "a" $|$ "b" $|$ "c" $|$ "d" $|$ "e" $|$ "f"
\end{grammar}

Sod understands only integers, not floating-point numbers; its integer syntax
goes slightly beyond C in allowing a @`0o' prefix for octal and @`0b' for
binary.  However, length and signedness indicators are not permitted.

\subsubsection{Punctuation} \label{sec:syntax.lex.punct}

\begin{grammar}
<punctuation> ::= any character other than "\"" or "'"
\end{grammar}

Due to the `maximal munch' rule, @<punctuation> tokens cannot be
alphanumeric.

\subsubsection{Comments} \label{sec:lex-comment}

\begin{grammar}
<comment> ::= <block-comment>
\alt <line-comment>

<block-comment> ::=
  "/*"
  <not-star>$^*$ $($<star>$^+$ <not-star-or-slash> <not-star>$^*)^*$
  <star>$^*$
  "*/"

<star> ::= "*"

<not-star> ::= any character other than "*"

<not-star-or-slash> ::= any character other than "*" or  "/"

<line-comment> ::= "//" <not-newline>$^*$ <newline>

<newline> ::= a newline character

<not-newline> ::= any character other than newline
\end{grammar}

Comments are exactly as in C99: both traditional block comments `\texttt{/*}
\dots\ \texttt{*/}' and \Cplusplus-style `\texttt{//} \dots' comments are
permitted and ignored.

\subsection{Special nonterminals}
\label{sec:special-nonterminals}

Aside from the lexical syntax presented above (\xref{sec:lexical-syntax}),
two special nonterminals occur in the module syntax.

\subsubsection{S-expressions} \label{sec:syntax-sexp}

\begin{grammar}
<s-expression> ::= an S-expression, as parsed by the Lisp reader
\end{grammar}

When an S-expression is expected, the Sod parser simply calls the host Lisp
system's \textsf{read} function.  Sod modules are permitted to modify the
read table to extend the S-expression syntax.

S-expressions are self-delimiting, so no end-marker is needed.

\subsubsection{C fragments} \label{sec:syntax.lex.cfrag}

\begin{grammar}
<c-fragment> ::= a sequence of C tokens, with matching brackets
\end{grammar}

Sequences of C code are simply stored and written to the output unchanged
during translation.  They are read using a simple scanner which nonetheless
understands C comments and string and character literals.

A C fragment is terminated by one of a small number of delimiter characters
determined by the immediately surrounding context -- usually a closing brace
or bracket.  The first such delimiter character which is not enclosed in
brackets, braces or parenthesis ends the fragment.

\subsection{Module syntax} \label{sec:syntax-module}

\begin{grammar}
<module> ::= <definition>$^*$

<definition> ::= <import-definition>
\alt <load-definition>
\alt <lisp-definition>
\alt <code-definition>
\alt <typename-definition>
\alt <class-definition>
\end{grammar}

A module is the top-level syntactic item.  A module consists of a sequence of
definitions.

\subsection{Simple definitions} \label{sec:syntax.defs}

\subsubsection{Importing modules} \label{sec:syntax.defs.import}

\begin{grammar}
<import-definition> ::= "import" <string> ";"
\end{grammar}

The module named @<string> is processed and its definitions made available.

A search is made for a module source file as follows.
\begin{itemize}
\item The module name @<string> is converted into a filename by appending
  @`.sod', if it has no extension already.\footnote{%
    Technically, what happens is \textsf{(merge-pathnames name (make-pathname
    :type "SOD" :case :common))}, so exactly what this means varies
    according to the host system.} %
\item The file is looked for relative to the directory containing the
  importing module.
\item If that fails, then the file is looked for in each directory on the
  module search path in turn.
\item If the file still isn't found, an error is reported and the import
  fails.
\end{itemize}
At this point, if the file has previously been imported, nothing further
happens.\footnote{%
  This check is done using \textsf{truename}, so it should see through simple
  tricks like symbolic links.  However, it may be confused by fancy things
  like bind mounts and so on.} %

Recursive imports, either direct or indirect, are an error.

\subsubsection{Loading extensions} \label{sec:syntax.defs.load}

\begin{grammar}
<load-definition> ::= "load" <string> ";"
\end{grammar}

The Lisp file named @<string> is loaded and evaluated.

A search is made for a Lisp source file as follows.
\begin{itemize}
\item The name @<string> is converted into a filename by appending @`.lisp',
  if it has no extension already.\footnote{%
    Technically, what happens is \textsf{(merge-pathnames name (make-pathname
    :type "LISP" :case :common))}, so exactly what this means varies
    according to the host system.} %
\item A search is then made in the same manner as for module imports
  (\xref{sec:syntax-module}).
\end{itemize}
If the file is found, it is loaded using the host Lisp's \textsf{load}
function.

Note that Sod doesn't attempt to compile Lisp files, or even to look for
existing compiled files.  The right way to package a substantial extension to
the Sod translator is to provide the extension as a standard ASDF system (or
similar) and leave a dropping @"foo-extension.lisp" in the module path saying
something like
\begin{listing}
(asdf:operate 'asdf:load-op :foo-extension)
\end{listing}
which will arrange for the extension to be compiled if necessary.

(This approach means that the language doesn't need to depend on any
particular system definition facility.  It's bad enough already that it
depends on Common Lisp.)

\subsubsection{Lisp escapes} \label{sec:syntax.defs.lisp}

\begin{grammar}
<lisp-definition> ::= "lisp" <s-expression> ";"
\end{grammar}

The @<s-expression> is evaluated immediately.  It can do anything it likes.

\textbf{Warning!}  This means that hostile Sod modules are a security hazard.
Lisp code can read and write files, start other programs, and make network
connections.  Don't install Sod modules from sources that you don't
trust.\footnote{%
  Presumably you were going to run the corresponding code at some point, so
  this isn't as unusually scary as it sounds.  But please be careful.} %

\subsubsection{Declaring type names} \label{sec:syntax.defs.typename}

\begin{grammar}
<typename-definition> ::=
  "typename" <identifier-list> ";"
\end{grammar}

Each @<identifier> is declared as naming a C type.  This is important because
the C type syntax -- which Sod uses -- is ambiguous, and disambiguation is
done by distinguishing type names from other identifiers.

Don't declare class names using @"typename"; use @"class" forward
declarations instead.

\subsection{Literal code} \label{sec:syntax-code}

\begin{grammar}
<code-definition> ::=
  "code" <identifier> ":" <identifier> $[$<constraints>$]$
  "{" <c-fragment> "}"

<constraints> ::= "[" <constraint-list> "]"

<constraint> ::= <identifier>$^+$
\end{grammar}

The @<c-fragment> will be output unchanged to one of the output files.

The first @<identifier> is the symbolic name of an output file.  Predefined
output file names are @"c" and @"h", which are the implementation code and
header file respectively; other output files can be defined by extensions.

The second @<identifier> provides a name for the output item.  Several C
fragments can have the same name: they will be concatenated together in the
order in which they were encountered.

The @<constraints> provide a means for specifying where in the output file
the output item should appear.  (Note the two kinds of square brackets shown
in the syntax: square brackets must appear around the constraints if they are
present, but that they may be omitted.)  Each comma-separated @<constraint>
is a sequence of identifiers naming output items, and indicates that the
output items must appear in the order given -- though the translator is free
to insert additional items in between them.  (The particular output items
needn't be defined already -- indeed, they needn't be defined ever.)

There is a predefined output item @"includes" in both the @"c" and @"h"
output files which is a suitable place for inserting @"\#include"
preprocessor directives in order to declare types and functions for use
elsewhere in the generated output files.

\subsection{Property sets} \label{sec:syntax.propset}

\begin{grammar}
<properties> ::= "[" <property-list> "]"

<property> ::= <identifier> "=" <expression>
\end{grammar}

Property sets are a means for associating miscellaneous information with
classes and related items.  By using property sets, additional information
can be passed to extensions without the need to introduce idiosyncratic
syntax.

A property has a name, given as an @<identifier>, and a value computed by
evaluating an @<expression>.  The value can be one of a number of types,
though the only operators currently defined act on integer values only.

\subsubsection{The expression evaluator} \label{sec:syntax.propset.expr}

\begin{grammar}
<expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>

<term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor>

<factor> ::= <primary> | "+" <factor> | "-" <factor>

<primary> ::=
     <integer-literal> | <string-literal> | <char-literal> | <identifier>
\alt "?" <s-expression>
\alt "(" <expression> ")"
\end{grammar}

The arithmetic expression syntax is simple and standard; there are currently
no bitwise, logical, or comparison operators.

A @<primary> expression may be a literal or an identifier.  Note that
identifiers stand for themselves: they \emph{do not} denote values.  For more
fancy expressions, the syntax
\begin{quote}
  @"?" @<s-expression>
\end{quote}
causes the @<s-expression> to be evaluated using the Lisp \textsf{eval}
function.
%%% FIXME crossref to extension docs

\subsection{C types} \label{sec:syntax.c-types}

Sod's syntax for C types closely mirrors the standard C syntax.  A C type has
two parts: a sequence of @<declaration-specifier>s and a @<declarator>.  In
Sod, a type must contain at least one @<declaration-specifier> (i.e.,
`implicit @"int"' is forbidden), and storage-class specifiers are not
recognized.

\subsubsection{Declaration specifiers} \label{sec:syntax.c-types.declspec}

\begin{grammar}
<declaration-specifier> ::= <type-name>
\alt "struct" <identifier> | "union" <identifier> | "enum" <identifier>
\alt "void" | "char" | "int" | "float" | "double"
\alt "short" | "long"
\alt "signed" | "unsigned"
\alt <qualifier>

<qualifier> ::= "const" | "volatile" | "restrict"

<type-name> ::= <identifier>
\end{grammar}

A @<type-name> is an identifier which has been declared as being a type name,
using the @"typename" or @"class" definitions.

Declaration specifiers may appear in any order.  However, not all
combinations are permitted.  A declaration specifier must consist of zero or
more @<qualifiers>, and one of the following, up to reordering.
\begin{itemize}
\item @<type-name>
\item @"struct" <identifier>, @"union" <identifier>, @"enum" <identifier>
\item @"void"
\item @"char", @"unsigned char", @"signed char"
\item @"short", @"unsigned short", @"signed short"
\item @"short int", @"unsigned short int", @"signed short int"
\item @"int", @"unsigned int", @"signed int", @"unsigned", @"signed"
\item @"long", @"unsigned long", @"signed long"
\item @"long int", @"unsigned long int", @"signed long int"
\item @"long long", @"unsigned long long", @"signed long long"
\item @"long long int", @"unsigned long long int", @"signed long long int"
\item @"float", @"double", @"long double"
\end{itemize}
All of these have their usual C meanings.

\subsubsection{Declarators} \label{sec:syntax.c-types.declarator}

\begin{grammar}
<declarator> ::=
  <pointer>$^*$ <inner-declarator> <declarator-suffix>$^*$

<inner-declarator> ::= <identifier> | <qualified-identifier>
\alt "(" <declarator> ")"

<qualified-identifier> ::= <identifier> "." <identifier>

<pointer> ::= "*" <qualifier>$^*$

<declarator-suffix> ::= "[" <c-fragment> "]"
\alt "(" <arguments> ")"

<arguments> ::= <empty> | "..."
\alt <argument-list> $[$"," "..."$]$

<argument> ::= <declaration-specifier>$^+$ <argument-declarator>

<argument-declarator> ::= <declarator> | $[$<abstract-declarator>$]$

<abstract-declarator> ::=
  <pointer>$^+$ | <pointer>$^*$ <inner-abstract-declarator>

<inner-abstract-declarator> ::= "(" <abstract-declarator> ")"
\alt $[$<inner-abstract-declarator>$]$ <declarator-suffix>$^+$
\end{grammar}

The declarator syntax is taken from C, but with some differences.
\begin{itemize}
\item Array dimensions are uninterpreted @<c-fragments>, terminated by a
  closing square bracket.  This allows array dimensions to contain arbitrary
  constant expressions.
\item A declarator may have either a single @<identifier> at its centre or a
  pair of @<identifier>s separated by a @`.'; this is used to refer to
  slots or messages defined in superclasses.
\end{itemize}
The remaining differences are (I hope) a matter of presentation rather than
substance.

\subsection{Defining classes} \label{sec:syntax.class}

\begin{grammar}
<class-definition> ::= <class-forward-declaration>
\alt <full-class-definition>
\end{grammar}

\subsubsection{Forward declarations} \label{sec:class.class.forward}

\begin{grammar}
<class-forward-declaration> ::= "class" <identifier> ";"
\end{grammar}

A @<class-forward-declaration> informs Sod that an @<identifier> will be used
to name a class which is currently undefined.  Forward declarations are
necessary in order to resolve certain kinds of circularity.  For example,
\begin{listing}
class Sub;

class Super : SodObject {
  Sub *sub;
};

class Sub : Super {
  /* ... */
};
\end{listing}

\subsubsection{Full class definitions} \label{sec:class.class.full}

\begin{grammar}
<full-class-definition> ::=
  $[$<properties>$]$
  "class" <identifier> ":" <identifier-list>
  "{" <class-item>$^*$ "}"

<class-item> ::= <slot-item> ";"
\alt <message-item>
\alt <method-item>
\alt  <initializer-item> ";"
\end{grammar}

A full class definition provides a complete description of a class.

The first @<identifier> gives the name of the class.  It is an error to
give the name of an existing class (other than a forward-referenced class),
or an existing type name.  It is conventional to give classes `MixedCase'
names, to distinguish them from other kinds of identifiers.

The @<identifier-list> names the direct superclasses for the new class.  It
is an error if any of these @<identifier>s does not name a defined class.

The @<properties> provide additional information.  The standard class
properties are as follows.
\begin{description}
\item[@"lisp_class"] The name of the Lisp class to use within the translator
  to represent this class.  The property value must be an identifier; the
  default is @"sod_class".  Extensions may define classes with additional
  behaviour, and may recognize additional class properties.
\item[@"metaclass"] The name of the Sod metaclass for this class.  In the
  generated code, a class is itself an instance of another class -- its
  \emph{metaclass}.  The metaclass defines which slots the class will have,
  which messages it will respond to, and what its behaviour will be when it
  receives them.  The property value must be an identifier naming a defined
  subclass of @"SodClass".  The default metaclass is @"SodClass".
  %%% FIXME xref to theory
\item[@"nick"] A nickname for the class, to be used to distinguish it from
  other classes in various limited contexts.  The property value must be an
  identifier; the default is constructed by forcing the class name to
  lower-case.
\end{description}

The class body consists of a sequence of @<class-item>s enclosed in braces.
These items are discussed on the following sections.

\subsubsection{Slot items} \label{sec:sntax.class.slot}

\begin{grammar}
<slot-item> ::=
  $[$<properties>$]$
  <declaration-specifier>$^+$ <init-declarator-list>

<init-declarator> ::= <declarator> $[$"=" <initializer>$]$
\end{grammar}

A @<slot-item> defines one or more slots.  All instances of the class and any
subclass will contain these slot, with the names and types given by the
@<declaration-specifiers> and the @<declarators>.  Slot declarators may not
contain qualified identifiers.

It is not possible to declare a slot with function type: such an item is
interpreted as being a @<message-item> or @<method-item>.  Pointers to
functions are fine.

An @<initializer>, if present, is treated as if a separate
@<initializer-item> containing the slot name and initializer were present.
For example,
\begin{listing}
[nick = eg]
class Example : Super {
  int foo = 17;
};
\end{listing}
means the same as
\begin{listing}
[nick = eg]
class Example : Super {
  int foo;
  eg.foo = 17;
};
\end{listing}

\subsubsection{Initializer items} \label{sec:syntax.class.init}

\begin{grammar}
<initializer-item> ::= $[$"class"$]$ <slot-initializer-list>

<slot-initializer> ::= <qualified-identifier> "=" <initializer>

<initializer> :: "{" <c-fragment> "}" | <c-fragment>
\end{grammar}

An @<initializer-item> provides an initial value for one or more slots.  If
prefixed by @"class", then the initial values are for class slots (i.e.,
slots of the class object itself); otherwise they are for instance slots.

The first component of the @<qualified-identifier> must be the nickname of
one of the class's superclasses (including itself); the second must be the
name of a slot defined in that superclass.

The initializer has one of two forms.
\begin{itemize}
\item A @<c-fragment> enclosed in braces denotes an aggregate initializer.
  This is suitable for initializing structure, union or array slots.
\item A @<c-fragment> \emph{not} beginning with an open brace is a `bare'
  initializer, and continues until the next @`,' or @`;' which is not within
  nested brackets.  Bare initializers are suitable for initializing scalar
  slots, such as pointers or integers, and strings.
\end{itemize}

\subsubsection{Message items} \label{sec:syntax.class.message}

\begin{grammar}
<message-item> ::=
  $[$<properties>$]$
  <declaration-specifier>$^+$ <declarator> $[$<method-body>$]$
\end{grammar}

\subsubsection{Method items} \label{sec:syntax.class.method}

\begin{grammar}
<method-item> ::=
  $[$<properties>$]$
  <declaration-specifier>$^+$ <declarator> <method-body>

<method-body> ::= "{" <c-fragment> "}" | "extern" ";"
\end{grammar}

%%%--------------------------------------------------------------------------
\section{Class objects}

\begin{listing}
typedef struct SodClass__ichain_obj SodClass;

struct sod_chain {
  size_t n_classes;                     /* Number of classes in chain */
  const SodClass *const *classes;       /* Vector of classes, head first */
  size_t off_ichain;                    /* Offset of ichain from instance base */
  const struct sod_vtable *vt;          /* Vtable pointer for chain */
  size_t ichainsz;                      /* Size of the ichain structure */
};

struct sod_vtable {
  SodClass *_class;                     /* Pointer to instance's class */
  size_t _base;                         /* Offset to instance base */
};

struct SodClass__islots {

  /* Basic information */
  const char *name;                     /* The class's name as a string */
  const char *nick;                     /* The nickname as a string */

  /* Instance allocation and initialization */
  size_t instsz;                        /* Instance layout size in bytes */
  void *(*imprint)(void *);             /* Stamp instance with vtable ptrs */
  void *(*init)(void *);                /* Initialize instance */

  /* Superclass structure */
  size_t n_supers;                      /* Number of direct superclasses */
  const SodClass *const *supers;        /* Vector of direct superclasses */
  size_t n_cpl;                         /* Length of class precedence list */
  const SodClass *const *cpl;           /* Vector for class precedence list */

  /* Chain structure */
  const SodClass *link;                 /* Link to next class in chain */
  const SodClass *head;                 /* Pointer to head of chain */
  size_t level;                         /* Index of class in its chain */
  size_t n_chains;                      /* Number of superclass chains */
  const sod_chain *chains;              /* Vector of chain structures */

  /* Layout */
  size_t off_islots;                    /* Offset of islots from ichain base */
  size_t islotsz;                       /* Size of instance slots */
};

struct SodClass__ichain_obj {
  const SodClass__vt_obj *_vt;
  struct SodClass__islots cls;
};

struct sod_instance {
  struct sod_vtable *_vt;
};
\end{listing}

\begin{listing}
void *sod_convert(const SodClass *cls, const void *obj)
{
  const struct sod_instance *inst = obj;
  const SodClass *real = inst->_vt->_cls;
  const struct sod_chain *chain;
  size_t i, index;

  for (i = 0; i < real->cls.n_chains; i++) {
    chain = &real->cls.chains[i];
    if (chain->classes[0] == cls->cls.head) {
      index = cls->cls.index;
      if (index < chain->n_classes && chain->classes[index] == cls)
        return ((char *)cls - inst->_vt._base + chain->off_ichain);
      else
        return (0);
    }
  }
  return (0);
}
\end{listing}

%%%--------------------------------------------------------------------------
\section{Classes}

\subsection{Classes and superclasses}

A @<full-class-definition> must list one or more existing classes to be the
\emph{direct superclasses} for the new class being defined.  We make the
following definitions.
\begin{itemize}
\item The \emph{superclasses} of a class consist of the class itself together
  with the superclasses of its direct superclasses.
\item The \emph{proper superclasses} of a class are its superclasses other
  than itself.
\item If $C$ is a (proper) superclass of $D$ then $D$ is a (\emph{proper})
  \emph{subclass} of $C$.
\end{itemize}
The predefined class @|SodObject| has no direct superclasses; it is unique in
this respect.  All classes are subclasses of @|SodObject|.

\subsection{The class precedence list}

Let $C$ be a class.  The superclasses of $C$ form a directed graph, with an
edge from each class to each of its direct superclasses.  This is the
\emph{superclass graph of $C$}.

In order to resolve inheritance of items, we define a \emph{class precedence
  list} (or CPL) for each class, which imposes a total order on that class's
superclasses.  The default algorithm for computing the CPL is the \emph{C3}
algorithm \cite{fixme-c3}, though extensions may implement other algorithms.

The default algorithm works as follows.  Let $C$ be the class whose CPL we
are to compute.  Let $X$ and $Y$ be two of $C$'s superclasses.
\begin{itemize}
\item $C$ must appear first in the CPL.
\item If $X$ appears before $Y$ in the CPL of one of $C$'s direct
  superclasses, then $X$ appears before $Y$ in the $C$'s CPL.
\item If the above rules don't suffice to order $X$ and $Y$, then whichever
  of $X$ and $Y$ has a subclass which appears further left in the list of
  $C$'s direct superclasses will appear earlier in the CPL.
\end{itemize}
This last rule is sufficient to disambiguate because if both $X$ and $Y$ are
superclasses of the same direct superclass of $C$ then that direct
superclass's CPL will order $X$ and $Y$.

We say that \emph{$X$ is more specific than $Y$ as a superclass of $C$} if
$X$ is earlier than $Y$ in $C$'s class precedence list.  If $C$ is clear from
context then we omit it, saying simply that $X$ is more specific than $Y$.

\subsection{Instances and metaclasses}

A class defines the structure and behaviour of its \emph{instances}: run-time
objects created (possibly) dynamically.  An instance is an instance of only
one class, though structurally it may be used in place of an instance of any
of that class's superclasses.  It is possible, with care, to change the class
of an instance at run-time.

Classes are themselves represented as instances -- called \emph{class
  objects} -- in the running program.  Being instances, they have a class,
called the \emph{metaclass}.  The metaclass defines the structure and
behaviour of the class object.

The predefined class @|SodClass| is the default metaclass for new classes.
@|SodClass| has @|SodObject| as its only direct superclass.  @|SodClass| is
its own metaclass.

\subsection{Items and inheritance}

A class definition also declares \emph{slots}, \emph{messages},
\emph{initializers} and \emph{methods} -- collectively referred to as
\emph{items}.  In addition to the items declared in the class definition --
the class's \emph{direct items} -- a class also \emph{inherits} items from
its superclasses.

The precise rules for item inheritance vary according to the kinds of items
involved.

Some object systems have a notion of `repeated inheritance': if there are
multiple paths in the superclass graph from a class to one of its
superclasses then items defined in that superclass may appear duplicated in
the subclass.  Sod does not have this notion.

\subsubsection{Slots}
A \emph{slot} is a unit of state.  In other object systems, slots may be
called `fields', `member variables', or `instance variables'.

A slot has a \emph{name} and a \emph{type}.  The name serves only to
distinguish the slot from other direct slots defined by the same class.  A
class inherits all of its proper superclasses' slots.  Slots inherited from
superclasses do not conflict with each other or with direct slots, even if
they have the same names.

At run-time, each instance of the class holds a separate value for each slot,
whether direct or inherited.  Changing the value of an instance's slot
doesn't affect other instances.

\subsubsection{Initializers}
Mumble.

\subsubsection{Messages}
A \emph{message} is the stimulus for behaviour.  In Sod, a class must define,
statically, the name and format of the messages it is able to receive and the
values it will return in reply.  In this respect, a message is similar to
`abstract member functions' or `interface member functions' in other object
systems.

Like slots, a message has a \emph{name} and a \emph{type}.  Again, the name
serves only to distinguish the message from other direct messages defined by
the same class.  Messages inherited from superclasses do not conflict with
each other or with direct messages, even if they have the same name.

At run-time, one sends a message to an instance by invoking a function
obtained from the instance's \emph{vtable}: \xref{sec:fixme-vtable}.

\subsubsection{Methods}
A \emph{method} is a unit of behaviour.  In other object systems, methods may
be called `member functions'.

A method is associated with a message.  When a message is received by an
instance, all of the methods associated with that message on the instance's
class or any of its superclasses are \emph{applicable}.  The details of how
the applicable methods are invoked are described fully in
\xref{sec:fixme-method-combination}.

\subsection{Chains and instance layout}

\include{sod-backg}
\include{sod-protocol}

\end{document}
\f
%%% Local variables:
%%% mode: LaTeX
%%% TeX-PDF-mode: t
%%% End: