Modules and Functors

Work on this exercise locally

This web app is a reference guide — you can read instructions, browse starter code, and view tests here. To actually complete the exercise, you need to work in your local development environment.

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit the starter file in your editor (VS Code, Vim, etc.) — replace failwith "TODO" with your implementation.

3Run the tests: dune runtest modules/module0-warmup/exercises/modules-and-functors

6. Exercise 4: Modules and Functors (~25 min)

File: exercises/modules-and-functors/starter/main.ml Run:

dune exec modules/module0-warmup/exercises/modules-and-functors/starter/main.exe

What You'll Implement

This exercise builds the exact same lattice pattern used in Modules 3-4. The LATTICE module type + MakeEnv functor structure here is identical to lib/abstract_domains/.

module type LATTICE = sig         <-- Interface (Part 1, provided)
  type t
  val bottom : t
  val top    : t
  val join   : t -> t -> t
  val equal  : t -> t -> bool
  val to_string : t -> string
end

module BoolLattice : LATTICE      <-- Example implementation (Part 2, provided)
module ThreeValueLattice : LATTICE <-- Your implementation (Part 3)
module MakeEnv(L : LATTICE)       <-- Functor (Part 4)

Function	What It Does	Concept
`BoolPrint.to_string`	Converts bool to "T"/"F"	Simple module function
`ThreeValueLattice.join`	Computes least upper bound	Lattice operation
`ThreeValueLattice.equal`	Tests equality of lattice values	Structural equality
`ThreeValueLattice.to_string`	Converts lattice value to string	Pattern matching
`MakeEnv.lookup`	Looks up variable in env	Map.find_opt
`MakeEnv.update`	Adds binding to env	Map.add
`MakeEnv.join`	Joins two environments pointwise	Map.union

Hints

BoolLattice is provided as a complete example. Follow the same pattern for ThreeValueLattice.

The three-value lattice:

    Unknown (top)
     /      \
  Zero    Positive
     \      /
      Bot (bottom)

join Bot x = x, join x Bot = x, join x x = x, otherwise Unknown.

For MakeEnv.join, use M.union:

M.union (fun _key v1 v2 -> Some (L.join v1 v2)) env1 env2

Expected Output

=== Exercise 4: Modules and Functors ===

-- BoolLattice --
BoolPrint.to_string true = T
BoolPrint.to_string false = F
BoolLattice.join false true = true
BoolLattice.equal true true = true

-- ThreeValueLattice --
bottom = Bot
top = Unknown
join Bot Zero = Zero
join Zero Positive = Unknown
join Positive Positive = Positive
equal Zero Zero = true
equal Zero Positive = false

-- MakeEnv(ThreeValueLattice) --
empty = {}
lookup empty "x" = Bot
env1 = {x -> Zero, y -> Positive}
env2 = {x -> Positive, z -> Zero}
join env1 env2 = {x -> Unknown, y -> Positive, z -> Zero}

Done!

Starter Files

starter

starter/main.ml

Read-only

Loading editor...

Work on this exercise locally

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit the starter file in your editor (VS Code, Vim, etc.) — replace failwith "TODO" with your implementation.

3Run the tests: dune runtest modules/module0-warmup/exercises/modules-and-functors