DEV Community: Zachery Yee

Introduce MoonBit AI and Deploy DeepSeek-R1 Locally into it

Zachery Yee — Tue, 18 Feb 2025 10:13:48 +0000

MoonBit is an emerging programming language optimized for WebAssembly, prioritizing small executable sizes without compromising performance. It combines a statically typed, lightweight object-functional hybrid approach, supported by a smart compiler to optimize the entire program at once. MoonBit also targets JavaScript and native backend. By describing itself as a "coding platform", MoonBit team is working on an integrated toolchain that includes an IDE, build system, and the MoonBit AI coding assistant embedded within the IDE.

MoonBit AI is currently capable of generating code, tests, documentations, and offering suggestions on fixing errors and improving code quality. It can be quite handy for those who work on MoonBit projects, but not for other languages. The developer of MoonBit reveals on their Discord channel that MoonBit AI is trained only with MoonBit.

While working on my MoonBit projects, I use MoonBit AI commands /test and /doc the most to save time from writing tedious tests and documentations. It turns out that the MoonBit team emphasizes the testing experience a lot by providing a built-in testing framework in its early stage. MoonBit AI will also verify the generated inline tests with type checking.

The /generate command, used to generate MoonBit code, is still in development and may not be as stable due to the language's early stage and relatively limited codebase. It is worth noting that MoonBit might be currently the most developed language for LLMs. The language and model are designed to work together. I look forward to the complete version of MoonBit AI when the language reaches 1.0 and grows a greater ecosystem.

This article will provide a step-by-step guide on how to deploy Deepseek R1 into MoonBit AI locally.

Obtain a DeepSeek API Key

Visit the DeepSeek official website, and click on the “API Platform” in the top-right corner.

Select “API Keys” from the left-side menu to enter the API key management page.

Click “Create new API key” at the bottom of the page.

In the pop-up window, enter a name for the key and click “Create API key”.

Save it for later use.

Configure DeepSeek in MoonBit AI

Open VSCode and press Ctrl + P to open the command palette.

Search for “Preferences: Open User Settings (JSON)” and open the settings file.

Add the following configuration at the bottom, replacing <your-api-key-here> with the API key obtained in the previous step:

{
  // ...
  "moonbit.ai.models": [
    {
      "name": "DeepSeek R1",
      "baseUrl": "https://api.deepseek.com",
      "apiKey": "<your-api-key-here>", // Replace with your actual API key
      "model": "deepseek-reasoner"
    }
  ]
}

After saving the settings, your configuration should look like this:

Using MoonBit AI for Documentation Generation

To generate documentation for a function using MoonBit AI:

First open your .mbt project, and click the rabbit icon on the function you want to generate documents.

In the drop-down menu, select “/doc Generate documentation for this function”.

A new window will open on the right side of the editor, displaying the documentation generation progress.

Once complete, the generated documentation will appear on the right side. To ensure the documentation generated is valid, MoonBit AI verifies the output at the same time. A green "Verified" suggests the docs pass the test. If not, MoonBit AI will also show you errors in red.

Click “Insert” to add the documentation to your code.

The final code will now include the newly generated documentation.

Conclusion

That’s it. Now you’ve deployed Deepseek R1 into MoonBit AI. Feel free to play with it!

If you want to explore more about MoonBit and its AI tool, it’s worth noting that MoonBit is still in its pre-1.0 phase, and official documentation for MoonBit AI features is not yet available. To stay updated on MoonBit AI, you might need to follow their release notes or check out demonstration videos of MoonBit AI’s capabilities on MoonBit’s Twitter and YouTube channels. As the language and its toolchain continue to develop, I believe MoonBit AI will become an even more powerful asset for MoonBit developers.

Implement Myers diff with MoonBit

Zachery Yee — Mon, 26 Aug 2024 06:18:32 +0000

Have you ever used the Unix tool diff? In short, it is a tool for comparing the differences between two text files. What's more, Unix has a tool called patch.

Nowadays, few people manually apply patches to software packages, but diff still retains its usefulness in another area: version control systems. It's quite handy to have the function of being able to see what changes have been made to source code files after a particular commit (and highlighted with different colors). Take the most popular version control system today, git, as an example:

diff --git a/main/main.mbt b/main/main.mbt
index 99f4c4c..52b1388 100644
--- a/main/main.mbt
+++ b/main/main.mbt
@@ -3,7 +3,7 @@

 fn main {
   let a = lines("A\nB\nC\nA\nB\nB\nA")
-  let b = lines("C\nB\nA\nB\nA\nC")
+  let b = lines("C\nB\nA\nB\nA\nA")
   let r = shortst_edit(a, b)
   println(r)
 }

But how exactly do we calculate the differences between two text files?

git's default diff algorithm was proposed by Eugene W. Myers in his paper An O(ND) Difference Algorithm and Its Variations. This paper mainly focuses on proving the correctness of the algorithm. In the following text, we will understand the basic framework of this algorithm in a less rigorous way and use MoonBit to write a simple implementation.

Defining "Difference" and Its Measurement Criteria

When we talk about the "difference" between two text files, what we are actually referring to is a series of editing steps that can transform text a into text b.

Assume the content of text a is

A
B
C
A
B
B
A

Assume the content of text b is

C
B
A
B
A
C

To transform text a into text b, the simplest edit sequence is to delete each character in a (indicated with a minus sign) and then insert each character in b (indicated with a plus sign).

- A
- B
- C
- A
- B
- B
- A
+ C
+ B
+ A
+ B
+ A
+ C

But such a result might not be very helpful for programmers reading the code. The following edit sequence is much better, at least it is shorter.

- A
- B
  C
+ B
  A
  B
- B
  A
+ C

In fact, it is one of the shortest edit sequences that can transform text a into text b, with 5 operations. If we only measure the length of the edit sequence, this result is satisfactory. But when we look at the various programming languages, we find that there are other metrics that are equally important for user experience. Let's look at the following examples:

// good quality
  struct RHSet[T] {
    set : RHTable[T, Unit]
  }
+ 
+ fn RHSet::new[T](capacity : Int) -> RHSet[T] {
+  let set : RHTable[T, Unit]= RHTable::new(capacity)
+  { set : set }
+ }


// bad quality
  struct RHSet[T] {
    set : RHTable[T, Unit]
+ }
+ 
+ fn RHSet::new[T](capacity : Int) -> RHSet[T] {
+  let set : RHTable[T, Unit]= RHTable::new(capacity)
+  { set : set }
  }

When we insert a new function definition at the end of a file, the calculated edit sequence should ideally locate the changes at the end. In similar cases, when there are both deletions and insertions, it is best not to calculate an edit sequence that interleaves these two operations. Here's another example.

Good:   - one         Bad:    - one
        - two                 + four
        - three               - two
        + four                + five
        + five                + six
        + six                 - three

Myers' diff algorithm can fulfill all those requirements. It is a greedy algorithm that skips over matching lines whenever possible (avoiding inserting text before {), and it also tries to place deletions before insertions, avoiding the latter situation.

Algorithm Overview

The basic idea in Myers' paper is to construct a grid graph of edit sequences and then search for the shortest path on this graph. Using the previous example a = ABCABBA and b = CBABAC, we create an (x, y) coordinate grid.

    0     1     2     3     4     5     6     7

0   o-----o-----o-----o-----o-----o-----o-----o
    |     |     | \   |     |     |     |     |
    |     |     |  \  |     |     |     |     |   C
    |     |     |   \ |     |     |     |     |
1   o-----o-----o-----o-----o-----o-----o-----o
    |     | \   |     |     | \   | \   |     |
    |     |  \  |     |     |  \  |  \  |     |   B
    |     |   \ |     |     |   \ |   \ |     |
2   o-----o-----o-----o-----o-----o-----o-----o
    | \   |     |     | \   |     |     | \   |
    |  \  |     |     |  \  |     |     |  \  |   A
    |   \ |     |     |   \ |     |     |   \ |
3   o-----o-----o-----o-----o-----o-----o-----o
    |     | \   |     |     | \   | \   |     |
    |     |  \  |     |     |  \  |  \  |     |   B
    |     |   \ |     |     |   \ |   \ |     |
4   o-----o-----o-----o-----o-----o-----o-----o
    | \   |     |     | \   |     |     | \   |
    |  \  |     |     |  \  |     |     |  \  |   A
    |   \ |     |     |   \ |     |     |   \ |
5   o-----o-----o-----o-----o-----o-----o-----o
    |     |     | \   |     |     |     |     |
    |     |     |  \  |     |     |     |     |   C
    |     |     |   \ |     |     |     |     |
6   o-----o-----o-----o-----o-----o-----o-----o


       A     B     C     A     B     B     A

The upper left of this grid is the starting point (0, 0), and the lower right is the endpoint (7, 6). Moving one step right along the x-axis deletes the corresponding character in a, moving one step down along the y-axis inserts the corresponding character in b, and diagonal lines indicate matching characters that can be skipped without triggering any edits.

Before writing the actual search code, let's manually perform two rounds of searching:

The first round starts at (0, 0) and moves one step to reach (0,1) and (1,0).
The second round starts at (0,1) and (1,0). From (0,1), moving down reaches (0,2), but there is a diagonal line leading to (1,3), so the final point is (1,3).

The entire Myers algorithm is based on this kind of breadth-first search.

Implementation

We have outlined the basic idea, now it's time to consider the design in detail. The input to the algorithm is two strings, but the search needs to be conducted on a graph. It's a waste of both memory and time to construct the graph and then search it.

The implementation of the Myers algorithm adopts a clever approach by defining a new coordinate k = x - y.

Moving right increases k by one.
Moving left decreases k by one.
Moving diagonally down-left keeps k unchanged.

Let's define another coordinate d to represent the depth of the search. Using d as the horizontal axis and k as the vertical axis, we can draw a tree diagram of the search process.

    |      0     1     2     3     4     5
----+--------------------------------------
    |
 4  |                             7,3
    |                           /
 3  |                       5,2
    |                     /
 2  |                 3,1         7,5
    |               /     \     /     \
 1  |           1,0         5,4         7,6
    |         /     \           \
 0  |     0,0         2,2         5,5
    |         \                       \
-1  |           0,1         4,5         5,6
    |               \     /     \
-2  |                 2,4         4,6
    |                     \
-3  |                       3,6

You can see that in each round of searching, k is strictly within the range [-d, d] (because in one move, it can at most increase or decrease by one from the previous round), and the k values between points have an interval of 2. The basic idea of Myers' algorithm comes from this idea: searching by iterating over d and k. Of course, it also needs to save the x coordinates of each round for use in the next round of searching.

Let's first define the Line struct, which represents a line in the text.

struct Line {
  number : Int // Line number
  text : String // Does not include newline
} derive(Debug, Show)

fn Line::new(number : Int, text : String) -> Line {
  Line::{ number : number, text : text }
}

Then, define a helper function that splits a string into Vec[Line] based on newline characters. Note that line numbers start from 1.

fn lines(str : String) -> @vec.Vec[Line] {
  let mut line_number = 0
  let buf = Buffer::make(50)
  let vec = @vec.Vec::new()
  for i = 0; i < str.length(); i = i + 1 {
    let ch = str[i]
    buf.write_char(ch)
    if ch == '\n' {
      let text = buf.to_string()
      buf.reset()
      line_number = line_number + 1
      vec.push(Line::new(line_number, text))
    }
  } else {
    // The text may not end with a newline
    let text = buf.to_string()
    if text != "" {
      line_number = line_number + 1
      vec.push(Line::new(line_number, text))
    }
    vec
  }
}

Next, we need to wrap the array so that it supports negative indexing because we will use the value of k as an index.

type BPArray[T] Array[T] // BiPolar Array 


fn BPArray::make[T](capacity : Int, default : T) -> BPArray[T] {
  let arr = Array::make(capacity, default)
  BPArray(arr)
}

fn op_get[T](self : BPArray[T], idx : Int) -> T {
  let BPArray(arr) = self
  if idx < 0 {
    arr[arr.length() + idx]
  } else {
    arr[idx]
  }
}

fn op_set[T](self : BPArray[T], idx : Int, elem : T) -> Unit {
  let BPArray(arr) = self
  if idx < 0 {
    arr[arr.length() + idx] = elem
  } else {
    arr[idx] = elem
  }
}

Now we can start writing the search function. Before searching for the complete path, let's start with our first goal to find the length of the shortest path (equal to the search depth). Here is the basic framework:

fn shortst_edit(a : @vec.Vec[Line], b : @vec.Vec[Line]) -> Int {
  let n = a.length()
  let m = b.length()
  let max = n + m
  let v = BPArray::make(2 * max + 1, 0)
  for d = 0; d < max + 1; d = d + 1 {
    for k = -d; k < d + 1; k = k + 2 {
    ......
    }
  }
}

In the most extreme case (the two texts have no matching lines), it can be inferred that the maximum number of steps needed is n + m, and the minimum is 0. Therefore, set the variable max = n + m. The array v uses k as an index to store the historical record of x values. Since k ranges from [-d, d], the size of this array is set to 2 * max + 1.

But even at this point, it is still difficult to figure out what to do next, so let's only consider the case d = 0; k = 0 for now. At this point, it must be at (0, 0). Also, if the beginnings of the two texts are the same, they can be skipped directly. We write the final coordinates of this round into the array v.

if d == 0 { // When d equals 0, k must also equal 0
  x = 0
  y = x - k
  while x < n && y < m && a[x].text == b[y].text {
    // Skip all matching lines
    x = x + 1
    y = y + 1
  }
  v[k] = x
}

When d > 0, the coordinate information stored from the previous round is required. When we know the k value of a point and the coordinates of the points from the previous round of searching, the value of v[k] is easy to deduce. Because with each step k can only increase or decrease by one, v[k] in the search tree must extend from either v[k - 1] or v[k + 1]. The next question is: how to choose between the two paths ending at v[k - 1] and v[k + 1]?

There are two boundary cases: k == -d and k == d.

When k == -d, you can only choose v[k + 1].
When k == -d, you can only choose v[k - 1].

Recalling the requirement mentioned earlier: arranging deletions before insertions as much as possible, this essentially means choosing the position with the largest x value from the previous position.

if k == -d {
  x = v[k + 1]
} else if k == d {
  x = v[k - 1] + 1 // add 1 to move horizontally
} else if v[k - 1] < v[k + 1] {
  x = v[k + 1]
} else {
  x = v[k - 1] + 1
}

Merging these four branches, we get the following code:

if k == -d || (k != d && v[k - 1] < v[k + 1]) {
  x = v[k + 1]
} else {
  x = v[k - 1] + 1
}

Combining all the steps above, we get the following code:

fn shortst_edit(a : @vec.Vec[Line], b : @vec.Vec[Line]) -> Int {
  let n = a.length()
  let m = b.length()
  let max = n + m
  let v = BPArray::make(2 * max + 1, 0)
  // v[1] = 0
  for d = 0; d < max + 1; d = d + 1 {
    for k = -d; k < d + 1; k = k + 2 {
      let mut x = 0
      let mut y = 0
      // if d == 0 {
      //   x = 0
      // }
      if k == -d || (k != d && v[k - 1] < v[k + 1]) {
        x = v[k + 1]
      } else {
        x = v[k - 1] + 1
      }
      y = x - k
      while x < n && y < m && a[x].text == b[y].text {
        x = x + 1
        y = y + 1
      }
      v[k] = x
      if x >= n && y >= m {
        return d
      }
    }
  } else {
    abort("impossible")
  }
}

Since the initial value of the array is 0, we can omit the branch for d == 0.

Epilogue

We have implemented an incomplete version of Myers' algorithm, which completes the forward path search. In the next article, we will implement the backtracking to restore the complete edit path and write a function to output a colored diff.

This article references:

https://blog.jcoglan.com/2017/02/15/the-myers-diff-algorithm-part-2/

Thanks to the author James Coglan.

Implementing Haskell's lazy evaluation in MoonBit (Part. 3)

Zachery Yee — Tue, 16 Jul 2024 07:00:56 +0000

This article is the third in a series on implementing Haskell's lazy evaluation in MoonBit. In the previous article, we learned how to compile let expressions and how to implement basic arithmetic and comparison operations. In this article, we will implement a context-based optimization method and add support for data structures.

Tracking Context

Let's review how we implemented primitives in the last tutorial.

let compiledPrimitives : List[(String, Int, List[Instruction])] = List::[
  // Arithmetic
  ("add", 2, List::[Push(1), Eval, Push(1), Eval, Add, Update(2), Pop(2), Unwind]),
  ("sub", 2, List::[Push(1), Eval, Push(1), Eval, Sub, Update(2), Pop(2), Unwind]),
  ("mul", 2, List::[Push(1), Eval, Push(1), Eval, Mul, Update(2), Pop(2), Unwind]),
  ("div", 2, List::[Push(1), Eval, Push(1), Eval, Div, Update(2), Pop(2), Unwind]),
  // Comparison
  ("eq",  2, List::[Push(1), Eval, Push(1), Eval, Eq,  Update(2), Pop(2), Unwind]),
  ("neq", 2, List::[Push(1), Eval, Push(1), Eval, Ne,  Update(2), Pop(2), Unwind]),
  ("ge",  2, List::[Push(1), Eval, Push(1), Eval, Ge,  Update(2), Pop(2), Unwind]),
  ("gt",  2, List::[Push(1), Eval, Push(1), Eval, Gt,  Update(2), Pop(2), Unwind]),
  ("le",  2, List::[Push(1), Eval, Push(1), Eval, Le,  Update(2), Pop(2), Unwind]),
  ("lt",  2, List::[Push(1), Eval, Push(1), Eval, Lt,  Update(2), Pop(2), Unwind]),
  // Miscellaneous
  ("negate", 1, List::[Push(0), Eval, Neg, Update(1), Pop(1), Unwind]),
  ("if",     3,  List::[Push(0), Eval, Cond(List::[Push(1)], List::[Push(2)]), Update(3), Pop(3), Unwind])
]

This implementation introduces many Eval instructions, but they are not always necessary. For example:

(add 3 (mul 4 5))

The two arguments of add are already in WHNF (Weak Head Normal Form) before executing Eval. Therefore, the Eval instructions here are redundant.

One feasible optimization method is to consider the context when compiling expressions. For example, add requires its arguments to be evaluated to WHNF, so its arguments are in a strict context during compilation. By doing this, we can identify some expressions that can be safely compiled with strict evaluation (only a subset).

An expression in a supercombinator definition is in a strict context.
If (op e1 e2) is in a strict context (where op is a primitive), then e1 and e2 are also in a strict context.
If (let (.....) e) is in a strict context, then e is also in a strict context (but the expressions corresponding to the local variables are not, as e may not need their results).

We use the compileE function to implement compilation in a strict context, ensuring that the value at the top of the stack is always in WHNF.

For the default branch, we simply add an Eval instruction after the result of compileC.

append(compileC(self, env), List::[Eval])

Constants are pushed directly.

Num(n) => List::[PushInt(n)]

For let/letrec expressions, the specially designed compileLet and compileLetrec become useful. Compiling a let/letrec expression in a strict context only requires using compileE to compile its main expression.

Let(rec, defs, e) => {
  if rec {
    compileLetrec(compileE, defs, e, env)
  } else {
    compileLet(compileE, defs, e, env)
  }
}

The if and negate functions, with 3 and 1 arguments respectively, require special handling.

App(App(App(Var("if"), b), e1), e2) => {
  let condition = compileE(b, env)
  let branch1 = compileE(e1, env)
  let branch2 = compileE(e2, env)
  append(condition, List::[Cond(branch1, branch2)])
}
App(Var("negate"), e) => {
  append(compileE(e, env), List::[Neg])
}

Basic binary operations can be handled uniformly through a lookup table. First, construct a hash table called builtinOpS to query the corresponding instructions by the name of the primitive.

let builtinOpS : RHTable[String, Instruction] = {
  let table : RHTable[String, Instruction] = RHTable::new(50)
  table["add"] = Add
  table["mul"] = Mul
  table["sub"] = Sub
  table["div"] = Div
  table["eq"]  = Eq
  table["neq"] = Ne
  table["ge"] = Ge
  table["gt"] = Gt
  table["le"] = Le
  table["lt"] = Lt
  table
}

The rest of the handling is not much different.

App(App(Var(op), e0), e1) => {
  match builtinOpS[op] {
    None => append(compileC(self, env), List::[Eval]) // Not a primitive op, use the default branch
    Some(instr) => {
      let code1 = compileE(e1, env)
      let code0 = compileE(e0, argOffset(1, env))
      append(code1, append(code0, List::[instr]))
    }
  }
}

Are we done? It seems so, but there's another WHNF besides integers: partially applied functions.

A partial application is when the number of arguments is insufficient. This situation is common in higher-order functions, for example:

(map (add 1) listofnumbers)

Here, (add 1) is a partial application.

To ensure that the code generated by the new compilation strategy works correctly, we need to modify the implementation of the Unwind instruction for the NGlobal branch. When the number of arguments is insufficient and the dump has saved stacks, we should only retain the original redex and restore the stack.

NGlobal(_, n, c) => {
  let k = length(self.stack)
  if k < n {
    match self.dump {
      Nil => abort("Unwinding with too few arguments")
      Cons((i, s), rest) => {
        // a1 : ...... : ak
        // ||
        // ak : s
        // Retain the redex and restore the stack
        self.stack = append(drop(self.stack, k - 1), s)
        self.dump = rest
        self.code = i
      }
    }
  } else {
    ......
  }
}

This context-based strictness analysis technique is useful but cannot do anything with supercombinator calls. Here we briefly introduce a strictness analysis technique based on boolean operations, which can analyze which arguments of a supercombinator call should be compiled using strict mode.

We first define a concept: bottom, which conceptually represents a value that never terminates or causes an exception. For a supercombinator f a[1] ...... a[n], if one argument a[i] satisfies a[i] = bottom, then f a[1] .... a[i] .... a[n] = bottom (other arguments are not bottom). This indicates that no matter how complex the internal control flow of f is, it must need the result of argument a[i] to get the final result. Therefore, a[i] should be strictly evaluated.

If this condition is not met, it does not necessarily mean that the argument is not needed at all; it may be used only in certain branches and its use is determined at runtime. Such an argument is a typical example of one that should be lazily evaluated.

Let's consider bottom as false and non-bottom values as true. In this way, all functions in coref can be considered boolean functions. Take abs as an example:

(defn abs[n]
  (if (lt n 0) (negate n) n))

We analyze how to translate it into a boolean function from top to bottom:

For an expression like (if x y z), x must be evaluated, but only one of y or z needs to be evaluated. This can be translated into x and (y or z). Taking the example of the function above, if n is bottom, then the condition (lt n 0) is also bottom, and thus the result of the entire expression is also bottom.
For primitive expressions, using and for all parts is sufficient.

To determine whether a parameter needs to be compiled strictly, you can convert the above condition into a Boolean function: a[i] = false implies f a[1] .... a[i] .... a[n] = false (with all other parameters being true).

This is essentially a method of program analysis called "abstract interpretation."

Custom Data Structures

The data structure type definition in Haskell is similar to the enum in MoonBit. However, since CoreF is a simple toy language used to demonstrate lazy evaluation, it does not allow custom data types. The only built-in data structure is the lazy list.

(defn take[n l]
  (case l
    [(Nil) Nil]
    [(Cons x xs)
      (if (le n 0)
        Nil
        (Cons x (take (sub n 1) xs)))]))

As shown above, you can use the case expression for simple pattern matching on lists.

The corresponding graph node for a list is NConstr(Int, List[Addr]), which consists of two parts:

A tag for different value constructors: the tag for Nil is 0, and the tag for Cons is 1.
A list of addresses for storing substructures, whose length corresponds to the number of parameters (arity) of a value constructor.

This graph node structure can be used to implement various data structures, but CoreF does not have a type system. For demonstration purposes, only lazy lists are implemented.

We need to add two instructions, Split and Pack, to deconstruct and construct lists.

fn split(self : GState, n : Int) -> Unit {
  let addr = self.pop1()
  match self.heap[addr] {
    NConstr(_, addrs) => {
      // n == addrs.length()
      self.stack = addrs + self.stack
    }
  }
}

fn pack(self : GState, t : Int, n : Int) -> Unit {
  let addrs = self.stack.take(n)
  // Assume the number of arguments is sufficient
  self.stack = self.stack.drop(n)
  let addr = self.heap.alloc(NConstr(t, addrs))
  self.putStack(addr)
}

Additionally, a CaseJump instruction is needed to implement the case expression.

fn casejump(self : GState, table : List[(Int, List[Instruction])]) -> Unit {
  let addr = self.pop1()
  match self.heap[addr] {
    NConstr(t, addrs) => {
      match lookupENV(table, t) {
        None => abort("casejump")
        Some(instrs) => {
          self.code = instrs + self.code
          self.putStack(addr)
        }
      }
    }
    otherwise => abort("casejump(): addr = \(addr) node = \(otherwise)")
  }
}

After adding the above instructions, we need to modify the compileC and compileE functions. Since the object matched by the case expression needs to be evaluated to WHNF, only the compileE function can compile it.

// compileE
  Case(e, alts) => {
    compileE(e, env) + List::[CaseJump(compileAlts(alts, env))]
  }
  Constructor(0, 0) => {
    // Nil
    List::[Pack(0, 0)]
  }
  App(App(Constructor(1, 2), x), xs) => {
    // Cons(x, xs)
    compileC(xs, env) + compileC(x, argOffset(1, env)) + List::[Pack(1, 2)]
  }

// compileC
  App(App(Constructor(1, 2), x), xs) => {
    // Cons(x, xs)
    compileC(xs, env) + compileC(x, argOffset(1, env)) + List::[Pack(1, 2)]
  }
  Constructor(0, 0) => {
    // Nil
    List::[Pack(0, 0)]
  }

At this point, a new problem arises. Previously, printing the evaluation result only needed to handle simple NNum nodes, but NConstr nodes have substructures. When the list itself is evaluated to WHNF, its substructures are mostly unevaluated NApp nodes. We need to add a Print instruction, which will recursively evaluate and write the result into the output component of GState.

struct GState {
  output : Buffer
  ......
}

fn gprint(self : GState) -> Unit {
  let addr = self.pop1()
  match self.heap[addr] {
    NNum(n) => {
      self.output.write_string(n.to_string())
      self.output.write_char(' ')
    }
    NConstr(0, Nil) => self.output.write_string("Nil")
    NConstr(1, Cons(addr1, Cons(addr2, Nil))) => {
      // Force evaluation of addr1 and addr2 is required, so we execute Eval instructions first
      self.code = List::[Instruction::Eval, Print, Eval, Print] + self.code
      self.putStack(addr2)
      self.putStack(addr1)
    }
  }
}

Finally, change the initial code of the G-Machine to:

let initialCode : List[Instruction] = List::[PushGlobal("main"), Eval, Print]

Now, we can write some classic functional programs using lazy lists, such as the infinite Fibonacci sequence:

(defn fibs[] (Cons 0 (Cons 1 (zipWith add fibs (tail fibs)))))

After introducing data structures, strictness analysis becomes more complex. For lazy lists, there are various evaluation modes:

Fully strict (requires the list to be finite and all elements to be non-bottom).
Fully lazy.
Head strict (the list can be infinite, but its elements cannot be bottom).
Tail strict (the list must be finite, but its elements can be bottom).

Moreover, the context in which a function is used can change the evaluation mode of its parameters (it cannot be analyzed in isolation and requires cross-function analysis). Such complex strictness analysis usually employs projection analysis techniques. Relevant literature includes:

Projections for Strictness Analysis
Static Analysis and Code Optimizations in Glasgow Haskell Compiler
Implementing Projection-based Strictness Analysis
Theory and Practice of Demand Analysis in Haskell

Epilogue

Lazy evaluation can reduce runtime redundant calculations, but it also introduces new problems, such as:

The notorious side effect order issue.
Excessive redundant nodes. Some computations that are not shared still store their results on the heap, which is detrimental to utilizing the CPU's caching mechanism.

The representative of lazy evaluation languages, Haskell, offers a controversial solution to the side effect order problem: Monads. This solution has some value for eagerly evaluated languages as well, but many online tutorials emphasize its mathematical background too much and fail to explain how to use it effectively.

Idris2, Haskell's successor (which is no longer a lazy language), retains Monads and introduces another mechanism for handling side effects: Algebraic Effects.

The Spineless G-Machine designed by SPJ improved the problem of excessive redundant nodes, and its successor, the STG, unified the data layout of different types of nodes.

In addition to improvements in abstract machine models, GHC's optimization of Haskell programs heavily relies on inline-based optimizations and projection analysis-based strictness analysis techniques.

In 2004, several GHC designers discovered that the previous push-enter model, where parameters are pushed onto the stack and then a function is called, was less effective than the eval-apply model, where the responsibility is handed to the caller. They published a paper titled "Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages."

In 2007, Simon Marlow found that jump and execute code in the tagless design significantly affected the performance of modern CPU branch predictors. The paper "Faster laziness using dynamic pointer tagging" described several solutions.

Lazy purely functional languages have shown many interesting possibilities, but they have also faced much criticism and reflection. Nevertheless, it is undoubtedly an intriguing technology!

Implement Haskell's G-Machine in MoonBit (Part 2)

Zachery Yee — Wed, 29 May 2024 10:28:27 +0000

This article is the second in the series on implementing lazy evaluation in MoonBit. In the first part, we explored the purposes of lazy evaluation and a typical abstract machine for lazy evaluation, the G-Machine, and implemented some basic G-Machine instructions. In this article, we will further extend the G-Machine implementation from the previous article to support let expressions and basic arithmetic, comparison, and other operations.

let Expressions

The let expression in coref differs slightly from that in MoonBit. A let expression can create multiple variables but can only be used within a limited scope. Here is an example:

{
  let x = n + m
  let y = x + 42
  x * y
}

Equivalent coref expression:

(let ([x (add n m)]
      [y (add x 42)])
  (mul x y)) ;; xy can only be used within let

It is important to note that coref's let expressions must follow a sequential order. For example, the following is not valid:

(let ([y (add x 42)]
      [x (add n m)])
  (mul x y))

In contrast, letrec is more complex as it allows the local variables defined to reference each other without considering the order of their definitions.

Before implementing let (and the more complex letrec), we first need to modify the current parameter passing method. The local variables created by let should intuitively be accessed in the same way as parameters, but the local variables defined by let do not correspond to NApp nodes. Therefore, we need to adjust the stack parameters before calling the supercombinator.

The adjustment is done in the implementation of the Unwind instruction. If the supercombinator has no parameters, it is the same as the original unwind. When there are parameters, the top address of the supercombinator node is discarded, and the rearrange function is called.

fn rearrange(self : GState, n : Int) -> Unit {
  let appnodes = take(self.stack, n)
  let args = map(fn (addr) {
  let NApp(_, arg) = self.heap[addr]
      arg
  }, appnodes)
  self.stack = append(args, drop(appnodes, n - 1))
}

The rearrange function assumes that the first N addresses on the stack point to a series of NApp nodes. It keeps the bottommost one (used as Redex update), cleans up the top N-1 addresses, and then places N addresses that directly point to the parameters.

After this, both parameters and local variables can be accessed using the same command by changing the PushArg instruction to a more general Push instruction.

fn push(self : GState, offset : Int) -> Unit {
  // Copy the address at offset + 1 to the top of the stack
  //    Push(n) a0 : . . . : an : s
  // => an : a0 : . . . : an : s
  let appaddr = nth(self.stack, offset)
  self.putStack(appaddr)
}

The next issue is that we need something to clean up. Consider the following expression:

(let ([x1 e1]
      [x2 e2])
  expr)

After constructing the graph corresponding to the expression expr, the stack still contains addresses pointing to e1 and e2 (corresponding to variables x1 and x2), as shown below (the stack grows from bottom to top):

<Address pointing to expr>
       |
<Address pointing to x2>
       |
<Address pointing to x1>
       |
...remaining stack...

Therefore, we need a new instruction to clean up these no longer needed addresses. It is called Slide. As the name suggests, the function of Slide(n) is to skip the first address and delete the following N addresses.

fn slide(self : GState, n : Int) -> Unit {
  let addr = self.pop1()
  self.stack = Cons(addr, drop(self.stack, n))
}

Now we can compile let. We will compile the expressions corresponding to local variables using the compileC function. Then, traverse the list of variable definitions (defs), compile and update the corresponding offsets in order. Finally, use the passed comp function to compile the main expression and add the Slide instruction to clean up the unused addresses.

Compiling the main expression using the passed function makes it easy to reuse when adding subsequent features.

fn compileLet(comp : (RawExpr[String], List[(String, Int)]) -> List[Instruction], defs : List[(String, RawExpr[String])], expr : RawExpr[String], env : List[(String, Int)]) -> List[Instruction] {
  let (env, codes) = loop env, List::Nil, defs {
    env, acc, Nil => (env, acc)
    env, acc, Cons((name, expr), rest) => {
      let code = compileC(expr, env)
      // Update offsets and add offsets for local variables corresponding to name
      let env = List::Cons((name, 0), argOffset(1, env))
      continue env, append(acc, code), rest
    }
  }
  append(codes, append(comp(expr, env), List::[Slide(length(defs))]))
}

The semantics of letrec are more complex - it allows the N variables within the expression to reference each other, so we need to pre-allocate N addresses and place them on the stack. We need a new instruction: Alloc(N), which pre-allocates N NInd nodes and pushes the addresses onto the stack sequentially. The addresses in these indirect nodes are negative and only serve as placeholders.

fn allocNodes(self : GState, n : Int) -> Unit {
  let dummynode : Node = NInd(Addr(-1))
  for i = 0; i < n; i = i + 1 {
    let addr = self.heap.alloc(dummynode)
    self.putStack(addr)
  }
}

The steps to compile letrec are similar to let:

Use Alloc(n) to allocate N addresses.
Use the loop expression to build a complete environment.
Compile the local variables in defs, using the Update instruction to update the results to the pre-allocated addresses after compiling each one.
Compile the main expression and use the Slide instruction to clean up.

fn compileLetrec(comp : (RawExpr[String], List[(String, Int)]) -> List[Instruction], defs : List[(String, RawExpr[String])], expr : RawExpr[String], env : List[(String, Int)]) -> List[Instruction] {
  let env = loop env, defs {
    env, Nil => env
    env, Cons((name, _), rest) => {
      let env = List::Cons((name, 0), argOffset(1, env))
      continue env, rest
    }
  }
  let n = length(defs)
  fn compileDefs(defs : List[(String, RawExpr[String])], offset : Int) -> List[Instruction] {
    match defs {
      Nil => append(comp(expr, env), List::[Slide(n)])
      Cons((_, expr), rest) => append(compileC(expr, env), Cons(Update(offset), compileDefs(rest, offset - 1)))
    }
  }
  Cons(Alloc(n), compileDefs(defs, n - 1))
}

Adding Primitives

From this step, we can finally perform basic integer operations such as arithmetic, comparison, and checking if two numbers are equal. First, modify the Instruction type to add related instructions.

  Add
  Sub
  Mul
  Div 
  Neg
  Eq // ==
  Ne // !=
  Lt // <
  Le // <=
  Gt // >
  Ge // >=
  Cond(List[Instruction], List[Instruction])

At first glance, implementing these instructions seems simple. Take Add as an example: just pop two top addresses from the stack, retrieve the corresponding numbers from memory, perform the operation, and push the result address back onto the stack.

fn add(self : GState) -> Unit {
  let (a1, a2) = self.pop2() // Pop two top addresses
  match (self.heap[a1], self.heap[a2]) {
    (NNum(n1), NNum(n2)) => {
      let newnode = Node::NNum(n1 + n2)
      let addr = self.heap.alloc(newnode)
      self.putStack(addr)      
    }
    ......
  }
}

However, the next problem we face is that this is a lazy evaluation language. The parameters of add are likely not yet computed (i.e., not NNum nodes). We also need an instruction that can force a computation to give a result or never stop computing. We call it Eval (short for Evaluation).

In jargon, the result of such a computation is called Weak Head Normal Form (WHNF).

At the same time, we need to modify the structure of GState and add a state called dump. Its type is List[(List[Instruction], List[Addr])], used by Eval and Unwind instructions.

The implementation of the Eval instruction is not complicated:

Pop the top address of the stack.
Save the current unexecuted instruction sequence and stack (by putting them into the dump).
Clear the current stack and place the previously saved address.
Clear the current instruction sequence and place the Unwind instruction.

This is similar to how strict evaluation languages handle saving caller contexts, but practical implementations would use more efficient methods.

fn eval(self : GState) -> Unit {
  let addr = self.pop1()
  self.putDump(self.code, self.stack)
  self.stack = List::[addr]
  self.code = List::[Unwind]
}

This simple definition requires modifying the Unwind instruction to restore the context when Unwind in the NNum branch finds that there is a recoverable context (dump is not empty).

fn unwind(self : GState) -> Unit {
  let addr = self.pop1()
  match self.heap[addr] {
    NNum(_) => {
      match self.dump {
        Nil => self.putStack(addr)
        Cons((instrs, stack), restDump) => {
          // Restore the stack
          self.stack = stack
          self.putStack(addr)
          self.dump = restDump
          // Return to original code execution
          self.code = instrs
        }
      }
    }
    ......
  }
}

Next, we need to implement arithmetic and comparison instructions. We use two functions to simplify the form of binary operations. The result of the comparison instruction is a boolean value, and for simplicity, we use numbers to represent it: 0 for false, 1 for true.

fn liftArith2(self : GState, op : (Int, Int) -> Int) -> Unit {
  // Binary arithmetic operations
  let (a1, a2) = self.pop2()
  match (self.heap[a1], self.heap[a2]) {
    (NNum(n1), NNum(n2)) => {
      let newnode = Node::NNum(op(n1, n2))
      let addr = self.heap.alloc(newnode)
      self.putStack(addr)
    }
    (node1, node2) => abort("liftArith2: \(a1) = \(node1) \(a2) = \(node2)")
  }
}

fn liftCmp2(self : GState, op : (Int, Int) -> Bool) -> Unit {
  // Binary comparison operations
  let (a1, a2) = self.pop2()
  match (self.heap[a1], self.heap[a2]) {
    (NNum(n1), NNum(n2)) => {
      let flag = op(n1, n2)
      let newnode = if flag { Node::NNum(1) } else { Node::NNum(0) }
      let addr = self.heap.alloc(newnode)
      self.putStack(addr)
    }
    (node1, node2) => abort("liftCmp2: \(a1) = \(node1) \(a2) = \(node2)")
  }
}

// Implement negation separately
fn negate(self : GState) -> Unit {
  let addr = self.pop1()
  match self.heap[addr] {
    NNum(n) => {
      let addr = self.heap.alloc(NNum(-n))
      self.putStack(addr)
    }
    otherwise => {
      // If not NNum, throw an error
      abort("negate: wrong kind of node \(otherwise), address \(addr) ")
    }
  }
}

Finally, implement branching:

fn condition(self : GState, i1 : List[Instruction], i2 : List[Instruction]) -> Unit {
  let addr = self.pop1()
  match self.heap[addr] {
    NNum(0) => {
      // If false, jump to i2
      self.code = append(i2, self.code)
    }
    NNum(1) => {
      // If true, jump to i1
      self.code = append(i1, self.code)
    }
    otherwise => abort("cond : \(addr) = \(otherwise)")
  }
}

No major adjustments are needed in the compilation part, just add some predefined programs:

let compiledPrimitives : List[(String, Int, List[Instruction])] = List::[
  // Arithmetic
  ("add", 2, List::[Push(1), Eval, Push(1), Eval, Add, Update(2), Pop(2), Unwind]),
  ("sub", 2, List::[Push(1), Eval, Push(1), Eval, Sub, Update(2), Pop(2), Unwind]),
  ("mul", 2, List::[Push(1), Eval, Push(1), Eval, Mul, Update(2), Pop(2), Unwind]),
  ("div", 2, List::[Push(1), Eval, Push(1), Eval, Div, Update(2), Pop(2), Unwind]),
  // Comparison
  ("eq",  2, List::[Push(1), Eval, Push(1), Eval, Eq,  Update(2), Pop(2), Unwind]),
  ("neq", 2, List::[Push(1), Eval, Push(1), Eval, Ne,  Update(2), Pop(2), Unwind]),
  ("ge",  2, List::[Push(1), Eval, Push(1), Eval, Ge,  Update(2), Pop(2), Unwind]),
  ("gt",  2, List::[Push(1), Eval, Push(1), Eval, Gt,  Update(2), Pop(2), Unwind]),
  ("le",  2, List::[Push(1), Eval, Push(1), Eval, Le,  Update(2), Pop(2), Unwind]),
  ("lt",  2, List::[Push(1), Eval, Push(1), Eval, Lt,  Update(2), Pop(2), Unwind]),
  // Miscellaneous
  ("negate", 1, List::[Push(0), Eval, Neg, Update(1), Pop(1), Unwind]),
  ("if",     3,  List::[Push(0), Eval, Cond(List::[Push(1)], List::[Push(2)]), Update(3), Pop(3), Unwind])
]

and modify the initial instruction sequence

let initialCode : List[Instruction] = List::[PushGlobal("main"), Eval]

Conclusion

In the next part, we will improve the code generation for primitives and add support for data structures.

How to Plot the Mandelbrot Set Using MoonBit?

Zachery Yee — Wed, 03 Apr 2024 10:11:37 +0000

It is the famous Mandelbrot set, a collection of points on the complex plane that form a fractal. It is the most famous fractal in the fractal theory proposed by the mathematician Benoit B. Mandelbrot.

The wonder of this set lies in the fact that when you infinitely magnify the Mandelbrot set, exquisite details emerge within it, all generated by a simple formula. Therefore, some consider the Mandelbrot set to be "the most peculiar and magnificent geometric shape ever made by mankind," often referred to as "God's fingerprint”.

MoonBit is a Rust-like programming language and toolchain optimized for WebAssembly, great for writing high-performance code. Today, I will share what fractal theory is, how to draw Mandelbrot fractals using MoonBit, and discover the beauty of mathematics with MoonBit.

What is Fractal Theory

First, let's look at what fractal theory is.

Fractal theory was created by Mandelbrot in 1975, stemming from the Latin word "fractus", meaning "broken" or "fractured." The mathematical foundation of fractal theory is fractal geometry, which describes and studies objective things from the perspective of fractional dimensions and mathematical methods.

Because of this, fractals transcend the dimensions of our conventional world, allowing for a more concrete and realistic description of complex systems, revealing the complexity and diversity of objective things.

Due to the "infinite complexity" of fractals, you might think that creating fractals is difficult, but it's a very simple process. To create a fractal, you just need to repeat the same process over and over again. In mathematical terms, a mathematical fractal is an iterative (a form of recursion) equation.

The most famous fractal is the Mandelbrot set, which comes from the complex number set c. Mathematician Adrien Douady defined the following function:
$f_{c}(z) = z^2 + c$

In homage to Mandelbrot, it is named the Mandelbrot set. When iterated from z=0, it does not diverge to infinity. Essentially, it is an iterative formula, where the variables in the equation are complex numbers. So when you calculate by substituting according to this formula, local patterns resemble the overall structure, and this similarity often concentrates on subtle details, requiring careful observation to discern.

How to Draw the Mandelbrot Set with MoonBit

Next, we will share how to draw the Mandelbrot set using MoonBit.

To determine the area of the graphic we want to draw, we must first introduce the concept of region coordinates. A point on the complex plane is represented by a complex number (d=x+yi). Adding width and height determines a rectangular area on the complex plane.

Suppose an image has a width of w pixels and a height of h pixels. We need to calculate the colors of w*h pixels and then draw them.

We use MoonBit to perform the color calculation part, and then pass the calculated colors to JavaScript. We use JavaScript canvas to draw the image.

Color Calculation

pub func calc_color(col : Int, row : Int, ox : Float64, oy : Float64,
    width : Float64) -> Int {
let pixel_size = width / image_width
let cx = (float_of_int(col) - coffset) * pixel_size + ox
let cy = (float_of_int(row) - roffset) * pixel_size + oy
var r = 0
var g = 0
var b = 0
var i = -1
while i <= 1 {
var j = -1
while j <= 1 {
  let d = iter(
    cx + float_of_int(i) * pixel_size / 3.0,
    cy + float_of_int(j) * pixel_size / 3.0,
  )
  let c = get_color(d)
  r = r + c.asr(16).land(0xFF)
  g = g + c.asr(8).land(0xFF)
  b = b + c.land(0xFF)
  j = j + 1
}
i = i + 1
}
r = r / 9
g = g / 9
b = b / 9
return r.lsl(16).lor(g.lsl(8)).lor(b)
}

calculate the coordinates of the center point of the square represented on the complex plane by the pixel at row and col.

let pixel_size = width / image_width
  let cx = (float_of_int(col) - coffset) * pixel_size + ox
  let cy = (float_of_int(row) - roffset) * pixel_size + oy

We know that for a complex number c, it belongs to the Mandelbrot set if and only if the infinite sequence of complex numbers obtained by the following recursive definition remains within a circle in the complex plane centered at the origin with a radius of 2: $z_0 = 0$ ; $z_n=z^2_{n-1} + c$ ; If we express $z_k$ as $x_k + y_{k}i$ with its real and imaginary parts separated, and similarly express $c$ as $c_x + c_{y}i$ (with its real and imaginary parts denoted as real $c_x$ and imag $c_y$ respectively), then the recursive definition above is essentially stating $x_0 = 0$ , $y_0 = 0$ ; $x_n = x^2_{n-1} - y^2_{n-1} + c_x$ , $y_n = 2x_{n-1}y_{n-1}+c_y$ ; a complex number $c_x +c_{y}i$ belongs to the Mandelbrot set if and only if for all natural numbers 'n', $x^2_n + y^2_n <2^2 = 4$ .

calc_color then calls iter to calculate x_n and y_n. This function returns the number of iterations at which the sequence escapes for the first time, or -1.0 if it does not escape after max_iter_number iterations.

pub func iter(cx : Float64, cy : Float64) -> Float64 {
    var x = 0.0
    var y = 0.0
    var newx = 0.0
    var newy = 0.0
    var smodz = 0.0
    var i = 0
    while i < max_iter_number {
      newx = x * x - y * y + cx
      newy = 2.0 * x * y + cy
      x = newx
      y = newy
      i = i + 1
      smodz = x * x + y * y
      if smodz >= escape_radius {
        return float_of_int(i) + 1.0 - log(log(smodz) * 0.5) / log(2.0)
      }
    }
    return -1.0
  }

Next, we need to choose the appropriate color based on the returned number of interpolation. What we need first is a color palette, and this is where interpolation comes into play. interpolation is used to generate a gradient of colors.

func interpolation(f : Float64, c0 : Int, c1 : Int) -> Int {
    let r0 = c0.asr(16).land(0xFF)
    let g0 = c0.asr(8).land(0xFF)
    let b0 = c0.land(0xFF)
    let r1 = c1.asr(16).land(0xFF)
    let g1 = c1.asr(8).land(0xFF)
    let b1 = c1.land(0xFF)
    let r = floor((1.0 - f) * float_of_int(r0) + f * float_of_int(r1) + 0.5)
    let g = floor((1.0 - f) * float_of_int(g0) + f * float_of_int(g1) + 0.5)
    let b = floor((1.0 - f) * float_of_int(b0) + f * float_of_int(b1) + 0.5)
    return r.lsl(16).lor(g.lsl(8).lor(b))
  }

get_color first performs some transformation on the number of iterations and then passes it to interpolation to obtain the corresponding color.

pub func get_color(d : Float64) -> Int {
    if d >= 0.0 {
      var k = 0.021 * (d - 1.0 + log(log(128.0)) / log(2.0))
      k = log(1.0 + k) - 29.0 / 400.0
      k = k - float_of_int(floor(k))
      k = k * 400.0
      if k < 63.0 {
        return interpolation(k / 63.0, 0x000764, 0x206BCB)
      } else if k < 167.0 {
        return interpolation((k - 63.0) / (167.0 - 63.0), 0x206BCB, 0xEDFFFF)
      } else if k < 256.0 {
        return interpolation((k - 167.0) / (256.0 - 167.0), 0xEDFFFF, 0xFFAA00)
      } else if k < 342.0 {
        return interpolation((k - 256.0) / (342.0 - 256.0), 0xFFAA00, 0x310230)
      } else {
        return interpolation((k - 342.0) / (400.0 - 342.0), 0x310230, 0x000764)
      }
    } else {
      return 0x000000
    }
  }

Color calculation is now completed.

Plot with canvas

Create a canvas:

<html>
<body>
  <canvas id="canvas"></canvas>
</body>

In the JavaScript code, obtain the canvas and set its size:

let canvas = document.getElementById("canvas");
var IMAGEWIDTH = 800;
var IMAGEHEIGHT = 600;
canvas.width = IMAGEWIDTH;
canvas.height = IMAGEHEIGHT;

Create an ImageData object to store the computed colors of the pixels:

var imagedata = context.createImageData(IMAGEWIDTH, IMAGEHEIGHT);

Then import the MoonBit code:

WebAssembly.instantiateStreaming(fetch("target/mandelbrot.wasm"), spectest).then(
    (obj) => {
      obj.instance.exports._start();
      const calcColor = obj.instance.exports["mandelbrot/lib::calc_color"];
      const drawColor = obj.instance.exports["mandelbrot/lib::draw_color"];

      //...

Draw the image:

function saveImage() {
    context.putImageData(imagedata, 0, 0);
  }

  function generateImage() {
    for (row = 0; row < IMAGEHEIGHT; row++) {
      for (col = 0; col < IMAGEWIDTH; col++) {
        let x = +ox.value;
        let y = +oy.value;
        let w = +width.value;
        var color = calcColor(col, row, x, y, w);
        drawColor(imagedata, col, row, color);
      }
    }

    saveImage();
  }

This is how the specific implementation looks like:

Drawing the Mandelbrot set involves a lot of mathematical derivation, which is not extensively explained in this tutorial. You can refer to:
https://eigolomoh.bitbucket.io/math/draw_mandelbrot.1.html

Full code: https://github.com/moonbitlang/moonbit-docs/tree/main/examples/mandelbrot

Implement Binary Heap & Pairing Heap with MoonBit

Zachery Yee — Thu, 21 Mar 2024 06:34:40 +0000

The concept of binary heap was introduced in 1964 by J.W.J Williams' Algorithm 232 - Heapsort. Over the following decades, people discovered that beyond general sorting (such as priority task scheduling, graph algorithms, etc.), this data structure can be applied to more settings, and various variants have been extended. This article will explore the principles of binary heaps implemented using arrays and pairing heaps implemented using lists, and how to implement them using MoonBit (a Rust-like language and toolchain optimized for WebAssembly experience).

(website here: https://www.moonbitlang.com/)

01 Basic Structure and Usage of Heap

What comes to mind when talking about "heap"?

The name "heap" is often related to a discontinuous program data storage area contrasting with stacks, but just like stacks, in the realm of data structures, "heap" holds a radically different definition. According to the earliest literature on “heap” from 1964, it is mentioned right at the beginning that heap sort is an improved version of tree sort, so the logical structure of a heap is a tree.

https://www.happycoders.eu/algorithms/heapsort/

In a heap, the value stored in any node is greater or smaller than the values of its child nodes, ensuring that any subtree in the heap also meets this condition. For users, using a heap is akin to using a "queue".

let h = MinHeap::new()

Users can add elements to the heap using the insert method:

h.insert(6)
h.insert(4)
h.insert(13)

You can also use pop to remove an element, but each time it is the smallest element in the current heap that pops from the heap, not necessarily in the order they were inserted.

h.pop() // the result should be 4.

In these examples, the elements stored in the heap are integers. However, in reality, the heap only requires elements to be comparable. In MoonBit, the comparison operators such as > and < are methods under the Compare interface. Any type that implements this interface can be used to store elements in the heap.

02 Array Implementation of Binary Heap

Here, we are implementing a max heap, where the root element of the heap is the largest.

The logical structure of a binary heap is a nearly complete binary tree (commonly termed as a "complete binary tree").

Suppose there is an n-level binary heap, where the first n-1 levels are full, and the nodes on the nth level tend to fill from left to right. The diagram below illustrates a binary heap arr with 6 elements, which can be stored in an array of length 6. The positions of each node in the corresponding array are marked in the diagram.

The online visualization display page of a binary heap can provide a clearer demonstration: https://visualgo.net/en/heap?slide=1

Due to the property mentioned earlier, each node can be assigned a specific identifier (used as an array index), and by using this identifier, we can find its left and right child nodes. Consequently, the entire binary heap can be directly stored in an array.

On an array indexed starting from 1, the left child node of node i is at position 2i, the right child node is at position 2i+1, and the parent node is at position i/2 rounded down.

fn parent(self : Int) -> Int {
    self / 2
  }

  fn left(self : Int) -> Int {
    self * 2
  }

  fn right(self : Int) -> Int {
    self * 2 + 1
  }

  // Assuming you want to obtain the array index corresponding to the parent node of node i, you can use i.parent().

In MoonBit, arrays are indexed starting from 0. To maintain formal consistency, the position initially indexed as 0 is left unused, and in heap-related operations, 1 is used as the index start.

In the BHeap::new function for creating a heap, to ensure that the actual heap capacity matches the parameter, the array length is incremented by one when creating the array. Consequently, the capacity() function, which retrieves the heap's capacity, subtracts 1 from the array length.

The built-in Array[T] in MoonBit is of fixed length, so a struct with an actual element count and an array needs to be established.

struct BHeap[T] {
    mut data : Array[T]
    mut count : Int
    min_value : T
  }

  fn BHeap::new[T : Compare](capacity : Int, minValue : T) -> BHeap[T] {
    { data: Array::make(capacity + 1, minValue), count: 0, min_value: minValue }
  }

  fn capacity[T](self : BHeap[T]) -> Int {
    self.data.length() - 1
  }

Creating an array requires default values, and it is recommended to fill it with the minimum value of type T.

The next step is to implement two related operations of the binary heap: insertion and popping.

Inserting elements into an empty binary heap is straightforward; just place the element at data[1]. However, when inserting more elements, how do we find the appropriate position by comparing their sizes?

A widely adopted approach is to first place the new element to be inserted at the end of the array - essentially finding the leftmost available position in the last level of the binary tree and designating it as a leaf node. If the bottom level is already full, a new level is started. The diagram below illustrates inserting the new element 20 into the right child node:

fn insert[T : Compare](self : BHeap[T], x : T) {
    ......
    self.data[self.count + 1] = x
    self.count = self.count + 1
    self.heap_fix(self.count)
    ......
}

This action has a high probability of violating the heap property. We have no idea about the size relationship between this new element and the randomly assigned parent node. However, although the heap property is disrupted, the previous heap elements still adhere to the rule of having the maximum element at the parent node. Repairing it based on this rule is not so difficult.

Suppose the array index corresponding to the new element is stored in the variable i. Then:

First, check if i is equal to 1. If it is, do nothing - there is no parent node. Since we are not using index 0, i not being equal to 1 can also be expressed as i > 1.
If i is not equal to 1, compare it with its parent node. If it is greater than the value of the parent node, exchange it with the parent node. In the diagram below, the newly inserted element 20 is greater than its parent node element 17, so 17 is moved downwards to allow 20 to "float up."
Assign i to i.parent() because this is the new position of the element.
Repeat the above process until the parent node at the new position of the element is greater than it or until it reaches the top of the heap.

fn heap_fix[T : Compare](self : BHeap[T], i : Int) {
    var i = i
    while i > 1 && self.data[i] > self.data[i.parent()] {
      self.data.exchange(i, i.parent()) // Exchange the positions of the elements.
      i = i.parent() // Mark the index corresponding to the inserted element now.
    }
  }

  fn exchange[T](self : Array[T], x : Int, y : Int) {
    let tmp = self[x]
    self[x] = self[y]
    self[y] = tmp
  }

Another important operation is popping the top element of the heap. Following the strategy of altering first and then rebalancing, we first swap the first and last elements of the array, then decrement the count variable by one. In the diagram below, the original top element of the heap is 45, and the element at the heap's end is 9. Now, by swapping their positions and decrementing the count , we remove 45.

The process of deletion can be viewed as gradually "sinking" the element that has been swapped to the top of the heap to a suitable position. This step is completed through the heapify function.

Suppose the index of the element swapped to the top of the heap is stored in the variable i, and each comparison is done using the variable s, which initially holds the index of the node with the maximum value.

First, find the indices of the left and right child nodes, named l and r.
Check if they are out of bounds - the indices calculated by left and right might not actually store elements or even exceed the current heap capacity.
If they are within bounds, compare the values of data[l] and data[s], assigning the index of the larger value to s.
If they are within bounds, compare the values of data[r] and data[s], assigning the index of the larger value to s (as l and i have already been compared; at this point, s should hold the index of the larger value between l and i).
Check if s is equal to i. If so, it means that data[i] is larger than both data[l] and data[r]. Considering the property of the subheap hasn't been violated, data[i] is already larger than all the elements in the subtree, so terminate the loop and exit.
If s is not equal to i, swap the values of s and i, because the original element's position has shifted downward. Then assign i to s and continue the loop. In the example below, after comparing the newly inserted element 9 with its left and right child nodes, the largest value 36 is swapped to the top of the heap.

The MoonBit code implementation corresponding to the process described above is as follows:

fn pop[T : Compare](self : BHeap[T]) -> Option[T] {
  if self.count == 0 {
    return None
  }
  let x = self.data[1] // Save the top element of the heap.
  let n = self.count
  self.data.exchange(1, n)
  self.count = self.count - 1 // Remove the original top element of the heap exchanged to the end of the array.
  if self.count > 0 {
    self.heapify(1)
  }
  return Some(x)
}

fn heapify[T : Compare](self : BHeap[T], index : Int) {
  let n = self.count
  var i = index
  var s = i
  while true {
    let l = i.left()
    let r = i.right()
    if l <= n && self.data[l] > self.data[s] {
      s = l
    }
    if r <= n && self.data[r] > self.data[s] {
      s = r
    }
    if s != i {
      self.data.exchange(s, i)
      i = s
    } else {
      break
    }
  }
}

With these two basic operations, it becomes quite straightforward to implement generic array sorting and selecting the largest k elements. However, some boundary condition handling, such as resizing when capacity is exhausted, is not explicitly written in the insert and delete functions. The complete code is shared here: try.moonbitlang.com/#421122d5.

In situations with small data sets and frequent element insertions and deletions, binary heaps perform quite well, as mentioned by Poul-Henning Kamp in his article "You’re Doing It Wrong: Think you’ve mastered the art of server performance? Think again."

However, when dealing with larger data sets and memory constraints, using a multi-way heap would be preferable.

The binary heap implemented above exhibits a clear imperative style, while MoonBit, as a multi-paradigm language, also provides good support for functional programming. Next, I will use immutable data structures such as List and enumerations in MoonBit to implement a pairing heap.

03 Pairing Heap

Implemented here is a min-heap.

Pairing heap is a type of heap based on a multiway tree. It is simple to implement and offers superior performance. It is used to implement priority queues in the GNU libstdc++ library. The complexity analysis of its operations presents challenges, which will not be covered in this article.

https://brilliant.org/wiki/pairing-heap/

Since the structure of a pairing heap is a more general multiway tree, here we use an enum to define PHeap. A PHeap is either an empty tree or a node containing one element and N subtrees. This concept can be naturally expressed through an enumeration type.

enum PHeap[T] {
    Empty
    Node(T, List[PHeap[T]])
  }

In the context of pairing heaps, it will be convenient to define the merge operation for two heaps first. By pattern matching, we can clearly describe the logic of merging:

If one of h1 and h2 is empty, then keep the other one.
If both are not empty, then compare the top elements of each heap and put the heap with the larger element into the list of the other heap.

fn merge[T : Compare](h1 : PHeap[T], h2 : PHeap[T]) -> PHeap[T] {
    match (h1, h2) {
      (Empty, h2) => h2
      (h1, Empty) => h1
      (Node(x, ts1), Node(y, ts2)) => if x < y {
        Node(x, Cons(Node(y, ts2), ts1))
      } else {
        Node(y, Cons(Node(x, ts1), ts2))
      }
    }
  }

Insertion can be seen as merging a single-element heap into the original heap:

fn insert[T : Compare](self : PHeap[T], x : T) -> PHeap[T] {
    merge(self, Node(x, Nil))
  }

Popping the top element from the heap requires folding the entire list of heaps using merge, employing the consolidate function. It's worth noting that the consolidate function effectively implements a two-stage consolidation through recursion. First, it merges the pairs of heaps in the list, and then it merges these newly generated heaps together. This is manifested in the nested merge function calls in the code.

fn consolidate[T : Compare](ts : List[PHeap[T]]) -> PHeap[T] {
    match ts {
      Nil => Empty
      Cons(t, Nil) => t
      Cons(t1, Cons(t2, ts)) => merge(merge(t1, t2), consolidate(ts))
    }
  }

  fn pop[T : Compare](self : PHeap[T]) -> Option[PHeap[T]] {
    match self {
      Empty => None
      Node(_, ts) => Some(consolidate(ts))
    }
  }

The use of match and enumeration types makes the operations related to pairing heaps very concise. The complete code can be found here: try.moonbitlang.com/#a2f1dd62.

From the definition of pairing heaps and their operations, it can be observed that they do not extensively retain additional information such as tree size, depth, or rank in their structure. This allows them to avoid the poor constants associated with data structures like Fibonacci heaps, earning them a reputation for efficiency, simplicity, and flexibility in practice.

Implementing Haskell's G-Machine in MoonBit

Zachery Yee — Wed, 13 Mar 2024 07:39:02 +0000

Lazy evaluation stands as a foundational concept in the realm of programming languages. Haskell, renowned as a purely functional programming language, boasts a robust lazy evaluation mechanism. This mechanism not only empowers developers to craft code that's both more efficient and concise but also enhances program performance and responsiveness, especially when tackling sizable datasets or intricate data streams. This article will delve into the Lazy Evaluation mechanism, thoroughly examining its principles and implementation methods, and then explore how to implement Haskell's evaluation semantics in MoonBit, a Rust-like language and toolchain optimized for WebAssembly experience.
(website here: https://www.moonbitlang.com/)

Higher-Order Functions and Performance Challenges

Higher-order functions such as map and filter often serve as many people's first impression of functional programming (although it goes far beyond these functions). They simplify many list processing tasks, but another problem emerges: using too many of these higher-order functions can lead to poor performance (because it requires multiple traversals of the list).

To enhance code efficiency, some propose leveraging compiler optimizations based on recurring patterns within higher-order functions. For instance, by rewriting map(f, map(g, list)) as：

map(fn (x) { f(g(x)) }, list)

Nice try, but it's important to recognize that such optimization techniques have inherent limitations, particularly when navigating more complex scenarios. Consolidating all processes into a single function might circumvent the need for repeated list traversals, yet it detrimentally affects code readability and complicates the process of making modifications. Could there be a more equitable solution that balances efficiency with maintainability?

Lazy evaluation is a technique that can reduce unnecessary costs to some extent in such scenarios. This strategy can be integrated into specific data structures (for example, the Stream type added in Java 8, and the stream in the earlier Scheme language), or the entire language can be designed to be lazy (successful examples include the Miranda language of the 1980s and later by Haskell and Clean languages).

Let's first explore how lazy lists (Stream) can avoid multiple traversals in such cases.

Lazy List Implementation

First, let's define its type:

enum Stream[T] {
  Empty
  Cons(T, () -> Stream[T])
}

The only real difference between Stream[T] and List[T] is in the Cons: the place holding the rest of the list is replaced with a parameterless function (in jargon, called a thunk). This is a simple implementation of lazy evaluation: wrapping things you don't want to compute right away in a thunk.

A function to convert a regular list into a lazy list is also needed:

fn Stream::fromList[T](l : List[T]) -> Stream[T] {
  match l {
    Nil => Empty
    Cons(x, xs) => Cons(x, fn () { Stream::fromList(xs) })
  }
}

This function does not need to traverse the entire list to convert it into Stream. For operations that are not urgent (here, Stream::fromList(xs)), wrap them directly in a thunk and return. The following map function will adopt this approach (though here, xs is already a thunk).

fn stream_map[X, Y](self : Stream[X], f : (X) -> Y) -> Stream[Y] {
  match self {
    Empty => Empty
    Cons(x, xs) => Cons(f(x), fn () { xs().stream_map(f) })
  }
}

The take function is responsible for performing computations, and it can extract n elements as needed.

fn take[T](self : Stream[T], n : Int) -> List[T] {
  if n == 0 {
    Nil
  } else {
    match self {
      Empty => Nil
      Cons(x, xs) => Cons(x, xs().take(n - 1))
    }
  }
}

The implementation of lazy data structures using thunks is straightforward and effectively addresses the problems mentioned above. This method requires users to explicitly indicate where in the code computation should be delayed, whereas the strategy of lazy languages is much more aggressive: it defaults to using lazy evaluation for all user-defined functions! In the following sections, I will present a minimal implementation of a lazy functional language and briefly introduce its underlying theoretical model.

A Lazy Evaluation Language and Its Abstract Syntax Tree

The example used in this article is a lazy evaluation language, deliberately made to resemble Clojure (a Lisp dialect) and named coreF. This design choice allows for the use of Clojure's syntax highlighting in markdown. Don't worry, though the syntax might seem a bit complex at first, it is straightforward enough.

Functions are defined using the defn keyword:

(defn factorial[n] ;; n is the parameter, this function calculates the factorial of n
  (if (eq n 0) ;; The definition starts here and continues for the next three lines
    1
    (mul n (factorial (sub n 1))))

Referring to it as a function in general conversation is acceptable. However, when discussing lazy functional languages, we must introduce a specialized term: Super Combinator. In the definition of a super combinator, all free variables should be included in an initial pair of [].

Execution of a coreF program begins with main, calling a specific super combinator as if replacing it with its definition.

(defn main[] (factorial 42))

Super combinators without parameters, such as main, are referred to by a specific term: Constant Applicative Forms (CAF).

coreF also possesses several language features, including custom data structures, case expressions for dismantling structures, and let and letrec for the declaration of local variables. However, the scope of this article is limited to the aforementioned features (actually, even less, as built-in functions like eq, mul, sub, etc., are planned for future implementation).

coreF excludes anonymous functions because anonymous functions introduce extra free variables. Removing them requires an additional transformation step: lambda lifting. This technique can transform a lambda expression into an external Super Combinator, but this is not a main point of lazy evaluation, hence its omission here.

Super combinators will eventually be parsed into ScDef[String], but writing a parser is a tedious task. I will provide it along with the final code.

enum RawExpr[T] {
  Var(T)
  Num(Int)
  Constructor(Int, Int) // tag, arity
  App(RawExpr[T], RawExpr[T])
  Let(Bool, List[(T, RawExpr[T])], RawExpr[T]) // isRec, Defs, Body
  Case(RawExpr[T], List[(Int, List[T], RawExpr[T])])
}

struct ScDef[T] {
  name : String
  args : List[T]
  body : RawExpr[T]
} derive (Show)

Additionally, some predefined coreF programs are required.

let preludeDefs : List[ScDef[String]] = {
  let id = ScDef::new("I", arglist1("x"), Var("x")) // id x = x
  let k = ScDef::new("K", arglist2("x", "y"), Var("x")) // K x y = x
  let k1 = ScDef::new("K1", arglist2("x", "y"), Var("y")) // K1 x y = y
  let s = ScDef::new("S", arglist3("f", "g", "x"), App(App(Var("f"), Var("x")), App(Var("g"), Var("x")))) // S f g x = f x (g x)
  let compose = ScDef::new("compose", arglist3("f", "g", "x"), App(Var("f"), App(Var("g"), Var("x")))) // compose f g x = f (g x)
  let twice = ScDef::new("twice", arglist1("f"), App(App(Var("compose"), Var("f")), Var("f"))) // twice f = compose f f
  Cons(id, Cons(k, Cons(k1, Cons(s, Cons(compose, Cons(twice, Nil))))))
}

Why Graph

In the coreF language, expressions (not RawExpr[T] mentioned earlier, but runtime expressions) are stored in memory in the form of a graph rather than a tree when being evaluated.)

Why is this approach taken? Let's examine this through a program example:

(defn square[x]  (mul x x))
(defn main[] (square (square 3)))

If we evaluate according to the conventional expression tree, it would be reduced to:

(mul (square 3) (square 3))

In this case, (square 3) would be evaluated twice, which is certainly not desirable for lazy evaluation.

To illustrate this more clearly, let's make a somewhat improper analogy using MoonBit code:

fn square(thunk : () -> Int) -> Int {
  thunk() * thunk()
}

To represent the program using a graph is to facilitate sharing of computation results and avoid redundant calculations. To achieve this purpose, it's crucial to implement an in-place update algorithm when reducing the graph. Regarding in-place update, let's simulate it using MoonBit code:

enum LazyData[T] {
  Waiting(() -> T)
  Done(T)
}

struct LazyRef[T] {
  mut data : LazyData[T]
}

fn extract[T](self : LazyRef[T]) -> T {
  match self.data {
    Waiting(thunk) => {
      let value = thunk()
      self.data = Done(value) // in-place update
      value
    }
    Done(value) => value
  }
}

fn square(x : LazyRef[Int]) -> Int {
  x.extract() * x.extract()
}

Regardless of which side executes the extract method first, it will update the referenced mutable field and replace its content with the computed result. Therefore, there's no need to recompute it during the second execution of the extract method.

Conventions

Before delving into how graph reduction works, let's establish some key terms and basic facts. I'll continue using the same program as an example:

(defn square[x]  (mul x x)) ;; multiplication
(defn main[] (square (square 3)))

Built-in primitives like mul are predefined operations.
Evaluating an expression (of course, lazy) and updating its corresponding node in the graph in place is called reduction.
(square 3) is a reducible expression (often abbreviated as redex), consisting of square and its argument. It can be reduced to (mul 3 3). (mul 3 3) is also a redex, but it's a different type of redex compared to (square 3) because square is a user-defined combinator while mul is an implemented built-in primitive.
The reduction result of (mul 3 3) is the expression 9, which cannot be further reduced. Such expressions that cannot be further reduced are called Normal forms.
An expression may contain multiple sub-expressions (e.g., (mul (add 3 5) (mul 7 9))). In such cases, the order of reduction of expressions is crucial – some programs only halt under specific reduction orders.
There's a special reduction order that always selects the outermost redex for reduction, known as normal order reduction. This reduction order will be uniformly adopted in the following discussion.

So, the graph reduction can be described with the following pseudocode:

While there exist reducible expressions in the graph {
    Select the outermost reducible expression.
    Reduce the expression.
    Update the graph with the result of reduction.
}

Dizzy now? Let's find a few examples to demonstrate how to perform reductions on paper.

Step 1: Find the next redex

The execution of the entire program starts from the main function.

(defn square[x]  (mul x x))
(defn main[] (add 33 (square 3)))

main itself is a CAF - the simplest kind of redex. If you perform the substitution, the current expression to be handled is:

(add 33 (square 3))

According to the principle of finding the outermost redex, it seems like you've immediately found the redex formed by add and its two parameters (let's assume it for now).

But wait! Due to the presence of default currying, the abstract syntax tree corresponding to this expression is actually composed of multiple nested App nodes. It roughly looks like this (simplified for readability):

App(App(add, 33), square3)

This chain-like structure from add to the outermost App node is called the "Spine"

Going back to check, add is an internally defined primitive. However, since its second argument (square 3) is not in normal form, you cannot reduce it (adding an unevaluated expression to an integer seems a bit absurd). So, you can't definitively say that (add 33 (square 3)) is a redex; it's just the outermost function application. To reduce it, you must first reduce (square 3).

Step 2: Reduce

Since square is a user-defined super combinator, reducing (square 3) involves only parameter substitution.

If a redex has fewer arguments than required by the super combinator, which is common in higher-order functions, consider the example of tripling all integers in a list.

(map (mul 3) list-of-int)

Here, (mul 3) cannot be treated as a redex because it lacks sufficient arguments, making it a weak head normal form (often abbreviated as WHNF). In this situation, even if its sub-expressions contain redexes, no action is needed.

Step 3: Update

This step only affects execution efficiency and can be skipped during paper deductions.

These operations are easy to perform on paper (when the amount of code doesn't exceed half a sheet), but when you switch to computers, how to translate these steps into executable code?

To answer this question, pioneers in the world of lazy evaluation programming languages have proposed various abstract machines for modeling lazy evaluation. These include:

G-Machine
Three Instruction Machine
ABC Machine (used by the Clean language)
Spineless Tagless G-Machine (abbreviated as STG, used by Haskell language)

They are execution models used to guide compiler implementations. It's important to note that, unlike various popular virtual machines today (such as the JVM), abstract machines are more like intermediate representations (IR) for compilers. Taking Haskell's compiler GHC as an example, after generating STG (Spineless Tagless G-Machine) code, it doesn't directly pass it to an interpreter for execution. Instead, it further transforms it into LLVM, C code, or machine code based on the selected backend.

To simplify implementation, this article will directly use MoonBit to write an interpreter for G-Machine instructions, starting from a minimal example and gradually adding more features.

G-Machine Overview

While the G-Machine is an abstract machine for lazy functional languages, its structure and concepts are not significantly different from what one encounters when writing general imperative languages. It also features structures like heap and stack, and its instructions are executed sequentially. Some key differences include:

The basic unit of memory in the heap is not bytes, but graph nodes.
The stack only contains pointers to addresses in the heap, not actual data.

This design may not be practical, but it's relatively simple.

In coreF, super combinators are compiled into a series of G-Machine instructions. These instructions can be roughly categorized as follows:

Access Data Instructions, For example, PushArg (access function arguments), and PushGlobal (access other super combinators).
Construct/update graph nodes in the heap, like MkApp, PushInt, Update
Clean up the Pop instruction of the unused addresses from the stack.
Express control flow with the Unwind instruction

Dissecting the G-Machine State

In this simple version of the G-Machine, the state includes:

Heap: This is where the expression graph and the sequences of instructions corresponding to super combinators are stored.

type Addr Int derive(Eq, Show) // Use the 'type' keyword to encapsulate an address type.

enum Node { // Describe graph nodes with an enumeration type.
  NNum(Int)
  NApp(Addr, Addr) // The application node
  NGlobal(Int, List[Instruction]) // To store the number of parameters and the corresponding sequence of instructions for a super combinator.
  NInd(Addr) // The Indirection node，The key component of implementing lazy evaluation
} derive (Eq)

struct GHeap { // The heap uses an array, and the space with None content in the array is available as free memory.
  mut objectCount : Int
  memory : Array[Option[Node]]
}

// Allocate heap space for nodes.
fn alloc(self : GHeap, node : Node) -> Addr {
  let heap = self
  // Assuming there is still available space in the heap.
  fn next(n : Int) -> Int {
    (n + 1) % heap.memory.length()
  }
  fn free(i : Int) -> Bool {
    match heap.memory[i] {
      None => true
      _    => false
    }
  }
  let mut i = heap.objectCount
  while not(free(i)) {
    i = next(i)
  }
  heap.memory[i] = Some(node)
  return Addr(i)
}

Stack: The stack only holds addresses pointing to the heap. A simple implementation can use List[Addr].
Global Table: It's a mapping table that records the names of super combinators (including predefined and user-defined) and their corresponding addresses as NGlobal nodes. Here I implement it using a Robin Hood hash table.
Current code sequence to be executed.
Execution status statistics: A simple implementation involves calculating how many instructions have been executed.

type GStats Int

let statInitial : GStats = GStats(0)

fn statInc(self : GStats) -> GStats {
  let GStats(n) = self
  GStats(n + 1)
}

fn statGet(self : GStats) -> Int {
  let GStats(n) = self
  return n
}

The entire state is represented using the type GState.


struct GState {
  stack : List[Addr]
  heap : GHeap
  globals : RHTable[String, Addr]
  code : List[Instruction]
  stats : GStats
}

fn putStack(self : GState, addr : Addr) {
  self.stack = Cons(addr, self.stack)
}

fn putCode(self : GState, is : List[Instruction]) {
  self.code = append(is, self.code)
}

fn pop1(self : GState) -> Addr {
  match self.stack {
    Cons(addr, reststack) => {
      self.stack = reststack
      addr
    }
    Nil => {
      abort("pop1: stack size smaller than 1")
    }
  }
}

fn pop2(self : GState) -> (Addr, Addr) {
  // Pop 2 pops the top two elements from the stack.
  // Returns (the first, the second).
  match self.stack {
    Cons(addr1, Cons(addr2, reststack)) => {
      self.stack = reststack
      (addr1, addr2)
    }
    otherwise => {
      abort("pop2: stack size smaller than 2")
    }
  }
}

Now, you can map each step of the graph reduction algorithm you deduced on paper to this abstract machine:

At the initial state of the machine, all compiled super combinators have been placed in NGlobal nodes on the heap. At this point, the current code sequence in the G-Machine contains only two instructions. The first instruction pushes the address of the main node onto the stack, and the second instruction loads the corresponding code sequence of main into the current code sequence.
The corresponding code sequence of main is instantiated on the heap, where nodes are allocated and data is loaded accordingly, ultimately constructing a graph in memory. This process is referred to as "instantiating" main. Once instantiation is complete, the address of the entry point of this graph is pushed onto the stack.
After instantiation is finished, cleanup work is done, which involves updating graph nodes (since main has no parameters, there is no need to clean up residual unused addresses in the stack) and finding the next redex.

All of these tasks have corresponding instruction implementations.

Corresponding Effect of Each Instruction

The highly simplified G-Machine currently consists of 7 instructions.

enum Instruction {
  Unwind
  PushGlobal(String)
  PushInt(Int)
  PushArg(Int)
  MkApp
  Update(Int)
  Pop(Int)
} derive (Eq, Debug, Show)

The PushInt instruction is the simplest. It allocates an NNum node on the heap and pushes its address onto the stack.

fn pushint(self : GState, num : Int) {
  let addr = self.heap.alloc(NNum(num))
  self.putStack(addr)
}

The PushGlobal instruction retrieves the address of the specified super combinator from the global table and then pushes the address onto the stack.

fn pushglobal(self : GState, name : String) {
  let sc = self.globals[name]
  match sc {
    None => abort("pushglobal(): cant find super combinator \(name)")
    Some(addr) => {
      self.putStack(addr)
    }
  }
}

The PushArg instruction is a bit more complex. It has specific requirements regarding the layout of addresses on the stack: the first address should point to the super combinator node, followed by n addresses pointing to N NApp nodes. PushArg retrieves the Nth parameter, starting from the offset + 1.

fn pusharg(self : GState, offset : Int) {
  // Skip the first super  combinator node.
  // Access the (offset + 1)th NApp node
  let appaddr = nth(self.stack, offset + 1)
  let arg = match self.heap[appaddr] {
    NApp(_, arg) => arg
    otherwise => abort("pusharg: stack offset \(offset) address \(appaddr) node \(otherwise), not a applicative node")
  }
  self.putStack(arg)
}

The MkApp instruction takes two addresses from the top of the stack, constructs an NApp node, and pushes its address onto the stack.

fn mkapp(self : GState) {
  let (a1, a2) = self.pop2()
  let appaddr = self.heap.alloc(NApp(a1, a2))
  self.putStack(appaddr)
}

The Update instruction assumes that the first address on the stack points to the current redex's evaluation result. It skips the addresses of the immediately following super combinator nodes and replaces the Nth NApp node with an indirect node pointing to the evaluation result. If the current redex is a CAF, it directly replaces its corresponding NGlobal node on the heap. From this, you can see why in lazy functional languages, there is not much distinction between functions without parameters and ordinary variables.

fn update(self : GState, n : Int) {
  let addr = self.pop1()
  let dst = nth(self.stack, n)
  self.heap[dst] = NInd(addr)
}

The Unwind instruction in the G-Machine is akin to an evaluation loop. It has several branching conditions based on the type of node corresponding to the address at the top of the stack:

For Nnum nodes: Do nothing.
For NApp nodes: Push the address of the left node onto the stack and Unwind again.
For NGlobal nodes: If there are enough parameters on the stack, load this super combinator into the current code.
For NInd nodes: Push the address contained within this indirect node onto the stack and Unwind again.

fn unwind(self : GState) {
  let addr = self.pop1()
  match self.heap[addr] {
    NNum(_) => self.putStack(addr)
    NApp(a1, _) => {
      self.putStack(addr)
      self.putStack(a1)
      self.putCode(Cons(Unwind, Nil))
    }
    NGlobal(_, n, c) => {
      if length(self.stack) < n {
        abort("Unwinding with too few arguments")
      } else {
        self.putStack(addr)
        self.putCode(c)
      }
    }
    NInd(a) => {
      self.putStack(a)
      self.putCode(Cons(Unwind, Nil))
    }
    otherwise => abort("unwind() : wrong kind of node \(otherwise), address \(addr)")
  }
}

The Pop instruction pops N addresses, eliminating the need for a separate function implementation.

Compiling Super Combinators into Instruction Sequences

In the G-Machine Overview section, I roughly described the behavior of compiled super combinators. Now I'll precisely describe the compilation process of super combinators.

Firstly, before the instruction sequence of a compiled super combinator is executed, there must be certain addresses already present in the stack:

The topmost address points to an NGlobal node (the super combinator itself).
Following are N addresses (N being the number of parameters for this super combinator), pointing to a series of App nodes - corresponding exactly to the spine of a redex. The bottommost address in the stack points to the outermost App node of the expression, and the rest follow suit.

When compiling a super combinator, you need to maintain an environment that allows us to find the relative position of parameters in the stack during the compilation process by their names. Additionally, since clearing the preceding N+1 addresses is necessary after completing the instantiation of a super combinator, the number of parameters N needs to be passed as well.

Here, "parameters" refer to addresses pointing to App nodes on the heap, and the actual parameter addresses can be accessed through the pusharg instruction.

fn compileSC(self : ScDef[String]) -> (String, Int, List[Instruction]) {
  let name = self.name
  let body = self.body
  let mut arity = 0
  fn gen_env(i : Int, args : List[String]) -> List[(String, Int)] {
    match args {
      Nil => {
        arity = i
        return Nil
      }
      Cons(s, ss) => Cons((s, i), gen_env(i + 1, ss))
    }
  }
  let env = gen_env(0, self.args)
  (name, arity, compileR(body, env, arity))
}

The compileR function generates code for instantiating super combinators by calling the compileC function, and then appends three instructions:

Update(N): Updates the original redex in the heap to an NInd node, which then points to the newly instantiated super combinator.
Pop(N): Clears the stack of redundant addresses.
Unwind: Searches for the next redex to start the next reduction.

fn compileR(self : RawExpr[String], env : List[(String, Int)], arity : Int) -> List[Instruction] {
  if arity == 0 {
    // The Pop 0 instruction does nothing in practice, so it is not generated when the arity is 0.
    append(compileC(self, env), from_array([Update(arity), Unwind]))
  } else {
    append(compileC(self, env), from_array([Update(arity), Pop(arity), Unwind]))
  }
}

When compiling the definition of super combinators, a rather crude approach is used: if a variable is not a parameter, it is treated as another super combinator (writing it incorrectly will result in a runtime error). For function application, the right-hand expression is compiled first, then all offsets corresponding to parameters in the environment are incremented (because an extra address pointing to the instantiated right-hand expression is added to the top of the stack), then the left-hand expression is compiled, and finally the MkApp instruction is added.

fn compileC(self : RawExpr[String], env : List[(String, Int)]) -> List[Instruction] {
  match self {
    Var(s) => {
      match lookupENV(env, s) {
        None => from_array([PushGlobal(s)])
        Some(n) => from_array([PushArg(n)])
      }
    }
    Num(n) => from_array([PushInt(n)])
    App(e1, e2) => {
      append(compileC(e2, env), append(compileC(e1, argOffset(1, env)), from_array([MkApp])))
    }
    _ => abort("not support yet")
  }
}

Running the G-Machine

Once the super combinators are compiled, they need to be placed on the heap (along with adding their addresses to the global table). This can be done recursively.

fn buildInitialHeap(scdefs : List[(String, Int, List[Instruction])]) -> (GHeap, RHTable[String, Addr]) {
  let heap = { objectCount : 0, memory : Array::make(10000, None) }
  let globals = RHTable::new(50)
  fn go(lst : List[(String, Int, List[Instruction])]) {
    match lst {
      Nil => ()
      Cons((name, arity, instrs), rest) => {
        let addr = heap.alloc(NGlobal(name, arity, instrs))
        globals[name] = addr
        go(rest)
      }
    }
  }
  go(scdefs)
  return (heap, globals)
}

Define a function "step" that updates the state of the G-Machine by one step, returning false if the final state has been reached.

fn step(self : GState) -> Bool {
  match self.code {
    Nil => { return false }
    Cons(i, is) => {
      self.code = is
      self.statInc()
      match i {
        PushGlobal(f) => self.pushglobal(f)
        PushInt(n) => self.pushint(n)
        PushArg(n) => self.pusharg(n)
        MkApp => self.mkapp()
        Unwind => self.unwind()
        Update(n) => self.update(n)
        Pop(n) => { self.stack = drop(self.stack, n) } // without the need for additional functions
      }
      return true
    }
  }
}

Additionally, define a function "reify" that continuously executes the "step" function until the final state is reached.

fn reify(self : GState) {
  if self.step() {
    self.reify()
  } else {
    let stack = self.stack
    match stack {
      Cons(addr, Nil) => {
        let res = self.heap[addr]
        println("\(res)")
      }
      _ => abort("wrong stack \(stack)")
    }
  }
}

Combine the above components.

fn run(codes : List[String]) {
  fn parse_then_compile(code : String) -> (String, Int, List[Instruction]) {
    let code = TokenStream::new(code)
    let code = parseSC(code)
    let code = compileSC(code)
    return code
  }
  let codes = append(map(parse_then_compile, codes), map(compileSC, preludeDefs))
  let (heap, globals) = buildInitialHeap(codes)
  let initialState : GState = {
    heap : heap,
    stack : Nil,
    code : initialCode,
    globals : globals,
    stats : initialStat
  }
  initialState.reify()
}

Conclusion

The features of the G-Machine constructed so far are too limited to run even a somewhat decent program. In the next article, I will incrementally add features such as primitives and custom data structures. Towards the end, lazy evaluation techniques will be introduced after covering the G-Machine.

Reference

Peyton Jones, Simon & Lester, David. (2000). Implementing functional languages: a tutorial.