This commit was manufactured by cvs2svn to create tag 'cnrisync'.

[python/dscho.git] / Doc / qua.tex

\documentstyle[11pt]{article}
\newcommand{\Cpp}{C\protect\raisebox{.18ex}{++}}

\title{
Interactively Testing Remote Servers Using the Python Programming Language
}

\author{
        Guido van Rossum \\
        Dept. AA, CWI, P.O. Box 94079 \\
        1090 GB Amsterdam, The Netherlands \\
        E-mail: {\tt guido@cwi.nl}
\and
        Jelke de Boer \\
        HIO Enschede; P.O.Box 1326 \\
        7500 BH  Enschede, The Netherlands
}

\begin{document}

\maketitle

\begin{abstract}
This paper describes how two tools that were developed quite
independently gained in power by a well-designed connection between
them.  The tools are Python, an interpreted prototyping language, and
AIL, a Remote Procedure Call stub generator.  The context is Amoeba, a
well-known distributed operating system developed jointly by the Free
University and CWI in Amsterdam.

As a consequence of their integration, both tools have profited:
Python gained usability when used with Amoeba --- for which it was not
specifically developed --- and AIL users now have a powerful
interactive tool to test servers and to experiment with new
client/server interfaces.%
\footnote{
An earlier version of this paper was presented at the Spring 1991
EurOpen Conference in Troms{\o} under the title ``Linking a Stub
Generator (AIL) to a Prototyping Language (Python).''
}
\end{abstract}

\section{Introduction}

Remote Procedure Call (RPC) interfaces, used in distributed systems
like Amoeba
\cite{Amoeba:IEEE,Amoeba:CACM},
have a much more concrete character than local procedure call
interfaces in traditional systems.  Because clients and servers may
run on different machines, with possibly different word size, byte
order, etc., much care is needed to describe interfaces exactly and to
implement them in such a way that they continue to work when a client
or server is moved to a different machine.  Since machines may fail
independently, error handling must also be treated more carefully.

A common approach to such problems is to use a {\em stub generator}.
This is a program that takes an interface description and transforms
it into functions that must be compiled and linked with client and
server applications.  These functions are called by the application
code to take care of details of interfacing to the system's RPC layer,
to implement transformations between data representations of different
machines, to check for errors, etc.  They are called `stubs' because
they don't actually perform the action that they are called for but
only relay the parameters to the server
\cite{RPC}.

Amoeba's stub generator is called AIL, which stands for Amoeba
Interface Language
\cite{AIL}.
The first version of AIL generated only C functions, but an explicit
goal of AIL's design was {\em retargetability}: it should be possible
to add back-ends that generate stubs for different languages from the
same interface descriptions.  Moreover, the stubs generated by
different back-ends must be {\em interoperable}: a client written in
Modula-3, say, should be able to use a server written in C, and vice
versa.

This interoperability is the key to the success of the marriage
between AIL and Python.  Python is a versatile interpreted language
developed by the first author.  Originally intended as an alternative
for the kind of odd jobs that are traditionally solved by a mixture of
shell scripts, manually given shell commands, and an occasional ad hoc
C program, Python has evolved into a general interactive prototyping
language.  It has been applied to a wide range of problems, from
replacements for large shell scripts to fancy graphics demos and
multimedia applications.

One of Python's strengths is the ability for the user to type in some
code and immediately run it: no compilation or linking is necessary.
Interactive performance is further enhanced by Python's concise, clear
syntax, its very-high-level data types, and its lack of declarations
(which is compensated by run-time type checking).  All this makes
programming in Python feel like a leisure trip compared to the hard
work involved in writing and debugging even a smallish C program.

It should be clear by now that Python will be the ideal tool to test
servers and their interfaces.  Especially during the development of a
complex server, one often needs to generate test requests on an ad hoc
basis, to answer questions like ``what happens if request X arrives
when the server is in state Y,'' to test the behavior of the server
with requests that touch its limitations, to check server responses to
all sorts of wrong requests, etc.  Python's ability to immediately
execute `improvised' code makes it a much better tool for this
situation than C.

The link to AIL extends Python with the necessary functionality to
connect to arbitrary servers, making the server testbed sketched above
a reality.  Python's high-level data types, general programming
features, and system interface ensure that it has all the power and
flexibility needed for the job.

One could go even further than this.  Current distributed operating
systems, based on client-server interaction, all lack a good command
language or `shell' to give adequate access to available services.
Python has considerable potential for becoming such a shell.

\subsection{Overview of this Paper}

The rest of this paper contains three major sections and a conclusion.
First an overview of the Python programming language is given.  Next
comes a short description of AIL, together with some relevant details
about Amoeba.  Finally, the design and construction of the link
between Python and AIL is described in much detail.  The conclusion
looks back at the work and points out weaknesses and strengths of
Python and AIL that were discovered in the process.

\section{An Overview of Python}

Python%
\footnote{
Named after the funny TV show, not the nasty reptile.
}
owes much to ABC
\cite{ABC},
a language developed at CWI as a programming language for non-expert
computer users.  Python borrows freely from ABC's syntax and data
types, but adds modules, exceptions and classes, extensibility, and
the ability to call system functions.  The concepts of modules,
exceptions and (to some extent) classes are influenced strongly by
their occurrence in Modula-3
\cite{Modula-3}.

Although Python resembles ABC in many ways, there is a a clear
difference in application domain.  ABC is intended to be the only
programming language for those who use a computer as a tool, but
occasionally need to write a program.  For this reason, ABC is not
just a programming language but also a programming environment, which
comes with an integrated syntax-directed editor and some source
manipulation commands.  Python, on the other hand, aims to be a tool
for professional (system) programmers, for whom having a choice of
languages with different feature sets makes it possible to choose `the
right tool for the job.'  The features added to Python make it more
useful than ABC in an environment where access to system functions
(such as file and directory manipulations) are common.  They also
support the building of larger systems and libraries.  The Python
implementation offers little in the way of a programming environment,
but is designed to integrate seamlessly with existing programming
environments (e.g. UNIX and Emacs).

Perhaps the best introduction to Python is a short example.  The
following is a complete Python program to list the contents of a UNIX
directory.
\begin{verbatim}
import sys, posix

def ls(dirname):    # Print sorted directory contents
    names = posix.listdir(dirname)
    names.sort()
    for name in names:
        if name[0] != '.': print name

ls(sys.argv[1])
\end{verbatim}
The largest part of this program, in the middle starting with {\tt
def}, is a function definition.  It defines a function named {\tt ls}
with a single parameter called {\tt dirname}.  (Comments in Python
start with `\#' and extend to the end of the line.)  The function body
is indented: Python uses indentation for statement grouping instead of
braces or begin/end keywords.  This is shorter to type and avoids
frustrating mismatches between the perception of grouping by the user
and the parser.  Python accepts one statement per line; long
statements may be broken in pieces using the standard backslash
convention.  If the body of a compound statement is a single, simple
statement, it may be placed on the same line as the head.

The first statement of the function body calls the function {\tt
listdir} defined in the module {\tt posix}.  This function returns a
list of strings representing the contents of the directory name passed
as a string argument, here the argument {\tt dirname}.  If {\tt
dirname} were not a valid directory name, or perhaps not even a
string, {\tt listdir} would raise an exception and the next statement
would never be reached.  (Exceptions can be caught in Python; see
later.)  Assuming {\tt listdir} returns normally, its result is
assigned to the local variable {\tt names}.

The second statement calls the method {\tt sort} of the variable {\tt
names}.  This method is defined for all lists in Python and does the
obvious thing: the elements of the list are reordered according to
their natural ordering relationship.  Since in our example the list
contains strings, they are sorted in ascending \ASCII{} order.

The last two lines of the function contain a loop that prints all
elements of the list whose first character isn't a period.  In each
iteration, the {\tt for} statement assigns an element of the list to
the local variable {\tt name}.  The {\tt print} statement is intended
for simple-minded output; more elaborate formatting is possible with
Python's string handling functions.

The other two parts of the program are easily explained.  The first
line is an {\tt import} statement that tells the interpreter to import
the modules {\tt sys} and {\tt posix}.  As it happens these are both
built into the interpreter.  Importing a module (built-in or
otherwise) only makes the module name available in the current scope;
functions and data defined in the module are accessed through the dot
notation as in {\tt posix.listdir}.  The scope rules of Python are
such that the imported module name {\tt posix} is also available in
the function {\tt ls} (this will be discussed in more detail later).

Finally, the last line of the program calls the {\tt ls} function with
a definite argument.  It must be last since Python objects must be
defined before they can be used; in particular, the function {\tt ls}
must be defined before it can be called.  The argument to {\tt ls} is
{\tt sys.argv[1]}, which happens to be the Python equivalent of {\tt
\$1} in a shell script or {\tt argv[1]} in a C program's {\tt main}
function.

\subsection{Python Data Types}

(This and the following subsections describe Python in quite a lot of
detail.  If you are more interested in AIL, Amoeba and how they are
linked with Python, you can skip to section 3 now.)

Python's syntax may not have big surprises (which is exactly as it
should be), but its data types are quite different from what is found
in languages like C, Ada or Modula-3.  All data types in Python, even
integers, are `objects'.  All objects participate in a common garbage
collection scheme (currently implemented using reference counting).
Assignment is cheap, independent of object size and type: only a
pointer to the assigned object is stored in the assigned-to variable.
No type checking is performed on assignment; only specific operations
like addition test for particular operand types.

The basic object types in Python are numbers, strings, tuples, lists
and dictionaries.  Some other object types are open files, functions,
modules, classes, and class instances; even types themselves are
represented as objects.  Extension modules written in C can define
additional object types; examples are objects representing windows and
Amoeba capabilities.  Finally, the implementation itself makes heavy
use of objects, and defines some private object types that aren't
normally visible to the user.  There is no explicit pointer type in
Python.

{\em Numbers}, both integers and floating point, are pretty
straightforward.  The notation for numeric literals is the same as in
C, including octal and hexadecimal integers; precision is the same as
{\tt long} or {\tt double} in C\@.  A third numeric type, `long
integer', written with an `L' suffix, can be used for arbitrary
precision calculations.  All arithmetic, shifting and masking
operations from C are supported.

{\em Strings} are `primitive' objects just like numbers.  String
literals are written between single quotes, using similar escape
sequences as in C\@.  Operations are built into the language to
concatenate and to replicate strings, to extract substrings, etc.
There is no limit to the length of the strings created by a program.
There is no separate character data type; strings of length one do
nicely.

{\em Tuples} are a way to `pack' small amounts of heterogeneous data
together and carry them around as a unit.  Unlike structure members in
C, tuple items are nameless.  Packing and unpacking assignments allow
access to the items, for example:
\begin{verbatim}
x = 'Hi', (1, 2), 'World'   # x is a 3-item tuple,
                            # its middle item is (1, 2)
p, q, r = x                 # unpack x into p, q and r
a, b = q                    # unpack q into a and b
\end{verbatim}
A combination of packing and unpacking assignment can be used as
parallel assignment, and is idiom for permutations, e.g.:
\begin{verbatim}
p, q = q, p                 # swap without temporary
a, b, c = b, c, a           # cyclic permutation
\end{verbatim}
Tuples are also used for function argument lists if there is more than
one argument.  A tuple object, once created, cannot be modified; but
it is easy enough to unpack it and create a new, modified tuple from
the unpacked items and assign this to the variable that held the
original tuple object (which will then be garbage-collected).

{\em Lists} are array-like objects.  List items may be arbitrary
objects and can be accessed and changed using standard subscription
notation.  Lists support item insertion and deletion, and can
therefore be used as queues, stacks etc.; there is no limit to their
size.

Strings, tuples and lists together are {\em sequence} types.  These
share a common notation for generic operations on sequences such as
subscription, concatenation, slicing (taking subsequences) and
membership tests.  As in C, subscripts start at 0.

{\em Dictionaries} are `mappings' from one domain to another.  The
basic operations on dictionaries are item insertion, extraction and
deletion, using subscript notation with the key as subscript.  (The
current implementation allows only strings in the key domain, but a
future version of the language may remove this restriction.)

\subsection{Statements}

Python has various kinds of simple statements, such as assignments
and {\tt print} statements, and several kinds of compound statements,
like {\tt if} and {\tt for} statements.  Formally, function
definitions and {\tt import} statements are also statements, and there
are no restrictions on the ordering of statements or their nesting:
{\tt import} may be used inside a function, functions may be defined
conditionally using an {\tt if} statement, etc.  The effect of a
declaration-like statement takes place only when it is executed.

All statements except assignments and expression statements begin with
a keyword: this makes the language easy to parse.  An overview of the
most common statement forms in Python follows.

An {\em assignment} has the general form
\vspace{\itemsep}

\noindent
{\em variable $=$ variable $= ... =$ variable $=$ expression}
\vspace{\itemsep}

It assigns the value of the expression to all listed variables.  (As
shown in the section on tuples, variables and expressions can in fact
be comma-separated lists.)  The assignment operator is not an
expression operator; there are no horrible things in Python like
\begin{verbatim}
while (p = p->next) { ... }
\end{verbatim}
Expression syntax is mostly straightforward and will not be explained
in detail here.

An {\em expression statement} is just an expression on a line by
itself.  This writes the value of the expression to standard output,
in a suitably unambiguous way, unless it is a `procedure call' (a
function call that returns no value).  Writing the value is useful
when Python is used in `calculator mode', and reminds the programmer
not to ignore function results.

The {\tt if} statement allows conditional execution.  It has optional
{\tt elif} and {\tt else} parts; a construct like {\tt
if...elif...elif...elif...else} can be used to compensate for the
absence of a {\em switch} or {\em case} statement.

Looping is done with {\tt while} and {\tt for} statements.  The latter
(demonstrated in the `ls' example earlier) iterates over the elements
of a `sequence' (see the discussion of data types below).  It is
possible to terminate a loop with a {\tt break} statement or to start
the next iteration with {\tt continue}.  Both looping statements have
an optional {\tt else} clause which is executed after the loop is
terminated normally, but skipped when it is terminated by {\tt break}.
This can be handy for searches, to handle the case that the item is
not found.

Python's {\em exception} mechanism is modelled after that of Modula-3.
Exceptions are raised by the interpreter when an illegal operation is
tried.  It is also possible to explicitly raise an exception with the
{\tt raise} statement:
\vspace{\itemsep}

\noindent
{\tt raise {\em expression}, {\em expression}}
\vspace{\itemsep}

The first expression identifies which exception should be raised;
there are several built-in exceptions and the user may define
additional ones.  The second, optional expression is passed to the
handler, e.g. as a detailed error message.

Exceptions may be handled (caught) with the {\tt try} statement, which
has the following general form:
\vspace{\itemsep}

\noindent
{\tt
\begin{tabular}{l}
try: {\em block} \\
except {\em expression}, {\em variable}: {\em block} \\
except {\em expression}, {\em variable}: {\em block} \\
... \\
except: {\em block}
\end{tabular}
}
\vspace{\itemsep}

When an exception is raised during execution of the first block, a
search for an exception handler starts.  The first {\tt except} clause
whose {\em expression} matches the exception is executed.  The
expression may specify a list of exceptions to match against.  A
handler without an expression serves as a `catch-all'.  If there is no
match, the search for a handler continues with outer {\tt try}
statements; if no match is found on the entire invocation stack, an
error message and stack trace are printed, and the program is
terminated (interactively, the interpreter returns to its main loop).

Note that the form of the {\tt except} clauses encourages a style of
programming whereby only selected exceptions are caught, passing
unanticipated exceptions on to the caller and ultimately to the user.
This is preferable over a simpler `catch-all' error handling
mechanism, where a simplistic handler intended to catch a single type
of error like `file not found' can easily mask genuine programming
errors --- especially in a language like Python which relies strongly
on run-time checking and allows the catching of almost any type of
error.

Other common statement forms, which we have already encountered, are
function definitions, {\tt import} statements and {\tt print}
statements.  There is also a {\tt del} statement to delete one or more
variables, a {\tt return} statement to return from a function, and a
{\tt global} statement to allow assignments to global variables.
Finally, the {\tt pass} statement is a no-op.

\subsection{Execution Model}

A Python program is executed by a stack-based interpreter.

When a function is called, a new `execution environment' for it is
pushed onto the stack.  An execution environment contains (among other
data) pointers to two `symbol tables' that are used to hold variables:
the local and the global symbol table.  The local symbol table
contains local variables of the current function invocation (including
the function arguments); the global symbol table contains variables
defined in the module containing the current function.

The `global' symbol table is thus only global with respect to the
current function.  There are no system-wide global variables; using
the {\tt import} statement it is easy enough to reference variables
that are defined in other modules.  A system-wide read-only symbol
table is used for built-in functions and constants though.

On assignment to a variable, by default an entry for it is made in the
local symbol table of the current execution environment.  The {\tt
global} command can override this (it is not enough that a global
variable by the same name already exists).  When a variable's value is
needed, it is searched first in the local symbol table, then in the
global one, and finally in the symbol table containing built-in
functions and constants.

The term `variable' in this context refers to any name: functions and
imported modules are searched in exactly the same way.  

Names defined in a module's symbol table survive until the end of the
program.  This approximates the semantics of file-static global
variables in C or module variables in Modula-3.  A module is
initialized the first time it is imported, by executing the text of
the module as a parameterless function whose local and global symbol
tables are the same, so names are defined in module's symbol table.
(Modules implemented in C have another way to define symbols.)

A Python main program is read from standard input or from a script
file passed as an argument to the interpreter.  It is executed as if
an anonymous module was imported.  Since {\tt import} statements are
executed like all other statements, the initialization order of the
modules used in a program is defined by the flow of control through
the program.

The `attribute' notation {\em m.name}, where {\em m} is a module,
accesses the symbol {\em name} in that module's symbol table.  It can
be assigned to as well.  This is in fact a special case of the
construct {\em x.name} where {\em x} denotes an arbitrary object; the
type of {\em x} determines how this is to be interpreted, and what
assignment to it means.

For instance, when {\tt a} is a list object, {\tt a.append} yields a
built-in `method' object which, when called, appends an item to {\tt a}.
(If {\tt a} and {\tt b} are distinct list objects, {\tt a.append} and
{\tt b.append} are distinguishable method objects.)  Normally, in
statements like {\tt a.append(x)}, the method object {\tt a.append} is
called and then discarded, but this is a matter of convention.

List attributes are read-only --- the user cannot define new list
methods.  Some objects, like numbers and strings, have no attributes
at all.  Like all type checking in Python, the meaning of an attribute
is determined at run-time --- when the parser sees {\em x.name}, it
has no idea of the type of {\em x}.  Note that {\em x} here does not
have to be a variable --- it can be an arbitrary (perhaps
parenthesized) expression.

Given the flexibility of the attribute notation, one is tempted to use
methods to replace all standard operations.  Yet, Python has kept a
small repertoire of built-in functions like {\tt len()} and {\tt
abs()}.  The reason is that in some cases the function notation is
more familiar than the method notation; just like programs would
become less readable if all infix operators were replaced by function
calls, they would become less readable if all function calls had to be
replaced by method calls (and vice versa!).

The choice whether to make something a built-in function or a method
is a matter of taste.  For arithmetic and string operations, function
notation is preferred, since frequently the argument to such an
operation is an expression using infix notation, as in {\tt abs(a+b)};
this definitely looks better than {\tt (a+b).abs()}.  The choice
between make something a built-in function or a function defined in a
built-in method (requiring {\tt import}) is similarly guided by
intuition; all in all, only functions needed by `general' programming
techniques are built-in functions.

\subsection{Classes}

Python has a class mechanism distinct from the object-orientation
already explained.  A class in Python is not much more than a
collection of methods and a way to create class instances.  Class
methods are ordinary functions whose first parameter is the class
instance; they are called using the method notation.

For instance, a class can be defined as follows:
\begin{verbatim}
class Foo:
   def meth1(self, arg): ...
   def meth2(self): ...
\end{verbatim}
A class instance is created by
{\tt x = Foo()}
and its methods can be called thus:
\begin{verbatim}
x.meth1('Hi There!')
x.meth2()
\end{verbatim}
The functions used as methods are also available as attributes of the
class object, and the above method calls could also have been written
as follows:
\begin{verbatim}
Foo.meth1(x, 'Hi There!')
Foo.meth2(x)
\end{verbatim}
Class methods can store instance data by assigning to instance data
attributes, e.g.:
\begin{verbatim}
self.size = 100
self.title = 'Dear John'
\end{verbatim}
Data attributes do not have to be declared; as with local variables,
they spring into existence when assigned to.  It is a matter of
discretion to avoid name conflicts with method names.  This facility
is also available to class users; instances of a method-less class can
be used as records with named fields.

There is no built-in mechanism for instance initialization.  Classes
by convention provide an {\tt init()} method which initializes the
instance and then returns it, so the user can write
\begin{verbatim}
x = Foo().init('Dr. Strangelove')
\end{verbatim}

Any user-defined class can be used as a base class to derive other
classes.  However, built-in types like lists cannot be used as base
classes.  (Incidentally, the same is true in \Cpp{} and Modula-3.)  A
class may override any method of its base classes.  Instance methods
are first searched in the method list of their class, and then,
recursively, in the method lists of their base class.  Initialization
methods of derived classes should explicitly call the initialization
methods of their base class.

A simple form of multiple inheritance is also supported: a class can
have multiple base classes, but the language rules for resolving name
conflicts are somewhat simplistic, and consequently the feature has so
far found little usage.

\subsection{The Python Library}

Python comes with an extensive library, structured as a collection of
modules.  A few modules are built into the interpreter: these
generally provide access to system libraries implemented in C such as
mathematical functions or operating system calls.  Two built-in
modules provide access to internals of the interpreter and its
environment.  Even abusing these internals will at most cause an
exception in the Python program; the interpreter will not dump core
because of errors in Python code.

Most modules however are written in Python and distributed with the
interpreter; they provide general programming tools like string
operations and random number generators, provide more convenient
interfaces to some built-in modules, or provide specialized services
like a {\em getopt}-style command line option processor for
stand-alone scripts.

There are also some modules written in Python that dig deep in the
internals of the interpreter; there is a module to browse the stack
backtrace when an unhandled exception has occurred, one to disassemble
the internal representation of Python code, and even an interactive
source code debugger which can trace Python code, set breakpoints,
etc.

\subsection{Extensibility}

It is easy to add new built-in modules written in C to the Python
interpreter.  Extensions appear to the Python user as built-in
modules.  Using a built-in module is no different from using a module
written in Python, but obviously the author of a built-in module can
do things that cannot be implemented purely in Python.

In particular, built-in modules can contain Python-callable functions
that call functions from particular system libraries (`wrapper
functions'), and they can define new object types.  In general, if a
built-in module defines a new object type, it should also provide at
least one function that creates such objects.  Attributes of such
object types are also implemented in C; they can return data
associated with the object or methods, implemented as C functions.

For instance, an extension was created for Amoeba: it provides wrapper
functions for the basic Amoeba name server functions, and defines a
`capability' object type, whose methods are file server operations.
Another extension is a built-in module called {\tt posix}; it provides
wrappers around post UNIX system calls.  Extension modules also
provide access to two different windowing/graphics interfaces: STDWIN
\cite{STDWIN}
(which connects to X11 on UNIX and to the Mac Toolbox on the
Macintosh), and the Graphics Library (GL) for Silicon Graphics
machines.

Any function in an extension module is supposed to type-check its
arguments; the interpreter contains a convenience function to
facilitate extracting C values from arguments and type-checking them
at the same time.  Returning values is also painless, using standard
functions to create Python objects from C values.

On some systems extension modules may be dynamically loaded, thus
avoiding the need to maintain a private copy of the Python interpreter
in order to use a private extension.

\section{A Short Description of AIL and Amoeba}

An RPC stub generator takes an interface description as input.  The
designer of a stub generator has at least two choices for the input
language: use a suitably restricted version of the target language, or
design a new language.  The first solution was chosen, for instance,
by the designers of Flume, the stub generator for the Topaz
distributed operating system built at DEC SRC
\cite{Flume,Evolving}.

Flume's one and only target language is Modula-2+ (the predecessor of
Modula-3).  Modula-2+, like Modula-N for any N, has an interface
syntax that is well suited as a stub generator input language: an
interface module declares the functions that are `exported' by a
module implementation, with their parameter and return types, plus the
types and constants used for the parameters.  Therefore, the input to
Flume is simply a Modula-2+ interface module.  But even in this ideal
situation, an RPC stub generator needs to know things about functions
that are not stated explicitly in the interface module: for instance,
the transfer direction of VAR parameters (IN, OUT or both) is not
given.  Flume solves this and other problems by a mixture of
directives hidden in comments and a convention for the names of
objects.  Thus, one could say that the designers of Flume really
created a new language, even though it looks remarkably like their
target language.

\subsection{The AIL Input Language}

Amoeba uses C as its primary programming language.  C function
declarations (at least in `Classic' C) don't specify the types of
the parameters, let alone their transfer direction.  Using this as
input for a stub generator would require almost all information for
the stub generator to be hidden inside comments, which would require a
rather contorted scanner.  Therefore we decided to design the input
syntax for Amoeba's stub generator `from scratch'.  This gave us the
liberty to invent proper syntax not only for the transfer direction of
parameters, but also for variable-length arrays.

On the other hand we decided not to abuse our freedom, and borrowed as
much from C as we could.  For instance, AIL runs its input through the
C preprocessor, so we get macros, include files and conditional
compilation for free.  AIL's type declaration syntax is a superset of
C's, so the user can include C header files to use the types declared
there as function parameter types --- which are declared using
function prototypes as in \Cpp{} or Standard C\@.  It should be clear by
now that AIL's lexical conventions are also identical to C's.  The
same is true for its expression syntax.

Where does AIL differ from C, then?  Function declarations in AIL are
grouped in {\em classes}.  Classes in AIL are mostly intended as a
grouping mechanism: all functions implemented by a server are grouped
together in a class.  Inheritance is used to form new groups by adding
elements to existing groups; multiple inheritance is supported to join
groups together.  Classes can also contain constant and type
definitions, and one form of output that AIL can generate is a header
file for use by C programmers who wish to use functions from a
particular AIL class.

Let's have a look at some (unrealistically simple) class definitions:
\begin{verbatim}
#include <amoeba.h>     /* Defines `capability', etc. */

class standard_ops [1000 .. 1999] {
    /* Operations supported by most interfaces */
    std_info(*, out char buf[size:100], out int size);
    std_destroy(*);
};
\end{verbatim}
This defines a class called `standard\_ops' whose request codes are
chosen by AIL from the range 1000-1999.  Request codes are small
integers used to identify remote operations.  The author of the class
must specify a range from which AIL chooses, and class authors must
make sure they avoid conflicts, e.g. by using an `assigned number
administration office'.  In the example, `std\_info' will be assigned
request code 1000 and `std\_destroy' will get code 1001.  There is
also an option to explicitly assign request codes, for compatibility
with servers with manually written interfaces.

The class `standard\_ops' defines two operations, `std\_info' and
`std\_destroy'.  The first parameter of each operation is a star
(`*'); this is a placeholder for a capability that must be passed when
the operation is called.  The description of Amoeba below explains the
meaning and usage of capabilities; for now, it is sufficient to know
that a capability is a small structure that uniquely identifies an
object and a server or service.

The standard operation `std\_info' has two output parameters: a
variable-size character buffer (which will be filled with a short
descriptive string of the object to which the operation is applied)
and an integer giving the length of this string.  The standard
operation `std\_destroy' has no further parameters --- it just
destroys the object, if the caller has the right to do so.

The next class is called `tty':
\begin{verbatim}
class tty [2000 .. 2099] {
    inherit standard_ops;
    const TTY_MAXBUF = 1000;
    tty_write(*, char buf[size:TTY_MAXBUF], int size);
    tty_read(*, out char buf[size:TTY_MAXBUF], out int size);
};
\end{verbatim}
The request codes for operations defined in this class lie in the
range 2000-2099; inherited operations use the request codes already
assigned to them.  The operations defined by this class are
`tty\_read' and `tty\_write', which pass variable-sized data buffers
between client and server.  Class `tty' inherits class
`standard\_ops', so tty objects also support the operations
`std\_info' and `std\_destroy'.

Only the {\em interface} for `std\_info' and `std\_destroy' is shared
between tty objects and other objects whose interface inherits
`standard\_ops'; the implementation may differ.  Even multiple
implementations of the `tty' interface may exist, e.g. a driver for a
console terminal and a terminal emulator in a window.  To expand on
the latter example, consider:
\begin{verbatim}
class window [2100 .. 2199] {
    inherit standard_ops;
    win_create(*, int x, int y, int width, int height,
                  out capability win_cap);
    win_reconfigure(*, int x, int y, int width, int height);
};

class tty_emulator [2200 .. 2299] {
    inherit tty, window;
};
\end{verbatim}
Here two new interface classes are defined.
Class `window' could be used for creating and manipulating windows.
Note that `win\_create' returns a capability for the new window.
This request should probably should be sent to a generic window
server capability, or it might create a subwindow when applied to a
window object.

Class `tty\_emulator' demonstrates the essence of multiple inheritance.
It is presumably the interface to a window-based terminal emulator.
Inheritance is transitive, so `tty\_emulator' also implicitly inherits
`standard\_ops'.
In fact, it inherits it twice: once via `tty' and once via `window'.
Since AIL class inheritance only means interface sharing, not
implementation sharing, inheriting the same class multiple times is
never a problem and has the same effect as inheriting it once.

Note that the power of AIL classes doesn't go as far as \Cpp{}.
AIL classes cannot have data members, and there is
no mechanism for a server that implements a derived class
to inherit the implementation of the base
class --- other than copying the source code.
The syntax for class definitions and inheritance is also different.

\subsection{Amoeba}

The smell of `object-orientedness' that the use of classes in AIL
creates matches nicely with Amoeba's object-oriented approach to
RPC\@.  In Amoeba, almost all operating system entities (files,
directories, processes, devices etc.) are implemented as {\em
objects}.  Objects are managed by {\em services} and represented by
{\em capabilities}.  A capability gives its holder access to the
object it represents.  Capabilities are protected cryptographically
against forgery and can thus be kept in user space.  A capability is a
128-bit binary string, subdivided as follows:

% XXX Need a better version of this picture!
\begin{verbatim}
        48             24          8           48       Bits
+----------------+------------+--------+---------------+
|    Service     |   Object   |  Perm. |     Check     |
|      port      |   number   |  bits  |     word      |
+----------------+------------+--------+---------------+
\end{verbatim}

The service port is used by the RPC implementation in the Amoeba
kernel to locate a server implementing the service that manages the
object.  In many cases there is a one-to-one correspondence between
servers and services (each service is implemented by exactly one
server process), but some services are replicated.  For instance,
Amoeba's directory service, which is crucial for gaining access to most
other services, is implemented by two servers that listen on the same
port and know about exactly the same objects.

The object number in the capability is used by the server receiving
the request for identifying the object to which the operation applies.
The permission bits specify which operations the holder of the capability
may apply.  The last part of a capability is a 48-bit long `check
word', which is used to prevent forgery.  The check word is computed
by the server based upon the permission bits and a random key per object
that it keeps secret.  If you change the permission bits you must compute
the proper check word or else the server will refuse the capability.
Due to the size of the check word and the nature of the cryptographic
`one-way function' used to compute it, inverting this function is
impractical, so forging capabilities is impossible.%
\footnote{
As computers become faster, inverting the one-way function becomes
less impractical.
Therefore, a next version of Amoeba will have 64-bit check words.
}

A working Amoeba system is a collection of diverse servers, managing
files, directories, processes, devices etc.  While most servers have
their own interface, there are some requests that make sense for some
or all object types.  For instance, the {\em std\_info()} request,
which returns a short descriptive string, applies to all object types.
Likewise, {\em std\_destroy()} applies to files, directories and
processes, but not to devices.

Similarly, different file server implementations may want to offer the
same interface for operations like {\em read()} and {\em write()} to
their clients.  AIL's grouping of requests into classes is ideally
suited to describe this kind of interface sharing, and a class
hierarchy results which clearly shows the similarities between server
interfaces (not necessarily their implementations!).

The base class of all classes defines the {\em std\_info()} request.
Most server interfaces actually inherit a derived class that also
defines {\em std\_destroy().} File servers inherit a class that
defines the common operations on files, etc.

\subsection{How AIL Works}

The AIL stub generator functions in three phases:
\begin{itemize}
\item
parsing,
\item
strategy determination,
\item
code generation.
\end{itemize}

{\bf Phase one} parses the input and builds a symbol table containing
everything it knows about the classes and other definitions found in
the input.

{\bf Phase two} determines the strategy to use for each function
declaration in turn and decides upon the request and reply message
formats.  This is not a simple matter, because of various optimization
attempts.  Amoeba's kernel interface for RPC requests takes a
fixed-size header and one arbitrary-size buffer.  A large part of the
header holds the capability of the object to which the request is
directed, but there is some space left for a few integer parameters
whose interpretation is left up to the server.  AIL tries to use these
slots for simple integer parameters, for two reasons.

First, unlike the buffer, header fields are byte-swapped by the RPC
layer in the kernel if necessary, so it saves a few byte swapping
instructions in the user code.  Second, and more important, a common
form of request transfers a few integers and one large buffer to or
from a server.  The {\em read()} and {\em write()} requests of most
file servers have this form, for instance.  If it is possible to place
all integer parameters in the header, the address of the buffer
parameter can be passed directly to the kernel RPC layer.  While AIL
is perfectly capable of handling requests that do not fit this format,
the resulting code involves allocating a new buffer and copying all
parameters into it.  It is a top priority to avoid this copying
(`marshalling') if at all possible, in order to maintain Amoeba's
famous RPC performance.

When AIL resorts to copying parameters into a buffer, it reorders them
so that integers indicating the lengths of variable-size arrays are
placed in the buffer before the arrays they describe, since otherwise
decoding the request would be impossible.  It also adds occasional
padding bytes to ensure integers are aligned properly in the buffer ---
this can speed up (un)marshalling.

{\bf Phase three} is the code generator, or back-end.  There are in
fact many different back-ends that may be called in a single run to
generate different types of output.  The most important output types
are header files (for inclusion by the clients of an interface),
client stubs, and `server main loop' code.  The latter decodes
incoming requests in the server.  The generated code depends on the
programming language requested, and there are separate back-ends for
each supported language.

It is important that the strategy chosen by phase two is independent
of the language requested for phase three --- otherwise the
interoperability of servers and clients written in different languages
would be compromised.

\section{Linking AIL to Python}

From the previous section it can be concluded that linking AIL to
Python is a matter of writing a back-end for Python.  This is indeed
what we did.

Considerable time went into the design of the back-end in order to
make the resulting RPC interface for Python fit as smoothly as
possible in Python's programming style.  For instance, the issues of
parameter transfer, variable-size arrays, error handling, and call
syntax were all solved in a manner that favors ease of use in Python
rather than strict correspondence with the stubs generated for C,
without compromising network-level compatibility.

\subsection{Mapping AIL Entities to Python}

For each programming language that AIL is to support, a mapping must
be designed between the data types in AIL and those in that language.
Other aspects of the programming languages, such as differences in
function call semantics, must also be taken care of.

While the mapping for C is mostly straightforward, the mapping for
Python requires a little thinking to get the best results for Python
programmers.

\subsubsection{Parameter Transfer Direction}

Perhaps the simplest issue is that of parameter transfer direction.
Parameters of functions declared in AIL are categorized as being of
type {\tt in}, {\tt out} or {\tt in} {\tt out} (the same distinction
as made in Ada).  Python only has call-by-value parameter semantics;
functions can return multiple values as a tuple.  This means that,
unlike the C back-end, the Python back-end cannot always generate
Python functions with exactly the same parameter list as the AIL
functions.

Instead, the Python parameter list consists of all {\tt in} and {\tt
in} {\tt out} parameters, in the order in which they occur in the AIL
parameter list; similarly, the Python function returns a tuple
containing all {\tt in} {\tt out} and {\tt out} parameters.  In fact
Python packs function parameters into a tuple as well, stressing the
symmetry between parameters and return value.  For example, a stub
with this AIL parameter list:
\begin{verbatim}
(*, in int p1, in out int p2, in int p3, out int p4)
\end{verbatim}
will have the following parameter list and return values in Python:
\begin{verbatim}
(p1, p2, p3)  ->  (p2, p4)
\end{verbatim}

\subsubsection{Variable-size Entities}

The support for variable-size objects in AIL is strongly guided by the
limitations of C in this matter.  Basically, AIL allows what is
feasible in C: functions may have variable-size arrays as parameters
(both input or output), provided their length is passed separately.
In practice this is narrowed to the following rule: for each
variable-size array parameter, there must be an integer parameter
giving its length.  (An exception for null-terminated strings is
planned but not yet realized.)

Variable-size arrays in AIL or C correspond to {\em sequences} in
Python: lists, tuples or strings.  These are much easier to use than
their C counterparts.  Given a sequence object in Python, it is always
possible to determine its size: the built-in function {\tt len()}
returns it.  It would be annoying to require the caller of an RPC stub
with a variable-size parameter to also pass a parameter that
explicitly gives its size.  Therefore we eliminate all parameters from
the Python parameter list whose value is used as the size of a
variable-size array.  Such parameters are easily found: the array
bound expression contains the name of the parameter giving its size.
This requires the stub code to work harder (it has to recover the
value for size parameters from the corresponding sequence parameter),
but at least part of this work would otherwise be needed as well, to
check that the given and actual sizes match.

Because of the symmetry in Python between the parameter list and the
return value of a function, the same elimination is performed on
return values containing variable-size arrays: integers returned
solely to tell the client the size of a returned array are not
returned explicitly to the caller in Python.

\subsubsection{Error Handling}

Another point where Python is really better than C is the issue of
error handling.  It is a fact of life that everything involving RPC
may fail, for a variety of reasons outside the user's control: the
network may be disconnected, the server may be down, etc.  Clients
must be prepared to handle such failures and recover from them, or at
least print an error message and die.  In C this means that every
function returns an error status that must be checked by the caller,
causing programs to be cluttered with error checks --- or worse,
programs that ignore errors and carry on working with garbage data.

In Python, errors are generally indicated by exceptions, which can be
handled out of line from the main flow of control if necessary, and
cause immediate program termination (with a stack trace) if ignored.
To profit from this feature, all RPC errors that may be encountered by
AIL-generated stubs in Python are turned into exceptions.  An extra
value passed together with the exception is used to relay the error
code returned by the server to the handler.  Since in general RPC
failures are rare, Python test programs can usually ignore exceptions
--- making the program simpler --- without the risk of occasional
errors going undetected.  (I still remember the embarrassment of a
hundredfold speed improvement reported, long, long, ago, about a new
version of a certain program, which later had to be attributed to a
benchmark that silently dumped core...)

\subsubsection{Function Call Syntax}

Amoeba RPC operations always need a capability parameter (this is what
the `*' in the AIL function templates stands for); the service is
identified by the port field of the capability.  In C, the capability
must always be the first parameter of the stub function, but in Python
we can do better.

A Python capability is an opaque object type in its own right, which
is used, for instance, as parameter to and return value from Amoeba's
name server functions.  Python objects can have methods, so it is
convenient to make all AIL-generated stubs methods of capabilities
instead of just functions.  Therefore, instead of writing
\begin{verbatim}
some_stub(cap, other_parameters)
\end{verbatim}
as in C, Python programmers can write
\begin{verbatim}
cap.some_stub(other_parameters)
\end{verbatim}
This is better because it reduces name conflicts: in Python, no
confusion is possible between a stub and a local or global variable or
user-defined function with the same name.

\subsubsection{Example}

All the preceding principles can be seen at work in the following
example.  Suppose a function is declared in AIL as follows:
\begin{verbatim}
some_stub(*, in char buf[size:1000], in int size,
             out int n_done, out int status);
\end{verbatim}
In C it might be called by the following code (including declarations,
for clarity, but not initializations):
\begin{verbatim}
int err, n_done, status;
capability cap;
char buf[500];
...
err = some_stub(&cap, buf, sizeof buf, &n_done, &status);
if (err != 0) return err;
printf("%d done; status = %d\n", n_done, status);
\end{verbatim}
Equivalent code in Python might be the following:
\begin{verbatim}
cap = ...
buf = ...
n_done, status = cap.some_stub(buf)
print n_done, 'done;', 'status =', status
\end{verbatim}
No explicit error check is required in Python: if the RPC fails, an
exception is raised so the {\tt print} statement is never reached.

\subsection{The Implementation}

More or less orthogonal to the issue of how to map AIL operations to
the Python language is the question of how they should be implemented.

In principle it would be possible to use the same strategy that is
used for C: add an interface to Amoeba's low-level RPC primitives to
Python and generate Python code to marshal parameters into and out of
a buffer.  However, Python's high-level data types are not well suited
for marshalling: byte-level operations are clumsy and expensive, with
the result that marshalling a single byte of data can take several
Python statements.  This would mean that a large amount of code would
be needed to implement a stub, which would cost a lot of time to parse
and take up a lot of space in `compiled' form (as parse tree or pseudo
code).  Execution of the marshalling code would be sluggish as well.

We therefore chose an alternate approach, writing the marshalling in
C, which is efficient at such byte-level operations.  While it is easy
enough to generate C code that can be linked with the Python
interpreter, it would obviously not stimulate the use of Python for
server testing if each change to an interface required relinking the
interpreter (dynamic loading of C code is not yet available on
Amoeba).  This is circumvented by the following solution: the
marshalling is handled by a simple {\em virtual machine}, and AIL
generates instructions for this machine.  An interpreter for the
machine is linked into the Python interpreter and reads its
instructions from a file written by AIL.

The machine language for our virtual machine is dubbed {\em Stubcode}.
Stubcode is a super-specialized language.  There are two sets of of
about a dozen instructions each: one set marshals Python objects
representing parameters into a buffer, the other set (similar but not
quite symmetric) unmarshals results from a buffer into Python objects.
The Stubcode interpreter uses a stack to hold Python intermediate
results.  Other state elements are an Amoeba header and buffer, a
pointer indicating the current position in the buffer, and of course a
program counter.  Besides (un)marshalling, the virtual machine must
also implement type checking, and raise a Python exception when a
parameter does not have the expected type.

The Stubcode interpreter marshals Python data types very efficiently,
since each instruction can marshal a large amount of data.  For
instance, a whole Python string is marshalled by a single Stubcode
instruction, which (after some checking) executes the most efficient
byte-copying loop possible --- it calls {\tt memcpy()}.


Construction details of the Stubcode interpreter are straightforward.
Most complications are caused by the peculiarities of AIL's strategy
module and Python's type system.  By far the most complex single
instruction is the `loop' instruction, which is used to marshal
arrays.

As an example, here is the complete Stubcode program (with spaces and
comments added for clarity) generated for the function {\tt
some\_stub()} of the example above.  The stack contains pointers to
Python objects, and its initial contents is the parameter to the
function, the string {\tt buf}.  The final stack contents will be the
function return value, the tuple {\tt (n\_done, status)}.  The name
{\tt header} refers to the fixed size Amoeba RPC header structure.
\vspace{1em}

{\tt
\begin{tabular}{l l l}
BufSize     & 1000            & {\em Allocate RPC buffer of 1000 bytes}    \\
Dup         & 1               & {\em Duplicate stack top}                  \\
StringS     &                 & {\em Replace stack top by its string size} \\
PutI        & h\_extra int32  & {\em Store top element in }header.h\_extra \\
TStringSlt  & 1000            & {\em Assert string size less than 1000}    \\
PutVS       &                 & {\em Marshal variable-size string}         \\
            &                 &                                            \\
Trans       & 1234            & {\em Execute the RPC (request code 1234)}  \\
            &                 &                                            \\
GetI        & h\_extra int32  & {\em Push integer from} header.h\_extra    \\
GetI        & h\_size int32   & {\em Push integer from} header.h\_size     \\
Pack        & 2               & {\em Pack top 2 elements into a tuple}     \\
\end{tabular}
}
\vspace{1em}

As much work as possible is done by the Python back-end in AIL, rather
than in the Stubcode interpreter, to make the latter both simple and
fast.  For instance, the decision to eliminate an array size parameter
from the Python parameter list is taken by AIL, and Stubcode
instructions are generated to recover the size from the actual
parameter and to marshal it properly.  Similarly, there is a special
alignment instruction (not used in the example) to meet alignment
requirements.

Communication between AIL and the Stubcode generator is via the file
system.  For each stub function, AIL creates a file in its output
directory, named after the stub with a specific suffix.  This file
contains a machine-readable version of the Stubcode program for the
stub.  The Python user can specify a search path containing
directories which the interpreter searches for a Stubcode file the
first time the definition for a particular stub is needed.

The transformations on the parameter list and data types needed to map
AIL data types to Python data types make it necessary to help the
Python programmer a bit in figuring out the parameters to a call.
Although in most cases the rules are simple enough, it is sometimes
hard to figure out exactly what the parameter and return values of a
particular stub are.  There are two sources of help in this case:
first, the exception contains enough information so that the user can
figure what type was expected; second, AIL's Python back-end
optionally generates a human-readable `interface specification' file.

\section{Conclusion}

We have succeeded in creating a useful extension to Python that
enables Amoeba server writers to test and experiment with their server
in a much more interactive manner.  We hope that this facility will
add to the popularity of AIL amongst Amoeba programmers.

Python's extensibility was proven convincingly by the exercise
(performed by the second author) of adding the Stubcode interpreter to
Python.  Standard data abstraction techniques are used to insulate
extension modules from details of the rest of the Python interpreter.
In the case of the Stubcode interpreter this worked well enough that
it survived a major overhaul of the main Python interpreter virtually
unchanged.

On the other hand, adding a new back-end to AIL turned out to be quite
a bit of work.  One problem, specific to Python, was to be expected:
Python's variable-size data types differ considerably from the
C-derived data model that AIL favors.  Two additional problems we
encountered were the complexity of the interface between AIL's second
and third phases, and a number of remaining bugs in the second phase
that surfaced when the implementation of the Python back-end was
tested.  The bugs have been tracked down and fixed, but nothing
has been done about the complexity of the interface.

\subsection{Future Plans}

AIL's C back-end generates server main loop code as well as client
stubs.  The Python back-end currently only generates client stubs, so
it is not yet possible to write servers in Python.  While it is
clearly more important to be able to use Python as a client than as a
server, the ability to write server prototypes in Python would be a
valuable addition: it allows server designers to experiment with
interfaces in a much earlier stage of the design, with a much smaller
programming effort.  This makes it possible to concentrate on concepts
first, before worrying about efficient implementation.

The unmarshalling done in the server is almost symmetric with the
marshalling in the client, and vice versa, so relative small
extensions to the Stubcode virtual machine will allow its use in a
server main loop.  We hope to find the time to add this feature to a
future version of Python.

\section{Availability}

The Python source distribution is available to Internet users by
anonymous ftp to site {\tt ftp.cwi.nl} [IP address 192.16.184.180]
from directory {\tt /pub}, file name {\tt python*.tar.Z} (where the
{\tt *} stands for a version number).  This is a compressed UNIX tar
file containing the C source and \LaTeX documentation for the Python
interpreter.  It includes the Python library modules and the {\em
Stubcode} interpreter, as well as many example Python programs.  Total
disk space occupied by the distribution is about 3 Mb; compilation
requires 1-3 Mb depending on the configuration built, the compile
options, etc.

\bibliographystyle{plain}

\bibliography{quabib}

\end{document}