Represent terms with an opaque data type
Nobody has claimed this yet.
- Dominant language
- Racket
- Stars
- 112
- Forks
- 42
- PR merge metrics
- No merged PRs in 30d
Description
Currently, Redex terms are stored as S-expressions. If we stored them as opaque values, destructurable only through pattern-matching, it would make possible some potentially important optimizations:
- caching the results of pattern-matching (this has the potential to improve the big-O of traversals)
- using Racket syntax objects to store the actual terms, enabling binding operations to use sets-of-scopes to perform mass renaming quickly (this should improve the big-O of traversals of syntax with binding)
Furthermore, it discourages the use of non-Redex operations on Redex terms. This is potentially a good thing, because many of the operations are unhygenic in surprising ways (for example equal? is not safe to use on terms in a language with binding).
The branch I linked above has significant progress towards this representation change (after which, implementing the above optimizations could be done in a local and contained fashion). I believe I've put the boundaries of the representation change in the right place, or almost the right place, and all of the unit tests pass, last I checked. Some models need to be updated; mainly to remove cases where they they treat terms as S-expressions.
However, once all of the example artifacts are updated, we can make this a largely backwards-compatible change. S-expressions should already be automatically coerced to terms, and (at least for a while, with the ability to opt-out) terms can be automatically coerced to S-expressions once they are put into the user's hands.
I was hoping to get this done myself (and I still might!), but I didn't want my progress to languish without at least making a couple notes here.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reviewing the linked new-representation branch and the existing unit tests, which the issue says currently pass. Then identify the example artifacts that still treat terms as S-expressions. Done means updating those artifacts and completing the representation change while preserving the described coercion behavior.
Written by the indexing model from the issue text.
Assessment
- Domain
- tooling
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 20/100