I use a slightly modified Dvorak keyboard. It is like a standard Dvorak keyboard, but the parentheses have been relocated to be unshifted keys.
lambda. The M, B, and D, are all right index finger.Alas.
Rebol 1.0 was slow. I paid little attention to speed in the implementation — I was concerned with correctness. The intepreter was intended to be a reference implementation, with well-defined behavior on every edge case. My intent was to add a compiler at a later date.
Once source of slowness was the liberal use of first-class continuations in the interpreter. Rebol 1.0 used a “Cheney on the MTA” interpretation strategy, where no function ever returned a value and the stack simply got deeper and deeper. When the stack overflowed, a stack garbage collection was triggered. Since most of the stack was garbage, this was a fast operation (I used a garbage collector that used time proportional to live storage). With such an implementation, first-class continuations were trivial to implement — all continuations were first-class, it was just a question of whether you surfaced them to the user. I didn’t have an ideological belief either way, but there they were, so why not? Many control flow constructs that would otherwise require an ad hoc implementation can be easily implemented with first-class continuations.
Rebol had return statements that would return control to the caller
from within the function. 99% of the time, the caller is sitting on
the stack just above the current frame. But 1% of the time, the
user would do something weird like create a lexical closure over the
return statement and pass it downward. Like as not he
didn’t deliberately do this, but rather used some library that was
implemented in continuation-passing style. If this happened,
the return statement might have to unwind an arbitrary
amount of stack. To implement this, I captured the current
continuation at the entry of each function and bound it to the
implicit “return” variable.
Invoking return invoked the continuation and returned
control to the caller.
The advantage of doing it this way was that return
statements had the correct semantics under all circumstances. There
were no special rules governing use of return and no
code had to have special cases for unexpected returns.
A similar thing happened in the implementation of break and
continue in loops. These were implemented by capturing the
continuation at the entry of the loop and binding it to the implicit
break variable, and capturing the continuation on each
iteration and binding it to the implicit continue
variable. Because these were first-class continuations, they could
be used to restart the loop after it exited. That wasn’t a
requirement. I was perfectly happy to stipulate
that break and continue only work while a
loop is in progress, but in Rebol 1.0, they’d continue to work after
the loop finished.
Worrying about continuations captured in lexical closures may seem
weird, but it’s a real issue. It is common to introduce implicit
lexical contours in a program: even a let expression does it. You
would like to be able to use break
and continue in the body of a let expression in a
loop. Some Rebol constructs were implemented by implicitly
macroexpanding the code into a call to a helper
function. break and continue would work
across function call boundaries, so there were no limitations on
introducing helper functions within a loop.
A more traditional language has a handful of ad
hoc iteration constructs that are implemented with special
purpose code. The special purpose code knows it is a loop and can
be optimized for this. break and continue
statements have a special dependency on the enclosing loop.
Rebol 1.0 was properly tail recursive, so there was no special
implementation of loops. They were ordinary functions that happened
to call themselves. Non-standard iteration constructs could be
created by the user by simply writing code that called itself.
break and continue
just surfaced the interpreter’s continuation to the user. As a
consequence, loops in Rebol 1.0 were implemented completely in Rebol
code but had signifcant interpreter overhead.
Rebol 2.0 and later are not properly tail recusive. As a consequence,
special looping constructs are required to be written in C to support
iteration. Common iteration constucts such as for
and while are provided and do not have interpreter
overhead, but if you want a non-standard iteration construct,
there is no way to achieve it. You have to re-write your code to
use one of the built-in iteration constructs or go without and risk
blowing the stack.
My intent was to eventually write a compiler for Rebol. I wrote a prototype called Sherman that compiled to MIT-Scheme and was supported by the MIT-Scheme runtime library. Loops compiled with Sherman ran quickly as expected.
It’s been a year since I wrote a review of GitHub Copilot. A reader asked me to write an update. He wanted to know what I thought of the apparent negative effects of Copilot on the quality of code in several codebases.
GitHub Copilot acts as an autocomplete tool. Suggested completions appear in the editor as you enter code. You can accept the suggestion or ignore it. But your frame of mind informs how you decide whether to accept or ignore a suggestion. Here are a few of the ways you can interact with GitHub Copilot.
The StackOverflow mode. On the StackOveflow web site, you’ll find questions about coding and answers that often contain sample code. As an engineer, you craft the solution to your specific problem by adapting some of the sample code to your specific needs. The problem with StackOverflow is that the quality of the answers varies widely. Some answers come with some well written and well tested sample code. Other times you’ll find that someone posts a code snippet that they didn’t even attempt to run. Sometimes the code in the answer is just plain wrong. You have to draw on your engineering skills to carefully evaluate and adapt the code you find on StackOverflow.
In StackOverflow mode, you pretend that GitHub Copilot is a StackOverflow search engine. You prompt Copilot to generate snippets of code. You evaluate the generated code as though it were taken from a StackOverflow answer. The code may be fairly well written and work as is, it might be completely wrong, or it might be somewhere inbetween. You have to be be prepared to evaluate the code critically. You may need to tweak the code to make it work in your specific context. There may be subtle bugs you need to watch for.
The autocomplete mode. When using Copilot in this mode, you treat Copilot as an autocomplete tool. As you type your program, Copilot will attempt to complete the snippet you are typing. The best way to interact with Copilot in this mode is to ignore most of the suggested completions and only accept the ones that are obviously right. Often Copilot suggests exactly what you were going to type anyway. Accept those suggestions. You don’t want to spend the time and intellectual energy evaluating and adapting suggested code in this mode. You just to want to get your code written quickly. Accept the code that saves you typing and reject everything else.
Code generation mode. Copilot is pretty good at discovering repeated patterns in your code. In code generation mode, you craft some prompt code attempting to induce Copilot to generate templated output. Typically writing out one or two examples of a repeating pattern of code is sufficient for Copilot to get the gist of what you are doing and have it automatically generate the next few repetitions.
Each of these modes of interacting with GitHub Copilot requires different amounts of attention and focus, and applying your attention and focus to different areas. To get the most out of Copilot, you need to be able to switch your attention and focus between the interaction modes. The better you can do this, the more you will get out of Copilot. It takes practice.
Copilot produces mediocre code. It’s not imaginative, it doesn’t have the big picture. It writes the same code that J. Random Neckbeard would write. Mr. Neckbeard will hack out servicable solutions, but won’t craft elegant ones. If you let Copilot take over writing large sections of code, you’ll end up with a pile of bad code. It may run, but it will be hard to read, understand, and maintain. You have to assert yourself and not let Copilot take control.
When you use Copilot, you have to be the boss. It’s too easy to be lazy and accept suggestons that Copilot makes because although they aren’t great, and they aren’t what you would have written, they are adequate. Do this enough and the resulting code won’t be great, but instead barely adequate. Resist the temptation to be lazy and reject suggestions that aren’t what you want.
I’ve been using Copilot for over a year now. I’ve used it in anger on a medium sized go project. It turns out that if you point Copilot at a text file or html file, it will generate prose as well as source code. As you write, Copilot will try to finish your sentences. If you let it do this too much, you’ll end up sounding like a section of a Wikipedia article. It is best to already have some text in mind and let Copilot try to guess what it is. Reject the suggestion when it guesses wrong. This way you can use Copilot to save you typing, but you sound like yourself. Copilot does however, occasionally suggest continuations that raise points you hadn’t addressed. The suggestion may be a bit of a non-sequitur at the point where it is made, but I’ve found that Copilot can remind me of things I’ve forgotten to mention.
Copilot is not a pair programmer. It is a complex program generation model with a front-end that appears to have a deceptively shallow learning curve. There are several different ways to effectively use Copilot, but they all present themselves as autocomplete. It takes time and practive to learn the different effective ways to use Copilot and to switch between them as you program.
If you are J. Random Neckbeard, Copilot will help you become much more prolific without a lot of effort. But if your standards are higher, you’ll have to work harder to get the most out of Copilot, and you’ll find yourself rejecting it more. Be prepared to put a few months of effort into practicing the different ways to use Copilot. Like any complex tool, it takes time to get good at using it.
Can you trust Copilot? Can you trust an engineer who uses Copilot? Ask yourself, do you trust StackOverflow? Do you trust an engineer who uses StackOverflow? Do you trust your engineers? Copilot may be the ultimate source of buggy code, but the engineer is responsible.
Many codebases have reported a decrease in quality since Copilot has come on the scene. I think it is reasonable to discourage its use in these codebases. But I don’t think Copilot makes programmers worse. It makes lazy programmers more prolific, which is probably not what you want. If you are a good programmer, Copilot can be a useful tool in your toolbox. If you are careful to not let Copilot write too much of your code, you can save time without your code suffering.
This experiment with writing an MIT-Scheme S-code interpreter in C# was successful in these ways:
It was a failure in these ways:
I think the next Lisp system I will try should be based around a simple, portable JIT compiler.
C# is not tail recursive. It could be. The IL that it compiles to supports tail recursion, but the C# compiler doesn’t generate the tail call instruction. It would be a simple thing to add: when the compiler emits a call instruction, it could check if the next instruction is a return, and if so, emit a tail call instruction. This could be controlled by a compiler flag so only us weirdos who want this feature would enable it.
But until the C# compiler adds this feature, we have to resort to other methods. I chose to use a trampoline at each call site. This is a small segment of code that awaits the result of the function call. If the callee wants to tail call, it returns the tail call target to the caller, which performs the call on the callee’s behalf. This requires a modification to the calling conventions.
EvalStep is the virtual method that all S-code objects
implement to perform an evaluation. Its signature is this:
abstract class Control : SchemeObject
{
public abstract TailRecursionFlag EvalStep (out object answer,
ref Control expression,
ref Environment environment);
}
The result of the evaluation is returned in the answer
parameter. This is an out parameter, so the answer is
allocated in the caller and a pointer to it is passed to the callee.
The callee returns the answer by modifying it in the callers
stack frame.
The expression and environment parameters
are the expected parameters for a call to Eval. They,
too, are allocated in the caller’s frame and references to them are
passed to the callee. The callee is allowed to modify the caller’s
values of these variables.
The returned value is a TailRecursionFlag. This is
either 1, indicating that a value has been returned in the answer,
or 0, indicating that the caller should perform
another EvalStep. To return a value, the callee
modifies the answer. To perform a tail call, the callee
modifies the expression and environment
references and returns 0.
Any caller must call EvalStep as follows: The caller
allocates an answer variable to receive the answer of
the call. It also allocates an expression,
and environment variable to pass to the callee. It
then calls EvalStep in a loop until the callee returns
a TailRecursionFlag of 1, indicating that
the answer has been set to the return value.
In the EvalStep for an S-code Conditional
we see an example of the calling convention:
object ev;
Control unev = predicate;
Environment env = environment;
while (unev.EvalStep (out ev, ref unev, ref env) == TailRecursionFlag.TailCall) { };
We are making a recursive call to evaluate
the predicate. We set up ev to receive
the result of the evaluation. We set up unev
and env to hold the expression and environment to pass
to EvalStep. unev.EvalStep does the eval
dispatch via virtual function dispatch.
If the predicate returns a TailRecursionFlag
of ReturnValue, the loop will exit. The predicate is
assumed to have put the return value in the ev
variable.
If the predicate wants to tail call, it will modify the values
of unev and env to the new expression and
new environment, and return a TailRecursionFlag
of TailCall. The loop will iterate, using the new
value of unev and env to again dispatch a
call to EvalStep.
When the while loop exits, the ev
variable will contain the return value of the predicate. Control
may be returned to the while loop several times before
the loop exits. This is the trampoline in action.
Conditional expressions don’t return a value. They either tail call
the consequent or the alternative. The EvalStep for a
conditional ends like this:
answer = null; expression = (ev is bool evb && evb == false) ? alternative : return TailRecursionFlag.TailCall; }
The answer variable in the caller is set to null.
out parameters must always be assigned to before the
function exits, so this just keeps the compiler happy. If the
return value of calling EvalStep on the predicate is
the boolean false, we set the expression in the caller
to the alternative, otherwise the consequent. This is the target of
our tail call to EvalStep. For the scode for a
conditional, we leave the environment alone — the
tail call uses the same environment unchanged. We finally
return TailRecursionFlag.TailCall so that the caller’s
trampoline makes another iteration around its while.
It will call EvalStep on the alternative or consequent
that we stuffed in the caller’s expression.
This little song and dance is performed at every recursive call
to EvalStep making EvalStep behave as a
tail-recursive function. This calling convention is about half the
speed of a normal C# method call. It is the cost of using a
trampoline for tail recursion.
There is one more obscure reason that the control might return to
us when evaluating the predicate. If some function further down the
call chain invokes call-with-current-continuation, we
need to copy the stack. The callee indicates this by returning a
magic return value of Special.UnwindStack. The callee
sets the caller’s environment to
an UnwinderState that will accumulate the stack frames
as we unwind the stack. So our calling convention says we need to
check the return value of EvalStep, and if it
is Special.UnwindStack, we allocate
a ConditionalFrame on the heap that will contain the
state of the current stack frame. We AddFrame to
the UnwinderState. We propagate this up the stack by
putting it in the caller’s environment, setting the
caller’s value of answer
to Special.UnwindStack and
returning TailRecursionFlag.ReturnValue to stop the
caller’s trampoline loop.
The full code of EvalStep for an
S-code if expression is this:
public override TailRecursionFlag EvalStep (out object answer,
ref Control expression,
ref Environment environment)
{
object ev;
Control unev = predicate;
Environment env = environment;
// Tail recursion trampoline.
while (unev.EvalStep (out ev, ref unev, ref env) == TailRecursionFlag.TailCall) { };
// Support for first class continuations.
if (ev == Special.UnwindStack)
{
((UnwinderState) env).AddFrame (new ConditionalFrame (this, environment));
environment = env;
answer = Special.UnwindStack;
return TailRecursionFlag.ReturnValue;
}
// Tail call EvalStep on the consequent or alternative.
answer = null;
expression = (ev is bool evb && evb == false) ? alternative : consequent;
return TailRecursionFlag.TailCall;
}
First class continuations allow you unload and reload the pending
call chain. We see that at each call site, we must check the return
value and, if it is Special.UnwindStack, we create a
new Frame on the heap and add it to the unwinder state
befor we propagate the Special.UnwindStack up the call
chain.
At the very top of the call chain, we have the outermost call
to EvalStep. If the Special.UnwindStack
value is returned to this call, the stack has been unwound and the
UnwinderState is sitting in the environment variable.
We need to rewind the stack and put the stack frames back on the
stack. We create a RewindState from
the UnwinderState. Each time we PopFrame
from the RewindState, we get a deeper frame. We reload
the stack by getting the outermost frame from
the RewindState and calling EvalStep on
it. The EvalStep for a Frame sets up the
trampoline loop, calls PopFrame to get the next frame,
and calls EvalStep on it. When we run out of stack
frames to reload, the stack is reloaded and we return control the
innermost frame so it can continue where it left off. This is the
rewind loop.
The EvalStep for a Frame, after making
the recursive call to EvalStep on the next frame,
continues with code that is a duplicate of the code in the original
frame before the cotinuation was captured. A specific example will
make this clear. If an if expression is on the stack
when it is uwound, a ConditionalFrame is created.
A ConditionalFrame is a subclass
of SubproblemFrame which has this EvalStep
method:
public override TailRecursionFlag EvalStep (out object answer,
ref Control expression,
ref Environment environment)
{
object temp;
Control expr = ((RewindState) environment).PopFrame ();
Environment env = environment;
while (expr.EvalStep (out temp, ref expr, ref env) == TailRecursionFlag.TailCall) { };
if (temp == Special.UnwindStack)
{
((UnwinderState) env).AppendContinuationFrames (continuation);
environment = env;
answer = Special.UnwindStack;
return TailRecursionFlag.ReturnValue;
}
expression = this.expression;
environment = this.environment;
return Continue (out answer, ref expression, ref environment, temp);
}
public abstract TailRecursionFlag Continue (out object answer,
ref Control expression,
ref Environment environment,
object value);
That is, the EvalStep of
the SubproblemFrame establishes a trampoline, pops the
next frame from the RewindState, and invokes
its EvalStep method. When an answer is returned,
the SubproblemFrame calls its Continue
method.
The Continue method is a virtual method that is
implemented by each subclass of SubproblemFrame. It
finishes the work of the frame. In the case of
a ConditionalFrame, the Continue method is
this:
public override TailRecursionFlag Continue (out object answer,
ref Control expression,
ref Environment environment,
object value)
{
answer = null;
expression = value is bool bvalue && bvalue == false
? SCode.EnsureSCode (this.expression.Alternative)
: SCode.EnsureSCode (this.expression.Consequent);
return TailRecursionFlag.TailCall;
}
compare this to the code in the original Conditional:
// Tail call EvalStep on the consequent or alternative.
answer = null;
expression = (ev is bool evb && evb == false) ? alternative : consequent;
return TailRecursionFlag.TailCall;
There are only superficial differences: the Continue
method gets the value returned by the predicate in an argument
rather than in a local variable. It type checks the alternative and
consequent components of the if expression by
calling SCode.EnsureSCode. Otherwise, the code does
the same thing.
It is not possible to actually rewind the stack with the original set of pending methods. What we do instead is rewind the stack with methods that do the same thing as the original pending methods. It is close enough. The same values will be computed.
There is one place you can see the difference. If you look at the
stack trace in the debugger before you capture a continuation, you
will see the pending recursive calls to the
S-code EvalStep methods. If you look at the stack
trace in the debugger after you capture a continuation, you will
instead see pending calls to the EvalStep methods of a
set of frames. The pending frames are in the same order and have
names similar to the original pending methods. They compute the
same values, too. But the debugger can notice that these are not
the originals.
Calls to (null? x) usually appear as the predicate to
a conditional. We can specialize the conditional. Instead of
[if [primitive-null?-argument0] [quote 69] [quote 420]]
We create a new S-code construct, if-null?-argument0, and
construct the conditional as
[if-null?-argument0 [quote 69] [quote 420]]
We avoid a recursive call and generating a ’T or ’NIL value and testing it, we just test for null and jump to the appropriate branch, just like the compiled code would have done.
We can further specialize the conditional based on the types of the
consequent and alternative. In this case, they are both quoted
values, so we can specialize the conditional to
[if-null?-argument0-q-q 69 420]. (Where the name of
the S-code type is derived from the type of the consequent and
alternative.)
if-null?-argument0-q-q is an esoteric S-code type that
codes a test of the first argument for null, and if it is null,
returns the first quoted value, otherwise the second quoted value.
This S-code type runs just as fast as compiled code. Indeed the
machine instructions for evaluating this S-code are the same as what
the compiler would have generated for the original Lisp form.
Why not continue in this vein specializing up the S-code tree? Wouldn’t our interpreter be as fast as compiled code? Well it would, but there is a problem. Every time we add a new S-code type, we add new opportunities for specialization to the containing nodes. The number of ways to specialize a node is the product of the number of ways to specialize its children, so the number of ways to specialize the S-code tree grows exponentially with the number of S-code types. The few specializations I’ve just mentioned end up producing hundreds of specialized S-code types. Many of these specialized S-code types are quite esoteric and apply at most to only one or two nodes in the S-code tree for the entire program and runtime system. Performing another round of inlining and specialization would produce thousands of specialized S-code types — too many to author by hand, and most of which would be too esoteric to ever be actually used.
The solution, of course, is to automate the specialization process. We only generate a specialized S-code type when it is actually used by a program. The number of specialized S-code types will be limited by the number of ways programs are written, which is linear in the size of the program.
But specializing the code when we first encounter it is just JIT compiling the code. We’ve just reinvented the compiler. We might as well skip the multi-level specialization of the S-code tree and write a simple JIT compiler.
Reconsider our model of a Lisp program as a “black box” that issues a series primitive function calls. We can eliminate some of the primitive function calls by implementing them directly within our “black box”. We inline some primitives.
Take null? as an example. Instead of
constructing (null? arg) as
[primitive-funcall1 [quote [primitive null?]] [argument 0]]
we add a new S-code construct, primitive-null?, and
construct (null? arg) as
[primitive-null? [argument 0]]
We don't have to evaluate the function. We don't even have to jump
to the entry point of the null? primitive. After we
evaluate argument 0, we just test for null in the interpreter and
return T or NIL as appropriate.
There are maybe 20 or so primitives that are used frequently enough to be worth inlining in this way. Each primitive you inline like this adds bloat to the interpreter.
The leaves of a tree of S-code are the atomic expressions, whereas the internal nodes of the tree are compound expressions. We can eliminate the leaves by inlining them into their parent nodes. For example if a leaf node is a lexical variable reference, we inline this into the parent node. We unroll the evaluation of the leaf node thus saving a recursive call to the interpreter and an evaluation dispatch.
Consider our previous example which we consructed as
[primitive-null? [argument 0]]
We further specialize primitive-null? based on its
argument type into primitive-null?-argument
or primitive-null?-lexical. Now our S-code
becomes:
[primitive-null?-argument 0]
The leaf node [argument 0] is absorbed
into the parent node [primitive-null? ...] making a
new leaf node [primitive-null?-argument]. The
evaluator for this S-code node simply tests if argument 0
is null and returns T or NIL as
appropriate.
Compare this to the original S-code:
[funcall [global 'null?] [argument 0]]
This required two recursive calls to the interpreter, a global
lookup, and a primitive function call on top of the null test.
We’ve eliminated all of those. There’s not much left to
do. Testing null? in the interpreter is almost as
fast as testing null? in compiled code.
The number of S-code types needed to perform this inlining is the number of kinds of leaf nodes raised to the power of the number of leaves in the parent node. A call to a one-argument primitive would need specializations for the cases where the argument is a quoted value, an argument, a lexical variable or a global variable — four specializations. Calls to a two-argument primitive turn into one of sixteen specializations — the product of four for each argument. A call to a three-argument primitive would turn into one of sixty-four specializations.
We can inline all the non-compound argument evaluations, both to primitive functions and to user-defined functions. In our S-code tree, we have removed all the leaf nodes and absorbed them into their parent nodes (which have now become new leaves). The interpreter is now quite a bit faster, although still not as fast as compiled code.