palm_mute (![[info]](http://p-stat.livejournal.com/img/userinfo.gif){kind=small} palm_mute) wrote,@ 2007-11-21 20:29:00 |
|
| Entry tags: | continuations, delimcc, tutorial |
Монады и continuations (shift/reset part 1.5)
In America, you execute a program.
In Soviet Russia, a program executes you!
При реализации DSL часто нужна зависимость выражения от
контекста. Нам часто требуется, чтобы что-то происходило за
кулисами. Например, в комбинаторах парсеров состояние парсера —
текущий фрагмент входной строки — передается неявно, и это удобно.
В монаде State за кулисами протаскивается глобальное состояние.
В монаде List недетерминизм является также неявным, каждая строка
зависит от предыдущих.
Ключевой идеей для введения такой зависимости от контекста является
инверсия потока управления. Для этого у нас в распоряжении имеется 2
варианта.
Пишем в ивертированном стиле сами
При использовании библиотек комбинаторов программа собирается из
множества маленьких функций, соединяемых в одно целое при помощи
библиотечных комбинаторов. В типичном выражении вида f
`magicCombinator` g именно magicCombinator решает, когда и сколько раз
вызывать функции f и g (потому это и является примером инверсии
управления).
Примерами этого подхода являются монадный стиль, continuation-passing style,
ленивые потоки из SICP.
Используем continuations
Если выбранный язык программирования поддерживает delimited
continuations, нам не нужно разбивать сложное выражение на множество
маленьких функций, связанных комбинаторами. Мы можем прервать процесс
вычисления сложного выражения в любой момент, захватив текущий
контекст (стек вызовов, то что осталось вычислить), а затем вызвать
захваченный контекст как функцию:
(some..big..expression .. (capture_context ctx (magicCombinator ctx))
..)
Имея в распоряжении continuations, мы можем реализовать любую монаду.
Пример: монада State
;; magic happens here
(define (reflect ma)
(shift k (bind ma k)))
;; ordinary State monad operations, copied verbatim from Haskell's
(define (return x)
(lambda (s) (cons x s)))
(define (bind m f)
(lambda (s)
(let* ((as1 (m s))
(a (car as1))
(s1 (cdr as1)))
((f a) s1))))
(define (put x)
(reflect (lambda (_) (cons (void) x))))
(define (get)
(reflect (lambda (s) (cons s s))))
(define (run-state m s0)
((reset (return (m))) s0))
;; tests
(define (test0) 45)
(define (test1)
(let ((x (get)))
(begin
(put (+ x 5))
(put (+ (get) (get)))
0)))
(run-state test0 10) ;; prints (45 . 10)
(run-state test1 10) ;; prints (0 . 30)
Ссылки
Representing Monads by A. Filinski
То же на РСДН, с обсуждением
