README.md

Three example Raven programs:

• malloc.rv, which is the memory allocator currently used in Raven's standard library and invoked by the compiler where needed.
  • It may well be the worst allocator ever written, but it gives an idea of what low-level pointer-programming looks like (bearing in mind this is not the language's design priority).
• complex.rv is also taken from the standard library and shows how you can define a new numeric type and various operations on it, using dispatch and pattern matching.
  • There's no Number type or any other abstract traits yet, interfaces are still informal, though tools for formal interfaces are planned.
• brainfuck.rv is the most complete and realistic program to date, showing parsing to a recursive AST and the core interpreter loop.
  • In future I expect programs to mostly look a bit more Python- or Clojure-like, centred around generic dictionaries and lists rather than custom types, but those data structures don't yet exist. This gives an unfinished but reasonably representative idea of how compiler-like code looks.
  • Don't expect good benchmark results yet. Although Raven has a high performance ceiling, I've focused on getting things like array operations working at all, with laughably naive implementations for some things.

To compile Raven code you need to run a Julia REPL in the Raven source code directory, then you can execute the compiled .js file using Node.js. (Raven compiles to wasm, but a little JavaScript is needed to load and invoke the .wasm file.)

➜  master git:(master) ✗ j --proj -q
julia> using Raven

julia> Raven.compile("brainfuck.rv")
"brainfuck.js"

julia> 
➜  master git:(master) ✗ node --experimental-wasm-stack-switching test.js hello.bf
Hello World!
➜  master git:(master) ✗ 

The first compile is pretty slow (~60s) due to Julia warmup; subsequent compiles in the same REPL session will be faster (~1s). (Though even that's much slower than I'd prefer.)

The above assumes you've saved brainfuck.rv to the same directory and also that you have a hello.bf brainfuck file to interpret. Here's a "hello world":

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

brainfuck.rv

bundle Instr {
  Left(), Right()
  Inc(), Dec()
  Read(), Write()
  Loop(body: List)
}

fn parse(code) {
  stack = []
  body = []
  for ch in code {
    # TODO cleaner dictionary lookup
    if ch == "<" {
      append(&body, Left())
    } else if ch == ">" {
      append(&body, Right())
    } else if ch == "+" {
      append(&body, Inc())
    } else if ch == "-" {
      append(&body, Dec())
    } else if ch == "," {
      append(&body, Read())
    } else if ch == "." {
      append(&body, Write())
    } else if ch == "[" {
      append(&stack, body)
      body = []
    } else if ch == "]" {
      loop = Loop(body)
      body = pop(&stack)
      append(&body, loop)
    }
  }
  return body
}

bundle Tape(data: List, i: Int64)

fn Tape() { Tape([0], 1) }

fn Tape(xs, i)[] { xs[i] }

fn left(&tape: Tape(xs, i)) {
  i = i - 1
  if i < 1 { abort("Tape error") }
  tape = Tape(xs, i)
}

fn right(&tape: Tape(xs, i)) {
  i = i + 1
  if i > length(xs) { append(&xs, 0) }
  tape = Tape(xs, i)
}

fn inc(&tape: Tape(xs, i)) {
  xs[i] = xs[i]+1
  tape = Tape(xs, i)
}

fn dec(&tape: Tape(xs, i)) {
  xs[i] = xs[i]-1
  tape = Tape(xs, i)
}

fn eval(&tape: Tape, instr: Instr) {
  match instr {
    let Left()  { left(&tape) }
    let Right() { right(&tape) }
    let Inc()   { inc(&tape) }
    let Dec()   { dec(&tape) }
    let Write() { print(js().String.fromCharCode(tape[])) }
    let Loop(body) {
      while tape[] != 0 {
        interpret(&tape, body)
      }
    }
  }
}

fn interpret(&tape: Tape, code) {
  for instr in code {
    eval(&tape, instr)
  }
  return tape
}

fn interpret(code) {
  interpret(Tape(), code)
}

{
  code = parse(readFile(args()[3]))
  interpret(code)
}

complex.rv

bundle Complex(re, im)

fn real(Complex(re, im)) { re }
fn imag(Complex(re, im)) { im }

fn one(Complex(re, im)) { Complex(one(re), one(im)) }

fn abs2(Complex(re, im)) {
  (re*re) + (im*im)
}

fn Complex(ra, ia) + Complex(rb, ib) {
  Complex(ra+rb, ia+ib)
}

fn Complex(ra, ia) - Complex(rb, ib) {
  Complex(ra-rb, ia-ib)
}

fn Complex(ra, ia) * Complex(rb, ib) {
  Complex((ra*rb) - (ia*ib), (ra*ib) + (rb*ia))
}

fn show(Complex(re, im)) {
  show(re)
  print(" + ")
  show(im)
  print("im")
}

malloc.rv

export {
  malloc!, free!, retain!, release!, blockSize, blockCount
  setBlockUsed!, headerSize, pageSize, allocationCount
}

# Current layout:
#
# l l l l u u u u m m m ....
# |       |       |
# |       used    |
# 32-bit size     user memory

# Internally we work with a pointer to the header, and consider block sizes
# to include the header. Pointers are shifted to point to user memory at the
# interface.
# (User) pointers are guaranteed to be 8-byte aligned, as long as all
# allocations are a multiple of 8 bytes.

pageSize = Int32(64*1024) # 64 KiB
headerSize = Int32(8)

fn getBlockSize(p: Ptr) { i32load(p) }
fn setBlockSize!(p: Ptr, sz: Int32) { i32store!(p, sz) }

fn getBlockUsed(p: Ptr) { i32load(p + Int32(4)) }
fn setBlockUsed!(p: Ptr, u: Int32) { i32store!(p + Int32(4), u) }

# Initialise first block
memoryGrow!(Int32(1))
setBlockSize!(Ptr(0), pageSize)

fn memorySize() {
  memoryPages() * pageSize
}

fn npages(bytes: Int32) {
  div(bytes + pageSize - Int32(1), pageSize)
}

# Block struct

bundle Block(ptr: Ptr, size: Int32)

fn getBlockSize(Block(_, size)) { size }

fn setBlockSize!(&bl: Block(ptr, _), size) {
  setBlockSize!(ptr, size)
  bl = Block(ptr, size)
}

fn getBlockUsed(Block(ptr, _)) { getBlockUsed(ptr) }
fn setBlockUsed!(Block(ptr, _), u: Int32) { setBlockUsed!(ptr, u) }

fn firstBlock() {
  Block(Ptr(0), getBlockSize(Ptr(0)))
}

fn next(&bl: Block(ptr, size)) {
  ptr = ptr + size
  bl = Block(ptr, getBlockSize(ptr))
}

fn isLastBlock(Block(ptr, size)) {
  addr(ptr + size) == memorySize()
}

fn publicPtr(Block(ptr, _)) {
  ptr + headerSize
}

# Main logic

# Combine a block with free neighbours to the right
fn coalesce(&bl: Block) {
  isLastBlock(bl) && return
  cl = next(bl)
  getBlockUsed(cl) && return
  coalesce(&cl)
  setBlockSize!(&bl, getBlockSize(bl) + getBlockSize(cl))
  return
}

# Find a free block of size >= n, creating it if necessary.
fn findFreeBlock(n: Int32) {
  bl = firstBlock()
  while not(isLastBlock(bl)) {
    if not(getBlockUsed(bl)) {
      coalesce(&bl)
      (getBlockSize(bl) >= n) && return bl
    }
    next(&bl)
  }
  if getBlockUsed(bl) {
    Block(ptr, size) = bl
    bl = Block(ptr+size, Int32(0))
  }
  size = getBlockSize(bl)
  if size < n {
    needed = n - size
    alloc = npages(needed)
    memoryGrow!(alloc)
    size = size + alloc*pageSize
    setBlockSize!(&bl, size)
  }
  return bl
}

fn trim(&bl: Block(ptr, size), newsize) {
  (size <= (newsize + headerSize)) && return
  setBlockSize!(&bl, newsize)
  newptr = ptr + newsize
  setBlockUsed!(newptr, false)
  setBlockSize!(newptr, size-newsize)
  return
}

# Public interface

fn malloc!(n: Int32) {
  n = n + headerSize
  bl = findFreeBlock(n)
  trim(&bl, n)
  setBlockUsed!(bl, true)
  return publicPtr(bl)
}

fn free!(p: Ptr) {
  p = p - headerSize
  setBlockUsed!(p, false)
  return
}

fn blockSize(p: Ptr) {
  getBlockSize(p - headerSize) - headerSize
}

fn blockCount(p: Ptr) {
  Int64(getBlockUsed(p - headerSize))
}

fn blockUnique(p: Ptr) {
  blockCount(p) == 1
}

fn retain!(p: Ptr) {
  p = p - headerSize
  n = getBlockUsed(p)
  if n == Int32(0) {
    abort("Memory management fault: retain")
  }
  setBlockUsed!(p, n+Int32(1))
  return
}

fn release!(p: Ptr, f: Int32) {
  p = p - headerSize
  n = getBlockUsed(p)
  if n == Int32(0) {
    abort("Memory management fault: release")
  } else if (n == Int32(1)) && (f != Int32(-1)) {
    invoke(Function(f, [TPtr], TNil), (p + headerSize) + 8)
  }
  # Setting to 0 equates to freeing
  setBlockUsed!(p, n-Int32(1))
}

fn release!(p: Ptr) { release!(p, widen(Int32(-1))) }

fn allocationCount() {
  i = 0
  bl = firstBlock()
  while true {
    getBlockUsed(bl) && (i = i + 1)
    isLastBlock(bl) && break
    next(&bl)
  }
  return i
}

fn checkAllocations() {
  if allocationCount() != 0 {
    println("Warning: retained memory")
  }
}