[kazinator]

> separated by language vs library

You're totally new to Lisp, right? There is no such clear boundary in Lisp languages.

> This can't be relevant when the objects referenced by these collections are mutable.

Why not? Explain your reasoning. E.g. why is not not relevant that we can make a longer list by adding an element to the front of a shorter list, without mutating that shorter list, if the elements are objects that support mutation?

[karmakaze]

How so? Tail-call optimization would be a language feature. The math/graph operations in a lib/module etc.

An example would be if presence in a collection is dependent on mutable properties of its entries.

[Kamq]

> Tail-call optimization would be a language feature.

Most lisps generally do it this way (except maybe emacs lisp?), but there's not really a requirement for it to be a language feature. TCO is really just AST manipulation, and lisp macros are more than capable of that, although you might want to hook into the reader as well if Kamila supports it (I didn't see anything about that in the github readme).

[James_K]

> TCO is really just AST manipulation

While it is true that tail call relationships can always be represented using goto, it requires that all related code is known to make this conversion. For instance:

  (defun f (x) (a x) (g x))
  (defun g (x) (b x) (h x))
  (defun h (x) (c x) (f x))

You cannot remove the tail call by altering the AST of F, G, or H. Instead, a third function must be instroduced that contains the bodies of all functions in the loop.

  (defun fgh-loop (start-at x)
    (tagbody
     (case start-at
           ((f) (go f))
           ((g) (go g))
           ((h) (go h)))
       f (a x) (go g)
       g (b x) (go h)
       h (c x) (go f)))
  (defun f (x) (fgh-loop 'f x))
  (defun g (x) (fgh-loop 'g x))
  (defun h (x) (fgh-loop 'h x))

You can only apply such optimisations in retrospect, but a macro would only have access to the body of F at the point of definition for F. And even then, you cannot TCO any lambdas that are passed around. A simple example is the Y combinator:

  ((lambda (x) (x x)) (lambda (x) (x x)))

[Kamq]

> You can only apply such optimisations in retrospect, but a macro would only have access to the body of F at the point of definition for F.

There's no actual reason for this, you can get the symbol tree for the functions in question, assuming the runtime allows this (several do), and re-compile them and blow over the old definitions. You can only apply the optimization once all of f, g, and h are defined, there's no rule saying that a macro can only modify the function being defined, or that other functions can't be defined (the CLOS would be impossible if that were the case).

Both this and the lambda example should be doable with function-lambda-expression, although it's not exactly standardized. It should be possible in principal with the right implementation.

[James_K]

> It should be possible in principal with the right implementation

Most implementations that do this also support TCO, and I think the process itself goes a little beyond AST manipulation. It's basically just manually combining the entire program into one function to get a version of unconstrained goto. It isn't a macro in the traditional lisp-sense of the word, more of a compiler for a new programming language that uses lisp as a host. Practically speaking, it doesn't have many of the properties that are important in macros. It is not defined in a composable way, and it needs deep integration with the language runtime. Tor instance to handle definitions that mutually recur between different packages, it would need to be installed globally in the implementation rather than locally in a given package. So if two packages tried to use different recursion macros, they would likely be incompatible. While it could hypothetically be implemented on top of another lisp, it is really only possible to do so properly as a language feature.

[Kamq]

> Most implementations that do this also support TCO

Sure, I acknowledged that in my original post. I just said that it didn't have to be done that way.

> It's basically just manually combining the entire program into one function to get a version of unconstrained goto.

You really only need to combine those functions in question, and common lisp already has a pretty unconstrained goto already. Worst case, if you're willing to deal with the code bloat, you could copy the function definitions of the functions in question into each function as it's compiled (you'd have to defer macro expansion for n-1 of the functions though until runtime, or conditionally trigger re-compilation as each one is compiled). Probably would be a big pain though.

> It isn't a macro in the traditional lisp-sense of the word, more of a compiler for a new programming language that uses lisp as a host.

I mean, isn't making a dsl out of lisp macros rather traditional? That's how the loop construct began. The CLOS/Metaobject protocol also started out as 3rd party packaged, and they're also absolute beasts.

But, like, that's kinda the point of lisp. You can add your own syntactic abstractions to the language. Adding things to the language is part of the language. Is the argument here that those dsls aren't really lisp? How about the dsls that made it into some of the standards?

> it doesn't have many of the properties that are important in macros. It is not defined in a composable way, and it needs deep integration with the language runtime.

I'm not entirely sure where you got these requirements for macros, but I've never heard them. Admittedly, I've spent most of my time in Common Lisp and playing around with some of its ancestors. Maybe this is the case in some of the more scheme derived languages with hygenic macro-systems? I haven't really played around with them that much aside from a semester of scheme way back in the day in college.

Also, you might be able to get around the language runtime integration by hooking into the reader, but that would probably require making a meta-compiler (or at least keeping track of the symbol trees of everything that you've compiled so far). Would be a lot more portable than the thing I'm thinking of though.

> So if two packages tried to use different recursion macros, they would likely be incompatible.

With the implementation I have in my head, I think you could re-write the ones in the other package with the recursion method that the last one that gets compiled uses, but this would probably open up even more of a can of worms.

I agree that this is a good reason to do it as a language feature instead of as a macro, but not that it's impossible to do as a macro.

[kazinator]

cons is a graph operation and + is a math operation. Go on ...