Papuascript

A Function-oriented Dialect of JavaScript

Pages

Customized function chaining

In imperative programming, sequences of operations are generally constructed by operating on a state of some kind, which is read from and updated at each step. In OOP, this state would take the form of an object, and the available operations on the state would be the object's public methods.

In functional programming sequences of operations take the form of function composition - that is, passing the output of one function to the input of the next. Function composition is the bread-and-butter of functional programming. 

/* This function composes two other functions.
   We name it "o" instead of "compose" to imitate mathematical
   notation, so the composition "g following f" is "g `o` f" */
o f g = \ ->
    g # f.apply undefined arguments

One downside of this style is the frequent need to perform some repetitive task each time a function in the sequence returns. Suppose, for example, that we wish to allow our functions to log messages. Since we are avoiding side-effects, a cumulative log message will have to be passed to each function and then returned again, possibly with additions.

zip list1 list2 =
    zipped = []
    for index i in list1
        zipped[i] = [list1[i], list2[i]]
    zipped

zipLog list1 list2 msg =
    [zipped, msg + 'zipped two lists']

/* ... other such pairs of functions ... */

bigOp input1 input2 input3 =
    msg = ''

    [listA, msg] = getListALog input1 input2 msg
    [listB, msg] = getListBLog input2 input3 msg
    [zipped, msg] = zipLog listA listB msg
    /* etc. */

This is obviously bad style. We should not be requiring or depending on the user to implement log-appending behavior for each and every function in this chain. Here is a better design, if more complicated than what we need in this case. The utility of the additional complexity will become clear when we look at further applications of it.

// We require that our chained functions return a Logger object
Logger x msg =
    this.x := x       // the "return" value
    this.msg := msg   // message to append to the log

/* Chaining function.
   'm' is a Logger
   'f' is a function from m.x to Logger */
Logger.into m f ->
    m2 = f m.x
    new Logger m2.x (m.msg + m2.msg)

// wraps a value in a Logger
Logger.result x = new Logger x ''

// returns all the data we want from the Logger
Logger.run m = [m.x, m.msg]

zipLog list1 list2 = new Logger (zip list1 list2) 'zipped two lists'

/* ... */

bigOp input1 input2 input3 =
    m1 = getListALog input1 input2
    m2 = getListBLog input2 input3
    zipped =
      listA <- m1.into
      listB <- m2.into
      zipLog listA listB

    /* ... */

Now the log-related logic is separated from the "normal" flow, running parallel to it instead of being interspersed. Notice that into does not know what value is being returned - the value is passed transparently to f, just as in normal function composition. Also notice that the chained functions do not know what the cumulative log message is, or how the chaining is implemented. The "return value" never depends on the log, or even on the fact that the function is part of a Logger chain.

For comparison, here is vanilla function composition implemented with the same pattern.

Identity x =
    this.x := x

Identity.into m f -> f m.x

// wraps a value in a Logger
Logger.result x = new Identity x

// returns all the data we want from the Logger
Logger.run m = m.x

If we have functions that do not need to do any logging, we can easily transform them into compatible functions.

loggerfy f = Logger.result `o` f

// Same as zipLog, but adds nothing to the log message
zipNoLog = loggerfy zip

We could do the same thing a different way, using a map-like function, which we call here fmap:

fmap m f = m.into (m.result `o` f)

This general pattern of customized function composition is reusable. It is usually discussed using the awful, abstruse term "monads." The pattern itself would, I guess, be called "monadic programming," and a specific kind of composition is called a "monad," singular. For example, Logger is what is traditionally called "the Writer monad." The word "monad" comes from math; I don't know what it actually means, and it doesn't matter what. Many an innocent programmer has wasted hours in the vain hope of figuring out just what the hell it means. Don't bother. It's customized function chaining, except in math, where it's something else.

The important features of a monad are:

Some Common Monads

There is a small set of monads that see repeated use. We'll look at a few here. First, we'll define some useful, reusable functions for monads. We use the "trait" model here: the Monad function adds the Monad trait to a constructor.

Monad = typeClass
      { result: undefined
      , into: undefined
      , run: undefined 
        /* "then" is for when you want the "effect" of m1 (the log
         * message, for instance), but not the "value"
         */
      , then: \type ->
          \m1 m2 -> type.into m1 \_ -> type.result m1 m2
      , fmap: \type ->
          \m f -> type.into m # type.result `o` f
      }

      { into: \m f   -> m.into f
      , run:  \m arg -> m.run arg
      , then: \m1 m2 -> m1.then m2
      , fmap: \m f   -> m.fmap f
      }

      { into: \f -> f this @
      , run:  \f -> f this @
      , then: \f -> f this @
      , fmap: \f -> f this @
      }

There are many other useful, generic functions on monads, but for now we'll keep it simple.

Notice that there is no Monad.result function. This is because there is no way to know which monad you want your data to be put into, so you have to specify.

List

The List Monad covers functions that may return multiple values, each of which serves as an input for the next function. This might be used in, for example, a game, where many moves are possible on each turn, and we want to compute all possible games.

List xs =
    this.xs := xs

Monad List
  { result: \x -> new List [x]
  , run: \m -> m.xs
  , into: \m f ->
      out = []
      for index i:v in m.xs
          out = out.concat (f v).xs

      new List out
  }

// Adds all possible rolls of one die to a running total
addDie total =
    newTotals = []
    for i = 1; i <= 6; i++
        newTotals.push (total + i)

    new List newTotals

// Show the sum of every possible roll of two dice
console.log # List.result 0 .into addDie .into addDie .run()

// Show every name made of these possibilities
firsts  = new List ['Fred', 'Mary', 'Stu']
middles = new List ['A.', 'Z.']
lasts   = new List ['Rogers', 'Lynn', 'Baker']

names =
    first  <- firsts.into
    middle <- middles.into
    last   <- lasts.into
    List.result (first + ' ' + middle + ' ' + last)

console.log names.run()

Error

Exceptions are a particularly hard-to-eliminate side effect. To manage them in a functional-friendly manner, we must continually surround calls with try blocks. As an alternative, we can replace error-throwing functions with error-returning ones, and use the Error monad to handle bubbling and catching. First, we define the Either class. An Either object is a container that either contains a valid value or an error message, and knows which kind it has. We use this class as the basis for our Error monad.

var left, right
(->
    Either a b isRight =
        this.a := a
        this.b := b
        this.isRight := isRight

    left a := new Either undefined a false
    right b := new Either undefined b true
  )()

Monad Either
    { result: right

    // if there's an error, skip the next function in the chain
    , into: \m f -> ?? m.isRight : f m.b : m
    , run: \m errHandler ->
        if m.isRight
            m.b
        else
            errHandler m.a
    }

// f must return an Either
// 'a.recover f .into b' allows b to still run, even if a raises an error
Either.recover m f = ?? m.isRight : m : f m.a
Either.prototype.recover = Either.recover this @

safelyReadFile path =
    try
        right # fs.readFileSync path
    catch ex
        left ex

safelyWriteFile path content =
    try
        right # fs.writeFileSync path content
    catch ex
        left ex

safeBackup path =
    safelyReadFile path .into \content ->
        safelyWriteFile (path + '.bak') content

State

(I find the State monad difficult to understand, so I'm going to explain it in a way that may seem pedantic. Sorry.)

We can use the monad pattern to emulate statefulness in a functional way. This may seem silly, since the whole point of function-oriented programming is to avoid using state. It may even seem impossible by definition. Be assured that the State Monad use pure functions throughout, you'll see that it does so in a way that enables better control and testing of state-based operations.

In the monads we've looked at so far, bound functions are called as soon as they are bound (i.e., as soon as we pass them to the into() function.) However, there is nothing about the monad pattern that requires us to do things this way. Until run() is called, the data inside the monad objects is invisible, so we can do things at any time. We make critical use of this fact in the State monad.

We are calling the monadic class Stateful here. A Stateful object is a wrapper around a state function - a function which takes the current state (an object) as input, and returns some value, together with the new state. This state will then get fed into the next state function in the chain. The tricky part is how these state functions get threaded together. I tried drawing a diagram, but found that to be even more confusing than just showing the code, so here it is:

// f :: state -> [a, state]
Stateful f =
  this.x := f

Monad Stateful
  {
    /* creates a state function that returns 'val'
     * and leaves the state unchanged
     */
    result: \val -> new Stateful \s -> [val, s]

  , into: \m f -> new Stateful \s ->
      // feed the current state into m
      [val, s2] = m.x s

      // feed the "value" of m into f, which returns a new Stateful object
      m2 = f val

      // feed the new state to the new Stateful object
      m2.x s2

    // run 'm' with 'state' as the initial state
  , run: \m state -> m.x state
  }

We now define our basic functions for getting and setting state variables.

// leaves the state unchanged, and passes the value for the given key
getVar k = new Stateful \s -> [s[k], s]

// creates a new state with the given key/value pair, and passes the value
setVar k v = new Stateful \s -> [v, set s k v]

Finally, here is an (admittedly contrived) example. Functions ending in 'M' return monad objects. Note that setInitials is itself a monad object, not a function, though in a sense it acts like one.

setNameM first last =
    setFirst = setVar :first_name first
    setLast  = setVar :last_name last
    setFirst.then setLast

setInitials =
    first <- getVar :first_name .into
    last  <- getVar :last_name .into
    setVar :initials (first[0] + last[0])

setAllM first last =
    setNameM first last .then setInitials

foobar = setAllM 'Foo' 'Bar'

[_, finalState] =  foobar.run {}
console.log finalState.initials // outputs "FB"

Using the State monad, we can make different pieces of state information available to different parts of our code, without having to expose it to the rest of the application, and without having to define "protected" members, or do any other such complicated things. And by keeping state information exclusively in an object, we make it easy - even trivial - to test that our state information is correct,

Monads behaving badly

It is possible to create pathological monads that don't act like function composition.

CountChain x count =
    this.x := x
    this.count := count

Monad CountChain
    { result: \x -> new CountChain x 0
    , into: \m f ->
        m2 = f m.x
        new CountChain m2.x (m.count + m2.count + 1)
    , run: \m -> [m.x, m.count]
    }

This code does something that, admittedly, no programmer would ever need to do: it counts the number of times into has been called in this chain. There's a problem, though: when chaining functions, chaining a function that does nothing should, well, do nothing.

upcase = \word ->
    CountChain.result word.toUpperCase()

chain1 = CountChain.result 'fwiw' .into upcase
chain2 = chain1.into Chaining.result   // chaining function that does nothing

chain1.run()   // == ['FWIW', 1]
chain2.run()   // == ['FWIW', 2]  uh oh!

CountChain fails to act like composition because is not a monad. We require monads to obey these "monad laws":

The first two laws say that chaining a function that does nothing should do nothing. The third law says it doesn't matter whether you nest your chained functions or not. It's the monadic version of (f `compose` g) `compose` h == f `compose` (g `compose` h)

Extra credit: The Continuation Monad

The Continuation monad is a brain-buster. It chains functions via continuation-passing style. One of its benefits is it doesn't actually call any of the actual continuation-passing functions until you call .run. For simplicity, we're ignoring errors for now.

Cont = \x ->
  this.x := x

Monad Cont
  { result: \val ->
      new Cont \g -> g val

  , into: \m f ->
      new Cont \g ->
        m.x \val ->
          (f val).x g

  , run: \m g ->
      m.x \val -> g val
  }

readFile file = new Cont \g ->
  (require 'fs').readFile file 'utf8' \err data ->
    g data

writeFile file content = new Cont \g ->
  (require 'fs').writeFile file content \err ->
    g()

// open the file, then open the file whose path you find in that file
redirectedRead file = readFile file .into readFile

concatFiles x y z = 
    contents_x <- readFile x .into
    contents_y <- readFile y .into
    writeFile z (contents_x + contents_y)

actions = concatFiles 'a.txt' 'b.txt' 'a_and_b.txt'
            .then redirectedRead '/path/to/file.txt'

actions.run \text -> console.log text

Continuation-passing style provides a way of dealing with the side effects of I/O. The strategy goes like this: all I/O functions are replaced (wrapped, actually) by ones that pass control to a user-provided callback when they finish. If we do things this way, and assuming we are otherwise side-effect-free, each callback is effectively like a new program, and the effects of the I/O are just the environment the "program" finds itself running in. The Cont monad can be used to make this continuation-passing style much more user-friendly.

Nesting functions indefinitely deep is a bad idea in most languages, including JavaScript. Fortunately, we can avoid this problem by using setTimeout, which runs the given function in a new call stack.

Monad Cont
  { result: \val ->
      new Cont \g -> setTimeout (-> g val)

  , into: \m f ->
      new Cont \g ->
        setTimeout \ -> m.x \val ->
          setTimeout \ -> (f val).x g

  , run: \m g ->
      m.x \val -> setTimeout (-> g val)
  }

Next time: Combining Monads

As I'll explain in the next update, monads can be combined either by using "monad transformers," or by just incorporating the functionality of both into a single mega-monad. The curious can take a look at nodam, which combines the Cont, State, and Error monads for doing I/O in node.js. Thanks for reading!

Project maintained by Rob Rosenbaum Theme by mattgraham, modified by Rob Rosenbaum