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.
