Redex long tutorial beta-eta equivalence is false
Nobody has claimed this yet.
- Dominant language
- Racket
- Stars
- 112
- Forks
- 42
- PR merge metrics
- No merged PRs in 30d
Description
Consider the following term in the language of Lambda from https://docs.racket-lang.org/redex/redex2015.html : ((lambda () ((lambda (x) 1))) 2). This term is not beta-equivalent to anything, because it's stuck. But it is eta-equivalent to ((lambda (x) 1) 2) which beta-reduces to 1. So the statement in the tutorial
The βη semantics is equivalent to the β variant. Formulate this theorem as a metafunction. Use redex-check to test your theorem.
is wrong.
This error was found by random testing, here: http://drdr.racket-lang.org/69138/racket/share/pkgs/redex-doc/redex/scribblings/long-tut/code/lab-tue-mor.rkt
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
Read the long tutorial section containing the βη-equivalence statement and inspect redex-doc/redex/scribblings/long-tut/code/lab-tue-mor.rkt, where random testing found the counterexample. Verify the stated equivalence against the supplied stuck term and determine the corrected tutorial claim or test expectation. Done means the tutorial no longer presents this false theorem.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers, documentation
- Issue type
- Documentation
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100