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.
