On Tuesday, March 21, 2017 at 4:59:50 PM UTC+1, William Byrd wrote: > > Hi Dmitrii! > > I'll give a brief answer now. I hope Michael Ballantyne will give a > more detailed explanation. I hope Michael will also go over the > faster-miniKanren implementation during one of the upcoming hangouts. > > As I recall, there are three main reasons faster-miniKanren is faster > than previous implementations: > > 1) use of efficient immutable data structures, rather than association > lists, to implement the substitution, etc. There are other miniKanren > implementations that do this. For a detailed exploration of how > different data structures perform, please see this unpublished paper: > > https://www.cs.indiana.edu/~lkuper/papers/walk.pdf
This paper is gone, can someone upload it somewhere for me please? Or give a summary of the ideas that are inside? Also, how do you benchmark (faster-)minikanren? > faster-miniKanren doesn't use the absolutely fastest representation, > at least as described in that paper, but any efficient representation > will perform much better than association lists for most real > miniKanren programs. > > 2) use of attributed variables to represent constraints. That is, > constraints other than unification (disequality, absento, numbero, > symbolo) are associated with logic variables, rather than just being > put in a list as in the original cKanren. The advantage is that it is > quick and easy to determine which constraints are involved in a given > unification. Compare this with the older approach, in which the > entire constraint store might be checked, even when unifying variables > that don't have constraints associated with them. > > This is a huge win for programs that make heavy use of constraints, > such as relational interpreters. > > As a historical note, I must take the blame for the inefficient > approach used in the original cKanren. Jeremiah Willcock suggested we > use attributed variables from the very beginning, and Claire and Dan > wanted to use them. I wasn't convinced that we'd be able to represent > all of our constraints using attributed variables, and advocated for > the slower, list-based constraint approach. I was wrong. > > I believe core.logic uses attributed variables, or something > equivalent, but I'm not sure. Michael Ballantyne wrote a very nice > implementation of our constraints using attributed variables for > faster-mk. I'm not sure if Claire used attributed variables in > Kraken, the successor to cKanren. > > Another possibility would be to implement constraints using Constraint > Handling Rules (CHR). I think Claire explored this approach for > Kraken. > > 3) Michael Ballantyne suggested another optimization, which, to my > knowledge, is only used in faster-miniKanren. Michael noticed that > many times logic variables are unified immediately after they are > created with a 'fresh'. In these cases it is not necessary to extend > the substitution. Instead, we can just mutate a structure > representing the variable (using a local mutation that is harmless). > This is the intent of the 'scope'-related comments in the code: > > https://github.com/webyrd/faster-miniKanren/blob/master/mk.scm > > Look at the definition of 'subst-add', in particular: > > ; set-var-val! optimization: set the value directly on the variable > ; object if we haven't branched since its creation > ; (the scope of the variable and the substitution are the same). > ; Otherwise extend the substitution mapping. > > I hope Michael will jump in and explain this optimization in more detail. > > Hope this helps! > > --Will > > > On Mon, Mar 20, 2017 at 5:17 AM, Dmitrii Kosarev > <[email protected] <javascript:>> wrote: > > Hey, folks > > > > Can you describe why faster miniKanren [1] is.. em... faster than every > > think else? I believe that it's true because I measured. Can you put > this > > very useful information in the repo description? What should I do to > make > > microKanren work in the same manner as faster miniKanren. > > > > Happy hacking, > > Dmitrii > > > > > > [1] https://github.com/michaelballantyne/faster-miniKanren > > -- 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.
