Awesome feedback is awesome!
Thanks Jason, thanks David.
Got a bunch to read now.
My implementation does first-search, i didn't implement the proper
interleaving for now.
I do use backtracking to check if 2 maps/association-lists/objects are
subtypes, since i have to find matching pair in 2 lists.
{:a Number :b String} is super type of {:b String :a Long } which is a
super type of {:a "a" :b 1}
Also for recursion schemes.
(rec a (cons (Or Number nil) a) is super type of (rec a (cons 1 (cons nil
a)))
Once I'm able to run the type-check against clojure.core.clj source or
other github projects,
I'll start tweaking the minikanren implementation.
Currently I'm dwelling with the java parts of clojure(RT), since i dont
have an ast for free.
I did went through my mind to type check java-bytecode, but that would be
just madness.
Cheers, Paulo
On Thursday, March 16, 2017 at 9:35:08 PM UTC-3, Jason Hemann wrote:
>
> You might also be interested in some of the linear-time or near-linear
> unification algorithms from Huet, Paterson & Wegman, and Martelli &
> Montanari. With that, you might also be interested in the Conchon &
> Filliâtre persistent union-find structure. The persistent union-find
> should give the advantage of a union-find based solution without the full
> cost of backtracking that David rightly warns against. Dan and I played
> with some of this a while back, and I think our experimental versions are
> still up on github somewhere.
>
> Best,
>
> JBH
>
> On Thu, Mar 16, 2017 at 6:35 PM, David Kahn <[email protected]
> <javascript:>> wrote:
>
>> Keep in mind that in minikanren you are constantly forking the
>> substitution at every conde. Any simplifications you make to the
>> substitution won't affect siblings branches on the search tree, and have to
>> be re-applied. For something like type inference which needs no
>> backtracking it should work great; but anything that does backtrack will
>> just be slowed down. This is just something you have to live with in fair
>> search, but can be somewhat gotten around by making a depth-first search
>> version of conde for problems where you aren't worried about divergence.
>>
>>
>> On Monday, February 6, 2017 at 7:26:16 PM UTC-6, Paulo César Cuneo wrote:
>>>
>>> Hi minikanren list!
>>>
>>> I was implementing my own version of minikanren in clojure and i figure
>>> out i could interleave walk with unifiy, so i could flatten out lvars chain.
>>> Beside the current version isnt tail recursive (and may stackoveflow),
>>> see any problem.
>>> I guess cache may missbehave, but lvars are not compacted together, soo
>>> i dont know.
>>> Is there a minikanren benchmark test anywhere?
>>> Someone already tried this?
>>>
>>>
>>> (defn unify [x y a]
>>> (cond
>>> (lvar? x) (let [x' (get-var a x)
>>> ;; get-var is not walk
>>> a' (if (lvar? x')
>>> (if (= x x')
>>> (ext-s a x' y)
>>> (unify x' y a))
>>> (unify y x' a))
>>> x'' (get-var a' x')]
>>> ;; compress path
>>> (ext-s a' x x''))
>>> (or (seq? x)
>>> (seq? y)) (unify-seq x y a)
>>> (= x y) a
>>> :else nil))
>>>
>>> Bye.
>>>
>> --
>> 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] <javascript:>.
>> To post to this group, send email to [email protected]
>> <javascript:>.
>> Visit this group at https://groups.google.com/group/minikanren.
>> For more options, visit https://groups.google.com/d/optout.
>>
>
>
>
> --
> JBH
>
--
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.
