CLC-INTERCAL Reference

... How to write a compiler for CLC-INTERCAL

CLC-INTERCAL 1.-94 no longer includes a parser. Instead, it contains a parser generator. The source language for the parser generator is a includes the CREATE statement and the ability to assign to special registers (to control the runtime operating mode). This document describes the syntax of a CREATE statement, and shows some examples.

Syntax

The CREATE and DESTROY statement have the form: 

    DO CREATE grammar class template AS code
    DO DESTROY grammar class template

The grammar is one of the two crawling horrors, and can be omitted. When compiling a compiler (with iacc), _1 represents the compiler compiler's grammar, and _2 represents the compiler being built; if the grammar is omitted, it defaults to _2. When not compiling a compiler, _1 is the current compiler and _2 is undefined. When using the CREATE or DESTROY statements with sick, the grammar must be omitted, and it defaults to _1.

The class specifies a syntactic class (some other languages might call it a nonterminal). Usually, this takes the form of a what ("?") followed by some alphanumerics, although anything which evaluates to a number will do. Please note that in CLC-INTERCAL the what does not introduce a unary logical operator as in C-INTERCAL, and it always produces a named constant (of sorts).

The template is composed of a sequence of terminals and nonterminals which vaguely resemble the syntax you are trying to define. Nonterminals are specified as a special type of constant, usually introduced by the "what" discussed before. Terminals are specified as "array slices", that is sequences of numbers enclosed in tails or hybrids and representing a 16-bit array containing ASCII character codes. Abbreviations are available for terminals consisting of just alhpanumerics, where the characters, rather than their codes, are included between the tails.

The code specifies the semantics of this production. There are many elements which can be used here, to produce chunks of code, copy the code produced by a symbol called from the template, etc. We defer discussion of this until a later section.

For example, consider the following production from sick.iacc: 

    DO CREATE _2 ?STMT_LABEL ,#40, ?CONSTANT ,#41, AS ?CONSTANT #1
This create a production for class ?STMT_LABEL; this matches an open parenthesis (#40), a numeric constant (which is parsed by ?CONSTANT), and the close parenthesis (#41). In other words, this production matches a normal statement label.

Some productions parse list of elements, and the code generated may contain the number of elements. In general, this is not the same as the number of symbols parsed. Consider the following productions to parse the list of register names used, for example, in a STASH statement: 

    DO CREATE _2 ?NAMES ?RNAME AS ?RNAME #1
    DO CREATE _2 ?NAMES ?RNAME ,#43, ?NAMES AS ?RNAME #1 + ?NAMES #1
To parse a list of two registers, the second production matches an ?RNAME (which presumably parses a register name), an intersection symbol (#43), and then matches itself recursively - in this recursive call, it will use the first production to match the second register. At the level of this production, we matched three symbols, ?RNAME, #43 and ?NAMES. So how do we obtain a count of 2 (which is required so that the STASH knows how many registers to stash?). To solve this problem, each element in the production can have a numeric "count" associated with it, using the syntax "=number". Moreover, a nonterminal can have the special count "=*" to indicate that the count produced by that nonterminal should be used. If a symbol does not have a count, it is assumed to be "=0". The total count of a production is the sum of all its counts. We rewrite the above as: 
    DO CREATE _2 ?NAMES ?RNAME=1 AS ?RNAME #1
    DO CREATE _2 ?NAMES ?RNAME=1 ,#43, ?NAMES=* AS ?RNAME #1 + ?NAMES #1
Now, consider again parsing .1+.2 - we need the second production, which matches .1 using ?RNAME and .2 using ?NAMES; the recursive call uses the first production to match .2 using ?RNAME. What is the count? the inner call has count 1, because there is just one count, =1. The outer call has count 2, the =1 from ?RNAME, and the =* from ?NAMES - which uses the inner count of 1. If you work out this example with more than two registers, you see how it works.

The DESTROY statement works like a CREATE in reverse. Only the first part, before the AS, is used. Suppose we no longer need the two above production, we can remove them with: 

    DO DESTROY _2 ?NAMES ?RNAME=1
    DO DESTROY _2 ?NAMES ?RNAME=1 ,#43, ?NAMES=*

While CREATE (and maybe DESTROY) are the major components of a compiler, it is often necessary to assign values to special registers and to set object flags. Special registers control the way the runtime handles the generated code; the compiler uses normal assignments to give these the appropriate values, and these values will be saved together with the code in the object, so that they can influence the runtime when the object is executed. The next section discusses special registers.

By contrast, flags are a property of the compiler itself, and are used by the command-line compiler tool (sick) and the calculator to decide what to do with an object. Flags are set by using assignments, but these assignments are executed at compile time. At the time of writing, the only flag is ?TYPE, which describes the compiler or other extension we are building. The possible values of this flag are:
?TYPEMeaning
?ASSEMBLERCompiler used to build assembler programs
?BASEAn object which just changes the arithmetic base
?COMPILERCompiler used to compile normal programs
?EXTENSIONCompiler extension, e.g. new syntax
?IACCCompiler used to compile other compilers
?OPTIMISERObject defining code optimisations
?OPTIONCompiler option, e.g. change the meaning of existing syntax
?POSTPRESpecial object loaded after all other objects and before the source
At present, the system does not distinguish between ?EXTENSION and ?OPTION; the command-line compiler tool accepts then indifferently, and the calculator lists all these object in the Options menu.

For example, towards the start of sick.iacc one can see: 

    DO ?TYPE <- ?COMPILER
On the other hand, the extensions we will develop as examples in this section will have: 
    DO ?TYPE <- ?EXTENSION

One further statement is of interest: MAKE NEW OPCODE. This is described in the section about writing an extension for sick.

Predefined symbols

Some nonterminals are predefined by CLC-INTERCAL. This means that you don't use CREATE statement to make them, and you can use them in your compiler or extension:

SymbolMeaning
?ANYTHINGAny single character
?BLACKSPACEAny non-space character
?CONSTANTAny numeric constant between 0 and 65535
?JUNKSee below
?SPACEAny space character
?SYMBOLAny sequence of alphanumerics or udnerscores

Although these symbols could be defined using CREATEs, it would be rather cumbersome to do so.

The ?JUNK symbol is used to parse comments. It matches the longest text which does not look like the start of a statement. Special register %JS, described in the next section, defines what constitutes the start of a statement. Normally, the value of %JS is ?END_JUNK, and the following productions are defined by the compiler: 

    DO CREATE _2 ?END_JUNK ?STMT_LABEL AS ,,
    DO CREATE _2 ?END_JUNK ,DO, AS ,,
    DO CREATE _2 ?END_JUNK ,PLEASE, AS ,,
In other words, the start of a statement is either a label (as defined in symbol ?STMT_LABEL), or one of the terminals "DO" or "PLEASE". When parsing a comment, the ?JUNK symbol will therefore find the first label, DO or PLEASE and matches the text in between.

Special Registers

A number of special register control how the compiler or the runtime operates.

Code generation

The right-hand side of a CREATE statement (the bit after the AS) generates the code to be executed when the template matches a bit of the program.

The code consists of elements, separated by the intersection symbol (+); each element can be one of the following:

As examples, consider the three CREATE statements listed in the previous section: 

    DO CREATE _2 ?STMT_LABEL ,#40, ?CONSTANT ,#41, AS ?CONSTANT #1
    DO CREATE _2 ?NAMES ?RNAME=1 AS ?RNAME #1
    DO CREATE _2 ?NAMES ?RNAME=1 ,#43, ?NAMES=* AS ?RNAME #1 + ?NAMES #1
The first statement generates code which evaluates to the constant provided inside the parentheses. This is obviously going to be used in a context where this is interpreted as a label number. The second statement just copies the code generated by ?RNAME; the third statement just produces the code generated by ?RNAME followed by the code generated by the recursive call to itself.

Now consider: 

    DO CREATE _2 ?VERB ,STASH, ?NAMES AS STA + !NAMES #1 + ?NAMES #1
STA is a bytecode opcode (which happens to correspond to the STASH operation). It takes an expression, representing a count, and then that number of registers. The generated code reflects this: !NAMES #1 is the number of registers, and ?NAMES #1 is the code generated by all the registers, one after the other.

If one wants to extend sick to allow direct access to the base, for example using the syntax SETBASE expression to change the base and GETBASE expression to get the base, one could say: 

    DO CREATE ?VERB ,SETBASE, ?EXPRESSION AS STO + ?EXPRESSION #1 + %BA
    DO CREATE ?VERB ,GETBASE, ?EXPRESSION AS STO + %BA + ?EXPRESSION #1
The STO opcode, followed by two expressions, assigns the first expression to the second. In this case, the code generated by SETBASE expression would be identical to the code generated by %BA <- expression, and the code generated by GETBASE expression would be identical to the code generated by expression <- %BA.

Bytecode

The bytecode represents an intermediate form produced by the compilers. This consists of opcodes which are executed in sequence. At present, a bytecode interpreter executes the program, however there are plans to allow direct generation of C or Perl source from the bytecode.

Each byte in the bytecode can be part of a statement, an expression or a register. In addition, a subset of expressions can be assigned to: these are called assignable expressions. For example, a constant is an assignable expression. When assigned to, it changes the value of the constant. This is necessary to implement overloading and is also a great obfuscation mechanism.

Constants

Constants can be specified in three ways:

Registers

Registers can be any number of register prefixes, followed by a type and a constant. There are limitations in the useful combination of prefixes.

The register types are:

The prefixes which can applied to registers are:

Expressions

Assignable expressions are sequences of bytecode which can used as the target of an assignment. Of course, all registers are assignable; all constants are also assignable, which makes then really variables. Instead of describing the assignable expressions separately, we describe all expressions and mention which ones are assignable. Assigning to an expression means assigning appropriate values to its subexpressions such that the expression, if evaluated, would result in the value being assigned. This is not always possible, so it can generate runtime errors.

In addition to registers and constants, the following are valid expressions:

Statements

The following opcodes are valid statements:

Writing an extension for sick

Writing an extension for the sick compiler (or any of the other compilers provided) is simply a matter of putting together the material in this chapter in a way which is consistent with the rest of the compiler. For this reason, this section provides a description of some of the compiler internals. Please note that while the compiler internals could change in future versions of CLC-INTERCAL, the parts described here are unlikely to change.

The most important grammar symbols defined by sick, ick and 1972 are (see below for further explanations):

When extending the expression syntax, one commonly adds a unary or a binary operator. This can be easily done by adding a production to symbol ?UNARY or ?BINARY, respectively. In general, the operation to add is not already present in CLC-INTERCAL (otherwise there would be already syntax for it), so one would use the undocumented expression opcode (UNE) and an additional Perl module to implement it.

The undocumented expression opcode takes two strings, a number, and then a list of expressions (the number determines how many). The first string is taken to be the name of a Perl module, with Language::INTERCAL:: automatically prepended to it, the second string is taken to be the name of a function to be called within that module; the expressions are passed as arguments to the function using the form: 

    $result = Language::INTERCAL::module->function(expr, expr...)
The module is automatically loaded if necessary.

Suppose, for example, we want to add an überwimp extension, which adds two new operators: a unary logical negation and a binary logical AND operator. We use the symbols "n" and "a" for these operations. We start by defining the Perl module to implement them: 

    package Language::INTERCAL::Ueberwimp;

    use Language::INTERCAL::Splats ':SP';
    use Language::INTERCAL::Numbers;

    sub negate {
        @_ == 2 or faint(SP_INVALID, 'Wrong number of arguments', 'negate');
	my ($class, $arg) = @_;
	$arg = $arg->number;
	return Language::INTERCAL::Numbers::Spot->new(! $arg);
    }

    sub and {
        @_ == 3 or faint(SP_INVALID, 'Wrong number of arguments', 'and');
	# remember we get the arguments in reverse order (OK, so it does
	# not matter here because this operation is commutative, but in
	# general we should remember this).
	my ($class, $second, $first) = @_;
	$first = $first->number;
	$second = $second->number;
	return Language::INTERCAL::Numbers::Spot->new($first && $second);
    }

    1;
This uses the runtime internals to get a Perl number from the arguments (this would automatically splat if the argument happens to be something other than a number), and create a new Spot value. Now, in order to use this module, we need to add the syntax and code for it: 
    DO ?TYPE <- ?EXTENSION
    DO CREATE ?UNARY ,n, AS
	UNE +
	MUL + #9 + #85 + #101 + #98 + #101 + #114 + #119 + #105 + #109 + #112 +
	MUL + #6 + #110 + #101 + #103 + #97 + #116 + #101 +
	#1
    DO CREATE ?BINARY ,a, AS
	UNE +
	MUL + #9 + #85 + #101 + #98 + #101 + #114 + #119 + #105 + #109 + #112 +
	MUL + #3 + #97 + #110 + #100 +
	#2
    PLEASE GIVE UP
This example shows one way of creating strings in bytecode: the MUL opcode, followed by the number of characters in the string, followed by the character codes. Note that the module and function name are provided in ASCII, but if the function requires any string arguments these are provided in Baudot for compatibility with alphanumeric I/O. In any case, we pass the string "Ueberwimp" (the Perl module name) and either "negate" or "and" as the first two arguments to UNE; the third argument is the number of expressions to follow, which will be #1 for "negate" and #2 for "and". The expressions will be automatically provided by the rest of the compiler.

To use this extension, save the above INTERCAL code to a file, say ueberwimp.iacc, and compile it with: 

    sick ueberwimp.iacc
Then save the above Perl code in a file Ueberwimp.pm somewhere your Perl interpreter will be able to find it. To use this extension, to compile yourprogram.i you just say: 
    sick -psick -pueberwimp yourprogram.i
For example, if the program contains "DO .1 <- .n2" or "DO .1 <- .2 a .3" this will automatically load your Perl module and call its negate or and method, as required.

Special note - the rest of this section contains information which may change in future. Implementing new statements is not fully supported yet.

The procedure to add a new statement is very similar to adding operators, however you use the Undocumented Statement (UNS) opcode which is almost identical to the Undocumented Expression except it does not return a value. It does, however, take the same arguments and expects you to write a corresponding Perl module.

Since statements can be referred to by gerund or template, each form of the statement must have a unique identifier; statements defined by CLC-INTERCAL use the bytecode opcode number for that, but if you use UNS you must specify your own gerund - just pick a number between #256 and #65535 which has not been used by other extensions.

Once all this is in place, you need to define your syntax by adding rules for the ?VERB symbol; you also create as many rules for the ?TEMPLATE symbol as there are different forms for your statement; finally you add one rule for the ?GERUND symbol returning all possible gerund identifiers, and setting the count value to the appropriate value.

We understand it is about time to provide an example. Let's say you want to do some form of code profiling, and you start by adding two statements which signal the start and the end of a profiling block. You want to be able to say: 

    DO PROFILE ON #1234
    ....
    DO PROFILE OFF #1234
And see on your standard error something like: 
    1174382975.857 ON 1234
    ....
    1174382975.868 OFF 1234
(The 1174382975 is just a Unix timestamp, which happens to mean Tue Mar 20 09:29:35 2007 - guess when this was written?). The assumption is that you'll also write a program to analyse this output and tell you where your program is being slow. As before, you start with a Perl module: 
    package Language::INTERCAL::Profile;

    use Language::INTERCAL::Splats ':SP';
    use Time::HiRes 'gettimeofday';

    sub on {
        @_ == 2 or faint(SP_INVALID, 'Wrong number of arguments', 'Profile ON');
	my ($class, $arg) = @_;
	$arg = $arg->number;
	my ($sec, $msec) = gettimeofday;
	fprintf STDERR "%d.%03d ON %d\n", $sec, $msec / 1000, $arg;
    }

    sub off {
        @_ == 2 or faint(SP_INVALID, 'Wrong number of arguments', 'Profile OFF');
	my ($class, $arg) = @_;
	$arg = $arg->number;
	my ($sec, $msec) = gettimeofday;
	fprintf STDERR "%d.%03d OFF %d\n", $sec, $msec / 1000, $arg;
    }

    1;
Next, you write a compiler extension to add the required syntax and generate the code: 
    DO ?TYPE <- ?EXTENSION
    DO MAKE NEW OPCODE #666 ,E, AS
	UNS +
	MUL + #7 + #80 + #114 + #111 + #102 + #105 + #108 + #101 +
	MUL + #2 + #111 + #110 +
	#1
    DO MAKE NEW OPCODE #666 ,E, AS
	UNS +
	MUL + #7 + #80 + #114 + #111 + #102 + #105 + #108 + #101 +
	MUL + #3 + #111 + #102 + #102 +
	#1
    DO CREATE ?VERB ,PROFILE, ,ON, ?EXPRESSION AS
	USG + #666 + ?EXPRESSION #1
    DO CREATE ?VERB ,PROFILE, ,OFF, ?EXPRESSION AS
	USG + #667 + ?EXPRESSION #1
    DO CREATE ?TEMPLATE ,PROFILE, ,ON, ,EXPRESSION, AS #666
    DO CREATE ?TEMPLATE ,PROFILE, ,OFF, ,EXPRESSION, AS #667
    DO CREATE ?GERUND ,PROFILING,=2 AS #666 + #667
    PLEASE GIVE UP
First we need to register new operation codes ("gerund codes") with the runtime. This is done by the two MAKE NEW OPCODE statements. The opcodes, #666 and #667, are very similar: they both take one expression as arguments (that's the ,E,), and they are implemented by a call to UNS with the appropriate parameters ("Profile" and the "on" or "off", respectively). After that, it is just a matter of using the new opcodes in the right place: the first two CREATE statements use USG ("use gerund") followed by the appropriate opcode and its arguments.

The two CREATE ?TEMPLATE statements define the two statement templates corresponding to the two previous definitions. They match strings "PROFILE ON" and "PROFILE OFF" and return the corresponding gerund (as a number, without using the USG opcode). Having defined these two templates, you are now allowed to confuse your profiling system with: 

   PLEASE SWAP PROFILE ON AND PROFILE OFF
Note that the two new gerunds were defined as taking one expression as argument: therefore they can be swapped with any other statement which takes just one expression: 
   PLEASE SWAP PROFILE ON AND RESUME EXPRESSION
   PLEASE CONVERT PROFILE OFF TO FORGET EXPRESSION

The last CREATE statement defined the gerund PROFILING, so you can control whether this output is produced by using DO ABSTAIN FROM PROFILING and DO REINSTATE PROFILING. Note that you return both gerunds here, and also set the count as appropriate (with the =2 after ,PROFILING,) so that the rest of the compiler knows how many gerunds you are trying to add.

Examples

The code for computed-labels.iacc is: 

    DO ?TYPE <- ?EXTENSION
    DO CREATE _2 ?STMT_LABEL ,#40, ?EXPRESSION ,#41, AS ?EXPRESSION #1
    DO GIVE UP
The ?TYPE flag is set to extension because this program extends the syntax of an existing compiler. The second statement extends the grammar; we have already seen that a standard label is parsed by stmbol ?STMT_LABEL and conststs of an open parenthesis, a constant, and a close parenthesis. The CREATE statement in this extension adds a second production for ?STMT_LABEL, allowing any expression in addition to the constant. As a result, a non-computed label can now be written in two ways, for example (1) and (#1).

The distribution also includes six very similar programs, with names 2.iacc, 3.iacc etc. We show 5.iacc: 

    DO ?TYPE <- ?BASE
    PLEASE %BA <- #5
    DO GIVE UP
The ?TYPE flag is set to base here, because this is what thie program does: it changes the arithmetic base. The only thing it needs to do is to assign #5 to special register %BA.

As a final example, next.iacc allows to extend the sick compiler with a NEXT statement. 

    DO ?TYPE <- ?EXTENSION
    DO CREATE _2 ?VERB ?LABEL ,NEXT, ?Q_NEXT AS ?Q_NEXT #1 + NXT + ?LABEL #1
    DO CREATE _2 ?Q_NEXT ,, AS ,,
    DO CREATE _2 ?Q_NEXT ,WHILE, ,NOT, ,NEXTING, AS QUA
    DO CREATE _2 ?GERUND ,NEXTING,=1 AS NXT
    DO CREATE _2 ?TEMPLATE ,LABEL, ,NEXT, AS NXT
    DO GIVE UP
Again, the ?TYPE flag is extension. This time there are several additions to the grammar. The first CREATE statement adds the actual NEXT, using the ?LABEL symbol already present in sick, as well as another auxiliary symbol, ?Q_NEXT, which is defined in the following two statements: it can be empty, and generate no code, or it can parse the text WHILE NOT NEXTING, in which case it adds QUA (QUAntum) to the generated code. Since we are adding a new statement, we also need to extend the definition of ?GERUND (used by ABSTAIN FROM etc) and of ?TEMPLATE (used by CONVERT, SWAP, as well as the template form of ABSTAIN FROM etc). Note that, unlike the case of user-generated statements discussed in a previous section, we can use the statement's opcode as gerund.