Design and Implementation of the Programming Language GRIP

By Serguei V. Makarov

Foreword

This assumes that the reader knows something about programming (if he does not, I might be so bold as to direct him to a programmer’s tutorial, one of which is found at the back).

• GRIP is not a full-fledged language like C++ or Java! (Not yet at least!) It is the bare skeleton of a conventional language. (But, see the next point!)

• It is not easy to make a language like GRIP. It wouldn’t have been possible for me without the large experience of my father, who guided me in:
• Designing a language simple enough to easily implement, yet full enough to be used for simple calculations such as primeSieve (given in part 2). That is, the language must support numbers, constants like in Pascal, and simple one-dimensional arrays as data types, and the conventional control structures.
• Giving me tips on developing GRIP when I most needed them.

• A key point I’d like to make to you is that it wouldn’t have been possible for me to start working on this project if my parents hadn’t believed in me and said that I wasn’t ready for this task.

Another, more pleasant point, is the so called “introduction”.

I hope this collection of guidelines has not made you bored or offended (if it has, then I sincerely apologize). We are about to get out of this dry area, and enter the actual world of programming, which I hope we can get on with right now.

Part 1. A case study of compilers/interpreters

In this section, I shall describe the basic similarities and differences of a compiler/interpreter. Think of this section as one big compare-and-contrast. So, we should now be getting on to..

Compilers VS. Interpreters: a compare and contrast.

The more effective way to work with programming languages is to translate the text to a form which a computer can directly execute. This strategy is called compiling, and the program which does this is called a compiler. C and C++ use this strategy.

The advantage behind a compiler is the fact that a compiler breaks a program down into simple operations which can then be quickly executed.

The disadvantage behind this strategy is the fact that when debugging, we must often recompile the code, and the quick execution time is received at the cost of slow and big algorithms like optimization.

Also, files of text often depend on one another in large programs, so whenever we change one file, we must recompile all files which depend on it, which causes the dilemma of which files to compile and which to keep the same for efficiency. Whole programming languages have been developed to address this dependency problem (such as the language of make)!

In contrast, an interpreter does not generate any files, but executes the text directly, possibly compiling it into an efficient internal form. Dino, Perl, and Python are all examples of full-fledged interpreted languages.

The advantage here is that debugging is faster and thus more efficient. Also we don’t have to worry about file dependency issues, since the dependencies are updated at each execution.

All this doesn’t come without a downside - when the program is virtually bug-free, it runs very slowly and sluggishly.

Also, it is not friendly to the people who use the program, but don’t work on it, since you must also install a large interpreter program, and if the user is not careful, he might mess with the files and completely screw up the program. I’m not talking about what a nightmare it would be when you wrote the interpreter for the program in an interpreted language, and so on and so forth. (Unfortunately, GRIP is one of these nightmare languages. It is written in an interpreted language!)

This strategy is used for languages that are made for developing tools either not distributed at all or distributed to the most avid of programmers.

Now that we’ve clarified the major differences, we can begin to look at the anatomy of a compiler/interpreter. The beginning is pretty much the same in both, and can be summarized on the next slide, since I feel that even though there’s lots of space here, it’s not enough for a good chart, and I would advise you to go to the next slide and we’ll continue our presentation there. But first I must clarify to you..

..why interpreters don’t execute the program directly.

Unlike the optimal internal representation of the program, the program is linear. This is okay when the commands are very primitive, e.g. CPU commands, whose best internal representation matches the form in which they are stored. The translation algorithm of interpreters is not as elaborate as the one in compilers, otherwise they’d lose all their good sides and just acquire the bad sides of both.

Now that we have clarified that, we can get on to..

The anatomy of compilers/interpreters

This is the basic, crudely shown beginning of the translation process. At the end, a compiler would write the results to a file, while an interpreter would proceed to execute what it got. Clicking on one of the green elements will take you to a slide which will explain that part of the program in more detail.

• Process command line arguments if applicable.

• Read from input file(s), if any.

• Scanner

• Parser

• Translator

The Scanner

The scanner is a program that translates the linear, byte-by-byte textual representation of the program to a form which it is easier for the parser to work on. For instance, a scanner might only recognize letters and “@”. Also, it might recognize certain patterns in the characters such as identifiers, numbers, etc. It might convert these patterns into the corresponding objects and place them in objects called tokens and send these to the parser.

The Parser

The parser breaks the program down into a representation according to rules called the grammar or syntax of the language. For instance, the grammar G which matches a letter or “@” followed by a letter can be represented as:

G[x] ::= {
        x ::= letter | “@” letter
}

G[x] is the name of the grammar. X is a nonterminal. The [x] in G[x] means that x is the base rule of G. A program that is syntactically correct from G’s point of view must match x. | expresses alternation, meaning that a rule may match either the objects on the left or the right objects. Letter is a terminal which is processed by the scanner. Letter may contain other information (such as the letter we’re actually looking at), but all G wants to know is that it’s letter that we’re looking at, so letter may match more than one thing. “@” is also a terminal, but this time it can only match one thing : “@”. There are many algorithms to parse using grammars, but sometimes we don’t even use a grammar, or we write a parser that can only parse one grammar G. As you can see, grammars are not absolutely necessary, although they are convenient.

The Translator

The translator takes the result of the parser and (in compilers) converts it to machine code, performing optimization, etc. In contrast, an interpreter might convert it into an efficient form that might take advantage of the language the interpreter is written in. The code (in an interpreter) is immediately executed. In the example on the previous page, letter might mean print the letter, while “@” letter would mean print the letter counting from the other end of the alphabet.

Now that we have clarified the tasks compilers/interpreters perform, we can work on explaining GRIP-specific issues that come with the language’s quirks and making them work.

Part 2 - Concepts in the rest of the presentation.

This short section contains explanations of the concepts used in the rest of the presentation, and is needed so that people unfamiliar with these concepts can understand Part 3 fully.

About the programming language Dino

There is no need to discuss Dino in detail here, since it tries to resemble C, (and you ought to know at least a little of C, for instance the if-then-else structure. The description of a C-like for loop is given in appendix A). Dino differs in its view of blocks, and in that it is block-structured (like GRIP) (Also, Dino is dynamically-typed (there is no restriction on values stored in variables =:-O), and this may cause some confusion to beginners ;-(.). Generally, a procedure/function was modeled as an entity that can be called and it will eventually return to the spot where it was called. In Dino, a mechanism of block instances is used. If a block is standing as a statement, Dino, when encountering it, creates a block instance and executes it. Blocks can also be declared. There are three type of blocks, but only two are used (the third is used for concurrency) in the implementation of GRIP. A block can be a function, returning a value or nil (roughly translated to “no value”, or void in C). Then all the variables are private, that is, unavailable to outsiders. A function, when called, creates a block instance of itself. The current computation is suspended until the function has returned, and then the block instance is destroyed. A class doesn’t return a value, but retains the block instance after it stops executing. Blocks are first-class values (i.e. they can be assigned to variables, passed as parameters to other block instances, and even returned. This allows for higher-order functions, something that before was left as the legacy of functional languages. Also, a block can be extended, that is, code can be added to the end of a block that we can’t change. This replaces the usual inheritance mechanism in object-oriented languages. Formal parameter formats are self-explanatory.

Example of a GRIP program

Here is a sample GRIP program. It illustrates the control structures and data types found in GRIP.

/* The program heading. The identifier can conflict with identifiers in
   the statement. */
program primeSieve
/* This is all one block statement. A GRIP program in fact consists of
    only one statement. */
{
        /* Constant declarations. */
        sievesize : constant 100;
        /* Global variables. */
        i count : integer;
        /* An array. */
        flags : integer [100];
        /* Initialize count and flags. */
        count <- 0;
        /* If it isn't the C-style for loop :-) */
        for (i <- 0; i < sievesize; i <- i + 1; /* This semicolon has to be here. */)
                flags[i + 1] <- 1;
        /* Now get to work! */
        for (i <- 0; i < sievesize; i <- i + 1;)
                /* This is a multi-branch form of if-then-else. */
                cond { /* This is NOT a block statement. Negative. */
                        flags[i + 1] { /* This is another block-statement. */
                                /* Two local variables. */
                                k prime : integer;
                                prime <- 2 * i + 3;
                                k <- prime + i;
                                for (; k < sievesize; k <- k + prime;)
                                        flags[k + 1] <- 0;
                                count <- count + 1;
                        }
                        /* Here would have been "else blablablablabla...", but primeSieve
                            has no need for "else blablablablabla..." */
                }
        /* I/O, unfortunately without the I. Maybe later ;-( */
        put "The number of primes less than " sievesize " is " count;
}
/* This has all of the constructs available to a GRIP programmer. Not much, eh? :-| */

Part 3 - How this combines to make GRIP and in what ways.

Now we can talk about GRIP and the issues that we face when developing it. I’ll walk through with you step-by step (with general flowcharts), starting with..

The Source Code For GRIP

Profile for a typical GRIP program given by DINO

The Scanner

The GRIP language is completely freely-typed, and spaces act only as list separators and separators where otherwise you could confuse two tokens for a completely different tokens. As a result of this, there is no “ “ token declared in the Earley Parser’s grammar. Comments /* and */ are analogous to spaces and are ignored as spaces are. Identifiers and numbers are put into generalized tokens for the parser’s efficiency. Keywords are first labeled as identifiers and then converted to the corresponding keyword tokens. For convenience in diagnostics of GRIP programs, the line number of the token is stored. This method is realized in GRIP as the function scanner().

1. Prepare token-code conversion tables, result array.

2. No more characters? Goto step 5.

3. Build up/Ignore the next token.

4. Convert it into a form the Earley Parser understands. Goto step 2.

5. Return the results.

The Parser

The parser is relatively straightforward, owing that the language DINO has Earley’s algorithm built in. The formal grammar (used by the parser) is stored in the file grip.g.

Read GRIP.G.

Call SCANNER().

Call Earley’s algorithm with tokens from scanner.

The Translator

The translator is a very large and complex part of the program. The flowcharts here reflect this complexity. The Earley algorithm returns an abstract tree that is specified in the grammar (to get an idea of it, run GRIP with the -v option. The translator consists of several procedures that are highly recursive (that is, may call themselves):

• PARSE_INSTRUCTION_ANODE().

• CHECK_BLOCK().

• PARSE_EXPRESSION_ANODE().

• PARSE_PROGRAM_ANODE().

PARSE_PROGRAM_ANODE()

Don’t be fooled by this straightforward function. More complex things are to come.

Call PARSE_INSTRUCTION_ANODE() for the root node.

Call CHECK_BLOCK() for the result.

Return the results.

PARSE_INSTRUCTION_ANODE()

Prepare Classes To Return.

Select type of Instruction.

Put: goto <1>.

Assignment: goto <2>.

Blocks: goto <3>.

Cond: goto <4>.

For: goto <5>.

Empty: goto <6>.

<7>: Return the results.


---

This is a relatively straightforward process for the put statement, of the form
    put expr1 expr2 …;
We call PARSE_EXPRESSION_ANODE() for every expression we get.

<1>: Call PARSE_EXPRESSION_ANODE() for every expression.

Goto <7>.

---

The assignment statement is not very daunting, but it takes some underlying machinery in the semantic checker, namely the usage of Earley Parser tokens until semantical checking, and making an expression that evaluates to zero for assignment to scalar values.


<2>: Process the array index, call PARSE_EXPRESSION_ANODE().

Goto <7>.

---

Since GRIP is block-structured, blocks are considerably more than compound statements. Even though a GRIP program consists of only 1 statement
(which may contain other statements inside), PARSE_PROGRAM_ANODE() integrates this statement into an object of class prog(), which contains methods to execute the program correctly (this is an advantage of the object-oriented movement, where program execution is modeled by strictly controlled interaction of objects. This allows the objects (which respond to a set of messages) to often not care about whom the message came from. This makes it possible to turn complex programs, which might need to change their implementation slightly, for instance to accommodate
a programming environment, to be transformed to “library objects”, instead of rewriting a considerable amount of the code or using clumsy inter-process
messaging). PARSE_EXPRESSION_ANODE() needs to process all the things the block needs.

<3>: Prepare objects to return.

Process next declaration.

Declare the identifiers.

Parse the instructions.

Redeclare our configuration for underlying blocks (the blocks may override our declarations).

Goto <7>.

---

Conditionals and for loops are relatively straightforward and require either iteration or even invariant recursion. The empty statement is even more trivial.

<4>: Process each alternative. Goto <7>.

<5>: Process all relevant information. Goto <7>.

<6> : Generate an empty statement. Goto <7>.

PARSE_EXPRESSION_ANODE()

The general shape of the flowchart for this function is similar to the one for PARSE_INSTRUCTION_ANODE(). The operators other than the ones found in GRIP itself are var, used for variable references, and num, the constant operator.

Prepare classes to return.

Select type of expression.

    Var
             Compile array subscript.
    Num
             Make type-value pair.
    Other 
Call PARSE_EXPRESSION_ANODE() for the operands.

 Return the result expression.

CHECK_BLOCK()

The semantic checker for GRIP is just an extremely recursive program that hunts out all the variable references and performs checks on each one. Errors captured statically include:

• Attempt to assign to a constant.

• Scalar value in structured context.

• Attempt to declare an identifier twice (this is done during the translation of blocks).

Execution

A GRIP program is transformed into an easy-to-manipulate, high-level structure. It has a table (which is a built-in Dino structure) of variables, and a vector of instructions, which contain other instructions and blocks, and expressions inside. Instructions are represented quite uniformly, with a name field and an unbounded vector of parameters. There is almost a one-to-one structural identity with source code. Expressions are also pretty simple. Instruction formats are the following (the parameters are written by name, type, and comments):

---


 

Put

Element	...
Expression	...
May be num (..., "string")	...

 

Assign

Identifier	Index	Value
Identifier	Expression	Expression
is a string	= 0 for scalars

---


 

Cond

Condition	Branch	...
Expression	Instruction	...
= 1 for else		...

---


 

Cond

Initialization	Condition	Incrementation	Body
Instruction	Expression	Instruction	Instruction

---

 

Block

Block

Program

Expressions are represented by binary trees, with the operands as leaves. Operations are:

var (x, y) = x[y] if y > 0, otherwise x.
num (x,y) = x, where y is the type of the literal.

+,-,*, etc. work as expected. The algorithm conforms with this data structure completely.

Conclusion

Programming is a very complex and diverse topic, varying from the most mathematical and elegant to the most practical and bulky.

High-level languages are very impractical to implement, but they are essential for ease of coding common algorithms. Optimization was devised when someone noticed that even though higher-level languages were the obvious choice, with elegance in programming we lose efficiency. Optimization tries to use an algorithmic approach to make programs more efficient.

The complexity of implementing GRIP is slightly more than the average individual unit a practical programmer works on. This does not mean I am better, since a trained programmer manages a unit of any size more efficiently and systematically than me. For me, this formal training is far away, yet this foray into (for me) uncharted lands paid off. Programming is, and will be, my favorite topic.

Bibliography

• Gries, David. Compiler Construction for Digital Computers. © 1971 John Wiley & Sons.

• Finkel, Raphael A. 1995. Advanced Programming Language Design. © 1995 Addison-Wesley Publishing Company, Inc.

• O.J. Dahl, E.W. Dijkstra, C.A.R. Hoare. Structured Programming. © 1972 Academic Press London & New York.

• The Linux Bible, 4th edition. © 1996 Yggdrasil Computing Inc.