René's URL Explorer Experiment


Title: CSE alphaKey hoists a Let's binders into its rename map, missing alpha-equivalent keys · Issue #349 · purescript-lua/purescript-lua · GitHub

Open Graph Title: CSE alphaKey hoists a Let's binders into its rename map, missing alpha-equivalent keys · Issue #349 · purescript-lua/purescript-lua

X Title: CSE alphaKey hoists a Let's binders into its rename map, missing alpha-equivalent keys · Issue #349 · purescript-lua/purescript-lua

Description: Problem Common-subexpression elimination groups repeated expressions by a canonical key. alphaKey in Language.PureScript.Backend.IR.CSE computes that key: it drops annotations and renames every binder bound within the expression to a pos...

Open Graph Description: Problem Common-subexpression elimination groups repeated expressions by a canonical key. alphaKey in Language.PureScript.Backend.IR.CSE computes that key: it drops annotations and renames every bin...

X Description: Problem Common-subexpression elimination groups repeated expressions by a canonical key. alphaKey in Language.PureScript.Backend.IR.CSE computes that key: it drops annotations and renames every bin...

Opengraph URL: https://github.com/purescript-lua/purescript-lua/issues/349

X: @github

direct link

Domain: github.com


Hey, it has json ld scripts:
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"CSE alphaKey hoists a Let's binders into its rename map, missing alpha-equivalent keys","articleBody":"## Problem\n\nCommon-subexpression elimination groups repeated expressions by a canonical key. `alphaKey` in `Language.PureScript.Backend.IR.CSE` computes that key: it drops annotations and renames every binder bound *within* the expression to a positional `$key\u003cn>` name, so — in the words of its own Haddock — \"two expressions have equal keys iff they are alpha-equivalent up to annotations\". Free references 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.\n\nIts `Let` case collects every binder name of the `Let` into one rename map up front and then canonicalizes all the right-hand sides under that single map:\n\n```haskell\n    Let ann binds body → do\n      -- Under unique binders no Let name can be referenced before it is\n      -- bound, so all the groupings can enter the rename map up front.\n      renames' ←\n        foldlM\n          ( \\rs name → do\n              name' ← mint\n              pure (Map.insert name name' rs)\n          )\n          renames\n          (filter (/= discardName) (bindingNames =\u003c\u003c toList binds))\n      let renameBound (bindAnn, name, expr) =\n            (bindAnn,Map.findWithDefault name name renames',)\n              \u003c$> go renames' expr\n      Let ann \u003c$> traverse (traverse renameBound) binds \u003c*> go renames' body\n```\n\nThat is the exact shape #345 fixed in `freshenBinders`, the traversal that alpha-renames an expression's binders before a copy of it is pasted elsewhere — down to the wording of the comment, which until #347 ended `(as in 'freshenBinders')`. The comment names the precondition the shortcut needs, and the IR's scoping rule is where it fails. `Note [Sequential scoping of Let bindings]` says a `Standalone` binding is non-recursive: its own name is **not** 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 is already present when its own right-hand side is walked, a *free* reference sharing that name is canonicalized as if it were bound.\n\nThe iff then breaks in the \"misses an equality\" direction. Take two expressions in a scope that already binds `x`:\n\n```\nlet x = x in x     -- binds a fresh name to the outer x, returns it\nlet y = x in y     -- the same thing, under a different binder name\n```\n\nThey 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` agrees. `alphaKey` does not:\n\n```\nalphaEq A B     = True\nalphaKey A == B = False\nkeyA = Let () (Standalone ((),Name \"$key0\",Ref () (Local (Name \"$key0\"))) :| []) (Ref () (Local (Name \"$key0\")))\nkeyB = Let () (Standalone ((),Name \"$key0\",Ref () (Local (Name \"x\"))) :| []) (Ref () (Local (Name \"$key0\")))\n```\n\nIn `keyA` the free `x` has been swallowed into the positional namespace as `$key0`; in `keyB` the identical free reference correctly survives as `x`.\n\n## Impact\n\nOnly in the safe direction, and only on input the compiler does not currently produce.\n\nThe direction matters, so it is worth being explicit: a shadowed right-hand side maps to a key shape that correct canonicalization can never emit for a `Standalone` binding, namely a reference to the binder's own positional name in the binder's own right-hand side. So the bug can only make two alpha-equivalent expressions key differently — CSE declines a hoist it could have made — and never the reverse. It cannot merge two occurrences that mean different things.\n\nAnd it does not fire today, for the same reason #345 had no effect on emitted code: `uniquifyNames` is the pipeline's entry pass and the only one whose stated precondition is merely `wellScoped`; 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.\n\nWhat makes it worth closing anyway is that `alphaKey` is now the last name-resolving traversal in the IR that does not implement the sequential rule. `Note [Sequential scoping of Let bindings]` lists the traversals that must agree — `countFreeRefs`, `alphaEq`, the well-scopedness lint, `qualifyTopRefs`, `uniquifyNamesInExpr` — and `freshenBinders` joined them in #347. A pass reordering that puts CSE ahead of uniquification, or a property fed deliberately non-uniquified generated input the way `IR Optimizer / inlines expressions referenced once` is, turns a latent divergence into a visible one.\n\n## Approach\n\nThe same change #347 made to `freshenBinders`: thread the map through the groupings instead of hoisting it. A `Standalone` right-hand side is canonicalized under the incoming map and only then does its binder enter; a `RecursiveGroup`'s members all enter before any of their right-hand sides is walked.\n\n```haskell\n    Let ann binds body → do\n      (renames', binds') ← mapAccumM keyGrouping renames binds\n      Let ann binds' \u003c$> go renames' body\n```\n\n`freshenBinders` after #347 is the working reference for both the grouping helper and the discard-binder exemption, which must survive here too: `_` is exempt from the uniqueness invariant, one `Let` can bind it several times, and nothing references it, so it takes no rename. The `LetValues` case of `alphaKey` already threads correctly and needs no change.\n\n## Verification\n\nThe change is a no-op on globally-unique input, where the two orders agree, so the golden corpus should stay byte-identical — that is the check that no CSE decision depended on the hoisted behaviour. The existing CSE property `keys alpha-equivalent expressions equally` restricts itself to input the generators uniquify, so it cannot catch this; the red-first test is the pair above, which must key equally and currently does not.\n\n## Prerequisites / Relations\n\nIndependent. #345 is the same bug in `freshenBinders`, fixed by #347, which carries the reasoning and the shape of the fix; this was surfaced while implementing it.\n\n## Acceptance criteria\n\n- `let x = x in x` and `let y = x in y` receive equal `alphaKey` values, matching `alphaEq`.\n- A `Standalone` right-hand side is canonicalized before its own binder enters the map; a `RecursiveGroup`'s members all enter before any of theirs.\n- The discard binder `_` remains unrenamed and out of the map.\n","author":{"url":"https://github.com/Unisay","@type":"Person","name":"Unisay"},"datePublished":"2026-07-29T09:26:56Z","url":"https://github.com/purescript-lua/purescript-lua/issues/349"}

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/_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format)
route-controllervoltron_issues_fragments
route-actionissue_layout
fetch-noncev2:09b6be3a-079b-5e41-e33c-0c6ec5d82b3d
current-catalog-service-hash81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114
request-id8242:11EACE:7209B8:9A814F:6B00DB6F
html-safe-nonce00693a0a31fd2040d800c88b249b9226dba8b0628f838dcb37ce79fdd62e1322
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI4MjQyOjExRUFDRTo3MjA5Qjg6OUE4MTRGOjZCMDBEQjZGIiwidmlzaXRvcl9pZCI6IjQ1MDM5NTY3ODU3NjExNDc3NTkiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ==
visitor-hmac1c387956c1108baf7b3042fcf994b55b61de0277fd35eebd90921acd6403e6ba
hovercard-subject-tagissue:5007653905
github-keyboard-shortcutsrepository,issues,copilot
google-site-verificationApib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I
octolytics-urlhttps://collector.github.com/github/collect
analytics-location///voltron/issues_fragments/issue_layout
fb:app_id1401488693436528
apple-itunes-appapp-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/purescript-lua/purescript-lua/349/issue_layout
twitter:imagehttps://opengraph.githubassets.com/33065e68185df949e8984e3c91f038269d03de36c850596a33c40c21f9987892/purescript-lua/purescript-lua/issues/349
twitter:cardsummary_large_image
og:imagehttps://opengraph.githubassets.com/33065e68185df949e8984e3c91f038269d03de36c850596a33c40c21f9987892/purescript-lua/purescript-lua/issues/349
og:image:altProblem Common-subexpression elimination groups repeated expressions by a canonical key. alphaKey in Language.PureScript.Backend.IR.CSE computes that key: it drops annotations and renames every bin...
og:image:width1200
og:image:height600
og:site_nameGitHub
og:typeobject
og:author:usernameUnisay
hostnamegithub.com
expected-hostnamegithub.com
None043c3f30fbcbe2c6c8e729e10cbbbc90c406546f9fbbb67c648d38f6b7d16daf
turbo-cache-controlno-preview
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
disable-turbofalse
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
react-app-nameissues

Links:

Skip to contenthttps://github.com/purescript-lua/purescript-lua/issues/349#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpurescript-lua%2Fpurescript-lua%2Fissues%2F349
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%2Fissues%2F349
Sign uphttps://github.com/signup?ref_cta=Sign+up&ref_loc=header+logged+out&ref_page=%2F%3Cuser-name%3E%2F%3Crepo-name%3E%2Fvoltron%2Fissues_fragments%2Fissue_layout&source=header-repo&source_repo=purescript-lua%2Fpurescript-lua
Reloadhttps://github.com/purescript-lua/purescript-lua/issues/349
Reloadhttps://github.com/purescript-lua/purescript-lua/issues/349
Reloadhttps://github.com/purescript-lua/purescript-lua/issues/349
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
https://github.com/purescript-lua/purescript-lua
New issuehttps://github.com/login?return_to=https://github.com/purescript-lua/purescript-lua/issues/349
New issuehttps://github.com/login?return_to=https://github.com/purescript-lua/purescript-lua/issues/349
#353https://github.com/purescript-lua/purescript-lua/pull/353
CSE alphaKey hoists a Let's binders into its rename map, missing alpha-equivalent keyshttps://github.com/purescript-lua/purescript-lua/issues/349#top
#353https://github.com/purescript-lua/purescript-lua/pull/353
area: irIR / optimizer / DCE / inlinerhttps://github.com/purescript-lua/purescript-lua/issues?q=state%3Aopen%20label%3A%22area%3A%20ir%22
bugSomething isn't workinghttps://github.com/purescript-lua/purescript-lua/issues?q=state%3Aopen%20label%3A%22bug%22
https://github.com/Unisay
Unisayhttps://github.com/Unisay
on Jul 29, 2026https://github.com/purescript-lua/purescript-lua/issues/349#issue-5007653905
#345https://github.com/purescript-lua/purescript-lua/issues/345
#347https://github.com/purescript-lua/purescript-lua/pull/347
#345https://github.com/purescript-lua/purescript-lua/issues/345
#347https://github.com/purescript-lua/purescript-lua/pull/347
#347https://github.com/purescript-lua/purescript-lua/pull/347
#347https://github.com/purescript-lua/purescript-lua/pull/347
#345https://github.com/purescript-lua/purescript-lua/issues/345
#347https://github.com/purescript-lua/purescript-lua/pull/347
Unisayhttps://github.com/Unisay
bugSomething isn't workinghttps://github.com/purescript-lua/purescript-lua/issues?q=state%3Aopen%20label%3A%22bug%22
area: irIR / optimizer / DCE / inlinerhttps://github.com/purescript-lua/purescript-lua/issues?q=state%3Aopen%20label%3A%22area%3A%20ir%22
on Jul 29, 2026https://github.com/purescript-lua/purescript-lua/issues/349#event-28650166281
Unisayhttps://github.com/Unisay
on Jul 29, 2026https://github.com/purescript-lua/purescript-lua/issues/349#event-28656961367
fix(ir): key a Let's binders in scope order in alphaKey (#349)https://github.com/purescript-lua/purescript-lua/commit/ba93054e437f7e1c33f7d24eb61c582272586917
#349https://github.com/purescript-lua/purescript-lua/issues/349
ba93054https://github.com/purescript-lua/purescript-lua/commit/ba93054e437f7e1c33f7d24eb61c582272586917
https://github.com/Unisay
Unisayhttps://github.com/Unisay
on Jul 29, 2026https://github.com/purescript-lua/purescript-lua/issues/349#issuecomment-5117775174
#347https://github.com/purescript-lua/purescript-lua/pull/347
Unisayhttps://github.com/Unisay
on Jul 29, 2026https://github.com/purescript-lua/purescript-lua/issues/349#event-28660512307
Merge pull request #353 from purescript-lua/issue-349/alphakey-sequen…https://github.com/purescript-lua/purescript-lua/commit/bbbcd6270c84d8eb68dda90b77429336c99786a7
#353https://github.com/purescript-lua/purescript-lua/pull/353
bbbcd62https://github.com/purescript-lua/purescript-lua/commit/bbbcd6270c84d8eb68dda90b77429336c99786a7
Unisayhttps://github.com/Unisay
completedhttps://github.com/purescript-lua/purescript-lua/issues?q=is%3Aissue%20state%3Aclosed%20archived%3Afalse%20reason%3Acompleted
#353https://github.com/purescript-lua/purescript-lua/pull/353
on Jul 29, 2026https://github.com/purescript-lua/purescript-lua/issues/349#event-28660512404
Sign up for freehttps://github.com/signup?return_to=https://github.com/purescript-lua/purescript-lua/issues/349
Sign in to commenthttps://github.com/login?return_to=https://github.com/purescript-lua/purescript-lua/issues/349
area: irIR / optimizer / DCE / inlinerhttps://github.com/purescript-lua/purescript-lua/issues?q=state%3Aopen%20label%3A%22area%3A%20ir%22
bugSomething isn't workinghttps://github.com/purescript-lua/purescript-lua/issues?q=state%3Aopen%20label%3A%22bug%22
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.