Usecases

[awalterschulze]

I open this issue with the hope of gathering use cases.
How would you like to use minikanren in Go, in an integrated way.

For example:

I would like to get all combinations of two strings that could produce "ab"

combos := Appendo(Var("q"), Var("p"), "ab")
print(combos)
// "", "ab"
// "a", "b"
// "ab", ""

Maybe we can start by making a better first example :)

Once we have these use cases we can try and design this library or code generator to be the minikanren we would like to use in Go.

Personally I would like to avoid using empty interface, if possible.
I prefer code generation over reflect, but we will have to see what is possible first.

[mewmew]

I would like to play with combining probabilistic notions and constraint satisfaction in minikanren with graph theory, to be used for fuzzy graph inference problems, where the initial knowledge set is not precise. Each property of the graph is given a probability (0 through 1) of being true, rather than a boolean value (0 or 1). The idea is to find a fuzzy isomorphic match between a set of graphs, such that the node mapping maximize the number of nodes above a certain confidence threshold (as based on the relation between properties in the graph).

I realize that both probabilistic logic and constraint programming is part of extensions to minikanren. Just want to raise such ideas early, so we don't paint ourselves into a corner where such extensions are not easy to model.

To give a specific use case for the above idea of fuzzy isomorphic matching, imagine the same source code (or mostly the same, may contain architecture specific code) of a larger program being compiled for three different architectures, producing the binaries A, B and C. Given call graphs for each of these binaries, how would you find which functions in binary A correspond to which functions in binaries B and C?

One way would be to specify what little you know of the properties of these functions (and to what certainty you know these properties) and then use inference to extend knowledge. For instance:

• A node of the call graph may be marked as the entry function of the program based on information from the executable format (e.g. PE, ELF). This property would be of high certainty.
• The callees of the entry function (or any function for that matter) gain the property of having the entry function as a caller.
• How many arguments does a given function take (based on calling conventions, and identified by use-def chains, where a use is seen before a def in a function, then a function argument (or global variable) has been identified). This property would be of medium certainty, as the analysis may be incorrect.
• ...

The knowledge about the call graphs is extended through inference until a fuzzy isomorphic match is found given a certain threshold of certainty for different properties of the graph.

[mewmew]

Maybe we can start by making a better first example :)

How about using Einstein's puzzle as an example?

Let us assume that there are five houses of different colors next to each other on the same road. In each house lives a man of a different nationality. Every man has his favorite drink, his favorite brand of cigarettes, and keeps pets of a particular kind.

• The Englishman lives in the red house.
• The Swede keeps dogs.
• The Dane drinks tea.
• The green house is just to the left of the white one.
• The owner of the green house drinks coffee.
• The Pall Mall smoker keeps birds.
• The owner of the yellow house smokes Dunhills.
• The man in the center house drinks milk.
• The Norwegian lives in the first house.
• The Blend smoker has a neighbor who keeps cats.
• The man who smokes Blue Masters drinks bier.
• The man who keeps horses lives next to the Dunhill smoker.
• The German smokes Prince.
• The Norwegian lives next to the blue house.
• The Blend smoker has a neighbor who drinks water.

The question to be answered is: Who keeps fish?

[awalterschulze]

Wow this is so far above my head as someone new to the field. Would you maybe also include how you would like the go code to look that you want to use. I hope this will help me to understand better.

[deosjr]

Einstein's puzzle is a good example, since it fits the logical programming style very well. I think what we should focus on indeed is how you would like a minikanren library in Go to look like.
Where does the minikanren code live? What does a call from Go to solve the puzzle look like? etc.

[mewmew]

Wow this is so far above my head as someone new to the field. Would you maybe also include how you would like the go code to look that you want to use. I hope this will help me to understand better.

Haha, it's way above my head as well. Which is what makes it a fun challenge :)

[awalterschulze]

Agreed 😀

…

On Tue, 26 Sep 2017, 19:16 Robin Eklind, ***@***.***> wrote: Wow this is so far above my head as someone new to the field. Would you maybe also include how you would like the go code to look that you want to use. I hope this will help me to understand better. Haha, it's way above my head as well. Which is what makes it a fun challenge :) — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#1 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABvsLQyH1PvveXC9X4ClnGutyPM7IA6gks5smTFugaJpZM4PjJvC> .

[deosjr]

I dont know minikanren, but I particularly like this solution to Einstein's puzzle in Prolog, since it clearly shows it can be solved by a simple matrix:
https://gist.github.com/jgilchrist/1b85b04f4395057972dd

Could a solution in minikanren look similar? How would you like to call this small program from a larger one that's in Go? Thinking about it, it looks like I could generate this program from Go and have it solve the problem in the logic language (might not be optimised for this problem, but could be nice for NLP solutions). That's a neat interaction we might want to explore too.

[awalterschulze]

First version is finally working.