Title: Lower self-recursive tail calls to while loops (loopification) by Unisay · Pull Request #205 · purescript-lua/purescript-lua · GitHub
Open Graph Title: Lower self-recursive tail calls to while loops (loopification) by Unisay · Pull Request #205 · purescript-lua/purescript-lua
X Title: Lower self-recursive tail calls to while loops (loopification) by Unisay · Pull Request #205 · purescript-lua/purescript-lua
Description: Closes #181. What A self-recursive tail call now lowers to a while true do loop with simultaneous multiple assignment of the parameters. return go$w(e1, e2) in tail position becomes p1, p2 = e1, e2 followed by fall-through to the end of the loop body; every other exit path keeps its return, which leaves the loop. The transform lives in the Lua code generator (new module Language.PureScript.Backend.Lua.Loopify), applied to recursive-group bindings at the two places they are lowered: top-level groups (self-reference through the M table) and Let-bound groups (plain local). The expression IR keeps no loop node, the same choice magicDo makes for statements. Foreign code never passes through it. Tail positions are found by walking the block spine of the generated function: the final statement of the body and, recursively, the final statement of each branch of a block-final if. This is exactly where the code generator puts IR tail positions (through Let bodies and IfThenElse branches), and it is what makes fall-through work as "continue" on a target without goto. Two things fell out beyond the issue text: Plain unary self-recursions loopify too, without needing a worker/wrapper split: countdown n = ... countdown (n - 1), and structural recursions like bat (Succ n) = bat n (which becomes n = n.value0). Only the tail self-calls need rewriting. Non-tail self-calls and the wrapper indirection stay real calls, each starting a fresh activation with its own loop. McCarthy 91 in the golden shows both in one body. Correctness guards Capture veto. Lua closures capture variables by reference, and parameters of a loopified function are shared across iterations, so a closure created in one iteration and surviving into the next would observe the reassigned values. A body that references a parameter from inside a nested function literal is therefore not loopified. Immediately-invoked scope wrappers (function() ... end)() are looked through transparently; without that, the comparison predicates the case compiler emits (IIFEs reading the scrutinee) would veto nearly everything. The golden's CPS accumulator (sumCPS n k = ... sumCPS (n - 1) (\r -> k (r + n))) pins the veto: it stays recursive, and the hand-written eval oracle would catch the corruption if it ever loopified. Explist balancing. The assignment's right-hand explist is balanced to the variable count, because the code generator drops trailing unused parameters and trailing Prim.undefined arguments, so the two lists can disagree in length. A short list is padded with explicit nils (declined when the last argument is a call or vararg, whose multiple results the pad would truncate where the call form spreads them); surplus expressions facing dropped parameters are removed when syntactically pure, and decline the rewrite otherwise. This also keeps luacheck's unbalanced-assignment check quiet. Tests New golden Golden.Loopification.Test with six shapes (unary countdown, binary accumulator, local where-bound worker, McCarthy 91, CPS capture veto, dead trailing parameter) and a hand-written eval oracle. Nine unit tests in Lua.Spec cover the decision points through fromUberModule: top-level and Let-bound groups, non-tail calls, the capture veto, and all four explist-balancing outcomes. Four existing goldens moved: Uncurry (the sumTo worker), LongCallbackChain, PatternMatching.Test2, and StringCodePoints (the library's codePointAtFallback worker loopifies). golden.ir files are untouched, since the transform is strictly Lua-side. All eval oracles pass unchanged. Measurements On curried_step (n=2e6, medians): PUC Lua 0.363s to 0.348s, the modest constant-factor win the issue predicted, since the loop body is still dominated by curried FFI closure allocation. Under LuaJIT the loop is blacklisted (IFUNCF to ILOOP in the accepted trace report) because those same per-iteration FNEWs abort trace recording, and the benchmark regresses from 0.196s to 0.366s for now. That interim regression should flip once #178/#180/#186 remove the allocations from loop bodies; it is tracked in #204.
Open Graph Description: Closes #181. What A self-recursive tail call now lowers to a while true do loop with simultaneous multiple assignment of the parameters. return go$w(e1, e2) in tail position becomes p1, p2 = e1, e2...
X Description: Closes #181. What A self-recursive tail call now lowers to a while true do loop with simultaneous multiple assignment of the parameters. return go$w(e1, e2) in tail position becomes p1, p2 = e1, e2...
Opengraph URL: https://github.com/purescript-lua/purescript-lua/pull/205
X: @github
Domain: github.com
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /:user_id/:repository/pull/:id/files(.:format) |
| route-controller | pull_requests |
| route-action | files |
| fetch-nonce | v2:6aa48444-35be-7de0-3543-d4f96a88ae9f |
| current-catalog-service-hash | ae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b |
| request-id | BD52:2E124E:910BD0:BA9A91:6B00EF99 |
| html-safe-nonce | fe3aad1f10082a13488223b95a4c8a47e59feb37df1edc2d9b4410cf2c321a9e |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJCRDUyOjJFMTI0RTo5MTBCRDA6QkE5QTkxOjZCMDBFRjk5IiwidmlzaXRvcl9pZCI6IjUyODUwMDY0NjY5NjM1MzM3MjIiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ== |
| visitor-hmac | 3d66ada9f7f1c95f5a7858737ab664f1a59c5a26708c1b665e2964dbeb0a88f2 |
| hovercard-subject-tag | pull_request:4009497751 |
| github-keyboard-shortcuts | repository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/purescript-lua/purescript-lua/pull/205/files |
| twitter:image | https://avatars.githubusercontent.com/u/1009751?s=400&v=4 |
| twitter:card | summary_large_image |
| og:image | https://avatars.githubusercontent.com/u/1009751?s=400&v=4 |
| og:image:alt | Closes #181. What A self-recursive tail call now lowers to a while true do loop with simultaneous multiple assignment of the parameters. return go$w(e1, e2) in tail position becomes p1, p2 = e1, e2... |
| og:site_name | GitHub |
| og:type | object |
| hostname | github.com |
| expected-hostname | github.com |
| None | 4ef498cbabcbe3c50befc7a5b743e7072ee770b4daf0e15e54801180d1fa91fc |
| turbo-cache-control | no-preview |
| diff-view | unified |
| go-import | github.com/purescript-lua/purescript-lua git https://github.com/purescript-lua/purescript-lua.git |
| octolytics-dimension-user_id | 131581790 |
| octolytics-dimension-user_login | purescript-lua |
| octolytics-dimension-repository_id | 587200487 |
| octolytics-dimension-repository_nwo | purescript-lua/purescript-lua |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 587200487 |
| octolytics-dimension-repository_network_root_nwo | purescript-lua/purescript-lua |
| turbo-body-classes | logged-out env-production page-responsive full-width |
| disable-turbo | true |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 9983dd5da06943f833c971dd5b6bc988e2858be5 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
Links:
Viewport: width=device-width