[PYTHON] Until you self-host your own interpreter

I am making an interpreter called Calcium. This time, I looked back on implementing the Calcium interpreter in the Calcium language itself.

What is the Calcium language?

First, let's try Hello, World.

hello.json

[
  [1, [], "#", "0_18"],
  [1, [], "call", null, ["var", "print"], ["Hello, World!"]],
  [1, [], "end"]
]

The Calcium language code is made up of JSON arrays. The reason I tried to write the code in JSON is that it doesn't require lexical analysis (JSON.parse () etc.). I also somehow thought that it would probably be compatible with the Web environment. If it can be described as a data format, it could be used for something. (When I looked it up later, for example, I think I saw somewhere that Scratch's internal VM is writing code in JSON.) So, writing Calcium in Calcium means writing an interpreter in JSON? ** But no one feels like writing such code directly. It will be a program that suffers from parentheses as much as LISP. In addition, there are more commas and double quotes.

Convert from Python to Calcium (JSON)

Fortunately, Calcium code can now be converted from a ** subset ** of Python. From the beginning, I was conscious of Python and decided the instructions to support. At first glance, the above example looks like an assembly-like mnemonic code. But it's Python that's affected. Each element of a Calcium JSON array (also an array) corresponds to a line in Python. Use Python's ʻastmodule to output the corresponding Calcium code from Python code. In Calcium, the integer of the first item corresponds to the indent. Block statements increase indentation. For example, the followingfor` statement

loop.py

for i in range(10):
    print(i)

It is converted as follows. (Indentation is for good looks)

loop.json

[
  [1, [], "#", "0_18"],
  [1, [], "for range", "i", [10]],
    [2, [], "call", null, ["var", "print"], [["var", "i"]]],
  [1, [], "end"]
]

I wrote ** subset ** of Python earlier, but there are restrictions on how to actually convert to the Calcium language. This means that you can only use some of Python's language features. There are other "bindings" such as function calls being statements rather than expressions. However, basic syntax such as for, while, ʻif-elif-else, def, class` can be converted to Calcium. That is, the Calcium interpreter supports those instructions. It's a bit long, but the following can be converted into valid Calcium code.

sample.py

def is_remainder_zero(a, b):
    return (a % b) == 0

prime = []
for i in range(101):
    j = 2
    while j < i:
        is_zero = is_remainder_zero(i, j)
        if is_zero:
            break
        else:
            j += 1
    if j == i:
        prime.append(i)
result = prime
print(result)

sample.json

[
  [1, [], "#", "0_18"],
  [1, [], "def", "is_remainder_zero", ["a", "b"]],
    [2, [], "return", ["==", ["%", ["var", "a"], ["var", "b"]], 0]],
  [1, [], "=", ["var", "prime"], [[]]],
  [1, [], "for range", "i", [101]],
    [2, [], "=", ["var", "j"], 2],
    [2, [], "while", ["<", ["var", "j"], ["var", "i"]]],
      [3, [], "call", ["var", "is_zero"], ["var", "is_remainder_zero"], [["var", "i"], ["var", "j"]]],
      [3, [], "ifs"],
        [4, [], "if", ["var", "is_zero"]],
          [5, [], "break"],
        [4, [], "else"],
          [5, [], "+=", ["var", "j"], 1],
    [2, [], "ifs"],
      [3, [], "if", ["==", ["var", "j"], ["var", "i"]]],
        [4, [], "call", null, ["attr", "prime", "append"], [["var", "i"]]],
  [1, [], "=", ["var", "result"], ["var", "prime"]],
  [1, [], "call", null, ["var", "print"], [["var", "result"]]],
  [1, [], "end"]
]

I was able to convert from a Python subset, with major differences such as function call statements and two-tier nesting of ʻif` statements. The converter takes a Python subset as input and outputs Calcium code. (This converter is called py3ca.py) This means that if you implement the Calcium interpreter in a Python subset, you can output the Calcium interpreter written by Calcium itself.

Implementation of Calcium interpreter

Currently, Calcium is implemented in JavaScript or Python. There are differences in each implementation (try-except support, equality operator behavior, etc.), but it reads and executes the JSON array as described above.

Implementation of calcium.js

We first implemented it in JavaScript as an environment that can be run in a browser. The reason is that you can use the debugger function. First of all, it was appropriate to implement it in JavaScript to see if it could be implemented.

Realization of ʻif`

In the Calcium language, each instruction is placed in tiled two-dimensional coordinates. The current address is represented by (indent, array index). For example, the ʻif` instruction evaluates the conditional expression and increments the indent by one if true (to the right of the figure). If false, increase the index without changing the indent (downward). Details of execution order can be found here. The image is to use indentation in Python code as a number at runtime.

Realization of for statement

Since function calls are statements in Calcium, we had to separate the iterations such as for i in range (10): from the foreach statement for elem in my_list:. Corresponds to the for range and for each instructions, respectively.

Implementation of calcium.py

Ported calcium.js to Python. As mentioned above, I had to implement calcium.py with the limitation that I could only use some of Python's language features. For example

--You can use up to one function call in one statement. --Up to one variable (including attributes and elements) on the left side of the assignment. --Lambda expressions cannot be used (closures can be used). --You cannot specify optional arguments.

There were many restrictions such as, but when I implemented it, I was able to write it unexpectedly well. In total, it fits in about 1500 lines of code (calcium.js is about 2500 lines). Calcium.py doesn't support try-except, and so on, but I didn't expect it to be this short.

Load calcium.py into py3ca.py

This is the main subject. Since it is a program that converts a Python subset into Calcium code, passing calcium.py will output the code that describes Calcium in Calcium. The result is about 1300 lines. It is shorter than calcium.py because there are no blank lines. Located here.

Run the Calcium interpreter

Currently, only calcium.js supports try-except, so check if Calcium can run Calcium on it. I prepared the following code.

cac03.py

class Engine:
    # calcium.Contents of py...
code = [
  [1, [], "#", "0_18"],
  [1, [], "call", None, ["var", "print"], ["Hello, World!"]],
  [1, [], "end"]
]
engine = Engine(code)
engine.run()

Load this into py3ca.py.

cac03.json

[
  [1, [], "#", "0_18"],
  [1, [], "class", "Engine", "object"],
 ...Abbreviation...
  [1, [], "=", ["var", "code"], [[[[1, [[]], "#", "0_18"]], [[1, [[]], "call", null, [["var", "print"]], [["Hello, World!"]]]], [[1, [[]], "end"]]]]],
  [1, [], "call", ["var", "engine"], ["var", "Engine"], [["var", "code"]]],
  [1, [], "call", null, ["attr", "engine", "run"], []],
  [1, [], "end"]
]

Pass it to calcium.js.

const code = [...]; //JSON array above
const engine = new calcium.Engine(code);
engine.setPrintFunction((desc) => { console.log(desc); });
engine.run();

This completes the execution.

Finally (promotion ...)

Calcium is characterized by being written in a JSON array, but it supports functions such as simple functions and classes.

Application of Calcium

When I searched for a good way to edit the JSON array, I found Blockly. I won't go into details, but you can access the development editor here (https://crepekit.web.app/). We aim to be a visual editor that programming beginners can use before learning Python. (This editor environment uses calcium.js)

Calcium is open source

If you are interested, please contact us from GitHub. We are also looking for people to discuss and develop with us. We would appreciate it if you could give us your opinions.