An Implementation of J
A discussion of an implementation of J must begin with
A Dictionary of APL.
I started studying it at around 1984.
It is full of insights and details on how to implement
an APL interpreter.
In particular, Table 2 provides a model in APL
of how to parse an expression.
There is executable code, and there is a table.
(It takes some study to realize that
you are looking at a table.)
To me, the more valuable part is the parse table
because it defines the syntax of the language;
the executable code is only to help understand
how the parse table worked.
One summer weekend in 1989, Arthur visited Ken at Kiln Farm and produced — on one page and in one afternoon — an interpreter fragment on the AT&T 3B1 computer. I studied this interpreter for a week for its organization and programming style; and on Sunday, August 27, 1989, at about four o’clock in the afternoon, wrote the first line of code that became J.
Years later, talking about “the one-page thing”,
Arthur said that he still wanted to write it in one page,
but using n-point font.
(The value of n increases
with each retelling of the story.)
Many C programmers object to this programming style; in particular, they object to this use of macros. The current J implementation has these exact or similar macros (and many others). The F1 F2 etc. macros define the declarations and prototypes of functions that apply to array arguments and return array results. I will say more about the DF1 and DF2 macros later.
ASSERT is one of my favorite macros. The little character “!” (not) allows conditions to be stated in a positive sense, e.g. 1>=AR(w) must be true, else signal rank error.
These macros and typedefs are used over 10,000 times
in the J interpreter.
A C programmer told me that an objection
to the programming style
is that he must look things up in order
to understand the code.
But look, if you look up F1 and understand it,
you’d understand 839 things.
I consciously designed and built the system around the parse table.
The C data and program structures were designed
so that the parse table in C corresponded
as directly as possible to the parse table in the dictionary.
I set an objective of being able to show Ken
the C source for the parser,
and have him verify that the syntax
being implemented was correct.
We never did carry out the exercise (of Ken reading the C source), but I reckon I met my objective, because eventually Ken replaced the parse table in the J dictionary with the parse table from the C source. Other effects of trying to meet the objective were entirely beneficial.
In the parse table,
the first two of the three numbers in each row
correspond to the ↓↓↓ (down arrows) in Table 2.
The last number tells the interpreter
where to put the “caret” in case of an error.
typedef A defines an array. It is pretty standard: a header followed by the ravelled values. The value is “cast” to an appropriate type.
What is not so standard is that everything
in J has type A ,
including verbs, adverbs, and conjunctions.
For such guys the value part is cast to be type V .
An example hopefully makes it clear.
The verb is the fork
From within J there are facilities (5!:x)
for looking at a terse version of this information.
Should it be desirable to implement special code
(as for example in the case ,/),
replace the function pointer
by a pointer to the new C function.
Everything else stays the same.
The DF1 and DF2 macros enforce the fact that derived verbs are invoked with an extra argument, the data structure we’ve been looking at.
This is how tacit definition was invented.
Presented at the Jsoftware Conference 2012, 2012-07-23.