From: Harold Boley (boley@informatik.uni-kl.de)
Date: 06/06/03
Hi Pat, > Hi Harold, a few questions about your selector notation. We have been > thinking along similar lines for SCL, hence the details. If the > answers are published somewhere just point me at that. > > >Hi Sandro, > > > >> > In the example, the individual constant "5.0 percent" can be > >>analyzed as the > >> > cterm percent[5.0], and the constant "2003/04" can be analyzed as either a > >> > positional cterm interval["2003","2004"] or again as an > >>object-oriented cterm > >> > interval[start->"2003";end->"2004"]. Note that square brackets > >>are preferable > >> > for cterms to clearly set them off from the parenthesized atoms. > >> > >> cterms are construction functor expressions? This syntax is new to > >> me; where does it come from? Does it have detractors? > > > >Yes, originally 'complex terms' are exactly what Prolog calls > >'structures'. The > >distinction between (round) parentheses for active calls and [square] brackets > >for passive structures was introduced in Relfun -- cf. > >http://www.relfun.org/ or > >http://www.cs.unb.ca/~boley/cs6905/cs6905FLP.pdf -- and can be seen > >as an obvious > >generalization of Prolog's list notation via a polyadic tup > >constructor, so that > >[e1,...,eM] is definable as tup[e1,...,eM]. > > SCL follows KIF in allowing polyadicity explicitly, so we can define > tup axiomatically, so this is also natural for us. Yes, this is good Lisp tradition. > >Later, in Object-Oriented RuleML, we have permitted 'complex terms' to *also* > >contain unordered roles with their fillers, or -- as in F-Logic -- to *only* > >contain such frame-like 'slots'. In that sense, this is a merger of Prolog and > >F-Logic. > > > >Well, a 'detractor' -- which sounds better as the antonym for > >'constructor' than > >'destructor' does -- in a unification-based language such as Prolog, > >Relfun, or > >F-Logic can be represented by a local unification and variable > >dereferencing for > >the selected part of the complex data structure (BTW, John McCarthy > >in his work > >on abstract syntax used 'selector' as the antonym for 'constructor'). > > First question, how does one unify a term which selects a > subexpression which isn't present? Does the unifier have to supply a > suitable binding, or does the unification fail? The unification fails: 'rest' variables must be explicit. > Eg consider unifying > interval[StartDate, EndDate] with a single variable ?x Without explicit 'rest' variables, interval[StartDate,EndDate] unifies with the single variable X by binding X = interval[StartDate,EndDate] does not unify with the unary interval[X] unifies with the binary interval[X,Y] by binding StartDate = X, EndDate = Y does not unify with the ternary interval[X,Y,Z] In Prolog a positional 'rest' variable -- only permitted in lists -- is indicated by separating it from previous elements via a "|" instead of the normal "," separator. Here, a positional 'rest' variable -- permitted in lists, structures, atoms, etc. -- is indicated by a (double) ",," instead of the normal (single) "," separator; this will also allow a (double) ";;" instead of the normal (single) ";" separator for unordered ('object-oriented') complex terms. With such explicit 'rest' variables, interval[StartDate,EndDate,,ResumeDates] unifies with variable X by binding X = interval[StartDate,EndDate,,ResumeDates] does not unify with the unary interval[X] unifies with the binary interval[X,Y] by binding StartDate = X, EndDate = Y, ResumeDates = [] unifies with the ternary interval[X,Y,Z] by binding StartDate = X, EndDate = Y, ResumeDates = [Z] unifies with the 4-ary interval[X,Y,Z,"2004"] by binding StartDate = X, EndDate = Y, ResumeDates = [Z,"2004"] unifies with the (1+n)-ary interval[X,,Y] by binding StartDate = X, Y = [EndDate,,ResumeDates] > >So we can access the start date of interval["2003","2004"] by unifying it with > >interval[StartDate,EndDate] and dereferencing StartDate to "2003". > >Similarly, we > >can access the end date of interval[start->"2003";end->"2004"] via unification > >with interval[start->StartDate;end->EndDate] and dereferencing > >EndDate to "2004". > > When is dereferencing performed? (Only during unification?) What is > the difference between dereferencing and binding? At least during unification, before built-ins are called, and for result printouts (the issue of performing or not performing the 'occurs check' is orthogonal to this discussion). > The above first > example looks like a normal unification if we read 'StartDate' as a > variable; what does it mean to dereference a variable? Yes, it *is* a normal unification -- everything above is still positional; Prolog's convention of capitalizing variable names such as 'StartDate' is assumed throughout. > Does interval[start->A; end->B] unify with interval[A,B] ? How about > interval[start->?x; end->B] unified with interval[A,B] ? Does that > bind ?x to A ; if so, what is the common instance? The object-oriented interval[start->A;end->B] does not unify with the positional interval[A,B]. However, an operation positionalize(interval[start->A;end->B]) can be defined to return the ordered interval[B,A] by omitting the role names after a lexicographic normalization (sorting) w.r.t. the role names. This interval[B,A] in turn would unify with the positional interval[A,B] by binding B = A. Likewise, interval[start->X;end->B] does not unify with interval[A,B] > What happens if we put the variable on the other side: > interval[start->A; end->B] unify with interval[?x,B] ? Does this > bind ?x simply to B or to something that indicates the 'end' role? > What is the common instance? (More generally, how is instantiation > defined over Cterms? ) Same as above. Neither do interval[start->a;end->b] and interval[X,b] unify, where the lower-case letters 'a' and 'b' are individual constants. Instantiation for positional cterms is defined as usual; for object-oriented cterms it is defined to apply the bindings of a substitution to the fJ of each slot rj->fJ (cf. remarks below on forbidding variables in the position of roles rJ). > Does f[a->A] unify with f[a->A, b->B] ? f[a->A] does not unify with f[a->A;b->B], since 'rest' variables must be explicit also for object-oriented cterms. With the ';;'-separator introduced above, f[a->A;;X] unifies with f[a->A;b->B] by binding X = [b->B]. Similarly, f[a->A;;X] unifies with f[a->A;b->B;c->C] by binding X = [b->B;c->C]. > (The reason for asking this is that in one interpretation, any > 'missing' roles should be interpreted as existentials, eg that would > be appropriate for case-grammar or event description logics, and then > this kind of unification would be appropriate.) Here, an existential is made explicit after the ';;'-separator by a fresh variable X (so the collection of these 'rest' roles can be referred to via X). Alternatively, an 'anonymous' variable can be employed (as in Prolog written as '_'): f[a->A;;_] unifies with f[a->A;b->B] without any bindings f[a->A;;_] unifies with f[a->A;b->B;c->C] without any bindings The applications for case-grammar, event description logics, etc. can thus be done equally well, and the more precise ';;'-free OO cterms can enforce more restricted unifications where needed. > Can I write a variable in a role position, eg: f[?x->A] unify with f[a->A] ?? I would not recommend this for several reasons, two of which being: * The 'functionality' (http://www.daml.org/listarchive/joint-committee/1366.html) of OO cterms could be lost, since initially different variables in two role positions could become unified when additionally used in a filler position. For example, f[X->1;Y->2;c->g[X,Y]] would unify with f[U->1;V->2;c->g[Z,Z]] with non-functional common instance f[Z->1;Z->2;c->g[Z,Z]]. * There would no longer be a unique most general unifier, so non-determinism would already arise during the unification phase of resolution. For example, f[X->U;Y->V] would unify with f[a->1;b->2] by binding X = a, U = 1, Y = b, V = 2 or, equally general, by binding X = b, U = 2, Y = a, V = 1. > >But instead of / in addition to this, we can introduce a 'universal' > >selector sel, > >parameterized by either a positive integer or a role name. > > > >sel[1](interval["2003","2004"]) would return "2003". > >sel[end](interval[start->"2003";end->"2004"]) would return "2004". > > What about > sel[1](interval[start->"2003";end->"2004"]) ? Is that "2003" or undefined? That is undefined; sel[start](interval[start->"2003";end->"2004"]) is "2003". However, with a positionalize function as indicated above, we could have the following computation ('end' is lexicographically before 'start'): sel[1](positionalize(interval[start->"2003";end->"2004"])) sel[1](positionalize(interval[end->"2004";start->"2003"])) sel[1](interval["2004","2003"]) "2004" > Final question: what is the point of all of this? Why bother writing > > sel[1](interval["2003","2004"]) when you could just write "2003" ? If an interval binding like I = interval["2003","2004"] is computed somewhere else, and we only need its start date, sel[1](I) always gives us the desired result. > Is the following meaningful?: > > sel[1](?x)= "2003" > when ?x bound to interval["2003","2004"] ? Well, when X is already bound to interval["2003","2004"], the call sel[1](X) behaves like sel[1](interval["2003","2004"]). However, when X is still free, we have a case of equation solving, here involving the inversion of the sel[1] function. Special cases of function inversion have been studied in functional-logic languages like Relfun, but here I assumed sel to be a built-in non-invertible function. > It seems to me that if this works then you ought to be able to use > this to mimic higher-order unifications. Has that been tried? I don't know whether that been tried. Since the free variable X of sel[1](X) = "2003" would only range over (non-ground) cterms, not over (lambda) functions, I don't see how it mimics higher-order unification in the sense studied, e.g., in lambda Prolog (http://www.cse.psu.edu/~dale/lProlog/). Best, Harold
This archive was generated by hypermail 2.1.4 : 06/06/03 EST