Logical unification in Python
Project description
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
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
logical-unification-0.4.6.tar.gz
(31.7 kB
view details)
File details
Details for the file logical-unification-0.4.6.tar.gz.
File metadata
- Download URL: logical-unification-0.4.6.tar.gz
- Upload date:
- Size: 31.7 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.2 CPython/3.9.16
File hashes
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 | 908435123f8a106fa4dcf9bf1b75c7beb309fa2bbecf277868af8f1c212650a0 |
|
| MD5 | c13e0fd23faadca1c894c226778883ff |
|
| BLAKE2b-256 | c0738dac224c46949e61bc52558384138a2b79fa0b7be10367074862fe9994dd |
