[Haskell-cafe] Parallel term reduction
John D. Ramsdell
ramsdell0 at gmail.com
Mon Feb 2 18:22:38 EST 2009
> On Sun, Feb 1, 2009 at 9:26 PM, John D. Ramsdell <ramsdell0 at gmail.com>
>> I have a reduction system in which a rule takes a term and returns a
>> set of terms.
>> The reduction system creates a tree that originates at a starting
>> value called the root.
>> For most problems, the reduction system terminates, but a step count
>> limit protects
>> from non-termination.
> That's typically a bad idea. Instead, use laziness to protect from
> nontermination. For example, in this case, we can output a collection of
> items lazily, and then take a finite amount of the output (or check whether
> the output is longer than some length), without having to evaluate all of
Very good suggestion. In my code, I should "take limit" on the
generated list, and fail if the length of the list is limit. Sounds
I'll study your parallel solution tonight after work. Thank you.
Here is an interesting fact about my term reduction system. The
binary relation that defines reduction is slightly different from the
usual. It's a relation between terms and sets of terms. Furthermore,
some normal forms can be identified as answers, and some normal forms
are dead ends. When applying a rule, it doesn't matter which set in
the relation is used as the result. The answer normal forms will all
be the same. If the rule produces the empty set for some choice, all
other choices will lead only to normal forms that are dead ends.
More information about the Haskell-Cafe