Experimenting with Bison Just for the hoc of It

The hoc interpreter was created by Brian Kernighan and Rob Pike and published in their 1984 book The UNIX Programming Environment. Their hoc project demonstrated the strategy of starting first with a small test program and then adding capabilities step-by-step to grow the program into a useful tool.

Using Steve Johnson's famous yacc (yet another compiler-compiler) parser-generator, the authors present development details and program sources for their high order calculator, implementing an interpreted C-like programming language suited to arithmetic applications.

The book presents six stages of step-by-step development. Stage 1 uses yacc to generate the parser for a four-function calculator. Stage 2 adds single-letter variables and error recovery. Stage 3 introduces arbitrary variable names and built-in functions such as sqrt(), cos() and so on.

In the next development step, Stage 4, the interpreter undergoes a major enhancement. It becomes a compiler, the output of which is threaded code in the form of a stored-program "machine" that can be executed. Stage 5 adds control flow and relational operators, so that the stored program can have loops and conditional branching. Stage 6, the final development stage presented in the book, provides recursively callable functions and procedures and adds the ability to print character strings and read values from stdin or from a named file.

In this article we continue development, presenting a stage 7 version of hoc designed for i386-family IBM-compatible PCs running GNU/Linux. The features added provide capabilities tailored mainly to scientific and engineering applications. As in the original hoc, our numeric data type is the double, augmented now with arrays of doubles, strings and arrays of strings.

For experimental purposes we have a home-brew device driver module for the speaker. SVGAlib is used for screen graphics, which is yet another reason that the program runs with the set-user-ID bit set. Since our goal is to have fun while learning about Bison, the PC and device driver modules, hoc7 is best run on a computer dedicated to a single-user, where we have root-access and can blame only ourselves for any havoc created while experimenting.

Although we speak here mainly to further development, yet for a sizeable range of applications the present version of hoc7 is usable out of the box, so to speak, as an alternative to BASIC. The code, of course, is GPLed. So, recalling those times when the command line was king, if "you pine for the days when men were men and wrote there own device drivers", and you prefer to arrange things to suit yourself, this project may offer those opportunities.

Download the file hoc7n.tgz from www.seasurf.com/~jdennon, create a directory on your system for the source with the command mkdir hoc7, for example, and then copy the compressed file hoc7n.tgz into that directory. Go to that directory and decompress the files with the command tar -xvzf hoc7n.tgz.

Go to the </dev> directory, promote yourself to superuser with the command su and type in root's password.

The hoc7 programs that use the speaker driver expect their device file to be in the /dev directory, so put it there with mknod spkr c 13 0. Then restore your normal user status with exit.

Now go to the directory that contains the device driver module for your version of the Linux kernel. For example, for Linux 2.4, use the command cd drivers2_4. Compile the speaker device driver module with the command mcomp.sh spkdrv.

Promote yourself to superuser with the command su, and type in root's password. Install the device driver with the command insmod spkdrv.o, then restore normal user status and return to the hoc sources directory with the command cd ..

Now create the hoc7 executable with the commands

   
        make clean
        make

The hoc7 executable needs to be "set user ID", so promote yourself to superuser and then use the command ./enable.sh hoc7 to change the file's owner to root and mark it set-user-ID.

To test the hoc7 interpreter, go to the examples directory with the command cd examples and run, for example, the following stirl program that calculates approximate factorial numbers using Stirling's approximation:

        '  stirling's factorial approximation formula
        '  provides a fast approximation to factorial(x)
        '  that gets better as x becomes larger.
        '
        func stirl() {
                return (sqrt(2*$1*PI) * ($1/E)^$1*(1 + 1/(12*$1)))
        }
        '
        '  calculate factorial(x)
        func fac() {
                if ($1 <= 0) { return (1) }
                return ($1 * fac($1-1))
        }
        '
        ' display the ratio of factorial(x) to stirling's approximation of
        ' the factorial, for x from 1 to 10.
        '
                print "\n Compare Stirling's approximation with the\n"
                print " factorials that it approximates:\n\n"
                i = 0
                print "        i    ratio: factorial(i)/stirling(i)\n"
                while ((i=i+1) <= 10) {
                        print " i = %4.0f ",i
                        ratio = fac(i)/stirl(i)
                        print "   ratio  = %12.9f",ratio
                        print "\n"
                }

You can execute this program with the command ../hoc7 stirl. You should get a response that looks like this:

         Compare Stirling's approximation with the
         factorials that it approximates:
                i    ratio: factorial(i)/stirling(i)
         i =    1    ratio  =  1.001019278
         i =    2    ratio  =  1.000518836
         i =    3    ratio  =  1.000278990
         i =    4    ratio  =  1.000171400
         i =    5    ratio  =  1.000115396
         i =    6    ratio  =  1.000082810
         i =    7    ratio  =  1.000062254
         i =    8    ratio  =  1.000048479
         i =    9    ratio  =  1.000038808
         i =   10    ratio  =  1.000031761