News for hackers. Stuff that matters.
Re:What’s in a Continuation (2016) by kazinator on Sunday July 02, 2017 @10:26AM (#14682613)
Continuation based list flattening in TXR Lisp:

  This is the TXR Lisp interactive listener of TXR 181.
  Quit with :quit or Ctrl-D on empty line. Ctrl-X ? for cheatsheet.
  1> (defun yflatten (obj)
       (labels ((flatten-rec (obj)
                  (cond
                    ((null obj))
                    ((atom obj) (yield-from yflatten obj))
                    (t (flatten-rec (car obj))
                       (flatten-rec (cdr obj))))))
         (flatten-rec obj)
         nil))
  yflatten
  2> (yflatten '(1 (2 3 (4) . 5) 6))
  #S(sys:yld-item val 1 cont #<intrinsic fun: 1 param>)
Oops, we need the obtain macro work with a function which yields:

  3> (obtain (yflatten '(1 (2 3 (4) . 5) 6)))
  #<interpreted fun: lambda (: resume-val)>
  4> [*3]
  1
  5> [*3]
  2
  6> [*3]
  3
  7> [*3]
  4
  8> [*3]
  5
  9> [*3]
  6
  10> [*3]
  nil
  11> [*3]
  nil
No continuation passing here: real stack where we can have unwind-protect.

Let's do it again --- but this time let's trace the function. For this we beak out flatten-rec into a top-level function we can trace.

  (defun flatten-rec (obj)
    (cond
      ((null obj))
      ((atom obj) (yield-from yflatten obj))
      (t (flatten-rec (car obj))
         (flatten-rec (cdr obj)))))
  
  (defun yflatten (obj)
    (flatten-rec obj)
    nil)
Now:

  1> (trace yflatten flatten-rec)
  nil
  2> (obtain (yflatten '(1 (2 3 (4) . 5) 6)))
  #<interpreted fun: lambda (: resume-val)>
  3> [*2]
  (yflatten ((1 (2 3 (4) . 5) 6))
    (flatten-rec ((1 (2 3 (4) . 5) 6))
      (flatten-rec (1)
    #S(sys:yld-item val 1 cont #<intrinsic fun: 1 param>))
  1
  4> [*2]
        nil)
      (flatten-rec (((2 3 (4) . 5) 6))
        (flatten-rec ((2 3 (4) . 5))
          (flatten-rec (2)
  2
  5> [*2]
            nil)
          (flatten-rec ((3 (4) . 5))
            (flatten-rec (3)
  3
  6> [*2]
              nil)
            (flatten-rec (((4) . 5))
              (flatten-rec ((4))
                (flatten-rec (4)
  4
  7> [*2]
                  nil)
                (flatten-rec (nil)
                  t)
                t)
              (flatten-rec (5)
  5
  8> [*2]
                nil)
              nil)
            nil)
          nil)
        (flatten-rec ((6))
          (flatten-rec (6)
  6
  9> [*2]
            nil)
          (flatten-rec (nil)
            t)
          t)
        t)
      t)
  nil
At this point, the flattening is done. What if we keep calling it?

  10> [*2]
            nil)
          (flatten-rec (nil)
            t)
          t)
        t)
      t)
  nil
  11> [*2]
            nil)
          (flatten-rec (nil)
            t)
          t)
        t)
      t)
  nil
It's just sputtering now, repeating the slice of execution spanning from several nestings deep into flatten-rec, up to the delimiting prompt, because no new continuation is captured.

There are no comments on this comment yet.