## Programming
## with Context
### using OCaml
Functional Thursday #111
----
- 請大家加入 slack g0v (https://join.g0v.tw)
- 然後找 `functional-thursday` channel 😉
----
### Who am I?
- **YunYan** (YY)
- ❤️ Functional
- prog., lang. and arch.
- Haskell and OCaml
- 💼 Blockhcain
- Protocol and Contract
- over 200k meaningful OCaml LoC
----
### what covered today
##### DISCLAIMER: solely based on personal experience
- abstraction in OCaml via `module`
- Programming with context
---
## Part I
~~abstraction in OCaml via `module`~~ \
OCaml 101
----
### 1.1 Basic OCaml syntax
----
```ocaml
(* simple function *)
let id = fun x -> x
let add_int m n = m + n
let add_opt opt m = match opt with
| None -> m | Some n -> m + n
let rec leng1 = fun x -> match x with
| [] -> 0
| _::xs -> 1 + leng1 xs
let rec leng2 = function
| [] -> 0
| _::xs -> 1 + leng2 xs
```
----
```ocaml
(* simple type *)
type t0 = C0
type 'a two = Two of 'a * 'a
let two x y = Two (x, y)
type ('a, 'b) meh
(* type alias *)
type my_int = int
let v = 10 (* : ? *)
```
----
```ocaml
(* variant types *)
type 'a non_empty_list =
| S of 'a
| C of 'a * 'a non_empty_list
(* recall: type ('a, 'b) meh *)
(* record type *)
type ppl = {
name : string;
age : int;
}
```
----
### 1.2 module in OCaml
----
```ocaml
(* simple module *)
module M0 = struct
type t0 = C0
type t1 = C0 | C1
let foo (C0 : t0) = (C0 : t1)
let bar = foo
end
```
----
```ocaml
(* simple module *)
(* namespace or scope *)
module M0 = struct
type t0 = C0
type t1 = C0 | C1
let foo (C0 : t0) = (C0 : t1)
let bar = foo
end
(* has type
sig
type t0 = C0 type t1 = C0 | C1
val foo : t0 -> t1 val bar : t0 -> t1
end
*)
```
----
```ocaml
(* simple module with explicit module type *)
module M0' : sig
type t0
type t1
val foo : t0 -> t1 -> t1
end = struct
type t0 = T0
type t1 = T1
let foo _ T1 = T1
end
```
----
```ocaml
(* what's the module type of M0''? *)
module M0'' : sig
type t0
type t1
val foo : t0 -> t1 -> t1
end = struct
type t0 = T0
type t1 = T1
let foo _ T1 = T1
let internal T0 = T1 (* /!\*)
end
```
----
```ocaml
(* reuse a module type? *)
module type M1T = sig
type t0
val bar : t0 -> t0
end
module M1 = struct
type t0 = T0a | T0b
let bar _ = T0b
let foo _ = T0a
end
module M1_has_M1T : M1T = M1
```
----
```ocaml
(* module type as the public interface *)
module M1 = struct
module type M1T = sig
type ta
type tb = int
val foo : ta -> tb
end
type ta = int
type tb = char
let internal_foo _ = 'x'
let foo n = if n <= 100 then 'y' else internal_foo n
end
```
----
```ocaml
(* module type as constrain; required by [Set] *)
module type OrderedType =
sig
type t
val compare: t -> t -> int (* 0 for eq *)
end
```
----
```ocaml
(* the converntion, [S], [T] and [t] *)
module M = struct
module type S = sig (* /!\ public *)
type t (* /!\ main data structure *)
type dropped = Y | N
val is_binary : t -> bool
val drop : t -> dropped
end
type t = int
type dropped = Y | N
let is_binary __ = true
let drop n = match n with 0 -> N | _ -> Y
end
```
----
### 1.3 first-class modules
```ocaml
(* we hope to have a module function look like this:
module M (N) = struct
(* things depend on N *)
end
*)
```
----
```ocaml
(* module function *)
module M (P : S) : T = struct ... end
```
----
```ocaml
(* module type as constrain on parameter*)
module Wrap (P : sig
type t
val to_string : t -> string
end) = struct
type t = P.t
let to_string x = "<" ^ (P.to_string x) ^ ">"
end
```
----
```ocaml
(* of course we would define that contrain somewhere else *)
module type C = sig
(* what we need *)
type t
val z : t
val prop : t -> bool
end
```
----
```ocaml
(* the convention, 2 [sig] and 1 [Make] *)
module M = struct
module type S = sig
type t
val zero : t
val check : t -> bool
end
module Make (P : C) : S = struct
(* impl. via a module function, [Make] *)
type t = T of P.t * int
let zero = T (P.z, 0)
let check (T (t, n)) = (P.prop t) && (n >= 0)
end
end
```
----
```ocaml
module Prop = struct
type t = int
let z = 0
let prop = fun n -> n <= 0
end
module G1 = M.Make (Prop)
let res = G1.check G1.zero
```
----
```ocaml
(* example using Stdlib *)
module Key = struct
type t = string list
let compare x y =
String.compare
(String.concat "" x)
(String.concat "" y)
end
module Ctx = Map.Make(Key) (* type? *)
let e0 = Ctx.empty
let e1 = Ctx.add ["x"; "y"] 1 e0
let e2 = Ctx.add ["v"] (Some 10) e0
```
----
#### out of scope! (escape if you can!)
- how to decide the `type t` in definition with the one in parameter?
- implicit
- explicit (manifest type)
- substitution (destructive)
----
#### a quick recap
- using **module** and **module type** to
- control namespace/scope
- define constrain/interface
- hide details
- conventionally, we have
- module type: `S` (or `T`)
- main type: `t`
- module generator: `Make`
- recommendation: [stdlib](https://github.com/ocaml/ocaml/tree/trunk/stdlib)
---
## Part II
Programming with context
----
### 2.1 What is Context?
----
#### Where we can spot Context often?
- `eval : Env -> Term -> Expr`
- `Γ ⊢ t : T`
- closure = lambda + environment
----
#### What is context?
- a mapping of variable (name) to value
- a list of pair of key and value
- sometimes, aka *Environment*
----
A context is the information needed for determining the outcome of a given computation
```ocaml
(* simple way *)
type ('k, 'v) ctx = ('k * 'v) list
(* using module Set *)
module Key = struct
type t = string list
let compare x y =
String.compare
(String.concat "" x)
(String.concat "" y)
end
module Ctx = Map.Make(Key)
```
----
```ocaml
(* using types *)
type key
type term
val compt : (key, term) ctx -> term -> term * (key, term) ctx
val compt : term Ctx.t -> term -> term * term Ctx.t
```
----
```ocaml
(* using modules *)
module Key = ...
module Term = ...
type ctx = Term.t Ctx.t
val compt : ctx -> Term.t -> Term.t * ctx
```
----
### 2.2 Context as the abstraction layer
----
a single point of access is helpful when we have many modules for data structures required for our computation
```ocaml
(* assuming there are many structres needed
and defined in separates files *)
module Vote_repr = struct ... end
module Proof_repr = struct ... end
module Context = struct
module Vote = Vote_repr
module Proof = struct
include Proof_repr
type sub_proof = ...
let trim (p : Proof._repr.t) : sub_proof = ...
end
(* and more global constants (or states) *)
end
```
----
```ocaml
(* how to use an abstraction layer *)
(* in the file where the "real" computation happens *)
open Context
let compt_whatever_needed =
let x = Vote.do_this in
let y = Proof.trim Proof.have_that in
...
```
----
2.3 Context as the state management
----
```ocaml
(* maintain a record for states and constants within a module *)
module Context = struct
type context = {
balance : Int32.t UidMap.t
step_cap : Int32.t
consumed_step : Int32.t
system_identity : string
path : string list
score : Int32.t
score_limit : Int32.t
}
type t = context
(* ... and more functions *)
end
```
----
Notice that
- the *key-value map* context is merely a special case of the *state management* one.
- it's actually just a *state monad* 🙃
----
- often, practically, we use both
- a internal *key-value context* with a tree-like-structured key
- a *record-based context* including the internal one as one field
- sometimes we call the internal one `storage`
- so, why two of them?
----
2.4 Context view
##### (not going to dive into the details)
----
for a *key-value context* with a tree-like-structured key..
- the *key-value map* is one way to **view** a context
- it sits in our *memory*, allowing us to access whenever necessary
----
- we can define other **view**s, like Tree or Binary, as we need
- to put a (sub-)context into a storage (disk, database)
- passing around through the internet
- a snapshot for cache or future repopulate
- a checksum or some sort of "proof"
---
### What we have today..
- *module* and *module type* (and module function) helps us to make our ocaml more well-structed
- A well-designed *context* module can help you manage your computation, states and even resources better
{"contributors":"[{\"id\":\"fbd2a9a4-ff78-4466-8356-17a33c030910\",\"add\":9485,\"del\":3165,\"latestUpdatedAt\":1763101640379}]","title":"Programming with Context, using OCaml","breaks":true,"description":"View the slide with \"Slide Mode\".","slideOptions":"{\"theme\":\"sky\",\"transition\":\"fade\"}"}