Ocaml

tags : Functional Programming, Programming Languages

In the early ’80s, there was a schism in the ML community with the French on one side and the British and US on another. The French went on to develop CAML and later Objective CAML (OCaml) while the Brits and Americans developed Standard ML. The two dialects are quite similar. Microsoft introduced its own variant of OCaml called F# in 2005.

Intro §

• Objective Categorical Abstract Machine language
• ML: Meta Language

Mutability §

• OCaml is primarily an immutable language, like most functional languages.
• It does support imperative programming with mutable state, but we can probably not use it

Types §

• Infer (Type checker will already do this)
• Annotate (Additional constraint for the type checker)
  • Eg. (e:t) : Parentheses are required for type annotation

Building blocks §

Syntax gotchas §

• A design choice is made not to overload operators, eg. * and *. are different operators for ints and floats.
• If statements explicitly want boolean guards and branches need to be of same type
• use camelCase for identifiers
• In ocaml we say, we apply a function than call it.
• Equality
  • = and <> examine structural equality whereas (This is what we want to use)
  • == and != examine physical equality.
• begin..end are equivalent to ()

Functions §

• Functions are values and the body of the function is not evaluated unless applied.
• Functions can be used as arguments
• Functions can be returned as result

• Anonymous Function (Lambda expressions)

  • syntax: fun x1 ... xn -> e
  • $\lambda xe$
  • Eg. : fun x -> 42

• Named

  • let poop x = x+1;
  • let poop = fun x -> x+1;

• Recursive

  • let rec poop = poop;
  • Mutually recursive functions can be written using and. 3110 book has a funny odd even example in Chapter2.4

• No multi argument functions

  • It might seem we can pass multiple arguments to ocaml, but that’s not what actually happens
  • fun x y -> e is syntactic sugar for fun x -> (fun y -> e)
  • let add x y = x +y is syntactic sugar for let add = fun x -> fun y -> x +y

• Polymporphic Functions

  

  • Eg. let id x = x;;
  • 'a : alpha (A type variable)

Operators §

• Defining infix binary operators, we must wrap the operator in parens.
  • Eg. let ( <^> ) x y = max x y;;, while let <^> x y = max x y;; will give you errors. btw not using simply ^ because that’s the concat operator in ocaml.
• To define infix operators, you must surround them in parens

Semantic gotchas §

Others §

• Unit values: Eg. assert e evaluates to a unit value and nothing happens if e is true
  • For the Unit type, there’s only one value: ()
  • It’s usually using code that has side effects. Printing is an example of a side effect: it changes the world and can’t be undone.
  • Special syntax that can be used to chain together multiple functions that return unit.
    • The expression e1; e2 first evaluates e1, which should evaluate to (), then discards that value, and evaluates e2.
    • This can be used to chain multiple print statements together which usually evaluate to Unit.

Value and Expression §

Values §

Do not need any further evaluation

Expressions §

• Syntax rules
• Semantics
  • Type checking rules
  • Evaluation checking rules

• let expression

  • This give a notion of scope
  • Eg. let x = 2 in x (let expressions, we can use this inside other expressions)
  • Here we’re binding a value to x
  • Outside of this expression it’ll not be bound to x whereas in case of let definition, it’ll be bound to.

• nested let expression w same variable name

  • let x = 5 in (let x = 6 in x)
  • What this expression is evaluate to is the last x.
  • In ocaml, things are not mutable. So, x will not be redefined.
  • Order is left to right
    • let x = 5 in ... : Alright, x is assigned 5 for that scope
    • let x = 6 in x : A new x is assigned here, and evaluated to x
    • x is returned. we get 6.(from the innermost scope). i.e let x = 5 in 6
    • But we never used the older x. So the older x remain unused.
    • In other words, ocaml will not let us substitute the older value of x in the nested expression because it’ll violate Principle of Name Irrelevance
  • It’s usually good not to mix the same variable name like this. You cannot get to the top level from the inner most level anyway for that x.

Definitions §

let definition §

• These are like variable
• These are NOT expressions, it does not have a value itself. (let expression and let definition are different things)
• Eg. let x = 2 (let definition)
  • This implicitly means, let x = 2 in "rest of what i type"
  • When we do x=4;;x=7 etc. we’re not mutating x, we’re defining new x in a new scope. (So if you do this in ocaml toplevel/utop, you won’t be able to access previously defined x but in files and programs we’ll be do so accordingly)

Builtin Data Types §

Lists §

• can be nil or we cons
• These are recursive and parameterized(takes any type) list
• #show list
• Operations
  • Prepend
    • Constant time O(1)
    • 'a -> 'a list -> 'a list
    • []~
    • :: is used for construct objects in memory (cons)
    • :: is a binary constructor, takes 'a and 'a list
    • :: is an infix constructor(the only one)
    • 1st element is head, rest of the elements are tail
    • []~
  • Appending
    • Linear time O(n)
    • 'a list -> 'a list -> 'a list
    • [88] @ [77], this is not recommended in the hot path because lists are implemented as a singly linked list.
    • The @ is the append operator, not related to the apply operator

Records §

• with : Allows record copy. eg. {poop with name = "something else"}. Does not allow you to add new fields as that would change the type of the record.

Tuple §

type time = int * int * string
let t = (10, 10, "am")

• Order is relevant
• fst and snd let you access tuple which are pairs

Features §

Pattern Matching §

match e with
| 2 -> e0
| p1 -> e1
| p2 -> e2
| pi -> ei
| _ -> 1
 
(* - p1, p2, p3 are patern variables so will be bound to e1, e2, e3 *)
(* - _ will not be bound *)

• Can be used for matching with types, ints, strings, lists, records, tuples
• Pattern variables: Things that go after | after with
• What it allows
  • Match is the shape of the data
  • Extract/Transform parts of the data
• Typechecking
  • e and pi need to have same type
  • Whole match would have type of ei. All ei need to be of same type

Syntax Sugars §

• For pattern matching with the last argument, we can use the function keyword.

Pipeline operator §

Pipeline (Reverse Application operator)

• succ (square (square (succ 3)));;
• v/s 5 |> succ |> square |> square |> succ;;

Custom Types §

type primary = Red | Green | Blue
type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;; (* here, 'a is type param/variable, tree is the name of the type *)

Variants §

• See Type Systems
• Value that could be one of several possibilities
• Each value is called a constructor and is separated with | (the use of word constructor is diff. from languages like c++)
  • constructor name must begin with Uppercase
  • constructor is a value
  • contructor can carry along optional data with it using the of keyword
  • contructior aka tags
• Accessing variants can only happen via Pattern Matching
• constructor can be constants or non-constants(which carry some value using of)
• Variant Type

Options §

• list and option are type constructors. They construct other types but are not types themsleves.
  • eg. int list, a' list, int option and so on
• For options, we can use Some and None for option
  • I think Some and None are variant wala constructors
• Syntax& Semantics
  • None is a value of type 'a option
  • Some e is an expression of type t option if e : t. If e ==> v then Some e ==> Some v

Exceptions §

Exception vs Options §

• Exceptions make it easy to pipeline operations

Higher order functions §

• Higher-order functions either take other functions as input or return other functions as output (or both).
• What differentiates this from things like function pointers in C is the idea of not having to pass the exta param of values of the variable to be used in the program. This is taken care of by the concept of closure in functional languages.
• About fold

    fold_left (+) 0 [1; 2; 3] <=> (((0 + 1) + 2 + 3) // zero is on the left
    fold_right (+) [1; 2; 3] 0 <=> 1 + (2 + (3 + 0))) // zero is on the right

Modularity §

scope and open §

let x = ListStack.peek (ListStack.push 42 ListStack.empty)
let x' = ListStack.(peek(push 42 empty))
let x'' = ListStack.(empty |> push 42 |> peek)
let x''' = let open ListStack in empty |> push 42 |> peek
(* Following is discouraged cuz pollute global scope *)
open ListStack
let v = empty |> push 42 |> peek

Signatures §

• These is sort of how we would implement interface

• Here Mt is a sig
• This also provides encapsulation in the way that you can define functions which are not in the signature in the struct but if you try accessing those method from the module directly, you’ll get a typechecking error
• In signature matching, it checks if the Mod suffices the Sig. If the function in Mod can take more than what Sig allows it’s okay, but it must atleast satisfy Sig.
• Abstract Types
  • Usually denoted by t
  • Constraints can be added with things like module type IntRing = Ring with type t = int

    module type T = sig type t end
    module type U = T with type t = int

• We can seal a Sig to a module using: module <NewSealedModName> : <SigName> = <UnsealedMod that Implements Sig>
• We can use include to include signature (declarations) or structures (definitions)

Compilation Units §

• DM : Definitions and Modules
• DS : Declarations and Signatures

include vs open §

Functors §

• Module values are not like regular ocaml values. Most of the things like returning a module from a function etc will not work.
• But we have Functor, which is a module level function. Input is a module, Output is a module.
• Type annotation is mandatory when writing a functor

Mutability §

ref §

Environment §

Tooling §

• opam : package manager
• ocamlopt : native code compiler
• ocamlc : bytecode compiler (less used)
• toplevel/utop
  • When using #use exit and reload the toplevel if debugging, sometimes previous load overloads or something.
  • -: in utop means it’s an anonymous definition

Links and Resources §

Books §

• A Guided Tour - Real World OCaml
• OCaml from the Very Beginning
• http://courses.cms.caltech.edu/cs134/cs134b/book.pdf

Notes from 3110 §

TODO §

• Skipping TDD: https://cs3110.github.io/textbook/chapters/data/ounit.html#test-driven-development
• Don’t understand: 5.7.2. Constraints
• Skipped: 5.6.6. Sets and Maps implementation

Scratch notes §

• https://github.com/ocaml-multicore/parallel-programming-in-multicore-ocamL

utop # let pp = Fmt.Dump.list Fmt.int ;;
val pp : int list Fmt.t = <fun>
 
utop # Format.printf "%a" pp [1;2;3] ;;
[1; 2; 3]- : unit = ()

pp above should be usable with ounit2. The printer type (Fmt.t which is Format.formatter -> ‘a -> unit) is very standard in OCaml, based on the stdlib Format module.