Re: [Haskell-cafe] Parallel term reduction

On Sun, Feb 1, 2009 at 9:26 PM, John D. Ramsdell wrote:

...

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 it.

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 easy. 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. John