hoc3 adds support for:

• The exponentiation operator, ^
• Language “built-ins” - Functions and constants that are available globally at startup. (By necessity, this will add some basic language support for recognizing function calls.)
• Variables with names of up to 100 characters. (A happy side-effect of our changes to recognize the names of builtins.)
• Most of our tiny math library, including floating-point error support.

Grammar Changes

Our grammar needs some additional rules to support exponents and parentheses, as well as more extensive changes to support multi-character variables. Last, we’ll add productions to call a builtin function with 0, 1, or 2 arguments (which are always expressions).

An overview of the new structure, without any parser actions, is below.

list:       /* nothing */
        |    list terminator
        |    list assign terminator
        |    list expr terminator
        |    list error terminator

assign:      assignable '=' expr
        |    assignable ':' '=' expr

call:        BUILTIN '(' ')'
        |    BUILTIN '(' expr ')'
        |    BUILTIN '(' expr ',' expr ')'

expr:        NUMBER
        |    assign
        |    call
        |    VAR
        |    CONST
        |    '@'
        |    expr '+' expr
        |    expr '-' expr
        |    expr '*' expr
        |    expr '/' expr
        |    expr '^' expr
        |    '-'expr
        |    '(' expr ')'

assignable: VAR
        |   CONST

terminator: '\n'
        |   ';'

Two interesting notes to keep in mind:

• Even though assign is a type of expr, it has its own list production, because we don’t want to output the value of an assignment.

• We have a new assignable production that encompases both variables and constants.

Module Organization

hoc3 adds enough independent functionality that we will split it into separate files.

• symbol.c – Builtin functions and constants, as well as user-defined variables/constants, are all defined as Symbols; this module exports the symbol table interface, defined later. This interface allows us to define new symbols, and lookup the type and value of existing ones.

• builtins.c – The builtins we’ve defined for the language. All predefined names in hoc3 are declared here.

• math.c – Implements the math builtins for hoc3, which are declared in builtins.c.

• hoc.h – For simplicity, a single header file is used to communicate all of our interfaces; the symbol, math, and builtins modules each export their APIs here.

• hoc.y – Still contains our language grammar and main loop. It also contains helper functions for runtime errors and warnings, used by the rest of the files.

hoc3’s Math Library

hoc3 now supports builtin functions; all that remains is to populate them. hoc3’s tiny math library is mostly a wrapper around the standard library.

Our Math Wrapper

We implement all math functions inside math.c; each of the functions in hoc3 is a wrapper around a math.h standard library function. The job of the wrapper functions is simply to check for error conditions and convert them into runtime hoc errors. As an example function, consider our “power” function, used to implement x ^ y:

static double check_math_err(double result, const char *op);

double Pow(double x, double y) {
  return check_math_err(pow(x, y), "exponentiation");
}

Handling Floating-Point Errors

The math library functions don’t fail when given “invalid” arguments, but they do report errors via other channels. But to expose these errors to our caller in hoc3, we want to use our exec_error function.

Now, floating-point errors in C may be reported in two different ways, depending on whether our machine has full IEEE floating-point support. We can check how errors will be reported using the math_errhandling macro, introduced in C99. It has one of three values:

1. MATH_ERRNO - Supports only using the errno variable to check floating-point errors
2. MATH_ERREXCEPT - Only the “new” fetestexcept function is supported
3. The bitwise-or of the above - Supports both

The fetestexcept function lets us check which kind of exeptional case has occured; we will ignore “inexact” results, since our core data type is double, many integer-valued operations will have inexact results.

static double check_math_err(double result, const char *op) {
  static const char *domain_msg = "argument outside domain";
  static const char *range_msg = "result outside range";
  static const char *other_msg = "floating-point exception occurred";

  const char *msg = NULL;
  if ((math_errhandling & MATH_ERREXCEPT) && fetestexcept(FE_ALL_EXCEPT)) {
    // Special case: Inexact results are not errors.
    if (fetestexcept(FE_INEXACT)) {
      goto done;
    }

    if (fetestexcept(FE_INVALID)) {
      msg = domain_msg;
    } else if (fetestexcept(FE_DIVBYZERO | FE_OVERFLOW | FE_UNDERFLOW)) {
      msg = range_msg;
    } else {  // unknown
      msg = other_msg;
    }

    feclearexcept(FE_ALL_EXCEPT);
  } else if (errno) {
    if (errno == EDOM) {
      msg = domain_msg;
    } else if (errno == ERANGE) {
      msg = range_msg;
    } else {
      msg = other_msg;
    }
    errno = 0;
  }

  if (msg != NULL) {
    exec_error("math error during %s: %s", op, msg);
  }

done:
  return result;
}

Since the IEEE floating-point exceptions provide more information for us than the old errno system, we default to using them. For embedded or older systems that support only errno, we leave logic in for them. More details can be found in the math_errhandling documentation.

Adding Exponent Syntax

Once we have our new math.c module and a Pow function, we can add it to our language as a piece of literal syntax.

First, we define our new ^ operator, alongside (but with higher precedence than) the other binary operators.

  %left   '*' '/'   /* left-assoc; higher precedence */
+ %right  '^' /* exponents */
  %left   UNARY_MINUS  /* Even higher precedence
                          than * or /. Can't use '-', as we've used
                          it already for subtraction. */

Our parser action will assume the Pow function is available by declaring it extern.

extern double Pow(double, double);

So long as the hoc3 program is linked with the math object file, we can now simply call Pow() in our action.

expr:           NUMBER { $$ = $1; }
...
          |       expr '-' expr   { $$ = $1 - $3; }
          |       expr '*' expr   { $$ = $1 * $3; }
          |       expr '/' expr
                  {
                      if ($3 == 0) {
                          exec_error("Division by zero");
                      } else {
                          $$ = $1 / $3;
                      }
                  }
+         |       expr '^' expr   { $$ = Pow($1, $3); }
          |       '-'expr         %prec UNARY_MINUS { $$ = (-1 * $2); }
+

Symbols & The Symbol Table

To manage an arbitrary set of user-defined variable names, along with the names of our builtin functions / constants, we’ll need a more sophisticated data structure than our simple 26-element variables array. To that end, hoc3 adds the concept of a Symbol: a named, typed value. The symbol module also defines functions for accessing a global symbol table.

We can call install_symbol to add a symbol to the table, and lookup to fetch a symbol’s current value.

Symbol *lookup(const char *name);
Symbol *install_symbol(const char *name, short type, double value);

The core data type of our symbol table is struct Symbol; it contains all the information required to find and use a named value.

struct Symbol {
  short   type;  // Generated from our token types
  char   *name;
  Symbol *next;
  union {
    double             val;   // a double-valued symbol
    struct BuiltinFunc func;  // a callable symbol
  } data;
};

Symbol Types

A Symbol is treated differently depending on its “type”, stored in the imaginatively-named type field.

• BUILTIN symbols point to functions, and can be called with zero or more arguments. They must return a double value.
• VARIABLEs hold a double. Without an operator, they will produce their current value. The assignment operator may be used to assign a new value to a variable.
• CONSTANTs operate like variables, but can only be assigned once.

We’ll define the actual values used for the type field when we make our grammar changes.

Symbol Data

The symbol’s data field has a different C type depending on the value of Symbol.type.

For “value symbols” (i.e. not functions), we have a simple double value, stored in Symbol.data.val.

For BUILTIN types we have Symbol.data.func, which is a struct containing enough information to call an appropriate function pointer. It has enough space for an integer, args, and a function pointer, which must return a double and take either 0, 1, or 2 arguments. When using a Symbol of type BUILTIN, we first examine its args field, which counts the expected number of arguments. Based on its value, we know to use the union field call0, call1, or call2.

/** Function descriptor for builtins: these always return doubles */
struct BuiltinFunc {
  int args;
  union {
    // anon union: e.g. use `data.func.call0` directly. */
    double (*call0)(void);
    double (*call1)(double);
    double (*call2)(double, double);
  };
};

Implementing the Symbol Table

The last two fields of Symbol are used for lookup. They implicitly define the symbol table.

• A name for lookup
• A next link to the next Symbol in our table.

The “table”, internally, is simply a static pointer to a linked list of Symbol objects. This implementation suffices, at least for “calculator” uses.

static Symbol *symbol_table = NULL;

Installing Symbols

Installing a new symbol object into the table requires us to:

1. Allocate memory for a new symbol object
2. Populate its fields based on the inputs to install_symbol()
3. Link it to the rest of the defined symbols, so it can be found by lookup().

Allocation is as simple as a malloc() to hold the structure and the name, though we wrap this in our own allocator, emalloc(), with the same argument as malloc() (covered at the end of this section).

Symbol *install_symbol(const char *name, short type, double value) {
  size_t  name_len = strlen(name);
  Symbol *s = emalloc(sizeof(Symbol)                       // actual symbol
                      + (sizeof(char)) * (name_len + 1));  // room for name

  s->name = (char *)(s + 1);
  strcpy(s->name, name);
  s->name[name_len] = '\0';
...

For hoc3, we’ll assume that every symbol we install is a simple double value; we’ll revisit this later.

...
  s->type = type;
  s->data.val = value;

Finally, we link the symbol to the existing global table. Since the static symbol_table variable starts as NULL, our table is always null-terminated.

...
  s->next = symbol_table;
  symbol_table = s;
  return s;
}

Our allocation wrapper

The emalloc() function is nothing more than a version of malloc that uses our exec_error() functionality to report errors:

void *emalloc(size_t nbytes) {
  void *ptr = malloc(nbytes);
  if (ptr == NULL) {
    exec_error("Out of memory!");
  }
  return ptr;
}

Symbol Lookup

Looking up symbols is as simple as walking our linked list, returning the first matching Symbol.

Symbol *lookup(const char *name) {
  Symbol *current = symbol_table;
  while (current != NULL) {
    if (strcmp(current->name, name) == 0) {
      return current;
    }
    current = current->next;
  }

  return NULL;
}

Reassignment for Free

Notice that the way we implemented install_symbol does not check for duplicates, and so assigning the same name twice simply installs a new symbol “in front” of the old one. This, combined with the linear-search behavior of lookup, means that re-assigning a variable “just works” with no additional logic, at the cost of some additional memory.

Named Variables

With the symbol table module, we can replace our simple variables array with uses of the Symbol table.

Step 1: Adding Symbol Tokens to our Grammar

When we produce Symbol tokens, we’ll return the symbol type as a token type, but the value produced for that token must be a full Symbol object.

We can do that by replacing our simple hoc_index token-value-type with a Symbol version.

%union {
  double hoc_value;
- int hoc_index;
+ Symbol *hoc_symbol;
}

We’ll also define the token types corresponding to symbols here; we’ll *reuse these values to populate Symbol.type!

  %token  <hoc_value>     NUMBER
+ %token  <hoc_symbol>    VAR CONST BUILTIN UNDEF
  %type   <hoc_value>     expr assign call

Step 2: Recognizing Symbols

Our lexer will need to be updated to recognize symbol tokens and produce Symbol objects. A symbol token will be any alphanumeric identifier that starts with a letter (just as in C). We read up to SYMBOL_NAME_LIMIT characters, discard the rest, and lookup the symbol. If it exists, we produce the existing value. Otherwise, we install an UNDEFined symbol with that name, and produce it. Our hope is that the symbol token is part of an assignment expression, so we’re about to define it. However, we don’t return the UNDEF token type; instead we return the type VAR. (See the next step for the reasons why.)

All of this logic goes at the bottom of our existing yylex() function

int yylex(void) {
    int c;
    ...
    if (isalpha(c)) {
        Symbol *s;

        char buf[SYMBOL_NAME_LIMIT+1];
        size_t nread = 0;
        do {
            buf[nread++] = c;
            c = getchar();
        } while (nread < SYMBOL_NAME_LIMIT && (isalpha(c) || isdigit(c)));

        // Just in case we exceeded the limit
        while ((isalpha(c) || isdigit(c))) {
            c = getchar();
        }

        // at this point, we have a non-alphanumeric 'c'
        ungetc(c, stdin);

        buf[nread] = '\0';
        if ((s=lookup(buf)) == NULL) {
            s = install_symbol(buf, UNDEF, 0.0);
        }

        // Produce symbol for parser
        yylval.hoc_symbol = s;
        return (s->type == UNDEF ? VAR : s->type);
    }

    return c;
}

Step 3: Evaluating Variables

We’ll create a new production for any symbol that we can assign a value to; namely, VARs and CONSTs. We’ll call this an “assignable”. For now, we’ll focus on VARs. Our VAR action changes to handle any assignable, and simply returns the value stored inside the symbol’s data.val field.

  expr:           NUMBER          { $$ = $1; }
          |       '@'             { $$ = previous_value; }
-         |       VAR             { $$ = variables[$1]; }
+         |       assignable
+                 {
+                     $$ = $1->data.val;
+                 }
...
+ assignable:     VAR | CONST
+         ;

Step 4: Assignment Changes

Our previous variable-assignment expression will be replaced with a non-production called assign.

- %token  <hoc_value>     NUMBER
- %token  <hoc_index>     VAR
+ %type   <hoc_value>     expr assign call

The assign action will change the Symbol type from UNDEF to VAR, then set the symbol’s value so it can be evaluated later.

  expr:           NUMBER                { $$ = $1; }
-         |       VAR '=' expr          { $$ = (variables[$1] = $3); }
+         |       assign
...

+ assign:         assignable '=' expr
+                 {
+                       $1->type = VAR;
+                       $$ = ($1->data.val = $3);
+                 }
+

Step 4: Detecting undefined symbols

We don’t want to let the user evaluate an undefined symbol, but they should be allowed to assign a value to one. To support this nuance, we have two options:

1. We can add add more specific productions to our parser
2. We can keep the productions generic, and add C code to check our requirements within the parser actions.

hoc3 chooses to do more in C; its lexer will always return the token type of an undefined symbol as VAR, but the Symbol object it produces will have the correct type field. This allows us to check the typewithin our parser action, and reject invalid uses of undefined symbols.

Example: Allowing Assignment of UNDEF Symbols

assign:   assignable '=' expr
          {
             $1->type = VAR;
             $$ = ($1->data.val = $3);
          }

Example: Refusing to Evaluate UNDEF Symbols

expr:         NUMBER        { $$ = $1; }
...
      |       assignable
              {
+                 if ($1->type == UNDEF) {
+                     exec_error("Undefined variable '%s'", $1->name);
+                 }
                  $$ = $1->data.val;
              }

The token type will never be UNDEF, because we never return that type from our lexer. (It’s mainly used as a way to add the enumeration value.)

Step 5: Defining Constant Symbols

Much like we check Symbol.type to detect undefined symbols, we can use a new type to describe symbols that cannot be reassigned once they have a value. In hoc3, we’ll use that to add some built-in constants for PI, E, etc. We’ll also allow our users can define new constants with the := operator.

The implementation of constants is relatively simple; the parser actions contain the logic.

When we are inside the “assign constant value” production, we:

1. Check if the symbol is already a constant, and fail
2. Otherwise, we update the type and value of our Symbol, so that it’s a constant from now on.

assign: ...
        assignable ':' '=' expr
        {
           if ($1->type == CONST) {
             exec_error("Cannot reassign constant '%s'", $1->name);
           } else {
             $1->type = CONST;
             $$ = ($1->data.val = $4);
           }
        }

We also have to update the variable-assignment production, to make sure that a user cannot use PI = 10 to modify our constants either.

assign:  assignable '=' expr
         {
           if ($1->type == CONST) {
             exec_error("Cannot reassign constant '%s'", $1->name);
           } else {
             $1->type = VAR;
             $$ = ($1->data.val = $3);
           }
         }

Step 6: Adding our Builtin Constants

Finally, we want to add the constants that hoc3 provides as part of its language, PI and E. We create a builtins.c module, which exposes a single public function via hoc.h.

void install_hoc_builtins(void);

This should be called on program startup, and should install all the symbols we want to “build into” the hoc3 language.

int main(int argc, char *argv[]) {
    (void)argc;

    program_name = argv[0];
    install_hoc_builtins(); <<<< Before setjmp!
    setjmp(begin);
    return yyparse();
}

To try to keep the modules as independent as possible, we’ll let install_symbol continue to be the only function that constructs a Symbol. We’ll use a separate, internal structure to hold the constants before installation (though using Symbol would work just as well, and use less memory). Notice that the last value in our constants array has a NULL name, informing us when we’re done.

static struct {
  const char *name;
  double      value;
} constants[] = {
    {"PI", 3.14159265358979323846},
    {"E", 2.71828182845904523536},
    {NULL, 0},
};

Our “install” function merely creates symbols for each of them.

void install_hoc_builtins(void) {
  for (int i = 0; constants[i].name != NULL; i++) {
    install_symbol(constants[i].name, CONST, constants[i].value);
  }

Supporting Builtin Functions

Once we have the infrastructure for Symbols and language builtin installation, adding Symbols for function calls requires surprisingly little code. First, we’ll add a single builtin function, to ensure the language structures are working. The next section will add the math functions described above.

Our language’s builtin functions will be declared in builtins.c, just as our constants are. We’ll use another anonymous structure to hold the data about the builtin functions. (You could re-use the BuiltinFunc struct, but it has no `namea field, since .)

#include <math.h> // From standard library
...
static struct {
  const char *name;
  int         args;
  union {
    double (*call0)(void);
    double (*call1)(double);
    double (*call2)(double, double);
  };
} builtins[] = {
    {"abs", 1, .call1 = fabs}, // temporary function
    {NULL, 0, .call0 = NULL},
};

And update our installation function to allow installing functions with 0, 1, or 2 arguments.

void install_hoc_builtins(void) {
  ...

  for (int i = 0; builtins[i].name != NULL; i++) {
    Symbol *s = install_symbol(builtins[i].name, BUILTIN, 0.0);

    // Overwrite `data` for the symbol; this is a function
    s->data.func.args = builtins[i].args;
    switch (builtins[i].args) {
      case 0:
        s->data.func.call0 = builtins[i].call0;
        break;
      case 1:
        s->data.func.call1 = builtins[i].call1;
        break;
      case 2:
        s->data.func.call2 = builtins[i].call2;
        break;
      default:
        exec_error("Cannot start hoc: Argument count error for builtin '%s'",
                   builtins[i].name);
    }
  }
}

With our symbol installed, we can now evaluate functions. We’ll add a new expression type, call, which has three different forms, one for each number of arguments.

call:           BUILTIN '(' ')'
                { ... actions here ... }
        |       BUILTIN '(' expr ')'
                { ... actions here ... }
        |       BUILTIN '(' expr ',' expr ')'
                { ... actions here ... }

Calling a function has two parts:

1. Checking the correct number of arguments were used
2. Evaluating the builtin function with the arguments

We’ll use call1 as our example; the other two are the same.

call: ...
     |     BUILTIN '(' expr ')'
           {
               check_call_args($1, 1);
               $$ = $1->data.func.call1($3);
           }

$3, our argument, is guaranteed to have a double value, since expr is declared to produce a hoc_value. That’s the value we produce as well, as builtin calls are expressions too. (Note that the call non-terminal is declared to produce a hoc_value in the preamble.)

check_call_args verifies our argument count & produces an easy-to-read error message, thanks to our exec_error helper.

/*
 * Verify Symbol's declared arg count matches actual,
 * or display a helpful error message with mismatch
 */
void check_call_args(Symbol *s, int actual) {
    int expected = s->data.func.args;
    if (expected != actual) {
        exec_error("Wrong number of arguments for %s: expected %d, got %d",
        s->name, expected, actual);
    }
}

Filling out the builtins List

We can now replace the temporary builtin for absolute values with a list of the math functions from math.c. First, we’ll need extern declarations in builtins, since we don’t want to expose the entire math library via hoc.h.

extern double Abs(double), Acos(double), Atan(double), Atan2(double, double),
    Cos(double), Exp(double), Integer(double), Lg(double), Ln(double),
    Log10(double), Sqrt(double), Sin(double);

Then, we can replace the temporary abs function with a list of the math.c functions.

...
} builtins[] = {
    {"abs", 1, .call1 = Abs},
    {"acos", 1, .call1 = Acos},
    {"atan", 1, .call1 = Atan},
    {"atan2", 2, .call2 = Atan2},
    {"cos", 1, .call1 = Cos},
    {"exp", 1, .call1 = Exp},
    {"int", 1, .call1 = Integer},
    {"lg", 1, .call1 = Lg},
    {"ln", 1, .call1 = Ln},
    {"log10", 1, .call1 = Log10},
    {"sin", 1, .call1 = Sin},
    {"sqrt", 1, .call1 = Sqrt},
    {NULL, 0, .call0 = NULL},
};

What’s Next

hoc3 allowed us to build the foundations of our symbol table and math library without changing the core language too drastically. In hoc4, we’ll add an interpreter layer to hoc, which will handle our core expression evaluation, and set the stage for flow control.