René's URL Explorer Experiment


Title: fix(ir): bound the bottom-up rewrite driver's re-application loop (#348) by Unisay · Pull Request #350 · purescript-lua/purescript-lua · GitHub

Open Graph Title: fix(ir): bound the bottom-up rewrite driver's re-application loop (#348) by Unisay · Pull Request #350 · purescript-lua/purescript-lua

X Title: fix(ir): bound the bottom-up rewrite driver's re-application loop (#348) by Unisay · Pull Request #350 · purescript-lua/purescript-lua

Description: Closes #348. The symptom pslua optimizes its intermediate representation (IR) by rewriting expression trees, and the rewrite rules are exercised by Hedgehog properties that generate random IR terms. Three of the first 500 hspec seeds — 109, 152 and 478 — made the IR Optimizer spec group stop emitting output and pin one core indefinitely. A complete run of that group costs 0.35 s; these were still spinning when killed at 120 s, with a flat 50 MiB resident set, so nothing was growing — the optimizer was looping. $ timeout 120 $(cabal list-bin spec) --match "IR Optimizer" --seed 109 blanking an unused shadowing binder keeps outer references bound [✔] ✓ property passed 1 test. timeout 120 $SPEC --match "IR Optimizer" --seed 109 119.58s user 0.21s system 99% cpu 2:00.00 total The last line printed is the test declared immediately before optimization keeps expressions well-scoped, the property that feeds generated terms through the whole optimizer pipeline — so the loop was inside that property, and it hung rather than reddening, which is the easiest kind of failure to misread as flakiness. What was looping The IR rewrite driver rewriteExpBottomUpM walks an expression bottom-up: it rewrites a node's children first, then applies the rule set to the node, and re-applies it to its own result until the rule set stops firing. That re-application loop had no bound. rewriteExpBottomUpM rule expr = runWriterT $ flip (rewriteMOf subexpressions) expr \e → lift (rule e) >>= traverse \e' → e' <$ tell Rewritten Among the rules that loop drives is betaReduce, which reduces a redex (λx. M) N to M[x := N]. Beta reduction has no terminating strategy on an arbitrary untyped term, and the generator draws untyped terms: it drew Ω = (λx. x x) (λy. y y), the smallest term with no normal form, whose every reduction step reproduces it modulo binder names. Instrumenting the loop to abort after 400 nested rewrites and print the node it was chewing on shows the cycle exactly — the two abstractions swap places and every binder index advances by one, because pasting a copy of the argument freshens its binders: BEFORE: AppN () (AbsN () (ParamNamed () (Name "x$400") :| []) (AppN () (Ref () (Local (Name "x$400"))) (Ref () (Local (Name "x$400")) :| []))) (AbsN () (ParamNamed () (Name "x$401") :| []) (AppN () (Ref () (Local (Name "x$401"))) (Ref () (Local (Name "x$401")) :| [])) :| []) AFTER: AppN () (AbsN () (ParamNamed () (Name "x$401") :| []) (AppN () (Ref () (Local (Name "x$401"))) (Ref () (Local (Name "x$401")) :| []))) (AbsN () (ParamNamed () (Name "x$402") :| []) (AppN () (Ref () (Local (Name "x$402"))) (Ref () (Local (Name "x$402")) :| [])) :| []) All three seeds hit the same term. So this is not the non-converging rule pair the issue guessed at, and it is not a guard that betaReduce is missing: no local test on a redex can decide whether reducing it terminates. The pass-level pipeline was never the problem either — its fixpoint combinator has carried a 1000-iteration backstop for a while. The unbounded loop was one level below it, inside a single pass, at a single node. The fix The loop now carries a budget, spelled maxNestedRewrites, and returns the term it has reached when the budget runs out: rewriteExpBottomUpM rule = runWriterT . reapply maxNestedRewrites where reapply budget = transformMOf subexpressions \e → lift (rule e) >>= \case Nothing → pure e Just e' → do tell Rewritten case budget of 0 → pure e' _ → reapply (budget - 1) e' This is the treatment the pass-level fixpoint already gives its own iteration cap: stopping early costs optimization and nothing else, because each rewrite preserves semantics and the IR invariants on its own, so a term the driver abandons mid-reduction is exactly as valid as a fully reduced one. The driver's WasRewritten flag — which the enclosing fixpoint trusts to decide whether to iterate again — also stays precise: it reports Rewritten iff some rule fired, whether or not the loop ran to exhaustion. The budget is 100, and it cannot reach legitimate work. Instrumenting the driver to record the deepest nesting it ever reaches and running the whole suite gives 5 — 1232 examples, 344 of them golden compilations of real PureScript including the ~300-deep constant chains that stress the pipeline hardest. That is the population that matters, since the IR is assumed well-typed (Note [IR is assumed well-typed]) and PureScript's type system rejects every term without a normal form; only the untyped terms the generators draw reach the bound at all. Diagnosability Nothing is silent about a term that exhausts the budget. optimizedUberModule (the production pipeline) returns a correct, under-optimized module, while optimizedUberModuleChecked (the same pipeline with every pass's contract linted, used by the test suite always and by the CLI behind --lint-ir) reports which fixpoint kept firing: optimizedUberModuleChecked mempty original === Left (FixpointDivergence "optimize+dce" maxFixpointIterations) Each round of that fixpoint genuinely changes the module — it advances Ω by another 100 beta steps — so the fixpoint runs its full cap and then names itself, which is the third acceptance criterion of the issue. Tests Two example-based tests replace the generator draw, so the fix is pinned by something that does not depend on a seed. Both hang on the parent commit; the test commit is deliberately red. let selfApplication name = abstraction (paramNamed name) $ application (refLocal name) (refLocal name) omega = application (selfApplication (Name "x")) (selfApplication (Name "y")) The first asserts the pipeline returns at all and that the abandoned term still satisfies the two IR invariants — lintWellScoped (every local reference resolves to an enclosing binder) and lintUniqueBinders (no local binder name bound twice within a top-level site). The second pins the FixpointDivergence report above. Verification cabal test all is green (1234 examples), fourmolu and hlint are clean, and the golden corpus is byte-identical — no golden.ir or golden.lua moved, which follows from the bound being 20× clear of the deepest chain any real compilation produces. The check the issue asks for is the sweep that found the stall, so here it is over the same range, with a timeout generous against the group's cost: $ for s in $(seq 1 500); do timeout 60 $SPEC --match "IR Optimizer" --seed $s; done worst_elapsed=6s failures: Every seed passes; the worst is seed 109 at 6 s. Two costs are worth naming rather than hiding. The group now takes about 3 s at every seed, up from 0.35 s, because the new example-based test deliberately drives the budget to exhaustion twice — the enclosing optimize+dce fixpoint keeps spending its 1000 rounds advancing a term that will never converge, since each round does change the module. On top of that, the three seeds that draw Ω themselves add ~2 s (109 → 6 s, 152 and 478 → 5 s). Full-suite wall clock is unchanged within noise at 88 s. Making an exhausted budget stop the enclosing fixpoint at once would remove both, but it means widening Pass.passRun's result and its three runners, so it belongs in its own change.

Open Graph Description: Closes #348. The symptom pslua optimizes its intermediate representation (IR) by rewriting expression trees, and the rewrite rules are exercised by Hedgehog properties that generate random IR terms...

X Description: Closes #348. The symptom pslua optimizes its intermediate representation (IR) by rewriting expression trees, and the rewrite rules are exercised by Hedgehog properties that generate random IR terms...

Opengraph URL: https://github.com/purescript-lua/purescript-lua/pull/350

X: @github

direct link

Domain: github.com

react-profiling0
react-import-mapreact,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-controllerpull_requests
route-actionfiles
fetch-noncev2:2ea376dd-56a0-16f3-507e-3d956e5857c1
current-catalog-service-hashae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b
request-idEE46:3F8AB1:8E4002:B8D855:6B00DBE3
html-safe-nonce2e06c2d0bff9caeff022501a2beadf01efe9c220dd4f69eac92845c42993817d
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJFRTQ2OjNGOEFCMTo4RTQwMDI6QjhEODU1OjZCMDBEQkUzIiwidmlzaXRvcl9pZCI6Ijg4MDAzNDI4MzgzMDgwMzU1NTUiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ==
visitor-hmaccf6bb958b058fbad6a864f72a9ddcb13c404c982e1214bb4e88da3a83d92f825
hovercard-subject-tagpull_request:4159607466
github-keyboard-shortcutsrepository,pull-request-list,pull-request-conversation,pull-request-files-changed,copilot
google-site-verificationApib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I
octolytics-urlhttps://collector.github.com/github/collect
analytics-location///pull_requests/show/files
fb:app_id1401488693436528
apple-itunes-appapp-id=1477376905, app-argument=https://github.com/purescript-lua/purescript-lua/pull/350/files
twitter:imagehttps://avatars.githubusercontent.com/u/1009751?s=400&v=4
twitter:cardsummary_large_image
og:imagehttps://avatars.githubusercontent.com/u/1009751?s=400&v=4
og:image:altCloses #348. The symptom pslua optimizes its intermediate representation (IR) by rewriting expression trees, and the rewrite rules are exercised by Hedgehog properties that generate random IR terms...
og:site_nameGitHub
og:typeobject
hostnamegithub.com
expected-hostnamegithub.com
None043c3f30fbcbe2c6c8e729e10cbbbc90c406546f9fbbb67c648d38f6b7d16daf
turbo-cache-controlno-preview
diff-viewunified
go-importgithub.com/purescript-lua/purescript-lua git https://github.com/purescript-lua/purescript-lua.git
octolytics-dimension-user_id131581790
octolytics-dimension-user_loginpurescript-lua
octolytics-dimension-repository_id587200487
octolytics-dimension-repository_nwopurescript-lua/purescript-lua
octolytics-dimension-repository_publictrue
octolytics-dimension-repository_is_forkfalse
octolytics-dimension-repository_network_root_id587200487
octolytics-dimension-repository_network_root_nwopurescript-lua/purescript-lua
turbo-body-classeslogged-out env-production page-responsive full-width
disable-turbotrue
browser-stats-urlhttps://api.github.com/_private/browser/stats
browser-errors-urlhttps://api.github.com/_private/browser/errors
release5425dc24e8bd8d6fca9641a12afc984825a43875
ui-targetfull
theme-color#1e2327
color-schemelight dark

Links:

Skip to contenthttps://github.com/purescript-lua/purescript-lua/pull/350/files#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpurescript-lua%2Fpurescript-lua%2Fpull%2F350%2Ffiles
GitHubRepository hosting, code review, and collaborationhttps://github.com/platform
CopilotAI coding agent for tasks, projects, and automated workhttps://github.com/features/copilot
ActionsCI/CD and automationhttps://github.com/features/actions
Code QualityQuality analysis, fixes, and enforcementhttps://github.com/features/code-quality
CodespacesCloud development environmentshttps://github.com/features/codespaces
Code SecurityVulnerability detection and remediationhttps://github.com/security/advanced-security/code-security
Secret ProtectionSecret scanning and leak preventionhttps://github.com/security/advanced-security/secret-protection
All Featureshttps://github.com/features
Documentationhttps://docs.github.com/en
Traininghttps://learn.github.com/skills
Certificationshttps://learn.github.com/credentials
Build with Copilothttps://github.com/features/ai
Customize Copilothttps://docs.github.com/en/copilot/how-tos/copilot-on-github/customize-copilot/customize-copilot-overview
Integrationshttps://github.com/marketplace
Trending reposhttps://github.com/trending
GitHub Sponsorshttps://github.com/open-source/sponsors
Developer articleshttps://github.com/resources/articles
ChangelogYour source for the latest features, improvements, and fixes across GitHub products, all in one place.https://github.blog/changelog/
Enterpriseshttps://github.com/enterprise
Teamhttps://github.com/team
Startupshttps://github.com/enterprise/startups
Nonprofitshttps://github.com/solutions/industry/nonprofits
Healthcarehttps://github.com/solutions/industry/healthcare
Financial serviceshttps://github.com/solutions/industry/financial-services
Manufacturinghttps://github.com/solutions/industry/manufacturing
Governmenthttps://github.com/solutions/industry/government
See all industrieshttps://github.com/solutions/industry
Why GitHubhttps://github.com/why-github
Customer Storieshttps://github.com/customer-stories
Business insightshttps://github.com/solutions/executive-insights
Trust Centerhttps://github.com/trust-center
GitHub Advanced SecurityEnterprise-grade code securityhttps://github.com/security/advanced-security
Copilot for businessEnterprise-grade AI featureshttps://github.com/features/copilot/copilot-business
Premium SupportEnterprise-grade 24/7 supporthttps://github.com/enterprise/premium-support
Documentationhttps://docs.github.com/en
Resource centerhttps://github.com/resources
Bloghttps://github.blog/
Events & webinarshttps://github.com/resources/events
Community Forumhttps://github.com/orgs/community/discussions
Customer Storieshttps://github.com/customer-stories
Integrationshttps://github.com/marketplace
Customer supporthttps://help.github.com/
Traininghttps://learn.github.com/skills
GitHub Statushttps://www.githubstatus.com/
Abouthttps://github.com/about
Partnershttps://github.com/partners
Changeloghttps://github.blog/changelog/
GitHub UniverseThe event for developers, by developers — talks, workshops, and what’s next for GitHub.https://githubuniverse.com/
Pricinghttps://github.com/pricing
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpurescript-lua%2Fpurescript-lua%2Fpull%2F350%2Ffiles
Sign uphttps://github.com/signup?ref_cta=Sign+up&ref_loc=header+logged+out&ref_page=%2F%3Cuser-name%3E%2F%3Crepo-name%3E%2Fpull_requests%2Fshow%2Ffiles&source=header-repo&source_repo=purescript-lua%2Fpurescript-lua
Reloadhttps://github.com/purescript-lua/purescript-lua/pull/350/files
Reloadhttps://github.com/purescript-lua/purescript-lua/pull/350/files
Reloadhttps://github.com/purescript-lua/purescript-lua/pull/350/files
purescript-luahttps://github.com/purescript-lua
purescript-luahttps://github.com/purescript-lua/purescript-lua
Codehttps://github.com/purescript-lua/purescript-lua
Issues48 (48)https://github.com/purescript-lua/purescript-lua/issues
Pull requestshttps://github.com/purescript-lua/purescript-lua/pulls
Discussionshttps://github.com/purescript-lua/purescript-lua/discussions
Actionshttps://github.com/purescript-lua/purescript-lua/actions
Projectshttps://github.com/purescript-lua/purescript-lua/projects
Security and qualityhttps://github.com/purescript-lua/purescript-lua/security
Insightshttps://github.com/purescript-lua/purescript-lua/insights
Sign up for GitHub https://github.com/signup?return_to=%2Fpurescript-lua%2Fpurescript-lua%2Fissues%2Fnew%2Fchoose
terms of servicehttps://docs.github.com/terms
privacy statementhttps://docs.github.com/privacy
Sign inhttps://github.com/login?return_to=%2Fpurescript-lua%2Fpurescript-lua%2Fissues%2Fnew%2Fchoose
Unisayhttps://github.com/Unisay
mainhttps://github.com/purescript-lua/purescript-lua/tree/main
issue-348/optimizer-fixpoint-livelockhttps://github.com/purescript-lua/purescript-lua/tree/issue-348/optimizer-fixpoint-livelock
Conversation 0 https://github.com/purescript-lua/purescript-lua/pull/350
Commits 2 https://github.com/purescript-lua/purescript-lua/pull/350/commits
Checks 2 https://github.com/purescript-lua/purescript-lua/pull/350/checks
Files changed https://github.com/purescript-lua/purescript-lua/pull/350/files
Please reload this pagehttps://github.com/purescript-lua/purescript-lua/pull/350/files
fix(ir): bound the bottom-up rewrite driver's re-application loop (#348) https://github.com/purescript-lua/purescript-lua/pull/350/files#top
Show all changes 2 commits https://github.com/purescript-lua/purescript-lua/pull/350/files
ffc3c5d test(ir): pin the optimizer against a term with no normal form (#348) Unisay Jul 29, 2026 https://github.com/purescript-lua/purescript-lua/pull/350/commits/ffc3c5dec657f092d21be78aaffabe72746bf9b0
ce91343 fix(ir): bound the bottom-up rewrite driver's re-application loop (#348) Unisay Jul 29, 2026 https://github.com/purescript-lua/purescript-lua/pull/350/commits/ce91343e5de0af481e5ee91aa9148c904dbf4af1
Clear filters https://github.com/purescript-lua/purescript-lua/pull/350/files
Please reload this pagehttps://github.com/purescript-lua/purescript-lua/pull/350/files
Please reload this pagehttps://github.com/purescript-lua/purescript-lua/pull/350/files
20260729_150000_unisay_bound_nested_rewrites.md https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-ff440e076969f0bda092b4226c5e0fc98f7127219d33cb0f2c1e15e7e9dd409a
Types.hs https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-c628fb950daac01f47dc80a039e24b8b452f9d578ab0d55483d10758027b4884
Spec.hs https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-241ea2421c606c31b9414fb386f9f4d1beb60055ed792935b393101edfd7b949
changelog.d/20260729_150000_unisay_bound_nested_rewrites.mdhttps://github.com/purescript-lua/purescript-lua/pull/350/files#diff-ff440e076969f0bda092b4226c5e0fc98f7127219d33cb0f2c1e15e7e9dd409a
View file https://github.com/purescript-lua/purescript-lua/blob/ce91343e5de0af481e5ee91aa9148c904dbf4af1/changelog.d/20260729_150000_unisay_bound_nested_rewrites.md
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/350/{{ revealButtonHref }}
lib/Language/PureScript/Backend/IR/Types.hshttps://github.com/purescript-lua/purescript-lua/pull/350/files#diff-c628fb950daac01f47dc80a039e24b8b452f9d578ab0d55483d10758027b4884
View file https://github.com/purescript-lua/purescript-lua/blob/ce91343e5de0af481e5ee91aa9148c904dbf4af1/lib/Language/PureScript/Backend/IR/Types.hs
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/350/{{ revealButtonHref }}
https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-c628fb950daac01f47dc80a039e24b8b452f9d578ab0d55483d10758027b4884
https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-c628fb950daac01f47dc80a039e24b8b452f9d578ab0d55483d10758027b4884
https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-c628fb950daac01f47dc80a039e24b8b452f9d578ab0d55483d10758027b4884
https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-c628fb950daac01f47dc80a039e24b8b452f9d578ab0d55483d10758027b4884
test/Language/PureScript/Backend/IR/Optimizer/Spec.hshttps://github.com/purescript-lua/purescript-lua/pull/350/files#diff-241ea2421c606c31b9414fb386f9f4d1beb60055ed792935b393101edfd7b949
View file https://github.com/purescript-lua/purescript-lua/blob/ce91343e5de0af481e5ee91aa9148c904dbf4af1/test/Language/PureScript/Backend/IR/Optimizer/Spec.hs
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/350/{{ revealButtonHref }}
https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-241ea2421c606c31b9414fb386f9f4d1beb60055ed792935b393101edfd7b949
https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-241ea2421c606c31b9414fb386f9f4d1beb60055ed792935b393101edfd7b949
https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-241ea2421c606c31b9414fb386f9f4d1beb60055ed792935b393101edfd7b949
https://github.com/purescript-lua/purescript-lua/pull/350/files#diff-241ea2421c606c31b9414fb386f9f4d1beb60055ed792935b393101edfd7b949
https://github.com
Termshttps://docs.github.com/site-policy/github-terms/github-terms-of-service
Privacyhttps://docs.github.com/site-policy/privacy-policies/github-privacy-statement
Securityhttps://github.com/security
Statushttps://www.githubstatus.com/
Communityhttps://github.community/
Docshttps://docs.github.com/
Contacthttps://support.github.com?tags=dotcom-footer

Viewport: width=device-width


URLs of crawlers that visited me.