DEV Community: Lex Plt

How does quoting works in ArkScript macros?

Lex Plt — Sun, 18 May 2025 10:00:00 +0000

The other night, I was talking about meta programming to other developers, and at one point someone asked how macros could be used to do meta programming. They were probably thinking about C type of macros, which are powerful but are just text processor tools.

Using macros you could have the following code:

double Compute()
{
  // doing something
  return result;
}

and transform it into:

double Compute()
{
  if (_cache.GetValue(out var result)
    return result;
  // doing something
  _cache.SetValue(result);
  return result;
}

💡 Macros

They are a tool to manipulate code, with code. It allows one to write generic code and have the compiler do the heavy lifting and monomorphize your code.

📝 Note

What's meta programming?

According to Wikipedia, it's a computer programming technique in which computer programs have the ability to treat other programs as their data. It means that a program can be designed to read, generate, analyse, or transform other programs, and even modify itself, while running. In some cases, this allows programmers to minimize the number of lines of code to express a solution, in turn reducing development time.

Then someone asked how we could implement the following code in ArkScript (not working by the way, because Rust macros are hygienic):

macro_rules! using_a {
    ($e:expr) => {
        {
            let a = 42;
            $e
        }
    }
}

let four = using_a!(a / 10);

I quickly threw this together, and sure enough, ArkScript let it pass as its macros aren't hygienic:

($ using_a (e) {
  (let a 42)
  e })
(let four {(using_a (/ a 10))})
(print four)  # 4.2

Homoiconicity

A concept that gets talked about quite frequently in the context of macros.

It is the ability to manipulate code in the language, using code from the same language. Code is data, and data is code. Lisp is the most common homoiconic language, but we can also cite all its dialects (Clojure, Scheme, Racket...), as well as Rebol, and you guessed it, ArkScript.

Using parentheses to represent S-expressions in Lisp inspired languages helps as you can represent your AST in code, and AST is also data.

Quoting?

In ArkScript macros, there is no capture of variables, you play directly with the AST:

($ foo (val)
  (print (@ val 2)))

(foo (list 1 5)) # -> becomes (print 5)

As long as you are inside a macro, the AST node isn't evaluated unless it is involved in an expression that can be evaluated at compile time (eg (+ 1 arg)).

Alas it comes at a cost and expressions can be evaluated at compile when you didn't mean to, if the example was passed something like (+ 1 2) it would print 2! To prevent this behavior I thought I just needed to have a way to stop macro evaluation and added $as-is to paste nodes in the AST as-is, stopping further macro evaluation on them.

This is particularly useful in the testing framework that relies on many macros, we can write:

(test:suite name {
  # ...
  (test:expect (some_computation)) })

As the test:xxx macros use ($as-is arg) to escape each argument:

($ test:expect (_cond ..._desc) {
  (if (!= true ($as-is _cond))
    (testing:_report_error true ($as-is _cond) "true" ($repr _cond) _desc)
    (testing:_report_success)) })

TL;DR: I reinvented (a less powerful) quote

Originally from lexp.lt

Instruction source location tracking in ArkScript

Lex Plt — Sat, 17 May 2025 10:00:00 +0000

Good error reporting is crucial in programming languages. Doing it at compile time was easy in ArkScript as we have all the context we need at hand, but since we compile code down to bytecode, which is then run by the virtual machine, we loose a lot of context: the source files, their path, their content, we don't have that anymore! Our runtime errors could only show the VM internal state. This article is about how it all changed.

Multiple solutions

I went to the drawing board, and three solutions presented themselves to me:

create a source location table in the bytecode, mapping an instruction to a file and line ;
emit special instructions that would be skipped by the VM, and used only when the VM crashed, backtracking to find the nearest SOURCE instruction ;
extend the size of instructions to 8 bytes and use the 4 new bytes to track the source file (eg 2 bytes for an identifier) and line (2 bytes for the line seemed enough to track 64k+ lines of files) ;

The second one was off the table pretty quickly, because I had a hunch it would hinder performances too much to my liking. It would also disrupt the IR optimizer, and I would have had to detect more instruction patterns as SOURCE instructions could be interleaved with optimizable instructions.

The third solution felt like a lot of work for a small gain, as it would be used only when handling errors. It would also double the size of the bytecode files, and lock the future evolutions of the VM as I wouldn't be able to use those additional 4 bytes for anything else.

📝 Note

As Robert Nystrom noted on Reddit, making the bytecode larger the VM would have more cache misses, making performance worse.

As you might have guessed, I went with the first solution.

Implementation

The source location data is added to each AST node by the parser, and the last compiler pass that can access the AST is the AST lowerer, whose job is to generate the IR, hence it felt logical to add two fields, source_file and source_line to the IR::Entity structure.

Bonus point: using this source tracking solution, there are (nearly) 0 modifications on the IR Optimizer! Nearly 0, because I had to add source location to each optimized IR entity from the compacted IR entities.

Which instruction should we track?

All of them!

You might ask yourself, "But wouldn't this make the generated bytecode twice as big, as solution 3 would?", and you're partly right. To make this right, we have to introduce de-duplication!

The proposed solution was to track every instruction source location, but many instructions would point to the same file and line, as a single statement like (if (< value 5) (print "you can pass!") (go-to-jail)) would involve around 10-12 instructions.

If we keep track of the source location of the first instruction in a series of instructions from the same file and on the same line, that's more than enough!

std::optional<InstLocation> prev = std::nullopt;

for (const auto& inst : page)
{
  if (inst.hasValidSourceLocation())
  {
    // we are guaranteed to have a value since we listed all
    // existing filenames in IRCompiler::process before,
    // thus we do not have to check if std::ranges::find
    // returned a valid iterator.
    auto file_id = static_cast<uint16_t>(
      std::distance(
        m_filenames.begin(),
        std::ranges::find(m_filenames, inst.filename())));

    std::optional<internal::InstLoc> prev = std::nullopt;
    if (!locations.empty())
      prev = locations.back();

     // skip redundant instruction location
     if (!(
           prev.has_value() &&
           prev->filename_id == file_id &&
           prev->line == inst.sourceLine() &&
           prev->page_pointer == i))
       locations.push_back(
         { .page_pointer = static_cast<uint16_t>(i),
           .inst_pointer = ip,
           .filename_id = file_id,
           .line = static_cast<uint32_t>(inst.sourceLine()) });
  }

  if (inst.kind() != IR::Kind::Label)
    ++ip;
}

Exploiting the new source location for our errors

We now need to track filenames and (page, instruction, filename id, line) tuples so that we have source locations for our errors. Those are split in two data tables in the bytecode.

Having those tables, given a page pointer and instruction pointer, we can retrieve the nearest source location information and the associated file by its id (index in the filenames table).

std::optional<InstLoc> VM::findSourceLocation(
    const std::size_t ip,
    const std::size_t pp
) {
  std::optional<InstLoc> match = std::nullopt;

  for (const auto location : m_state.m_inst_locations)
  {
    if (location.page_pointer == pp && !match)
      match = location;

    // select the best match: we want to find the location
    // that's nearest our instruction pointer, but not equal
    // to it as the IP will always be pointing to the next
    // instruction, not yet executed. Thus, the erroneous
    // instruction is the previous one.
    if (location.page_pointer == pp && match &&
        location.inst_pointer < ip / 4)
      match = location;

    // early exit because we won't find anything better, as
    // inst locations are ordered by ascending (pp, ip)
    if (location.page_pointer > pp || (
          location.page_pointer == pp &&
          location.inst_pointer >= ip / 4))
      break;
  }

  return match;
}

Results!

Given the following erroneous code:

(let foo (fun (a b) (+ a b)))

(foo 1 2 3)

We expect an arity error upon calling foo, as we passed too many arguments.

ArityError: When calling `(foo)', received 3 arguments, but expected 2: `(foo a b)'

In file a.ark
    1 | (let foo (fun (a b) (+ a b)))
      | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
    2 |
    3 | (foo 1 2 3)

[   2] In function `foo' (a.ark:1)
[   1] In global scope (a.ark:3)

Current scope variables values:
foo = Function@1
At IP: 0, PP: 1, SP: 5

In terms of bytecode, it generated the following:

Symbols table (length: 3)
0) foo
1) a
2) b

Constants table (length: 4)
0) (PageAddr) 1
1) (Number) 1
2) (Number) 2
3) (Number) 3

Instruction locations table (length: 3)
 PP, IP
  0,  0 -> a.ark:0
  0,  4 -> a.ark:2
  1,  4 -> a.ark:0

Code segment 0 (length: 24)
   0 39 00 00 00 LOAD_CONST_STORE
   1 38 00 20 01 LOAD_CONST_LOAD_CONST
   2 03 00 00 03 LOAD_CONST 3 (Number)
   3 02 00 00 00 LOAD_SYMBOL_BY_INDEX (0)
   4 0b 00 00 03 CALL (3)
   5 0a 00 00 00 HALT

Code segment 1 (length: 28)
   0 05 00 00 01 STORE a
   1 05 00 00 02 STORE b
   2 02 00 00 01 LOAD_SYMBOL_BY_INDEX (1)
   3 02 00 00 00 LOAD_SYMBOL_BY_INDEX (0)
   4 20 00 00 00 ADD
   5 09 00 00 00 RET
   6 0a 00 00 00 HALT

As you can see, the instruction locations table is quite small thanks to the de-duplication, and we have all the information we need to report errors correctly!

Originally from lexp.lt

Optimizing scopes data in ArkScript VM

Lex Plt — Fri, 16 May 2025 10:00:00 +0000

If you don't know me yet, I have been working on ArkScript for nearly 6 years now. ArkScript is a scripting language in modern C++, running on a custom virtual machine (like Python or Lua), with the goal of having a syntax easy to learn and use, a C++ interface to embed it in programs, and decent performances (without trying to be as fast as Lua though, Mike Pall is a genius and did outstanding work on LuaJIT).

Is my language fast?

A silly question that you shouldn't care about, unless the perceived slowness of the language is becoming a problem.

Recently, I added more benchmarks to the language, and I was quite astonished to see that it was 1.5 times slower than Python on such a simple benchmark:

(mut collection [])
(mut i 0)
(while (< i 1000000) {
  (append! collection i)
  (set i (+ i 1)) })

(mut sum 0)
(set i 0)
(while (< i 1000000) {
  (set sum (+ sum (@ collection i)))
  (set i (+ i 1)) })

It is also 17 times slower than Python on the binary tree benchmark. I expected it to be a bit slower, but not by that much! When digging in profiler traces, it appears that we lose about 35% of execution time looking for variables. This is what inspired me to write this article: how locals are stored in the virtual machine, and what kind of optimizations were applied.

📝 Note

You can see the benchmark results on this page: arkscript-lang.dev/benchmarks.html. They are generated from github.com/ArkScript-lang/benchmarks.

Some definitions

[A stack-based VM, such as ArkScript], is a processor in which the primary interaction is moving short-lived temporary values to and from a push-down stack.
Wikipedia — Stack machine

ArkScript does not use any kind of registers; all computations are done using a stack, so (1 + 2) * 3 is:

PUSH 2
PUSH 1
ADD  // pop 1, 2, push (1+2)
PUSH 3
MUL  // pop the addition result, 3, push (3*3)

Variables are stored in a scope, and a stack of scopes defines the environment at one point in the program execution. I call the current scope (the last one on the stack of scopes) locals: it holds all the variables defined in the current scope.

Evolution between versions

For the following sections, I inspected the code of each version to see how locals and scopes were handled. Some versions do not change that much and instead have optimizations elsewhere, which I didn't bother checking/measuring since it isn't the main focus of the article.

Benchmarks are run on the Ackermann-Péter function using google/benchmark, because it's a recursive function but not a primitive recursive function, meaning compilers can't easily optimize it. It grows quickly, creates a lot of scopes and destroys them a lot too, which is perfect for our use case.

They are run on a M1 MacBook Pro with 10 cores and 32GB of RAM:

Run on (8 X 24 MHz CPU s)
CPU Caches:
  L1 Data 64 KiB
  L1 Instruction 128 KiB
  L2 Unified 4096 KiB (x8)

To retrace my steps, I created one git worktree per tag on the project (and that's when I saw that the first tag on the project was 3.0.1 instead of 0.0.1):

$ git worktree list
~/ArkScript/Ark        d1be6b9f [dev]
~/ArkScript/ark-v301   b43738be (detached HEAD)
~/ArkScript/ark-v3010  4d8067ce (detached HEAD)
~/ArkScript/ark-v3011  a0627382 (detached HEAD)
~/ArkScript/ark-v3012  9452ccee (detached HEAD)
~/ArkScript/ark-v3013  6e7c5b7b (detached HEAD)
~/ArkScript/ark-v3014  75ca4090 (detached HEAD)
~/ArkScript/ark-v3015  0744f9a0 (detached HEAD)
~/ArkScript/ark-v302   788e9d5e (detached HEAD)
~/ArkScript/ark-v303   1191515e (detached HEAD)
~/ArkScript/ark-v304   2173b4f5 (detached HEAD)
~/ArkScript/ark-v305   7ae2bf51 (detached HEAD)
~/ArkScript/ark-v306   ce876013 (detached HEAD)
~/ArkScript/ark-v307   386e289e (detached HEAD)
~/ArkScript/ark-v308   4f99008c (detached HEAD)
~/ArkScript/ark-v309   250e27cb (detached HEAD)
~/ArkScript/ark-v310   c2dcd843 (detached HEAD)
~/ArkScript/ark-v311   d301511a (detached HEAD)
~/ArkScript/ark-v312   a9e7ef97 (detached HEAD)
~/ArkScript/ark-v313   bf151b77 (detached HEAD)
~/ArkScript/ark-v320   0f16875d (detached HEAD)
~/ArkScript/ark-v330   c6c59c4c (detached HEAD)
~/ArkScript/ark-v340   425f7baf (detached HEAD)
~/ArkScript/ark-v350   2efb4ed8 (detached HEAD)
~/ArkScript/ark-v4002  f5b247c3 (detached HEAD)
~/ArkScript/ark-v4003  019d36bd (detached HEAD)
~/ArkScript/ark-v4004  07e569b6 (detached HEAD)
~/ArkScript/ark-v4005  6a4c6449 (detached HEAD)

Instantiating a bunch of stacks and big empty vectors

From version 3.0.1 to 3.0.12.

The very first version of the VM uses a Frame object, instantiated for each scope. I think I stole this idea from Java, though my implementation is subpar, and I probably didn't understand everything at the time. Each Frame instanced a new stack for itself, implemented as a std::vector, which means that pushing to it would make grow and copy all of its elements, which is highly inefficient.

Locals were stored as a std::shared_ptr<std::vector<Value>> (Scope_t). You read that right, no id. You accessed a specific variable using locals[variable_id]. The shared pointer is there because locals could be added by closures, which have to retain their environment, which can be mutated. The stack of scopes was materialized as std::vector<Scope_t>.

class Frame
{
public:
  Frame();
  Frame(const Frame&) = default;
  Frame(std::size_t caller_addr, std::size_t caller_page_addr);

  Value&& pop()
  {
    m_i--;
    return std::move(m_stack[m_i]);
  }

  void push(const Value& value)
  {
    m_stack[m_i] = value;
    m_i++;
  }

  std::size_t stackSize() const { return m_i; }
  std::size_t callerAddr() const { return m_addr; }
  std::size_t callerPageAddr() const { return m_page_addr; }

  // related to scope deletion

  void incScopeCountToDelete() { m_scope_to_delete++; }
  void resetScopeCountToDelete() { m_scope_to_delete = 0; }
  uint8_t scopeCountToDelete() const { return m_scope_to_delete; }

private:
  std::size_t m_addr, m_page_addr;
  std::vector<Value> m_stack;
  int8_t m_i;
  uint8_t m_scope_to_delete;
};

Results:

Benchmark                         Time             CPU   Iterations
ackermann                       197 ms          197 ms            4

Locals as a list of pairs of id and value

From version 3.0.13 to 3.0.15.

The next iteration of local management introduced the first version of the Scope, which we're still using today! They are still instantiated inside shared pointers, but they are way smaller as we do not access a variable through operator[], but iterate through the pairs of id -> value instead.

class Scope
{
public:
  Scope() noexcept;

  void push_back(uint16_t id, Value&& val) noexcept;
  void push_back(uint16_t id, const Value& val) noexcept;
  bool has(uint16_t id) noexcept;
  Value* operator[](uint16_t id) noexcept;
  uint16_t idFromValue(Value&& val) noexcept;
  const std::size_t size() const noexcept;

  friend class Ark::VM;

private:
  std::vector<std::pair<uint16_t, Value>> m_data;
};

This version tried to be smart: upon adding a new value, we sort the elements, so that the lookup would be faster. In retrospect (and after having looked at benchmarks), I now know it was a bad idea (which is why I'm not doing this anymore!):

#define push_pair(id, val) \
  m_data.emplace_back(std::pair<uint16_t, Value>(id, val))
#define insert_pair(place, id, val) \
  m_data.insert(place, std::pair<uint16_t, Value>(id, val))

void Scope::push_back(uint16_t id, Value&& val) noexcept
{
#ifdef ARK_SCOPE_DICHOTOMY
  switch (m_data.size())
  {
    case 0:
      push_pair(std::move(id), std::move(val));
      break;

    case 1:
      if (m_data[0].first < id)
        push_pair(std::move(id), std::move(val));
      else
        insert_pair(m_data.begin(), std::move(id), std::move(val));
      break;

    default:
      auto lower = std::lower_bound(
        m_data.begin(),
        m_data.end(),
        id,
        [](const auto& lhs, uint16_t id) -> bool {
          return lhs.first < id;
        });
      insert_pair(lower, std::move(id), std::move(val));
      break;
  }
#else
  push_pair(std::move(id), std::move(val));
#endif
}

Inserting while trying to keep all elements ordered is slower than simply adding each element to the end of the scope:

Results:

Benchmark                         Time             CPU   Iterations
ackermann_dichotomy             294 ms          294 ms            2
ackermann_push_back             192 ms          192 ms            4

Single stack

From version 3.1.0 to 4.0.0-10.

In v3.1.0, the Scope removed the sorted insert to push everything to the end of its std::vector<std::pair<id, Value>>. Also, the horrendous std::vector<Frame> was replaced by a std::unique_ptr<std::array<Value, 8192>>, which yielded a much-needed performance improvement. Instead of having a separate data structure to save the caller page pointer and instruction pointer, we now push those on the stack too (meaning we have a recursion depth of 4096 for non-primary recursive functions, that can't be optimized to loops).

Results:

Benchmark                         Time             CPU   Iterations
ackermann                       146 ms          146 ms            5

Then, in v3.1.3 the ExecutionContext appeared: it's a struct with everything the VM needs to run code (instruction, page and stack pointer, stack, std::vector<Scope> for locals...). This has been added to help with adding parallelism to the language; it did not downgrade performances (nor did it improve them).

In later versions, more AST and new IR optimizations were implemented, which helped divide the run time of our benchmark by ~2.4:

Benchmark                         Time             CPU   Iterations
ackermann                      60.4 ms         60.3 ms           50

However, we still spend around 35% of our time in findNearestVariable (which calls Scope::operator[] on line 5):

inline Value* VM::findNearestVariable(
  const uint16_t id,
  internal::ExecutionContext& ctx
) noexcept
{
  for (auto it = ctx.locals.rbegin(), it_end = ctx.locals.rend();
       it != it_end; ++it)
  {
    if (const auto val = (*it)[id]; val != nullptr)
      return val;
  }
  return nullptr;
}

Even with a basic bloom filter, searching for a value takes a lot of time, plus data locality isn't that good:

bool Scope::maybeHas(const uint16_t id) const noexcept
{
  return m_min_id <= id && id <= m_max_id;
}

Value* Scope::operator[](const uint16_t id_to_look_for) noexcept
{
  if (!maybeHas(id_to_look_for))
    return nullptr;

  for (auto& [id, value] : m_data)
  {
    if (id == id_to_look_for)
      return &value;
  }
  return nullptr;
}

How can we do better?

In his book Crafting Interpreters, Robert Nystrom shows that you can use the stack for storing local variables in the Local Variables chapter. This would mean using a single contiguous data structure for all of our needs, which would actually be pretty neat, and most certainly yield impressive performance improvements!

Alas, due to how closures work in ArkScript, this isn't doable. Storing variables on the stack means the compiler has to know where we put each variable, and since no type checking is done at compile time, we can't easily know when we're compiling a closure call!

📝 Note

Actually, we can infer that from a.b or a.b.c because the dot notation is reserved for closures and field accessing, but this only covers 90% of use cases, by reading (foo) we don't know if we're calling a C++ function, a user function or a user closure.

But this gave me an idea: what if we could use a single contiguous data structure for our variables? And make small adaptations to handle closure scopes, that need to be kept alive while a closure is being called?

Well, I did that. And it worked.

Contiguous storage for our locals

Currently, our locals are stored in a std::vector<std::shared_ptr<std::vector<std::pair<id, value>>>>, basically a list of pointers to lists of pairs. This can't be good, our piles of id -> value are scattered all over RAM! However, what we need for storing locals is:

a vector or array to store our pairs id -> value
a length, to know how many elements are in our scope
maybe some min and max id to implement a basic bloom filter

So we could make views over a single std::array<std::pair<id, value>, N>, that knows where they start, and how many elements they hold.

The Scope implementation didn't even have to change that much:

ScopeView::ScopeView(
  std::array<pair_t, ScopeStackSize>* storage,
  const std::size_t start
) noexcept :
  m_storage(storage), m_start(start), m_size(0),
  m_min_id(std::numeric_limits<uint16_t>::max()),
  m_max_id(0)
{}

void ScopeView::push_back(uint16_t id, Value&& val) noexcept
{
  if (id < m_min_id)
    m_min_id = id;
  if (id > m_max_id)
    m_max_id = id;

  (*m_storage)[m_start + m_size] = std::make_pair(id, std::move(val));
  ++m_size;
}

bool ScopeView::maybeHas(const uint16_t id) const noexcept
{
  return m_min_id <= id && id <= m_max_id;
}

Value* ScopeView::operator[](const uint16_t id_to_look_for) noexcept
{
  if (!maybeHas(id_to_look_for))
    return nullptr;

  for (std::size_t i = m_start; i < m_start + m_size; ++i)
  {
    auto& [id, value] = (*m_storage)[i];
    if (id == id_to_look_for)
      return &value;
  }
  return nullptr;
}

And creating a new scope is still quite easy, we just need to pass a pointer to our array, and the first free position:

context.locals.emplace_back(
  // our array<pair<id, value>>
  &context.scopes_storage,
  // the end of the scope (size + start) = first free slot
  context.locals.back().storageEnd()
);

As for closures, I had to create a dedicated ClosureScope, which was basically the old Scope, since the closure needs to have ownership of a scope, and now we use views. Merging a ClosureScope inside a Scope is still doable (so that we can create a scope of references to the closure's fields):

void ClosureScope::mergeRefInto(ScopeView& other)
{
  for (auto& [id, value] : m_data)
  {
    if (value.valueType() == ValueType::Reference)
      other.push_back(id, value);
    else
      other.push_back(id, Value(&value));
  }
}

All of this is very fancy, and seems to work on paper, right? But some of you may have noticed a flaw in this design: what if we need to add values to a scope that isn't the last and active one? It would break! Luckily, this can't happen as only one scope can be active at a time, and variables are always added to the current active scope, which is the last one on our pile of scopes.

Gotta go fast!

By using a contiguous storage, avoiding useless copies of the pairs id -> value when the storage vector grew, avoiding reserving and freeing memory every time a function is call / returns, we have achieved a 21% performance improvement on our benchmark (and even up to 76% improvement on the binary tree benchmark!):

Results:

Benchmark                         Time             CPU   Iterations
ackermann_begining              197 ms          197 ms            4
ackermann_dichotomy             294 ms          294 ms            2
ackermann_push_back             192 ms          192 ms            4
ackermann_single_stack         60.4 ms         60.3 ms           50
ackermann_contiguous           47.8 ms         47.7 ms           50

binary_trees_single_stack    3965.9 ms      3962.32 ms            1
binary_trees_contiguous         941 ms          939 ms            1

Originally from lexp.lt

Publishing ZIP artifacts with SBT

Lex Plt — Thu, 15 May 2025 10:00:00 +0000

In my previous article about Scala, I briefly mentioned we were publishing Swaggers inside JARs, that we could unzip to retrieve the Swagger definition and then run our code generation. It works, but using ZIPs would feel better and less confusing for users.

I have decided to nerd snip myself and see how I could publish a ZIP using SBT, and then use said ZIP as a dependency for sbt-swaggerinator.

sbt-native-packager to the rescue

I quickly noticed that sbt-native-packager could output ZIPs, which was very helpful as we are already using it for bundling JARs and creating Docker images.

With this basic SBT configuration, you can publish a ZIP:

lazy val publishZipSettings = Seq(
  publishTo := "https://my-maven-repository",
  publishConfiguration := publishConfiguration.value.withOverwrite(true),
  Universal / mappings ++= contentOf(sourceDirectory.value / "main" / "resources"),
  publish := (publish dependsOn (Universal / packageBin)).value,
  publishLocal := (publishLocal dependsOn (Universal / packageBin)).value,
) ++ makeDeploymentSettings(Universal, Universal / packageBin, "zip")

lazy val `my-api-swagger` = (project in file("modules/my-api-swagger"))
  .enablePlugins(UniversalPlugin)
  .enablePlugins(UniversalDeployPlugin)
  .settings(publishZipSettings)

Line 4 is quite important ; at first I wrote Universal / mappings += (Compile / packageBin).value -> "swagger.yaml", as per the docs, not really knowing what I was doing. It seems that it worked, but it is actually putting the JAR in the ZIP as a file named swagger.yaml, which isn't ideal if you ask me. Since we generate the Swagger files under the resources/ folder, using contentOf is good enough.
Lines 5 and 6 aren't strictly necessary, just useful to be able to generate the ZIP file in a single command: sbt "my-api-swagger / publish".

Problems:

Publishing works as expected, but we have problems when trying to retrieve the ZIP for the Maven repository: SBT is looking for a POM file which isn't generated! Great, we can push artifacts but not retrieve them.
Apparently we need to generate POM files, which we do not have.
The module is published with a _2.13 suffix at the end, even though it doesn't depend on any particular Scala version.

Using SBT artifacts

We can tell SBT that we are publishing an artifact, that might help us. At first, I thought we had to publish a module, eg my-api, with an attached artifact named my-api-swagger ; not really what I was looking for but let's try this anyway.

It turns out that creating a project with a single artifact correctly configured was a thing: an artifact is just what SBT is publishing (by default: the binary JAR, docs etc). And we can disable JAR publishing, as well as docs, since we don't need them!

New settings:

 lazy val publishZipSettings = Seq(
   publishTo := "https://my-maven-repository",
   publishConfiguration := publishConfiguration.value.withOverwrite(true),
   Universal / mappings ++= contentOf(sourceDirectory.value / "main" / "resources"),
+  Compile / packageBin / publishArtifact := false,
+  Compile / packageDoc / publishArtifact := false,
   publish := (publish dependsOn (Universal / packageBin)).value,
   publishLocal := (publishLocal dependsOn (Universal / packageBin)).value,
+  crossPaths := false,
 ) ++ makeDeploymentSettings(Universal, Universal / packageBin, "zip")

 lazy val `my-api-swagger` = (project in file("modules/my-api-swagger"))
   .enablePlugins(UniversalPlugin)
   .enablePlugins(UniversalDeployPlugin)
   .settings(publishZipSettings)
+  .settings(addArtifact(Artifact("my-api-swagger", "zip", "zip"), Universal / packageBin))

With those additions, we can:

avoid publishing a jars/ folder (line 5) ;
avoid publishing a docs/ folder (line 6) ;
avoid the _2.13 suffix (line 9) ;
generate POM and ivy.xml files for SBT ;
keep publishing a ZIP under the zips/ folder (line 16).

It's still a bit verbose, and I would have liked to be able to add the addArtifact(...) setting inside the publishZipSettings, deducing the artifact name from the module ; alas we need to rely on a setting (projectID.value.name), and you can only use .value on settings inside other settings or macros. That leaves room for improvements, but for now, it's good enough!

Originally from lexp.lt

Generating swaggers at compile time

Lex Plt — Wed, 14 May 2025 15:48:30 +0000

At work, we've been generating code from swaggers and publishing said generated code. Alas, this requires us to remember to generate the swagger(s), as well as fixing versions of libraries (which means you need to upgrade versions in the server, publish updated generated code, then update your client), see this examples from eikek/sbt-openapi-schema:

import com.github.eikek.sbt.openapi._

val CirceVersion = "0.14.1"
libraryDependencies ++= Seq(
  "io.circe" %% "circe-generic" % CirceVersion,
  "io.circe" %% "circe-parser"  % CirceVersion
)

openapiSpec := (Compile/resourceDirectory).value/"test.yml"
openapiTargetLanguage := Language.Scala
Compile/openapiScalaConfig := ScalaConfig()
    .withJson(ScalaJson.circeSemiauto)
    .addMapping(CustomMapping.forType({ case TypeDef("LocalDateTime", _) =>
      TypeDef("Timestamp", Imports("com.mypackage.Timestamp"))
    }))
    .addMapping(CustomMapping.forName({ case s => s + "Dto" }))

enablePlugins(OpenApiSchema)

The problem

When defining endpoints, it's not uncommon to couple the endpoint and its implementation with a .serverLogic, meaning creating our endpoints relied on the implementation being available (need to instantiate the API, repositories to connect to databases, http clients...).

This made it harder than necessary to write our swaggers to disk:

you needed to compile the app,
run all the services (databases, kafka...),
run the app,
go to http://localhost:8080/swagger/

For the swagger to be generated and written to disk. Otherwise, generated code wouldn't be up to date, which is a problem. A very long procedure, not very convenient, that we used to do once in a while.

Simple solution

We can generate swaggers using libraries like tapir:

val swagger = OpenAPIDocsInterpreter()
  .toOpenAPI(
    tapirEndpoints,
    "my app",
    "v0.0.1"
  )
  .openapi("3.0.3")
  .toYaml

writeSwaggerToFile(swagger, pathToSwaggerFile)

Then we would just have to decouple our Endpoints and their implementation (which made them ServerEndpoints by the way, but you only need Endpoint to generate the OpenAPI spec).

// MyApiEndpoints.scala
class Endpoints {
  protected val booksListingEndpoint: PublicEndpoint[(BooksQuery, Limit, AuthToken), String, List[Book], Any] = 
    endpoint
      .get
      .in(("books" / path[String]("genre") / path[Int]("year")).mapTo[BooksQuery])
      .in(query[Limit]("limit").description("Maximum number of books to retrieve"))
      .in(header[AuthToken]("X-Auth-Token"))
      .errorOut(stringBody)
      .out(jsonBody[List[Book]])

  val plainEndpoints: List[AnyEndpoint] = List(booksListingEndpoint)
}

// MyApiRoutes.scala
class Routes(api: MyApiService) extends Endpoints {
  private val booksListing =
    booksListingEndpoint
      .serverLogic { case (booksQuery, limit, authToken) =>
        api.listBooks(authToken, booksQuery, limit)
      }

  val endpoints: List[ServerEndpoint[Fs2Streams[IO], IO]] = List(
    booksListing
  )
  val routes: HttpRoutes = Http4sServerInterpreter()
    .toRoutes(endpoints)
}

And then find a way to compile and run code calling OpenAPIDocsInterpreter with the new Endpoints().plainEndpoints. Easy right?

Let's over engineer it

Splitting endpoints and server endpoints implementation is the right and easy thing to do, but we can go further. What if we could leverage our build system to generate a swagger for us each time we compile?

Making a sbt plugin

sbt is the de facto build tool in Scala, hence I made a plugin to do the generating for us. A plugin can define a task, which you can then call inside the sbt shell as a command.

import sbt.Keys.*
import sbt.*

object SpecGen extends AutoPlugin {
  object autoImport {
    val Spec = config("spec").extend(Runtime)
    val specGenMain = settingKey[String]("Main class (FQDN) to run")
    val specGenArgs = settingKey[Seq[String]]("Arguments to pass to runner")
    val specGenMake = taskKey[Unit]("run code/resource generation from config")
  }

  import autoImport.*

  override def projectSettings: Seq[Def.Settings[?]] = inConfig(Spec)(Defaults.configSettings ++ Seq(
    specGenMain := "<user defined>",
    specGenArgs := Seq.empty,
    specGenMake := {
      val logger = streams.value.log
      val classPath = Attributed.data((Spec / fullClasspath).value)
      (Spec / runner).value.run(specGenMain.value, classPath, specGenArgs.value, logger).get
    }
  )) :+ (ivyConfigurations := overrideConfigs(Spec)(ivyConfigurations.value))
}

💡 Tip

This small implementation is the bare minimum to register a class, instantiate it, and run it via sbt.

To make our task run after compile we would have to make it return a File and add a resource generator: Compile / resourceGenerators += (Spec / specGenMake).taskValue.

This simple plugin can be enabled on projects as follows:

val `my-api` = (project in file("application/my-api"))
  .settings(...)
  .enablePlugins(SpecGen)
  .settings(
    Spec / specGenMain := "org.myapi.GenerateSwagger"
  )

// we need a project to be able to `publish` the swagger.
// GenerateSwagger would write to the <module>/src/resources/swagger.yaml
val `my-api-swagger` = project in file("modules/my-api-swagger")

And we just have to write a GenerateSwagger class that instanciate Endpoints and call OpenAPIDocsInterpreter on them, to write the resulting yaml to a file!

📝 Note

For now, this small implementation requires the user to run Spec / specGenMake;compile to have the swagger generated and code to be compiled, until I revisit it. For our needs it isn't a huge deal, as we generate and publish swaggers inside our CI/CD environement.

Generating Scala code from a published swagger

How would you generate code from a swagger inside a jar downloaded by sbt?

Using sbt-swaggerinator, the swagger downloader and unpacker, it's quite easy! Add your swagger module as a dependency and let the plugin do the job:

// build.sbt
object Dependencies {
  lazy val swagger = "com.example" % "my-api-swagger_2.13" % "1.0.0"
  lazy val circe = Seq(
    "io.circe" % "circe-core",
    "io.circe" % "circe-generics",
    "io.circe" % "circe-generic-extras"
  ).map(_ %% "0.14.1")
}

lazy val `my-api-generated` = (project in file("modules/my-api-generated"))
  .enablePlugins(OpenApiSchema)
  .enablePlugins(SwaggerinatorSbt)
  .settings(swaggerinatorDependency := Dependencies.swagger)
  .settings(swaggerinatorPackage := Pkg("com.example.my-api.generated"))
  .settings(libraryDependencies ++= Dependencies.circe)

lazy val infrastructure = (project in file("modules/infrastructure"))
  // ...
  .dependsOn(`my-api-generated` % "compile->compile")

Passing the dependency to swaggerinator will let it access the swagger inside it, by unzipping the jar (after all, it's just a ZIP file with another extension). Then the plugin generates code from the swagger, by calling the OpenApiSchema plugin for us.

Originally from lexp.lt

Implementing an Intermediate Representation for ArkScript

Lex Plt — Mon, 14 Oct 2024 07:37:33 +0000

ArkScript is a scripting language, running on a VM. To accomplish this, we had (as of September 2024) a compiler generating bytecode for the virtual machine, receiving an AST from the parser (and a few other passes like name resolution, macro evaluation, name and scope resolution...).

Exploring new optimizations

The only thing we could optimize was the virtual machine and the memory layout of our values, and some very little things directly in the compiler, like tail call optimization. Having implemented computed gotos a few weeks ago, I think I've hit the limit in terms of feasible optimization for this VM.

For a while, a friend tried to push me toward making an intermediate representation for ArkScript. I shrugged it off, saying it was too much work, not really knowing what I would get into and having bigger fish to fry.

Biting the bullet

At the end of September, I stumbled upon a post by Eniko on Mastodon (if you don't follow her already, what are you waiting for?), and the idea of making an IR came back into my mind... and I just started thinking about, but seriously this time.

What were my goals?

Optimizing the bytecode produced by the compiler, so that we could remove useless or redundant instructions ;
Replacing a series of instructions by a single one, more specific, that could do multiple things at once.

Problem: operating directly on bytecode is hard: we either need

to replace instructions with NOP (that would still be decoded and run by the VM, even to do virtually nothing)
to recompute every single jump address after merging or removing instructions (this problem appears with both relative and absolute jumps)

Designing the IR

The IR would have to solve this problem, otherwise it would be useless for its single job: helping to produce better bytecode. Let's see what we can work with:

The compiler job is to flatten the AST (Abstract Syntax Tree, our parsed code represented as a tree that we visit recursively) into a list of instructions. To simplify the calling convention, each function is compiled in a dedicated region that I call a page. Inside a page, each jump is relative to the first instruction, and the bytecode is essentially a uint8_t[][], that we can access using a page pointer and an instruction pointer.

First draft

My first idea was to output a tree of IR instructions instead of a list of instructions. That would still be flatter than the AST, and on paper, it would solve the jump problem as we have jumps only for loops and conditions.

If we use a Lisp-like (ArkScript-like?) syntax, it could look like this

(store a 0)   # a = 0
(setval a 5)  # a = 5
(load_symbol a)
(load_const 0)
(gt)          # (< a 0)
(if
    then...
    else...)

However I didn't really like this idea, it felt like reinventing the wheel, another tree, as we have a non-flat structure to handle a sequence of conditions (if cond (if cond2 ...)).

Second try: getting rid of jumps altogether

This time, we will use a structure very similar if not identical to the bytecode, and get rid of all the JUMP instructions. Taking inspiration from assembly, they will get replaced by labels and gotos in our IR! This way we can add and remove as many instructions as we want, as long as we don't update a label we can still compute its address later and compile our gotos to absolute jumps without any issues.

This is also the easiest solution, as it does not require me to entirely rewrite the compiler: I just have to add a wrapper for the Instruction, that gets compiled to bytecode.

Implementing the IR

The wrapper is small, and was easy to implement, needing only an additional Kind to differentiate final instructions (Opcode and Opcode2Args) and entities that require processing to be compiled to final instructions (Goto, GotoIfTrue, GotoIfFalse all require the attached label to be computed first). The Label is only there to get an address in the bytecode, and won't produce an instruction.

enum class Kind
{
    Label,
    Goto,
    GotoIfTrue,
    GotoIfFalse,
    Opcode,
    Opcode2Args
};

using label_t = std::size_t;

class Entity
{
public:
    explicit Entity(Kind kind);
    explicit Entity(Instruction inst, uint16_t arg = 0);
    Entity(Instruction inst, uint16_t primary_arg, uint16_t secondary_arg);

    // tools to build IR entities easily
    static Entity Label();
    static Entity Goto(const Entity& label);
    static Entity GotoIf(const Entity& label, bool cond);

    [[nodiscard]] Word bytecode() const;
    // getters
    [[nodiscard]] inline label_t label() const { return m_label; }
    [[nodiscard]] inline Kind kind() const { return m_kind; }
    [[nodiscard]] inline Instruction inst() const { return m_inst; }
    [[nodiscard]] inline uint16_t primaryArg() const { return m_primary_arg; }
    [[nodiscard]] inline uint16_t secondaryArg() const { return m_secondary_arg; }

private:
    inline static label_t LabelCounter = 0;

    Kind m_kind;
    label_t m_label { 0 };
    Instruction m_inst { NOP };
    uint16_t m_primary_arg { 0 };
    uint16_t m_secondary_arg { 0 };
};

using Block = std::vector<Entity>;

Instructions in ArkScript

It is also interesting to speak about the instruction representation in ArkScript. An instruction in on four bytes: iiiiiiii pppppppp aaaaaaaa aaaaaaaa.

i represents the instruction bits, 8, giving us 256 different instructions possible
p is for padding, ignored in instructions with a single immediate argument
a represents the bits of the immediate argument, a total of 16 (0 -> 65'535)

Super Instructions can require up to two arguments, which are encoded using the padding: iiiiiiii ssssssss ssssaaaa aaaaaaaa.

we still have our instruction on the same byte,
s represents the bits of the secondary argument, a total of 12 (0 -> 4095)
a represents the bits of the primary argument, a total of 12 (0 -> 4095)

Compiling an IR entity to bytecode

Since some instructions can take two arguments, the instruction-to-bytecode helper had to be updated. Implementation for reference:

struct Word
{
    uint8_t opcode = 0;
    uint8_t byte_1 = 0;
    uint8_t byte_2 = 0;
    uint8_t byte_3 = 0;

    explicit Word(const uint8_t inst, const uint16_t arg = 0) :
        opcode(inst),
        // byte_1 = 0, this is our padding here
        byte_2(static_cast<uint8_t>(arg >> 8)),
        byte_3(static_cast<uint8_t>(arg & 0xff))
    {}

    Word(const uint8_t inst, const uint16_t primary_arg,
         const uint16_t secondary_arg) :
        opcode(inst)
    {
        byte_1 = static_cast<uint8_t>((secondary_arg & 0xff0) >> 4);
        byte_2 = static_cast<uint8_t>(
            (secondary_arg & 0x00f) << 4 | (primary_arg & 0xf00) >> 8
        );
        byte_3 = static_cast<uint8_t>(primary_arg & 0x0ff);
    }
};

The rest is pretty straightforward: instead of having the Compiler output bytecode directly, it now outputs IR entities, and a new IRCompiler has been introduced. All it has to do is map an IR entity to its instruction, and turn it into a Word so that it can be written to disk.

An important step is to compute the labels addresses so that we can generate correct JUMP, POP_JUMP_IF_TRUE and POP_JUMP_IF_FALSE instructions:

uint16_t pos = 0;
std::unordered_map<IR::label_t, uint16_t> label_to_position;
for (auto inst : page)
{
    switch (inst.kind())
    {
        case IR::Kind::Label:
            label_to_position[inst.label()] = pos;
            // the label isn't an instruction,
            // do not update `pos` here
            break;

        default:
            ++pos;
    }
}

Detecting sequence of entities that can be combined

This one was way easier than I thought, all we have to do is iterate on the given IR blocks, and match the current entity and the next one with a known pattern. The only thing to be aware of is jumping over the instructions we managed to fuse, so that we do not push left over instructions in our optimized IR.

void IROptimizer::process(
    const std::vector<IR::Block>& pages,
    const std::vector<std::string>& symbols,
    const std::vector<ValTableElem>& values)
{
    m_symbols = symbols;
    m_values = values;

    for (const auto& block : pages)
    {
        m_ir.emplace_back();
        IR::Block& current_block = m_ir.back();

        std::size_t i = 0;
        const std::size_t end = block.size();

        while (i < end)
        {
            // alias to ease the writing of the rules below:
            const Instruction first = block[i].inst();
            const uint16_t arg_1 = block[i].primaryArg();

            // if we have at least two instructions left,
            // we can try to match for super instructions patterns
            if (i + 1 < end)
            {
                const Instruction second = block[i + 1].inst();
                // only the `primaryArg` is needed as we will check
                // for normal instructions below, which have
                // a single argument
                const uint16_t arg_2 = block[i + 1].primaryArg();

                // LOAD_CONST x
                // LOAD_CONST y
                // ---> LOAD_CONST_LOAD_CONST x y
                if (first == LOAD_CONST && second == LOAD_CONST)
                {
                    current_block.emplace_back(
                        LOAD_CONST_LOAD_CONST, arg_1, arg_2);
                    i += 2;
                }
                // ...
                else
                {
                    // otherwise we should not forget to add the
                    // other instructions to the output IR, we don't
                    // want just the optimzed IR!
                    current_block.emplace_back(block[i]);
                    ++i;
                }
            }
            else
            {
                current_block.emplace_back(block[i]);
                ++i;
            }
        }
    }
}

Performance gain!

Who would have thought that avoiding a series of LOAD_CONST, STORE and using a single LOAD_CONST_STORE instruction would be so beneficial? We are avoiding a push -> pop and immediately putting a value from our constants table inside a variable.

Applying this pattern to increment (LOAD_SYMBOL a, LOAD_CONST 1, ADD becomes INCREMENT a), decrement, and store the head or tail of a list in a variable helps, tremendously according to the benchmarks:

                          |           | 5-c7f632ff   | 6-28999c0f
--------------------------+-----------+--------------+--------------------
 quicksort                | real_time | 0.168728ms   | -0.014 (-8.2280%)
                          | cpu_time  | 0.168515ms   | -0.014 (-8.2479%)
 ackermann/iterations:50  | real_time | 68.31ms      | -7.278 (-10.6545%)
                          | cpu_time  | 68.2342ms    | -7.259 (-10.6384%)
 fibonacci/iterations:100 | real_time | 6.62604ms    | -0.160 (-2.4159%)
                          | cpu_time  | 6.61819ms    | -0.161 (-2.4266%)
 man_or_boy               | real_time | 0.0169651ms  | -0.001 (-7.6834%)
                          | cpu_time  | 0.0160228ms  | -0.000 (-2.3673%)
 builtins                 | real_time | 0.622685ms   | -0.037 (-5.8815%)
                          | cpu_time  | 0.621938ms   | -0.037 (-5.9495%)

The first column, 5-c7f632ff is our reference benchmark (based on ArkScript commit 684ea758), and the second one, 5-ee9ff764, is the result of implementing our IR and IR optimizer. Quite the improvement, we gained at least 2% and at most 10% on every single benchmark!

Originally from lexp.lt

Implementing computed gotos in C++

Lex Plt — Wed, 25 Sep 2024 11:19:49 +0000

A common idiom in virtual machines or state machines is to read data from a list, execute some code depending on the value we read, advance in the list, rinse and repeat. That could be written as:

std::vector<uint8_t> bytecode = readBytecode();
std::size_t pos = 0;
while (pos < bytecode.size())
{
    uint8_t inst = bytecode[pos];
    pos++;

    switch (inst)
    {
        case DO_THIS:
            // ...
            break;
        case DO_THAT:
            // ...
            break;
        // ...
    }
}

While this works, there are other ways that do the same thing but are also better in term of performances. This current approach isn't very branch-predictor friendly because we read data from a vector, select code to execute, break, and repeat. The branch-predictor can not learn what common instructions follow each other.

Definition

A way to solve that is to use computed gotos. We read an instruction, load the next and jump to its code. No more instruction selection, a single stream of code to run -> jump -> repeat, which pleases the branch predictor. It can now learn what instruction Y often follows another instruction X and preload code (even though it can still fail, which degrades performances).

Modifying our code for compute gotos

We'll use the code shown previously as a basis

Using gotos

std::vector<uint8_t> bytecode = readBytecode();
std::size_t pos = 0;
uint8_t inst = bytecode[pos];
{
    dispatch_op:
    switch (inst)
    {
        case DO_THIS:
            // ...
            inst = bytecode[pos];
            pos++;
            goto dispatch_op;
        case DO_THAT:
            // ...
            inst = bytecode[pos];
            pos++;
            goto dispatch_op;
        // ...
    }
}

Here we replaced our while loop with a switch, a label and a goto, nearly achieving the same thing as before. Nearly because we are now loading the next instruction before our goto, and we don't have any if (pos < bytecode.size()) anymore.

[!NOTE]
While we could add an if (end of bytecode) condition before our goto, an easier solution would be to add a special STOP_INTERPRETER instruction, implemented like this:
case STOP_INTERPRETER:
    break;  // or another goto label_end;
            // with label_end after the switch

This code isn't any faster or slower than the previous implementation, it is just another way (though not a recommended one due to the presence of gotos) to write a loop, but that will help us for the next transformations.

Making our code slightly better with macros

Now, we have to add instruction fetching into every case. We could make this easier using macros:

#define FETCH_INSTRUCTION()    \
    do {                       \
        inst = bytecode[pos];  \
        pos++;                 \
    } while (false)
#define DISPATCH_GOTO() goto dispatch_op
#define DISPATCH()        \
    FETCH_INSTRUCTION();  \
    DISPATCH_GOTO()

std::vector<uint8_t> bytecode = readBytecode();
std::size_t pos = 0;
uint8_t inst = bytecode[pos];
{
    dispatch_op:
    switch (inst)
    {
        case DO_THIS:
            // ...
            DISPATCH();
        case DO_THAT:
            // ...
            DISPATCH();
        case STOP_INTERPRETER:
            goto label_end;
        // ...
    }
    label_end:
    // we can't have a label at the end of a block in C++98-20,
    // this only works in C++23 and onward
    do {} while (false);
}

Computed gotos

With a gcc extension, we can take the address of a label, and store it in an array. Using this, we can goto array[index]; and jump at a given label. What if we put one label per instruction now?

#define FETCH_INSTRUCTION()    \
    do {                       \
        inst = bytecode[pos];  \
        pos++;                 \
    } while (false)

#define DISPATCH_GOTO() goto opcodes[inst]
#define TARGET(op) TARGET_##op

#define DISPATCH()        \
    FETCH_INSTRUCTION();  \
    DISPATCH_GOTO()

std::vector<uint8_t> bytecode = readBytecode();
std::size_t pos = 0;
uint8_t inst = bytecode[pos];
{
    const std::array opcodes = {
        &&TARGET_DO_THIS,
        &&TARGET_DO_THAT,
        &&TARGET_STOP_INTERPRETER
    };

    {
        TARGET(DO_THIS)
        {
            // ...
            DISPATCH();
        }
        TARGET(DO_THAT)
        {
            // ...
            DISPATCH();
        }
        TARGET(STOP_INTERPRETER)
        {
            goto label_end;
        }
        // ...
    }
    label_end:
    do {} while (false);
}

Everything together

With some conditions and more macros, we could have a dual implementation, generating a switch or a computed gotos table:

#define FETCH_INSTRUCTION()    \
    do {                       \
        inst = bytecode[pos];  \
        pos++;                 \
    } while (false)

#if USE_COMPUTED_GOTO
#  define DISPATCH_GOTO() goto opcodes[inst]
#  define TARGET(op) TARGET_##op
#else
#  define DISPATCH_GOTO() goto dispatch_op
#  define TARGET(op) case op:
#end

#define DISPATCH()        \
    FETCH_INSTRUCTION();  \
    DISPATCH_GOTO()

std::vector<uint8_t> bytecode = readBytecode();
std::size_t pos = 0;
uint8_t inst = bytecode[pos];
{
#if !USE_COMPUTED_GOTO
    dispatch_op:
    switch (inst)
#else
    const std::array opcodes = {
        &&TARGET_DO_THIS,
        &&TARGET_DO_THAT,
        &&TARGET_STOP_INTERPRETER
    };
#end
    {
        TARGET(DO_THIS)
        {
            // ...
            DISPATCH();
        }
        TARGET(DO_THAT)
        {
            // ...
            DISPATCH();
        }
        TARGET(STOP_INTERPRETER)
        {
            goto label_end;
        }
        // ...
    }
    label_end:
    do {} while (false);
}

Results

I've implemented this in ArkScript, a small scripting language I've been working on for a few years now, and this has yielded about a 10% performance improvement:

Machine (M1 MBP):

Run on (8 X 24 MHz CPU s)
CPU Caches:
- L1 Data 64 KiB
- L1 Instruction 128 KiB
- L2 Unified 4096 KiB (x8)

Before:

Load Average: 3.62, 2.42, 2.46
---------------------------------------------------------------------------
Benchmark                                 Time             CPU   Iterations
---------------------------------------------------------------------------
quicksort                             0.223 ms        0.222 ms         3125
ackermann/iterations:50                97.0 ms         96.9 ms           50
fibonacci/iterations:100               9.23 ms         9.22 ms          100

After:

Load Average: 2.87, 2.73, 3.07
---------------------------------------------------------------------------
Benchmark                                 Time             CPU   Iterations
---------------------------------------------------------------------------
quicksort                             0.218 ms        0.218 ms         3231
ackermann/iterations:50                88.9 ms         88.9 ms           50
fibonacci/iterations:100               8.58 ms         8.57 ms          100

Sources

The Design & Implementation of the CPython Virtual Machine

Originally from lexp.lt

Adding short-circuiting in a bytecode interpreter

Lex Plt — Mon, 16 Sep 2024 13:44:51 +0000

In the previous article, we saw how to compile functions and handle their scopes. We also saw how to optimize a certain kind of function calls, the tail call ones in Understanding tail call optimization, now we are going to see yet another optimization, this time on conditions and expression evaluation.

Basic way to deal with conditionals

Following the previous article(s), we could implement and / or as follows:

# a and b
LOAD a
LOAD b
AND
# foo() and bar()
LOAD foo
CALL 0
LOAD bar
CALL 0
AND

As you can see, each argument have to be evaluated before calling the operator, which is not something we might want! In mainstream languages like C, C++, Java, Python... the expression a and b would evaluate b only if a is true. If a is false, no need to evaluate the rest of the expression: it will be false. Same thing goes for or, if a is true, no need to evaluate the rest of the expression: it will be true.

Understanding how short-circuiting works

What we want is evaluate arguments one at a time in an expression, and immediately stop if we have a false in an and expression, or true in an or expression. In Python you could write it like this:

if a and b:
    print("hello")
# vvv
if a:
    if b:
        print("hello")
# else: ...

# -----------------

if a or b:
    print("hello")
# vvv
if a:
    print("hello")      # <-+--- this is exactly the same code,
else:                   #   |    actually not duplicated once
    if b:               #   |    compiled.
        print("hello")  # <-/

(and) We check if a is true, if not do nothing. Otherwise, evaluate b and act accordingly.
(or) We check if a is true and execute our code. Otherwise evaluate b and if true execute our code.

Implementation in bytecode

Let's see how and is implemented in ArkScript (as of 16/09/2024):

LOAD_SYMBOL a
DUP
POP_JUMP_IF_FALSE (after)  ---`
POP                           |
LOAD_SYMBOL b                 |
                  <-----------+

We load our a variable as before and duplicate it
We duplicate it for later use
We pop the duplicate, if it is false we jump after the expression, on the next instruction (which could be a store or another compare ; thanks to the duplicate, we still have the false value here at the end
If it is true, we pop the original value, we don't need it anymore and just load b. As in 3. we continue with no special treatment with the next instruction, now having our boolean loaded to compare it, store it...

And that's it, we don't have to have a specific implementation to handle if a and b and val = a and b separately, as we jump on the next instruction, which might be a POP_JUMP_IF_FALSE in the case of a condition (to avoid executing the code of the condition), or a STORE in case of a variable assignment.

[!NOTE]
Implementing or would be practically identical, apart from the POP_JUMP_IF_FALSE instruction that would be a POP_JUMP_IF_TRUE!

Originally from lexp.lt

Comparing Python and ArkScript asynchronous models

Lex Plt — Tue, 03 Sep 2024 21:02:29 +0000

Python has received a lot of attention lately. The 3.13 release, planned for October this year, will begin the huge work of removing the GIL. A prerelease is already out for the curious users who want to try a (nearly) GIL-less Python.

All this hype made me dig in my own language, ArkScript, as I had a Global VM Lock, too, in the past (added in version 3.0.12, in 2020, removed in 3.1.3 in 2022), to compare things and force me to dig deeper into the how and why of the Python GIL.

Definitions

To get started, let's define what a GIL (Global interpreter lock) is:

A global interpreter lock (GIL) is a mechanism used in computer-language interpreters to synchronize the execution of threads so that only one native thread (per process) can execute basic operations (such as memory allocation and reference counting) at a time.

Wikipedia — Global interpreter lock

Concurrency is when two or more tasks can start, run and complete in overlapping time periods, but that doesn't mean they will both be running simultaneously.
Parallelism is when tasks literally run at the same time, eg on a multicore processor.

For an in-depth explanation, check this Stack Overflow answer.

Python's GIL

The GIL can increase the speed of single-threaded programs because you don't have to acquire and release locks on all data structures: the entire interpreter is locked so you are safe by default.

However, since there is one GIL per interpreter, that limits parallelism: you need to spawn a whole new interpreter in a separate process (using the multiprocessing module instead of threading) to use more than one core! This has a greater cost than just spawning a new thread because you now have to worry about inter-process communication, which adds a non-negligible overhead (see GeekPython — GIL Become Optional in Python 3.13 for benchmarks).

How does it affect Python's async?

In the case of Python, it lies down to the main implementation, CPython, not having thread-safe memory management. Without the GIL, the following scenario would generate a race condition:

create a shared variable count = 5
thread 1: count *= 2
thread 2: count += 1

If thread 1 runs first, count will be 11 (count * 2 = 10, then count + 1 = 11).

If thread 2 runs first, count will be 12 (count + 1 = 6, then count * 2 = 12).

The order of execution matters, but even worse can happen: if both threads read count at the same time, one will erase the result of the other, and count will be either 10 or 6!

Overall, having a GIL makes the (CPython) implementation easier and faster in general cases:

faster in the single-threaded case (no need to acquire/release a lock for every operation)
faster in the multi-threaded case for IO-bound programs (because those happen outside the GIL)
faster in the multi-threaded case for CPU-bound programs that do their compute-intensive work in C (because the GIL is released before calling the C code)

It also makes wrapping C libraries easier, because you're guaranteed thread-safety thanks to the GIL.

The downside is that your code is asynchronous as in concurrent, but not parallel.

[!NOTE]
Python 3.13 is removing the GIL!

The PEP 703 added a building configuration --disable-gil so that upon installing Python 3.13+, you can benefit from performance improvements in multithreaded programs.

Python async/await model

In Python, functions have to take a color: they are either "normal" or "async". What does this mean in practice?

>>> def foo(call_me):
...     print(call_me())
... 
>>> async def a_bar():
...     return 5
... 
>>> def bar():
...     return 6
... 
>>> foo(a_bar)
<coroutine object a_bar at 0x10491f480>
<stdin>:2: RuntimeWarning: coroutine 'a_bar' was never awaited
RuntimeWarning: Enable tracemalloc to get the object allocation traceback
>>> foo(bar)
6

Because an asynchronous function does not return a value immediately, but rather invokes a coroutine, we can't use them everywhere as callbacks, unless the function we are calling is designed to take async callbacks.

We get a hierarchy of functions, because "normal" functions need to be made async to use the await keyword, needed to call asynchronous functions:

         can call
normal -----------> normal

         can call
async -+-----------> normal
       |
       .-----------> async

Apart from trusting the caller, there is no way to know if a callback is async or not (unless you try to call it first inside a try/except block to check for an exception, but that's ugly).

ArkScript parallelism

In the beginning, ArkScript was using a Global VM Lock (akin to Python's GIL), because the http.arkm module (used to create HTTP servers) was multithreaded and it caused problems with ArkScript's VM by altering its state through modifying variables and calling functions on multiple threads.

Then in 2021, I started working on a new model to handle the VM state so that we could parallelize it easily, and wrote an article about it. It was later implemented by the end of 2021, and the Global VM Lock was removed.

ArkScript async/await

ArkScript does not assign a color to async functions, because they do not exist in the language: you either have a function or a closure, and both can call each other without any additional syntax (a closure is a poor man object, in this language: a function holding a mutable state).

Any function can be made async at the call site (instead of declaration):

(let foo (fun (a b c)
    (+ a b c)))

(print (foo 1 2 3))  # 6

(let future (async foo 1 2 3))
(print future)          # UserType<0, 0x0x7f0e84d85dd0>
(print (await future))  # 6
(print (await future))  # nil

Using the async builtin, we are spawning a std::future under the hood (leveraging std::async and threads) to run our function given a set of arguments. Then we can call await (another builtin) and get a result whenever we want, which will block the current VM thread until the function returns.

Thus, it is possible to await from any function, and from any thread.

The specificities

All of this is possible because we have a single VM that operates on a state contained inside an Ark::internal::ExecutionContext, which is tied to a single thread. The VM is shared between the threads, not the contexts!

        .---> thread 0, context 0
        |            ^
VM <----+       can't interact
        |            v
        .---> thread 1, context 1

When creating a future by using async, we are:

copying all the arguments to the new context,
creating a brand new stack and scopes,
finally create a separate thread.

This forbids any sort of synchronization between threads since ArkScript does not expose references or any kind of lock that could be shared (this was done for simplicity reasons, as the language aims to be somewhat minimalist but still usable).

However this approach isn't better (nor worse) than Python's, as we create a new thread per call, and the number of threads per CPU is limited, which is a bit costly. Luckily I don't see that as problem to tackle, as one should never create hundreds or thousands of threads simultaneously nor call hundreds or thousands of async Python functions simultaneously: both would result in a huge slow down of your program.

In the first case, this would slowdown your process (even computer) as the OS is juggling to give time to every thread ; in the second case it is Python's scheduler that would have to juggle between all of your coroutines.

[!NOTE]
Out of the box, ArkScript does not provide mechanisms for thread synchronization, but even if we pass a UserType (which is a wrapper on top of type-erased C++ objects) to a function, the underlying object isn't copied.

With some careful coding, one could create a lock using the UserType construct, that would allow synchronization between threads.
(let lock (module:createLock))
(let foo (fun (lock i) {
  (lock true)
  (print (str:format "hello {}" i))
  (lock false) }))
(async foo lock 1)
(async foo lock 2)

Conclusion

ArkScript and Python use two very different kinds of async / await: the first one requires the use of async at the call site and spawns a new thread with its own context, while the latter requires the programmer to mark functions as async to be able to use await, and those async functions are coroutines, running in the same thread as the interpreter.

Sources

Originally from lexp.lt

Finding bugs by fuzzing your code

Lex Plt — Sun, 06 Nov 2022 12:12:59 +0000

If you have ever worked on a large scale project, you know that finding and tracking bugs can be very tedious and lengthy.

Did you know it could be automated? There are multiple ways to achieve this, starting with unit & integration tests run regularly to detect regressions, end-to-end tests to ensure a functionality is behaving as intended, and much more.

However, writing those tests is also a lengthy process, and you miss some hard to find bugs. We are going to focus on fuzzing, an automated crash detection process.

What is fuzzing?

According to wikipedia, fuzzing is an automated software testing technique that involves providing invalid, unexpected, or random data as inputs to a computer program (https://en.wikipedia.org/wiki/Fuzzing).

Given a set of inputs your program can work on, a fuzzer will generate as much diverging data as possible and feed it to your program, recording each crash.

Fuzzing in practice

If you don't know me yet, I am the developper of ArkScript, an easy to embed scripting language, and I have worked on dozen of new functionalities this past year. However, this can (and it has) introduce bugs, sometimes quite tricky to find.

Fuzzing comes to the rescue here! I didn't want (nor had time) to write thousands of tests by hand, so I just wrote the basic tests, checking that every good input leads to the expected output. What was missing was the "bad input leads to bad output" kind of tests.

Introducing AFL++

AFL++ is a superior fork of AFL (American Fuzzy Lop), a fuzzer originally developed by Google.

Here is how it operates:

It is very easy to use, you have to recompile your project using afl-cc and/or afl-c++, give it an input corpus, and let it work for you until you are satisfied.

Generating an input corpus

Since I wanted to fuzz a programming language, my input corpus was easy to put together: code samples, parts of the standard library, some tests files.

The process is as follows:

given the corpus, we want to generate an unique corpus to remove inputs from the corpus that do not produce a new path/coverage in the target
minimizing the corpus: the shorter the input files that still traverse the same path within the target, the better the fuzzing will be.

# step 1)
afl-cmin -i fuzzing/corpus -o fuzzing/unique -- ${buildFolder}/arkscript @@ -L ./lib

mkdir -p fuzzing/input
cd fuzzing/unique

# step 2)
for i in *; do
  afl-tmin -i "$i" -o "../input/$i" -- ../../${buildFolder}/arkscript @@ -L ../../lib
done

You may have noticed the -- ${buildFolder}/arkscript @@ -L ./lib bit: this is the command to run the inputs against, with @@ being the filename of the input generated by AFL++.

Then we can run the fuzzer as follows, and get crashes:

afl-fuzz -i fuzzing/input -o fuzzing/output -s 0 -m 64 -- ${buildFolder}/arkscript @@ -L ./lib

The -s 0 is here to set the RNG seed to 0, to be able to reproduce RNG based crashes more easily ; every crash will be stored under fuzzing/output/.

The -m 64 sets a hard limit of 64MB of RAM for the target so that memory leaks can be more easily detected, and it will prevents potential out-of-memory problem for your computer. I tried to run with no limit, and sure enough my system crashed after 15 minutes (out of memory). I then played around with -m value, 8MB is not enough and it prevents my target to starts.

And here we are, the fuzzer is running and finding bugs for us.

Analysing crashes

Now comes the hard part, reducing the input to find the smallest input sample which still generates the bug. Oftentimes, this has to be done by hand, and it is a tedious process, but finding those buggy inputs by hand would have taken much more time, so it's still a win!

AFL++ has tools to minimize the crashes, helping you to find the bugs:

afl-tmin -i fuzzing/output/main/crashes/id... -o fuzzing/minimized_result -- ./build/arkscript @@ -L ./lib

Once you have your smallest input possible for a given crash, and you have fixed it, it is a good idea to keep it somewhere to be able to run the next version(s) of your program on it and see if it is still fixed. This has personally helped me starting a collection of bad inputs, to check in my tests if they are correctly handled.

Some things to note about fuzzing:

a lot of crashes can be very similar, when the AFL++ fuzzer finds a bugs it will use it and derive it to find others
because of 1) you might want to run multiple fuzzers at the same time, it will find more bugs, plus it was designed to work that way (one master instance and multiple variants)
you don't have to limit the memory allocated to each fuzzer, but if you don't you might exhaust all your RAM
a fuzzer can run for a very long time and not find anything, that doesn't mean your program is bug free!

Because fuzzing can require a lot of time and ressources, you might want to run those tests once in a while, for example for every new release instead of for every commit or test added.

Originally from lexp.lt

Making your project available through Homebrew

Lex Plt — Wed, 07 Sep 2022 14:57:19 +0000

As software developers, having our projects available easily to anyone is a goal, but it can be hard to achieve. Using package managers like apt, pacman or brew has become an industry standard (compared to wget + compile it yourself + install it), but publishing a project on it can be quite tedious.

In this article, we will go through the basics of creating a tap for homebrew (available on both Linux and MacOS).

Creating a tap

A tap is an external source of formulae (installation scripts) for homebrew. Using them requires to add them with brew tap user/repo. It is much easier than submitting a new formula to homebrew/core and waiting for it be approved (or rejected).

Creating a new tap is as easy as

# creates a folder under /opt/homebrew/Library/Taps/xxx/xxx
brew tap-new arkscript-lang/homebrew-arkscript

# generates a formula in your newly created tap
brew create --cmake \
    'https://github.com/ArkScript-lang/Ark.git' \
    --HEAD \
    --set-name 'arkscript@3.3.0' \
    --set-version '3.3.0' \
    --tap arkscript-lang/homebrew-arkscript

I specified the type of build needed with --cmake (other templates are available for crystal, go, meson, python, node, ruby, perl and rust), the URL of my git repository (--HEAD is here to tell brew that the URL is a repo, not a file). With set-name I gave the formula's name, and then its version with set-version. Finally, with tap I gave it a repository (the user and repo name will have to match on GitHub/GitLab/etc).

Editing your formula

Once this last command has been entered you will be entering your selected editor (for me it's vim) to edit the formula:

# Documentation: https://docs.brew.sh/Formula-Cookbook
#                https://rubydoc.brew.sh/Formula
# PLEASE REMOVE ALL GENERATED COMMENTS BEFORE SUBMITTING YOUR PULL REQUEST!
class ArkscriptAT330 < Formula
  desc ""
  homepage ""
  license ""
  head "https://github.com/ArkScript-lang/Ark.git"

  depends_on "cmake" => :build

  def install
    # ENV.deparallelize  # if your formula fails when building in parallel
    system "cmake", "-S", ".", "-B", "build", *std_cmake_args
    system "cmake", "--build", "build"
    system "cmake", "--install", "build"
  end

  test do
    # `test do` will create, run in and delete a temporary directory.
    #
    # This test will fail and we won't accept that! For Homebrew/homebrew-core
    # this will need to be a test that verifies the functionality of the
    # software. Run the test with `brew test arkscript@3.3.0`. Options passed
    # to `brew install` such as `--HEAD` also need to be provided to `brew test`.
    #
    # The installed folder is not in the path, so use the entire path to any
    # executables being tested: `system "#{bin}/program", "do", "something"`.
    system "false"
  end
end

Note that because we used --HEAD this formula will only work with brew install --head. To remedy this, we will add an url:

class ArkscriptAT330 < Formula
  desc ""
  homepage ""
  url "https://github.com/ArkScript-lang/Ark.git", tag: "v3.3.0"
  license ""
  head "https://github.com/ArkScript-lang/Ark.git"

It has to go right before the license field, which itself has to follow the SPDX license naming convention (https://spdx.org/licenses/), eg MPL-2.0.

Custom steps

Once every field has been filled, and default comments have been removed, we can play a little more with the formula's steps.

For testing, I added a post_install step:

class ArkscriptAT330 < Formula
  # ...

  def post_install
    ohai "ℹ️  Add ARKSCRIPT_PATH=" + lib + "/Ark/ to your bashrc/zshrc"
  end

  # ...

This basically tells the user to add an environment variable to their shell configuration file for the project to work with ohai (prints a message). There is odie as well to display an error message and opoo for warnings. You can find more steps and fields to customize your formula here: https://rubydoc.brew.sh/Formula.html.

Checking for errors

Now that you have written a formula, let's test it with

brew audit --new arkscript@3.3.0

If it returns nothing, then you are good to go and you can publish your tap.

You should build your formula to check for misconfiguration and errors using

brew install --build-from-source <user>/<repo>/<formula>

If you need to do the test again, just do a brew remove <formula>.

Publishing a tap

First, you will have to create a repository on GitHub/GitLab if that wasn't already done, with the following name: homebrew-<tap name>. The prefix is mandatory.

Then, you can add a remote to your tap with

git remote add origin git@github.com:<user>/<repo>.git

Commit your work, and you can now push to your repository and voilà!

Using your tap

Using brew tap <user>/<repo>, you will add your tap to brew list of taps. Then your formulae will be available either as brew install <formula> or brew install <user>/<repo>/<formula> if the name is already taken in homebrew core.

Going further

Now that you have published your formula in a tap, and made your project easily available to anyone, you might want to go further and check this complete guide: https://docs.brew.sh/Formula-Cookbook

Originally from lexp.lt

Understanding tail-call optimization

Lex Plt — Sun, 20 Feb 2022 17:58:41 +0000

Lately, I've been working on optimizations for my language, ArkScript, and finally take some time to add tail-call optimization to my compiler.

In this article, I'll explain what is tail-call optimization, why it seems easy to implement, and how to do it.

Definition

Tail-call optimization is a method to optimize some recursive functions so that we don't have to create a bunch of stack frames to execute, and reuse only one. This leads to less memory being used and more performances, as we don't have to create and destroy a bunch of stack frames.

The functions we can optimize with said methods are the tail recursive ones:

let factorial = (n, acc) {
    if (n <= 1)
        return acc
    else
        return factorial(n - 1, n * acc)
}

print(factorial(10, 1))

This is called a tail recursive function because the last call of the function is a call to itself.

Note that our factorial function takes an additional parameter, an accumulator, because the following implementation wouldn't be tail recursive:

let factorial = (n) {
    if (n <= 1)
        return 1
    else
        return n * factorial(n - 1)
}

as the last operation of the function isn't a call to itself, but the multiplication between n and factorial(n - 1).

Why can we optimize tail recursive functions?

The last thing these functions are doing is a call to themselves, thus all previous state can be discarded as it's either being passed as arguments to the function, or not being used at all. Thus, we don't have to keep a state somewhere in case the function returns and need something from this state (which is needed in the version returning n * factorial(n - 1)).

Thus, we can rewrite the tail recursive functions with loops:

let factorial = (n, acc) {
    while (true) {
        if (n <= 1)
            return acc

        // we replace the recursive call with this
        acc = n * acc
        n = n - 1
    }
}

How to implement this optimization?

When we look at the above snippet, it seems that replace the last function call of a function by its argument list and the values, and adding a jump to the beginning of the function, is all we need to do. In fact, this is right. The hard part is identifying a tail call.

Given a recursive compiler on an abstract syntax tree, you'll need:

to keep track of the name of the current variable being compiled (here we need to know the variable name is factorial when we are compiling its body)
to know if the current node will be returned or not (if it's the value given to the return keyword)

The first part is quite easy, just send another argument to compile(node) when compiling a variable definition. The second one is equally easy, add two arguments to your handleFunctionCall(node) to tell it the name of the current variable (if any) and if the node is going to be returned or not.

Then the implementation is as simple as this:

void Compiler::handleFunctionCall(const Node& node, const std::string& var_name, bool is_returned)
{
    // checking if the function we are calling has the same
    // name as the current function being compiled
    if (node.constList()[0].string() == var_name && is_returned)
    {
        // push the arguments in reverse order
        // because our calling convention is arg0, arg1...
        // but our stack will handle them in a LIFO fashion
        for (std::size_t i = node.constList().size() - 1; i >= n; --i)
            compile(x.constList()[i]);

            // jump to the top of the function
            bytecode.push_back(Instruction::JUMP);
            bytecode.pushNumber(0_u16);
    }
    else
    {
        // normal function call
    }
}

The diff between the old bytecode and the new should be as follows:

POP, STORE in n
POP, STORE in acc
LOAD n
LOAD_CONST 0  # 1
LE
POP_JUMP_IF_TRUE &if
# else:
- LOAD n               # |- computing acc * n
- LOAD acc             # |
- MUL                  # |-------------------
+ LOAD n
+ LOAD_CONST 0  # 1
+ SUB
- LOAD n               #   |- computing n - 1
- LOAD_CONST 0  # 1    #   |
- SUB                  #   |-----------------
+ LOAD n
+ LOAD acc
+ MUL
- LOAD factorial
- CALL 2
+ JUMP 0             # jump to the top of the function
JUMP &end
# if:
LOAD acc
# end:
RET

(blocks were named &block in the example, but those labels aren't in the final bytecode, it's just to clarify)

If your language doesn't use a return keyword, you might run into some trouble (so did I) when trying to identify the returning node of your functions.

What did was the following:

add a flag to all the compile_* methods I have to know if the current node is terminal or not
the only methods setting this to true is my compile_function, in charge of compiling the body of a function
then I alter this flag based on two things:
- if we are compiling a block (with multiple subnodes), then all the nodes except the last one are non terminal ; for the last one, the flag is passed as is
- if we are compiling a condition (if block), then the flag is passed as is to both branches, then and else, since both can be terminal depending on the condition

Finally, instead of checking for a is_returned I checked for a is_terminal. You can find the complete implementation of this implementation here.

Originally from lexp.lt