gocaml

GoCaml :camel:

[![Linux and macOS Build Status][]][Travis CI] [![Windows Build Status][]][Appveyor] [![Coverage Status][]][Codecov]

GoCaml is subset of OCaml in Go based on [MinCaml][] using [LLVM][]. GoCaml adds many features to original MinCaml. MinCaml is a minimal subset of OCaml for educational purpose. It is statically-typed and compiled into a binary.

This project aims incremental compiler development for my own programming language. Type inference, closure transform, mid-level IR are implemented.

• Japanese presentation (Go Conference Tokyo 2017 Spring)
• Japanese presentation (builderscon 2017)

Example:

…

ml e1; e2; e3; e4

In above program, expressions are evaluated in order of `e1 -> e2 -> e3 -> e4` and the sequenced
expression is evaluated to the value of `e4`.
Program must be evaluated to unit type, so the `e4` expression must be evaluated to `()` (unit value).

### Comments

There is a block comment syntax. It starts with `(*` and ends with `*)`. Any comment must be closed
with `*)`, otherwise it falls into syntax error.

```ml
(*
   This is comment.
*)

Constants

There are unit, integer, boolean, float and string constants.

(* integer *)
42;

(* float *)
3.0;
3.14e+10;
3.14e-10;
1.;

(* boolean *)
true;
false;

(* string *)
"hello, world";
"contains\tescapes\n";

(* only one constant which is typed to unit *)
()

Show values

print_* and println_* built-in functions are available to output values to stdout.

print_int 42;
println_bool true

Please see 'Built-in functions' section below for more detail.

Unary operators

You can use some unary prefixed operators.

-42;

(* GoCaml distinguishes float and int in operators. -. is a float version of - *)
-.3.14;

not true;

()

Arithmetic binary operators

As mentioned above, GoCaml distinguishes int and float in operators. Operators for float values are suffixed by . (dot).

(* integer calculation *)
1 + 2;
1 - 2;
1 * 2;
1 / 2;

(* float calculation *)
1.0 +. 2.0;
1.0 -. 2.0;
1.0 *. 2.0;
1.0 /. 2.0;

()

…

ml
42 = 42; (* => true *)
42 <> 42; (* => false *)

3.14 > 2.0;
1.0 = 2.0;
1.0 `, but cannot be compared with
`` and `>=`. Arrays (described below) cannot be compared directly with any compare
operators. You need to compare each element explicitly.

### Logical operators

`&&` and `||` are available for boolean values.

```ml
println_bool (true || false && false || false)

Variable

let expression binds some value to a variable.

(* 42 is bound to a *)
let a = 42 in
(* You can use the variable as value in any expression *)
a + 4;

()

The syntax is let {name} = {e1} in {e2}. e2 will be evaluated where e1 is bound to name. By chain let, you can define multiple variables.

let pi = 3.141592 in
let r = 2 in
let area = r *. r *. pi in
print_float area

And you can redefine the same name variable as already-defined ones.

let a = 42 in
println_int a;
let a = true in
println_bool a

The first a and the second a are different variable. Second one just shadows first one. So you can always redefine any variable names as any type. Shadowed variable can be no longer referred.

Functions are first-class object in GoCaml. So you can also bind functions to variable as value.

let rec hello _ = println_str "hello" in
let f = hello in

(* Shows "hello" *)
f ();

(* Binds external function *)
let p = println_str in

(* Shows "hi" *)
p "hi"

Functions

let rec is a keyword to define a function. Syntax is let rec name params... = e1 in e2 where function name is defined as e1 and then e2 will be evaluated. f a b c is an expression to apply function f with argument a, b and c. As long as the argument is simple, you don't need to use ().

Note that, if you use some complicated expression (for example, binary operators), you need to use () like f (a+b) c. If you specify f a + b c, it would be parsed as (f a) + (b c).

let rec f a b c = a + b + c in
let d = f 10 20 30 in

(* Output: 60 *)
println_int d

You can make a recursive function as below.

let rec fib x =
    if x  0.0 then x else -.x in
    let rec go z p =
        if abs (p -. z)  x + y in

(* Above is like below, but the function is anonymous *)
let rec add2 x y in x + y in

println_int (add 1 10);
println_int (add2 1 10);

It's useful when passing a function without considering its name.

let rec quick_sort xs pred =
    (* ...snip *)
in
let a = Array.make 10 0 in
let sorted = quick_sort a (fun l r -> l  x + y + z
in
...

Type Annotation

Type can be specified explicitly at any expression, parameter and return type of function with :

Types can be written in the same syntax as other ML languages.

• Primitive: int, float, bool, string
• Any type: _
• Tuple: t1 * t2 * ... * tn (e.g. int * bool)
• Function: a -> b -> ... -> r (e.g. if f takes int and bool and returns string, then f: int -> bool -> string)
• Array: t array (e.g. int array, int array array)
• Option: t option (e.g. int option (int -> bool) option)

Types can be specified in code as following. Compiler will look and check them in type inference.

…

Type Alias

type {name} = {type}; syntax declares type alias. It can be declared on toplevel. It means that all type aliases must be put before any expression.

type board = int array array;
type point = int * int;
let p: point = 1, 2 in
let b: board = Array.make 4 (Array.make 4 0) in
()

In above example, board is an alias of int array array. It can be used the same as int array array. Note that type does not make another type here. Just make an alias.

Tuples

N-elements tuple can be created with comma-separated expression e1, e2, ..., en. Element of tuple can be extracted with let expression.

(* (int, bool, string) is bound to t *)
let t = 1, true, "aaa" in

(* Destructuring tuple with `let` expression *)
let i, b, s = t in

let rec fst pair = let x, _ = pair in x in

(* Show '42' *)
println_int (fst (42, true))

Arrays

Array can be created with Array.make size elem where created array is allocated with size elements and all elements are initialized as elem. And array literal [| e1; e2; ... |] is also supported which allocates an array with specified (e1, e2...) elements.

arr.(idx) accesses to the element of array where arr is an array and idx is an integer. And `arr.(idx) println_int o | None -> println_str "none" in print None; print (Some 42)

First `|` can be omitted so you can write it in one line.

```ml
if match o with Some i -> true | None -> false then
  println_str "some!"
else
  println_str "none..."

Option values can be compared with = or <> directly.

let rec is_some x = x <> None in
let rec is_none x = (x = None) in

println_bool (is_some (Some 42));
println_bool (is_some None);
println_bool (is_none (Some 42));
println_bool (is_none None)

Currently match with expression is only for option type because GoCaml doesn't have variant types.

Ignored Symbol _

Variables named _ are ignored. It's useful if the variable is never used.

(* Ignored variable *)
let _ = 42 in

(* Ignored parameter *)
let rec first x _ _ = x in

(* Ignored element of tuple *)
let (_, second, _) = 1, "foo", true in

(* Error! Cannot refer ignored variable *)
print_int _

If a type of an ignored variable is never determined, compiler regards its type as () and compilation will pass.

let f _ = 42 in
println_int 42

In above program, the type of ignored variable _ will never be determined because function f is never used. In this case, compiler regards type of f as unit -> int and compilation will continue.

External Symbols

All external symbol must be declared with external syntax.

external name: type = "c_name";

The name is a symbol name of the external symbol. And the "c_name" is a symbol name linked in C level. The type cannot contain any generic type variable and _. For example, when you define gocaml_int foo(gocaml_int i) function in C, then you need to declare "foo" external C name with type int -> int to use it from GoCaml.

external foo: int -> int = "foo";
foo 42

Or when you define a global variable gocaml_int x in C, you need to declare external "x" C name to use the global variable value from GoCaml.

external x: int = "x";
println_int x

If C name does not exist in link phase, compiler will cause a linker error at compiling the source.

Like type syntax, all external declarations should be written before any expression.

Prerequisites

• Go 1.7+
• GNU make
• Clang or GCC (for building small runtime)
• cmake (for building LLVM)
• Git

Installation

Linux or macOS

For Linux or macOS, below commands build gocaml binary at root of the repository. [libgc][] is needed as dependency.

# On Debian-family Linux
$ sudo apt-get install libgc-dev

# On macOS
$ brew install go cmake bdw-gc coreutils

$ mkdir -p $GOPATH/src/github.com/rhysd && cd $GOPATH/src/github.com/rhysd
$ git clone https://github.com/rhysd/gocaml.git
$ cd gocaml

# Full-installation with building LLVM locally
$ make

…

console
$ sudo apt-get install libllvm5.0 llvm-5.0-dev
$ export LLVM_CONFIG=llvm-config-5.0

If you use macOS, use [Homebrew][]. GoCaml's installation script will automatically detect LLVM installed with Homebrew.

$ brew install llvm

Now you can build gocaml with USE_SYSTEM_LLVM flag.

$ USE_SYSTEM_LLVM=true make

Windows

Currently Windows is not well-supported. You need to clone LLVM repository to $GOPATH/src/llvm.org/ and build Go bindings of llvm-c following [the instruction][Go binding building instruction]. It needs cmake command and C++ toolchain.

It also needs to build [libgc][] static library and put it to library path.

After installing [goyacc][], generate a parser code with it.

$ goyacc -o parser/grammar.go parser/grammar.go.y

Finally you can build gocaml binary with go build.

Usage

gocaml command is available to compile sources. Please refer gocaml -help.

Usage: gocaml [flags] [file]

  Compiler for GoCaml.
  When file is given as argument, compiler will compile it. Otherwise, compiler
  attempt to read from STDIN as source code to compile.

Flags:
  -analyze
    	Analyze code and report errors if exist
  -asm
    	Emit assembler code to stdout
  -ast
    	Show AST for input
  -dump-env
    	Dump analyzed symbols and types information to stdout
  -g	Compile with debug information
  -help
    	Show this help
  -ldflags string
    	Flags passed to underlying linker
  -llvm
    	Emit LLVM IR to stdout
  -mir
    	Emit GoCaml Intermediate Language representation to stdout
  -obj
    	Compile to object file
  -opt int
    	Optimization level (0~3). 0: none, 1: less, 2: default, 3: aggressive (default -1)
  -show-targets
    	Show all available targets
  -target string
    	Target architecture triple
  -tokens
    	Show tokens for input

Compiled code will be linked to [small runtime][]. In runtime, some functions are defined to print values and it includes and. So you can use them from GoCaml codes.

gocaml uses clang for linking objects by default. If you want to use other linker, set $GOCAML_LINKER_CMD environment variable to your favorite linker command.

Program Arguments

You can access to program arguments via special global variable argv. argv is always defined before program starts.

print_str "argc: "; println_int (Array.length argv);
print_str "prog: "; println_str (argv.(0))

…

c
// gocaml.h is put in ru