René's URL Explorer Experiment


Title: Choose case columns by Maranget's pbaN composite by Unisay · Pull Request #311 · purescript-lua/purescript-lua · GitHub

Open Graph Title: Choose case columns by Maranget's pbaN composite by Unisay · Pull Request #311 · purescript-lua/purescript-lua

X Title: Choose case columns by Maranget's pbaN composite by Unisay · Pull Request #311 · purescript-lua/purescript-lua

Description: Closes #237. mkCase compiles a PureScript case to a decision tree of nested if/else tests, choosing at every step which outstanding pattern test to emit next — a "column" here is a focused sub-value of a scrutinee (the scrutinee expression plus the projection steps into it). The chooser, matchChosenByHeuristic, used a single metric: pick the column tested by the most other clauses. This PR replaces that metric with the pbaN composite from Maranget's "Compiling Pattern Matching to Good Decision Trees" (ML 2008), adapted to the clause-per-row representation. Candidates are scored lexicographically: p — the number of consecutive clauses, starting from the current one, that test the column (a test every following clause needs cannot be wasted); b — fewest distinct patterns tested on the column across the remaining clauses (a column with fewer distinct tests is retired sooner); a — fewest sub-tests those patterns expose once passed; N — leftmost on full ties. Everything around the choice is untouched, including the MatchHistory pruning that skips tests whose outcome is already decided on a path. Where the metrics disagree, the composite emits a smaller tree. The new unit test (test/Language/PureScript/Backend/IR/Spec.hs, "tests the column with fewer distinct patterns first") compiles this five-clause matrix, where every clause tests both columns — so the old total-count metric ties (4 vs 4) and falls back to the left column — while pbaN sees four distinct patterns on column 1 against two on column 2 and tests column 2 first: case 'x', 'y' of 'a', 'p' -> 1 'b', 'p' -> 2 'c', 'p' -> 3 'd', 'p' -> 4 'a', 'q' -> 5 The pre-change compiler (captured by the test's red run before the fix) produces 9 tests — the column-2 test 'p' == 'y' is re-emitted inside every branch of the four-way column-1 chain: if 'a'=='x' then (if 'p'=='y' then 1 else if 'q'=='y' then 5 else fail) else if 'b'=='x' then (if 'p'=='y' then 2 else fail) else if 'c'=='x' then (if 'p'=='y' then 3 else fail) else if 'd'=='x' then (if 'p'=='y' then 4 else fail) else fail With pbaN the column-2 test runs once and the column-1 chain follows once per outcome — 8 tests (this is the tree the unit test asserts): if 'p'=='y' then (if 'a'=='x' then 1 else if 'b'=='x' then 2 else if 'c'=='x' then 3 else if 'd'=='x' then 4 else fail) else (if 'd'=='x' then fail else if 'a'=='x' then (if 'q'=='y' then 5 else fail) else fail) Across the golden corpus the change is a wash, which is the intended safety property: exactly one module moves, and only by an order swap with an identical test count. In Golden.CasePruning.Test's literalNegatives (1 1 -> 1; 2 2 -> 2; 1 2 -> 3; _ _ -> 4), once 1 == v has failed the remaining clauses only ever test the second scrutinee v1 against 2 (one distinct pattern) while the first scrutinee v still carries two, so pbaN retires v1 first — verbatim from the golden diff: - elseif 2 == v then - if 2 == v1 then return 2 else return 4 end + elseif 2 == v1 then + if 2 == v then return 2 else return 4 end Verification: the corpus eval goldens (hand-verified runtime-output oracles, never auto-accepted) pass unchanged, so only tree shape moved, not semantics; ./bench/ci reports bench counters match goldens, so the LuaJIT FNEW/TNEW censuses and trace reports over the linked bench artifacts are byte-identical; the full suite is green and the IR spec group was re-run 10 times with fresh seeds. Code-size delta across the corpus is zero lines.

Open Graph Description: Closes #237. mkCase compiles a PureScript case to a decision tree of nested if/else tests, choosing at every step which outstanding pattern test to emit next — a "column" here is a focuse...

X Description: Closes #237. mkCase compiles a PureScript case to a decision tree of nested if/else tests, choosing at every step which outstanding pattern test to emit next — a "column" here is ...

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

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:a23593d2-df8d-2237-1931-e0349691d61d
current-catalog-service-hashae870bc5e265a340912cde392f23dad3671a0a881730ffdadd82f2f57d81641b
request-id9BE2:1CEA6F:9CA0BB:D0FB75:6B00E599
html-safe-nonced9365b5c6adb9d334bd3a532635ecc4d6490341e5589bb9db9faba5aec62fcd9
visitor-payloadeyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI5QkUyOjFDRUE2Rjo5Q0EwQkI6RDBGQjc1OjZCMDBFNTk5IiwidmlzaXRvcl9pZCI6IjY5NTIyOTM5MTYzNjQzMDE3MjEiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ==
visitor-hmac0083b74356fffb4405aeda3b34aad180250dd84c2048e8b918fed7e0093851de
hovercard-subject-tagpull_request:4140428638
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/311/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 #237. mkCase compiles a PureScript case to a decision tree of nested if/else tests, choosing at every step which outstanding pattern test to emit next — a "column" here is a focuse...
og:site_nameGitHub
og:typeobject
hostnamegithub.com
expected-hostnamegithub.com
None27088b6977484d0d3321d9a11c907c6d6637b315cfa359ef7952dbf6292f9b14
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
release624179fb8b88d26ba5bba08894eb60a1c5a1d93d
ui-targetfull
theme-color#1e2327
color-schemelight dark

Links:

Skip to contenthttps://github.com/purescript-lua/purescript-lua/pull/311/files#start-of-content
https://github.com/
Sign inhttps://github.com/login?return_to=https%3A%2F%2Fgithub.com%2Fpurescript-lua%2Fpurescript-lua%2Fpull%2F311%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%2F311%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/311/files
Reloadhttps://github.com/purescript-lua/purescript-lua/pull/311/files
Reloadhttps://github.com/purescript-lua/purescript-lua/pull/311/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-237/pban-column-heuristichttps://github.com/purescript-lua/purescript-lua/tree/issue-237/pban-column-heuristic
Conversation 0 https://github.com/purescript-lua/purescript-lua/pull/311
Commits 1 https://github.com/purescript-lua/purescript-lua/pull/311/commits
Checks 2 https://github.com/purescript-lua/purescript-lua/pull/311/checks
Files changed https://github.com/purescript-lua/purescript-lua/pull/311/files
Please reload this pagehttps://github.com/purescript-lua/purescript-lua/pull/311/files
Choose case columns by Maranget's pbaN composite https://github.com/purescript-lua/purescript-lua/pull/311/files#top
Show all changes 1 commit https://github.com/purescript-lua/purescript-lua/pull/311/files
277913f feat(ir): choose case columns by Maranget's pbaN composite Unisay Jul 27, 2026 https://github.com/purescript-lua/purescript-lua/pull/311/commits/277913f40d88ec427d772deba882115928766478
Clear filters https://github.com/purescript-lua/purescript-lua/pull/311/files
Please reload this pagehttps://github.com/purescript-lua/purescript-lua/pull/311/files
Please reload this pagehttps://github.com/purescript-lua/purescript-lua/pull/311/files
20260727_100000_unisay_pban_column_heuristic.md https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-5c1f753bc3e4e717a885f8e868b7f701428fb179263b1ce07953a96b11944f55
IR.hs https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-b2e6467526a4a74dfd4d619dae7237fb05d5ad4386d4f8a893d4f82b4c31cd39
Spec.hs https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-edf87e4278f1d402b5fa79b30b8cc39979fe6db9af8cd7afaa5c09dadced0e4e
golden.ir https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-90b270fb0c575ad63be2d3a34d6f490c96c8f6b0536069fb79a97c918d69da98
golden.lua https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-3dbcfad1e19a11d68f5041cfd1b9d50c09eacb7a6255757ee2f716b8fb1d8e0c
changelog.d/20260727_100000_unisay_pban_column_heuristic.mdhttps://github.com/purescript-lua/purescript-lua/pull/311/files#diff-5c1f753bc3e4e717a885f8e868b7f701428fb179263b1ce07953a96b11944f55
View file https://github.com/purescript-lua/purescript-lua/blob/277913f40d88ec427d772deba882115928766478/changelog.d/20260727_100000_unisay_pban_column_heuristic.md
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/311/{{ revealButtonHref }}
lib/Language/PureScript/Backend/IR.hshttps://github.com/purescript-lua/purescript-lua/pull/311/files#diff-b2e6467526a4a74dfd4d619dae7237fb05d5ad4386d4f8a893d4f82b4c31cd39
View file https://github.com/purescript-lua/purescript-lua/blob/277913f40d88ec427d772deba882115928766478/lib/Language/PureScript/Backend/IR.hs
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/311/{{ revealButtonHref }}
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-b2e6467526a4a74dfd4d619dae7237fb05d5ad4386d4f8a893d4f82b4c31cd39
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-b2e6467526a4a74dfd4d619dae7237fb05d5ad4386d4f8a893d4f82b4c31cd39
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-b2e6467526a4a74dfd4d619dae7237fb05d5ad4386d4f8a893d4f82b4c31cd39
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-b2e6467526a4a74dfd4d619dae7237fb05d5ad4386d4f8a893d4f82b4c31cd39
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-b2e6467526a4a74dfd4d619dae7237fb05d5ad4386d4f8a893d4f82b4c31cd39
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-b2e6467526a4a74dfd4d619dae7237fb05d5ad4386d4f8a893d4f82b4c31cd39
test/Language/PureScript/Backend/IR/Spec.hshttps://github.com/purescript-lua/purescript-lua/pull/311/files#diff-edf87e4278f1d402b5fa79b30b8cc39979fe6db9af8cd7afaa5c09dadced0e4e
View file https://github.com/purescript-lua/purescript-lua/blob/277913f40d88ec427d772deba882115928766478/test/Language/PureScript/Backend/IR/Spec.hs
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/311/{{ revealButtonHref }}
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-edf87e4278f1d402b5fa79b30b8cc39979fe6db9af8cd7afaa5c09dadced0e4e
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-edf87e4278f1d402b5fa79b30b8cc39979fe6db9af8cd7afaa5c09dadced0e4e
test/ps/output/Golden.CasePruning.Test/golden.irhttps://github.com/purescript-lua/purescript-lua/pull/311/files#diff-90b270fb0c575ad63be2d3a34d6f490c96c8f6b0536069fb79a97c918d69da98
View file https://github.com/purescript-lua/purescript-lua/blob/277913f40d88ec427d772deba882115928766478/test/ps/output/Golden.CasePruning.Test/golden.ir
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/311/{{ revealButtonHref }}
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-90b270fb0c575ad63be2d3a34d6f490c96c8f6b0536069fb79a97c918d69da98
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-90b270fb0c575ad63be2d3a34d6f490c96c8f6b0536069fb79a97c918d69da98
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-90b270fb0c575ad63be2d3a34d6f490c96c8f6b0536069fb79a97c918d69da98
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-90b270fb0c575ad63be2d3a34d6f490c96c8f6b0536069fb79a97c918d69da98
test/ps/output/Golden.CasePruning.Test/golden.luahttps://github.com/purescript-lua/purescript-lua/pull/311/files#diff-3dbcfad1e19a11d68f5041cfd1b9d50c09eacb7a6255757ee2f716b8fb1d8e0c
View file https://github.com/purescript-lua/purescript-lua/blob/277913f40d88ec427d772deba882115928766478/test/ps/output/Golden.CasePruning.Test/golden.lua
Open in desktop https://desktop.github.com
https://github.co/hiddenchars
https://github.com/purescript-lua/purescript-lua/pull/311/{{ revealButtonHref }}
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-3dbcfad1e19a11d68f5041cfd1b9d50c09eacb7a6255757ee2f716b8fb1d8e0c
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-3dbcfad1e19a11d68f5041cfd1b9d50c09eacb7a6255757ee2f716b8fb1d8e0c
https://github.com/purescript-lua/purescript-lua/pull/311/files#diff-3dbcfad1e19a11d68f5041cfd1b9d50c09eacb7a6255757ee2f716b8fb1d8e0c
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.