OCaml Learning

It means Objective categorical abstract machine langauge. ML part in the name originates from the famous Meta Language which is created for making a proof assistant.

Ocaml is a statically-typed and type-safe programming language. Type errors are detected at compile time. Such guards against type errors means the language is type safe. This reduces the possibility of a buffer overflow error and related exploitation. (?)

Although OCaml is a statically typed language, it is not necessary to annotate each expression with its type. However, it's possible to do type annotation to put further restriction for debugging purposes. For example

(31 * 11 : int);;

341

Note, the () around the value is necessary.

A definition in OCaml is distinct from expression or values. It does not have a value, hence you cannot combine it with the other expressions to form more complicated things.

(let z = 10) + 22;;

Line 1, characters 11-12:
1 | (let z = 10) + 22;;;;
               ^
Error: Syntax error

You need an identifiers , which needs to start with lower case character and also an expression that can be evaluated to give the value to the identifier.

let x = 10 + 22;;

val x : int = 32

Note, you can also use let to define functions

let add x y = x + y;;

val add : int -> int -> int = <fun>

Note, you could load scripte you write within utop with directives like #use

#use "resources/mycode.ml";;
inc 3;;

- : int = 4

There's a recommended workflow in utop for development.

1. Edit code in file
2. Load code in utop and test it
3. Exit utop to have fresh code loaded next time you test it.

Unfortunately, the third step cannot be skipped. Reminds us how great Revise.jl was.

let a = "hello" in
let b = "world" in a^ b;;

- : string = "helloworld"

let x = 1 in
let x = 2 in
x;;

Line 1, characters 4-5:
1 | let x = 1 in
        ^
Warning 26 [unused-var]: unused variable x.
- : int = 2

The format was somewhat similar to that of C. Say you have a file hello.ml and you want to compile it, you could do

ocamlc -o hello.byte hello.ml

If you would like to automate these, you could use dune, OCaml's own build system like Makefile. You will need a dune file in your project's toplevel directory.

Your build will be in folder _build.

Some reference are

1. OCaml Expressions
2. OCaml Values

let x = 2;;
3.14 *. (float_of_int x);;

- : float = 6.28

let x = true;;
let y = false;;
x || y;;
x && y;;

- : bool = false

Explain the difference between <> vs != and = vs ==.

assert (1 = 2);;

Exception: Assert_failure ("//toplevel//", 1, 0).

if "batman" > "superman" then "joker!" else "Luther!"

- : string = "Luther!"

Note the returned expression needs to have the same type

if "batman" > "superman" then "joker!" else 1

Line 1, characters 44-45:
1 | if "batman" > "superman" then "joker!" else 1;;
                                                ^
Error: This expression has type int but an expression was expected of type
         string

Nesting of the if else if is possible

if "batman" > "joker" then "Earthling survives!"
else if "superman" > "Luther" then "Earthling survives"
else "We are doomed!"

- : string = "Earthling survives"

There are two ways to define a function in OCaml, they are syntactically different but semantically the same.

let inc = fun x -> x + 1;;
let inc x = x + 1;;
(* the later is syntactic sugar of the previous  *)

val inc : int -> int = <fun>

let rec fact n =
  if n = 0 then 1
    else n * fact (n-1);;
fact 10

- : int = 3628800

(** [even n] is whether [n] is even.
    Requires: [n >= 0]. *)
let rec even n =
  n = 0 || odd (n - 1)

(** [odd n] is whether [n] is odd.
    Requires: [n >= 0]. *)
and odd n =
  n <> 0 && even (n - 1);;

even 10;;

- : bool = true

(fun x -> x + 1) 2;;

- : int = 3

let square x = x * x;;
square @@ inc 5;;

- : int = 36

5 |> inc |> square;;

- : int = 36

In OCaml, you denote an type variable, a variable holding the type of a variable with ' and a name. I.e 'a.

let id x = x;;

val id : 'a -> 'a = <fun>

Notice, we could instantiate a specific type version of the polymorphic function by explicitly specifying the type information.

let first x y = x;;
let first_int : int -> 'b -> int = first;;
(* first_int 10 20;; *)
(* let bad_first : int -> 'b -> string = first;; *)

- : int = 10

Note, the bad_first doesn't work because the type are inconsistent.

It looks like keyword and optional arguments

let f ~name1:(arg1 : int) ~name2:(arg2 : int) = arg1 + arg2;;
let f ?name:(arg1=8) arg2 = arg1 + arg2;;

val f : ?name:int -> int -> int = <fun>

All multi-argument functions in OCaml are just partial application functions applied in chain.

let addx x = fun y -> x + y;;
addx 2 @@ 3 ;;

- : int = 5

You could define your own infix operators.

let (<^>) x y = max x y;;
10 <^> 20;;

- : int = 20

Recursive call eats up your stack memory. It achieves so by reusing the stack memory of the previous caller. But the programmer needs to rewrite the program such that the compiler knows nothing needs to be done in the caller anymore but return the returned value of next level function.

let rec count n =
  if n = 0 then 0 else 1 + count (n - 1);;

let rec count_aux n acc =
  if n = 0 then acc else count_aux (n - 1) (acc + 1);;

let count_tr n = count_aux n 0;;

(* this will explode your stack  *)
(* count 100000;; *)

(* the following will not *)
count_tr 10000000;;

- : int = 10000000

The usual None return value is denoted as () in OCaml, you will see it being displayed as unit which only has one value.

let () = print_endline "Camels" in
let () = print_endline "Horses" in
print_endline "Donkeys";;

Camels
Horses
Donkeys
- : unit = ()

Notice in the above statement, it's a hassel to have to write let _ in each time. We are not binding any value to an expression, so we could replace it with ; like below

print_endline "Camels";
print_endline "Horses";
print_endline "Donkeys"

Camels
Horses
Donkeys
- : unit = ()

Due to type safety requirements, if we truly want to output a unit type no matter the output type of our computation, we could use the ignore function.

ignore @@ 2 + 3;;

- : unit = ()

You could either employ printing or tracing for debugging. To enable tracing use directive #trace.

let rec fib x = if x <= 1 then 1 else fib (x - 1) + fib (x - 2);;
#trace fib;;
fib 3;;

fib <-- 3
fib <-- 1
fib --> 1
fib <-- 2
fib <-- 0
fib --> 1
fib <-- 1
fib --> 1
fib --> 2
fib --> 3
- : int = 3

Don't assume users know the range of arguments, give tests to make sure they input correct range of arguments.

(* possibility 1 *)
let random_int bound =
  assert (bound > 0 && bound < 1 lsl 30);
  (* proceed with the implementation of the function *)

(* possibility 2 *)
let random_int bound =
  if not (bound > 0 && bound < 1 lsl 30);
  then invalid_arg "bound";
  (* proceed with the implementation of the function *)

(* possibility 3 *)
let random_int bound =
  if not (bound > 0 && bound < 1 lsl 30)
  then failwith "bound";
  (* proceed with the implementation of the function *)

• Singly-linked
• Immutable

When an interpreter sees some code is being run over and over again, it can improve performance by compiling this piece of code to byte code to improve performance.

A compiler has two parts, a front end and a backend. The frontend is responsible for translating the source code into Abstract Syntax Tree and then into Intermediate Representation. The backend is then responsible for translating the IR into machine code. The interpreter on the other hand does not have backend. It executes AST or IR directly. (But how?)

The frontend of them follows three steps

1. Lexer: it parses the source code characters into word streams, known as tokens.
2. Parser: it constructs an Abstract Syntax Tree out of the word steam. These nodes are known as AST nodes.
3. Sematics analysis: it analyzes the sematics of the AST, checking for type errors etc.

You don't have to write your own parse and lexers as OCaml has those included.

{
open Parser
}

let white = [' ' '\t']+
let digit = ['0'-'9']
let int = '-'? digit+
let letter = ['a'-'z' 'A'-'Z']
let id = letter+

rule read =
  parse
  | white { read lexbuf }
  | "true" { TRUE }
  | "false" { FALSE }
  | "<=" { LEQ }
  | "*" { TIMES }
  | "+" { PLUS }
  | "(" { LPAREN }
  | ")" { RPAREN }
  | "let" { LET }
  | "=" { EQUALS }
  | "in" { IN }
  | "if" { IF }
  | "then" { THEN }
  | "else" { ELSE }
  | id { ID (Lexing.lexeme lexbuf) }
  | int { INT (int_of_string (Lexing.lexeme lexbuf)) }
  | eof { EOF }

%{
  open Ast
%}

%token <int> INT
%token <string> ID
%token TRUE
%token FALSE
%token LEQ
%token TIMES
%token PLUS
%token LPAREN
%token RPAREN
%token LET
%token EQUALS
%token IN
%token IF
%token THEN
%token ELSE
%token EOF

%nonassoc IN
%nonassoc ELSE
%left LEQ
%left PLUS
%left TIMES

%start <Ast.expr> prog
expr:
  | production  { action }
  | i = INT { Int i }
  | x = ID { Var x }
  | TRUE { Bool true }
  | FALSE { Bool false }
  | e1 = expr; LEQ; e2 = expr { Binop (Leq, e1, e2) }
  | e1 = expr; TIMES; e2 = expr { Binop (Mult, e1, e2) }
  | e1 = expr; PLUS; e2 = expr { Binop (Add, e1, e2) }
  | LET; x = ID; EQUALS; e1 = expr; IN; e2 = expr { Let (x, e1, e2) }
  | IF; e1 = expr; THEN; e2 = expr; ELSE; e3 = expr { If (e1, e2, e3) }
  | LPAREN; e=expr; RPAREN {e}
  ;
%%

meta-variable ::= expression | ... | expression

To format your code, you could use ocamlformat. It's a tool that formats your code. It's doable with dune build @fmt and then dune promote to accept the formatting.