Saturday, July 20, 2013

You could use a monad.


Scenario: A piece of data is determined in the first function `f1', but is only processed in a sub-sub-sub-… function `fx'.

One way is to use pass `the-data' as arguments from `f1' through `f2' all the way down to `fx':
(define f1 (the-data …)
  …
  (f2 the-data …)
  …)

(define f2 (the-data …)
  …
  (f3 the-data …)
  …)

…

(define fx (the-data …)
  … the-data …)
But in the above way, the body of `f2', `f3', `f4' and so on doesn't use `the-data'. It is only passed to the next function. And I still have to add the argument `the-data'.

Are there other ways to solve this problem?
You could use a monad.

The basic gist of it is that instead of manipulating the-data, we manipulate functions. So the inner functions f2, f3, ... will change from this:
(define (f2 the-data arg arg …)
      …
      (f3 the-data x y …))
to this:
(define (f2 arg arg …)
  (lambda (the-data)
      …
      ((f3 x y …) the-data)))
We just move the-data to the end of the argument list and curry the functions. That makes things more complicated at first, but the inner functions that don't actually use the-data can be eta-reduced. (lambda (x) (f x)) => f

So f2 eta-reduces to:
(define (f2 arg arg …)
      …
      (f3 x y …))
and all mentions of the-data disappear in the inner functions (pretty slick!) The innermost fx can't be reduced this way, of course, and the callers of f0 have to change to pass the initial value of the-data.

I just did this with an ad-hoc code transformation. A "monad" formalizes this. (and I skipped over a lot of detail.)

Matthias Felleisen elaborated further:
Here is what Joe is saying, with fake macros; the first two parts are real:
#lang racket

;; -----------------------------------------------------------------------------
;; an example using lexical scope

(define (f1-lexical-scope x)
  (define the-data (sin x))
  (define (f2 y)
    `(f2 ,(f3 y)))
  (define (f3 z)
    `(f3 ,(f4 z)))
  (define (f4 w)
    `(f4 ,the-data ,w))
  (f2 10))

(f1-lexical-scope pi)

;; -----------------------------------------------------------------------------
;; the same example with the 'monad' spelled out

(define (f1-monad x)
  (define the-data (sin x)) ;;
  ((f2 10) the-data))

(define ((f2 y) the-data)
  `(f2 ,((f3 y) the-data)))

(define ((f3 z) the-data)
  `(f3 ,((f4 z) the-data)))

(define ((f4 w) the-data)
  `(f4 ,the-data ,w))

(f1-monad pi)

;; -----------------------------------------------------------------------------
;; a sketch of how syntax would hide the monad where needed

;; the following macros are fake, because I don't have time to write them out:
;; see the HtDP language macros for #%app, which register functions too

;; defines the-data and initializes it
(define-syntax-rule (create-store x) (define the-data x))
;; registers f as a store-passer
(define-syntax-rule (define-store-passer (f x) e) (define ((f x) the-data) e))
;; this supplements #%app so that when a registered store-passer f is applied,
;; it picks up the-data in a curried application; other functions work normally
(define-syntax-rule (apply-store-passer f x ...) (old-apply (f x ...) the-data))
;; pick up the-data from secret stash
(define-syntax-rule (access-store) 42)

;; if you had these macros, the above would read like this:

(define (f1-monad.v2 x)
  (create-store (sin x)) ;;
  (f2 10))

(define-store-passer (f2.v2 y)
  `(f2 ,(f3 y)))

(define-store-passer (f3.v2 z)
  `(f3 ,(f4 z)))

(define (f4.v2 w)
  `(f4 ,(access-store) ,w))

(f1-monad.v2 pi)

2 comments:

Pascal Costanza said...

What's wrong with using special variables here?

Joe Marshall said...

Nothing at all. It was suggested earlier in the thread. I mentioned it in jest, but someone took it seriously and asked for details. So I wrote a two-paragraph sketch of the solution.

Matthias wrote out the whole solution (modulo the macros, but he sketched out how you can hide the monad with special syntax). I liked his explanation, but it wouldn't make sense without the prior post as context.