Lisp in Dart 2.0

[decafbad]

"Tail call optimization, which also implies tail recursion optimization"

I thought those were exactly same thing.

[cwzwarich]

There are three distinct concepts that are often conflated:

1) The syntactic construct of a tail call.

2) Abstract space efficiency properties that guarantee asymptotic space usage of programs using tail calls.

3) The implementation techniques used to guarantee 2).

Even though the implementation techniques of 3) apply to all calls, the space efficiency properties in 2) are asymptotic and thus are only meaningful when applied to programs with unbounded recursive function invocations. Applying the techniques of 3) only to function calls that might potentially be involved in a recursive chain would still satisfy any of the standard definitions of 2).

See Will Clinger's paper Proper Tail Recursion and Space Efficiency (https://dl.acm.org/citation.cfm?id=277719) for details regarding the standard definition of "proper tail recursion" used in the Scheme spec and elsewhere.

[uryga]

You can also optimize non-recursive tail calls:

  def add10(y: int) -> int:
      return y+10

  def def add11(x: int) -> int:
      # won't get optimized
      return add10(x)+1

  def add11_tail(x: int) -> int:
      # should get optimized
      return add10(x+1)

in `add11_tail` the call to `add10` is in the tail position, i.e. you can "forget" about `add11_tail`'s stack frame since it's not needed anymore. It's still needed in `add10`, because you start in `add11`, call `add10` and go back to to `add11` to add 1 to the result.

[patrec]

In a language with guranteed tail call optimization, the below consumes no stack, although there's no recursion.

    def f(a):
       return g(2*a)

    def g(a):
       return a + 1

[chc4]

Tail call optimization is returning the result of any function, with tail recursion being the specific case where it's the same function. I think I've seen some languages where they special-case recursion by doing a code transformation, but would stack overflow if you called anything else instead.

[ac130kz]

I have only one question: what is the purpose of this stuff? Was it made to extend the possibilies of Dart?

[indigo747]

It looks like it was for fun. The author has several repositories on Github holding Lisp interpreters in different languages. It might also be a learning technique: interpreters for higher order languages are good intermediate projects when learning new languages.

[stewbrew]

"A sort of subset of Emacs Lisp, but being Lisp-1 with lexical scoping"

Couldn't we please base such things on scheme or clojure (for Lisp-1) or common lisp (for Lisp-2).