Skip to content

Design tips

Write stubs!

When you are starting to write a function, write a "stub". This is an incomplete function. Just put in

  • the arguments

  • type annotations for arguments and the return type (This is very important! Don't skip this step!)

  • and failwith "TODO" for the body.

Then fill it in later.

Here's an example of a stub:

let halts_on_all_inputs (f : int -> int) : bool =
  failwith "TODO"

(This particular function might be a bit hard to write, though. 😄)

Writing stubs is a great way to get past "coder's block". Once the stub is written, you can compile it and make sure it type checks. If it's recursive, you can usually easily fill in the base cases. At that point, you're ready to work on the body of the function.

Use wishful thinking!

If a function seems too difficult/complex to write directly, ask yourself "what function do I need which would make it really easy to write this function?" Then assume that that function exists (i.e. write a stub for it), and write your main function using the assumed function. When that's done, go back and write the body of the assumed function.

This is one of the most useful programming tips. It's explored at some length in the CS 4 textbook Structure and Interpretation of Computer Programs (SICP).

Use the support library!

The support library (which is part of the CS 164 code base) contains a number of modules with useful functions and data structures. Often, this can save you a lot of time versus writing them yourself. Here, we will briefly discuss the modules, but we strongly encourage you to read the comments in the support/*.mli files to find out more. We will remind you in the assignments which functions and data structures are particularly useful for that assignment.

The support library contains these modules:

  • Functors

This module defines three module types: OrderedTypeS, SetS.S and MapS.S. They are extensions of the standard OCaml module types OrderedType, Set.S and Map.S. The extensions mostly have to do with functions that convert instances of the internal datatypes to and from S-expressions, as well as a few other utility functions. There are also new functors called SetS.Make and MapS.Make that create modules with the module types SetS.S and MapS.S respectively, given a module of module type OrderedTypeS.

In general, you should never be using a module of module type OrderedType, Set.S, or Map.S. Always use the extended versions (OrderedTypeS, SetS.S, or MapS.S). Usually, all you have to do is type the extra S at the end of the name.

  • Dgraph

This module contains a functor called Make which makes a module of type Dgraph.S, which implements a directed graph. The functor takes an ordered type module (module type OrderedTypeS) as its argument.

Note that this (like the other graph implementations in this library) is implemented in a purely functional way. This is not as efficient as an imperative graph could be, but it's more than sufficient for our needs and tends to be very well-behaved (as functional data structures usually are).

  • Multigraph

This is like Dgraph, but implements a directed multigraph.

  • PriorityQueue

This module contains a very simple (some might call it "brain dead") version of a priority queue module called PriorityQueue.Simple. One day we may provide a more efficient one, but this will do for now.

  • Ugraph

This is like Dgraph, but implements an undirected graph.

  • Utils

This contains lots of little utility functions that aren't found in the OCaml standard libraries. There are string and list functions, functions to generate unique variable names, functions to work with S-expressions, and so on. This is a module you will want to get familiar with.

You use the support library by opening it and then opening whatever modules you need from it:

open Support
open Functors
open Utils

If you only need one module, you can alternatively do this:

open Support.Utils

Or you can open Support and then use a qualified function e.g. Utils.last.

Avoid functions that raise unhelpful exceptions!

Avoid using functions that raise unhelpful and hard-to-track-down exceptions like Not_found. One example is the find function of the Map functor. You should prefer to use the find_opt variant, which returns an option type. Then handle the None case explicitly, usually by raising an exception with a specific error message.

Also, most uses of find_opt use this pattern:

match Map.find_opt key map with
  | None -> failwith "some error message"
  | Some v -> (* do something with `v` *)

We've provided a helper function called find_or_fail in the extended MapS implementation in the support library. The above code would become:

let v = Map.find_or_fail key map ~err_msg: "some error message" in
  (* do something with `v` *)

We recommend you use find_or_fail for this case, and only use find_opt when this isn't sufficient. You should never use plain find unless you are 100% certain that there is no way that the key won't be found.

Note

Somehow, the OCaml gods delight in showing you that something that "can't possibly happen" can indeed happen, so we recommend coding somewhat defensively.

We also provide a more general function called find_or, which can do arbitrary actions in the case of a lookup failure. It takes a labelled argument called f which is a function of type (unit -> 'a), where 'a is the value type. You can use this to return a default value, or to raise an arbitrary exception on lookup failure.

Be careful with catch-all match cases!

Many functions in your compilers will be large match expressions handling a lot of different constructors. In addition, new constructors for many types will be added with each new version of the compiler. Some functions will require that you handle (say) one case specially, and then all other cases can be handled in a generic manner. It's totally natural to write such functions with a match expression that looks like this:

match <thing to match> with
  | <special case> -> <special case code>
  | _ -> <generic code for all other cases>

In normal OCaml programming, this would be fine. For us, it's not optimal, because it's very easy to forget to handle new constructors when you add them in later compilers. If that happens, the new constructors will be handled by the generic code (the catch-all handler), which will probably be wrong and which may be hard to debug.

Instead of this, we recommend this style:

match <thing to match> with
  | <special case> -> <special case code>
  | <case 1>
  | <case 2>
  | <case 3>
  | ... ->
    <generic code for all other cases>

Each <case N> form is a constructor with a wildcard for the constructor arguments e.g. for a constructor Foo it would be Foo _ (assuming that Foo has arguments). This way, if you add another constructor in the next compiler, and you forget to handle that case, you will get a warning about a non-exhaustive pattern match, and you will be able to fix the problem right away!

You can also write this more concisely as:

match <thing to match> with
  | <special case> -> <special case code>
  | <case 1> | <case 2> | <case 3> | ... ->
    <generic code for all other cases>

This is a bit easier on the eyes.