280: Monads

by Hernán Ibarra Mejia

Status

This SRFI is currently in draft status. Here is an explanation of each status that a SRFI can hold. To provide input on this SRFI, please send email to srfi-280@nospamsrfi.schemers.org. To subscribe to the list, follow these instructions. You can access previous messages via the mailing list archive.

Table of Contents

  1. Abstract
  2. Rationale
  3. Conventions
  4. Specification
    1. Monad Objects
    2. Haskell's do-notation
  5. Example
  6. Implementation
  7. Prior Art
  8. Acknowledgements
  9. References
    1. Literature on Monads in Scheme
    2. Implementations of Monads in Scheme
  10. Copyright

Abstract

Monads are a fundamental concept in functional programming. Schemers have been using them for a long time, albeit with ad hoc constructions only meant for specific monads. This SRFI deals with monads generally by extending Scheme with first-class monad objects and adding Haskell-like syntax for composing monadic computations. The API is minimal and the implementation trivial.

Issues

None at present.

Rationale

Do monads need introduction anymore? From a niche in category theory, they have become common knowledge among functional programmers. As there are already many good introductions to monads, ranging from short tutorials (see, for example, this list) to book-length treatments, we gloss over technical definitions and cut through why they deserve a place in Scheme.

Why monads? I have not needed them before.

Monads simplify common tasks in pure functional programming. Schemers tend not to be aware of monads because some monads are built into the language. If you have used continuations, lazy evaluation, or lists, you have been using monads.

Okay, but since we already have continuations, lazy evaluation, and lists, why do we need monads in Scheme?

Other monads not included in Scheme are just as useful, and many Schemers agree. We give substantial evidence in the Prior Art section.

Strangely, even though the same basic infrastructure for monads in Scheme has been reinvented many times, no SRFI has put it forward. Nieper-Wißkirchen’s SRFI 165 and SRFI 247 add specific monads to Scheme, as does Cowan and Corcoran-Mathe’s SRFI 189. But none attempt to deal with monads generally, like SRFI 280 does.

Can’t we just keep adding support for specific monads with SRFIs?

Useful monads shouldn’t have to be individually proposed as an SRFI. This leads to different APIs for the same underlying concept. We encourage portability by adding a minimal but general interface, which allows the programmer to define and use custom monads with ease.

Then why a general interface? Why not a pick-and-choose monad library that would supersede SRFI 165, SRFI 247, and SRFI 189?

The problem with a fully fledged monad library is that it is hard to know when to stop. Is it enough to add these n different monads? Do we support additive monads? What about comonads? Wouldn’t it be nice to have monad transformers? And so on. We leave open the possibility that a future SRFI will take on these challenges. Such a hypothetical SRFI would supersede those other SRFIs, but SRFI 280 does not.

Why not side effects instead? Isn’t that more idiomatic?

Schemers tend to avoid side effects whenever possible, but it is true that Scheme was designed with “escape hatches”, set! and friends, which allow for such effects when the burden of pure functional programming becomes too great.

Monads are the best of both worlds, since they provide a framework for imperative-style programming which is actually effect-free. For this reason alone they should be in every Schemer’s toolbelt.

We take no sides in the debate between pure and impure functional programmers, but we mention that side effects can significantly slow a Scheme program, depending on the Scheme implementation. This is the opposite of what usually happens in an imperative programming language like C, in which assignments are cheap but function calls are relatively expensive. The CHICKEN Scheme documentation on type declarations and flow-analysis:

Assignments make flow-analysis much harder and remove opportunities for optimization. Generally you should avoid using a lot of mutations of both local variables and data held in local variables.

Conventions

To avoid confusion, we use the following terms and notation.

Monad
A mathematical object whose definition can be found in an arbitrary category theory textbook. We use M to denote an arbitrary monad.
Type
A Scheme type, or just type for short, is as defined in R7RS section 3.2. We use the letters t and u to denote arbitrary types.
Monad instance
Each monad M defines a type M⁡t for each type t. As types are not first-class objects in Scheme, this association cannot be expressed portably in the language. Nevertheless, we informally mention this association whenever relevant. An instance of monad M, or just a monad instance when M is understood, is a Scheme object whose type is of the form M⁡t.
Monad object
A Scheme object returned by make-monad defined below.

In the prototypes below, the following naming conventions imply type restrictions (except for the informalities, of course, since these cannot be checked).

unit
A procedure. Informally, for a fixed monad M, it should take an object of type t and return a monad instance of type M⁡t.
bind
A procedure. Informally, for a fixed monad M, it should take as first argument an object of type M⁡t, and as second argument a procedure f and return a monad instance of type M⁡u. The procedure f should take as an argument an object of type t and return a monad instance of type M⁡u.
mnd
A monad object.
mndi
Any Scheme object. Informally, a monad instance.

Specification

Monad objects

(make-monad unit bind)

Returns a monad object by definition. A monad object is essentially a record with two read-only fields: the procedures unit and bind. To constitute a monad, these procedures are required to satisfy some requirements, known as the monad laws, see any category theory textbook. A SRFI-280-conformant implementation is not required to check the monad laws, leaving that responsibility to the user of the SRFI.

(monad? obj)

Returns #t if obj is a monad object and #f otherwise.

(monad-unit mnd)
(monad-bind mnd)

Returns the corresponding procedures that were given as arguments to make-monad to create mnd.

Haskell’s do-notation

This is the heart of SRFI 280. While composing monads with the bind and then operators works, it results in a lot of boilerplate and nesting, which is hard to read. Haskell gets around this by using do-blocks, inside of which syntactic sugar is activated that significantly improves readability. We provide similar sugar with the do/m syntax.

(do/m mnd ⟨action1⟩ ⟨action2⟩ …)

The definition of ⟨action⟩ requires two auxiliary pieces of syntax: define/m and return/m. 

⟨action⟩ -> (define/m ⟨variable⟩ mndi)
         -> (return/m obj)
         -> mndi

An SRFI-280-conformant implementation must report an error if a use of do/m does not syntactically conform to the grammar above, or if either of the following situations occur.

  • An application define/m ends the do/m actions.
  • An application of return/m does not end the do/m actions.

The do/m syntax can be interpreted as follows. 

; Base cases

(do/m mnd (define/m ⟨variable⟩ mndi)) -> *error*
(do/m mnd (return/m obj)) -> ((monad-unit mnd) obj)
(do/m mnd mndi) -> mndi

; Inductive cases

(do/m mnd (define/m ⟨variable⟩ mndi) ⟨action1⟩ ⟨action2⟩ …)
  -> ((monad-bind mnd)
        mndi
        (lambda (⟨variable⟩)
          (do/m mnd ⟨action1⟩ ⟨action2⟩ …)))

(do/m mnd (return/m obj) ⟨action1⟩ ⟨action2⟩ …)
  -> *error*

(do/m mnd mndi ⟨action1⟩ ⟨action2⟩ …)
  -> ((monad-bind mnd)
        mndi
        (lambda (_)
          (do/m mnd ⟨action1⟩ ⟨action2⟩ …)))

Care must be taken so that the last expansion is hygienic: the variable _ should not appear in the body of the lambda.

Example

Programming with monads takes practice and some study. This example is not meant to introduce monads, but to showcase their power when combined with the additions of SRFI 280.

In Monadic Programming in Scheme, Oleg Kiselyov comments on the following task (taken from a question in the comp.lang.functional mailing list): build a tree whose nodes are tagged with unique integers. Kiselyov points out that while an imperative solution is obvious (update a global counter while building each node), a purely functional solution appears to require passing the counter around function calls—extremely tedious.

He presents a better solution using monads; we adapt it to use the syntax of this SRFI. Identifiers which denote monad instances are prefixed by the dollar sign, and identifiers which denote procedures that return a monad instance are prefixed with an at sign. The identifier conventions are not mandated by SRFI 280. 

; Setup

(import (srfi 280))

(define (@unit x) (lambda (counter) (cons counter x)))
(define (@bind $ @)
  (lambda (counter)
    (let* ((wrapped ($ counter))
           (updated-counter (car wrapped))
           (new-val (cdr wrapped)))
      ((@ new-val) updated-counter))))

(define <numbered> (make-monad @unit @bind))

(define $inc (lambda (counter) (cons (+ 1 counter) counter)))
(define (run-<numbered> $ initial-counter) ($ initial-counter))

; Payoff

(define (@make-node val kids)
  (do/m <numbered>
    (define/m counter $inc)
    (return/m (cons (cons counter val) kids))))

; Note how the counter is invisible.
(define (@build-tree depth)
  (if (zero? depth)
    (@make-node depth '())
    (do/m <numbered>
      (define/m left-branch (@build-tree (- depth 1)))
      (define/m right-branch (@build-tree (- depth 1)))
      (@make-node depth (list left-branch right-branch)))))

(run-<numbered> (@build-tree 3) 100)

Below is the pretty-printed output.

(115
 (114 . 3)
 ((106 . 2)
  ((102 . 1) ((100 . 0)) ((101 . 0)))
  ((105 . 1) ((103 . 0)) ((104 . 0))))
 ((113 . 2)
  ((109 . 1) ((107 . 0)) ((108 . 0)))
  ((112 . 1) ((110 . 0)) ((111 . 0)))))

Implementation

The sample implementation is written in portable R7RS with no dependencies. A test suite is available, which requires SRFI 64.

Prior art

The ideas presented in this document are not original, quite the opposite. We have included a sample of existing literature and discussions in the References section. All of them seem to invent and reinvent the same small core which forms the basis of SRFI 280, but also give implementations of commonly used monads, which SRFI 280 eschews. The discussion Monads in Scheme? shows that the basic idea is as old as 2004. We also remark that even Daniel P. Friedman toyed with the idea in Monads à la mode.

Besides expository work and informal discussion, there exist a number of complete implementations. Some use unhygienic macros to achieve a different (more convenient?) syntax. We bring special attention to the monad egg, from which we took the idea of using the “/m” suffix for monad operations.

Acknowledgements

TODO

References

Literature on Monads in Scheme

Implementations of Monads in Scheme

Editor: Arthur A. Gleckler