Nixers Book Club - Book #1: The UNIX Programming Environment - Community & Forums Related Discussions

Users browsing this thread: 2 Guest(s)
Long time nixers
Merry Christmas and happy new year, nixers!
It's time to bump this thread!

Chapter 8 is about the full use of the UNIX environment and its development tools to develop a project of an interpreter for a language that deals with floating point arithmetic. The development is broken down into six stages that “parallel the way that they actually wrote the program”. The stages go from a simple calculator executed as it is parsed, to a stack machine interpreter, to a full language with functions calls and recursion.

In the first stage, expressions are evaluated as the input is parsed. In more complicated situations (including hoc4 and its successors), the parsing process generates code for later execution. We implement a four-function calculator with parentheses.

In the second stage, we use an array of characters from a through z to implement variables.

In the third stage, we implement arbitrarily long variable names and built-in functions by implementing a symbol table (which is actually a linked list of structures holding variable names and a union of a value and pointer to function).

In the fourth stage, we move from executing code as the input is parsed to generate code as the input is parsed for later execution (rather than being evaluated on the fly).

In the fifth stage, we add control-flow (if-else and while), conditions and statement grouping.

In the sixth and last stage, we add recursive functions and string handling.

The main tool is the yacc(1) parser generator, that is used to write one of the most important parts of the project (along with the machine interpreter): the grammatical parser. The chapter also introduces the make(1) utility to manage the project, and does a short digression on lex(1) (the lexical analyzer generator).

The interpreter we develop is hoc, the High Order Calculator. Although hoc(1) hasn't survived into modern UNIXes, it survives on plan 9. Its source code is disponible here (bundled in a single shell script!).

It was very fun to write hoc, you can see my implementation here on github.

Quote:The machine itself is an array of pointers that point either to routines like `mul` that perform an operation, or to data in the symbol table.

I think that the `Inst` type is a botch. It is used not only to type a Instruction operation in the machine memory, but also to type instruction operands (entries to the symbol table) and also to type pointer to other instructions (as is needed in stage 5 for while and if statements). The original implementation uses a multiple purpose pointer to function that is casted to other stuff. I chose to use a union instead. The code on `whilecode` and `ifcode` became more straightforward with my change. They don't need those complex type casts anymore.

Quote:By the way, we chose to put all this information in one file instead of two. In a larger program, it might be better to divide the header information into several files so that each is included only where really needed.

The one-header method is used through the entire project. I didn't like this approach, as as the program grows the header becomes messy. I opted to separate the code into more files and write a header to each module.

Another feature I implemented was to use variable-length argument list for built-in functions, in order to use bultin functions with variable number of arguments. I implemented a argument list in the parser as a grammatical class, and assign it a pointer to a structure containing the arguments of a builtin function. This also prohibit assignment to constants, because I implemented constants as a nullary function, for example pi(), and hoc prohibits assignment to a builtin function. For example, atan2(y, x) will allocate a Arg structure with two elements, and pass its address to the builtin function. The structure will be freed with delargs() after evaluating the builtin function.

This is the first time I used yacc(1) and I liked it a lot. It is a really useful utility. I have seen other implementations of hoc(1) that uses GNU Bison extensions, but I had to maintain myself in the POSIX yacc, as that's what my system has.

Messages In This Thread
RE: Nixers Book Club - Book #1: The UNIX Programming Environment - by seninha - 02-01-2021, 08:13 AM