Пишем на Lisp: продолжения

Перевод статьи Writing a Lisp: Continuations, автор Rein van der Woerd

На этой неделе я добавил продолжения в Lisp. Эта увлекательная функция и популярный запрос. До сих пор это была самая сложная функция, как для реализации, так и для объяснения, но игра стоила свеч.

Во-первых, что такое продолжение?

Продолжение - это особый вид функции, который похож на закладку на местоположение выражения. Продолжение позволяет вам вернуться к более ранней точке программы, тем самым обойдя поток управления обычной оценочной модели.

Продолжения можно использовать для реализации других механизмов управления, таких как исключения return, генераторы, сопрограммы и т. д.

В этом примере let/cc привязывается к текущему продолжению here. Оно оценивает блок let, которому присваивается продолжение cont. Последнее выражение возвращается как обычно, и оценка продолжается.

(define cont nil)

(+ 1 (+ 2 (+ 3 (+ (let/cc here
                    (set! cont here) 4) 
                  5)))) ; 15

Обычные функции

В моем lisp продолжения - это просто обычные функции, содержащие short-circuitформу. Эта прозрачность облегчает отладку, а реализация меньше.

(lambda (x) (<primitive> (+ 1 (+ 2 (+ 3 (+ x 5))))))

При вызове short-circuitнемедленно передает управление продолжению, пропуская окружающее выражение.

(* 10 (cont 10)) ; 21, not 210

Другой пример: оператор return. В этом случае управление немедленно переходит в верхнюю часть области функции, возвращая заданное значение.

(define (return-test)
  (let/cc return
    1 (return 2) 3))) 

(return-test) ; 2

Let в качестве макроса

Форма let - действительно просто синтаксический сахар. Он расширен в вызов call/cc, короткий для продолжения вызова с текущим.

(define-syntax (let/cc sym . body)
  '(call/cc ~(list* 'lambda '(~sym) body)))

Ранний выход с

Чтобы учесть возможность раннего выхода, я добавил EitherT в стек монады, где Left представляет собой ранний выход, и правый обычный порядок оценки.

newtype LispM a = LispM 
  { unLispM :: EitherT LispVal (StateT Callstack IO) a }
  deriving ( Monad
           , Functor
           , Applicative
           , MonadIO
           , MonadState Callstack)

shortCircuit - просто синоним left и throwError.

run :: LispM a -> IO (Either LispVal a)
run m =
  evalStateT (runEitherT (unLispM m)) []

shortCircuit - просто синоним для left и throwError.

shortCircuit :: LispVal -> LispM ()
shortCircuit = LispM . left

Захват контекста

call/cc и shortCircuit также являются особыми формами. call/cc предопределено в окружающей среде. Когда он вызывается, он захватывает окружающее вычисление, обертывает его внутри функции и передает его аргументу.

Когда вызывается продолжение, оно вызывает shortCircuit'его тело, и оценка продолжается оттуда.

impurePrimitiveMacros =
  wrapPrimitives True Impure
    [--
     ("call/cc", callCC)]

callCC env [l] = do
  lambda <- eval env l
  cont <- makeCont
  eval env $ List [lambda, cont]

  where makeCont = do
          contFnBody <- topFrame >>= walk replaceContForm
          return $ makeFn False Anonymous [Symbol "x"]
                     [List [shortCircuit', contFnBody]]
                     env

shortCircuit' = 
  wrapPrimitive False Impure sc
  where sc env [val] = do
          r <- eval env val
          shortCircuit r
          return r

В call/ccкачестве продолжения используется внешнее выражение, которое лексически содержит форму. Это позволяет избежать бесконечных циклов при использовании внутри именованных функций, где функция продолжения и именования будет постоянно вызывать друг друга.

topFrame =
  State.get
  <&> reverse
  <&> map extractCallframe
  <&> find containsCallCCForm
  <&> fromJust


extractCallframe (Callframe val) =
  val


containsCallCCForm val =
  case val of
    List [Symbol "call/cc", _] ->
      True
    List xs                    ->
      any containsCallCCForm xs
    _                          ->
      False

Наконец, сама call/cc форма заменяется параметром 'x'.

replaceContForm val =
  return $ case val of
    List [Symbol "call/cc", _] ->
      Symbol "x"
    _                          ->
      val

Оценка и обработка ошибок

После оценки кода результат разворачивается из монады LispM и печатается. Поскольку в данный момент как Left, так и Right должны содержать LispVal, они обрабатываются одинаково.

evalString :: Env -> String -> IO ()
evalString =
  runWithCatch action
  where action env string = do
          readtable <- getReadtable env
          let r = readOne readtable string >>= eval env
          liftIO $ run r >>= either printVal printVal


runWithCatch :: (Env -> String -> LispM ()) -> Env -> String -> IO ()
runWithCatch f env x = do
  let action = fromRight' <$> run (f env x)
  catch action (printError :: LispError -> IO ())

Дальнейшее чтение

  1. У Beautiful Racket есть отличная глава о продолжениях.
  2. Википедия также дает достойный обзор темы.