Git Product home page Git Product logo

logpy's Introduction

kanren

Logic Programming in Python

Examples

kanren enables the expression of relations and the search for values which satisfy them. The following code is the "Hello, world!" of logic programming. It asks for 1 number, x, such that x == 5

>>> from kanren import run, eq, membero, var, conde
>>> x = var()
>>> run(1, x, eq(x, 5))
(5,)

Multiple variables and multiple goals can be used simultaneously. The following code asks for a number x such that x == z and z == 3

>>> z = var()
>>> run(1, x, eq(x, z),
              eq(z, 3))
(3,)

kanren uses unification, an advanced form of pattern matching, to match within expression trees. The following code asks for a number, x, such that (1, 2) == (1, x) holds.

>>> run(1, x, eq((1, 2), (1, x)))
(2,)

The above examples use eq, a goal constructor to state that two expressions are equal. Other goal constructors exist such as membero(item, coll) which states that item is a member of coll, a collection.

The following example uses membero twice to ask for 2 values of x, such that x is a member of (1, 2, 3) and that x is a member of (2, 3, 4).

>>> run(2, x, membero(x, (1, 2, 3)),  # x is a member of (1, 2, 3)
              membero(x, (2, 3, 4)))  # x is a member of (2, 3, 4)
(2, 3)

Logic Variables

As in the above examples, z = var() creates a logic variable. You may also, optionally, pass a token name for a variable to aid in debugging:

>>> z = var('test')
>>> z
~test

Lastly, you may also use vars() with an integer parameter to create multiple logic variables at once:

>>> a, b, c = vars(3)
>>> a
~_1
>>> b
~_2
>>> c
~_3

Representing Knowledge

kanren stores data as facts that state relationships between terms.

The following code creates a parent relationship and uses it to state facts about who is a parent of whom within the Simpsons family.

>>> from kanren import Relation, facts
>>> parent = Relation()
>>> facts(parent, ("Homer", "Bart"),
...               ("Homer", "Lisa"),
...               ("Abe",  "Homer"))

>>> run(1, x, parent(x, "Bart"))
('Homer',)

>>> run(2, x, parent("Homer", x))
('Lisa', 'Bart')

We can use intermediate variables for more complex queries. Who is Bart's grandfather?

>>> y = var()
>>> run(1, x, parent(x, y),
              parent(y, 'Bart'))
('Abe',)

We can express the grandfather relationship separately. In this example we use conde, a goal constructor for logical and and or.

>>> def grandparent(x, z):
...     y = var()
...     return conde((parent(x, y), parent(y, z)))

>>> run(1, x, grandparent(x, 'Bart'))
('Abe,')

Data Structures

kanren depends on functions, tuples, dicts, and generators. There are almost no new data structures/classes in kanren so it should be simple to integrate into preexisting code.

Extending kanren to other Types

kanren uses Multiple Dispatch and the unification library to support pattern matching on user defined types. Also see unification (wikipedia). Types which can be unified can be used for logic programming. See the project examples for how to extend the collection of unifiable types to your use case.

Install

With pip or easy_install

pip install kanren

From source

git clone [email protected]:logpy/logpy.git
cd logpy
python setup.py install

Run tests with tox

tox

Dependencies

kanren supports 3.5+. It is pure Python and requires no dependencies beyond the standard library, toolz, multipledispatch, and unification.

It is, in short, a light weight dependency.

Author

Matthew Rocklin

License

New BSD license. See LICENSE.txt

Motivation

Logic programming is a general programming paradigm. This implementation however came about specifically to serve as an algorithmic core for Computer Algebra Systems in Python and for the automated generation and optimization of numeric software. Domain specific languages, code generation, and compilers have recently been a hot topic in the Scientific Python community. kanren aims to be a low-level core for these projects.

References

logpy's People

Contributors

alexrudnick avatar brandonwillard avatar jaberg avatar jdmcbr avatar kootenpv avatar lucaswiman avatar mrocklin avatar skirpichev avatar t3db0t avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

logpy's Issues

Proposing a PR to fix a few small typos

Issue Type

[x] Bug (Typo)

Steps to Replicate and Expected Behaviour

  • Examine kanren/assoccomm.py and observe regsitry, however expect to see registry.
  • Examine kanren/assoccomm.py and observe parition, however expect to see partition.

Notes

Semi-automated issue generated by
https://github.com/timgates42/meticulous/blob/master/docs/NOTE.md

To avoid wasting CI processing resources a branch with the fix has been
prepared but a pull request has not yet been created. A pull request fixing
the issue can be prepared from the link below, feel free to create it or
request @timgates42 create the PR. Alternatively if the fix is undesired please
close the issue with a small comment about the reasoning.

https://github.com/timgates42/logpy/pull/new/bugfix_typos

Thanks.

Package is not installable from pypi

$ pip install logpy
Downloading/unpacking logpy
  Downloading LogPy-1.0.tar.gz
  Running setup.py egg_info for package logpy
    Traceback (most recent call last):
      File "<string>", line 14, in <module>
      File "/home/sk/.virtualenvs/test/build/logpy/setup.py", line 6, in <module>
        long_description = open('README.rst').read(),
    IOError: [Errno 2] No such file or directory: 'README.rst'
    Complete output from command python setup.py egg_info:
    Traceback (most recent call last):

  File "<string>", line 14, in <module>

  File "/home/sk/.virtualenvs/test/build/logpy/setup.py", line 6, in <module>

    long_description = open('README.rst').read(),

IOError: [Errno 2] No such file or directory: 'README.rst'

It seems, this is fixed in the master.

Confusing `conso` results

Consider the following:

from unification import var
from kanren.goals import conso

run(0, var('a'),
    (conso, 3, var('a_cdr'), var('a')),
    (conso, 4, var('a_cddr'), var('a_cdr')))

It produces the unexpected results

((3, 4), LCons(3, LCons(4, LCons(~_47, ~_48))))

instead of (cons 3 (cons 4 ~_1))/(3 4 . ~_1) for some logic variable ~_1 in Lisp-like notation (or LCons([3, 4], ~_1) in Python).

This isn't the result one would get from standard implementations of conso (e.g. the one from "The Reasoned Schemer"), and I'm not entirely sure what the underlying relation in this implementation actually is.

Remove sympy dependency for associative/commutative matching

Associative and commutative unification currently rely on the answer to this problem

http://stackoverflow.com/questions/13131491/partition-n-items-into-k-bins-in-python-lazily

This question was solved by @smichr who then wrote the solution into the sympy.utilities.iterables.kbins function

Issue Theano/Theano#1046 would like commutative unification found in LogPy but can not depend on the development version of SymPy (nor, ideally, any version).

Solutions:

  1. Copy the relevant parts of sympy's iterables and combinatorics modules (what are the license issues for this?)
  2. Rewrite the solution using pure python.
  3. Write a more awesome less brute-force solution to associative/commutative matching. See issue #7

Silly wish - SymPy iterables and part of the combinatorics modules might be better off as a separate project. The current setup follows the "You wanted a banana but got a gorilla holding a banana instead" pattern.

nosetests fails on py2.6

(env)11:27:09 Python (master) >  git clone [email protected]:logpy/logpy.git
Cloning into 'logpy'...
cd logpy
nosetests --with-doremote: Counting objects: 1251, done.
remote: Compressing objects: 100% (552/552), done.
remote: Total 1251 (delta 727), reused 1187 (delta 670)
Receiving objects: 100% (1251/1251), 209.43 KiB | 197 KiB/s, done.
Resolving deltas: 100% (727/727), done.
(env)11:27:25 Python (master) >  cd logpy
(env)11:27:25 logpy (master) >  nosetests --with-doctest
....................................E..............................................
======================================================================
ERROR: Failure: ImportError (cannot import name expectedFailure)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/jacobsen/env/lib/python2.6/site-packages/nose/loader.py", line 390, in loadTestsFromName
    addr.filename, addr.module)
  File "/Users/jacobsen/env/lib/python2.6/site-packages/nose/importer.py", line 39, in importFromPath
    return self.importFromDir(dir_path, fqname)
  File "/Users/jacobsen/env/lib/python2.6/site-packages/nose/importer.py", line 86, in importFromDir
    mod = load_module(part_fqname, fh, filename, desc)
  File "/Users/jacobsen/Programming/Python/logpy/logpy/tests/test_core.py", line 6, in <module>
    from unittest import expectedFailure as FAIL
ImportError: cannot import name expectedFailure

----------------------------------------------------------------------
Ran 83 tests in 0.169s

FAILED (errors=1)
(env)11:27:26 logpy (master) >  

Interleave

Implement interleave and replace chain

Matching one expression against a lot (>1000) possible patterns?

Is there an idiom in logpy for a high-performance matching against multiple possible patterns. For instance, something like an or/xor goal constructor (but probably with dedicated interface):

>>> run(1, x, xor(  eq((1,2), (1,x)),
                    eq((1,2), (2,x)),
                    many_others ))
(2,)

>>> match_against_many(x, [the_same_big_list_of_eq_goal_constructors])
(2,)

Is it possible to do this in O(1) (with some magical hashing)?

I am asking this question because of languages like Haskel and Mathematica, where such high-performance pattern matching is a requirement.

Python cons package

Instead of manually copying and updating separate versions of the same cons implementation I recently added here (e.g. originally from here), I've finally gotten around to making a package: https://github.com/brandonwillard/python-cons

It has some recent updates and should be better for ongoing fixes and enhancements, so, if it's also good for kanren, I can put in a PR to add this as an external dependency.

Dict Unification

We should support unification with other datatypes, particularly dictionaries.

Associative/Commutative unification

It is important that (add x y z) can match to (add a b) with for example

associative

{a: (add, x, y), b: z} 

commutative

{a: z, b: (add, y, x)}

This can be costly but is quite doable. The implementation in SymPy has the relevant code for permutations and such. Apparently this is also a topic of research

http://scholar.google.com/scholar?hl=en&q=associative+commutative+unification&btnG=&as_sdt=1%2C14&as_sdtp=

A couple of highly cited papers on the topic
http://www.sciencedirect.com/science/article/pii/S0747717187800044
http://dl.acm.org/citation.cfm?id=322262

`eq_comm` does not propagate

The eq_comm goal isn't applied to sub-terms.

Starting from the docstring example, the following demonstrates:

>>> from kanren import run, var, fact, eq
>>> from kanren.assoccomm import eq_comm
>>> from kanren.assoccomm import commutative
>>> fact(commutative, 'add')

>>> x = var()
>>> run(0, x, eq_comm(('add', 1, 2, 3),
>>>                   ('add', 2, x, 1)))
(3,)

>>> run(0, x, eq_comm(('div', 1, ('add', 1, 2, 3)),
>>>                   ('div', 1, ('add', 2, x, 1))))
()

It would seem as though the last expression should produce (3,), as well.

Inequality goal

hi,

Is there an inequality test / goal in logpy?

If so, how can I use it? If not, is it possible to create one?

cheers

Phil

Goalified sympy.ask does not work

I've been trying to read @mrocklin 's thesis and gather bits that seemed relevant to do custom term rewriting in sympy. Patching code excerpts, I get:

from sympy import Basic, Q, ask, log, exp, Abs
from sympy.abc import x,y
from logpy import Relation, var, facts, goalify, run, variables

Basic._term_op = lambda self: self.func
Basic._term_args = lambda self: self.args
Basic._term_new = classmethod(lambda op, args: op(*args))
Basic._term_isleaf = lambda self: len(self.args) == 0


patterns = [
  (Abs(x), x, Q.positive(x)),
  (exp(log(x)), x, Q.positive(x)),
  (log(exp(x)), x, Q.real(x)),
  (log(x**y), y*log(x), True)
  ]

vars = {x, y}

rewrites = Relation('rewrites')
facts(rewrites, *patterns)

asko = goalify(ask)

def rewrite_step(expr, rewrites):
  """ Possible rewrites of expr given relation of patterns """
  target, condition = var(), var()
  with variables(*vars):
    return run(
            None,
            target,
            rewrites(expr, target, condition),
            asko(condition, True))
rewrite_step(log(x**y), rewrites)

But this fails with:

Traceback (most recent call last):
  File "test.py", line 38, in <module>
    rewrite_step(log(x**y), rewrites)
  File "test.py", line 37, in rewrite_step
    asko(condition, True))
  File "/usr/local/lib/python3.5/dist-packages/logpy/goals.py", line 157, in funco
    raise EarlyGoalError()
logpy.core.EarlyGoalError

Here I used pip3 install sympy logpy. Are there more recent explanations which would work with current versions of logpy and smypy? Or should I try something completely different?

Expression tuples

The use of ordinary Python tuples and lists to model unevaluated expressions/forms has caused some issues in my work on symbolic-pymc (e.g. reconstruction nested "tuplized" objects). In that project, I worked around those issues by simply creating a tuple-based expression class: ExpressionTuple.

Additionally, these ExpressionTuples have made it easier to clarify when/where term and operator/arguments are actually applicable (e.g. operator and arguments implemented for generic tuples/lists removes the distinction between objects that are normal collections and those that are modeling an expression) and it allows for a naive sort of tuple-expression evaluation/reification caching.

If you folks are interested, I can put in a PR to termpy adding this class and another for its use in kanren.

Side note: @mrocklin, issues aren't enabled for termpy; otherwise, I would've posted this there.

Name Change to `kanren`

The LogPy name conflicts with a logging library. In particular there is a conflict in the pypi registry. The LogPy organization is also growing to support more projects.

I'm considering changing the name of this project to kanren

Hi, is this compatible with python 3.10?

Hi, when I run from kanren import * on python 3.10, it will throw following error:

ImportError: cannot import name 'Iterator' from 'collections'

Is this because kanren now is incompatible with python 3.10, or it is because I have some configuration errors?

RecursionError: maximum recursion depth exceeded

I define friend relation as follows. It got RecursionError, how do you avoid of it?

#!/usr/local/bin/python
# -*- coding: utf-8 -*-
from kanren import *

class DemoRelation(Relation):
    def __call__(self, *args, **kwargs):
        print('pair', *args)
        super(DemoRelation, self).__call__(*args, **kwargs)

pair = DemoRelation()

facts(pair, ("Liao", "Lufei"))
facts(pair, ("Liao", "Wang"))

def friend(x,z):
    print(x, z, 'friend?')
    y=var()
    return conde((pair(x, z),), (pair(x,y), pair(y,z)), (friend(z, x),))

x=var()
res =run(1, x, friend(x, "Liao"))

print(res)

If-else?

I hate to ask this here, but I seem to be out of options, and it's turned out to be hard to google for this—

I'm trying to implement a goal that works like this:

def trimo(value, trimLevel, newValue):
    # give me value such that newValue <= trimLevel

    # "if value > trimLevel, newValue = trimLevel
    # else newValue = value"

    # almost but not quite--the second clause should only be used if the first is not
    return conde(
        [(gt, value, trimLevel), (eq, newValue, trimLevel)],
        [(eq, value, newValue)]
    )

This works, but I need the (eq, value, newValue) to be run only like an "else". I have a feeling I'm missing something more fundamental, as has often been the case when trying to teach myself scheme ;)

I think this is "condA"? But I'd be lost as to how to implement that myself :/

Any ideas? cc @lucaswiman :)

Stream Processing Questions

While working on #71, I've run into some recursion issues and noticed that lall uses earlyorder, which appears to pre-evaluate all the goals (and discard the resulting states?). If the goals are coming from a lazily-evaluated stream/generator, then it would seem as though earlyorder effectively undoes that—potentially causing problems for infinite streams/generators.

Clearly, if the goals are tuple-expressions, then the recursion thing isn't necessarily an issue, but it would still spoil the generator. Otherwise, if a single goal is a recursive generator, then earlyorder would absolutely break things.

On a similar note, why isn't all stream processing performed through generators? It seems possible to reorder goals—similar to how earlyorder does—by splitting the stream with tee and queuing the failed goal for later, no?

TypeError: 'Var' object is not subscriptable

Given this implementation (link):

def lefto(q, p, list):
        # give me q such that q is left of p in list
        # zip(list, list[1:]) gives a list of 2-tuples of neighboring combinations
        # which can then be pattern-matched against the query
        return membero((q,p), zip(list, list[1:]))

We get:

<ipython-input-49-52f501fbe475> in lefto(q, p, list)
      3         # zip(list, list[1:]) gives a list of 2-tuples of neighboring combinations
      4         # which can then be pattern-matched against the query
----> 5         return membero((q,p), zip(list, list[1:]))

TypeError: 'Var' object is not subscriptable

Using Python 3 and:

>>> kanren.__version__
'0.2.2'

Obfuscated exceptions/errors

While working with kanren, I've noticed that it's rather difficult to debug non-trivial errors due to how the exceptions are handled in goaleval, earlyorder, and potentially some other goal-processing functions.

Specifically, goaleval catches all exceptions and raises its own EarlyGoalError. This has the effect of removing vital traceback and type information about the actual source of an error.

Here's an interesting example that demonstrates another issue that's also related to the aforementioned:

from unification import var
from kanren import run, lall


class SomeException(Exception):
    pass


def bad_relation():
    def _bad_relation():
        raise SomeException("some exception")
    return (lall, (_bad_relation,))


run(0, var(), (bad_relation,))
>>> run(0, var(), (bad_relation,))
---------------------------------------------------------------------------
EarlyGoalError                            Traceback (most recent call last)
<ipython-input-72-49a12718352d> in <module>
----> 1 run(0, var(), (bad_relation,))

~/projects/code/python/logpy/kanren/core.py in run(n, x, *goals)
    238     (1,)
    239     """
--> 240     results = map(partial(reify, x), goaleval(lall(*goals))({}))
    241     return take(n, unique(results, key=multihash))
    242 

~/projects/code/python/logpy/kanren/core.py in lall(*goals)
     51     (2, 3)
     52     """
---> 53     return (lallgreedy, ) + tuple(earlyorder(*goals))
     54 
     55 

~/projects/code/python/logpy/kanren/core.py in earlyorder(*goals)
    158 
    159     if not good:
--> 160         raise EarlyGoalError()
    161     elif not bad:
    162         return tuple(good)

EarlyGoalError: 

In this case, beyond the information lost by goaleval's exception handling, earlyorder is completely dropping any and all information about the originating exception (by way of earlysafe).

If there are no fundamental objections, and/or requirements/issues I'm not addressing, I'll put in a PR to change earlyorder and goaleval so that they retain the originating exceptions.

Build issue

Invoking python setup.py install in a otherwise vanilla Python virtualenv (2.7.13) results in:

Processing dependencies for kanren==0.2.3
Searching for unification
Reading https://pypi.python.org/simple/unification/
Downloading https://pypi.python.org/packages/1c/26/432ea4a47aded7b0d64662fc265252da2b2a059f92af2eeb3321d60c9f8a/unification-0.2.2.tar.gz#md5=b2f1723d75b0f5c34a7e9be4137eafbf
Best match: unification 0.2.2
Processing unification-0.2.2.tar.gz
Writing /var/folders/gj/_4b9jvwj1qg2vcv231xvz5sr0000gq/T/easy_install-qGiQjt/unification-0.2.2/setup.cfg
Running unification-0.2.2/setup.py -q bdist_egg --dist-dir /var/folders/gj/_4b9jvwj1qg2vcv231xvz5sr0000gq/T/easy_install-qGiQjt/unification-0.2.2/egg-dist-tmp-O8KXW2
error: [Errno 2] No such file or directory: 'dependencies.txt'

(On Mac OS X)

Understanding user classes

I'm struggling a bit with user classes. I have this script: https://gist.github.com/t3db0t/2f31e4bcb103a168563b657ea510ee1c

The unification works, and I get the expected result (finding a device with a certain ID). However, when it prints out, I see that if the 'dummy' value is the same as any property values, those values all get overridden to the search value.

So this is fixable by providing a dummy value that would 'never' occur, but that's sketchy. I also am not quite clear on exactly what function the dummy values are performing? Like, why can't I just do source = Controller(0x0) and target = Controller(0x0) and leave out the with variables(*vars)?

Readme updates

The README (https://github.com/logpy/logpy/blob/master/README.md#extending-logpy-to-other-types) seems to make the assumption that the reader knows what unify() does already. (assumes prior knowledge)
A quick introduction (or a link) to what it does and its purpose would help the reader understand that section of the readme better. It would otherwise be better to use another (already introduced) dispatched function.

Also I was looking for a Performance section on the readme to know how expensive it is to do this form of pattern matching.

Package incompatible with python 3.4

Importing the module in python 3.4 gives the following error:

>>> from logpy import facts, parent
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/diwank/.envs/tw/lib/python3.4/site-packages/logpy/__init__.py", line 5, in <module>
    from core import run, eq, conde, membero
ImportError: No module named 'core'

It seems that the fix should be really simple, merely converting the imports to relative imports should do the trick. Happy to make a PR!

`appendo`

The miniKanren appendo solution depends on technology present in Scheme which is not accessible in Python. It also uses match, a generally useful macro.

The solution of this problem will bring up and inform the solution to a number of issues deep within the design of this project.

Index relations

Relations contain sets of facts. The relation is used to create a goal. When this goal is used it scans through this set of facts to find all matches to the input substitution. By replacing the set with a more complex data structure we could reduce the complexity of using relations. For example by assuming that all facts in relations are tuples of size n we could index the facts with n dicts and use those dicts to rapidly select the matching facts.

Problem with commutative

I may be misunderstanding commutative, but with the following code

from logpy import run, var, fact
from logpy.assoccomm import eq_assoccomm as eq
from logpy.assoccomm import commutative

op = 'op'
fact(commutative, op)

x1, x2, x3, x4 = (var("x1"), var("x2"), var("x3"), var("x4"))
pattern = (op, (op, (op, x1,x2),(op, (op, (op, x1,x3),(op, x2,x4)),(op, (op, x1,x4),(op, x2,x3)))),(op, (op, x1,x3),(op, (op, (op, x1,x2),(op, x3,x4)),(op, (op, x1,x4),(op, x2,x3)))))
expr = (op, (op, (op, 1,2),(op, (op, (op, 1,3),(op, 2,4)),(op, (op, 1,4),(op, 2,3)))),(op, (op, 1,4),(op, (op, (op, 1,2),(op, 3,4)),(op, (op, 1,3),(op, 2,4)))))
expr0 = (op, (op, (op, 1,2),(op, (op, (op, 1,3),(op, 2,4)),(op, (op, 1,4),(op, 2,3)))),(op, (op, 1,3),(op, (op, (op, 1,2),(op, 3,4)),(op, (op, 1,4),(op, 2,3)))))
print run(0, (x1,x2,x3,x4), eq(pattern, expr))
print run(0, (x1,x2,x3,x4), eq(pattern, expr0))

I would expect

((1, 2, 4, 3), )
((1, 2, 3, 4), (1, 3, 2, 4))

Instead, I get

()
((1,2,3,4),)

Improve conso and membero

Currently conso and membero are very limited in the kinds of deductions they can perform. The following fails with an early goal error:

>>> from logpy import *
>>> x, y, z = map(var, 'xyz')
>>> from logpy.goals import *
>>> run(1, [y], (conso, 1, x, y), (conso, 2, y, z))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Users/lucaswiman/opensource/logpy/logpy/core.py", line 241, in run
    results = map(partial(reify, x), goaleval(lall(*goals))({}))
  File "/Users/lucaswiman/opensource/logpy/logpy/core.py", line 61, in lall
    return (lallgreedy, ) + tuple(earlyorder(*goals))
  File "/Users/lucaswiman/opensource/logpy/logpy/core.py", line 167, in earlyorder
    raise EarlyGoalError()
logpy.core.EarlyGoalError
>>> run(0, q, (conso, 1, x, q), (conso, 2, y, x), (eq, y, ())) 
((1, 2),)

Clojure's core.logic handles this correctly:

user=> (require 'clojure.core.logic)
nil
user=> (load "logic_tutorial/tut1")
nil
user=> (in-ns 'logic-tutorial.tut1)
#<Namespace logic-tutorial.tut1>
logic-tutorial.tut1=> conso
#<logic$conso clojure.core.logic$conso@eaaf669>
logic-tutorial.tut1=> (run* [q] (fresh [x y] (conso 1 x q) (conso 2 y x)))
((1 2 . _0))
logic-tutorial.tut1=> (run* [q] (fresh [x y] (conso 1 x q) (conso 2 y x) (== y [])))
((1 2))

core.logic does fail on membero though:

logic-tutorial.tut1=> (run* [q], (membero 1 q), (membero 2 q))

StackOverflowError   clojure.lang.KeywordLookupSite$1.get (KeywordLookupSite.java:45)

I think the same lcons trick that core.logic uses might work for sets as well, which would be extremely useful.

SWI-Prolog seems to handle these cases correctly, though still requires a cut to avoid a seemingly infinite search:

?- member(1, X), member(2, X), length(X, 2), !.
X = [1, 2].

logpy? minikanren? recursive function?

Greetings,

I am building a triple store in python based on my previous work in Scheme. Using Scheme I rely on minikanren to do the query (like datomic does) because it allows to express recursive queries quiet nicely.

Here is an example, this will build a representation of vertical and horizontal frame buffers and query for the lead file-buffers. I have omitted the database setup part, the query part:

                (defrel (verticalo yiwen frame out)
                  (fresh (left right)
                    (whereo yiwen frame 'type 'vertical-split)
                    (whereo yiwen frame 'left left)
                    (whereo yiwen frame 'right right)
                    (disj
                     (file-buffero yiwen left out)
                     (file-buffero yiwen right out))))

                (defrel (horizontalo yiwen frame out)
                  (fresh (top bottom)
                    (whereo yiwen frame 'type 'horizontal-split)
                    (whereo yiwen frame 'top top)
                    (whereo yiwen frame 'bottom bottom)
                    (disj
                     (file-buffero yiwen top out)
                     (file-buffero yiwen bottom out))))

                (defrel (file-buffero yiwen frame out)
                  (conda
                   ((verticalo yiwen frame out))
                   ((horizontalo yiwen frame out))
                   ((== frame out))))

                (run* q
                  (file-buffero yiwen 'frame0 q))

The full code is at sr.ht.

Anyway, the thing is relations are definition using defrel and look like normal procedures. Is it possible to achieve something similar with logpy? I found nothing from this spirit while skimming through the documentation.

TIA!

CLP based on LP

Have the author considered to extend the logic programming with constraint solving abilities?

Matche - (LISPer needed)

Appendix B and C (particularly C) of William Byrd's thesis introduce matche a very useful pattern matching macro. Having this as a Python function would allow many things to be written more concisely and more consistently with miniKanren. Of course, we don't have macros, not to worry.

I suggest the syntax [a, b] instead of (a . b) found in miniKanren. We don't use lists for anything else and this might be important enough. Like run, variables will need to be constructed ahead of time. It is reasonable to assume that anything in a matche is unevaluated like (foo, a, b) instead of foo(a, b).

To be honest the definitions scare me a bit. The surrounding examples are good though. My hope is that someone more familiar with Scheme can manage this without too much sweat. This would make writing many things in LogPy much easier.

This is, to date, the highest value issue.

How to find all ancestors?

I have a parent-child relation called parent and a subset of a family tree as facts. I'm trying to write a goal to find all of the ancestors of somebody.

from kanren import run, var, Relation, facts, lall, lany

parent = Relation()

family_info = facts(parent,
    ('Abraham', 'Ishmael'), ('Hagar', 'Ishmael'),
    ('Abraham', 'Isaac'), ('Sarah', 'Isaac'),
    ('Isaac', 'Esau'), ('Rebecca', 'Esau'),
    ('Isaac', 'Jacob'), ('Rebecca', 'Jacob'),
    ('Jacob', 'Reuben'), ('Jacob', 'Simeon'), ('Jacob', 'Levi'), ('Jacob', 'Judah'),
    ('Leah', 'Reuben'), ('Leah', 'Simeon'), ('Leah', 'Levi'), ('Leah', 'Judah'),
    ('Jacob', 'Dan'), ('Jacob', 'Naphtali'), ('Bilnah', 'Dan'), ('Bilnah', 'Naphtali'),
    ('Jacob', 'Gad'), ('Jacob', 'Asher'), ('Zilpah', 'Gad'), ('Zilpah', 'Asher'),
    ('Jacob', 'Issachar'), ('Jacob', 'Zebulun'), ('Jacob', 'Dinah'),
    ('Leah', 'Issachar'), ('Leah', 'Zebulun'), ('Leah', 'Dinah'),
    ('Jacob', 'Joseph'), ('Jacob', 'Benjamin'), ('Rachel', 'Joseph'), ('Rachel', 'Benjamin'),
    ('Joseph', 'Manasseh'), ('Joseph', 'Ephraim'), ('Asenath', 'Manasseh'), ('Asenath', 'Ephraim')
)


def ancestor(x, z):
    y = var()
    return \
    (lany,
        (parent, x, z),
        (lall,
            (parent, x, z),
            (ancestor, y, x)
        )
    )


ancestors = var()

results = run(0, ancestors, (ancestor, ancestors, 'Ephraim'))
print(f'Number of results: {len(results)}')
for result in results:
    print(result)

I thought that the recursive call to ancestor with a new variable would have helped me find more than just the parents (e.g. grandparents), but it didn't work. Right now, it only prints out "Joseph", and "Asenath". I would have expected to also get "Jacob", "Rachel", "Isaac", "Rebecca", "Abraham", and "Sarah".

What am I doing wrong?

Arithmetic Goals and Var

Create functions addo, mulo, gto, lto, etc....
Create class ArithVar(Var) and class Lexpr(object) that implement these operators using python syntax like __add__ and __eq__

run(0, x, x > 5, y == x + 4, y < 10)

Strategies for graph traversal

Issue #1 says that we should replace chain with interleave. While this choice is generally wise it is still a choice. The pattern by which logpy searches for solutions should be programmable. We should implement programmable strategies for graph traversal.

How to write "not unify"

In minikanren, we can say a variable does not unify with something with =/=. Can we do it here?

Issue when running logpyZebra.py

I tried running the zebra problem example and got the following error:
~/Documents/dev/logic/logpyZebra.py

Traceback (most recent call last):
File "/Users/cjm/Documents/dev/logic/logpyZebra.py", line 58, in
(membero, (var(), var(), var(), 'zebra', var()), houses)
File "/Users/cjm/Documents/dev/logic/logpy/core.py", line 53, in lall
return (lallgreedy, ) + tuple(earlyorder(*goals))
File "/Users/cjm/Documents/dev/logic/logpy/core.py", line 155, in earlyorder
groups = groupby(earlysafe, goals)
File "/Users/cjm/Documents/dev/logic/toolz/itertoolz.py", line 93, in groupby
dkey(item)
File "/Users/cjm/Documents/dev/logic/logpy/core.py", line 138, in earlysafe
goaleval(goal)
File "/Users/cjm/Documents/dev/logic/logpy/core.py", line 300, in goaleval
return find_fixed_point(evalt, goal)
File "/Users/cjm/Documents/dev/logic/logpy/core.py", line 285, in find_fixed_point
cur = f(cur)
File "/Users/cjm/Documents/dev/logic/logpy/util.py", line 84, in evalt
return t0
File "/Users/cjm/Documents/dev/logic/logpyZebra.py", line 9, in lefto
return membero((q,p), zip(list, list[1:]))
TypeError: 'Var' object has no attribute 'getitem'

Relation bug?

def test_logic():
    from logpy import run,var,Relation,fact
    valido = Relation()
    fact(valido,"a","b")
    fact(valido,"b","a")
    x = var()
    assert run(0,x, valido(x,x)) == ()

E       assert ('a', 'b') == ()
E         Left contains more items, first extra item: 'a'

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.