Paper and bruit › Jon's FoCS Experiments [focs-experiments]
- November 17, 2026
- Patrick Ferris
Towards the end of the week, I hopped on a call with Jon Ludlam to talk about some of his experiments in teaching the Foundations of Computer Science course at Cambridge.
Diagrams and steppers
- November 17, 2026
- Patrick Ferris
The conversation centred on a diagrammatic explanation of a rather infamous tcons function that updates a functional array (see chapter 4 of "ML for the Working Programmer" and Braun trees). I managed to unearth an explanation I used when teaching the opposite of this function pop in my supervisions.
Popping elements from a Braun tree.
The field of teaching functional programming is littered with steppers. Jon made reference to an OCaml stepper in his experiments:
Then, is there any debugging tool that is accessible to first-day programmers? In our view, the algebraic stepper of DrRacket, a pedagogical programming environment for the Racket language, serves as such a tool. ...the stepper tells us how the whole program looks like at each step, by rewriting the input program according to the reduction semantics of Racket.
The authors apply this to a "practical fragment of OCaml". Jon's experiments marry these kinds of steppers with a diagrammatic interpretation of the algorithm and data-structure; which I think is a good idea.
The right language for FoCS
- November 17, 2026
- Patrick Ferris
The choice of abstraction for diagramming matters a lot. On one hand, using an imperative, and perhaps closer to physical reality, interpretation of the data structures in diagrams is useful for explaining low-level details like memory layout and cache lines etc. On the other, using a functional, more abstract approach might make more sense when teaching functional programming with a mathematical hat on (and in particular, when such a course is teeing up something like Discrete Mathematics).
This reminded of the "Diagramming Program Values by Spatial Refinement" paper from this year's PLDI -- though that does not visualise algorithms. It might be nice to hack this into Introcaml or a runtime types library and get something rough and ready for OCaml.
When Jon and I discussed the trade-off in diagramming choices, our conversation turned to the Software Foundations books. I asked whether it might make sense to teach FoCS using Gallina, but Jon rightly pointed out that it could become quite limiting in real-world scenarios.
This mostly stemmed from a personal desire to see the foundational courses in first year blend together a bit more. I think students should be comfortable writing proofs with pen and paper, but, at the same time, I think teaching functional programming with one eye on proving theorems about your program might help make the whole thing make more sense. Teaching that a tree like:
type 'a tree = Leaf | Branch of 'a * 'a tree * 'a tree
is inductively defined and that may be a good way to prove things about your trees would be nice.
Using the browser
- November 17, 2026
- Patrick Ferris
We also both thought that having tools accessible in the browser was probably quite a good idea. In particular, having offline tools makes a lot of sense and reduces the burden on course maintainers to administrate servers running notebooks.
It also makes it easier to instrument the code behind the scenes. For example, Jon has plumbed the code into the OCaml compiler's tail-recursion checker to help teach students about making functions tail-recursive. During this conversation, I thought about instrumenting the code using bisect_ppx to help students see which code paths were exercised during a run of the code.
All of these are just ideas.