In this third installment of our series, we’ll finally reach the stage where our lightweight programming language can execute code. While it won’t achieve Turing-completeness or remarkable power, it will gain the capability to evaluate expressions and even interact with external functions written in C++.

My goal is to elaborate on this process as comprehensively as possible, not only because it aligns with the objective of this blog series, but also for my personal documentation. This aspect became particularly crucial in this part, as the complexity increased.

While I began coding for this part before publishing the second article, it became evident that the expression parser warranted a dedicated blog post due to its standalone nature.

This separation, along with the utilization of certain programming techniques that some might consider unconventional, helped prevent this part from becoming excessively lengthy. Nevertheless, it’s likely that some readers will question the rationale behind employing these techniques.

Why Employ Macros?

Throughout my programming journey, working on diverse projects and collaborating with various individuals, I’ve observed a tendency among developers to gravitate towards dogmatism—perhaps because it simplifies matters.

The first programming dogma dictates that the goto statement is inherently flawed, detrimental, and should be avoided at all costs. While I comprehend the sentiment behind this belief and concur with it in the majority of instances where goto is employed, it’s important to acknowledge that breaking out of nested loops in C++ can be effortlessly achieved using goto. The alternative, often involving a bool variable or a dedicated function, can potentially hinder readability compared to code that adheres to this dogmatic restriction.

The second dogma, particularly relevant to C and C++ developers, asserts that macros are inherently problematic, hazardous, and essentially disasters waiting to happen. This stance is often accompanied by the following illustrative example:

1
2
3
4
5

#define max(a, b) ((a) > (b) ? (a) : (b))
...
int x = 3;
int z = 2;
int y = max(x++, z);

Subsequently, the question arises: What is the value of x after executing this code snippet? The answer is 5 because x is incremented twice, once on each side of the ? operator.

The crux of the matter is that this scenario doesn’t represent a typical use case for macros. Macros become problematic when employed in situations where ordinary functions would suffice, especially if they masquerade as functions, thereby obscuring their side effects from the user. However, our utilization of macros will not mimic functions, and we will employ block letters for their names to clearly distinguish them as non-functions. While we acknowledge the drawback of limited debugging capabilities, we accept this trade-off as the alternative—copy-pasting identical code multiple times—poses a significantly higher risk of errors compared to employing macros. One potential solution would be to develop a code generator, but why reinvent the wheel when C++ already provides one?

Programming dogmas, in most cases, are counterproductive. The use of “almost” here is deliberate to avoid falling into the same dogmatic trap I’ve just highlighted.

The code and all macros for this part are accessible here.

Variables

In the previous part, I mentioned that Stork wouldn’t be compiled into traditional binary code or assembly language. However, I also stated that it would maintain static typing. Consequently, while compilation will occur, the output will be a C++ object capable of execution. This will become clearer later. For now, it’s sufficient to understand that all variables will be represented as individual objects.

To manage these objects within a global variable container or on the stack, a convenient approach is to define a base class and derive from it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class variable;
using variable_ptr = std::shared_ptr<variable>;

class variable: public std::enable_shared_from_this<variable> {
private:
  variable(const variable&) = delete;
  void operator=(const variable&) = delete;
protected:
  variable() = default;
public:
  virtual ~variable() = default;
  virtual variable_ptr clone() const = 0;

  template <typename T>
  T static_pointer_downcast() {
    return std::static_pointer_cast<
      variable_impl<typename T::element_type::value_type>
    >(shared_from_this());
  }
};

As evident, this base class is straightforward. The clone function, responsible for deep copying, represents its sole virtual member function apart from the destructor.

Since we’ll consistently interact with objects of this class through shared_ptr, inheriting from std::enable_shared_from_this makes sense, simplifying the retrieval of shared pointers. The function static_pointer_downcast is provided for convenience, as we’ll frequently need to downcast from this class to its concrete implementations.

The actual implementation of this class is variable_impl, parameterized by the type it encapsulates. We’ll instantiate it for the four types we’ll utilize:

1
2
3
4

using number = double;
using string = std::shared_ptr<std::string>;
using array = std::deque<variable_ptr>;
using function = std::function<void(runtime_context&)>;

We’ll employ double for numeric values. Strings, being immutable, will be reference-counted to enable optimizations when passed by value. Arrays will be represented using std::deque due to its stability. It’s worth noting that runtime_context will encapsulate all pertinent information about program memory during runtime, a topic we’ll revisit later.

The following definitions will also be frequently used:

1
2
3
4
5

using lvalue = variable_ptr;
using lnumber = std::shared_ptr<variable_impl<number>>;
using lstring = std::shared_ptr<variable_impl<string>>;
using larray = std::shared_ptr<variable_impl<array>>;
using lfunction = std::shared_ptr<variable_impl<function>>;

The “l” here serves as an abbreviation for “lvalue.” Whenever we deal with an lvalue of a specific type, we’ll utilize a shared pointer to variable_impl.

Runtime Context

During program execution, the runtime_context class will maintain the memory state.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class runtime_context{
private:
  std::vector<variable_ptr> _globals;
  std::deque<variable_ptr> _stack;
  std::stack<size_t> _retval_idx;
public:
  runtime_context(size_t globals);
  variable_ptr& global(int idx);
  variable_ptr& retval();
  variable_ptr& local(int idx);
  void push(variable_ptr v);
  void end_scope(size_t scope_vars);
  void call();
  variable_ptr end_function(size_t params);
};

Initialization occurs with the count of global variables.

• _globals stores all global variables, accessible via the global member function using absolute indices.
• _stack houses local variables and function arguments, while the integer at the top of _retval_idx tracks the absolute index within _stack of the current return value.
• The return value is accessed through the retval function, whereas local variables and function arguments are accessed using the local function by providing indices relative to the current return value. Function arguments, in this case, have negative indices.
• The push function adds variables to the stack, while end_scope removes a specified number of variables from the stack.
• The call function expands the stack by one element and pushes the index of the last element in _stack onto _retval_idx.
• end_function removes the return value and a specified number of arguments from the stack, returning the removed return value.

We won’t implement any low-level memory management, relying instead on C++’s native memory management. Similarly, we won’t delve into heap allocations, at least not for now.

With runtime_context in place, we possess all the fundamental components required for the core and most intricate aspect of this part.

Expressions

To elucidate the intricate solution presented here, I’ll briefly touch upon a couple of unsuccessful attempts that paved the way for this approach.

The most straightforward approach involved evaluating every expression as a variable_ptr and defining the following virtual base class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class expression {
  ...
public:
  variable_ptr evaluate(runtime_context& context) const = 0;
  lnumber evaluate_lnumber(runtime_context& context) const {
    return evaluate(context)->static_pointer_downcast<lnumber>();
  }
  lstring evaluate_lstring(runtime_context& context) const {
    return evaluate(context)->static_pointer_downcast<lstring>();
  }
  number evaluate_number(runtime_context& context) const {
    return evaluate_lnumber(context)->value;
  }
  string evaluate_string(runtime_context& context) const {
    return evaluate_lstring(context)->value;
  }
  ...
};
using expression_ptr = std::unique_ptr<expression>;

Subsequently, we would derive from this class for each operation, such as addition, concatenation, function calls, and so on. For instance, the implementation of an addition expression might resemble this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class add_expression: public expression {
private:
  expression_ptr _expr1;
  expression_ptr _expr2;
public:
  ...
  variable_ptr evaluate(runtime_context& context) const override{
    return std::make_shared<variable_impl<number> >(
      _expr1->evaluate_number(context) +
      _expr2->evaluate_number(context)
    );
  }
  ...
};

This approach entails evaluating both sides (_expr1 and _expr2), adding them, and then constructing a variable_impl<number>.

Downcasting variables wouldn’t pose an issue since their types are verified during compile time. However, the primary concern lies in the performance overhead introduced by the heap allocation of the returned object, which, in theory, is unnecessary. This allocation stems from the need to satisfy the virtual function declaration. While the first version of Stork will tolerate this penalty when returning numbers from functions, it’s unacceptable for simple pre-increment expressions to incur such an overhead.

As an alternative, I explored type-specific expressions inheriting from a common base:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class expression {
  ...
public:
  virtual void evaluate(runtime_context& context) const = 0;
  ...
};

class lvalue_expression: public virtual expression {
  ...
public:
  virtual lvalue evaluate_lvalue(runtime_context& context) const = 0;
  void evaluate(runtime_context& context) const override {
    evaluate_lvalue(context);
  }
  ...
};
using lvalue_expression_ptr = std::unique_ptr<lvalue_expression>;

class number_expression: public virtual expression {
  ...
public:
  virtual number evaluate_number(runtime_context& context) const = 0;
  void evaluate(runtime_context& context) const override {
    evaluate_number(context);
  }
  ...
};
using number_expression_ptr = std::unique_ptr<number_expression>;

class lnumber_expression: public lvalue_expression, public number_expression {
  ...
public:
  virtual lnumber evaluate_lnumber(runtime_context& context) const = 0;
  lvalue evaluate_lvalue(runtime_context& context) const override {
    return evaluate_lnumber(context);
  }
  number evaluate_number(runtime_context& context) const override {
    return evaluate_lnumber(context)->value;
  }
  void evaluate(runtime_context& context) const override {
    return evaluate_lnumber(context);
  }
  ...
};
using lnumber_expression_ptr = std::unique_ptr<lnumber_expression>;

This represents merely a fragment of the hierarchy (specifically for numbers), and already, we encounter the diamond problem (a class inheriting from two classes sharing a common base class).

Fortunately, C++ offers virtual inheritance, allowing inheritance from a base class while maintaining a pointer to it within the derived class. Consequently, if classes B and C virtually inherit from A, and class D inherits from both B and C, there will be only one instance of A within D.

However, this approach comes with certain trade-offs, including performance implications and the inability to downcast from A. Nonetheless, it seemed like a viable opportunity to leverage virtual inheritance.

With this approach, the implementation of the addition expression becomes more intuitive:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class add_expression: public number_expression {
private:
  number_expression_ptr _expr1;
  number_expression_ptr _expr2;
public:
  ...
  number evaluate_number(runtime_context& context) const override{
    return _expr1->evaluate_number(context) +
      _expr2->evaluate_number(context);
  }
  ...
};

Syntactically, it’s quite satisfactory. However, if any inner expression represents an lvalue number expression, it would necessitate two virtual function calls for evaluation—not ideal, but not entirely disastrous either.

Let’s introduce strings into the mix and observe the consequences:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class string_expression: public virtual expression {
  ...
public:
  virtual string evaluate_string(runtime_context& context) const = 0;
  void evaluate(runtime_context& context) const override {
    evaluate_string(context);
  }
  ...
};
using string_expression_ptr = std::unique_ptr<string_expression>;

To enable the conversion of numbers to strings, we need to inherit number_expression from string_expression.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class number_expression: public string_expression {
  ...
public:
  virtual number evaluate_number(runtime_context& context) const = 0;
  string evaluate_string(runtime_context& context) const override {
    return tostring(evaluate_number(context));
  }
  void evaluate(runtime_context& context) const override {
    evaluate_number(context);
  }
  ...
};
using number_expression_ptr = std::unique_ptr<number_expression>;

While we’ve managed to overcome this hurdle, we’re forced to override the evaluate virtual method once more. Otherwise, we’ll encounter significant performance degradation due to unnecessary conversions from numbers to strings.

As evident, the design is becoming increasingly convoluted. It barely survives because we lack bidirectional type conversions between expressions. If such a scenario arose, or if we attempted any form of circular conversion, our hierarchy would crumble. After all, hierarchies should reflect “is-a” relationships, not the weaker “is-convertible-to” relationship.

These unsuccessful attempts led me to a more intricate yet, in my view, more appropriate design. Firstly, having a single base class isn’t strictly necessary. While we need an expression class that can evaluate to void, if we can differentiate between void expressions and others during compile time, runtime conversions become unnecessary. Consequently, we’ll parameterize the base class with the expression’s return type.

Here’s the complete implementation of this class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

template <typename R>
class expression {
  expression(const expression&) = delete;
  void operator=(const expression&) = delete;
protected:
  expression() = default;
public:
  using ptr = std::unique_ptr<const expression>;

  virtual R evaluate(runtime_context& context) const = 0;
  virtual ~expression() = default;
};

This ensures only one virtual function call per expression evaluation (recursive calls aside). Given that we’re not compiling to binary code, this is a favorable outcome. The only remaining task is handling type conversions where permitted.

To achieve this, we’ll parameterize each expression with its return type and inherit from the corresponding base class. Within the evaluate function, we’ll convert the evaluation result to the function’s return type.

For instance, consider our addition expression:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

template <typename R>
class add_expression: public expression<R> {
  ...
  R evaluate(runtime_context& context) const override{
    return convert<R>(
      _expr1->evaluate(context) + 
      _expr2->evaluate(context)
    );
  }
  ...
};

To implement the convert function, we require some infrastructure:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

template<class V, typename T>
struct is_boxed {
  static const bool value = false;
};

template<typename T>
struct is_boxed<std::shared_ptr<variable_impl<T> >, T> {
  static const bool value = true;
};

string convert_to_string(number n) {
  std::string str
  if (n == int(n)) {
    str = std::to_string(int(n));
  } else {
    str = std::to_string(n);
  }
  return std::make_shared<std::string>(std::move(str));
}

string convert_to_string(const lnumber& v) {
  return convert_to_string(v->value);
}

The is_boxed structure is a type trait containing an inner constant, value, evaluating to true if and only if the first parameter is a shared pointer to variable_impl parameterized with the second type.

Implementing the convert function would be feasible even in earlier C++ versions. However, C++17 introduced a valuable statement called if constexpr, which evaluates conditions at compile time. If the condition is false, the corresponding block is entirely discarded, even if it would lead to a compile-time error. Otherwise, the else block is discarded.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

template<typename To, typename From>
auto convert(From&& from) {
  if constexpr(std::is_convertible<From, To>::value) {
    return std::forward<From>(from);
  } else if constexpr(is_boxed<From, To>::value) {
    return unbox(std::forward<From>(from));
  } else if constexpr(std::is_same<To, string>::value) {
    return convert_to_string(from);
  } else {
    static_assert(std::is_void<To>::value);
  }
}

Let’s analyze this function:

• Conversion occurs if permissible in C++ (for variable_impl pointer upcasting).
• Unboxing takes place if the value is boxed.
• Conversion to a string happens if the target type is a string.
• No action is taken if the target type is void.

In my opinion, this is significantly more readable than the older SFINAE-based syntax.

I’ll provide a concise overview of expression types, omitting some technical nuances for brevity.

We have three primary types of leaf expressions in an expression tree:

• Global variable expressions
• Local variable expressions
• Constant expressions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

template<typename R, typename T>
class global_variable_expression: public expression<R> {
private:
  int _idx;
public:
  global_variable_expression(int idx) :
    _idx(idx)
  {
  }

  R evaluate(runtime_context& context) const override {
    return convert<R>(
      context.global(_idx)
      ->template static_pointer_downcast<T>()
    );
  }
};

Apart from the return type, it’s also parameterized by the variable type. Local variables are handled similarly. For constants, we have:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

template<typename R, typename T>
class constant_expression: public expression<R> {
private:
  T _c;
public:
  constant_expression(T c) :
    _c(std::move(c))
  {
  }

  R evaluate(runtime_context& context) const override {
    return convert<R>(_c);
  }
};

Here, we immediately convert the constant within the constructor.

This serves as the base class for most of our expressions:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

template<class O, typename R, typename... Ts>
class generic_expression: public expression<R> {
private:
  std::tuple<typename expression<Ts>::ptr...> _exprs;

  template<typename... Exprs>
  R evaluate_tuple(
    runtime_context& context,
    const Exprs&... exprs
  ) const {
    return convert<R>(O()(
      std::move(exprs->evaluate(context))...)
    );
  }
public:
  generic_expression(typename expression<Ts>::ptr... exprs) :
    _exprs(std::move(exprs)...)
  {
  }

  R evaluate(runtime_context& context) const override {
    return std::apply(
      [&](const auto&... exprs){
        return this->evaluate_tuple(context, exprs...);
      },
      _exprs
    );
  }
};

The first argument represents the functor type, instantiated and called during evaluation. The remaining types correspond to the return types of child expressions.

To minimize boilerplate code, we define three macros:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#define UNARY_EXPRESSION(name, code)\
struct name##_op {\
  template <typename T1> \
  auto operator()(T1 t1) {\
    code;\
  }\
};\
template<typename R, typename T1>\
using name##_expression = generic_expression<name##_op, R, T1>;

#define BINARY_EXPRESSION(name, code)\
struct name##_op {\
  template <typename T1, typename T2>\
  auto operator()(T1 t1, T2 t2) {\
    code;\
  }\
};\
template<typename R, typename T1, typename T2>\
using name##_expression = generic_expression<name##_op, R, T1, T2>;
#define TERNARY_EXPRESSION(name, code)\
struct name##_op {\
  template <typename T1, typename T2, typename T3>\
  auto operator()(T1 t1, T2 t2, T3 t3) {\
    code;\
  }\
};\
template<typename R, typename T1, typename T2, typename T3>\
using name##_expression = generic_expression<name##_op, R, T1, T2, T3>;

Note that operator() is defined as a template, although it’s not always strictly necessary. This consistent approach simplifies expression definitions compared to specifying argument types as macro arguments.

Now, we can define most expressions. For instance, here’s the definition for /=:

1
2
3
4

BINARY_EXPRESSION(div_assign,
  t1->value /= t2;
  return t1;
);

We can define almost all expressions using these macros. Exceptions include operators with defined argument evaluation orders (logical && and ||, ternary (?), and comma (,) operators), array indexing, function calls, and param_expression, which clones parameters for pass-by-value function arguments.

Implementing these exceptions is relatively straightforward. Function call implementations are the most complex, so let’s examine one:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

template<typename R, typename T>
class call_expression: public expression<R>{
private:
  expression<function>::ptr _fexpr;
  std::vector<expression<lvalue>::ptr> _exprs;
public:
  call_expression(
    expression<function>::ptr fexpr,
    std::vector<expression<lvalue>::ptr> exprs
  ):
    _fexpr(std::move(fexpr)),
    _exprs(std::move(exprs))
  {
  }

  R evaluate(runtime_context& context) const override {
    std::vector<variable_ptr> params;
    params.reserve(_exprs.size());
	
    for (size_t i = 0; i < _exprs.size(); ++i) {
      params.push_back(_exprs[i]->evaluate(context));
    }
    
    function f = _fexpr->evaluate(context);
    
    for (size_t i = params.size(); i > 0; --i) {
      context.push(std::move(params[i-1]));
    }
    
    context.call();
    f(context);
    if constexpr (std::is_same<R, void>::value) {
      context.end_function(_exprs.size());
    } else {
      return convert<R>(
        context.end_function(
          _exprs.size()
        )->template static_pointer_downcast<T>()
      );
    }
  }
};

This code prepares the runtime_context by pushing all evaluated arguments onto its stack and invoking the call function. It then calls the evaluated first argument (representing the function itself) and returns the result of the end_function method. We can observe the use of if constexpr here as well, allowing us to avoid writing specializations for the entire class to handle functions returning void.

With this, we have all the runtime expression-related components. The final piece involves converting the parsed expression tree (described in the previous blog post) into a tree of expressions.

Expression Builder

To avoid confusion, let’s define the distinct phases of our language development cycle:

• Meta-compile time: When the C++ compiler executes.
• Compile time: When the Stork compiler executes.
• Runtime: When the Stork script executes.

Here’s the pseudo-code for the expression builder:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

function build_expression(nodeptr n, compiler_context context) {
  if (n is constant) {
    return constant_expression(n.value);
  } else if (n is identifier) {
    id_info info = context.find(n.value);
    if (context.is_global(info)) {
      return global_variable_expression(info.index);
    } else {
      return local_variable_expression(info.index);
    }
  } else { //operation
    switch (n->value) {
       case preinc:
        return preinc_expression(
          build_expression(n->child[0])
        );
      ...
      case add:
        return add_expression(
          build_expression(n->child[0]),
          build_expression(n->child[1])
        );
      ...
      case call:
        return call_expression(
          n->child[0], //function
          n->child[1], //arg0
          ...
          n->child[k+1], //argk
        );
    }
  }
}

While handling all operations is necessary, the algorithm itself appears straightforward.

Unfortunately, this approach is flawed. Firstly, we need to specify the function’s return type, which isn’t fixed in this case. The return type depends on the type of node being visited. While node types are known at compile time, return types should be determined at meta-compile time.

In the previous post, I expressed skepticism about the advantages of dynamically typed languages. In such languages, implementing the pseudo-code shown above would be almost literal. Now, I’m quite aware of their merits—instant karma at its finest.

Fortunately, we know the type of the top-level expression. While it depends on the compilation context, we can determine it without parsing the entire expression tree. For instance, consider the following for loop:

1
2

for (expression1; expression2; expression3)
...

The first and third expressions have a void return type because their evaluation results are unused. However, the second expression has a number type because it’s compared to zero to determine whether to terminate the loop.

Knowing the type of the expression associated with a node operation often reveals the types of its child expressions.

For example, if the expression (expression1) += (expression2) has the type lnumber, it implies that expression1 also has the type lnumber, while expression2 has the type number.

However, the expression (expression1) < (expression2) always results in a number, even though its child expressions can be either number or string. In this case, we check if both nodes represent numbers. If so, we build expression1 and expression2 as expression<number>. Otherwise, they become expression<string>.

Another challenge we must address involves handling incompatible types during expression building.

Imagine needing to build an expression of type number. We cannot return anything meaningful if we encounter a concatenation operator. While we know this shouldn’t happen due to type checking during expression tree construction (in the previous part), it prevents us from writing a template function parameterized by the return type. Such a function would have invalid branches depending on the return type.

One approach could involve splitting the function based on the return type using if constexpr. However, this is inefficient, as repeating code for the same operation across multiple branches becomes necessary. Writing separate functions in such cases might be preferable.

The implemented solution splits the function based on the node type. Within each branch, we check if that branch’s type is convertible to the function’s return type. If not, a compiler error is thrown. While this should never occur ideally, the code’s complexity makes such a strong claim risky—I might have made a mistake.

We use the following self-explanatory type trait structure to check for convertibility:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

template<typename From, typename To>
struct is_convertible {
  static const bool value =
    std::is_convertible<From, To>::value ||
    is_boxed<From, To>::value ||
    (
      std::is_same<To, string>::value &&
      (
        std::is_same<From, number>::value ||
        std::is_same<From, lnumber>::value
      )
    );
};

After this split, the code becomes relatively straightforward. We can semantically cast from the original expression type to the desired one without encountering meta-compile-time errors.

However, this approach introduces a significant amount of boilerplate code, prompting heavy reliance on macros for reduction.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

template<typename R>
class expression_builder{
private:
  using expression_ptr = typename expression<R>::ptr;

  static expression_ptr build_void_expression(
    const node_ptr& np,
    compiler_context& context
  );

  static expression_ptr build_number_expression(
    const node_ptr& np,
    compiler_context& context
  );

  static expression_ptr build_lnumber_expression(
    const node_ptr& np,
    compiler_context& context
  );

  static expression_ptr build_string_expression(
    const node_ptr& np,
    compiler_context& context
  );

  static expression_ptr build_lstring_expression(
    const node_ptr& np,
    compiler_context& context
  );

  static expression_ptr build_array_expression(
    const node_ptr& np,
    compiler_context& context
  );
  static expression_ptr build_larray_expression(
    const node_ptr& np,
    compiler_context& context
  );
  static expression_ptr build_function_expression(
    const node_ptr& np,
    compiler_context& context
  );

  static expression_ptr build_lfunction_expression(
    const node_ptr& np,
    compiler_context& context
  );
public:
  static expression_ptr build_expression(
    const node_ptr& np,
    compiler_context& context
  ) {
    return std::visit(overloaded{
      [&](simple_type st){
        switch (st) {
          case simple_type::number:
            if (np->is_lvalue()) {
              RETURN_EXPRESSION_OF_TYPE(lnumber);
            } else {
              RETURN_EXPRESSION_OF_TYPE(number);
            }
          case simple_type::string:
            if (np->is_lvalue()) {
              RETURN_EXPRESSION_OF_TYPE(lstring);
            } else {
              RETURN_EXPRESSION_OF_TYPE(string);
            }
          case simple_type::nothing:
            RETURN_EXPRESSION_OF_TYPE(void);
        }
      },
      [&](const function_type& ft) {
        if (np->is_lvalue()) {
          RETURN_EXPRESSION_OF_TYPE(lfunction);
        } else {
          RETURN_EXPRESSION_OF_TYPE(function);
        }
      },
      [&](const array_type& at) {
        if (np->is_lvalue()) {
          RETURN_EXPRESSION_OF_TYPE(larray);
        } else {
          RETURN_EXPRESSION_OF_TYPE(array);
        }
      }
    }, *np->get_type_id());
  }
};

The build_expression function represents the sole public function here. It invokes std::visit on the node type, applying the provided functor to the variant and decoupling it in the process. You can find more information about this and the overloaded functor here.

The RETURN_EXPRESSION_OF_TYPE macro calls private functions for expression building and throws an exception if conversion is impossible:

1
2
3
4
5
6
7

#define RETURN_EXPRESSION_OF_TYPE(T)\
    if constexpr(is_convertible<T, R>::value) {\
      return build_##T##_expression(np, context);\
    } else {\
      throw expression_builder_error();\
      return expression_ptr();\
    }

We must return a null pointer in the else branch because the compiler cannot determine the function’s return type if conversion is impossible. Otherwise, std::visit requires all overloaded functions to have identical return types.

For example, here’s the function for building expressions with string as the return type:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

static expression_ptr build_string_expression(
  const node_ptr& np, compiler_context& context
) {
  if (std::holds_alternative<std::string>(np->get_value())) {
    return std::make_unique<constant_expression<R, string>>(
      std::make_shared<std::string>(
        std::get<std::string>(np->get_value())
      )
    );
  }

  CHECK_IDENTIFIER(lstring);

  switch (std::get<node_operation>(np->get_value())) {
    CHECK_BINARY_OPERATION(concat, string, string);
    CHECK_BINARY_OPERATION(comma, void, string);
    CHECK_TERNARY_OPERATION(ternary, number, string, string);
    CHECK_INDEX_OPERATION(lstring);
    CHECK_CALL_OPERATION(lstring);
    default:
      throw expression_builder_error();
  }
}

It first checks if the node contains a string constant and builds a constant_expression accordingly.

Next, it checks if the node holds an identifier and returns a global or local variable expression of type lstring. This scenario can occur if we implement constant variables. Otherwise, it assumes the node contains a node operation and attempts all operations that can yield a string.

Here are the implementations of the CHECK_IDENTIFIER and CHECK_BINARY_OPERATION macros:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#define CHECK_IDENTIFIER(T1)\
  if (std::holds_alternative<identifier>(np->get_value())) {\
    const identifier& id = std::get<identifier>(np->get_value());\
    const identifier_info* info = context.find(id.name);\
    if (info->is_global()) {\
      return std::make_unique<\
        global_variable_expression<R, T1>\ 
      >(info->index());\
    } else {\
      return std::make_unique<\
        local_variable_expression<R, T1>\
      >(info->index());\
    }\
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#define CHECK_BINARY_OPERATION(name, T1, T2)\
    case node_operation::name:\
      return expression_ptr(\
        std::make_unique<name##_expression<R, T1, T2> > (\
          expression_builder<T1>::build_expression(\
            np->get_children()[0], context\
          ),\
          expression_builder<T2>::build_expression(\
            np->get_children()[1], context\
          )\
        )\
      );

The CHECK_IDENTIFIER macro needs to consult the compiler_context to construct a global or local variable expression with the correct index. This is the only instance where compiler_context is used within this structure.

As you can see, CHECK_BINARY_OPERATION recursively calls build_expression for its child nodes.

Wrapping Up

You can access the complete source code my GitHub page, compile it, input expressions, and observe the evaluated variable results.

I believe that in all creative endeavors, there comes a moment when the creator realizes their creation has, in a sense, come alive. For programming language construction, it’s the moment when you witness the language “breathing.”

In the next and final installment of this series, we’ll implement the remaining features of our minimal language and see it in action.