DEV Community

James [Undefined]
James [Undefined]

Posted on

A Bunch of Odysseus Pseudocode I Guess

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 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, 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

call_ext_tail means to do a tail call 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 0th 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
Enter fullscreen mode Exit fullscreen mode

First, we define the function:

fn factorial/1 ->
Enter fullscreen mode Exit fullscreen mode

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)]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Discussion (0)