5 ms·

It’s a romantic idea but it’s simply not true. I have two examples. The first example is easy: Implement an O(1) jump table in Common Lisp that respects the le

It’s a romantic idea but it’s simply not true. I have two examples. The first example is easy: Implement an O(1) jump table in Common Lisp that respects the lexical environment. (You can’t, unless CASE is itself optimized to a jump table, which it usually isn’t.) The second example: Consider the SAME-FRINGE [0] problem. You’ll have a hard time macro-ing your way out of that unless your Lisp implementation has a built-in API for coroutines [1], or you write extraordinarily difficult macros to CPS-convert the entirety of Common Lisp to allow for CALL/CC. The latter is itself a hefty project to do well. This is not to say SAME-FRINGE can’t be solved in Lisp. It can. The page I linked has several solutions in Common Lisp. But idiomatic solutions are consy and inefficient. For instance, the usual SICP hack to write lazy sequences with thunks “works”, but doesn’t deeply integrate with the rest of Lisp so easily. And coroutine/CPS libraries in Lisp often have a bag of gotchas (e.g., they don’t work with high-order functions like MAPCAR). While I understand this is subjective, the most natural solution to this problem uses a control mechanism that just doesn’t exist in Common Lisp. [0] http://wiki.c2.com/?SameFringeProblem http://wiki.c2.com/?SameFringeProblem [1] Many Lisps used to, but it has fallen by the wayside since Lisps began to support native OS threads.

gumby 7y ago
> The first example is easy: Implement an O(1) jump table in Common Lisp that respects the lexical environment. (You can’t, unless CASE is itself optimized to a jump table, which it usually isn’t.) Perhaps I don't understand your objection: you can certainly store any object in an array and funcall it which would be O(1); the object could be a lambda that captured the lexical environment. I was doing that 35 years ago on the lisp machine Interestingly I did this also on the D-Machine Interlisp and each closure forked the stack, so it ground the machine to a halt, a design bug later fixed. Both examples I'm talking about predate Common Lisp standardization.
- ohyes 7y ago
  For the true jump table experience Tagbody / go would also work just fine for this. You can put the ‘go’s in lambdas in an array and funcall them. This sounds like fun.
  - reikonomusha 7y ago
    Not so. The table of lambdas have to be built at runtime, making it O(N). You can’t use LOAD-TIME-VALUE because that doesn’t respect the lexical environment, which TAGBODY tags live in.
    - ohyes 7y ago
      Well, you have to make the go statement in lexical scope in order for the tagbody to work... that seems reasonable enough to me. You specifically stated: > Implement an O(1) jump table in Common Lisp that respects the lexical environment. You don't know the lexical environment until there's a lexical environment to know, you can't have your cake and also eat it (or not have your cake and also know it). Interestingly, try/catch also solves this problem fairly elegantly without distastefully consing up a list or array at run-time. (defun jump2 (i) (let ((location nil)) (tagbody (catch 'a (catch 'b (catch 'c (catch 'd (setf location (elt #(a b c d) i)) (throw location nil)) (when location (print "D!") (go end))) (when location (print "C!") (go end))) (when location (print "B!") (go end))) (when location (print "A!") (go end)) end))) I'll leave the relevant macro to the reader, it shouldn't be that difficult... (I'm hoping I didn't just do someone's homework). edit: removed some cruft from experiments and fixed formatting
      - dan-robertson 7y ago
        Well here you can replace the tagbody with a block and replace the (go end) with an appropriate (return) instead do you can get results out of your jump table. But that’s beside the point because in practice this is probably O(n) not O(1). I think most CL compilers are going to need to push things to the control stack for each catch. Even if the compiler is clever enough to eliminate the catches, it still mightn’t implement the computation of which catch catches as O(n). So even in the best case of a very smart compiler, your code is basically equivalent to: (case i (0 (print "A!")) (1 ...)) Which isn’t guaranteed to be O(1). The point the GP is making is that the only solution which looks like it might O(1) (and indeed is O(1) if there is no (or just one) lexical scope to capture) is the array-of-lambdas-doing-go, but that this isn’t guaranteed by the language to be O(1) when the lexical scope changes each time because in a naive evaluation, the array of lambdas must be consed before jumping and this is O(n). The reason that it is reasonable to complain about this is that what one needs for a jump table is weaker than this. The lambdas do capture the lexical scope but they only have dynamic extent and don’t extend the scope at all so a lambda of the form (lambda () (go foo)) only has to be consed each time you hit the jump table because you can only reference foo once you are inside the tagbody. However the code to actually jump is likely to be static for most compilers. For guaranteed O(1) performance (which doesn’t rely on the cleverness of the compiler) you’d need to introduce a new special form, e.g. (jump n tag1 tag2 ... tagn) which evaluates n and jumps to the nth tag in its arguments in O(1) time.
- reikonomusha 7y ago
  The lambdas, a set of lexical closures, have to built at runtime, in order to capture the environment, and then stored in the array. That’s an O(N) operation.
  - ScottBurson 7y ago
    No, it's O(1). Time complexity is about how the execution time grows with the size of the input, not the size of the program. In this case, each of those lambdas is a piece of the program text; the size of the jump table is therefore a constant for any particular program. The time complexity here is the time taken for one jump through the table as a function of the number of jumps, and clearly that's a constant also. In fact, it would still be a constant if the 'case' were implemented as a chain of 'if's. Time complexity, since it concerns asymptotic growth of runtime as a function of input size, is not the correct notion to invoke here. You're just interested in performance in the ordinary sense: you want your program to run as fast as reasonably possible, and you know that a chain of 'if's leaves something to be desired in that regard. Fair enough. But let's look at the array-of-closures implementation again. Assuming that the number of jumps made through one of these tables, once you've created it, is much larger than the number of times you have to create a table, it's a perfectly workable implementation. I think your second point is more substantive. I too have come to the conclusion that coroutines were an unfortunate omission from the CL spec.
    - gumby 7y ago
      > I too have come to the conclusion that coroutines were an unfortunate omission from the CL spec. There was no consensus on multiprocessing at the time of standardization and language support was very uncommon. But still it’s weird: coroutines were over 20 years old by then, and newer ideas like the condition system and CLOS were included. And while nowadays the CL runtime is considered small, at the time it was criticized for being too large.
      - ScottBurson 7y ago
        Coroutines are not quite threads, but then, they don't require a scheduler. They're also not quite firstclass continuations, but then, they're simpler to implement, simpler to use, and don't have the same implications for the rest of the language and implementation design. Still, they can do some of the things you might otherwise use threads or firstclass continuations for; and as reikonomusha points out, those things can be quite difficult to do otherwise in a clean way. I'm sure some of the implementors (though not Symbolics, of course) would have been unenthusiastic about their inclusion, but still I wish it had been done.
omaranto 7y ago
I think that simulating coroutines by explicitly building the call stack they would have had isn't too ugly. This solution only conses to build those call stacks: (defun leaves (tree) "Return a function that returns the leaves of TREE one by one when called repeatedly." (let ((work (list tree))) (flet ((schedule (x) (when x (push x work)))) (lambda () (loop for task = (pop work) until (atom task) do (schedule (cdr task)) (schedule (car task)) finally (return task)))))) (defun same-fringe-p (t1 t2) (loop with l1 = (leaves t1) and l2 = (leaves t2) for x1 = (funcall l1) and x2 = (funcall l2) while (or x1 x2) always (eql x1 x2)))
dreamcompiler 7y ago
I have a coroutine implementation that GB and I wrote for CCL. It runs on top of native threads and is rather kludgy. It's not nearly as elegant as an implementation using stack-groups. Now I prefer to solve problems like same-fringe with general composable streams (like SICP lazy sequences but using CLOS rather than closures).
aidenn0 7y ago
Yes, the missing feature of something of equivalent power to call/cc is my biggest missing feature of CL. I've considered implementing green threads for SBCL as that's fairly straightforward to implement at the runtime level. There is a working delimited continuation library, but it's not exactly trivial.
aidenn0 7y ago
Won't tagbody/go with an array of symbols work for jump tables (assuming GO is O(1)?): (tagbody (go (aref #(a b c d) N)) a ... b ... c ... d))
- ScottBurson 7y ago
  Alas, no; 'go' is a special form — its argument is unevaluated.
  - aidenn0 7y ago
    Indeed it appears so. Strangely enough, the hyperspec doesn't specify that it's not evaluated.
    - dan-robertson 7y ago
      For special forms I think it’s implied that the arguments aren’t evaluated (as they are special) unless stated otherwise.
      - aidenn0 7y ago
        At least some forms say explicitly evaluated or not.
pfdietz 7y ago
You could do the jump tables if your CL gives you some access to the lexenv at compile time. What you do is modify the individual cases so that instead of accessing the surrounding runtime lexenv directly, they go through reader and writer thunks. These thunks are then passed in as a separate argument to the lambda for each case. The table mapping case values to these lambdas is a compile time constant. You might complain that this takes time proportional to the number of accessed objects in the lexenv, to set up the thunks. And that's true, but it's constant in the number of cases.
kazinator 7y ago
> (You can’t, unless CASE is itself optimized to a jump table, which it usually isn’t.) That's surprising. Even the brain-dead compiler in my TXR Lisp (a dialect that has some things in common with Common Lisp) does it. 1> (disassemble (compile-toplevel '(caseql x (1 'a) (2 'b) (3 'c) ((4 5 6) 'd) (7 'e) (8 'f) (9 'g)))) ** warning: (expr-1:3) unbound variable x data: 0: #:nohit 1: a 2: b 3: c 4: d 5: e 6: f 7: g syms: 0: x 1: integerp 2: <= 3: sys:b- code: 0: 04020002 frame 2 2 1: A0800000 getlx v00000 0 2: 30810400 movsr v00001 d000 3: 24010003 gcall t003 1 v00000 4: 08000001 5: 48000026 if t003 38 6: 00000003 7: 38050004 movrsi t004 1 8: 38250005 movrsi t005 9 9: 24030003 gcall t003 2 t004 v00000 t005 10: 00040002 11: 00050800 12: 48000026 if t003 38 13: 00000003 14: 38050005 movrsi t005 1 15: 24020004 gcall t004 3 v00000 t005 16: 08000003 17: 00000005 18: 54090004 swtch t004 24 26 28 30 30 30 32 34 36 19: 001A0018 20: 001E001C 21: 001E001E 22: 00220020 23: 00000024 24: 30810401 movsr v00001 d001 25: 44000025 jmp 37 26: 30810402 movsr v00001 d002 27: 44000025 jmp 37 28: 30810403 movsr v00001 d003 29: 44000025 jmp 37 30: 30810404 movsr v00001 d004 31: 44000025 jmp 37 32: 30810405 movsr v00001 d005 33: 44000025 jmp 37 34: 30810406 movsr v00001 d006 35: 44000025 jmp 37 36: 30810407 movsr v00001 d007 37: 30030801 movsr t003 v00001 38: 4C00002A ifq v00001 d000 42 39: 08010400 40: 30020000 movsr t002 nil 41: 4400002B jmp 43 42: 30020801 movsr t002 v00001 43: 10000002 end t002 44: 10000002 end t002 instruction count: 32 #<sys:vm-desc: 8522ca8> And, oh, the work is done by ... the case macro! 2> (macroexpand '(caseql x (1 'a) (2 'b) (3 'c) ((4 5 6) 'd) (7 'e) (8 'f) (9 'g))) (let ((#:test-0034 x) (#:swres-0036 '#:nohit)) (and (integerp #:test-0034) (<= 1 #:test-0034 9) (set #:swres-0036 (sys:switch (- #:test-0034 1) #(('a) ('b) ('c) ('d) ('d) ('d) ('e) ('f) ('g))))) (if (eq #:swres-0036 '#:nohit) (progn) #:swres-0036)) The sys:swtch special form is then spun into the jump table code.

gumby 7y ago

> The first example is easy: Implement an O(1) jump table in Common Lisp that respects the lexical environment. (You can’t, unless CASE is itself optimized to a jump table, which it usually isn’t.) Perhaps I don't understand your objection: you can certainly store any object in an array and funcall it which would be O(1); the object could be a lambda that captured the lexical environment. I was doing that 35 years ago on the lisp machine Interestingly I did this also on the D-Machine Interlisp and each closure forked the stack, so it ground the machine to a halt, a design bug later fixed. Both examples I'm talking about predate Common Lisp standardization.

ohyes 7y ago
For the true jump table experience Tagbody / go would also work just fine for this. You can put the ‘go’s in lambdas in an array and funcall them. This sounds like fun.
- reikonomusha 7y ago
  Not so. The table of lambdas have to be built at runtime, making it O(N). You can’t use LOAD-TIME-VALUE because that doesn’t respect the lexical environment, which TAGBODY tags live in.
  - ohyes 7y ago
    Well, you have to make the go statement in lexical scope in order for the tagbody to work... that seems reasonable enough to me. You specifically stated: > Implement an O(1) jump table in Common Lisp that respects the lexical environment. You don't know the lexical environment until there's a lexical environment to know, you can't have your cake and also eat it (or not have your cake and also know it). Interestingly, try/catch also solves this problem fairly elegantly without distastefully consing up a list or array at run-time. (defun jump2 (i) (let ((location nil)) (tagbody (catch 'a (catch 'b (catch 'c (catch 'd (setf location (elt #(a b c d) i)) (throw location nil)) (when location (print "D!") (go end))) (when location (print "C!") (go end))) (when location (print "B!") (go end))) (when location (print "A!") (go end)) end))) I'll leave the relevant macro to the reader, it shouldn't be that difficult... (I'm hoping I didn't just do someone's homework). edit: removed some cruft from experiments and fixed formatting
    - dan-robertson 7y ago
      Well here you can replace the tagbody with a block and replace the (go end) with an appropriate (return) instead do you can get results out of your jump table. But that’s beside the point because in practice this is probably O(n) not O(1). I think most CL compilers are going to need to push things to the control stack for each catch. Even if the compiler is clever enough to eliminate the catches, it still mightn’t implement the computation of which catch catches as O(n). So even in the best case of a very smart compiler, your code is basically equivalent to: (case i (0 (print "A!")) (1 ...)) Which isn’t guaranteed to be O(1). The point the GP is making is that the only solution which looks like it might O(1) (and indeed is O(1) if there is no (or just one) lexical scope to capture) is the array-of-lambdas-doing-go, but that this isn’t guaranteed by the language to be O(1) when the lexical scope changes each time because in a naive evaluation, the array of lambdas must be consed before jumping and this is O(n). The reason that it is reasonable to complain about this is that what one needs for a jump table is weaker than this. The lambdas do capture the lexical scope but they only have dynamic extent and don’t extend the scope at all so a lambda of the form (lambda () (go foo)) only has to be consed each time you hit the jump table because you can only reference foo once you are inside the tagbody. However the code to actually jump is likely to be static for most compilers. For guaranteed O(1) performance (which doesn’t rely on the cleverness of the compiler) you’d need to introduce a new special form, e.g. (jump n tag1 tag2 ... tagn) which evaluates n and jumps to the nth tag in its arguments in O(1) time.
reikonomusha 7y ago
The lambdas, a set of lexical closures, have to built at runtime, in order to capture the environment, and then stored in the array. That’s an O(N) operation.
- ScottBurson 7y ago
  No, it's O(1). Time complexity is about how the execution time grows with the size of the input, not the size of the program. In this case, each of those lambdas is a piece of the program text; the size of the jump table is therefore a constant for any particular program. The time complexity here is the time taken for one jump through the table as a function of the number of jumps, and clearly that's a constant also. In fact, it would still be a constant if the 'case' were implemented as a chain of 'if's. Time complexity, since it concerns asymptotic growth of runtime as a function of input size, is not the correct notion to invoke here. You're just interested in performance in the ordinary sense: you want your program to run as fast as reasonably possible, and you know that a chain of 'if's leaves something to be desired in that regard. Fair enough. But let's look at the array-of-closures implementation again. Assuming that the number of jumps made through one of these tables, once you've created it, is much larger than the number of times you have to create a table, it's a perfectly workable implementation. I think your second point is more substantive. I too have come to the conclusion that coroutines were an unfortunate omission from the CL spec.
  - gumby 7y ago
    > I too have come to the conclusion that coroutines were an unfortunate omission from the CL spec. There was no consensus on multiprocessing at the time of standardization and language support was very uncommon. But still it’s weird: coroutines were over 20 years old by then, and newer ideas like the condition system and CLOS were included. And while nowadays the CL runtime is considered small, at the time it was criticized for being too large.
    - ScottBurson 7y ago
      Coroutines are not quite threads, but then, they don't require a scheduler. They're also not quite firstclass continuations, but then, they're simpler to implement, simpler to use, and don't have the same implications for the rest of the language and implementation design. Still, they can do some of the things you might otherwise use threads or firstclass continuations for; and as reikonomusha points out, those things can be quite difficult to do otherwise in a clean way. I'm sure some of the implementors (though not Symbolics, of course) would have been unenthusiastic about their inclusion, but still I wish it had been done.

omaranto 7y ago

I think that simulating coroutines by explicitly building the call stack they would have had isn't too ugly. This solution only conses to build those call stacks: (defun leaves (tree) "Return a function that returns the leaves of TREE one by one when called repeatedly." (let ((work (list tree))) (flet ((schedule (x) (when x (push x work)))) (lambda () (loop for task = (pop work) until (atom task) do (schedule (cdr task)) (schedule (car task)) finally (return task)))))) (defun same-fringe-p (t1 t2) (loop with l1 = (leaves t1) and l2 = (leaves t2) for x1 = (funcall l1) and x2 = (funcall l2) while (or x1 x2) always (eql x1 x2)))

dreamcompiler 7y ago

I have a coroutine implementation that GB and I wrote for CCL. It runs on top of native threads and is rather kludgy. It's not nearly as elegant as an implementation using stack-groups. Now I prefer to solve problems like same-fringe with general composable streams (like SICP lazy sequences but using CLOS rather than closures).

aidenn0 7y ago

Yes, the missing feature of something of equivalent power to call/cc is my biggest missing feature of CL. I've considered implementing green threads for SBCL as that's fairly straightforward to implement at the runtime level. There is a working delimited continuation library, but it's not exactly trivial.

aidenn0 7y ago

Won't tagbody/go with an array of symbols work for jump tables (assuming GO is O(1)?): (tagbody (go (aref #(a b c d) N)) a ... b ... c ... d))

ScottBurson 7y ago
Alas, no; 'go' is a special form — its argument is unevaluated.
- aidenn0 7y ago
  Indeed it appears so. Strangely enough, the hyperspec doesn't specify that it's not evaluated.
  - dan-robertson 7y ago
    For special forms I think it’s implied that the arguments aren’t evaluated (as they are special) unless stated otherwise.
    - aidenn0 7y ago
      At least some forms say explicitly evaluated or not.

pfdietz 7y ago

You could do the jump tables if your CL gives you some access to the lexenv at compile time. What you do is modify the individual cases so that instead of accessing the surrounding runtime lexenv directly, they go through reader and writer thunks. These thunks are then passed in as a separate argument to the lambda for each case. The table mapping case values to these lambdas is a compile time constant. You might complain that this takes time proportional to the number of accessed objects in the lexenv, to set up the thunks. And that's true, but it's constant in the number of cases.

kazinator 7y ago

> (You can’t, unless CASE is itself optimized to a jump table, which it usually isn’t.) That's surprising. Even the brain-dead compiler in my TXR Lisp (a dialect that has some things in common with Common Lisp) does it. 1> (disassemble (compile-toplevel '(caseql x (1 'a) (2 'b) (3 'c) ((4 5 6) 'd) (7 'e) (8 'f) (9 'g)))) ** warning: (expr-1:3) unbound variable x data: 0: #:nohit 1: a 2: b 3: c 4: d 5: e 6: f 7: g syms: 0: x 1: integerp 2: <= 3: sys:b- code: 0: 04020002 frame 2 2 1: A0800000 getlx v00000 0 2: 30810400 movsr v00001 d000 3: 24010003 gcall t003 1 v00000 4: 08000001 5: 48000026 if t003 38 6: 00000003 7: 38050004 movrsi t004 1 8: 38250005 movrsi t005 9 9: 24030003 gcall t003 2 t004 v00000 t005 10: 00040002 11: 00050800 12: 48000026 if t003 38 13: 00000003 14: 38050005 movrsi t005 1 15: 24020004 gcall t004 3 v00000 t005 16: 08000003 17: 00000005 18: 54090004 swtch t004 24 26 28 30 30 30 32 34 36 19: 001A0018 20: 001E001C 21: 001E001E 22: 00220020 23: 00000024 24: 30810401 movsr v00001 d001 25: 44000025 jmp 37 26: 30810402 movsr v00001 d002 27: 44000025 jmp 37 28: 30810403 movsr v00001 d003 29: 44000025 jmp 37 30: 30810404 movsr v00001 d004 31: 44000025 jmp 37 32: 30810405 movsr v00001 d005 33: 44000025 jmp 37 34: 30810406 movsr v00001 d006 35: 44000025 jmp 37 36: 30810407 movsr v00001 d007 37: 30030801 movsr t003 v00001 38: 4C00002A ifq v00001 d000 42 39: 08010400 40: 30020000 movsr t002 nil 41: 4400002B jmp 43 42: 30020801 movsr t002 v00001 43: 10000002 end t002 44: 10000002 end t002 instruction count: 32 #<sys:vm-desc: 8522ca8> And, oh, the work is done by ... the case macro! 2> (macroexpand '(caseql x (1 'a) (2 'b) (3 'c) ((4 5 6) 'd) (7 'e) (8 'f) (9 'g))) (let ((#:test-0034 x) (#:swres-0036 '#:nohit)) (and (integerp #:test-0034) (<= 1 #:test-0034 9) (set #:swres-0036 (sys:switch (- #:test-0034 1) #(('a) ('b) ('c) ('d) ('d) ('d) ('e) ('f) ('g))))) (if (eq #:swres-0036 '#:nohit) (progn) #:swres-0036)) The sys:swtch special form is then spun into the jump table code.