[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.

[James_K]

> isn't making a dsl out of lisp macros rather traditional

The idea of a DSL is that it coexists with the regular code. Eg:

  (some-function (sql-query :select * :from ...))

The language mixes freely with other lisp forms and even with other DSLs. You can combine them like Lego bricks. When the entire program is written in a DSL, it is no longer a program in the host language, it is a program in a new language which uses the host language as an interpreter. Otherwise we would say Python files are written in C, because the Python interpreter is written in C. Python would only become a DSL in a C program if Python expressions were embedded into and cooperated with the surrounding C code. Both languages must be present simultaneously rather than one just interpreting the other.

> You can add your own syntactic abstractions to the language

The idea of an abstraction is that its closed in the formal sense. It affects only a small localised region of code. This makes it composable with other abstractions.

> I'm not entirely sure where you got these requirements for macros

It's what makes lisp macros different from the C pre-processor. You could, for example, run your C program through PHP as an additional pre-processing step and write arbitrarily complicated macros that way. The special thing about lisp is that it is homoiconic, and hence its macros can be composed in the same way other language features can. Eg:

  #define TEST 1)
  (1 + TEST == 2

It is valid to do this in C because macros are not closed. They can spill out and affect he surrounding code. While you technically could do something similar with reader macros in lisp, you notice that in practice, these macros are all written to be closed so that they can fit in with the code around them in a predictable way.

> hygenic macro-systems

While this is similar in the sense that it aims to have macros act more predictably, I am talking about a different aspect of macros. Specifically, I am saying that there are certain aspects of lisp macros which make them far more useful than simple text substitution. Certain most lisp dialects allow for macros which violate these principals, but I would say those macros are malformed. It is bad form to write them in lisp code, hence I don't consider them lisp macros.

[Kamq]

Hmm, ok, I think I might get what you're saying, it's not exactly what I thought you were getting at originally. Although I'm not quite following still. I did bring up hooking into the reader, but that was for something more than just the basic TCO with macros. I'm reasonably sure that what I was talking about can be done with normal macros themselves.

Just to check my understanding:

So, going back to your example, we have 3 functions f, g, and h. These will be re-written as one big function with gotos and three helper functions that call into the right point of that function.

So, is your objection to this that the other functions are re-written, or that a new function is defined in the namespace you happen to be in?

To elaborate further, let's say f, g, and h are defined in order. When f and g are compiled, nothing happens, but when h is compiled, noting that f and g are already defined, h is compiled into something like:

    (defun h (x)
      (flet ((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))))
      (fgh-loop 'h x)))

Obtaining the definitions for f and g by examining the environment and copying them over. That should be alright, in your opinion, right?

There's not as much benefit, as f and g don't get the optimization, but in exchange we don't get spooky action at a distance.

How about if we used a macro to define functions instead of the traditional defun? Each one registering the function as willing to be re-written when everything they depend on is defined. That should give the user of the code a warning that these functions are likely to be re-written. Functions that aren't defined using this macro aren't re-written, but don't gain the benefit.