Page MenuHomePhabricator

Support Tail Recursion (at Least When Using the Tail Function)
Closed, ResolvedPublic

Description

Description

This may be very easy in composition language V2. The object returned by Z812/Tail could attach its scope to the previous frame, rather than retaining the scope of the call to Z812. That way, arbitrary numbers of calls to Z812/Tail would produce an object parented to the same stack frame, obviating stack frame growth when iterating over a list.

In future, we might even allow user-defined functions to describe themselves as tail calls, allowing for any function to take advantage of this behavior.

Desired behavior/Acceptance criteria (returned value, expected error, performance expectations, etc.)

  • return value of Z812/Tail should be attached to parent scope, not the current scope
  • stack size should no longer grow when using Z812/Tail to iterate over a list

Completion checklist

Event Timeline

Sounds like fun! I’ve recently added prepend reversed first list to second list (Z31580) as a “primitive” reversal function. It scales reasonably well, but can we look forward to significant improvement with V2 tail-call optimisation? One thing I noticed is that the type for the result list is de-referenced to a full type object on recursion, which seems undesirable.

Reversing 49 forms of être.

Hopefully! There are some aspects of tail recursion that will require additional work (namely, an extra abstraction to track whether an arbitrary set of resolution operations from one Z7 leads to another Z7), but for the uses of Z812 in particular, I suspect we'll be able to get some improvements. The type de-referencing will hopefully be fixed in V2, as well. I'm now going to make liberal use of your function as a test case, hehe.

Sounds like fun! I’ve recently added prepend reversed first list to second list (Z31580) as a “primitive” reversal function. It scales reasonably well, but can we look forward to significant improvement with V2 tail-call optimisation? One thing I noticed is that the type for the result list is de-referenced to a full type object on recursion, which seems undesirable.

Reversing 49 forms of être.

Nice! There’s some problem with the function signature, for which I’ve filed a ticket. I’ve also used the function in:

Another interesting (?) implementation is:

Hopefully! There are some aspects of tail recursion that will require additional work (namely, an extra abstraction to track whether an arbitrary set of resolution operations from one Z7 leads to another Z7), but for the uses of Z812 in particular, I suspect we'll be able to get some improvements. The type de-referencing will hopefully be fixed in V2, as well. I'm now going to make liberal use of your function as a test case, hehe.

cmassaro renamed this task from Support Tail Recursion to Support Tail Recursion (at Least When Using the Tail Function).Sun, Feb 15, 10:08 AM

apine opened https://gitlab.wikimedia.org/repos/abstract-wiki/wikifunctions/function-orchestrator/-/merge_requests/549

Draft: Support stack/rate limits in composition language v2; test that stack size doesn't grow in tail() compositions.

ecarg merged https://gitlab.wikimedia.org/repos/abstract-wiki/wikifunctions/function-orchestrator/-/merge_requests/549

Support stack/rate limits in composition language v2; test that stack size doesn't grow in tail() compositions.

Change #1240291 had a related patch set uploaded (by Jforrester; author: Jforrester):

[operations/deployment-charts@master] wikifunctions: Upgrade orchestrator from 2026-02-11-121010 to 2026-02-18-140059

https://gerrit.wikimedia.org/r/1240291

Change #1240291 merged by jenkins-bot:

[operations/deployment-charts@master] wikifunctions: Upgrade orchestrator from 2026-02-11-121010 to 2026-02-18-140059

https://gerrit.wikimedia.org/r/1240291