The Class language is a (toy) object-capability programming language. It has formal semantics, which allows proving that programs cannot violate the object-capability properties. I developed the language and its formal (operational) semantics as part of my master's thesis as a (more) rigorous foundation for research on object-capability programming languages.
Even though the development of Class focused on theoretical studies, having an interpreter for the language was very helpful for debugging the semantics. This repository contains an interactive interpreter for Class programs written in Python2. It supports stepping through or executing programs, as well as inspecting the resulting configurations.
I provide the interpreter here as an example for (a) how such an interpreter can be implemented by hand, and (b) how to use PyMeta for parsing. If you are developing a new programming language, instead of writing everything by hand, consider using a modern semantics framework like the K framework or Spoofax. Semantics defined in these frameworks are executable, which means that they provide an interpreter for the defined language for free.
The interpreter is implemented in Python, a dynamic programming language available on all common platforms. To be able to run the interpreter, please install Python version 2.5 or greater on your system. Please refer to Python's own documentation for instructions specific to your platform. Also, note that Python version 3.x is partially incompatible with the 2.x series of Python. The interpreter will therefore not work with it.
Besides Python itself, the interpreter relies on the PyMeta
module. PyMeta is an object-oriented pattern matcher based on
OMeta and is used for parsing the Class-programs. Please
ensure that it is available within Python's module path; you can
modify this path via the PYTHONPATH environment variable. Again,
please refer to Python's documentation for exact instructions. If
everything is set up correctly, Python's interactive command shell
allows importing the module via import pymeta. Otherwise you will
receive an ImportError exception.
No installation is required for the Class interpreter---you can
start it directly from the downloaded repository. Simply execute the
file class_interpreter.py.
The interpreter provides an interactive shell for loading, executing
and inspecting Class programs; its prompt is the string Class Interpreter>. In the text below, typewriter style denotes
interaction with the interpreter.
Most of this section's documentation is available on line within the
interpreter. You can use the command help to retrieve a list of
available commands. To receive further information on a command c,
enter help c. Issuing exit or quit will terminate the
interpreter. An empty line repeats the previous command.
Note that you can speed up typing by using command and parameter
completion with the Tab key if the readline Python module is
installed. Hitting the Tab key twice will present you with a list
of possible alternatives. Readline comes as a part of Python itself
on Unix and related operating systems such as Linux and MacOS~X.
A typical session with the interpreter starts with loading a program
through the command load.
Syntax: load <file name>
The command loads and parses the program stored in file . It returns nothing on success, but prints an error message if the file could not be opened or the contents could not be parsed.
Please note that a limitation of the PyMeta pattern matcher reduces the helpfulness of error messages. The construct reported as causing the error only marks the beginning of the biggest part that failed. Hence, a whole construct, such as a class declaration, is tagged wrong if one of its parts contains errors, for example if a method body misses a semicolon.
Example. The interpreter comes together with an example program in
the file busy.cls that simulates the 3-state busy beaver. We want
to experiment with it and therefore load it into the interpreter.
This results in below interaction.
Class Interpreter> load busy.cls
Class Interpreter>
Loaded programs can be executed with the step command. It applies
the transition relation times to the current
configuration.
Syntax: step [<number of steps>]
Note that it typically takes several applications of the transition relation to execute a Class statement. Therefore, is always higher than the number of statements the program advances. If the number of steps is omitted, the program executes a single step.
The command returns nothing on success and issues a note if the program terminated. The final store's contents will remain available after the program finished. However, the then-current frame contains no variables and, hence, does not allow browsing through the store. See the discussion on labelling objects for a workaround of this limitation.
Example. Suppose we knew from previous experiments that it
requires 37 steps to execute all initialisation statements of the busy
beaver program. Continuing above example, we fast forward to the
point where the run() method is called as shown below.
Class Interpreter> step 37
Class Interpreter>
How is it possible to know the number of steps it takes until a
certain statement? A simple approach is to small-step through the
program and check the intermediate configurations' statements with the
program command.
Syntax: program
The command prints the statement of the current configuration. The code reflects all transformations that were applied during the execution up to this point.
Example. Picking up the example again, we check whether 37 steps really took us to the right statement in the program.
Class Interpreter> program
[
{ self.run() };
return self
]
Class Interpreter>
Note that the interpreter employs its own pretty printer to output the statements. Indentation and line-breaks will therefore possibly differ from the source file's contents if you invoke the command directly after loading a program.
Beside the current configuration's statement, it is also possible to
inspect its store. The command inspect allows looking at objects.
Syntax: inspect [--depth <depth>] <object path>+
The optional parameter specifies the inspection depth d. With d=0, only the specified object obj itself will be printed on the screen. A depth of d>0 will treat all objects that obj holds references to (in its member variables) as being specified, too, with a depth of d-1.
A list of object paths specifies which objects to inspect. An object
path is a, possibly empty, string that describes a reference to an
object in the store. It consists of segments joined by periods.
For example, the object path one.two has two segments: one and
two.
Each segment names a member variable in the object designated by the
previous segment. Their combination then stands for the reference
that is the value of this last member variable. In above example,
path one.two denotes a reference to the object that member variable
two of (the object referred to by) one points to.
Object paths always start at the current frame object pointer. Hence,
the path one means the reference that is the value of the current
frame's member variable one. Because scoping requires indirection,
the object referred to is variable one's container. Consequently,
path one.one is the value of variable one in the current scope.
See the thesis section on memory contents in Class for a detailed
explanation.
Note that Tab completion also works for object paths: Pressing Tab
once completes the segment under the cursor as far as the current
prefix is unique; pressing it twice prints a list of valid
alternatives.
Example. After having seen the current configuration's statement in the previous subsection, we have a look at some of the objects. We start by inspecting the current frame.
Class Interpreter> inspect
================================
Object at ref:0x8a3e8cc
================================
char_0 -> ref:0x8a3e06c
char_1 -> ref:0x8a3e06c
current_state -> ref:0x8a3e06c
false -> ref:0x8a3e06c
head -> ref:0x8a3e06c
int:CLASS -> ref:0x882c28c
int:PREV -> ref:0x8a3e10c
self -> ref:0x8a3e14c
state_A -> ref:0x8a3e06c
state_B -> ref:0x8a3e06c
state_C -> ref:0x8a3e06c
true -> ref:0x8a3e06c
--------------------------------
--------------------------------
Class Interpreter>
Afterwards we check the cell under the Turing machine's read and write head.
Class Interpreter> inspect head.head
==================================
Object at ref:0x8a3ec0c
==================================
content -> ref:0x8a3eb8c
default -> ref:0x8a3eb8c
left_neighbour -> ref:0x8a3ec0c
right_neighbour -> ref:0x8a3ec0c
----------------------------------
left()
read()
right()
set_left(l)
set_right(r)
write(c)
----------------------------------
Class Interpreter>
Internalised names are accessible through a special prefix to a
segment. The segment internal:class, or i:c for short, denotes
the internalised name class. Likewise, internal:previous or i:p
is the internalised name prev.
Two ways to describe absolute references complete above relative path
segments. The first is by label via label:foo where foo was
assigned beforehand to an object path using the command label.
Prefix l: is an abbreviation for label:. The second way is by
memory address using the prefix reference: or r:.
Example. The command inspect i:prev.x.x lets us look at the
object that is the value of variable x in the previous frame.
It is often convenient to remember objects for later inspection. The
command label makes it possible to tag an object denoted by an
object path with a user-defined name . This
makes it easy to retrieve the object, even if it would be complicated
to address from within the current frame.
Syntax: label <object path> <name>
Afterwards, use the segment label:<name> to refer to the object.
This form will also be used as the preferred name when looking at
objects with inspect.
Set labels can be removed with the command unlabel.
Syntax: unlabel <name>
If an object path---even with a label: structure---is used as
argument instead of a simple name, all labels to the specified object
will be removed.
Example. Let us continue working with the busy beaver from the
previous example. Our goal is to inspect the final tape contents. A
possible approach is to remember the frame from the constructor and
check the bound variable head after the program terminated. For
better readability, we also assign names to the tape symbols 0 and 1.
Class Interpreter> label . cframe
Class Interpreter> label char_0.char_0 0
Class Interpreter> label char_1.char_1 1
Class Interpreter> step 500
The program finished execution after 386 steps.
Memory contents remain available for inspection
until a new program is loaded.
Class Interpreter> inspect l:cframe.head.head
==================================
Object at ref:0xa571e8c
==================================
content -> label:1
default -> label:0
left_neighbour -> ref:0xa56cc0c
right_neighbour -> ref:0xa5828ac
----------------------------------
left()
read()
right()
set_left(l)
set_right(r)
write(c)
----------------------------------
From this cell on we can use the left_neighbour and
right_neighbour member variables to traverse the whole tape.
Copyright (c) 2008--2012 Peter Dinges pdinges@acm.org.
The software in this repository is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
The software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.