René's URL Explorer Experiment


Title: fix(ir): key a Let's binders in scope order in alphaKey (#349) by Unisay · Pull Request #353 · purescript-lua/purescript-lua · GitHub

Open Graph Title: fix(ir): key a Let's binders in scope order in alphaKey (#349) by Unisay · Pull Request #353 · purescript-lua/purescript-lua

X Title: fix(ir): key a Let's binders in scope order in alphaKey (#349) by Unisay · Pull Request #353 · purescript-lua/purescript-lua

Description: Closes #349. The bug Common-subexpression elimination (Language.PureScript.Backend.IR.CSE) finds repeated pure subexpressions in one function body and hoists them into a shared local binding. It decides what counts as a repeat by canonicalizing each candidate to a key: alphaKey drops annotations and renames every binder bound within the expression to a positional $key name, so — in the words of its own documentation — "two expressions have equal keys iff they are alpha-equivalent up to annotations". References that are free in the expression keep their own names, because they belong to the enclosing scope and two occurrences only mean the same thing if they name the same outer binder. Its Let case collected every binder name of the Let into one rename map up front, then canonicalized all the right-hand sides under that single map: Let ann binds body → do -- Under unique binders no Let name can be referenced before it is -- bound, so all the groupings can enter the rename map up front. renames' ← foldlM ( \rs name → do name' ← mint pure (Map.insert name name' rs) ) renames (filter (/= discardName) (bindingNames =<< toList binds)) The IR's scoping rule is where that shortcut fails. Note [Sequential scoping of Let bindings] fixes Let scoping as sequential, like Scheme's let*: a Standalone binding (the IR's non-recursive grouping, as opposed to a RecursiveGroup) does not have its own name in scope in its right-hand side, so a reference to that name from its own right-hand side resolves to an outer binder. Because the binder's map entry was already present when its own right-hand side was walked, a free reference sharing that name got canonicalized as if it were bound. The stated iff then breaks in the "misses an equality" direction. Take two expressions in a scope that already binds x: let x = x in x -- binds a fresh name to the outer x, returns it let y = x in y -- the same thing, under a different binder name They are alpha-equivalent — they differ only in the name chosen for the binder, and the right-hand-side x is a free occurrence of the same outer binder in both. alphaEq, the IR's alpha-equivalence relation, agrees. alphaKey did not (this block and the one at the end of the next section are verbatim GHCi output, before and after the fix): alphaEq a b = True alphaKey a == b = False keyA = Let () (Standalone ((),Name "$key0",Ref () (Local (Name "$key0"))) :| []) (Ref () (Local (Name "$key0"))) keyB = Let () (Standalone ((),Name "$key0",Ref () (Local (Name "x"))) :| []) (Ref () (Local (Name "$key0"))) In keyA the free x had been swallowed into the positional namespace as $key0; in keyB the identical free reference correctly survived as x. The fix The map is now threaded through the groupings instead of hoisted, which is the shape freshenBinders (the traversal that alpha-renames an expression's binders before a copy of it is pasted elsewhere) and the LetValues case of alphaKey itself already use: -- The groupings bind sequentially, so the map grows left to right. Let ann binds body → do (renames', binds') ← mapAccumM keyGrouping renames binds Let ann binds' <$> go renames' body keyGrouping splits on the grouping kind, so each right-hand side is canonicalized under exactly the map that is in scope for it: -- A Standalone binding is non-recursive: its RHS does not see its -- own binder, so the RHS is canonicalized under the incoming map and -- the binder enters only afterwards. A RHS reference sharing the -- binder's name is therefore an occurrence of an outer binder and -- keeps its name, as it must. Standalone (bindAnn, name, expr) → do expr' ← go renames expr (renames', name') ← bindMinted renames name pure (renames', Standalone (bindAnn, name', expr')) -- Every member of a recursive group is in scope in every member's -- RHS, so the whole group enters the map before any RHS is walked. RecursiveGroup members → do The discard binder _ keeps its exemption, now in bindMinted: it is exempt from the IR's binder-uniqueness invariant, so one Let can bind it several times (magic-do's discard statements), and nothing may reference it, so it takes no positional name: bindMinted ∷ Map Name Name → Name → State Natural (Map Name Name, Name) bindMinted rs name | name == discardName = pure (rs, name) The two expressions now key equally, matching alphaEq: alphaKey a == b = True keyA = Let () (Standalone ((),Name "$key0",Ref () (Local (Name "x"))) :| []) (Ref () (Local (Name "$key0"))) keyB = Let () (Standalone ((),Name "$key0",Ref () (Local (Name "x"))) :| []) (Ref () (Local (Name "$key0"))) Test Red first, at the level the bug manifests: two lambdas that differ only in a Let binder name are one alpha-equivalence class, so CSE must hoist them into one shared $cse0 binding. Wrapping each in a lambda is what makes it a candidate — lambda literals are one of the pass's effect-free candidate classes, a bare Let is not. it "hoists Lets whose Standalone RHS references an outer binder (#349)" do let shadowing name = abstraction (paramNamed (Name "$p")) $ lets (pure (Standalone (noAnn, Name name, refLocal (Name "x")))) (refLocal (Name name)) expr = application (application f (shadowing "x")) (shadowing "y") expected = lets (pure (bind0 (shadowing "x"))) (application (application f cse0) cse0) cseExpression expr `shouldBe` expected Verbatim failure on the parent commit — the pass returned the input unchanged, declining the hoist: 1) CSE hoists Lets whose Standalone RHS references an outer binder (#349) expected: Let Nothing (Standalone (Nothing, Name "$cse0", AbsN Nothing (ParamNamed Nothing (Name "$p") :| []) (Let Nothing (Standalone (Nothing, Name "x", Ref Nothing (Local (Name "x"))) :| []) (Ref Nothing (Local (Name "x"))))) :| []) (AppN Nothing (AppN Nothing (Ref Nothing (Local (Name "f"))) (Ref Nothing (Local (Name "$cse0")) :| [])) (Ref Nothing (Local (Name "$cse0")) :| [])) but got: AppN Nothing (AppN Nothing (Ref Nothing (Local (Name "f"))) (AbsN Nothing (ParamNamed Nothing (Name "$p") :| []) (Let Nothing (Standalone (Nothing, Name "x", Ref Nothing (Local (Name "x"))) :| []) (Ref Nothing (Local (Name "x")))) :| [])) (AbsN Nothing (ParamNamed Nothing (Name "$p") :| []) (Let Nothing (Standalone (Nothing, Name "y", Ref Nothing (Local (Name "x"))) :| []) (Ref Nothing (Local (Name "y")))) :| []) A second test pins the contrasting branch, which the fix must not disturb: a RecursiveGroup member's right-hand side does see its own binder, so two self-referencing groups differing only in the member name are alpha-equivalent and must still be shared. It is green on both sides of the fix — it guards the branch the rewrite introduces. The existing property CSE / keys alpha-equivalent expressions equally cannot catch any of this: it draws generated expressions and uniquifies them, so it never presents a shadowed shape. Impact on emitted code: none The golden corpus is byte-identical — no golden.ir or golden.lua moved — which is the check that no CSE decision depended on the hoisted behaviour. Two independent reasons: The direction of the bug was safe. A shadowed right-hand side keyed to a shape correct canonicalization can never emit for a Standalone binding, namely a reference to the binder's own positional name inside the binder's own right-hand side. So the bug could only make two alpha-equivalent expressions key differently — CSE declining a hoist it could have made — and never merge two occurrences that mean different things. And it did not fire at all. uniquifyNames is the pipeline's entry pass, and every pass behind it, CSE included, declares passRequires = guc — the global-uniqueness condition, under which every binder in the program has a distinct name and no free reference can collide with one. What the fix buys is that alphaKey no longer depends on that condition for correct name resolution. It was the last name-resolving traversal in the IR that did not implement the sequential rule; freshenBinders was the same bug (#345, fixed in #347). A pass reordering that puts CSE ahead of uniquification, or a property fed deliberately non-uniquified input the way IR Optimizer / inlines expressions referenced once is, would turn a latent divergence into a visible one. The module's == GUC section and alphaKey's documentation are updated to say what GUC is still load-bearing for (the exactness of the hoist-point scope guard) and what it no longer is. Verification cabal test all green — 1236 examples, 0 failures — with no golden churn. fourmolu and hlint clean; the two touched modules recompile with no warnings. The Hedgehog-driven groups were stressed with fresh seeds: --match "CSE" and --match "IR Optimizer", 12 runs each, all green.

Open Graph Description: Closes #349. The bug Common-subexpression elimination (Language.PureScript.Backend.IR.CSE) finds repeated pure subexpressions in one function body and hoists them into a shared local binding. It de...

X Description: Closes #349. The bug Common-subexpression elimination (Language.PureScript.Backend.IR.CSE) finds repeated pure subexpressions in one function body and hoists them into a shared local binding. It de...

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

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:60b3e410-99e3-f439-a03c-9948b728998d
current-catalog-service-hashae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b
request-idD67A:3A4875:758BD5:9E1508:6B00DBBA
html-safe-nonce9f2a559d2fbd6d91115c7331c6042f68b943f248ea6550d4ea4824c4e61c2f78
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiJENjdBOjNBNDg3NTo3NThCRDU6OUUxNTA4OjZCMDBEQkJBIiwidmlzaXRvcl9pZCI6IjUyMTc4OTg0NDkwNzIwODU5NDYiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ==
visitor-hmac2878dcda7e44dfb086ee6ff19224dc9e4281f7b5a1ec0ea513d160fb610d22e4
hovercard-subject-tagpull_request:4160030299
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/353/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 #349. The bug Common-subexpression elimination (Language.PureScript.Backend.IR.CSE) finds repeated pure subexpressions in one function body and hoists them into a shared local binding. It de...
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/353/files#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpurescript-lua%2Fpurescript-lua%2Fpull%2F353%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%2F353%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/353/files
Reloadhttps://github.com/purescript-lua/purescript-lua/pull/353/files
Reloadhttps://github.com/purescript-lua/purescript-lua/pull/353/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-349/alphakey-sequential-scopinghttps://github.com/purescript-lua/purescript-lua/tree/issue-349/alphakey-sequential-scoping
Conversation 0 https://github.com/purescript-lua/purescript-lua/pull/353
Commits 2 https://github.com/purescript-lua/purescript-lua/pull/353/commits
Checks 2 https://github.com/purescript-lua/purescript-lua/pull/353/checks
Files changed https://github.com/purescript-lua/purescript-lua/pull/353/files
Please reload this pagehttps://github.com/purescript-lua/purescript-lua/pull/353/files
fix(ir): key a Let's binders in scope order in alphaKey (#349) https://github.com/purescript-lua/purescript-lua/pull/353/files#top
Show all changes 2 commits https://github.com/purescript-lua/purescript-lua/pull/353/files
75e92b0 test(ir): pin CSE against a Let shadowing its own binder (#349) Unisay Jul 29, 2026 https://github.com/purescript-lua/purescript-lua/pull/353/commits/75e92b009110d47d59a39b25eb2b2111c326b8bf
ba93054 fix(ir): key a Let's binders in scope order in alphaKey (#349) Unisay Jul 29, 2026 https://github.com/purescript-lua/purescript-lua/pull/353/commits/ba93054e437f7e1c33f7d24eb61c582272586917
Clear filters https://github.com/purescript-lua/purescript-lua/pull/353/files
Please reload this pagehttps://github.com/purescript-lua/purescript-lua/pull/353/files
Please reload this pagehttps://github.com/purescript-lua/purescript-lua/pull/353/files
20260729_170000_unisay_cse_alpha_key_scope_order.md https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-bfcf889a9b4cf346d49a22596ffeaab316ba516c1ba81f5dae1881ecb19dabbd
CSE.hs https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-6be6a9f2640687d94599e51891cd330b71f17b84ce95090a902d96d1c5399cd6
Spec.hs https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-d8e60bc4e21fc8a9d8acd073744a8f0517fcfe5cf18722a5e1ac774381d12bfd
changelog.d/20260729_170000_unisay_cse_alpha_key_scope_order.mdhttps://github.com/purescript-lua/purescript-lua/pull/353/files#diff-bfcf889a9b4cf346d49a22596ffeaab316ba516c1ba81f5dae1881ecb19dabbd
View file https://github.com/purescript-lua/purescript-lua/blob/ba93054e437f7e1c33f7d24eb61c582272586917/changelog.d/20260729_170000_unisay_cse_alpha_key_scope_order.md
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/353/{{ revealButtonHref }}
lib/Language/PureScript/Backend/IR/CSE.hshttps://github.com/purescript-lua/purescript-lua/pull/353/files#diff-6be6a9f2640687d94599e51891cd330b71f17b84ce95090a902d96d1c5399cd6
View file https://github.com/purescript-lua/purescript-lua/blob/ba93054e437f7e1c33f7d24eb61c582272586917/lib/Language/PureScript/Backend/IR/CSE.hs
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/353/{{ revealButtonHref }}
https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-6be6a9f2640687d94599e51891cd330b71f17b84ce95090a902d96d1c5399cd6
https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-6be6a9f2640687d94599e51891cd330b71f17b84ce95090a902d96d1c5399cd6
https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-6be6a9f2640687d94599e51891cd330b71f17b84ce95090a902d96d1c5399cd6
https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-6be6a9f2640687d94599e51891cd330b71f17b84ce95090a902d96d1c5399cd6
https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-6be6a9f2640687d94599e51891cd330b71f17b84ce95090a902d96d1c5399cd6
https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-6be6a9f2640687d94599e51891cd330b71f17b84ce95090a902d96d1c5399cd6
test/Language/PureScript/Backend/IR/CSE/Spec.hshttps://github.com/purescript-lua/purescript-lua/pull/353/files#diff-d8e60bc4e21fc8a9d8acd073744a8f0517fcfe5cf18722a5e1ac774381d12bfd
View file https://github.com/purescript-lua/purescript-lua/blob/ba93054e437f7e1c33f7d24eb61c582272586917/test/Language/PureScript/Backend/IR/CSE/Spec.hs
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/353/{{ revealButtonHref }}
https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-d8e60bc4e21fc8a9d8acd073744a8f0517fcfe5cf18722a5e1ac774381d12bfd
https://github.com/purescript-lua/purescript-lua/pull/353/files#diff-d8e60bc4e21fc8a9d8acd073744a8f0517fcfe5cf18722a5e1ac774381d12bfd
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.