diff options
Diffstat (limited to 'Doc/qua.tex')
| -rw-r--r-- | Doc/qua.tex | 1235 |
1 files changed, 1235 insertions, 0 deletions
diff --git a/Doc/qua.tex b/Doc/qua.tex new file mode 100644 index 0000000..ec7aaef --- /dev/null +++ b/Doc/qua.tex @@ -0,0 +1,1235 @@ +\documentstyle[11pt,times]{article} + +\title{ +Interactively Testing Remote Servers Using the Python Programming Language +} + +\author{ + Guido van Rossum \\ + CWI, dept. CST; Kruislaan 413 \\ + 1098 SJ 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 C++ 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 C++ 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 C++. +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 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} |