Right. I'll try. So the feature structures are lists, and I am assuming the
car of a feature structure is a symbol eg. (a (b c) (d e)). To unify two
feature structures f1 and f2 (say (a (b c) (d e)) with (a (b c) (f g)) with
unify°, we first test to see whether they are equal, if they are, then
their unification is either one of them and `out` unifies with f1 (it could
as well be f2). If they are not we make sure their car is equal (otherwise
they can't unify), and call unify unify-list-with-list° on their cdrs (in
this case ((b c) (d e)) and ((b c) (f g)), the result is unified to `res`,
and the final answer is the car of f1 consed to res.
unify-list-with-list° calls unify-f-with-list° with the car of the first
list ((b c)) and the second list ((b c) (f g)). And repeats for all
elements of the first list.
unify-f-with-list° tries to unify the the feature f1 ((b c)) with the list
l1 ((b c) (f g)). It does so how you suggested, it checks for the first
member of l1((b c)) whether the car of f1 is the car of said member (in
this case it is), if it is, it tries to unify bot features structures by
calling unify° on them (since in this case they are equal, it returns (b c)
). If it succeeds, it returns the result of their unifications consed to
the rest of l1. If both cars are not the same, it goes on to the next item
in l1. If we get to the end, it just means that f1 was not in l1, and we
can return it, and it will be added to the end of l1.
>From here the process goes on to try to unify (d e) with our list ((b c) (f
g)). Since d is not in any of the members of this list, it returns it and
we end up with ((d e) (b c) (f g)). The unification then succeeds with (a
(d e) (b c) (f g)).
Now, for the problematic case:
(run* (q)
(unify° '(a (c (x d))) q '(a (b d) (c (x d)))))
We're asking what feature structured needs to unify with '(a (c (x d))) to
produce '(a (b d) (c (x d))). There are several answers: '(a (b d)), '(a (b
d) (c)) and '(a (b d) (c (x d))) which minikanren seems to finds, plus some
other possibilities which it does not seem to find. Also, as soon as one
asks for more, minikanren cannot figure out that there are no more answers
and gets stuck.
I've tried reordering the goals, but no luck so far.
My guess is that it may have something to do with returning either f1 or f2
in the first conde line of unify°, and the fact that order in the feature
structures shouldn't matter.
In any case, this is pretty close to what I need.
El dom., 9 dic. 2018 a las 21:08, Apocalypse Mystic (<
[email protected]>) escribió:
> Not off hand, although maybe if you commented what you thought the code
> was doing it would become clear. What sort of structure do your features
> have? I'm not 100% sure I'm reading those tests correctly.
>
> On Sun, Dec 9, 2018 at 2:23 PM Matías Guzmán Naranjo <[email protected]>
> wrote:
>
>> Hi Evan,
>>
>> you're idea almost works (at least how I implemented it), thank you!
>> Forward unification works as expected, but backward queries get stuck in
>> infinite loops with run*. The system doesn't seem to be able to figure out
>> that there is a finite number of solutions. Any ideas on how to fix this on
>> the code below?
>>
>> Since you asked. I am working on a formal theory of proportional analogy
>> for HPSG. So it's mostly theoretical stuff I want to be able to check with
>> the computer, nothing really 'practical'.
>>
>> ----
>>
>> ;; unifies f1 with l2
>> (define unify-f-with-list°
>> (lambda (f1 l2 out)
>> (conde
>> [(== '() l2) (== `(,f1) out)]
>> [(fresh (la ld a2 d2 a1 d1 res)
>> (=/= '() l2)
>> (== `(,la . ,ld) l2)
>> (== `(,a2 . ,d2) la)
>> (== `(,a1 . ,d1) f1)
>> (conde
>> [(== a2 a1)
>> (== `(,res . ,ld) out)
>> (unify° f1 la res)]
>> [(fresh ()
>> (=/= a2 a1) ;; if not
>> (== `(,la . ,res) out)
>> (unify-f-with-list° f1 ld res))]))])))
>>
>> (define unify-list-with-list°
>> (lambda (l1 l2 out)
>> (conde
>> [(== '() l1) (== l2 out)]
>> [(== '() l2) (== l1 out)]
>> [(fresh (a1 d1 res)
>> (=/= '() l1)
>> (== `(,a1 . ,d1) l1)
>> (unify-f-with-list° a1 l2 res)
>> (unify-list-with-list° d1 res out))])))
>>
>> (define unify°
>> (lambda (f1 f2 out)
>> (conde
>> [(== f1 f2) (== f1 out)]
>> [(fresh (a1 d1 a2 d2)
>> (=/= f1 f2)
>> (== `(,a1 . ,d1) f1)
>> (== `(,a2 . ,d2) f2)
>> (== a1 a2)
>> (fresh (res)
>> (unify-list-with-list° d1 d2 res)
>> (== `(,a1 . ,res) out)))])))
>>
>> (run* (q)
>> (unify° '(a (c b) (e d)) '(a (e d) (c) ) q))
>>
>> (run* (q)
>> (unify° '(a (c b) (e d)) '(a (e d) (c b) ) q))
>>
>> (run* (q)
>> (unify° '(a (c b) (e d)) '(a (e d) (c b) ) q))
>>
>> (run* (q)
>> (unify° '(a (c b)) '(a (c b) (d e) ) q))
>>
>> (run* (q)
>> (unify° '(a (c (x d))) '(a (d e) (c (g o))) q))
>>
>> (run* (q)
>> (unify° '(a (c (x d))) '(a (b d)) q))
>>
>> (run 2 (q)
>> (unify° '(a (c (x d))) q '(a (b d) (c (x d)))))
>>
>> (run 3 (q)
>> (unify° '(a (c (x d))) q '(a (b d) (c (x d)))))
>>
>> (run 4 (q)
>> (unify° '(a (c (x d))) q '(a (b d) (c (x d)))))
>>
>> ;; this one is the problem here
>>
>> (run* (q)
>> (unify° '(a (c (x d))) q '(a (b d) (c (x d)))))
>>
>> El mié., 5 dic. 2018 a las 4:10, Apocalypse Mystic (<
>> [email protected]>) escribió:
>>
>>> Hi,
>>>
>>> If your problem will fit the tree-based encoding, that is definitely the
>>> easiest way to do it. If not, you could probably hack the unifier and maybe
>>> get better performance or something, but probably the best place to start
>>> would be by just writing a (feature-structure-unify A B C) relation as
>>> mentioned above. I haven't implemented this, so perhaps I'm overlooking
>>> something (caveat emptor), but I would think you would just need to iterate
>>> through features in A, and for each one check it against each feature in B.
>>> If they unify, unify them (recursively feature-unify them) and add the
>>> result to C. If they don't (disequality constraint), keep looking through
>>> the features of B. At the end of B's features, you would check whether the
>>> feature has yet been added to C, and if not, just add the feature. Same
>>> process for B, perhaps with some pre-checking to see if A has already added
>>> that feature to C. Have you tried something like this and encountered any
>>> particular problems?
>>>
>>> Incidentally, I'm also working on NLP in minikanren, and I'm curious to
>>> know what you're doing with it, if you don't mind sharing.
>>>
>>> Cheers,
>>> Evan
>>>
>>> On Sat, Dec 1, 2018 at 1:13 PM Matías Guzmán Naranjo <
>>> [email protected]> wrote:
>>>
>>>> > Maybe the term unification is misleading here.
>>>>
>>>> Well, that's how they call it ;). They are extremely useful when
>>>> working with grammatical formalisms which make use of them (HPSG, LFG, TAG,
>>>> etc. ). If you're doing statistical NLP they are not all that useful, but
>>>> they are at the core of symbolic NLP.
>>>>
>>>> > But it could unify with [Agr [number sg, gender f]]?
>>>>
>>>> yes
>>>>
>>>> > My system narrow the search space. So indeed, if you want to know
>>>> everything that can unify with [Agr [number sg]] you *could* query every
>>>> every facts that are an Agr (instead of all the facts) and then filter
>>>> manualy those that don't have [number sg] or have something else and do
>>>> that recursively... In theory it's possible to do such thing I guess.
>>>>
>>>> Not sure why you think the search would have to be that deep and
>>>> complex. To me it feels like it should be like the `appendo` example, where
>>>> once you define a relational append, it can run backwards just fine. Once
>>>> one defines `unifyo` relationally it should be able to do the search
>>>> backwards, no?
>>>>
>>>> > I will come back to this subject at some point, but the lack of
>>>> real-world problem to solve doesn't make it appealing.
>>>>
>>>> Well, it would be useful for people like me working on symbolic NLP,
>>>> who want to write relational parsers. I will work on it using your
>>>> representation, I was trying to do it using lists: (Agr (number sg) (person
>>>> 3)), but I couldn't figure it out.
>>>>
>>>> El sáb., 1 dic. 2018 a las 18:19, Amirouche Boubekki (<
>>>> [email protected]>) escribió:
>>>>
>>>>>
>>>>>
>>>>> Le sam. 1 déc. 2018 à 17:00, Matías Guzmán Naranjo <
>>>>> [email protected]> a écrit :
>>>>>
>>>>>> Hi Amirouche,
>>>>>>
>>>>>> yes, those are the feature structures I am talking about. Your idea
>>>>>> for representing them seems interesting, I am wondering whether you have
>>>>>> a
>>>>>> solution for unification?
>>>>>>
>>>>>
>>>>> Maybe the term unification is misleading here. That's why I asked the
>>>>> question initially. I also asked the question because I am interested in
>>>>> NLP and feature structures seems to be thing in this field. But I failed
>>>>> to
>>>>> find more ressources to better understand the use cases.
>>>>>
>>>>> Quick answer is that it doesn't do unification in terms of feature
>>>>> structures. It does unification of triples with a semantic that *looks*
>>>>> like SPARQL (without support for OPTIONAL).
>>>>>
>>>>> Say I have [Agr [number sg]] and want to unify it with [Agr [person
>>>>>> 1]], it should produce: [Agre [number sg, person 1]] (where order doesn't
>>>>>> matter).
>>>>>>
>>>>> However, it should fail if I want to unify [Agr [number sg]] and [Agr
>>>>>> [number pl]].
>>>>>>
>>>>>
>>>>> But it could unify with [Agr [number sg, gender f]]?
>>>>>
>>>>>
>>>>>> Ideally, it should also run in reverse: I should be able to ask what
>>>>>> [Agr [number sg]] needs to unify with to produce [Agr [number sg, person
>>>>>> 1]].
>>>>>>
>>>>>
>>>>> That is an interesting problem.
>>>>>
>>>>>
>>>>>> Can your system do this?
>>>>>>
>>>>>
>>>>> My system narrow the search space. So indeed, if you want to know
>>>>> everything that can unify with [Agr [number sg]] you *could* query every
>>>>> every facts that are an Agr (instead of all the facts) and then filter
>>>>> manualy those that don't have [number sg] or have something else and do
>>>>> that recursively... In theory it's possible to do such thing I guess.
>>>>>
>>>>> Like I said previously, it can not do feature-structure unification
>>>>> as-is. To support that last query it requires a minikanren with
>>>>> constraints
>>>>> support (and possibly to support bigger than RAM dataset it would require
>>>>> streamable solutions).
>>>>>
>>>>> I will come back to this subject at some point, but the lack of
>>>>> real-world problem to solve doesn't make it appealing.
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "minikanren" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>>> an email to [email protected].
>>>>> To post to this group, send email to [email protected].
>>>>> Visit this group at https://groups.google.com/group/minikanren.
>>>>> For more options, visit https://groups.google.com/d/optout.
>>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "minikanren" group.
>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>> an email to [email protected].
>>>> To post to this group, send email to [email protected].
>>>> Visit this group at https://groups.google.com/group/minikanren.
>>>> For more options, visit https://groups.google.com/d/optout.
>>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "minikanren" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to [email protected].
>>> To post to this group, send email to [email protected].
>>> Visit this group at https://groups.google.com/group/minikanren.
>>> For more options, visit https://groups.google.com/d/optout.
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "minikanren" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected].
>> To post to this group, send email to [email protected].
>> Visit this group at https://groups.google.com/group/minikanren.
>> For more options, visit https://groups.google.com/d/optout.
>>
> --
> You received this message because you are subscribed to the Google Groups
> "minikanren" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> Visit this group at https://groups.google.com/group/minikanren.
> For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google Groups
"minikanren" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/minikanren.
For more options, visit https://groups.google.com/d/optout.
