## Do as I say: “monadic do” notation in Snap!

January 13, 2020

Snap!
is one of the most widely-used programming languages whose primary editor is
entirely block-based. For a while, I was skeptical of its expressive
capabilities, but, after finally playing around with it myself, I realized that
it has support for some extremely expressive constructs that enable embedded
domain-specific languages. As part of
Sarah Chasins’
CS 294: Building User-Centered Programming Tools
class, I implemented a *monadic do* construct in Snap!, similar to
monadic do notation in Haskell
and
binding operators in OCaml.

I explain more about how this construct works in the rest of this post (along with an example), but if you want to mess around with it live (and see the definitions of every block I use), you can do so here!

### Implementation

To implement a *monadic do* construct, I had to implement four main features, each of which builds off the previous.

#### Feature 1: Basic Algebraic Data Type Support

I first introduced an “option” (i.e. nullable) type implemented under-the-hood as a singleton list:

I also implemented pattern matching for options and lists:

#### Feature 2: Functor and Monad Typeclasses

Next, I introduced blocks that allow for the definition of “anonymous” functor and monad instances:

These blocks can be used to create typeclass instances that can be assigned to a variable using a normal Snap! *set* block:

Under the hood, I represent typeclasses as a product of functions, akin to dictionary passing. I also provide “getter” blocks that simply return the correct function in a given typeclass dictionary:

Using these getters, I implemented some “typeclass functions” such as *bind* for arbitrary monads:

Unfortunately, these functions require explicitly passing in the monad as an argument. Which brings me to…

#### Feature 3: Monadic “Using” Notation

As the next step toward a nice *monadic do* construct, I introduced a block that allows its subexpressions to use a particular monad *implicitly*:

It works by setting the global variable `current monad`

to the supplied monad, running the block’s subexpression, and resetting `current monad`

to its previous value. For example, using this block, I implemented a *return* block that simply calls the *pure* function of `current monad`

with a given argument:

#### Feature 4: Monadic Let Bindings

Lastly, I introduced monadic let bindings akin to `x <- mx`

in Haskell and `let* x = mx in …`

in OCaml, which are sugar for the monadic bind operation:

These blocks only work in a *using* block because they rely on `current monad`

being set properly (so that they can access its *bind* function).

To implement this block, I used an *upvar*, a surprisingly versatile Snap! construct that, rather than *consuming* the value of a variable passed in by a user, instead *provides* a variable to the user. (As an aside, I’ve found upvars to be a fantastic use of interesting/atypical programming language theory tailored to a specific domain that really improves developer experience.)

Using an upvar turned out to be a bit tricky in this context because it meant that I had to rely on mutation to set this provided variable properly, which is not how typical *monadic do* implementations desugar. In particular, I treat the body of the monadic let binding as an uninterpreted expression and perform the following desugaring:

`let* x = mx in body`

↝ `mx >>= (fun output -> (x := output; body))`

Which, in Snap!, looks like this:

As a convenience, I also implemented *pure let bindings* to complement monadic let bindings:

### An Example

Using the list monad (which simulates a collection semantics for nondeterministic choice), I implemented a simple procedure that

- “Nondeterministically” chooses a variable
`x`

from the list`[4, 2, 3]`

, then - (Purely) sets
`y`

to twice the value of`x`

, then - “Nondeterministically” chooses
`z`

from the list`[1, 2, …, y]`

, and finally - Returns the triple
`(x, y, z)`

:

When run, this program returns all possible outputs of the procedure just described: