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 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]> 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. -- 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.
