Preface

在学习Abstract interpretation的过程中， continuation作为一种对栈的模拟被大量的使用。实际上在Racket之类的Scheme语言中， 这个也是非常常见和重要的编程工具，因为这类的语言往往没有命令式语言那么好的control flow控制，比如when啊 for 啊之类的东西。不过说实话，现在我也没有完全搞懂.....比如dynamic wind

0x00 什么是continuation

continuation是指程序剩下的还没有被解析，或者计算的部分。比如对于如下程序:

(+ 1 (+ 1 0))

在解析的过程中很明显，有一个中间步骤是对程序右侧的部分(+ 1 0)先进行计算， 这时候程序剩下的部分是(+ 1 ...)。此时这个剩下的就被称为continuation。在scheme中我们可以通过一些方式来获取程序的continuation.一个比较常见的方式就是使用call/cc。

(+ 1
   (call/cc
    (λ (k) (k 1))))
;; > 2

call/cc可以捕捉当前的continuation，用一个传入当前continuatio k的函数来表示。 在上述程序中，k的值就是(+ 1 ...)而当(k 1)被调用时，实际上就是吧计算完成的值回填到原来的continuation中。需要注意的是，一旦k被调用那么当前call/cc包裹的栈会被放弃，从结果上来说，就好像是程序指针jump回到了call/cc出现的位置.

(+ 1
   (call/cc
    (λ (k) (+ 1 (k 1)))))
;; > 2

0x01 call/ec

call/cc可以写出很多很诡异的代码，你甚至可以从吧call/cc作为参数去传递并在另一个call/cc中调用它, 最后在返回一个call/cc，我有一种感觉可以拿这个来实现一下回调或者Monad之类的，但是一时半会好像想不出来。

;; (let/cc k ....) is just a alias for (call/cc (λ (k) ...))
(let ([k (let/cc m
           (displayln "ping")
           m)])
  (let/cc esc
    (displayln "pong")
    (k esc)))

racket提供了一种性能比较好的替代品call/ec,全名叫call-with-esacpe-continuation，这个没法互相跳，把上面的code改成ec就会报错。
既然是escape很好理解彻底逃出当前的栈，这个其实非常类似于命令式编程中的return, 一个意思，也可以用在当我们需要从一个循环之类的东西（比如递归）中跳出的时候。或者是异常也是一个不错的应用场景。

(let/ec return
  (map (λ (x)
         (if (number? x)
             (return "a invalid number!")
             (+ 1 x)))
       '(1 2 a 1)))

0x02 prompt

之前对call/cc的讨论中还是有一些欠缺，比如，如果在call/cc block中k没有调用会怎么办？这时候其实还是会跳回call/cc的调用点，不过在这种情况下block中的栈其实已经执行完了也就 没有放不放弃的问题了

(+ 1
   (call/cc
    (λ (k) (+ 1 1))))
;; > 3

不过实际上racket还提供了一个功能可以更加细致的控制这个跳回，我们可以让它跳到某个栈上的提示符Prompt。看一个更加复杂的例子来说明这个问题

(define kont 'nothing)
(sqrt
 (call-with-continuation-prompt
  (λ ()
    (+ 1 2 3
       (call/cc
        (λ (k)
          (set! kont k)
          0))))))

在Racket中call-with-continuation-prompt, 缩写call/prompt,表示插入一个Prompt,Prompt相当于在栈上的某个位置打上了一个tag, 而在这段代码中, call/cc会捕获到达最经默认prompt 位置的continuation。 也就是说

> (kont 0)
6

需要注意的是，如果你直接在代码中放上这一句你是得不到任何结果的，因为一旦kont被调用所有当前调用kont的栈，也就是你程序最外面的栈会被放弃，也就意味着程序结束了，不过在REPL环境中，没有这个问题， REPL每一次sent数据给它，它本质都是放到一个线程里面去执行的所以你一旦调用kont甚至能得到两个6,一个是原来的，还有一个是call kont时候的。
Note: 这个例子来自stackoverflow上Alexis Kings上的回答，还是去看他的讲解2333，这个例子是真的很confuse,不过很好展示了undelimited continuation的特性

call/cc其实是可以通过参数来指定prompt的位置的,不过暂时好像还没有想到传递call/cc可以怎么用的很fancy

0x03 Delimited Continuation

call/cc有一个问题， 当传入函数中捕获的contiuation 被执行的时候会放弃当前的正在执行的栈退回到call/cc的调用点， 这因点在上面的例子中表现的已经是很明显了。 这种continuation 被称为Undelimited Continuation。 在很多的语言，比如python或者Javascript中我们可以通过yield/awaitt来实栈的跳出和再跳入。这一点使用undelimited continuation 就比较难实现了,因为我们比较难再回到之前执行到一半的堆栈中，通过那种互相传递，再互相call的call/cc调用可能是可以实现的，也是类似coroutine的方式，但是这个代码写起来想想都回很痛苦。好在还有一种delimite continuation可以实现这一点， 在Racket中这个也被称为composible continuation, 使用call/comp，稍微修改上面的例子我们就可以得到想要的结果。

(define tag2 (make-continuation-prompt-tag 'tag2))

(sqrt
   (call/prompt
    (λ ()
      (+ 1 2 3
         (call/comp
          (λ (k)
            (set! kont k)
            0)
          tag2)))
    tag2))

(kont 0)

这一次因为我们使用的call/comp， 我们当前程序的stack不会丢失。

0x04 some pearl about Monadic way in racket

之前Tom， Kris讨论的时候，提到了一段神奇的code，大概意思就是通过联合使用delimited和undelimited的可以做到动态的把一个全是prompt的函数栈全部给替换成某一个想要的计算过程，同时，在中间输出，就做到了类似把副作用在中间输出的感觉，使得一个函数变成纯函数

(define counttag (make-continuation-prompt-tag))
(define (setup-counter thnk)
  (let loop ([pthnk thnk]
             [count 0])
    (define val (call/prompt pthnk counttag))
    (if (continuation? val)
        (loop (lambda () (val count)) (+ count 1))
        val)))
(define (inc-count)
  (call/comp
   (lambda (ccc)
     (abort/cc counttag (lambda () ccc)))
   counttag))
(setup-counter
 (lambda ()
   (pretty-print (inc-count))
   (pretty-print (inc-count))
   (pretty-print (inc-count))
   (pretty-print (inc-count))
   'end
   ))

是不是很有monadic I/O的感觉23333333
这个例子中相当于传给(setup-counter)那个thnk函数在不停的被调用， 而inc-count是一个delimited continuation，如果用call/prompt,自然不断的运行到带prompt的位置，这个函数巧妙的地方在与，他在comp中使用了abort/cc，其实就是个call/cc，也就是说他每次跳完，并且触发完continuation,整个thnk 都会丢失一部分。

change of thnk

换句话说，这里的setup-counter就像是一个解析器(我口胡的)，每一个delimitet continuation 可以看作是一跳指令，你做的define call/comp实际上就是在定义一条指令，call/prompt其实就是在fetch指令，指令本身并没有计算，而set-counter则是完成了真正解析计算的过程。 这就得到了一个在函数式语言中写命令式dsl的效果。

好吧其实不是很像Monad，就是个continuation版本的do-block。

基于上面代码的想法，我还写了一些更加奇怪的玩具代码～～～试着用continuation来实现maybe monad的功能

当然我不会在racket中使用haskell那样的类型系统

#lang racket

(require racket/control)

;; monadic perform Maybe chain
(define do-tag (make-continuation-prompt-tag 'do))

;; a monad-like adt is a algebra contian
;; it's just Monad like because no real type class here
;; return :: a -> M a
;; bind :: M a -> (a -> M b) -> M b
;; fail :: String -> M a
(define (do-block thnk freturn fbind ffail)
  (let/ec return-do-main
    (letrec ([do-helper
              (λ (pthnk calculated)
                (define next (call/prompt pthnk do-tag))
                (match next
                  ;; continuation execute rest of stack
                  ;; >>
                  [(? continuation?)
                   (do-helper (λ () (next calculated))
                              calculated)]
                  ;; >>=
                  [`(bind ,(? continuation? next-c) ,v)
                   (do-helper (λ () (fbind v next-c))
                              v)]
                  [`(return ,(? continuation? next-c) ,v)
                   ;; things in (next-c lambda) is a side effect
                   ;; for example IO
                   (do-helper (λ () (next-c v))
                              (freturn v))]
                  ;; give up stack when fail
                  ['fail
                   (return-do-main (ffail calculated))]
                  ;; default value case, return it
                  [else calculated]
                  ))])
      (do-helper thnk 'empty))))

;; s :: string
(define (fail s)
  (call/comp
   (λ (ccc)
     (abort/cc do-tag (λ () 'fail)))
   do-tag))

;; v :: a
(define (return v)
  (call/comp
   (λ (ccc)
     (abort/cc do-tag (λ () `(return ,ccc ,v))))
   do-tag))

;; ⟵ can be witted by define
;; x :: a
;; m :: M a
(define-syntax-rule (⟵ x m)
    (define x (>>= m)))

;; bind is something  a repackage function, the data type in whole
;; monad may change, so many be a value/type guard needed
;; in do block each 'line' will cause a bind call
;; f :: a -> b
(define (>>= v)
  (call/c
   (λ (ccc)
     ;; abort/cc is used to replace function call with
     ;; wrapper continuation
     (abort/cc do-tag (λ () `(bind ,ccc ,v))))
   do-tag))

;; define maybe
(define (maybe? m)
  (match m
    ['Nothing #t]
    [`(Just ,x) #t]
    [else #f]))

;; def of maybe monad
(define (maybe-return v)
  `(Just ,v))

(define (maybe-fail v)
  'Nothing)

(define (maybe-bind m f)
  (match m
    ['Nothing 'Nothing]
    [`(Just ,x) (f x)]))

;; test
(do-block
 (λ ()
   (⟵ a '(Just 2))
   (>>= '(Just 1))
   (⟵ b '(Just 4))
   (>>= '(Just 2))
   ;; (>>= 'Nothing)
   (>>= `(Just ,(+ a b)))
   )
 maybe-return
 maybe-bind
 maybe-fail)

---

Ref

https://stackoverflow.com/questions/29838344/what-exactly-is-a-continuation-prompt
http://www.michaelburge.us/2018/03/07/continuations-in-racket.html