Starting with a fragmentary understanding of ocaml I build an ocaml version of the division algebras. I keep the Scheme pattern where an algebra is a value bound to an identifier but in OCaml such values are called ‘modules’, are static and completed upon compilation. The mathematical ideas are in the Scheme development and not here. An algebra is roughly what an ocaml ‘module’ is for. Module names (as in “Xx” from “module Xx = struct end;;”) are in a special static space however. The Scheme version creates the new types dynamically whereas Ocaml can create them only at compile time but that is not a practical problem in the case at hand. I would like to see other applications of the Ocaml functor.
I try to do reals as reals from the division algebras.
(define reals (list (lambda (x) x) rr 0 zero? 1 + - * (lambda (x) (/ x))))where rr is a random real generating function.
module Reals = struct type kind = float let conj x : float = x let zero = 0. let one = 1. let zeroQ x = x = 0. let (+) = (+.) let (-) = (-.) let ( * ) = ( *.) let inv x = 1. /. x endThis definition yields the signature:
module Reals : sig type kind = float val zero : float val conj : float -> float val one : float val zeroQ : float -> bool val ( + ) : float -> float -> float val ( - ) : float -> float -> float val ( * ) : float -> float -> float val inv : float -> float endBut we want a signature that hides the fact that the values are floats; which isn’t so for higher algebras. If we hide that we will need a conversion to strings so we can see our computed results.
module Reals : sig type kind val conj : kind -> kind val zero : kind val one : kind val zeroQ : kind -> bool val (+) : kind -> kind -> kind val (-) : kind -> kind -> kind val ( * ) : kind -> kind -> kind val inv : kind -> kind val str : kind -> string end = struct type kind = float let zero = 0. let conj x = x let one = 1. let zeroQ x = x = 0. let (+) = (+.) let (-) = (-.) let ( * ) = ( *.) let inv x = 1. /. x let str = string_of_float endBehold:
Reals.str (Reals.(+) Reals.one Reals.one);; - : string = "2."Now we try to build a type from a type dynamically. We need to specify a shape that each of the division algebras will have in common. Maybe ocaml is good enough to infer this but for now we will give it explicitly. We need a module type for this shape which we will call “DivAlgebra”. All of the sample ocaml above code was provisional; together the following sample code runs.
module type DivAlgebra = sig type kind val conj : kind -> kind val zero : kind val one : kind val zeroQ : kind -> bool val (+) : kind -> kind -> kind val (-) : kind -> kind -> kind val ( * ) : kind -> kind -> kind val inv : kind -> kind val str : kind -> string end;;The Reals that we defined above are already trimmed down; we abstracted away the concrete properties such as the fact that they are built from floats. To minimize the eventual program source we undo that abstraction and define the BareReals as
module BareReals = struct type kind = float let conj x = x let zero = 0. let one = 1. let zeroQ x = x = 0. let (+) = (+.) let (-) = (-.) let ( * ) = ( *.) let inv x = 1. /. x let str = string_of_float end;;and instead build the Reals as merely
module Reals = (BareReals : DivAlgebra);;The only point of the above line of code is to verify that our module BareReals actually conforms to the module type DivAlgebra. Now we attempt the process of building the function, which Ocaml calls a ‘Functor’ that goes from a DivAlgebra to the next higher DivAlgebra.
module G = functor (Alg: DivAlgebra) -> struct type kind = {r: Alg.kind; i: Alg.kind} let conj x = {r = Alg.conj x.r; i = Alg.(-) Alg.zero x.i} let zero = {r = Alg.zero; i = Alg.zero} let one = {r = Alg.one; i = Alg.zero} let zeroQ x = Alg.zeroQ x.r & Alg.zeroQ x.i let (+) x y = {r = Alg.(+) x.r y.r; i = Alg.(+) x.i y.i} let (-) x y = {r = Alg.(-) x.r y.r; i = Alg.(-) x.i y.i} let ( * ) x y = {r = Alg.(-) (Alg.( * ) x.r y.r) (Alg.( * ) (Alg.conj x.i) y.i); i = Alg.(+) (Alg.( * ) x.r y.i) (Alg.( * ) x.i y.r)} let inv x = let d = Alg.inv (Alg.(+) (Alg.( * ) x.r (Alg.conj x.r)) (Alg.( * ) x.i (Alg.conj x.i))) in {r = Alg.( * ) d (Alg.conj x.r); i = Alg.(-) Alg.zero (Alg.( * ) d x.i)} let str x = Alg.str x.r ^ ", " ^ Alg.str x.i end;;Now the functor G should take an algebra and return the next algebra.
module Complex = G(Reals);;Thence:
Complex.str (Complex.(+) Complex.one Complex.one);; - : string = "2., 0."and
module Quaternion = G(G(Reals));;Thence:
Quaternion.str (Quaternion.(+) Quaternion.one Quaternion.one);; - : string = "2., 0., 0., 0."The definition of G can be abbreviated to
module G = functor (Alg: DivAlgebra) -> struct open Alg type kind = {r: Alg.kind; i: Alg.kind} let conj x = {r = conj x.r; i = (-) zero x.i} and zero = {r = zero; i = zero} and one = {r = one; i = zero} and zeroQ x = zeroQ x.r & zeroQ x.i and (+) x y = {r = x.r + y.r; i = x.i + y.i} and (-) x y = {r = x.r - y.r; i = x.i - y.i} and ( * ) x y = {r = x.r * y.r - (conj x.i) * y.i; i = x.r * y.i + x.i * y.r} and inv x = let d = inv (x.r * (conj x.r) + x.i * (conj x.i)) in {r = d * (conj x.r); i = zero - d * x.i} and str x = str x.r ^ ", " ^ str x.i end;;The text “open Alg” allows us to omit many instances of “Alg.”. Ocaml’s style of value definition is not recursive but that for types is. That is why the “Alg.”s are still necessary in the definition of kind.