One-shot continuations

Neutrino has two basic control structures: method calls and one-shot continuations. In my last blog post I outlined how method calls work. In this one I’ll outline one-shot continuations.

You may already be thinking: continuations? Seriously? But it’s not as hairy as it sounds. First of all, these are one-shot, not fully general call/cc. It’s really just a convenient way to define all the usual control structures, including break, continue, and local and non-local return, in terms of one fundamental construct. In particular, one-shot continuations are, even in the most general case, no more expensive in terms of implementation complexity than non-local returns.

In the current syntax (I’ll get back to the topic of syntax and why you shouldn’t focus too much on that later) a one-shot continuation use looks something like this:

with_1cc (return) {
for (i : 0 .. 10) {
if found_it(i)
then return(i)
}
-1;
}

What’s happening here is: at the beginning of the with_1cc statement we capture the current continuation and store it in a variable called return. We then loop from 0 to 9 and, if a condition holds, invoke the continuation and immediately yield the specified value as the result of the with_1cc expression without executing any more of the body. If the condition doesn’t hold then the continuation is implicitly invoked with the result of the body which is -1. Invoking a one-shot continuation more than once is an error and the final implicit call ensures that you’ll get an error if you try to invoke the continuation after the with_1cc expression has completed.

That’s all there is to with_1cc: it gives you a function that you can call — once — to bail out of an arbitrarily nested computation and yield a value to the whole expression. Cases like above where the capture and use of the continuation occur together in a single function are easy for the compiler to recognize and for those it can generate code that doesn’t actually materialize the continuation but simply uses a jump to leave the expression. This will work in any situation where you could use break, continue or local return in a standard C-family language:

def my_function() {
with_1cc (return) {
// ... prepare loop ...
with_1cc (break) {
for (i : 0 .. n) {
with_1cc (continue) {
// ... loop body ...
}
}
}
// ... finish ...
}
}

The above code is obviously very verbose and luckily you wouldn’t have to actually write that in neutrino — the syntax is flexible and the compiler is free to automatically introduce with_1ccs when required. The point is that this can be used to implement any of the basic local jumps from the C-like languages, except for goto, and generate as efficient code for each of them as in languages where they’re built-in. In addition to mimicking other control structures it also allows patterns that are not possible on C-like languages, like expression-local returns:

def matching_entry := with_1cc (leave) {
for (entry : this.entries) {
if entry.name = name
then leave(entry);
}
}
print("Found entry: ${matching_entry}");

This code loops over a list of entries and leaves the loop, but not the whole function, immediately when the appropriate one has been found. This can be simulated in various ways: creating a utility method that uses normal return, assigning to matching_entry and breaking out of the loop, or inlining the action to be performed with the result at the place where the result is identified. Using with_1cc you can express the behavior directly without the need for workarounds. And, again, this comes without any performance penalty since the control flow can be resolved statically and the continuation doesn’t have to be materialized.

In the case where the continuation is not used locally it behaves similarly to non-local returns in language that support that, like Smalltalk. The difference is that where non-local return ties the return to a method call, with_1cc lets you return to an arbitrary expression. Other than that they are completely equivalent.

As mentioned, the syntax of neutrino is flexible and there’s every reason for libraries to introduce shorthands based on this construct that allows it to be used without the full syntactic complexity. This is a basic building block that the base language supports, not something you’re likely to see that often in its naked form.

Update: Kevin Millikin points out that just calling the continuation on exit isn’t enough to ensure that it won’t get called more than once. Kevin’s counterexample is

def get_me_back_in := with_1cc (get_me_out) {
with_1cc (invoke_me_later) {
get_me_out(invoke_me_later);
}
}
print("hest");
get_me_back_in(...);

Here we escape the implicit invocation of invoke_me_later by leaving via a surrounding continuation. Bummer. This issue is present in any language with non-local return that can be captured, for instance SmallTalk:

outer
| innerReturn |
innerReturn := self inner.
^ innerReturn value: 5.

inner
^ [ :v | ^ v ]

(I just tried this in Squeak; you get a BlockCannotReturn exception.)

The solution is to enclose the body of the with_1cc in an unwind-protect that ensure that no matter how we leave the with_1cc, the corresponding continuation will be disabled. Divorcing calling a continuation from disabling it does mean that the name “one-shot continuation” stops being accurate so I’ll probably have to come up with a more fitting name.

One thing I haven’t written about yet are coroutines, which neutrino also supports. Mixing not-really-one-shot-continuations-anymore with those is also interesting but that is a future blogpost.

Methods

Neutrino is an object-oriented language and as such the most fundamental operation is the method call. Neutrino methods are not smalltalk-style single dispatch ones, however, but multimethods.

The smalltalk model is nice and simple — but also limiting in practice. This obviously doesn’t just apply to smalltalk but any single dispatch language. You find yourself repeating the double dispatch pattern over and over. Operations that are binary by nature, such as addition and equality, are difficult to express in a way that is fully general. Generalizations such as catch-all methods or proxy objects can be awkward to express. Single dispatch is like an iceberg: the tip, the mechanism itself, has little complexity but there is a huge amount of hidden complexity that comes from having to express operations that are not, by nature, singly dispatched using only that mechanism. With neutrino I wanted to try a slightly more complex basic mechanism, under the assumption that it would reduce the amount of hidden complexity drastically.

The mechanism works like this. When defining what looks like a method you’re actually defining a matcher, so

def (this is Point).norm()
-> Math.sqrt(this.x*this.x + this.y*this.y);

might look like a method definition on Point but is, in reality a matcher that matches any call where the name is "norm" and the first argument is an instance of Point. Similarly,

def (this is Point)+(this is Point) -> ...

is not a method on Point but a matcher that matches any call with the name "+" and a first and second argument which are Points.

Using this model method lookup becomes a matter of, given a call, finding the matcher that best matches the call. This is done using a scoring function which, for each possible matcher, gives an integer value to each entry in the matcher and then takes the lowest scoring (best matching) function. In the first example, if you pass a Point then the match is perfect and the score is 1. If you pass an instance of a subtype, say a CartesianPoint then the match is less perfect and the score is 1 + the shortest distance through the inheritance hierarchy. This means that if there is a more specific method, one that takes a CartesianPoint, then it will score lower and be preferred over the method that takes general Points. If no method matches a LookupError is thrown. If there is no unique best match then an AmbiguityError is thrown. That’s it.

When matching, all parts of the matcher are treated equally. Some parts will usually be known at compile time, for instance the method name, which means that the compiler will be able to generate more efficient code. However, that is an implementation detail and the method name is a parameter like any other. In particular, a matcher that matches any String as the name and a Point as the first argument is as valid and no different from one that happens to have a compile-time known name.

I’ve been using this mechanism for a while and find it to be much more convenient than single dispatch. There is really no comparison. No more visitors, you get to just express what you’re trying to do. Multimethods are often accused of being confusing and hard to understand. I think this is a matter of keeping the lookup rules simple and not being afraid to report an error if there is no obvious best match, rather than use elaborate tie-breaker rules.

This may look like a challenge to implement efficiently but the mechanism has been designed such that you only pay for the generality if you actually use it. If you do normal single or double dispatch with compile-time known method names then that’s what you pay for and, in particular, double dispatch can be less expensive because you can express it directly rather than through chains of separate calls, which means that the system can more easily optimize for it.

I’ve written up the details of the mechanism on the wiki under MultiMethodDispatch. This also describes how this works with keyword methods, which neutrino has but which I haven’t described here.

Neutrino

In the past I’ve written on this blog about various programming language projects I’ve been working on, including neptune and saturn. It’s been a while though, mainly because I’ve been working on v8 and spent more than enough time implementing languages at work so I didn’t have the energy to do it as a hobby as well.

That is no longer the case and I am indeed back on the horse working on the next language, neutrino. I’m trying a different approach to writing about it this time since there are a lot of interesting implementation issues as well as language design issues. I’ve started a new blog, the neutrino blog, where I’ll post about language design and implementation progress. Go on, take a look!

What is neutrino?

One of my plans with this blog is to keep it light and stick with relatively short posts about a single thing at a time. I’m planning to start writing about what neutrino is and, in keeping with the plan, I will do it in a number of separate posts rather than one big one. In this one I’ll talk about what the goal of neutrino is.

What is neutrino? It is a new programming language and implementation. I’ve implemented a lot of experimental programming languages in my spare time. Some I’ve written about, like neptune and saturn. Most of them I haven’t because they’ve just been experiments that lived on my laptop and nowhere else. Neutrino is the next programming language in the sequence and the first one I’ve worked on for this long and still felt that everything fits together just as it should.

Here’s a snippet of neutrino code, a teaser. The syntax isn’t actually that important and will change over time so don’t pay too much attention to that. I’ll explain the details of what’s going on here in future posts.

protocol ElfStringTable is ElfSection;

def ElfStringTable.new() {
def result := new ElfStringTable {
table := new HashMap(),
strings := new ArrayList(),
r_size := new Ref(0)
};
result.ensure("");
result;
}

def (this is ElfStringTable).alignment -> 1;

def (this is ElfStringTable).size -> this.r_size.get();

def (this is ElfStringTable).name -> ".strtab";

def (this is ElfStringTable).type -> 3; // SHT_STRTAB

def (this is ElfStringTable)[key]
-> this.table[key];

def (this is ElfStringTable).ensure(key) {
def prev := this.table[key];
if prev = null then {
def index := this.size;
this.table[key] := index;
this.r_size.set(index + key.length + 1);
this.strings.add(key);
index;
} else {
prev;
}
}

def (this is ElfStringTable).encode(out, elf) {
def info := elf.layout.info(this.name);
assert_equal(info.start, out.length);
for (str : this.strings)
out.write_c_string(str);
assert_equal(info.end, out.length);
}

This is taken from the ELF file encoder that is part of neutrino’s linux implementation.

Besides some original ideas, neutrino takes its inspiration from a number of different places. Its concurrency and security constructs resemble those in E (the overall syntactic similarity with E is a coincidence though). The module mechanism is inspired by newspeak. The multi-stage programming model is inspired by MetaML and APT. The implementation approach and low-level programming library are very much inspired by the jikes RVM. There are many more examples like these.

These are all good ideas that are not available in any mainstream languages. There is great potential in creating a solid high-performance language implementation that combines these different ideas within one coherent model. The goal of neutrino is to do that.

Plankton

Neutrino needs to be able to encode object graphs as dumb data, for a number of reasons: as a wire format when communicating between processes over a binary connection, as an image format for binary images, as a serialization format for “paging out” whole processes, etc.

I’m already using a format which is the output of the neutrino compiler written in Java and which is the source format used by the neutrino native compiler written in neutrino, PIB (platform-independent binary). This format, however, is lame.

Before I start implementing its replacement, plankton, I decided to write down a draft specification, which has been a good opportunity to stop and think before forging ahead with an implementation. This format is simple, general, and compact. In particular, the template mechanism means that object graphs (trees really) representing syntax trees can be encoded as something no more verbose than bytecode in a way that doesn’t require special support — it falls out of the encoding mechanism automatically.

This specification is sure to change as I implement and use this but now the basics are there.

Linker Failure, Data Success

Over the last few weeks I’ve spent a lot of time trying to generate ELF files that would make the linux linker happy. Using the standard ELF tools like readelf and nm I got pretty far in generating structurally correct files, but ld just didn’t want anything to do with them, it said the files were in an unsupported format.

Finally I decided to build gold and trace through the code while it tries to link to see what makes it choke. This way I discovered the first problem: it had nothing to do with the file format, I had just accidentally used a 1-based index a place where I should have been using 0-based. It turns out that ld‘s error messages are not the model of accuracy. Hrmf.

The trouble didn’t end there, however, and I ended up building my own version of ld and tracing through that to figure out what the problem is. The code in ld does reveal some of the limitations inherit in C, as exemplified by the wonderful RELOC_FOR_GLOBAL_SYMBOL macro which is an absolute delight to debug.

Yesterday finally I gave up linux linking for now and spent some time working on static data in Mach-O files, which now works. The neutrino compiler can now embed data which is accessible to the generated program. This is an important step towards the generated runtime so I’m pretty excited about that. The next step is to be able to store complete object graphs, which will require some object pointer relocation fun in the generator. But I think we’re close to having all the fundamental building blocks in place for self hosting the language.

Macho Elves

Most of my time working on neutrino these days is spent generating object files. I had originally planned to generate executables directly and had a limited version of that working. However, I quickly ran into trouble with dynamic linking, which is required as soon as you want your program to interact with the surrounding system in any way.

Eventually I learned that you’re much better off interacting with the system through calls to the standard C library because libc is more stable than the underlying system call API. And you’re much better off letting the system linker turn your object files into executables than generating those executables yourself. It’s not that it’s impossible to do it yourself but it’s painful and I’m fine with letting the linker developers deal with that pain.

So now I’m working on generating native object files which means that I’ve spent a lot of time poring over the Mach-O file format reference and, lately, the ELF specification. They’re nice straightforward formats actually but it still takes a lot of time to shape the program output into the required form. The tools for working with object files are really good, otool and nm on mac and readelf on linux, and make this work a lot easier.

The current status is that you can build .o files on mac and link them into executables that can be run to successfully. As in

$> scons neuneu
[scons output]

$> ./bin/obj/neuneu.ia386.mach-o
int32 comparison
int32 arith
raw malloc
struct malloc
char_ptr_t
static data

What’s running there is neutrino code, compiled by neutrino code.

What I’m working on now is being able to do the same on linux and then the next step, the ability to store nontrivial data structures in object files. I will also need to eventually generated DLLs but since mac and linux are the only platforms I use regularly they’re the ones I’ll start with.

Ne.utrino.org

After existing just as a googlecode project, antineutrino, for a while I’ve finally started building an actual home for the neutrino project at ne.utrino.org. The code still lives at googlecode but there is now also a wiki, this blog, a main page and google docs.

This blog will be used to post development updates about the progress of the project and various topics about the neutrino language and platform.

Scribble

I recently came across an old note pad I had been using about two years ago. I like to keep all my old note pads; they’re like raw dumps of what I was doing then and the ideas I was playing around with. This particular one was the one I was using while reading the World’s Writing Systems, the mother lode for anyone interested in writing systems.

The image on the right is one of the pages. After reading about so many different writing systems I just had to try making my own. The underlying language is English but unlike the latin system it has only a cursive form and makes heavy use of diacritics, which makes it a lot more compact and altogether just a very different kind of system to use.

Actually, what you see is the system in its most primitive and childish rendering. It’s very geometric and angular, like something you might see on an alien spaceship in a bad science fiction movie. That’s not exactly the look I was going for. But then I had only just learned it when I wrote this. My idea was to actually learn to use it, learn which corners could be cut without losing readability, evolve some comfortable ligatures, basically the same thing I did to get from the handwriting I had when I first learned the latin alphabet to my current utilitarian but definitely more aesthetically pleasing hand. That takes a long time but if I don’t lose interest before then I’ll be back in 10-15 years to present a much nicer-looking cursive handwriting.

Scsh

I use shell scripts a lot. To automate things I do often. To tie together different commands like grep and sed. For one-shot tasks like running the same command 100 times and calculate the average execution time. Basically, when want to instruct my machine to carry out some operation I’ll almost always do it by invoking a shell script, usually one written by myself.

Up until I left the v8 project I’d written most shell scripts in bash or, if that became too horrible, python. But when I left v8 to work on wave I made a decision: no more. I don’t want to be stuck with a choice between a language that is, frankly, grotesquely horrible, bash, or one that is okay but just not made for what I was using it for, python.

That’s when I remembered scsh, the scheme shell (pronounced “skish”, rhymes with fish). I had read Olin Shivers’ report on it and of course the famous acknowledgements and I’d always thought it was a brilliant idea to use scheme as a glue language. I’d never actually tried the tool though so I decided that this was the perfect time to give it a try.

The latest release of scsh is from 2006. You don’t get the impression that it’s a project under active development. It’s also not available on most system I use. This would normally have put me off but the though that it might rid my life of bash motivated me to give it a try anyway.

On mac it’s easy to install, just

sudo port install scsh

On my linux machine I had to build and install it myself, and I had to tweak the build files a little for it to build on a 64 bit machine; if I remember correctly all I had to do was add -m32 at the right place in a generated Makefile.

Having installed it I was ready to start running shell scripts written in scheme. Or so I thought. I wrote my first script,

#!/usr/local/bin/scsh

(display “Hello World!”)

and ran it. No dice.

$ ./helloworld.ss
Unknown switch ./helloworld.ss 
Usage: scsh [meta-arg] [switch ..] [end-option arg ...]
meta-arg: \
switch:
... snip ...
-s <script> Specify script.
... snip ...

Ah, I forgot to use the -s option. Add that, try again:

$ ./helloworld.ss
Error: EOF inside block comment -- #! missing a closing !#
       #{Input-port #{Input-channel "./helloworld.ss"}}

Okay, now it’s running the script in scsh but it chokes on the #!. For a language designed to run shell scripts it’s surprisingly uncooperative. After experimenting a while and a few google searches I came upon the required magic enchantment. My script was now:

#!/usr/local/bin/scsh -s
!#
(display "Hello World!")

While this violates POLA in 100 different ways it works. Yay! The reason it works is because #! ... !# happens to be the block comment syntax in scheme, or at least scheme48 which is the implementation scsh is based on.

Okay, now I could start actually using it to write scripts. The first thing I wanted to implement was a set of wrappers that helped keep track of a handful of git clones of the same underlying non-git repository. That way I can keep tests running and build output intact in one workspace while I work on something else in another separate one, something that using different git branches in the same workspace doesn’t give you.

Scsh uses macros and unquote to run external commands so for instance this function,

(define (git-new-branch name)
  (run (git checkout -b ,name))

will run the command

git checkout -b <name>

The , means that the value of the parameter name should be inserted there. The output goes to standard output. You can also get the output back as a list of strings by using run/strings instead of run. As an example of using that here’s a function that returns whether or not a git repository has pending changes:

(define CHANGE-RX
  (rx (| "Changed but not updated:" "Changes to be committed:")))
(define (git-has-changes)
  (call-with-current-continuation
    (lambda (return)
      (define (process-line line)
 (if (string-match CHANGE-RX line)
     (return #t)))
      (let ((output (run/strings (git status))))
 (map process-line output))
 (return #f))))

This code runs git status and then iterates through the strings returned looking for the string Changed but not updated: and Changes to be committed:, returning immediately when it finds one. Scsh comes with a rich regular expression library which is the rx part above. It’s more verbose than POSIX regexps and does lack some of the conveniences, but is on the other hand much more straightforward and readable and seems to be at least as, if not more, powerful.

At this point you may say: hey, I could have written that function in one line using grep. And you could. The difference is that when I use grep the complexity of my script increases exponentially with the complexity of what I’m trying to accomplish. With scsh a script may start out a bit more verbose, as above, but when the script grows a little more complex, as they tend to do, I can solve the problem using standard high-level programming constructs that are already hardwired in my brain instead of having to pore over the grep manpage to figure out how I make it do what I’m trying to do.

For instance, I can write a one-line script using find and sed that removes all lines containing a.b.c.X from a file, easy. But if I want to extend my script a bit so it only removes a.b.c.X when it occurs within a block of lines enclosed in square brackets that also contains a.b.c.Y the problem has become too complex for me to solve by chaining together shell commands. I’m sure it can be done but I would have to spend an inordinate amount of time figuring out how. On the other hand, doing this in scsh I can solve each individual problem separately: finding blocks enclosed in square brackets, searching for a.b.c.Y, deleting lines containing a.b.c.X, and and combine the individual operations using standard language constructs.

;; This script removes all lines enclosed in brackets containing
;; |to-be-removed| but only if the block also contains
;; |removal-indicator|.
(define (main args)
  (let ((to-be-removed (cadr args))
        (removal-indicator (caddr args))
        (file-name (cadddr args)))
    ;; Regexp matching python lists
    (define LIST-RE
      (rx (: "[" (submatch (* (~ "]"))) "]")))
    ;; Regexp matching lines containing |to-be-removed|.
    (define STRIP-REMOVED-RE
      (rx
        (: #\newline 
           (* (~ #\newline)) 
           ,to-be-removed
           (* (~ #\newline)))))
    ;; Processes all matches
    (define (process-input str)
      (regexp-substitute/global
        #f LIST-RE str 'pre process-list 'post))
    ;; Processes the contents of square brackets
    (define (process-list match)
      (let ((result-contents (remove-if-required
                               (match:substring match 1))))
        (string-append "[" result-contents "]")))
    ;; Removes all occurrences of |to-be-removed| where it is
    ;; together with |removal-indicator|
    (define (remove-if-required str)
      (if (and
            (string-contains str removal-indicator)
            (string-contains str to-be-removed))
          (strip-removed str)
          str))
    ;; Removes one line containing |to-be-removed|
    (define (strip-removed str)
      (regexp-substitute/global
        #f STRIP-REMOVED-RE str 'pre "" 'post))
    (let*  ((input-port (open-input-file file-name))
      (input (read-string 100000 input-port)))
      (display (process-input input) (open-output-file file-name)))))

This is more verbose but took a lot less time to write and debug than it would have taken me to write an equivalent bash script, and it will be much easier to understand and extend later on. And this is scsh competing with bash where bash is strong. As the complexity of your script increases the power of scsh’s abstractions becomes more and more apparent. Here’s the command I use to update all my git clones from the central repository, using one über-workspace that stays in sync with the underlying repository and then a number of unter-workspaces that clone the über-workspace:

;; Performs the work of a 'sync' operation.
(define (run-sync)
  (within (@workspace UBER-WORKSPACE)
    (within (@git-branch MASTER-BRANCH-NAME)
      (sync-from-repository)))
  (for (workspace in UNTER-WORKSPACES)
    (within (@workspace workspace)
      (pull-from-master workspace))))

This is not pseudo-code, this is literally the code that is run. The within form takes care of entering something, a directory, branch or whatever, carrying out an operation and leaving again, dealing gracefully with errors at any point. The sync-from-repository and pull-from-master functions are straightforward one-line calls to external tools. I usually wrap external calls in a function that includes logging to make debugging easier.

The above function uses a number of generally useful abstractions, including the within and for forms which, it should be noted, are not built into scsh, I defined those myself using scheme’s define-syntax. You would obviously like these abstractions to live in separate files that could be shared between different scripts. Importing or including other files is not one of scsh’s strong sides. There is a module system that I have no doubt is powerful and clever, but I just didn’t have the patience to figure out how it worked so I use a scsh runner script that takes care of loading libraries before starting your script:

#!/bin/sh
#
# Usage: scsh.sh <scsh script> <options> ...
#
# Loads the specified scsh script and all .sm files in the same
# directory and calls the 'main' function.
SCRIPT=$1
ROOT=`dirname $SCRIPT`
LIBS=`ls $ROOT/*.sm | sort | xargs -n1 -i@ echo -l @`
MAIN=main

exec /usr/local/bin/scsh $LIBS -e $MAIN -s $*

Using this script rather than calling scsh directly I can factor utilities out into .sm (scsh module) files and have them loaded automatically. And with a library loading mechanism in place, and a bit of practice with scheme and some basic convenient utilities in place, scsh is an extremely powerful tool. Here are some more examples taking from my scripts.

Here’s an example of defining command-line options

(define parse-options
  (option-parser
    ((--runs r)
      (set! number-of-runs r))
     (--help
      (exit-with-usage))))

The option-parser form lets you define a number of command-line options and the action to perform when the option is encountered. It returns a function that performs the appropriate processing and returns a list of those arguments that were left when removing all the ones that were recognized.

This command enters the branch in the über-workspace that corresponds to your current git branch in an unter-workspace and asks for the underlying changelist id:

(define (get-current-cl)
  (let* ((all-branches (git-list-branches))
         (current-branch (car all-branches)))
    (within (@review-client current-branch)
      (get-current-cl))))

Again, this command actually does a lot of work but you hardly notice because it’s all been packed away in the various abstractions. You only see the high-level structure of what’s going on.

This command pushes the current unter-workspace branch to the über-workspace, enters that branch and exports it as a change against the underlying repository:

(define (run-export)
  (let* ((all-branches (git-list-branches))
         (current-branch (car all-branches)))
    (git-push "origin" current-branch)
    (within (@workspace UBER-WORKSPACE)
      (within (@git-branch current-branch)
        (export-change)))))

Overall I’d suggest that if you’ve ever been frustrated with traditional shell scripts and have a basic knowledge of scheme, or want to learn it, you should give scsh a chance. I’ve never been a lisp or scheme fanatic but despite some amount of unfriendliness from the tool itself, including the odd way you have to invoke it and poor error reporting, I’ve been totally won over. Scsh FTW!