racket / racket/redex

Represent terms with an opaque data type

Open
#74 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Racket
Stars
112
Forks
42
PR merge metrics
No merged PRs in 30d

Description

Partial progress here

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.