Pepsi -- not quite The Real Thing

Introduction

• as a malleable space in which to explore possible syntax and semantics for a real Smalltalk-like end-user programming platform to be built in 'Coke'; and
• as a space sufficiently simple to allow experimentation with modularity and security all the way down (subsuming the entire implementation) to the metal.

• a late-bound dynamic language can be statically-compiled and implemented in a manner that is 100% compatible with the platform ABI and seamlessly interoperable with it; and (having written a back-end generating assembler source directly) that
• a pure object-oriented language can be self-hosting without resorting to generating a single line of horrid C code; and (having written a back-end generating assembler binary directly) that
• a dynamically-compiled object-oriented language can be trivially and completely self-hosting by compiling parts of itself statically; that
• there is no reason to consider statically-compiled code (from any source) as being any less malleable at runtime than is dynamically-compiled code; and that
• the choice of whether to make a particular language/system feature/component dynamic or (effectively) static should be nothing more than a function of personal style, with no implications for malleability or performance.

idst -o foo.c foo.st

idst -I../Smalltalk -I../MyClassLibrary -o foo.c foo.st

Compiling the compiler

Smalltalk	The '.st' files containing the Smalltalk kernel classes.
etc	An 'idst-mode' for Emacs that mostly works.
example	A cheezoid example program, intended mainly as a template for your own programs.
gcX.Y	The conservative garbage collector (courtesy of Hans Boehm).
idst	The source for the idst compiler itself (written entirely in idst).
xidst	The source for the bootstrap idst compiler (written in C++).

For the record, I have tested the compiler on:

• Macintosh, OS X 10.3.8.
• Cygwin, WinXP SP2.
• Debian Linux 2.4.27.

The really adventurous might want to try building the compiler without using the precompiled 'idst.c' file supplied with the above. Typing 'make bootstrap' in the top-level directory will perform a 'classic' three-stage bootstrap. First a bootstrap compiler called 'xidst' (written in C++) is compiled. Then xidst is run to create a 'stage1' compiler from the real compiler sources ('idst/idst.st'). The 'stage1' compiler is used to create a stage2 compiler, and that in turn is used to create a stage3 compiler. Stage2 and stage3 are compared (they should be identical), leaving behind a new 'idst.c' file containing the compiler. Finally, the new compiler is used to compile a short test file (that tries hard to break various parts of the compiler and Smalltalk library). If the whole process finishes without error then you have a brand-new, perfectly healthy compiler.

"this is ignored"

Programs are translated one source file (with zero or more additional source files being imported) at a time. To the compiler, this body of code is called a translation unit. The compiler always processes one complete translation unit at a time, and currently (this is a temporary limitation) a translation unit must contain an entire program (all object and method definitions required, with no external or unresolved references).

A translation unit consists of a sequence of definitions and imperatives. Definitions either either create a new prototype or add a method to an existing prototype. Imperatives are sequences of code that are executed in-order when the program is run.

Imperatives

[ statements ]

Top-level imperatives can also take the form:

{ directive optionalArguments... }

{ import name }

Prototype definitions

name ( listOfSlots )

Such a prototype has no useful behaviour (it can't even clone itself to create useful application objects). Adding a minimum of primitive behaviour (e.g., cloning) is the first thing you'll want to do to such an object.

The second form:

name : parent ( listOfSlots )

(This is every bit as bogus as a single inheritance mechanism being used to share state and behaviour, but I'm still trying to figure out how to separate delegation from the sharing of state without sacrificing performance. Only allowing slots to be accessed by name in their defining prototype, forcing inherited slots to be accessed by message send, is probably the way to go. Better still, making all state accesses into message sends -- especially assignments.)

Method definitions

name pattern [ statements ]

The pattern component can be a unary, binary or keyword message pattern. Extending Smalltalk's fixed-arity messages, blocks associated with keyword patterns can be variadic (accomodating zero or more additional arguments, beyond those associated with explicit keywords). This is indicated by an ellipsis in the message pattern. Expanding the pattern part of the above syntax, the four valid forms of message pattern are therefore:

name unarySelector [ statements ]
name binarySelector argumentName [ statements ]
name keywords: arguments [ statements ]
name keywords: arguments ... [ statements ]

(Simply for lack of time, there is currently no friendly syntax to recover the 'rest' arguments within the body of a message. Wizards, however, can easily recover these arguments by writing some low-level 'magic' inside an external block. There will be an example of this later.)

Blocks

[ statements ]
[ :arguments | statements ]
[ | temporaries | statements ]
[ :arguments | | temporaries | statements ]

(This means that you cannot set a method-level temporary by naming it as a block argument. It also means two blocks in the same method that share an argument or temporary name will each refer to a completely different value, regardless of the common name.)

Assignment

identifier := expression

Message sends

primary unarySelector
unaryMessage binarySelector unaryMessage
binaryMessage keywords: binaryMessages
receiver messageSend ; messageSend

Extending the Smalltalk-80 syntax is the ability to send a keyword message with 'anonymous' arguments. (See the discussion above on variadic message patterns.) The simplest possible change that would allow this is to drop the name part of the keyword (but keep the colon):

receiver keywords: arguments : anonymousArgument

Parentheses

Literals

1. It's cleaner, making the semantics simpler to explain (no more confusing behaviour when a program inadvertently modifies a literal causing some method somplace to have behaviour different to that implied by its source code).
2. My C compiler puts literals in a read-only data section, at one point causing me a certain amount of stress while debugging what was ultimately correct code but containing an attempt to write into a read-only location. If all compiler-generated literals are immutable then this particular platform idiosyncracy ceases to be of any concern whatsoever.

In addition to literal Arrays

#( elements )

#{ integers }

#[ integers ]

Integer literals themselves are in decimal by default, with the usual

radixInteger r valueInteger

0xvalueInteger

Smalltalk-80 Character literals are supported:

$character

syntax	asciiValue	ASCII designation
$\a	7	bel (alert)
$\b	8	bs (backspace)
$\t	9	ht (horizontal tab)
$\n	10	nl (newline)
$\v	11	vt (vertical tab)
$\f	12	np (new page, or form feed)
$\r	13	cr (carriage return)
$\e	27	esc (escape)
$\\	92	\ (a single backslash character)

$\octalNumber

String literals obey much the same rules as Smalltalk-80. Adjacent String literals:

'like''this'

like'this

'like\nthis\n\000'

'like\'this'

Note: The 'character escape' rules above apply to Symbols too. If you want to write the literal symbol for the 'remainder on division' binary message, you have to say '#\\\\' (since the first and third backslash characters escape the second and fourth). I think this is a bug (character escapes should only be recognised if the Symbol is created from a String [so '#'\\\\' == #\\' would hold]) and intend to fix it sometime. In the meantime: beware!

Anything else...?

Semantics

• There is no built-in distinction between classes and instances. There are only objects. If you want to make some objects behave in a class-like manner, and others in an instance-like manner, that's your choice. Even the 'Smalltalk kernel' library, used by the Compiler and provided for reuse in your own programs if you want, gets by just fine without classes. (Although some ideas on how to separate class/instance concerns in a more traditional fashion are given below.)
• Blocks are real closures.
• Everything with a name (with one exception) is first-class (i.e., a variable that you can modify).

Blocks

Block contexts (activated BlockClosures) have strictly local arguments and temporaries. The value of an argument or temporary can never come into contact with, nor be affected in any way by, an enclosing lexical context. They are quite literally inaccessible. You cannot, for example, implictly assign to a method temporary by naming it as a block argument.

BlockClosures can 'close-over' local state defined in a lexically-enclosing scope. In such cases, the closed-over state will be preserved on exit from the enclosing scope, leaving it accessible to future activations of blocks defined within that scope. Each time the defining scope is entered, fresh copies of closed-over state are created. (In other words, block closures 'see' the state associated with the activation in which they were created, rather than that associated with the closure in which they were created. Things like 'fixTemps' are completely unnecessary.)

All BlockClosures are first-class (they can be stored or passed upward for activation at a later time) although block activations are strictly LIFO, with no exceptions. (Your hardware really, really wants things to be this way.)

(For the terminally-curious: closed-over state, corresponding to any variables that appear 'free' within a lexically-nested scope, are stored in a heap-allocated 'state vector' independent of the defining method or block activation context. These state vectors persist for as long as there are reachable block closures that reference them -- either explicitly, as their defining context, or implicitly, by holding a reference to a free variable stored within the vector.)

Non-local returns

There is currently one limitation: blocks containing non-local returns make no attempt to detect whether their defining method context has already returned. Attempting to return from a block whose method activation has already exited, rather than resulting in a friendly runtime error along the lines 'this block cannot return', will most likely provoke a segmentation fault and core dump. (This is really easy to fix; I'm just too lazy to deal with it right now.)

Prototypes and objects

Objects are created by being cloned, which creates an uninitialised shallow copy of the original object. By convention the 'reusable' object that you clone, to make a new object to be modified and otherwise abused, is the 'prototype' for its 'clone family'. All members of a clone family share the same behaviour (response to messages), including the 'prototype' at the head of the clone family. If you modify the behaviour of the prototype (or any other member of its clone family) then the behaviour of all members of the clone family (including that of the prototype) is modified, identically. This is something of a compromise between Lieberman-style prototypes (much simpler and more general oganisational conventions, but very difficult to implement efficiently) and class-instance systems (easier to implement efficiently, but imposing much more complex organisational conventions on their surrounding systems).

In other words, a prototype (in the sense of the present discussion) is nothing more than an object that has been:

• cloned from some 'parent' prototype object;
• had named slots added to it (according to its prototype specification);
• been associated with a fresh (empty) method dictionary, in which undound messages are delegated to the 'parent' prototype object; and
• bound to a name by which it is known to further prototype specifications and method definitions.

Foo : Point ()

" add 'Foo' to the set of visible named prototypes, then... "
  Foo := Smalltalk allocate: Point byteSize + N "size of Foo slots in bytes".
  Foo methodDictionary: (MethodDictionary new parent: Point methodDictionary).

BadVisibilityZone : Dictionary ()
[
    (BadVisibilityZone := BadVisibilityZone new)
        at: 'Archer'      put: #below;
        at: 'Warrior'     put: #below;
        at: 'Sparrowhawk' put: #above;
        at: 'Cardinal'    put: #above.
]

Note that the explicit reinitialisation (by sending 'new') of the prototype is required since the implicit cloning in the prototype specification creates an uninitialised object (in all respect other than having a valid method dictionary installed in it).

Random thoughts on class-like behaviour

Point : Object ( x y )

Point new
[
    self := super new.
    x := 0.
    y := 0.
]

Point magnitude
[
    ^((x * x) + (y * y)) sqrt
]

Another possibility would be to create parallel hierarchies, with class behaviour defined in one and instance behaviour in the other.

Point : Object ()          "the 'class' side"
aPoint : anObject ( x y )  "the 'instance' side"

Point new
[
    self := aPoint clone.
    x := 0.
    y := 0.
]

aPoint magnitude
[
    ^((x * x) + (y * y)) sqrt
]

Everything is first-class

Point new
[
    self := self clone.
    x := y := 0
]

Point new
[
    ^super new setX: 0 setY: 0
]

In the meantime, primitive behaviour has to be hand-coded (by a wizard) and inserted explicitly into the compiled code at the appropriate point. Code appearing between braces '{...}' is copied verbatim to the output. Such external blocks are legal

• at the top-level (executed in-order during initialisation, along with other definitions, directives, etc.);
• as the body of a method (the external block is the entire method body);
• wheverver a statement would be legal (in a top-level 'Smalltalk' code block, in the body of a method, or in the body of a block closure)

Here's a trivial example, showing how to send a 'Character' to the 'console', answering 'true' or 'false' depending on whether the operation succeeded:

Character : Object
(
  value    "character's value as a Smalltalk integer"
)

Character putchar
{
  struct t_Character *this= (struct t_Character *)self;
  int value= _integerValue(this->value);
  return putchar(value) >= 0 ? v_true : v_false;
}

• 'self' is known as 'self', and has type 'oop' (generic 'pointer to object');
• arguments, temporaries and globals are prefixed with 'v_' (so a local called 'foo' can be accessed as 'v_foo');
• a named prototype leaves behind a struct declaration of the same name prefixed with 't_' (so a reference to a 'Foo' can be cast to 'struct t_Foo *' for access to the structure members);
• (not shown) free variables are not readily accessible (you have to know the offset within the state vector to which they were assigned by the compiler);
• (not shown) non-local returns are not readily accessible (for a similar reason, but involving knowing where to look for a 'pointer' to the 'home' context).

Character putchar
[
    {
      struct t_Character *this= (struct t_Character *)self;
      int value= _integerValue(this->value);
      if (putchar(value) >= 0) return self;
    }.
    " fall through to failure code... "
    ^self primitiveFailed
]

sel_t _selector(char *name)

invokes the message send '_selector intern: name'.

oop _proto(oop parent)

invokes the message send 'parent _delegated'.

void _method(oop prototype, sel_t selector, imp_t method)

invokes the message send 'prototype _methodAt: selector put: method'.

The runtime system: introspection and intercession

Runtime structures

_object ()
    _selector ( size _name next )
    _binding ( selector _method )
    _vtbl ( size capacity _bindings delegate )

_object is a singleton prototype that defines behaviour common to all objects. This behaviour includes message lookup (dynamic binding), which is achieved by sending (real) messages to the objects involved. In other words, every single object created must eventually delegate to _object, otherwise it would be impossible to interact with (send messages to) that object. In yet other words, _object is necessarily the parent of every other object in the system. If you write

RootPrototype ()

RootPrototype : _object ()

_selector is an interned (unique) string, much like a Smalltalk Symbol. The selector itself is stored as a 'size' (in bytes) and a '_name' (a primitive array of bytes; i.e., of type 'char *'). The 'next' field links all the selectors into a list for purposes of interning.

_binding associates a _selector (in the 'selector' slot) with the address of native code implementing a method (in the '_method' slot).

_vtbl is a 'virtual table', similar to a MethodDictionary in Smalltalk-80. Virtual tables map selectors to method implementations for a particular clone family (one _vtbl is shared between all clones in a given family). The '_bindings' slot points to a primitive vector of pointers to _binding objects describing the virtual table's mapping. The 'size' slot contains the number of entries in _bindings, and 'capacity' is the maximum number of entries that _bindings can contain (without being grown). Finally, 'delegate' points to another _vtbl to which all unrecognised messages are delegated.

Essential protocol of runtime objects

• _object _delegated

  creates a new prototype (with an empty protocol) whose clones delegate unimplemented messages to the receiver's family. This is the only mechanism for creating a prototype hierarchy, including during object/prototype initialisation at program startup. The source form

  Foo : Bar (...)

  is equivalent to creating a new name Foo and then evaluating:

  Foo := Bar _delegated

  (The '_delegate' message has an initial underscore to avoid over-polluting the protocol of user prototypes derived from _object.)

• _selector _intern: _cString

  creates a new unique selector whose name is the given C string (a primitive string, of type 'char *' ). This is the only mechanism for creating new selectors. (The initial underscore in the selector is a convention indicating that the argument '_cString' is a primitive, non-object type.)

• _object _methodAt: aSelector put: _aMethod

  extends (or modifies) the protocol of the receiver's clone family. Subsequent lookups of aSelector in the receiver's family will be resolved to _aMethod. This is the only mechanism for adding protocol to a prototype. The source form

  Foo bar: baz [ ... ]

  is equivalent to evaluating:

  Foo _methodAt: (_selector _intern: "bar:") put: barMethod

  where "bar:" is a primitive string ('char *') and barMethod is the address of the native code implementing 'Foo _bar:'. (The initial underscore in the selector is to avoid polluting _object's protocol.)

• _vtbl lookup: aSelector

  answers (a raw pointer to the native code of) the method implementing the response to aSelector within the receiver. This is the only mechanism for performing message lookup (dynamic binding) within the system. (Note that for performance reasons the results of 'lookup:' may be memoized by the runtime system. There is currently no way to prevent this, meaning that a given _vtbl might only have one chance to influence the meaning of a given message send. This is a limitation [read: bug] and will be fixed soon.)

The implementation of the above methods (along with several potentially useful auxiliary methods in the runtime classes) can be found in the file 'Smalltalk/runtime.st'.

Additional protocol of runtime objects

• _vtbl flushCache

  causes the runtime system to purge all 'memoized' lookups stored in method caches. After invoking this method, the next send of a given selector to an object in a given protocol family is guaranteed to invoke '_vtbl lookup:' to resolve the message send. This method should be invoked after every modification of (other than monotonic additions to) protocol to ensure the changes take effect immediately.

• _object _beTaggedType
  _object _beNilType

  causes the runtime to consider tagged objects (whose oops are odd addresses) and nil (oop zero), respectively, to belong to the receiver's clone family. (For example, these messages are sent from within 'Smalltalk/kernel.st' to the prototypes 'SmallInteger' and 'UndefinedObject' to advise the runtime of the peculiar behaviour of their corresponding object pointers.

Runtime examples

A (somewhat contrived) example showing how to control the modification of object protocol and the behaviour of method lookup can be found in 'example/intercede.st'. To build and run it, type

make PROGRAM=intercede
./intercede

Object layout and object pointers

The header word is a pointer to the object's virtual table. Message sends to the object are resolved (when not present in the method cache) by sending 'lookup:' to the header object. This is the only explicit relationship between an object and the value stored in its header word.

• The first element in a SequenceableCollections is at index 0. The last element is at index 'size - 1'. This simplifies a lot of code by removing frequent adjustments of indices by 1.
• Messages that operate on a contiguous range of elements within a SequenceableCollection (such as 'replaceFrom:to:with:startingAt:') have an inclusive (zero-relative) lower bound, but an exclusive (zero-relative) upper bound. In other words, to replace the first five elements of a collection you would specify '0' and '5' as the 'from:' and 'to:' indices. This simplifies a lot of arithmetic that calculates an index from a combination of sizes involving two or more collections. (If you don't believe me, look at the definition of the concatenation message ','.)

• '+1' is legal, being the number '1' with a sign that is ignored. (In Smalltalk-80 the sign would not be legal.)
• '--1' is legal, with the negative signs cancelling out. (Similarly illegal in Smalltalk-80.)
• '3+4' is illegal, being the integer literal '3' followed by the literal '+4'. (In Smalltalk-80, the sign would be parsed as a selector.)
• '6-5' is similarly illegal, being '6' followed by '-5'. (In Smalltalk-80, the sign would be parsed as a selector.)
• The symbol '#foo:bar' is illegal, since it is not a well-formed keyword. (Smalltalk-80 happily accepts identifiers in the last position of a multi-part keyword symbol.)
• There are probably others, but I've yet to stumble across them.