[sod] / doc / syntax.tex

%%% -*-latex-*-
%%%
%%% Module syntax
%%%
%%% (c) 2015 Straylight/Edgeware
%%%

%%%----- Licensing notice ---------------------------------------------------
%%%
%%% This file is part of the Sensible Object Design, an object system for C.
%%%
%%% SOD 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.
%%%
%%% SOD 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.
%%%
%%% You should have received a copy of the GNU General Public License
%%% along with SOD; if not, write to the Free Software Foundation,
%%% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

\chapter{Module syntax} \label{ch:syntax}

%%%--------------------------------------------------------------------------

Fortunately, Sod is syntactically quite simple.  The notation is slightly
unusual in order to make the presentation shorter and easier to read.

Anywhere a simple nonterminal name $x$ may appear in the grammar, an
\emph{indexed} nonterminal $x[a_1, \ldots, a_n]$ may also appear.  On the
left-hand side of a production rule, the indices $a_1$, \ldots, $a_n$ are
variables which vary over all nonterminal and terminal symbols, and the
variables may also appear on the right-hand side in place of a nonterminal.
Such a rule stands for a family of rules, in each variable is replaced by
each possible simple nonterminal or terminal symbol.

The letter $\epsilon$ denotes the empty nonterminal
\begin{quote}
  \syntax{$\epsilon$ ::=}
\end{quote}

The following indexed productions are used throughout the grammar, some often
enough that they deserve special notation.
\begin{itemize}
\item @[$x$@] abbreviates @<optional>$[x]$, denoting an optional occurrence
  of $x$:
  \begin{quote}
    \syntax{@[$x$@] ::= <optional>$[x]$ ::= $\epsilon$ @! $x$}
  \end{quote}
\item $x^*$ abbreviates @<zero-or-more>$[x]$, denoting a sequence of zero or
  more occurrences of $x$:
  \begin{quote}
    \syntax{$x^*$ ::= <zero-or-more>$[x]$ ::=
      $\epsilon$ @! <zero-or-more>$[x]$ $x$}
  \end{quote}
\item $x^+$ abbreviates @<one-or-more>$[x]$, denoting a sequence of zero or
  more occurrences of $x$:
  \begin{quote}
    \syntax{$x^+$ ::= <one-or-more>$[x]$ ::= <zero-or-more>$[x]$ $x$}
  \end{quote}
\item @<list>$[x]$ denotes a sequence of one or more occurrences of $x$
  separated by commas:
  \begin{quote}
    \syntax{<list>$[x]$ ::= $x$ @! <list>$[x]$ "," $x$}
  \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 <string-literal>
\alt <char-literal>
\alt <integer-literal>
\alt <punctuation>
\end{grammar}

This syntax is slightly ambiguous, and is disambiguated by the \emph{maximal
munch} rule: at each stage we take the longest sequence of characters which
could be a token.

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

There are no reserved words at the lexical level, but the higher-level syntax
recognizes certain identifiers as \emph{keywords} in some contexts.  There is
also an ambiguity (inherited from C) in the declaration syntax which is
settled by distinguishing type names from other identifiers at a lexical
level.

\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> ::= "0" | <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 nonalphanumeric character other than "_", "\"" or "'"
\end{grammar}

\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{quote}
  \textsf{(asdf:load-system :foo-extension)}
\end{quote}
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.

\begin{boxy}[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.} %
\end{boxy}

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

\begin{grammar}
<typename-definition> ::=
  "typename" <list>$[\mbox{@<identifier>}]$ ";"
\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> ::= "[" <list>$[\mbox{@<constraint>}]$ "]"

<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> ::= "[" <list>$[\mbox{@<property>}]$ "]"

<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 "bool" | "_Bool"
\alt "imaginary" | "_Imaginary" | "complex" | "_Complex"
\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.  The following type names are
defined in the built-in module.
\begin{itemize}
\item @"va_list"
\item @"size_t"
\item @"ptrdiff_t"
\item @"wchar_t"
\end{itemize}

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 @"_Bool", @"bool"
\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"
\item @"float _Imaginary", @"double _Imaginary", @"long double _Imaginary"
\item @"float imaginary", @"double imaginary", @"long double imaginary"
\item @"float _Complex", @"double _Complex", @"long double _Complex"
\item @"float complex", @"double complex", @"long double complex"
\end{itemize}
All of these have their usual C meanings.

\subsubsection{Declarators} \label{sec:syntax.c-types.declarator}
\begin{grammar}
<declarator>$[k]$ ::= @<pointer>^* <primary-declarator>$[k]$

<primary-declarator>$[k]$ ::= $k$
\alt "(" <primary-declarator>$[k]$ ")"
\alt <primary-declarator>$[k]$ @<declarator-suffix>

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

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

<argument-list> ::= $\epsilon$ | "..."
\alt <list>$[\mbox{@<argument>}]$ @["," "..."@]

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

<argument-declarator> ::= <declarator>$[\mbox{@<identifier> @! $\epsilon$}]$

<simple-declarator> ::= <declarator>$[\mbox{@<identifier>}]$

<dotted-name> ::= <identifier> "." <identifier>
\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> ":" <list>$[\mbox{@<identifier>}]$
  "{" @<properties-class-item>^* "}"

<properties-class-item> ::= @[<properties>@] <class-item>

<class-item> ::= <slot-item>
\alt <initializer-item>
\alt <message-item>
\alt <method-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 @<list>$[\mbox{@<identifier>}]$ 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> ::=
  @<declaration-specifier>^+ <list>$[\mbox{@<init-declarator>}]$ ";"

<init-declarator> ::= <simple-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 dotted names.

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"@] <list>$[\mbox{@<slot-initializer>}]$ ";"

<slot-initializer> ::= <dotted-name> "=" <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 @<dotted-name> 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> ::=
  @<declaration-specifier>^+
  <keyword-declarator>$[\mbox{@<identifier>}]$
  @[<method-body>@]
\end{grammar}

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

\begin{grammar}
<method-item> ::=
  @<declaration-specifier>^+
  <keyword-declarator>$[\mbox{@<dotted-name>}]$
  <method-body>

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

%%%----- That's all, folks --------------------------------------------------

%%% Local variables:
%%% mode: LaTeX
%%% TeX-master: "sod.tex"
%%% TeX-PDF-mode: t
%%% End: