This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
@@ -46,7 +46,14 @@ diamond property. Here is a counter example.
Both terms can reduce to `a a`, but the second term requires two steps
to get there, not one.
To side-step this problem, we'll define an auxiliary reduction
If we abstract this example, whenever `N —→ N'`,
we have two ways to reduce a term of the form `(λ x. M) N`:
(λ x. M) N —→ (λ x. M) N′
(λ x. M) N —→ M [ x := N ]
To bring these two reductions back together in a single step,
we'll define an auxiliary reduction
relation, called _parallel reduction_, that can perform many
reductions simultaneously and thereby satisfy the diamond property.
Furthermore, we show that a parallel reduction sequence exists between
Expand All
@@ -72,7 +79,50 @@ open import plfa.part2.Untyped
## Parallel Reduction
The parallel reduction relation is defined as follows.
The problem with the example above is that when we reduce
(λ x. M) N —→ M [ x := N ]
we make _two_ copies of `N`. That's why bringing the terms back
together requires two reduction steps, not one. Because `M` is `x x`,
M [ x := N ]
≡
N N
—→
N' N
—→
N' N'
Parallel reduction turns this sequence into a single step by allowing
both function and argument to be reduced in the same step:
N N ⇛ N' N'
To make reduction work in parallel, all that's needed is to change the
rule for reducing a term of the form `L · M`.
Ordinary reduction must reduce `L` _or_ `M`, but parallel reduction
may reduce both `L` _and_ `M`. Given a term `M [x := N ]`
where `N —→ N'`, parallel reduction can reduce every copy of `N`
in a single step.
Parallel reduction has one other fine point: in a term of the form
(λ x. M) N,
it may be that `M [x := N ]` contains _no_ copies of `N` (because `x`
does not occur free in `M`). In this case,
to match the reduction
(λ x. M) N —→ (λ x. M) N′
it must be possible for `M [x := N]` to parallel-reduce to itself.
(It is sufficient to allow a variable to parallel-reduce to itself;
the rest is taken care of by
structural rules for reducing abstractions and applications.)
Using these two ideas, reflexive reduction and simultaneous reduction,
the parallel-reduction relation is defined as follows.
```agda
infix 2 _⇛_
Expand Down
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
motivate and explain parallel reduction, plus wordsmithing #1020
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Are you sure you want to change the base?
Uh oh!
There was an error while loading. Please reload this page.
motivate and explain parallel reduction, plus wordsmithing #1020
Filter by extension
Viewed files
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
There are no files selected for viewing