A Bunch of Odysseus Pseudocode I Guess
Tags: calypso, rust, langdev
Published: 2021-03-17 20:22:52

Hey there! Sorry for the small hiatus.

# Calypso

## Notes and Thoughts

- I've mostly finished the redesign of the syntax. I'm working on [writing a EBNF grammar][0] to both (semi-)specify the language and to make it easier to write the parser once it comes to that part.
- I've also got a bit of syntax highlighting working. There's [a VSCode extension][1], but be aware it's pretty buggy and I'm going to rewrite it anyway once I'm done writing the EBNF grammar.

## TODOs

- Finish EBNF grammar
- Redo syntax highlighting
- Finish lexer rewrite

# Odysseus

## Notes and Thoughts

- I've been working a little bit on the design of Odysseus. It's probably going to be somewhat inspired by the BEAM (cause it's pretty good, to be honest, and I have no dang clue how to write a VM). Here's an example of the code so far:
```
// Factorial (recursive) and hello world
// PSEUDOCODE -- Subject to change

/*
fn factorial(0);
fn factorial(1) ->
    1
end

fn factorial(n) where n > 1 ->
    n * factorial(n - 1)
end

fn hello() ->
    println("Hello, world!")
end
*/

fn factorial/1 ->
label @0:
    register %n, const fnarg:0
    select %n, @2, [(uint(1), @1), (uint(2), @1)]
label @1:
    ret uint(1)
label @2:
    test_guard is_gt, [%n, uint(1)]
    $0 = call_ext_dispatch 1, &:"gaia.ops.Sub.sub", %n, [uint(1)]
    $1 = call 1, &:"factorial", @0, [$0]
    $2 = call_ext_dispatch 1, &:"gaia.ops.Mul.mul", %n, [$1]
    ret $2
end

data ->
    0: string("Hello, world!")
end

fn hello/0 ->
label @0:
    call_ext_tail 1, &:"atlas.io.println", [data:0]
end
```

Let's go through this (roughly) line-by-line. Ignore the comments at the start, those are just info about the file and the source code. Let's start with `hello/0`. This is the code that corresponds to it:
```
data ->
    0: string("Hello, world!")
end

fn hello/0 ->
label @0:
    call_ext_tail 1, &:"atlas.io.println", [data:0]
end
```

The first section there is the data section. It defines a single entry in the data section of the binary, `data:0`, which is a string, `"Hello, world!"`.

Then, the function.

`fn hello/0 ->` defines the function `hello/0` (`hello` with arity 0, i.e. 0 arguments).

Then, we define label `@0`, the first label to be executed when calling the function.

Inside that label, we have one instruction:
```
call_ext_tail 1, &:"atlas.io.println", [data:0]
```

`call_ext_tail` means to do a [tail call][2] of an external function. Tail calls are helpful because they can allow tail call optimization, which is where a call instruction (which requires a stack frame) can be turned into a simple jump.

The next argument to that instruction, `1`, is the arity of the function. Then we have the name of the function, `atlas.io.println`. The syntax `&:"atlas.io.println"` is just a function reference to the name of the function as an atom. Note that this is just pseudocode, so this syntax will probably look different in the future.

Then, we have our last argument, the list of arguments to the function: `[data:0]`. `data:0` is simply a reference to the `0`th entry in the data section of the binary. Thus, `data:0` is a reference to the `"Hello, world!"` string. Thus, this simply calls `println("Hello, world!")`.

Next, let's go through the factorial function. This one is a bit more complex.

```
fn factorial/1 ->
label @0:
    register %n, const fnarg:0
    select %n, @2, [(uint(1), @1), (uint(2), @1)]
label @1:
    ret uint(1)
label @2:
    test_guard is_gt, [%n, uint(1)]
    $0 = call_ext_dispatch 1, &:"gaia.ops.Sub.sub", %n, [uint(1)]
    $1 = call 1, &:"factorial", @0, [$0]
    $2 = call_ext_dispatch 1, &:"gaia.ops.Mul.mul", %n, [$1]
    ret $2
end
```

First, we define the function:
```
fn factorial/1 ->
```

Then, we define the label `@0`. Inside it, we initialize the register `%n` as a register corresponding to the first function argument (which is a constant). Then, we do a pattern match over `%n`:
```
select %n, @2, [(uint(1), @1), (uint(2), @1)]
```

`select` is an instruction that matches over the register provided and jumps to the labels provided, or a label for failure to match.

In this case, it matches over `%n`. If it's `uint(1)` (the unsigned integer 1), it jumps to `@1`. If it's `uint(2)`, it also jumps to `@1`. Otherwise, in failure, it jumps to `@2`.

The label `@1` just contains one instruction: `ret uint(1)`. This simply returns the unsigned integer 1.

The label `@2` is a bit more complicated. This is the case where we run `n * factorial(n - 1)`.

```
label @2:
    test_guard is_gt, [%n, uint(1)]
    $0 = call_ext_dispatch 1, &:"gaia.ops.Sub.sub", %n, [uint(1)]
    $1 = call 1, &:"factorial", @0, [$0]
    $2 = call_ext_dispatch 1, &:"gaia.ops.Mul.mul", %n, [$1]
    ret $2
```

We first test the function guard, which is `n > 1`. To do this, we test `is_gt` (is greater than), with the arguments `%n` and `uint(1)`. In the case of failure, it will cause an exception as it is the only remaining guard.

Then, we set the temporary register `$0` (prefixed by `$` rather than `%`) to the value of `call_ext_dispatch 1, &:"gaia.ops.Sub.sub", %n, [uint(1)]`

This function dispatches an external trait function. The first argument is the arity of the function, excluding the `self` argument. The second argument is the trait function, in this case `gaia.ops.Sub.sub`. The third argument is the `self` object, in this case, `%n`. The last argument is the list of arguments, in this case simply `[uint(1)]`.

This is equivalent to `n - 1`, just with operator overloading via traits.

Then, we set the temporary register `$1` to the value of `call 1, &:"factorial", @0, [$0]`. `call` is a non-tail call in the local module. The first argument is, again, the arity. The second is the function name, in this case `factorial`. The third argument is the label of that function, which can help to enable optimizations. In this case, we just use the entry label (`@0`). The final argument is the list of arguments, in this case, just `$0` which was set to `n - 1`.

We then do a similar thing to the subtraction for the multiplication, just switching out the registers and trait function. Then, finally, we return `$2`, which is now equal to `n * factorial(n - 1)`.

I hope this made some semblance of sense, but if it doesn't, feel free to comment or talk to me on Discord. Note that this is all pseudocode and is subject to change.

## TODOs

- Solidify ABI and ISA
- Pretty much everything

# Calypso Build Tool

I need a name for the Calypso build tool (kinda like `cargo` for Rust or `mix` for Elixir), but I'm bad at naming things. If you have any ideas, leave a comment or DM me on Discord!

# Conclusion

Basically, it's going well! :)

If you find anything that I might've missed or you'd like more information on, feel free to comment or otherwise contact me!

Otherwise, have a good morning/afternoon/evening/night/etc.!
-James

[0]: https://github.com/calypso-lang/calypso/blob/main/pseudocode-design/calypso.bnf
[1]: https://github.com/calypso-lang/calypso-syntax-highlighting
[2]: https://en.wikipedia.org/wiki/Tail_call