Stork, Part 4: Implementing Statements and Wrapping Up

In our quest to create a lightweight programming language using C++, we started by creating our tokenizer three weeks ago, and then we implemented the expression evaluation in the following two weeks.

Now, it is time to wrap up and deliver a complete programming language that will not be as powerful as a mature programming language but will have all the necessary features, including a very small footprint.

I find it funny how new companies have FAQ sections on their websites that do not answer questions that are asked frequently but questions that they want to be asked. I will do the same here. People following my work often ask me why Stork doesn’t compile to some bytecode or at least some intermediate language.

Why Doesn’t Stork Compile to Bytecode?

I am happy to answer this question. My goal was to develop a small-footprint scripting language that will easily integrate with C++. I don’t have a strict definition of “small-footprint,” but I imagine a compiler that will be small enough to enable portability to less powerful devices and will not consume too much memory when run.

I didn’t focus on speed, as I think that you will code in C++ if you have a time-critical task, but if you need some kind of extensibility, then a language like Stork could be useful.

I don’t claim that there are no other, better languages that can accomplish a similar task (for example, Lua). It would be truly tragic if they didn’t exist, and I am merely giving you an idea of this language’s use case.

Since it will be embedded into C++, I find it handy to use some existing features of C++ instead of writing an entire ecosystem that will serve a similar purpose. Not only that, but I also find this approach more interesting.

As always, you can find the full source code on my GitHub page. Now, let’s take a closer look at our progress.

Changes

Up to this part, Stork was a partially complete product, so I wasn’t able to see all of its drawbacks and flaws. However, as it took a more complete shape, I changed the following things introduced in previous parts:

• Functions are not variables anymore. There is a separate function_lookup in compiler_context now. function_param_lookup is renamed to param_lookup to avoid confusion.
• I changed the way that functions are called. There is the call method in runtime_context that takes std::vector of arguments, stores old return value index, pushes arguments onto the stack, changes return value index, calls the function, pops arguments from the stack, restores old return value index, and returns the result. That way, we don’t have to keep the stack of return value indices, as before, because the C++ stack serves that purpose.
• RAII classes added in compiler_context that are returned by calls to its member functions scope and function. Each of those objects creates new local_identifier_lookup and param_identifier_lookup, respectively, in their constructors and restores the old state in the destructor.
• An RAII class added in runtime_context, returned by the member function get_scope. That function stores the stack size in its constructor and restores it in its destructor.
• I removed the const keyword and constant objects in general. They could be useful but aren’t absolutely necessary.
• var keyword removed, as it is currently not needed at all.
• I added sizeof keyword, which will check an array size in runtime. Maybe some C++ programmers will find the name choice blasphemous, as C++ sizeof runs in compile time, but I chose that keyword to avoid collision with some common variable name - for example, size.
• I added tostring keyword, which explicitly converts anything to string. It cannot be a function, as we don’t allow function overloading.
• Various less interesting changes.

Syntax

Since we are using syntax very similar to C and its related programming languages, I will give you just the details that may not be clear.

Variable type declarations are as follows:

• void, used only for the function return type
• number
• string
• T[] is an array of what holds elements of type T
• R(P1,...,Pn) is a function that returns type R and receives arguments of types P1 to Pn. Each of those types can be prefixed with & if it is passed by reference.

Function declaration is as follows: [public] function R name(P1 p1, … Pn pn)

So, it has to be prefixed with function. If it is prefixed with public, then it can be called from C++. If the function doesn’t return the value, it will evaluate to the default value of its return type.

We allow for-loop with a declaration in the first expression. We also allow if-statement and switch-statement with an initialization expression, as in C++17. The if-statement starts with an if-block, followed by zero or more elif-blocks, and optionally, one else-block. If the variable was declared in the initialization expression of the if-statement, it would be visible in each of those blocks.

We allow an optional number after a break statement that can break from multiple nested loops. So you can have the following code:

for (number i = 0; i < 100; ++i) {
  for(number j = 0; j < 100; ++j) {
    if (rnd(100) == 0) {
      break 2;
    }
  }
}

Also, it will break from both loops. That number is validated in compile time. How cool is that?

Compiler

Many features were added in this part, but if I get too detailed, I will probably lose even the most persistent readers who are still bearing with me. Therefore, I will intentionally skip one very big part of the story - compilation.

That is because I already described it in the first and second parts of this blog series. I was focusing on expressions, but compiling anything else is not much different.

I will, however, give you one example. This code compiles while statements:

statement_ptr compile_while_statement(
  compiler_context& ctx, tokens_iterator& it, possible_flow pf
)
{
  parse_token_value(ctx, it, reserved_token::kw_while);
  parse_token_value(ctx, it, reserved_token::open_round);
  expression<number>::ptr expr = build_number_expression(ctx, it);
  parse_token_value(ctx, it, reserved_token::close_round);

  block_statement_ptr block = compile_block_statement(ctx, it, pf);

  return create_while_statement(std::move(expr), std::move(block));
}

As you can see, it is far from complicated. It parses while, then (, then it builds a number expression (we don’t have booleans), and then it parses ).

After that, it compiles a block statement that may be inside { and } or not (yes, I allowed single-statement blocks) and it creates a while statement in the end.

You are already familiar with the first two function arguments. The third one, possible_flow, shows the permitted flow-changing commands (continue, break, return) in the context that we are parsing. I could keep that information in the object if the compilation statements were member functions of some compiler class, but I am not a big fan of mammoth classes, and the compiler would definitely be one such class. Passing an extra argument, especially a thin one, will not hurt anyone, and who knows, maybe one day we will be able to parallelize the code.

There is another interesting aspect of the compilation that I would like to explain here.

If we want to support a scenario where two functions are calling each other, we can do it the C-way: by allowing forward declaration or having two compilation phases.

I chose the second approach. When the function definition is found, we will parse its type and name into the object named incomplete_function. Then, we will skip its body, without an interpretation, by simply counting the nesting level of curly braces until we close the first curly brace. We will collect tokens in the process, keep them in incomplete_function, and add a function identifier into compiler_context.

Once we pass the entire file, we will compile each of the functions completely, so that they can be called in the runtime. That way, each function can call any other function in the file and can access any global variable.

Global variables can be initialized by calls to the same functions, which leads us immediately to the old “chicken and egg” problem as soon as those functions access uninitialized variables.

Should that ever happen, the issue is solved by throwing a runtime_exception—and that’s only because I am nice. Franky, access violation is the least you can get as a punishment for writing such code.

The Global Scope

There are two kinds of entities that can appear in the global scope:

• Global variables
• Functions

Each global variable can be initialized with an expression that returns the correct type. The initializer is created for each global variable.

Each initializer returns lvalue, so they serve as global variables’ constructors. When no expression is provided for a global variable, the default initializer is constructed.

This is the initialize member function in runtime_context:

void runtime_context::initialize() {
  _globals.clear();

  for (const auto& initializer : _initializers) {
    _globals.emplace_back(initializer->evaluate(*this));
  }
}

It is called from the constructor. It clears the global variable container, as it can be called explicitly, to reset the runtime_context state.

As I mentioned earlier, we need to check if we access an uninitialized global variable. Therefore, this is the global variable accessor:

variable_ptr& runtime_context::global(int idx) {
  runtime_assertion(
    idx < _globals.size(),
    "Uninitialized global variable access"
  );
  return _globals[idx];
}

If the first argument evaluates to false, runtime_assertion throws a runtime_error with the corresponding message.

Each function is implemented as lambda that captures the single statement, which is then evaluated with the runtime_context that the function receives.

Function Scope

As you could see from the while-statement compilation, the compiler is called recursively, starting with the block statement, which represents the block of the entire function.

Here is the abstract base class for all the statements:

class statement {
  statement(const statement&) = delete;
  void operator=(const statement&) = delete;
protected:
  statement() = default;
public:
  virtual flow execute(runtime_context& context) = 0;
  virtual ~statement() = default;
};

The only function apart from the default ones is execute, which performs the statement logic on runtime_context and returns the flow, which determines where the program logic will go next.

enum struct flow_type{
  f_normal,
  f_break,
  f_continue,
  f_return,
};

class flow {
private:
  flow_type _type;
  int _break_level;
  flow(flow_type type, int break_level);
public:
  flow_type type() const;
  int break_level() const;

  static flow normal_flow();
  static flow break_flow(int break_level);
  static flow continue_flow();
  static flow return_flow();
  flow consume_break();
};

Static creator functions are self-explanatory, and I wrote them to prevent illogical flow with non-zero break_level and the type different from flow_type::f_break.

Now, consume_break will create a break flow with one less break level or, if the break level reaches zero, the normal flow.

Now, we will check all statement types:

class simple_statement: public statement {
private:
  expression<void>::ptr _expr;
public:
    simple_statement(expression<void>::ptr expr):
      _expr(std::move(expr))
    {
    }

    flow execute(runtime_context& context) override {
      _expr->evaluate(context);
      return flow::normal_flow();
    }
};

Here, simple_statement is the statement that is created from an expression. Every expression can be compiled as an expression that returns void, so that simple_statement can be created from it. As neither break nor continue or return can be a part of an expression, simple_statement returns flow::normal_flow().

class block_statement: public statement {
private:
  std::vector<statement_ptr> _statements;
public:
  block_statement(std::vector<statement_ptr> statements):
    _statements(std::move(statements))
  {
  }

  flow execute(runtime_context& context) override {
    auto _ = context.enter_scope();
    for (const statement_ptr& statement : _statements) {
      if (
        flow f = statement->execute(context);
        f.type() != flow_type::f_normal
      ){
        return f;
      }
    }
    return flow::normal_flow();
  }
};

The block_statement keeps the std::vector of statements. It executes them, one by one. If each of them returns non-normal flow, it returns that flow immediately. It uses a RAII scope object to allow local scope variable declarations.

class local_declaration_statement: public statement {
private:
  std::vector<expression<lvalue>::ptr> _decls;
public:
  local_declaration_statement(std::vector<expression<lvalue>::ptr> decls):
    _decls(std::move(decls))
  {
  }

  flow execute(runtime_context& context) override {
    for (const expression<lvalue>::ptr& decl : _decls) {
      context.push(decl->evaluate(context));
    }
    return flow::normal_flow();
  }
};

local_declaration_statement evaluates the expression that creates a local variable and pushes the new local variable onto the stack.

class break_statement: public statement {
private:
  int _break_level;
public:
  break_statement(int break_level):
    _break_level(break_level)
  {
  }

  flow execute(runtime_context&) override {
    return flow::break_flow(_break_level);
  }
};

break_statement has the break level evaluated in the compile time. It just returns the flow that corresponds to that break level.

class continue_statement: public statement {
public:
  continue_statement() = default;

  flow execute(runtime_context&) override {
    return flow::continue_flow();
  }
};

continue_statement just returns flow::continue_flow().

class return_statement: public statement {
private:
  expression<lvalue>::ptr _expr;
public:
  return_statement(expression<lvalue>::ptr expr) :
    _expr(std::move(expr))
  {
  }

  flow execute(runtime_context& context) override {
    context.retval() = _expr->evaluate(context);
    return flow::return_flow();
  }
};

class return_void_statement: public statement {
public:
  return_void_statement() = default;

  flow execute(runtime_context&) override {
    return flow::return_flow();
  }
};

return_statement and return_void_statement both return flow::return_flow(). The only difference is that the former has the expression that it evaluates to the return value before it returns.

class if_statement: public statement {
private:
  std::vector<expression<number>::ptr> _exprs;
  std::vector<statement_ptr> _statements;
public:
  if_statement(
    std::vector<expression<number>::ptr> exprs,
    std::vector<statement_ptr> statements
  ):
    _exprs(std::move(exprs)),
    _statements(std::move(statements))
  {
  }

  flow execute(runtime_context& context) override {
    for (size_t i = 0; i < _exprs.size(); ++i) {
      if (_exprs[i]->evaluate(context)) {
        return _statements[i]->execute(context);
      }
    }
    return _statements.back()->execute(context);
  }
};

class if_declare_statement: public if_statement {
private:
  std::vector<expression<lvalue>::ptr> _decls;
public:
  if_declare_statement(
    std::vector<expression<lvalue>::ptr> decls,
    std::vector<expression<number>::ptr> exprs,
    std::vector<statement_ptr> statements
  ):
    if_statement(std::move(exprs), std::move(statements)),
    _decls(std::move(decls))
  {
  }

  flow execute(runtime_context& context) override {
    auto _ = context.enter_scope();
    
    for (const expression<lvalue>::ptr& decl : _decls) {
      context.push(decl->evaluate(context));
    }
    
    return if_statement::execute(context);
  }
};

if_statement, which is created for one if-block, zero or more elif-blocks, and one else-block (which could be empty), evaluates each of its expressions until one expression evaluates to 1. It then executes that block and returns the execution result. If no expression evaluates to 1, it will return the execution of the last (else) block.

if_declare_statement is the statement that has declarations as the first part of an if-clause. It pushes all declared variables onto the stack and then executes its base class (if_statement).

class switch_statement: public statement {
private:
  expression<number>::ptr _expr;
  std::vector<statement_ptr> _statements;
  std::unordered_map<number, size_t> _cases;
  size_t _dflt;
public:
  switch_statement(
    expression<number>::ptr expr,
    std::vector<statement_ptr> statements,
    std::unordered_map<number, size_t> cases,
    size_t dflt
  ):
    _expr(std::move(expr)),
    _statements(std::move(statements)),
    _cases(std::move(cases)),
    _dflt(dflt)
  {
  }

  flow execute(runtime_context& context) override {
    auto it = _cases.find(_expr->evaluate(context));
    for (
      size_t idx = (it == _cases.end() ? _dflt : it->second);
      idx < _statements.size();
      ++idx
    ) {
      switch (flow f = _statements[idx]->execute(context); f.type()) {
        case flow_type::f_normal:
          break;
        case flow_type::f_break:
          return f.consume_break();
        default:
          return f;
      }
    }
    
    return flow::normal_flow();
  }
};

class switch_declare_statement: public switch_statement {
private:
  std::vector<expression<lvalue>::ptr> _decls;
public:
  switch_declare_statement(
    std::vector<expression<lvalue>::ptr> decls,
    expression<number>::ptr expr,
    std::vector<statement_ptr> statements,
    std::unordered_map<number, size_t> cases,
    size_t dflt
  ):
    _decls(std::move(decls)),
    switch_statement(std::move(expr), std::move(statements), std::move(cases), dflt)
  {
  }

  flow execute(runtime_context& context) override {
    auto _ = context.enter_scope();

    for (const expression<lvalue>::ptr& decl : _decls) {
      context.push(decl->evaluate(context));
    }
    
    return switch_statement::execute(context);
  }
};

switch_statement executes its statements one by one, but it first jumps to the appropriate index that it gets from the expression evaluation. If any of its statements returns non-normal flow, it will return that flow immediately. If it has flow_type::f_break, it will consume one break first.

switch_declare_statement allows a declaration in its header. None of those allows a declaration in the body.

class while_statement: public statement {
private:
  expression<number>::ptr _expr;
  statement_ptr _statement;
public:
  while_statement(expression<number>::ptr expr, statement_ptr statement):
    _expr(std::move(expr)),
    _statement(std::move(statement))
  {
  }

  flow execute(runtime_context& context) override {
    while (_expr->evaluate(context)) {
      switch (flow f = _statement->execute(context); f.type()) {
        case flow_type::f_normal:
        case flow_type::f_continue:
          break;
        case flow_type::f_break:
          return f.consume_break();
        case flow_type::f_return:
          return f;
      }
    }
    
    return flow::normal_flow();
  }
};

class do_statement: public statement {
private:
  expression<number>::ptr _expr;
  statement_ptr _statement;
public:
  do_statement(expression<number>::ptr expr, statement_ptr statement):
    _expr(std::move(expr)),
    _statement(std::move(statement))
  {
  }

  flow execute(runtime_context& context) override {
    do {
      switch (flow f = _statement->execute(context); f.type()) {
        case flow_type::f_normal:
        case flow_type::f_continue:
          break;
        case flow_type::f_break:
          return f.consume_break();
        case flow_type::f_return:
          return f;
      }
    } while (_expr->evaluate(context));
    
    return flow::normal_flow();
  }
};

while_statement and do_while_statement both execute their body statement while their expression evaluates to 1. If the execution returns flow_type::f_break, they consume it and return. If it returns flow_type::f_return, they return it. In case of normal execution, or continue, they do nothing.

It may appear as if continue doesn’t have an effect. However, the inner statement was affected by it. If it was, for example, block_statement, it didn’t evaluate to the end.

I find it neat that while_statement is implemented with the C++ while, and do-statement with the C++ do-while.

class for_statement_base: public statement {
private:
  expression<number>::ptr _expr2;
  expression<void>::ptr _expr3;
  statement_ptr _statement;
public:
  for_statement_base(
    expression<number>::ptr expr2,
    expression<void>::ptr expr3,
    statement_ptr statement
  ):
    _expr2(std::move(expr2)),
    _expr3(std::move(expr3)),
    _statement(std::move(statement))
  {
  }

  flow execute(runtime_context& context) override {
    for (; _expr2->evaluate(context); _expr3->evaluate(context)) {
      switch (flow f = _statement->execute(context); f.type()) {
        case flow_type::f_normal:
        case flow_type::f_continue:
          break;
        case flow_type::f_break:
          return f.consume_break();
        case flow_type::f_return:
          return f;
      }
    }
    
    return flow::normal_flow();
  }
};

class for_statement: public for_statement_base {
private:
  expression<void>::ptr _expr1;
public:
  for_statement(
    expression<void>::ptr expr1,
    expression<number>::ptr expr2,
    expression<void>::ptr expr3,
    statement_ptr statement
  ):
    for_statement_base(
      std::move(expr2),
      std::move(expr3),
      std::move(statement)
    ),
    _expr1(std::move(expr1))
  {
  }

  flow execute(runtime_context& context) override {
    _expr1->evaluate(context);
    
    return for_statement_base::execute(context);
  }
};

class for_declare_statement: public for_statement_base {
private:
  std::vector<expression<lvalue>::ptr> _decls;
  expression<number>::ptr _expr2;
  expression<void>::ptr _expr3;
  statement_ptr _statement;
public:
  for_declare_statement(
    std::vector<expression<lvalue>::ptr> decls,
    expression<number>::ptr expr2,
    expression<void>::ptr expr3,
    statement_ptr statement
  ):
    for_statement_base(
      std::move(expr2),
      std::move(expr3),
      std::move(statement)
    ),
    _decls(std::move(decls))
  {
  }

  flow execute(runtime_context& context) override {
    auto _ = context.enter_scope();
    
    for (const expression<lvalue>::ptr& decl : _decls) {
      context.push(decl->evaluate(context));
    }
    return for_statement_base::execute(context);
  }
};

for_statement and for_statement_declare are implemented similarly as while_statement and do_statement. They are inherited from the for_statement_base class, which does most of the logic. for_statement_declare is created when the first part of the for-loop is variable declaration.

These are all statement classes that we have. They are building blocks of our functions. When runtime_context is created, it keeps those functions. If the function is declared with the keyword public, it can be called by name.

That concludes the core functionality of Stork. Everything else that I will describe are afterthoughts that I added to make our language more useful.

Tuples

Arrays are homogeneous containers, as they can contain elements of a single type only. If we want heterogeneous containers, structures immediately come to mind.

However, there are more trivial heterogeneous containers: tuples. Tuples can keep the elements of different types, but their types have to be known in compile time. This is an example of a tuple declaration in Stork:

[number, string] t = {22321, "Siveric"};

This declares the pair of number and string and initializes it.

Initialization lists can be used to initialize arrays as well. When the types of expressions in the initialization list don’t match the variable type, a compiler error will occur.

Since arrays are implemented as containers of variable_ptr, we got the runtime implementation of tuples for free. It is compile time when we assure the correct type of contained variables.

Modules

It would be nice to hide the implementation details from a Stork user and present the language in a more user-friendly way.

This is the class that will help us accomplish that. I present it without the implementation details:

class module {
  ...
public:
  template<typename R, typename... Args>
  void add_external_function(const char* name, std::function<R(Args...)> f);

  template<typename R, typename... Args>
  auto create_public_function_caller(std::string name);

  void load(const char* path);
  bool try_load(const char* path, std::ostream* err = nullptr) noexcept;

  void reset_globals();
  ...
};

The functions load and try_load will load and compile the Stork script from the given path. First, one of them can throw a stork::error, but the second one will catch it and print it on the output, if provided.

The function reset_globals will re-initialize global variables.

The functions add_external_functions and create_public_function_caller should be called before the compilation. The first one adds a C++ function that can be called from Stork. The second one creates the callable object that can be used to call the Stork function from C++. It will cause a compile-time error if the public function type doesn’t match R(Args…) during the Stork script compilation.

I added several standard functions that can be added to the Stork module.

void add_math_functions(module& m);
void add_string_functions(module& m);
void add_trace_functions(module& m);
void add_standard_functions(module& m);

Example

Here is an example of a Stork script:

function void swap(number& x, number& y) {
  number tmp = x;
  x = y;
  y = tmp;
}

function void quicksort(
  number[]& arr,
  number begin,
  number end,
  number(number, number) comp
) {
  if (end - begin < 2)
    return;

  number pivot = arr[end-1];

  number i = begin;

  for (number j = begin; j < end-1; ++j)
    if (comp(arr[j], pivot))
      swap(&arr[i++], &arr[j]);

  swap (&arr[i], &arr[end-1]);

  quicksort(&arr, begin, i, comp);
  quicksort(&arr, i+1, end, comp);
}

function void sort(number[]& arr, number(number, number) comp) {
  quicksort(&arr, 0, sizeof(arr), comp);
}


function number less(number x, number y) {
  return x < y;
}

public function void main() {
  number[] arr;

  for (number i = 0; i < 100; ++i) {
    arr[sizeof(arr)] = rnd(100);
  }

  trace(tostring(arr));

  sort(&arr, less);

  trace(tostring(arr));

  sort(&arr, greater);

  trace(tostring(arr));
}

Here is the C++ part:

#include <iostream>
#include "module.hpp"
#include "standard_functions.hpp"

int main() {
  std::string path = __FILE__;
  path = path.substr(0, path.find_last_of("/\\") + 1) + "test.stk";

  using namespace stork;

  module m;

  add_standard_functions(m);

  m.add_external_function(
    "greater",
    std::function<number(number, number)>([](number x, number y){
      return x > y;
    }
  ));

  auto s_main = m.create_public_function_caller<void>("main");

  if (m.try_load(path.c_str(), &std::cerr)) {
    s_main();
  }

  return 0;
}

Standard functions are added to the module before the compilation, and the functions trace and rnd are used from the Stork script. The function greater is also added as a showcase.

The script is loaded from the file “test.stk,” which is in the same folder as “main.cpp” (by using a __FILE__ preprocessor definition), and then the function main is called.

In the script, we generate a random array, sorting in ascending by using the comparator less, and then in descending by using the comparator greater, written in C++.

You can see that the code is perfectly readable for anyone fluent in C (or any programming language derived from C).

What to Do Next?

There are many features that I would like to implement in Stork:

• Structures
• Classes and inheritance
• Inter-module calls
• Lambda functions
• Dynamically-typed objects

Lack of time and space is one of the reasons why we don’t have them implemented already. I will try to update my GitHub page with new versions as I implement new features in my spare time.

Wrapping Up

We have created a new programming language!

That took a good part of my spare time in the past six weeks, but I can now write some scripts and see them running. It’s what I was doing in the last few days, scratching my bald head every time it crashed unexpectedly. Sometimes, it was a small bug, and sometimes a nasty bug. At other times, though, I felt embarrassed because it was about a bad decision that I had already shared with the world. But each time, I would fix and keep coding.

In the process, I learned about if constexpr, which I had never used before. I also became more familiar with rvalue-references and perfect forwarding, as well as with other smaller features of C++17 that I don’t encounter daily.

The code is not perfect—I would never make such a claim—but it is good enough, and it mostly follows good programming practices. And most importantly - it works.

Deciding to develop a new language from scratch may sound crazy to an average person, or even to an average programmer, but it’s all the more reason for doing it and proving to yourself that you can do it. Just like solving a difficult puzzle is a good brain exercise to stay mentally fit.

Dull challenges are common in our day-to-day programming, as we can’t cherry-pick only the interesting aspects of it and have to do serious work even if it is boring at times. If you are a professional developer, your first priority is to deliver high-quality code to your employer and put food on the table. This can sometimes make you avoid programming in your spare time and it can dampen the enthusiasm of your early programming school days.

If you don’t have to, don’t lose that enthusiasm. Work on something if you find it interesting, even if it is already done. You don’t have to justify the reason to have some fun.

And if you can incorporate it—even partially—in your professional work, good for you! Not many people have that opportunity.

The code for this part will be frozen with a dedicated branch on my GitHub page.