Hacker News Reader

Comment by choeger | Hacker News Reader

First of all, I don't think you should program in CPS yourself but use proper language support if it's available. Otherwise just leave it at that. Code is read much more often than written. You also don't use Church-Encoding or De-Bruijn variables if you can avoid it.

Secondly, what's the point when you have to inline? If your function would return an optional and you inline it, you would get the same effect from any decent compiler.

View on HN

If your language has do-notation or something like it, then CPS can be quite readable.

With the syntax:

    cps {
      let! x = doThisThing
      let y = x * 2 + 3
      let! z = doOtherThing y
      return z + 1
    }

Without the syntax:

    doThisThing.Then(fun x -> 
      let y = x * 2 + 3
      doOtherThing(y).Then(fun z -> 
        z + 1
      )
    )

Proper language support? But it's CPS passing functions rather than returning values, no? So

  lookup(
   "key", table,
   result => { ... },
   error => { ... }
  )

  lookup(
   "key", table
  ).then(result => {
    ...
  })
  .then(next_result => {
    ...
  })
  .catch(error => {
    ...
  })

Or do you mean, one optimised for performance?

In "On Lisp," there's a chapter where pg explains how to write continuation-style passing macros without sacrificing readability. I used it to implement nondeterministic backtracking in python, and it worked. No coroutines, no language support, just macros and locally-captured continuations.

(I'm a bit too tired to figure out how this relates to your question, but I'm pretty certain it's related.)

Here's the whole chapter as an imgur album: https://imgur.com/a/ccv4Q9o

It's hard to see from that chapter alone why it's so powerful, but later chapters implement a variety of wonderful things with these abstractions: a process scheduler, language analysis, and other nondeterministic things.

It was neat playing with it on real algorithms in python, rather than being consigned to obscure-lisp-impelmentation hell: https://twitter.com/theshawwn/status/1373239490660069379

Basically, it's similar to your lookup.then.then.catch example, but the macros automate all of the code generation. It's also not quite the same thing as async-await, nor coroutines; there are some subtle, interesting differences.

Out of interest what did this end up looking like in python?

Glad you asked. Like this:

https://github.com/shawwn/pymen/blob/68b66dccc96910869ab370d...

  (=defun choose-bind-test ()
    (choose-bind x '(0 1 2 3 4 5 6 7 8 9)
      (write (str x))
      (if (= x 6) x (fail))))

If it's confusing why it looks like Lisp, it's because it's a self-hosted Lisp that runs entirely in Python. (Basically, there's no "runtime" -- it uses native python constructs, and all of the code compiles directly to real python.)

What does the python look like? Well:

https://github.com/shawwn/pymen/blob/12753ebb1251970f29eb04e...

  setenv("choose-bind-test", macro=__choose_bind_test__macro1)
  def L_61choose_bind_test(L_42cont42=None):
    def __f73(x=None):
      write(L_str(x))
      if x == 6:
        return x
      else:
        return L_61fail(L_42cont42)
    __L_42cont428 = __f73
    return L_61choose(__L_42cont428, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

As you can see, macros do an incredible amount of work under the hood. This code is reminiscent of the parent comment's try.then.then.catch example, yet the source code is wonderfully readable.

Thus, lisp's power.

If you want to play around with it:

  git clone https://github.com/shawwn/pymen
  cd pymen
  git checkout ml
  # optionally, brew install rlwrap
  rlwrap bin/pymen
  > (load "lib/onlisp.l")
  > (choose-bind-test)
  0123456

Note, I didn't invent this technique. This is courtesy of Scott Bell's Lumen lisp: https://github.com/sctb/lumen

I "merely" ported it to Python, and a few billion other things over the years.

The specific example listed in the tweet was made using this:

  (=defun path (node1 node2)
    (if (null? (neighbors node1))
        (fail)
        (in node2 (neighbors node1))
        (=values (list node2))
      (=bind (n) (choose (neighbors node1))
        (=bind (m) (path n node2)
          (=values `(,n ,@m))))))

  (defconst nodes*
    (obj a: '(b d)
         b: '(c)
         c: '(a)
         d: '(e)
         e: '()))

  (def neighbors (n)
    (get nodes* n))

Which you can run like this:

  > (print (str (path 'a 'e)))
  ("d" "e")
  > (print (str (fail)))
  ("b" "c" "a" "d" "e")
  > (print (str (fail)))
  ("b" "c" "a" "b" "c" "a" "d" "e")
  > (print (str (fail)))
  ("b" "c" "a" "b" "c" "a" "b" "c" "a" "d" "e")

The (print (str ...)) stuff is because otherwise it would pretty-print the actual python objects, which are dictionaries. It's a bit harder to read.

  > (fail)
  {0: 'b',
   1: 'c',
   2: 'a',
   3: 'b',
   4: 'c',
   5: 'a',
   6: 'b',
   7: 'c',
   8: 'a',
   9: 'b',
   10: 'c',
   11: 'a',
   12: 'd',
   13: 'e'}

As you can see, lists are represented as dicts, not cons cells.

So, to sum up, Lisp is so powerful that I was able to port pg's On Lisp examples with almost no modification whatsoever, directly into Python. These examples are almost verbatim from the book. (There are more in the github links above.)

Since this will be my last chance to demonstrate this for some time, I close with an example of the "ballet" from On Lisp, where multiple processes are collaborating together to reach some goal:

  (program ballet ()
    (fork (visitor 'door1) 1)
    (fork (host 'door1) 1)
    (fork (visitor 'door2) 1)
    (fork (host 'door2) 1))

expands into:

  setenv("ballet", macro=__ballet__macro1)
  def L_61ballet(L_42cont42=None):
    global L_42procs42
    L_42procs42 = None
    ____x179 = ["visitor", ["quote", "door1"]]
    def __f60(__id39=None):
      L_61visitor(L_42cont42, "door1")
      return pick_process()
    L_42procs42 = join([make_proc(state=__f60, pri=1)], L_42procs42)
    ____x183 = ["host", ["quote", "door1"]]
    def __f61(__id40=None):
      L_61host(L_42cont42, "door1")
      return pick_process()
    L_42procs42 = join([make_proc(state=__f61, pri=1)], L_42procs42)
    ____x187 = ["visitor", ["quote", "door2"]]
    def __f62(__id41=None):
      L_61visitor(L_42cont42, "door2")
      return pick_process()
    L_42procs42 = join([make_proc(state=__f62, pri=1)], L_42procs42)
    ____x191 = ["host", ["quote", "door2"]]
    def __f63(__id42=None):
      L_61host(L_42cont42, "door2")
      return pick_process()
    L_42procs42 = join([make_proc(state=__f63, pri=1)], L_42procs42)
    while True:
      L_print("looping")
      time.sleep(0.5)
      if not is63(pick_process()):
        break
    return catch(L_42halt42)

Notice the incredible amount of leverage you get from macros. Most programmers simply go ahead and write that kind of callback-hell-style code in other languages. Bugs become very difficult to spot. Here, you don't need to.

The whole book is available here: https://www.csee.umbc.edu/courses/331/resources/lisp/onLisp/

I am working the examples in the new book Software Design for Flexibility both in Scheme and Python. I agree with you that it is good to carry practices from Lisp languages to Python, when we must use Python.

Chicken Scheme implements R5RS Scheme using the continuation passing style underneath ("Cheney on the MTA"), so it is never strictly exposed to the programmer (no syntax changes), whilst giving them the performance improvements and making call/cc macros practically free.

That's what I would call first class language support.

I found one can program in that style in Python as well. I am not sure whether it is usually a good idea....

Reply on news.ycombinator.com