5 ms·

After reading the first paragraph, I realized that I mistook "CL" to mean "Clojure." The comment about Common Lisp lacking tail-call-optimization being a facto

After reading the first paragraph, I realized that I mistook "CL" to mean "Clojure." The comment about Common Lisp lacking tail-call-optimization being a factor in not considering it a functional language reflects my only real problem with Clojure so far. Other than that, this writeup reflects what I've learned so far of Common Lisp - it's much more of an imperative style language than it is a functional language.

swannodette 16y ago
You can get most of the real benefits of TCO (including many mutually recursive functions) in Clojure with lazy-sequences. The harder (and less frequest) use case of TCO'ing CPS style code can be accomplished with trampoline.
- GrooveStomp 16y ago
  Lazy sequences are my favorite new language feature since learning Clojure.
irahul 16y ago
Clojure does have TCO, though you have to be explicit about it. I use Clojure's looping constructs and list comprehensions for most of the tasks; explicit TCO using loop/recur for problems which are best expressed recursively.
- GrooveStomp 16y ago
  Interesting, I didn't realize that loop/recur used TCO. Makes sense. :) As far as usage, I do like a friend told me: Favor map and filter, but use loop/recur if you're stuck.
- ohyes 16y ago
  Sort of. In true TCO, you optimize not only tail calls to the same function, but also tail calls to other functions. (Think of coroutines as an application). One way to think of a TCO is that you are turning a function call (machine code to save your spot in the function, then a jump) into a simple jump (you don't need to save your spot, because there is nothing left in the function anyway). Clojure doesn't support this (because it would be too difficult[inefficient, i think kawa scheme and JRuby do implement it] on the JVM). I assume that the common lisps which do support TCO, have true TCO, as they are using assembly or interpreters. Clojure's TCO can be seen as a special form of a loop (in fact, it is very easy to write a macro that takes a loop-recur form and transforms it into a common lisp style Do* loop).
  - swannodette 16y ago
    As I mention below you can get the same result with lazy-sequences and it's very efficient.
    - ohyes 16y ago
      I think that you would have to be careful with that. To my knowledge, with lazy sequences in Clojure, the thunks are grouped into segments of 32. This chunking is for efficiency, but it has the (sometimes) weird implication that you ask for the first element in a sequence and it evaluates that first element, and the next 31 elements as well. This is troublesome if you attempt to use side effects. (Mr. Fogus has a nice writeup (and workaround) of this phenomena here: http://blog.fogus.me/2010/01/22/de-chunkifying-sequences-in-clojure/ http://blog.fogus.me/2010/01/22/de-chunkifying-sequences-in-...) I have to admit, I am not quite getting my head around how using a lazy sequence to the same effect would work (ignoring the chunking issue). I see how they are similar, a lazy sequence is just a flattened trampoline. Could you maybe pastebin or lisppaste an example? Anyway, I guess the point I was trying to make was not that it is impossible to do these things, but that TCO is a compiler level optimization of the function calling convention (manipulating the stack), and although Clojure has 'tail calls,' it can't really be called TCO in the true sense of the word. (Which is OK, as you said, there are other ways to do this sort of stuff).
      - swannodette 16y ago
        You can easily create true one-at-a-time lazy-sequences. I've been working on my own implementation of miniKanren (from The Reasoned Schemer) in Clojure. It's been quite challenging since the original implementation assumes the presence of TCO. Also one-at-time laziness is very much required here to enforce interleaving of streams results and to avoid divergence. I was happy to find I could get the same non-stack consuming behavior and that it turns out to perform better than miniKanren under Racket. https://github.com/swannodette/logos/blob/master/src/logos/minikanren.clj#L226 https://github.com/swannodette/logos/blob/master/src/logos/m...
smanek 16y ago
Just to clarify, although the CL spec doesn't require TCO, every CL implementation I've used has it anyways.

swannodette 16y ago

You can get most of the real benefits of TCO (including many mutually recursive functions) in Clojure with lazy-sequences. The harder (and less frequest) use case of TCO'ing CPS style code can be accomplished with trampoline.

GrooveStomp 16y ago
Lazy sequences are my favorite new language feature since learning Clojure.

irahul 16y ago

Clojure does have TCO, though you have to be explicit about it. I use Clojure's looping constructs and list comprehensions for most of the tasks; explicit TCO using loop/recur for problems which are best expressed recursively.

GrooveStomp 16y ago
Interesting, I didn't realize that loop/recur used TCO. Makes sense. :) As far as usage, I do like a friend told me: Favor map and filter, but use loop/recur if you're stuck.
ohyes 16y ago
Sort of. In true TCO, you optimize not only tail calls to the same function, but also tail calls to other functions. (Think of coroutines as an application). One way to think of a TCO is that you are turning a function call (machine code to save your spot in the function, then a jump) into a simple jump (you don't need to save your spot, because there is nothing left in the function anyway). Clojure doesn't support this (because it would be too difficult[inefficient, i think kawa scheme and JRuby do implement it] on the JVM). I assume that the common lisps which do support TCO, have true TCO, as they are using assembly or interpreters. Clojure's TCO can be seen as a special form of a loop (in fact, it is very easy to write a macro that takes a loop-recur form and transforms it into a common lisp style Do* loop).
- swannodette 16y ago
  As I mention below you can get the same result with lazy-sequences and it's very efficient.
  - ohyes 16y ago
    I think that you would have to be careful with that. To my knowledge, with lazy sequences in Clojure, the thunks are grouped into segments of 32. This chunking is for efficiency, but it has the (sometimes) weird implication that you ask for the first element in a sequence and it evaluates that first element, and the next 31 elements as well. This is troublesome if you attempt to use side effects. (Mr. Fogus has a nice writeup (and workaround) of this phenomena here: http://blog.fogus.me/2010/01/22/de-chunkifying-sequences-in-clojure/ http://blog.fogus.me/2010/01/22/de-chunkifying-sequences-in-...) I have to admit, I am not quite getting my head around how using a lazy sequence to the same effect would work (ignoring the chunking issue). I see how they are similar, a lazy sequence is just a flattened trampoline. Could you maybe pastebin or lisppaste an example? Anyway, I guess the point I was trying to make was not that it is impossible to do these things, but that TCO is a compiler level optimization of the function calling convention (manipulating the stack), and although Clojure has 'tail calls,' it can't really be called TCO in the true sense of the word. (Which is OK, as you said, there are other ways to do this sort of stuff).
    - swannodette 16y ago
      You can easily create true one-at-a-time lazy-sequences. I've been working on my own implementation of miniKanren (from The Reasoned Schemer) in Clojure. It's been quite challenging since the original implementation assumes the presence of TCO. Also one-at-time laziness is very much required here to enforce interleaving of streams results and to avoid divergence. I was happy to find I could get the same non-stack consuming behavior and that it turns out to perform better than miniKanren under Racket. https://github.com/swannodette/logos/blob/master/src/logos/minikanren.clj#L226 https://github.com/swannodette/logos/blob/master/src/logos/m...

smanek 16y ago

Just to clarify, although the CL spec doesn't require TCO, every CL implementation I've used has it anyways.