From a declarative variant of Remy's algorithm for uniform random generation of binary trees, we derive a generalization to term algebras of an arbitrary signature. With trees seen as sets of edges connecting vert...
详细信息
ISBN:
(纸本)9781450351911
From a declarative variant of Remy's algorithm for uniform random generation of binary trees, we derive a generalization to term algebras of an arbitrary signature. With trees seen as sets of edges connecting vertices labeled with logic variables, we use Prolog's multiple-answer generation mechanism to derive a generic algorithm that counts terms of a given size, generates them all, or samples a random term given the signature of a term algebra. As applications, we implement generators for term algebras defining Motzkin trees, use all-term and random-term generation for mutual cross-testing and describe an extension mechanism that transforms a random sampler for Motzkin trees into one for closed lambda terms.
Constraint Handling Rules (CHR) is a committed-choice rule-based language that was originally intended for writing constraint solvers. In this paper we show that it is also possible to write the classic union-find alg...
详细信息
Constraint Handling Rules (CHR) is a committed-choice rule-based language that was originally intended for writing constraint solvers. In this paper we show that it is also possible to write the classic union-find algorithm and variants in CHR. The programs neither compromise in declarativeness nor efficiency. We study the time complexity of our programs: they match the almost-linear complexity of the best known imperative implementations. This fact is illustrated with experimental results.
暂无评论