Logical Unification

Logical unification in Python, extensible via dispatch.

Installation

Using pip:

pip install logical-unification

To install from source:

git clone git@github.com:pythological/unification.git
cd unification
pip install -r requirements.txt

Tests can be run with the provided Makefile:

make check

Examples

unification has built-in support for unifying most Python data types via the function unify:

>>> from unification import *
>>> unify(1, 1)
{}
>>> unify(1, 2)
False
>>> x = var()
>>> unify((1, x), (1, 2))
{~x: 2}
>>> unify((x, x), (1, 2))
False

Unifiable objects containing logic variables can also be reified using reify:

>>> reify((1, x), {x: 2})
(1, 2)

And most Python data structures:

>>> unify({"a": 1, "b": 2}, {"a": x, "b": 2})
{~x: 1}
>>> unify({"a": 1, "b": 2}, {"a": x, "b": 2, "c": 3})
False
>>> from collections import namedtuples
>>> ntuple = namedtuple("ntuple", ("a", "b"))
>>> unify(ntuple(1, 2), ntuple(x, 2))
{~x: 1}

Custom classes can be made "unifiable" with the unifiable decorator:

@unifiable
class Account(object):
    def __init__(self, id, name, balance):
        self.id = id
        self.name = name
        self.balance = balance

>>> data = [Account(1, 'Alice', 100),
            Account(2, 'Bob', 0),
            Account(2, 'Charlie', 0),
            Account(2, 'Denis', 400),
            Account(2, 'Edith', 500)]
>>> id, name, balance = var('id'), var('name'), var('balance')
>>> [unify(Account(id, name, balance), acct) for acct in data]
[{~name: 'Alice', ~balance: 100, ~id: 1},
{~name: 'Bob', ~balance: 0, ~id: 2},
{~name: 'Charlie', ~balance: 0, ~id: 2},
{~name: 'Denis', ~balance: 400, ~id: 2},
{~name: 'Edith', ~balance: 500, ~id: 2}]
>>> [unify(Account(id, name, 0), acct) for acct in data]
[False,
{~name: 'Bob', ~id: 2},
{~name: 'Charlie', ~id: 2},
False,
False]

unification also supports function dispatch through pattern matching:

>> from unification.match import *
>>> n = var('n')

@match(0)
def fib(n):
    return 0


@match(1)
def fib(n):
    return 1


@match(n)
def fib(n):
    return fib(n - 1) + fib(n - 2)

>>> map(fib, [0, 1, 2, 3, 4, 5, 6, 7, 8, 0])
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

The pattern matching can be fairly complex:

>> name, amount = var('name'), var('amount')

@match({'status': 200, 'data': {'name': name, 'credit': amount}})
def respond(name, amount):
    balance[name] +=  amount


@match({'status': 200, 'data': {'name': name, 'debit': amount}})
def respond(name, amount):
    balance[name] -= amount


@match({'status': 404})
def respond():
    print("Bad Request")

See the full example in the examples directory.

Performance and Reliability

unification's current design allows for unification and reification of nested structures that would otherwise break the Python stack recursion limit. It uses a generator-based design to "stream" the unifications and reifications.

Below are some stack vs. stream benchmarks that demonstrate how well the stream-based approach scales against the stack-based approach in terms of unifying and reifying deeply nested lists containing integers. These benchmarks were generated from the tests in tests/test_benchmarks.py using CPython 3.7.3.

Stack vs. stream benchmarks

-------------------------------------------------------------------------------- benchmark 'reify_chain size=10': 2 tests -------------------------------------------------------------------------------
Name (time in us)                   Min                 Max               Mean            StdDev             Median               IQR                Outliers  OPS (Kops/s)            Rounds  Iterations
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_reify_chain_stack[10]      41.0790 (1.0)      545.1940 (3.20)     52.9087 (1.07)     9.7964 (1.04)     50.8650 (1.08)     6.4301 (8.37)      11815;10849       18.9005 (0.93)     260164           1
test_reify_chain_stream[10]     42.4410 (1.03)     170.5540 (1.0)      49.3080 (1.0)      9.3993 (1.0)      47.2400 (1.0)      0.7680 (1.0)      14962;102731       20.2807 (1.0)      278113           1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------ benchmark 'reify_chain size=1000': 1 tests -----------------------------------------
Name (time in ms)                          Min      Max     Mean  StdDev  Median     IQR  Outliers      OPS  Rounds  Iterations
-------------------------------------------------------------------------------------------------------------------------------
test_reify_chain_stream_large[1000]     7.7722  28.2579  10.0723  2.5087  9.4899  0.3106    70;155  99.2820    1528           1
-------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------- benchmark 'reify_chain size=300': 2 tests --------------------------------------------------------------------------
Name (time in ms)                   Min                Max              Mean            StdDev            Median               IQR            Outliers       OPS            Rounds  Iterations
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_reify_chain_stack[300]      1.5183 (1.0)      22.1821 (1.19)     1.9826 (1.0)      1.5511 (1.16)     1.7410 (1.0)      0.0801 (1.0)       144;684  504.3878 (1.0)        7201           1
test_reify_chain_stream[300]     1.7059 (1.12)     18.6020 (1.0)      2.1237 (1.07)     1.3389 (1.0)      1.9260 (1.11)     0.1020 (1.27)      118;585  470.8745 (0.93)       6416           1
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

--------------------------------------------------------------------------------- benchmark 'reify_chain size=35': 2 tests --------------------------------------------------------------------------------
Name (time in us)                    Min                 Max                Mean             StdDev              Median                IQR             Outliers  OPS (Kops/s)            Rounds  Iterations
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_reify_chain_stream[35]     129.2780 (1.0)      868.1510 (1.02)     190.0433 (1.11)     36.2784 (1.41)     179.5690 (1.08)     21.5360 (2.30)     1535;1455        5.2620 (0.90)      26072           1
test_reify_chain_stack[35]      150.7850 (1.17)     853.7920 (1.0)      170.5166 (1.0)      25.7944 (1.0)      165.8500 (1.0)       9.3530 (1.0)      3724;5480        5.8645 (1.0)       81286           1
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------- benchmark 'reify_chain size=5000': 1 tests ------------------------------------------
Name (time in ms)                           Min      Max     Mean  StdDev   Median     IQR  Outliers      OPS  Rounds  Iterations
---------------------------------------------------------------------------------------------------------------------------------
test_reify_chain_stream_large[5000]     46.9073  86.9737  52.9724  6.6919  49.6787  3.9609     68;68  18.8778     292           1
---------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------------- benchmark 'unify_chain size=10': 2 tests -------------------------------------------------------------------------------
Name (time in us)                   Min                 Max                Mean             StdDev              Median               IQR            Outliers  OPS (Kops/s)            Rounds  Iterations
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_unify_chain_stream[10]     77.6280 (1.0)      307.9130 (1.0)       86.7625 (1.0)      17.5355 (1.20)      82.7525 (1.0)      1.7290 (1.0)      809;1736       11.5257 (1.0)       15524           1
test_unify_chain_stack[10]      92.9890 (1.20)     309.8770 (1.01)     104.2017 (1.20)     14.6694 (1.0)      101.0160 (1.22)     4.2368 (2.45)    3657;6651        9.5968 (0.83)      73379           1
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

------------------------------------------- benchmark 'unify_chain size=1000': 1 tests ------------------------------------------
Name (time in ms)                           Min      Max     Mean  StdDev   Median     IQR  Outliers      OPS  Rounds  Iterations
---------------------------------------------------------------------------------------------------------------------------------
test_unify_chain_stream_large[1000]     27.3518  65.5924  31.1374  4.2563  29.5148  3.5286     38;35  32.1158     496           1
---------------------------------------------------------------------------------------------------------------------------------

------------------------------------------------------------------------- benchmark 'unify_chain size=300': 2 tests --------------------------------------------------------------------------
Name (time in ms)                   Min                Max              Mean            StdDev            Median               IQR            Outliers       OPS            Rounds  Iterations
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_unify_chain_stream[300]     3.6957 (1.0)      13.1876 (1.0)      4.4439 (1.0)      1.0719 (1.42)     4.2080 (1.0)      0.2410 (1.67)        51;95  225.0298 (1.0)        1114           1
test_unify_chain_stack[300]      4.2952 (1.16)     13.4294 (1.02)     4.7732 (1.07)     0.7555 (1.0)      4.6623 (1.11)     0.1446 (1.0)        36;136  209.5024 (0.93)       2911           1
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

--------------------------------------------------------------------------------- benchmark 'unify_chain size=35': 2 tests ---------------------------------------------------------------------------------
Name (time in us)                    Min                   Max                Mean             StdDev              Median                IQR            Outliers  OPS (Kops/s)            Rounds  Iterations
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_unify_chain_stream[35]     285.6880 (1.0)        934.9690 (1.0)      324.5402 (1.0)      40.8338 (1.0)      319.8520 (1.0)      20.4375 (1.0)      962;1159        3.0813 (1.0)       24331           1
test_unify_chain_stack[35]      345.2770 (1.21)     1,088.3650 (1.16)     407.9067 (1.26)     52.2263 (1.28)     396.6640 (1.24)     20.6560 (1.01)    2054;3027        2.4515 (0.80)      37594           1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

--------------------------------------------- benchmark 'unify_chain size=5000': 1 tests ---------------------------------------------
Name (time in ms)                            Min       Max      Mean   StdDev    Median      IQR  Outliers     OPS  Rounds  Iterations
--------------------------------------------------------------------------------------------------------------------------------------
test_unify_chain_stream_large[5000]     555.2733  754.9897  605.4949  50.6124  591.1251  61.4030       2;2  1.6515      26           1
--------------------------------------------------------------------------------------------------------------------------------------

Legend:
  Outliers: 1 Standard Deviation from Mean; 1.5 IQR (InterQuartile Range) from 1st Quartile and 3rd Quartile.
  OPS: Operations Per Second, computed as 1 / Mean

About

This project is a fork of unification.

Development

Install the development dependencies:

$ pip install -r requirements.txt

Set up pre-commit hooks:

$ pre-commit install --install-hooks

Package profile

logical-unification

Releases

Release table

PyPI Downloads

Dependencies

Details

Project URLs

Dependencies

Package description