Finite Domains and Exclusions as First-Class Citizens 
Author Message
 Finite Domains and Exclusions as First-Class Citizens

A recent RELFUN extension permits finite domains (generally, 'types')
as VALUES of variables, giving them a full 'first-class' status.  The
separate type and value slots of 'destructive-assignment' (procedural)
languages are thus joined in 'specializing-assignment' (LP) languages:

procedural variable                     logical variable  --  type/value

For example, an initial

X is dom[a,b,c], ...   % assign the finite domain containing a, b, c to X

makes the domain act both as the X value (allowed as/in an intensional
answer) and as the X type (constraining possible further unifications).
Extending the conjunction,

..., X is d            % try to assign d to X

fails (since d is not in the 'enumeration type' {a,b,c}), while

..., X is dom[c,d]     % try to assign the finite domain of {c,d} to X

specializes the domain value of X to the ordinary value c (the
intersection result of the two domains, normalized via dom[c] = c).

For obtaining the below report, please email me your snail address.


Languages based on logical variables can regard finite domains, finite
exclusions, and, generally, types as values.  Like a variable can be
bound to a non-ground structure which can be later specialized through
in-place assignment of some inner variables, it can also be bound to,
say, a domain structure which can be specialized later through
`in-place deletion' of some of its elements (e.g. by intersection with
other domain structures).  While finite domains prescribe the elements
of a disjunctive structure, the complementary finite exclusions forbid
the elements of a conjunctive structure. Domains and exclusions can be
values of variables or occur inside clauses as/in terms or within an
occurrence-binding construct (useful to name arbitrary terms).  In a
relational-functional language (e.g., RELFUN) they can also be
returned as values of functions. Altogether, domains and exclusions
become first-class citizens. Because they are completely handled by an
extended unification routine, they do not require delay techniques
needed in (more expressive) constraint systems. Still, their
backtracking-superseding `closed' representation leads to smaller
proof trees (efficiency), and abstracted, intensional answers
(readability).  Anti-unification (for generalization) exchanges the
roles of domains and exclusions.  The operational semantics of
domains, exclusions, and occurrence bindings is specified by a RELFUN
meta-unify function (and implemented in pure LISP).

AUTHOR             = {Harold Boley},
TITLE              = {{Finite Domains and Exclusions as First-Class Citizens}},
BOOKTITLE          = {Fourth International Workshop on
Extensions of Logic Programming,
St. Andrews, Scotland, March 1993, Preprints and Proceedings},
EDITOR             = {Roy Dyckhoff},
NOTE               = {Also available as Research Report RR-94-07, Feb.\ 1994,
DFKI, P.\ O.\ Box 2080, D-67608 Kaisers\-lautern},
PUBLISHER          = {Springer},
SERIES             = {LNAI},
YEAR               = {1994}


Wed, 04 Sep 1996 01:58:37 GMT  
 [ 1 post ] 

 Relevant Pages 

1. Theorem Prover on Propositions in Finite Domains

2. seeking for Real or Finite Domains constraint solving algorithm in Prolog

3. Constraint Satisfaction Problems (CSP) w/ non-finite domains?

4. Finite Domain Problem

5. Finite domain constraint solver for LISP?...

6. Off topid: finite element vs finite volume

7. LSP and constructors with first-class classes

8. First class classes

9. simple finite state machine class

10. RDB-access classes in public domain?

11. Business Domain Class availability (2)

12. Business Domain Classes availability


Powered by phpBB® Forum Software