elodie

Elodie Programming Language

A statically typed language written in Go.

• About
  • Variables
  • For
  • If
  • Functions
  • Operators
• Compiler
  • Literals
  • Preallocated
  • Instructioned
    • Summary
    • 35th Fibonacci number using a non tail-recursive recursive alogrithm
    • Mandelbrott from PHP bench.php
  • Contributing

About

Elodie is an experimental interpreted language in the early stages of development.

    # run the tests and benchmarks
    go test -bench=. ./...
    
    # build the binary
    go build cmd/elodie.go
    
    # run a program
    ./elodie exec example/fib35r.e

    # show compiler output
    ./elodie compile example/fib35r.e

Elodie consists of:

• a Lexer producing a sequence of tokens from a source file.
• a Parser generating an Abstract Syntax Tree from the lexed tokens.
• a Single pass Compiler generating byte-code from the AST.
• a Register Machine executing byte-code, running the program.

Elodie currently has support for a few constructs and types.

Variables

Variables are declared implicitly, are scoped in the current function, are prefixed with $ and cannot change type. Multiple variables can be assigned separated by commas.

eg.

// an int
$someInt = 3

// a float
$someFloat = 1.23

// a boolean
$someBool = true

// multiple assignment of 1
$a, $b, $c = 1

// mutliple assignment of multiple types
$a, $b, $c = 1, 1.1, false

// arrays
$a = [2]int{1,2} // an array of 2 ints [1,2]
$a = [3]bool{} // an array of 3 booleans with nil values, [false, false, false] 

For

For loops can take multiple (traditional) forms

// 0 conditions
for {}

// 1 condition
$a = true
for $a { $a = false; }

// 2 conditions
for $a = true; $a { $a = false; }

// 3 conditions
for $a = 1; $a < 10; $a = $a + 1 { print $a; }

If

If statements can have a single condition argument or an assignment and condition argument. Else if's are supported in the same manor.

    $t = fn()(bool){return false;}
    if $f = $t(); $f == false {
        println !$f // prints true
    }
    $a = 1
    if $a < 10 {
        print 1
    } else if $b = 1; $b < 11 {
        print "2"
    } else if $a {
        print true
    } else {
        print 4.0
    }

Functions

Functions are defined using the fn keyword and may have multiple arguments and multiple returns. Anonymous functions are supported by assignment.

fn inc($a int) (int) { return $a + 1; }
fn add($a int, $b int) (int) { return $a + $b; }
fn quorem($num int, $quo int) (int, int) { return $num / $quo, $num % $quo; }
fn arr($a [3]int)([3]int){ return $a; }
$a = fn ($a float, $b float) (float) { return $a + $b; }
$a = fn ($a [2]float, $b [2]float ) (bool) { return $a == $b; }
inc(1);
add(1,2);
$quo, $rem = quorem(10, 3);
$added = $a(1.1, 2.2);

Operators

Compiler

I took a make it up as you go along approach. This was an attempt at getting a first hand appreciation for challenges and resulted in what I believe to be my own limited approach, a couple of compiler textbooks and a plan to migrate to a SSA based IR with a future rewrite.

Currently the compiler uses a mechanism I made up called VRWC, Variable Read Write Count. This is in some part similar to an SSA approach (as I found out) as it identifies things that can change and adjusts behaviour as such.

Coupled with a desire to attempt to execute quickly and some limitations or difficulties presented by Go, I settled on catagorising variables as Literal, Preallocated or Instructed.

Literals

Literal values have no writes in a loop context. An example of VRWC doing something useful:

$a = [2][2]int{{1,2},{3,4}};
if $a[0][0] == 2 {
    $i = 0;
} else {
    $i = 1;
}
println $a[1][$i];

The compiler is able to determine that $i will always be equal to 1 and that the value at $a[1][1] is always 4. The resulting instruction generated is PrintLnIntLit 4 (print out the number 4). This is an example of what I found through reading to be coined, dead code elimination (in a rudimentary form).

Literal expressions can be evaluated by the compiler:

$a = [2]int{1+1, 3*7};
print $a;

This results in 2 PrintIntLit instructions for the int values 2 and 21 and is an example of constant folding.

Preallocated

In an attempt to speed up execution, Frames may be generated with 'registers' already set to values. There are slices for ints, floats, bools and strings in the IR which are likely only bounded by memory constraints.

In situations where values may be read dynamically in a way the compiler cannot determine, values are prepopulated in the type specific frame registers. For example:

$a = [2]int{1,2};
for $i = 0; $i < len($a); $i = $i + 1 {
    println $a[$i];
}

The int register is prepopulated with the values 1 and 2. As the value of $i changes through iteration, the index that is retrieved from the ints register is adjusted accordingly. This is a good example of the limitations of the VRWC approach; the compiler could know that $i can only be 0 or 1 and issue 2 PrintLnIntLit instructions, but currently does not. As I learn more about optimisations, I hope to revisit topics such as this.

Instructioned

In situations where a value changes dynamically (for example in a loop) and is not categorised as Literal or Preallocated, an initial value is prepopulated and a reference kept to the register index. Any mutations are then performed by instructions.

Summary

For the fib(35) test, PHP 7.1 was the clear winner with 1.5s, Elodie came in 2nd place with 1.938s and Python 2.7 3rd with 4.6s.

For the Mandelbrot 100x100 test, PHP 7.1 was the clear winner with 0.92s, Elodie came in 2nd place with 1.250s

35th Fibonacci number using a non tail-recursive recursive alogrithm

All tests run on a 2012 iMac

go-lua

function fib(n)
    if n == 0 then
      return 0
    elseif n == 1 then
      return 1
    end
    return fib(n-1) + fib(n-2)
end

print(fib(35))

$ time ./fib

9227465

real 0m7.211s
user 0m7.090s
sys	 0m0.038s

python 2.7

def fibonacci(n):
    if n == 0:
        return n
    if n == 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print fibonacci(35)

$ time python fib.py

9227465

real 0m4.586s
user 0m4.396s
sys	 0m0.046s

elodie 0.0.1

fn fib ($n int) (int) {
    if $n == 0 {
        return 0;
    } else if $n == 1 {
        return 1;
    }
    return fib($n-2) + fib($n-1);
}

println fib(35);

$ time elodie exec fib.elodie

9227465

real	0m1.938s
user	0m1.934s
sys     0m0.004s

php 7.1

<?php
function fib($num){
    if($num==0){
       return 0;
    }else if($num == 1){
       return 1;
    }  else {
        return (fib($num-1) + fib($num-2));
    }
}
echo fib(35).PHP_EOL;

$ time php fib.php

9227465

real    0m1.507s
user    0m1.495s
sys     0m0.010s

Mandelbrott from PHP bench.php

php 7.1

<?php
function mandel() {
  $w1=100;
  $h1=100;
  $recen=-.45;
  $imcen=0.0;
  $r=0.7;
  $s=0;  $rec=0;  $imc=0;  $re=0;  $im=0;  $re2=0;  $im2=0;
  $x=0;  $y=0;  $w2=0;  $h2=0;  $color=0;
  $s=2*$r/$w1;
  $w2=40;
  $h2=12;
  for ($y=0 ; $y<=$w1; $y=$y+1) {
    $imc=$s*($y-$h2)+$imcen;
    for ($x=0 ; $x<=$h1; $x=$x+1) {
      $rec=$s*($x-$w2)+$recen;
      $re=$rec;
      $im=$imc;
      $color=1000;
      $re2=$re*$re;
      $im2=$im*$im;
      while( ((($re2+$im2)<1000000) && $color>0)) {
        $im=$re*$im*2+$imc;
        $re=$re2-$im2+$rec;
        $re2=$re*$re;
        $im2=$im*$im;
        $color=$color-1;
      }
      if ( $color==0 ) {
        print "_";
      } else {
        print "#";
      }
    }
    print PHP_EOL;
    flush();
  }
}
mandel();

$ time php man.php

real 0m0.926s
user 0m0.821s
sys	 0m0.052s

elodie 0.0.1

fn mandel() {
    $w1 = 100.0;
    $h1 = 100.0;
    $recen = -0.45;
    $r = 0.7;
    $imcen, $s, $rec, $imc, $re, $im, $re2, $im2, $x, $y, $w2, $h2 = 0.0;
    $color = 0;
    $s = 2.0 * $r / $w1;
    $w2 = 40.0;
    $h2 = 12.0;
    for $y = 0.0; $y <= $w1; $y = $y + 1.0 {
        $imc = $s * ($y - $h2) + $imcen;
        for $x = 0.0; $x <= $h1; $x = $x + 1.0 {
            $rec = $s * ($x - $w2) + $recen;
            $re = $rec;
            $im = $imc;
            $color = 1000;
            $re2 = $re * $re;
            $im2 = $im * $im;
            for (($re2+$im2) < 1000000.0) && ($color > 0) {
                  $im = $re * $im * 2.0 + $imc;
                  $re = $re2 - $im2 +$rec;
                  $re2 = $re * $re;
                  $im2 = $im * $im;
                  $color = $color - 1;
            }
            if $color == 0 {
                print "_";
            } else {
                print "#";
            }
        }
        println "";
    }
}

mandel();

$ time ./elodie exec mandel.elodie
real 0m1.250s
user 0m1.188s
sys  0m0.272s

Contributing

Please do!