Arcueid 弧

Well, it’s been seventeen days or so since I embarked upon this project, and now the core of the experimental branch is able to load and run all of arc.arc and it passes the old unit tests that I created for the master branch way back when. Next step is to build a new thread dispatcher and REPL then we’ll have a 0.1.0 release. Now we’ll have no more nonsense about having oddly built continuations done by copying the C stack, and have more nonsense about a large number of functions using Duff’s device to provide what amounts to continuations on a trampoline. XD

Posted in arcueid, devnotes

As I mentioned previously I have begun rewriting the interpreter core to address some of the deficiencies I had encountered in the previous architecture, most notably how the C interface fits in, as this seems like a rather fundamental deficiency. I am presently reworking the core interpreter to fit into the new architecture, and while I’m at it, I might as well begin making some optimisations that I should have tried to do.

I ran across a paper by Richard A. Kelsey: Tail-Recursive Stack Disciplines for an Interpreter, where he describes some techniques for managing continuations and such on the stack. Essentially, what previous versions of Arcueid have done is essentially store all environments and continuations on the heap, as Appel suggests. This seems like the most logical thing to do, because Arc’s parameters are substantially more complicated than Scheme’s or those of other Lisp dialects. There are optional parameters, rest parameters, and most complicated of all, destructuring binds. Arcueid’s compiler essentially copies all parameters off the stack and into the heap, performing destructuring binds and the evaluation of optional arguments as they are required, so that parameter access is as simple as possible. However, this is slow because every parameter is copied from the stack to the heap, and tail calls, such as they are, produce large quantities of garbage that might not be immediately collected.

What we can try to do, however, is use the stack itself to store environments, as the values were already put there by the caller to begin with. Of course, optional arguments, rest parameters, and destructuring binds still need to be handled, and there are a number of approaches we can take to handle this in our interpreter.

The env instruction that creates environments can instead be a three-parameter instruction that takes the number of flat arguments that should be present, the number of optional arguments after the last one, and the number of additional arguments that are to be bound to the destructuring binds. The instruction does the following things:

1. The first parameter determines the minimum portion of the stack that becomes part of the environment, with destructuring bind arguments being counted as only one argument for these purposes. These are the minimum number of parameters that can be passed to the function.
2. The second parameter determines how many destructuring bind parameters are added.
3. The third parameter determines how many optional parameters can be expected from the stack.

The env instruction thus sets up the stack to hold an environment that includes all parameters that have been pushed on the stack, determines which optional parameters were unbound, and adds extra space for destructuring bind arguments. For example, for this rather complicated parameter list:

(fn (a (b c) d (o e d)) ... )

The env instruction would be env 3 2 1, making an environment that is six elements in size. The environment entries would thus be:

3b

Additional instructions to destructure environment slot 1 and bind the results to envronment slots 3 and 4 then follow, as will an instruction to check if environment slot 5 is already bound to some value. If not, instructions to compute the default value are available.

Tenatively the above parameters should compile to something like:

env 3 2 1
; Destructuring bind instructions
lde 0 1
car
ste 0 3
lde 0 1
cdr
car
ste 0 4
; Optional arguments
lde 0 5
jbnd L1
lde 0 2
L1: ...


The new instruction jbnd (jump if bound) is used to jump if the value register is not the value CUNBOUND.

The envr instruction is used for parameters that look like this:

(fn (a (b c) d (o e d) . f) ... )

That would be envr 3 1 2, making an environment that is seven elements in size.

The rest parameters are bound up by the envr instruction so with the sole exception of envr replacing env as needed.

What happens when a closure is returned, like say for a higher-order function, or when call/cc creates a continuation? There are several implementation strategies that might work, and there are strategies such as spaghetti stacks as well as perhaps copying the whole stack, which might be more expensive if ccc is used a lot but perhaps not so much in actual practice. We’ll see just how all of this fits together.

Posted in arcueid, devnotes

One of the big problems I had with the last release of Arcueid last year was with continuations that needed to be created within C code itself. I made use of several troublesome techniques for dealing with this issue, which was the cause of some of the problems the current 0.0.x series code has. I already made use of a technique based on Simon Tatham’s C coroutines to set this up, but it looks like I’m going to have to take the technique further and make more intensive use of it within the core for the new release that I’m working on.

I have written a set of rather ugly macros that hide most of the gory details of these Arcueid Foreign Functions, so it becomes possible to write a foreign function that looks like this:

AFFDEF(doubler, func, a, b)
{
  AVAR(rval);
  AFBEGIN;

  AFCALL(AV(func), AV(a), AV(b));
  AV(rval) = INT2FIX(2 * FIX2INT(AFCRV));
  ARETURN(AV(func));
  AFEND;
}
AFFEND

The definitions for these macros are in arcueid.h in the experimental branch of the code on Github, and probably look extremely strange. The AFBEGIN/AFEND macro pair essentially turns the body of the function into a large switch statement (yes, this is an instance of Duff’s device). Another oddity is that the AFCALL macro, perversely, uses a return statement to do its job! This is because these functions are executed by means of a sort of trampoline. The AFCALL macro basically does what one would expect a Lisp function application to do: create and save a continuation, push arguments on the stack, then jump to the function, by returning to the trampoline with the callee set up for the trampoline to execute. When the called function returns, the trampoline restores the continuation that the foreign function created.

Continuations are created for C functions within the AFCALL macro by using the __LINE__ macro provided by the C preprocessor. This is used as the “offset into the function” as it were, and goes into the continuation as such. It is then used as a case label within the giant switch statement that the AFBEGIN/AFEND macros created. Thus, for the trampoline to restore such a C continuation, it has to call the function again with the offset available for the switch statement to see.

There are a lot of other weird techniques in other macros there as well, such as for AFFDEF(…). That one makes some rather creative use of C’s variadic macros in order to make an Arcueid Foreign Function definition that looks more reasonable. The techniques to do this I are based on answers I found here.

This method of defining foreign functions looks reasonably clean, I should think, and the macros do a good job of hiding the black magic that the foreign function interface has to do. There are also mechanisms for causing the the trampoline to pause execution on a non-ready file descriptor for instance, which caused me a lot of problems in my first attempt.

Posted in arcueid, devnotes

I’ve finally managed to find some time to do a little bit more work on Arcueid, and now I’m engaged in a major code reorganisation and simplification that should make things a bit cleaner, and I have a bit of a better idea for how to fix some of the most serious problems in the 0.0.x series of the interpreter: perhaps we’ll have a 0.1.0 series soon. More on that anon.

Anyhow, what this post is really about is something that has been bothering me about the current Arc interpreter for a long time. It is very easy to crash the interpreter by simply doing the following:


arc> (= x '(1 2))
arc> (scdr x x)


This sends arc3 and every version of Anarki I have tried into an infinite loop. Seems like it shouldn’t be too hard to fix, and in the experimental branch of Arcueid I have made attempts to deal with cyclic structures like that one somehow by using a hash table that keeps track of what goes where. The pretty printer algorithm I’m testing for the new version now displays something a bit more reasonable:


arc> (= x '(1 2))
arc> (scdr x x)
(1 . (...))


There are other possibilities on what to display that may be a bit more sophisticated, but I don’t think that they’re all that useful for now. For example, the above structure could be displayed as:


arc> (= x '(1 2))
arc> (scdr x x)
#0=(1 . #0#)


as some Scheme interpreters do. Maybe we’ll eventually do something similar.

It is essentially impossible to use cyclic structures in meaningful ways within Arc at the moment thanks to some rather naïve algorithms even for some fairly simple functions like for ‘iso’. The new version I have in the works does essentially a depth-first search whenever traversing a data structure that might be cyclic, by using a hash table to keep track of what has already been visited.

Posted in arcueid, devnotes