Tyger 3 Evaluation

Doing magic and conjuring meaning

Finally, we have arrived at the stage where we can actually get something out of our program; out of any program which we write in the language - evaluation.

Evaluation is where the interpreter actually applies meaning to the series of statements which compose our AST; this is how an expression like 5 + 10 actually affect “reality”, i.e. by producing a value from computation.

Now the primary divergence here from the book is that since I am using C, I don’t have the “luxury” of garbage collection; so my plans for initial implementation of the interpreter is to simply malloc new objects, and let it leak until the interpreter exits. I will revisit this when I implement “proper” garbage collection, for now leaking is fine as it allows me to get up and running, and the lifespan of the interpreter will only be short anyway (it is also hard to test garbage collection is properly functional in absence of the evaluation as it requires the presence of objects to free).

Background And Asides

I’m going to cover a few things before I start on the meat of actual evaluation; jump here for the actual process of evaluation.

An Aside on Objects

Throughout the rest of this article - and likely the series - I will make reference to objects; these are not objects in the Object-Oriented-Programming (OOP) sense, merely this is the most effective way of communicating and referring to a type, a data structure, to the reader. I will note however that there are, in some ways, similarities to objects in a language, such as Java, where “primitives” (e.g. integers) are encapsulated within the object’s memory, whereas other objects are more like “Objects” (classes) where there is an additional heap allocation for the stored data (e.g. strings).

Objects are defined as:

typedef struct tyinteger
{
  int64_t value;
} TyInteger;

typedef struct tystring
{
  const char *value;
  size_t len;
} TyString;

typedef union utyobj
{
  TyInteger integer;
  TyString string;
} uTyObj;

typedef struct tyobj
{
  TyObject_Kind kind;
  uTyObj o;
} TyObj;

Again the pattern of a tagged union arises, simply because it is useful; but to reinforce the point raised earlier, we see the TyInteger type encapsulates the value in the structure (i.e. dereferencing a pointer to an instance of this object in the VM will not require a second pointer hop to get the value), whereas the TyString type contains the length but requires a second “pointer hop” to access the underlying data (and hence comes with a second heap allocation). Whilst this isn’t super important now, it is worth covering the memory allocation, and the “management strategy” because, even though the current strategy is just “leak”, when I implement garbage collection, this will have to be covered and dealt with again (and possibly changed once more).

All objects are, however, allocated on the heap, I think the first example of arbitrary heap allocation we’ve had in this project (at least the non-test code). To perform all necessary creation/destruction of objects there are just 2 functions:

TyObj *tyobj_new(TyObject_Kind kind, void *datum);
void tyobj_delete(TyObj *obj)

I won’t dwell on the details as you can read the code to see implementation, but these exist to abstract repeated logic required to construct objects from given data; or in this case datum. I sense that this will be subject to revisiting if/when I add classes to the language but the simple interface of datum may suffice. These are also functions that I will possibly want to rework some more once garbage collection is implemented, which is another argument for centralising the logic here as it makes it so there is less surface area of allocation code.

Results of Evaluation

All evaluations must have some result, the question is what should this be on a fundamental type level? Take for example, the 2 statement types within the language, var statements, and expression statements; what should the result of each be? This is a design decision, as it affects some architecture, and process decisions for the internals of the “virtual machine” (a term I use with respect to this interpreter rather loosely).

Take, for instance, the process of binding (read assigning) a variable, var x = 10; - should this return a value? I would argue no, there is no result of said statement other than to mutate internal state of the VM, there is no type. This is where I differ, in aesthetic standards, from say JavaScript where the equivalent - let x = 10; - would yield a undefined. This isn’t to imply that there is no effect here, obviously an Object needs to be allocated somewhere, and this value associated with the ident. Expression statements however do return values, they may also mutate some internal state of the VM, but these do produce values. For example, evaluating an ident - x; yielding 10 in this case - or the result of an arithmetic expression - such as 10 + 5; yielding 15 - should produce a value, and return these either for other variables to be bound to, or for human interpretation of a result. It is worth noting that this is the reason for the TYOBJ_NONE enumerant, for cases where the VM performs an operation which doesn’t “produce” a value.

Environments

The first major component of the VM is the concept of “Environments”, defined as a collection of variables(/constants - when implemented) with a defined scope; the actual scoping of environments will be done later, but at time of writing there is no support for nested blocks, nor functions, there is only the “global” scope (i.e. top level to the interpreter).

Environments are implemented as a hash map, where the hash of a given key (the ident of a variable) is the result of a 32-bit FNV-1a hash function modulo the [defined] capacity of the hash map; moduloing the hash clamps the result to a defined range of entries/slots, i.e. assume the hash result of "foo" is 11736239235, if we apply %16 (the capacity of an example environment) to said hash, then we are gaurenteed the hashed key always is in the range 0 <= x <= 15, in this case the value is 3; this constrains our objects to a set of slots which can be allocated up front. In general, our algorithm for generating hashes looks like the following:

key := "foo"
hash := fnv1a(key)           -- generate initial value
hash := hash % env.capacity  -- clamp to defined range of valid slots

Evironments are defined as follows:

typedef struct tyenv_var TyEnv_Var;
struct tyenv_var
{
  const char *ident;
  size_t ident_len;
  TyObj *object;
  TyEnv_Var *next;
};

typedef struct tyenv
{
  TyEnv_Var *vars;
  size_t capacity;
} TyEnv;

I.e. each environment is an array of TyEnv_Vars, which are themselves defined as a singly-linked list node; the reason for the linked list nature of each hashmap entry is this allows for collision resolution later, i.e. the case where 2 keys (idents) have the same hash generated - asssuming the hash is generated according to the earlier defined algorithm. Capacity is a defined member here for a few reasons:

1. it allows for preallocation of a defined number of slots which can be written to (indicating our variables)
2. it allows for consistent clamping of the results of hashing to a defined range between all functions that accept the environment as an argument
3. it allows for a user (or me the developer) to specify different amounts of slots on a per instance basis

The last of these points was particularly useful for testing collisions, but I forsee if as potentially useful for when implementing functions - it seems sensible to me that a function’s environment should be smaller than that of the global environment, for instance. Due to the fact that each environment is backed by a dynamically defined array, then each environment needs to be explicitly created and destroyed:

// snippet taken from the REPL
{
  TyEnv global;
  tyenv_init(&global, 16);
  while (true)
  {
    // ... parse code and do things with the environment
  }
  tyenv_free(&global);
}

What options should we be able to perform on our environment (referred to as hash maps from here on)? We need to be able to:

• insert new key/value pairs,
• update existing keys,
• and delete keys

A pretty simple set of operations.

Inserting new key/value pairs is a fairly simple process, all we need to do is initially generate our hash value, perform a lookup to see if our key conflicts with existing entries, and if so resolve. In pseudocode this looks something like¹:

def env_do_insert(var: *TyEnv_Var, key: str, obj: TyObj) -> bool:
    if var.key == key:
        # handle case where key exists
    else:
        if var.next:
            return env_do_insert(var.next, key, obj)
        else:
            var.next = env_new_var(key, obj)
            return True

def env_insert(env: *TyEnv, key: str, obj: TyObj) -> bool:
    key_hash: u32 = fnv1a(key) % env.capacity
    exists: *TyObj = env_get(env, key_hash)
    if exists:
        if key == exists.key:
            # handle case where key exists
        else:
            return env_do_insert(exists, key, obj)
    else:
        env.elems[key_hash].key = key
        env.elems[key_hash].obj = obj
    return True

Here we see that key insertion consists of 2 functions, a pattern I implement across all hash map related functions:

1. env_insert

   1. hashes the key
   2. checks whether the map already contains an entry at the given [hash] slot
   3. if not then insert the object here
   4. if it does exist, check if the keys match
   5. if keys match, handle this*
   6. else call the function to perform the insert

2. env_do_insert

   1. compare if keys match
   2. if they match, handle this*
   3. else check if there is a “next” value in the linked list
   4. if there is a “next” value then recurse into this function, passing next
   5. otherwise create a new node in the list

*R.e. the question of what to do in cases where insertion hits a key which already exists, I decided to handle this as an “in-place” update and not throw an error; I decided that throwing errors in relation to this should be handled at a higher level, i.e. in actual evaluation rather than here; although, as I write, I may reconsider this in a planned refactor that’s coming for this whole system¹.

The pattern for updating keys is very similar to this pattern, the main difference here is if no stored object is found in the derived slot for the ident, or at in the linked list of entries, then we return an error:

def env_do_update(var: *TyEnv_Var, key: str, obj: TyObj) -> bool:
    if var.key == key:
        var.obj = obj
    else:
        if var.next:
            return env_do_update(var.next, key, obj)
        else:
            return False

def env_update(env: *TyEnv, key: str, obj: TyObj) -> bool:
    key_hash: u32 = fnv1a(key) % env.capacity
    exists: *TyObj = env_get(env, key)
    if exists:
        if key == exists.key:
            exists.obj = obj
            return True
        else:
            return env_do_update(exists, key, obj)
    else:
        return False;

In this case, “updates” where the key is not found should be considered a failure, as this is a failure in the operation on the type rather than a semantic thing in the language VM, albeit the same behaviour we would expect [from the language]. One thing I should make a callout to here as well is that there are no language semantics within Tyger to facilitate updates, however I figured I should implement it in preparation of that eventual feature. The same holds true for deletion of objects from the map, i.e. no language level support for it (and this doesn’t happen during garbage collection as there is none), but implementing this now will be useful later (even if I plan to refactor this all anyway).

The only other operation I think which is interesting to cover is retrieving (“getting”) values from the map:

Retrieving a value from the map is simple, again:

def env_do_get(var: *TyEnv_Var, key: str) -> *TyEnv_Var:
    if var.key == key:
        return var
    else:
        if var.next:
            return env_do_get(var.next, key)
        else:
            return nil

def env_get(env: *TyEnv, key: str) -> *TyEnv_Var:
    key_hash: u32 = fnv1a(key) % env.capacity
    exists: *TyEnv_Var = nil
    if env.elems[key_hash].key:
        if key == env.elems[key_hash].key:
            exists = env.elems[key_hash]
        else:
            exists = env_do_get(env.elems[key_hash], key)
        return exists
    else:
        return exists

1. generate the hash
2. check if the var exists in any of the slots
3. if so return
4. else, recursively call do_get until either the code reaches the end of the linked list, or finds a matching key

In this case, our “invalid” lookup case returns a null pointer, as this is simple to check for, and given how much weird out-parameter stuff I’ve already had to do in this project, I would rather reframe from returning a success parameter - and correctly overwriting the out parameter - and take the “risk” of null pointer dereference (which will at least crash my program, is obvious, and will not potentially yield weird, alternative errors later)².

Deleting values is a little more tricky as, like insertions, I decided to make it require 2 distinct code paths to implement, depending on whether the key occupies a slot, or is in the linked list, and also some careful re-jigging of the next node pointers needs to be performed.

def env_do_delete(var: *TyEnv_Var, key: str) -> bool:
    next_node: *TyEnv_Var = nil
    if var.key == key:
        next_node = var.next
        tyenv_var_delete(var)
        if next_node:
            var = next_node
        return True
    else:
        if var.next:
            return env_do_delete(var.next, key)
        else:
            return False

def env_delete(env: *TyEnv, key: str) -> bool:
    key_hash: u32 = fnv1a(key) % env.capacity
    exists: *TyEnv_Var = env_get(env, key)
    if exists:
        if exists.key == key:
            next_node: *TyEnv_Var = exists.next
            # NOTE: assume this function exists and will handle all cleanup "in place"
            tyenv_var_inplace_delete(exists)
            if next_node:
                exists = next_node
            return True
        else:
            return env_do_delete(exists, key)
    else:
        return False

In essence, if we need to delete a node which contains a next pointer, then we need to take the reference to this, delete the current object (TyEnv_Var), then reassign the current instance to point to the previous reference; obviously if next was null then no update needs to happen.

Evaluation And Object Creation

Firstly let’s cover evaluation of expressions. The previous installment in the series covered the creation of the AST, so you should hopefully remember that expressions are simply things which produce values; whilst there are several types of expression I will zoom in on the 2 easiest to process, which are literals. As shown earlier there are 2 builtin types currently supported, those being integers and strings.

How Eval Works

Before we touch that, I should state that the API for interfacing with the actual evaluation engine in the VM is defined as a single function:

TyObj eval(TyEnv *global_env, const Program *prog);

A single function, which will always yield some kind of object (even if its type is NONE, i.e. not an object). Currently there is a question over whether I should return a pointer to the object, rather than dereference it within eval, if I change my opinion here - which is not strongly held, or informed - then I will write some notes on why. This however, isn’t the main workhorse, this immediately calls another function which will iterate over all statements in the parsed program and repeatedly calls another eval function on each:

static TyObj *eval_program_statements(TyEnv *env, const Program *prog)
{
  TyObj *res = NULL;

  for (size_t i = 0; i < prog->statements.len; ++i)
  {
    const Statement *stmt = &(prog->statements.elems[i]);
    const Parser_Context *ctx = &(prog->context);
    res = eval_statement(env, stmt, ctx);
  }

  return res;
}

As mentioned, there are only 2 statements, those being var and expression; we will focus first on evaluating expressions (since this is the part which I think is coolest as we actually get to see things happen).

Expression Evaluation

All expression evaluation starts first, by retrieving a pointer to the expression we want to evaluate, by converting a handle (see the previous entry to refresh why this is needed):

static TyObj *eval_expression_statement(TyEnv *env, Expression_Handle handle, const Parser_Context *ctx)
{
  TyObj *res;
  const Expression *expr = &(ctx->expressions.elems[handle]);
  res = eval_expression(env, expr, ctx);
  return res;
}

Integer Evaluation

Within eval_expression, the relevant function is called depending on the type of expression parsed; for our first check we’ll look at integers (EXPR_INT):

static TyObj *eval_int(const Int_Expression *expr)
{
  TyObj *res = tyobj_new(TYOBJ_INT, (void*) &expr->value);
  return res;
}

This is quite simple, a call to tyobj_new is made where we specify that we’re constructing an integer, and just pass the underlying value straight from the AST.

String Evaluation

Strings are a little more involved in the requisite code:

static TyObj *eval_string(const String_Expression *expr, const Parser_Context *ctx)
{
  char *buffer = malloc(sizeof(char) * (expr->len + 1));
  assert(buffer && "failed to malloc string memory");

  const char *string = &(ctx->strings.elems[expr->string_handle]);
  strncpy(buffer, string, expr->len);
  buffer[expr->len] = '\0';

  TyObj *res = malloc(sizeof(TyObj));
  assert(res && "failed to allocate space for [TyObj::String]");
  res->kind = TYOBJ_STRING;
  res->o.string = (TyString) {
    .value = buffer,
    .len = expr->len,
  };

  return res;
}

You will notice my flagrant disregard for my own new/delete functions here; I honestly don’t know why it was implemented this way, and is on the list of things to be fixed in a cleanup pass after this entry in the series. To summarise, I think that I need to utilise some “string view” type (as I have already defined) to pass in as the datum argument to tyobj_new, which can then perform the allocation, and copy from a defined, sized string.

Evaluating Infix Expressions

With these basics covered, what we could consider “leaves” to our interpreter (because they are terminal points, i.e. no further evaluation can be done), we can move to evaluating infix epxressions (and hopefully make the mind-melting data processing in recursive descent parsing worth it!) All calls to eval_infix perform indirect recursion as they themselves call eval_expression on the left, and right hand side of tree, which may call eval_infix and repeat arbitrarily many times:

static TyObj *eval_infix(TyEnv *env, const Infix_Expression *expr, const Parser_Context *ctx)
{
  TyObj *res = NULL;

  const Expression *lhs = &(ctx->expressions.elems[expr->lhs]);
  const Expression *rhs = &(ctx->expressions.elems[expr->rhs]);

  TyObj *lhs_res = eval_expression(env, lhs, ctx);
  TyObj *rhs_res = eval_expression(env, rhs, ctx);
  assert(eval__do_op(&res, expr->op, lhs_res, rhs_res));

  return res;
}

So eventually the left, and right hand sides will reach some “leaf” node, and terminate (i.e. they will encounter a string or a integer), and subsequently this will return up the call stack. Take for example, 1 + 2 - the left hand side of this evaluates to 1, and the right to 2, subsequently the add opp is performed on these 2 operands (and will eventually yield 3). This will also correctly handle more complex expressions such as 1 + 2 + 3 (a very simple but illustrative example) as:

1. the following sub-expressions are defined
   1. left hand side: 1 + 2
   2. right hand side: $LHS + 3
2. the left hand side is evaluated first:
   1. this calls eval_expression and encounters an infix
   2. the LHS and RHS are both integers
   3. after evaluation these are passed to the op function
   4. the 2 values are summed to 3 and this new object is returned
3. the right hand side is then evaluated
   1. since this is an integer only this will be returned
4. another call to do_op is performed on the result of left hand side evaluation and the right hand side
5. a new object with integer value 6 is generated
6. this is returned, evaluation has finished

Now I know I mentioned not wanting to deal with out parameters earlier, this however seems like a better option for handling operator evaluation since I have to allocate a new object somewhere anywhere, and rather than require all do_op functions have to allocate an object, I decided it would be better to allocate once and pass this to be later modified. Again, string concatenation isn’t supported and the only other type, integers, are stored “inplace” in the object, so I can just update these values later. This may change again once I start implementing garbage collection, and add other types, as my hacky work around may no longer be applicable.

Speaking of how operators are handled:

static int eval__do_op(TyObj **out, Operator op, const TyObj *lhs, const TyObj *rhs)
{
  int success = 0;

  (*out) = tyobj_new(TYOBJ_NONE, NULL);
  assert((*out) && "failed to create new object");

  if (lhs->kind == rhs->kind)
  {
    switch (op)
    {
    case OP_PLUS:     { success = eval__do_add((*out), lhs, rhs); } break;
    case OP_MINUS:    { success = eval__do_sub((*out), lhs, rhs); } break;
    case OP_ASTERISK: { success = eval__do_mul((*out), lhs, rhs); } break;
    case OP_SLASH:    { success = eval__do_div((*out), lhs, rhs); } break;
    default: { assert(0 && "unreachable"); }
    }
  }
  else
  {
    return success;
  }
  return success;
}

This VM requires that in all cases, the types of each operand must match, i.e. if one operand is an integer, both must be integers - this is subject to change as logic requirements become more complex, but this is serviceable for now. Each supported operator calls an interpreter specific function to perform the neccessary logic; one thing should be noted which is arithmetic operator calls on non-integer types will yield an error (i.e. there is no string concatenation for "foo" + "|" + "bar").

NOTE: The gif shows the evaluation result is 7, rather than 6.2, this is because the language only supportes integer division; this is the way Python 2 worked, and will be changed once support for floats is added (where the result of integer division will be a float if there is a modulo is non-zero)

Call Expressions

I will lead by noting that my implementation is the most scuffed one could make it for such a simple case, and will need revisiting as soon as I expand call expression support beyond the builtin println:

static void eval_function_builtin(TyEnv *env, const Argument_List *args, const Parser_Context *ctx)
{
  // NOTE(HS): all println handling
  {
    TyObj *evaluated_args = malloc(sizeof(TyObj) * args->len);
    for (size_t i = 0; i < args->len; ++i)
    {
      const Expression *expr = &(args->elems[i]);
      TyObj *o = eval_expression(env, expr, ctx);
      memcpy(&(evaluated_args[i]), o, sizeof(TyObj));
    }

    for (size_t i = 0; i < args->len; ++i)
    {
      TyObj *obj = &(evaluated_args[i]);
      switch (obj->kind)
      {
      case TYOBJ_INT: { printf("%" PRIi64 "", obj->o.integer.value); } break;
      case TYOBJ_STRING: { printf("%s", obj->o.string.value); } break;
      case TYOBJ_NONE: { printf("<NONE>"); } break;
      }
      tyobj_delete(obj);
      if (i + 1 < args->len) { printf(", "); }
    }
    free(evaluated_args);
    printf("\n");
  }
}

static TyObj *eval_call_expression(TyEnv *env, const Call_Expression *expr, const Parser_Context *ctx)
{
  TyObj *res = tyobj_new(TYOBJ_NONE, NULL);

  const Expression *function = &(ctx->expressions.elems[expr->function]);
  assert(function->kind == EXPR_IDENT);
  const Ident_Expression *ie = &(function->expression.ident_expression);
  const char *ident = &(ctx->evaluated_identifiers.elems[ie->ident_handle]);

  assert(compare_function_names_eq("println", ident));
  eval_function_builtin(env, &expr->args, ctx);

  return res;
}

Println is analagous to the print function from Python except I do not allow things like overriding the line ending (so you only get newline termination).

How this works is the current function is checked to be println (and if not, the interpreter crashes - elegantly… not!), then call eval_function_builtin on the function, which:

1. preallocates a buffer of objects which hold the evaluation result of each arg the function is called with
2. loop over all the args the function was called with
3. evaluate each argument, and copy the resultant object into the buffer
4. loop over the buffer of objects
5. serialise the object to a string
6. print the string, then print a comma (assuming the arg was not the last one)
7. delete the object from the buffer
8. free the buffer
9. print the final newline

I’ve separated builtins out for now, as these are things which are builtin to the interpreter and require some different handling compared to a user defined function.

Among the obvious (like the very much hard coded to only support println) that I could improve on, I think that:

• I need to find some alternative way of handling object evaluation for each arg
  • I don’t like the preallocation of some object buffer which then has separate tyobj_delete calls for each entry in the buffer
  • I’m sure something else must be better - maybe a candidate for object pooling where some permanent set of objects is always present to be overridden
  • only problem there is a related clear function probably needs to exist to ensure no leaks
• create an object to_string function to handle to serialisation of strings to be printed
• it would be nice to serialise 1 string, then print rather than printf each arg and delimiter
  • could be a case for my string_builder from the parer trace code

With that point about leaking, it is worth noting that this current implementation leaks anyway, as the call to tyobj_new calls malloc and is not freed; see, it gets hard to manage the lifetime soup beyond the basics (there’s even a leak present in expression evaluation)!

I guess now would also be a good time to clarify that the convention I will work with with respect to order of argument evaluation, if it wasn’t apparent from the code this is left to right, i.e. if you pass 5 args to a function, arg 1 (index 0) will always be evaluated first, then 2, 3, 4, and finally 5.

Wiring It All Together

Now we’ve covered most of what’s important, so the only thing is to “complete” the program and get this all working as part of the interpreter REPL so I can start “using” it. Fortunately, like pretty much all operations involved in extending the REPL it’s a fairly small change:

void repl_run(void)
{
  TyEnv global;
  tyenv_init(&global, 16);

  while (true)
  {
    // ...
    Program program = parser_parse_program(&parser);
    TyObj res = eval(&global, &program);
    tyobj_inspect(&res);
    // ...
  }

  tyenv_free(&global);
}

Improvements And Next Steps

I’ve not quite finished even this “first pass”, and there’s a lot more that needs doing before I’m comfortable with “finishing” this project; in no particular order here’s a list of improvements and next steps in the project.

Refactor My Hash Map Implementation

As noted¹, I am not happy with my current implementation, however I think that I can refactor this to be significantly better, and more feature complete now I’ve walked through what the actual algorithms for each operation should look like. One thing for example, that wasn’t any good was my deletion code. I attempted to be “lazy” and only implement only a single memory free path, rather than do as I did for insertion. This ended up biting me on my initial attempt as I passed stack memory to the nested free call and this blew up my program in a very non-helpful way.

Refactor Tagged Union Member

There are a few differet ways the union member of the project’s tagged unions are labelled, and I think from a semantic view this could be improved across the code base; the improvement is to renanme things according to the “as pattern” (for lack of a better description). This “pattern” is just a naming convention for naming the union member of a tagged union such that the code reads <tagged union>.as.<unioned type>, for example, the TyObj would look like:

typedef struct tyobj
{
  TyObj_Kind kind;
  union {
    TyInteger integer;
    TyString  string;
  } as;
} TyObj

In this case all usage of this in code will look something like:

TyObj *obj = env_get(env, "foo");
switch (obj->kind)
{
  // ...
  case TYOBJ_INT:
  {
    printf("object is integer with value " PRIi64 "\n", obj->as.integer);
  } break;
  // ...
}

I personally think this is a nicer, and clearer way of semantically describing what is being done in code; I took advice for this after reading through this Git repo and seeing the naming scheme implemented.

Actual Error Handling

Now whilst I don’t have plans for language level ways of handling errors, what I want is to actually implement a good system for reporting errors, both those generated from parsing, and also those which arise from runtime errors. The infrastructure is mostly there, I just need to actually do something with it.

One big thing that would be an improvement is to actually use the location struct generated from lexing, and include this in all parser node info, then print out debug info like the “file” (which will be more useful once this evolves beyond a REPL), the line, and column position of the error. For example, assume the following:

var x = 10 + "foo";

I would expect that the error states something about invalid operands to call to + operator, then tell me the fact the types are mismatched, what the types of each operand are, and the solution (in this case, arithmetic operators can only be called on 2 numeric types).

Something like the following:

NULL:1 TypeError: mismatched types of operands for operator(+)
    var x = 10 + "foo";
    10: integer
    "foo": string
    operator(+): strings cannot be concatenated to integers
    Remedy: both operands must be of the same type

And more aspirational:

NULL:1 TypeError: mismatched types of operands for operator(+)
var x = 10 + "foo"
        ^  ^ ^
        |  | |_ type: string
        |  |
        |  |_ operator: +
        |
        |_ type: integer
    
    Cannot apply operator(+) to operands <integer> and <string>.
    Both operands must be of the same type.

More General Evaluation of Call Expressions

I wonder what a better way of handling functions would be; I have been playing with the idea of creating some wrapper function for environments, which would set up the gloval environment, then register the builtin functions to said environment. This means that if I decide to reimplement environments such that reinserting an existing key fails, then I can also prevent users from overriding these functions (and I that if I make the “global”, then these will be available from all function and other scopes).

Richer Built-In Types And More Language Constructs

So far there are 2 builtin types, string and integer, and only 2 statement types;

The set of additional types I want to add support for include:

• floating point numbers (like integers I will probably only provide _double_s)
• nil type - i.e. null pointers (they’re just useful)
• functions - i.e. user defined functions
• booleans

Additional language constructs:

• return statements - return a value, when done at “top level” then this should exit the program
• if/else control flow
• loops - for and while
• boolean logic
• prefix operators (! and -)
• improved type operations
  • I think that a + b should be successful where a & b are numbers (int or float)
  • I think that a + b should be successful where a & b are strings

This should make the langauge much more useful, and, for the most part, consist of adding a few extra cases in most places in the interpreter.

VM & Garbage Collection

So I should probably actually create some concept of a VM where all state for the interpreter can be stored, and also I need to get to working on garbage collection, and more generally clean up the various memory leak issues (besides the intended ones). I think I’ll implement the mark and sweep algorithm, mainly as this will take care of circular references (which are a problem in simpler reference counting methods).

Evaluation of Files

As it stands, the language and project are REPL only, and don’t support user ability to run files; support for this will be relatively trivial to implement but I left it as the REPL is a good enough general solution, and allows for quick testing of new features.

General Asides

Some general points which don’t fit well elsewhere, but I think are worth calling out.

Discovering Old Bugs: Why Tooling Matters

I found a very fun bug in my parsing whilst playing around with my interpreter, namely that the following statement would always evaluate (“successfully”) to 1, rather than the expected 2:

var x = 1 + 1;

As it turns out there was a bug in my parsing code, specifically the order in which I get a new expression handle to copy the parsed epxressions into after parsing the value being assigned in a var statement:

Tyger_Error parse_var_statement(Parser *p, Parser_Context *ctx, Statement *stmt)
{
  //..
  parser_next_token(p);

  Expression_Handle expression_handle = va_array_next_handle(ctx->expressions);
  Expression expr;
  err = parse_expression(p, ctx, &expr, PRECIDENCE_LOWEST);
  if (err.kind != TYERR_NONE)
  {
    return err;
  }

  va_array_append(ctx->expressions, expr);
  // ...
}

The fix for this was as simple as moving the call to va_array_next_handle to just before the call to append. Simply this is because the va_array_next_handle macro doesn’t increment the length of the array, because of this, the handle I “generated” was overriden during the subsequent call to parse_expression.

This should serve as a good demonstration as to why, even with well thought out tests, onse should engage in as much exploratory testing of a system as possible, simply because you have almost certainly missed stuff. It should also be worth reiterating that you should never assume your code is correct just because the tests are all green - this should increase your confidence, but don’t let it blind you. It’s also a good idea to have some form of immediate, more easily digestable form of feedback whenever you’re doing testing, it would have been alot of work stepping over, and re-stepping over many lines of code in the debugger if I didn’t have my “trace” system for parse trees as previously implemented. Yes I could have spotted this in the debugger, but since the “trace” module just shows you the parsed AST this helped narrow down that it was a problem in how expressions were parsed, and probably confined to var statement parsing (as things like this in lone infix expression tests were correct, and also 1 + 1 on its own just worked in the REPL).

There are new tests in the parser which cover this case, at least to a basic level, now so this shouldn’t rear its head again (and will be caught if it ever does).

GTest Fixtures - Actually Really Useful

I don’t know why I haven’t been using these the whole time! Seriously, these are a useful construct within the test framework and I don’t know why I didn’t start using them, especially during my parser tests. One of the many things I did, which may not be the best use, is just to set up some protected members within the class, and some util methods for setting up a new program to evaluate, and all the other associated boilerplate; also a few associated helper methods for running some assertions.

This is the loose scaffold of what I came up with:

class TestEval : public ::testing::Test
{
protected:
  Lexer l;
  Parser parser;
  Program prog;
  TyEnv env;

  void setup_test(const char *input)
  {
    lexer_init(&this->l, input);
    parser_init(&this->parser, &this->l);
    this->prog = parser_parse_program(&this->parser);
    tyenv_init(&this->env, 16);
  }

  void teardown_test()
  {
    program_free(&this->prog);
    tyenv_free(&this->env);
  }

  // ...
};

tests/test_eval.cpp

To utilise these effectively, I would recommend checking out the docs, but to summarise you need to extend the GTest testing::Test class, then create whatever shared data/methods you want. My implementation makes it very simple to run a series of tests without needing to do all the setup and teardown code shown here:

TEST_F(TestEval, Test_Eval_Int_Expression)
{
  // ... setting up test cases
  for (auto& tc : test_cases)
  {
    setup_test(tc.input);
    DEFER({ teardown_test(); });
    TyObj act = eval(&this->env, &this->prog);
    assert_object_value_eq(act, tc.exp);
  }
}

Much cleaner, and I only need to implement the same code once, I may have to go refactor my parser tests to do something similar now I’ve had a chance to experiment.

Test Your Data Structures/Algorithms

I mentioned that I build the hash map twice; the first time was a disaster as my tests for it were all done at the language level, rather than being sensible and writing separate tests for the map. The first attempt was essentially vibe coded without the AI - so maybe that’s where I went wrong! - but really, I think this has been a lesson in how to actually develop things like this, i.e. data structures; I “understood” how hash maps worked in theory, but clearly I either didn’t or didn’t translate that well to the inital code. Anyway, even though I’ll be refactoring again, the current code at least works, and isn’t nightmarish to integrate.

The Curse Of Your Prior Self

Yourself 2 weeks ago really isn’t a bad guy, even though he seems it when you’re dealing with his code and terrible decisions. Once again, as mentioned in the previous post, try not to leave projects to rot, it’s more painful to come back and pick it up even if it’s painful in the now. Also I have come to appreciate a take I’ve seen echoed by a few people, just don’t leave todos in your code (there is a great irony in this project here but bear with me), normally it’s something simple and you’re just being lazy, and also future you probably won’t know what you meant. He may gleam it, but he may also fail, either way it’s a lot of work and you’re probably in a better position to take 10 minutes to deal with it than he is.

The example I will raise from my “finishing” this project is just issue #11, where simply I stumbled across an old commend in my handle converter functions stating

// TODO(HS): need to update functions here to accept the raw dynamic array which
// can then be operated on (otherwise we get problems).

I have no idea what I was thinking here, I think I meant that I should just accept the minimum possible amount of data to work on, so as to minimise potential side effects, but like I say this is past me communicating something he actually knew with no real context because “I’m sure he’ll understand”. We do complain about third party code in programming, but unfortunately the worst provider of third party code is your past self, because he never suspects you will not just know what he meant.

Epilogue

That’s it, the base of the interpreter is done, we can actually evaluate (basic) programs! I’m reasonably happy so far with this, but a lot more work is required. I’ll be posting less frequent updates, mainly covering things as I actually implement stuff I think is worth covering, such as garbage collection, or control flow (particularly loops as this might be worth showing).

But until then I hope you’ve enjoyed reading this, and maybe this has helped inspire your own journey. You can check out the repo as it stands at time of writing here, download it, build and try it out, and remember to have fun!