ztangent/julog.jl

A Julia package for Prolog-style logic programming.

julog.jl's Issues

Engine does not run through all available variants

I tried to implement simple zebra puzzle. After several hours of struggling through I decided to implement simple check test: generate all permutations on 4 elements

clauses = @julog [
     tuples(T) <<= 
        eq(T, [_,_,_,_]) &
        subset([1,2,3,4], T),
        
    eq(A,A)',
    member(X, [X | Y])',
    member(X, [Y | YS]) <<= member(X, YS),
    subset([],_)',
    subset([X | XS], L) <<= member(X,L) & subset(XS,L)
]
goals = @julog [tuples(T)]
resolve(goals,clauses)[2]

However the output was

8-element Array{Any,1}:
 {T => [1, 2, 3, 4]}
 {T => [1, 2, 4, 3]}
 {T => [1, 3, 2, 4]}
 {T => [1, 4, 2, 3]}
 {T => [2, 1, 3, 4]}
 {T => [2, 1, 4, 3]}
 {T => [3, 1, 2, 4]}
 {T => [4, 1, 2, 3]}

Instead of all 24 permutations
I wrote very similar code on Prolog to compare results:

tuples(T) :-
    T = [_,_,_,_],
    subset([1,2,3,4],T).

subset([],_).

subset([X | XS], L) :-
    member(X,L),
    subset(XS,L).

?- tuples(T)

And got right result

T = [1, 2, 3, 4]
T = [1, 2, 4, 3]
T = [1, 3, 2, 4]
T = [1, 4, 2, 3]
T = [1, 3, 4, 2]
T = [1, 4, 3, 2]
T = [2, 1, 3, 4]
T = [2, 1, 4, 3]
T = [3, 1, 2, 4]
T = [4, 1, 2, 3]
T = [3, 1, 4, 2]
T = [4, 1, 3, 2]
T = [2, 3, 1, 4]
T = [2, 4, 1, 3]
T = [3, 2, 1, 4]
T = [4, 2, 1, 3]
T = [3, 4, 1, 2]
T = [4, 3, 1, 2]
T = [2, 3, 4, 1]
T = [2, 4, 3, 1]
T = [3, 2, 4, 1]
T = [4, 2, 3, 1]
T = [3, 4, 2, 1]
T = [4, 3, 2, 1]

This shows that Julog engine does not run through all available variants

Too large an expression?

Hi @ztangent,

I was recently trying to put together a demonstration of logical programming using the 4 color theorem to color a map of the US. Although the code is relatively simple, the logical expressions are quite large; they're show below:

color_pairs = @julog [
    n(red, green)<<=true,
    n(green, red)<<=true,
    n(blue, red)<<=true,
    n(yellow, red)<<=true,
    n(red, blue)<<=true,
    n(green, blue)<<=true,
    n(blue, green)<<=true,
    n(yellow, green)<<=true,
    n(red, yellow)<<=true,
    n(green, yellow)<<=true,
    n(blue, yellow)<<=true,
    n(yellow, blue)<<=true
]

map_layout_all = @julog colors(AK, AL, AR, AZ, CA, CO, CT, DC, DE, FL, GA, HI, IA, ID, IL, IN, KS, KY, LA, MA, MD, ME, MI, MN, MO, MS, MT, NC, ND, NE, NH, NJ, NM, NV, OH, OK, OR, PA, RI, SC, SD, TN, TX, UT, VA, VT, WA, WI, WV, WY)<<=
    n(AL, FL) & n(AL, GA) & n(AL, MS) & n(AL, TN) &
    n(AR, LA) & n(AR, MS) & n(AR, MO) & n(AR, OK) & n(AR, TN) & n(AR, TX) &
    n(AZ, CA) & n(AZ, NM) & n(AZ, NV) & n(AZ, UT) &
    n(CA, OR) & n(CA, NV) &
    n(CO, KS) & n(CO, NE) & n(CO, NM) & n(CO, OK) & n(CO, UT) & n(CO, WY) &
    n(CT, MA) & n(CT, NY) & n(CT, RI) &
    n(DE, MD) & n(DE, NJ) & n(DE, PA) &
    n(FL, GA) &
    n(GA, NC) & n(GA, SC) & n(GA, TN) &
    n(ID, MT) & n(ID, NV) & n(ID, OR) & n(ID, UT) & n(ID, WA) & n(ID, WY) &
    n(IL, IA) & n(IL, IN) & n(IL, KY) & n(IL, MO) & n(IL, WI) &
    n(IN, KY) & n(IN, MI) & n(IN, OH) &
    n(IA, MN) & n(IA, MO) & n(IA, NE) & n(IA, SD) & n(IA, WI) &
    n(KS, MO) & n(KS, NE) & n(KS, OK) &
    n(KY, MO) & n(KY, OH) & n(KY, TN) & n(KY, VA) & n(KY, WV) &
    n(LA, MS) & n(LA, TX) &
    n(ME, NH) &
    n(MD, PA) & n(MD, VA) & n(MD, WV) &
    n(MA, NH) & n(MA, NY) & n(MA, RI) & n(MA, VT) &
    n(MI, OH) & n(MI, WI) & n(MI, MN) & #MI and MN share a water border
    n(MN, ND) & n(MN, SD) & n(MN, WI) &
    n(MS, TN) &
    n(MO, NE) & n(MO, OK) & n(MO, TN) &
    n(MT, ND) & n(MT, SD) & n(MT, WY) &
    n(NE, SD) & n(NE, WY) &
    n(NV, OR) & n(NV, UT) &
    n(NH, VT) &
    n(NJ, NY) & n(NJ, PA) &
    n(NM, OK) & n(NM, TX) &
    n(NY, PA) & n(NY, VT) & n(NY, RI) & #NY and RI share a water border 
    n(NC, SC) & n(NC, TN) & n(NC, VA) &
    n(ND, SD) &
    n(OH, PA) & n(OH, WV) &
    n(OK, TX) &
    n(OR, WA) &
    n(PA, WV) &
    n(SD, WY) &
    n(TN, VA) &
    n(UT, WY) &
    n(VA, WV) &
    n(DC, VA) & n(DC, MD)

goal_all = @julog colors(AK, AL, AR, AZ, CA, CO, CT, DC, DE, FL, GA, HI, IA, ID, IL, IN, KS, KY, LA, MA, MD, ME, MI, MN, MO, MS, MT, NC, ND, NE, NH, NJ, NM, NV, OH, OK, OR, PA, RI, SC, SD, TN, TX, UT, VA, VT, WA, WI, WV, WY)
map_soln_all = resolve(goal_all, vcat(color_pairs, map_layout_all), mode=:any, search=:dfs)

When I first ran this without any options set in resolve, the solver failed to finish after about an hour, and considering the size of the search space (~4^51 I believe) this didn't seem unreasonable. I then hoped that setting mode=:any and search=:dfs would solve in a reasonable amount of time for a single solution, but I also had to halt the solver after a half an hour had passed.

I wanted to see if this second attempt (trying to find any solution via depth-first search) is one you would have expected to finish in a "reasonable" amount of time, or if this is simply too large a problem even for those options.

Also as a side note, it seems like there's no validity check with the resolve options, and any invalid option choice will just "fail" silently by using the default settings. Am I reading the code correctly for these cases?

Thanks as always!

License?

Hi,

thank you for the great Julia package! Unfortunately I could not find any information about its license. Would it be possible to provide a LICENSE.md file?

Thank you,
Falco

`member` usage

Hello there,

I was trying member example like this,

resolve(@julog(member(b, [a, b, c])),Clause[])

Is this a bug or feature?

Use of Julog to parse first order formulas in usual binary logic

Retired teacher (maths, & computer science), born in 1947. Living in the North of France (Boulogne sur Mer).
Writing, as a hobby, some stuff on the web for educational purposes.
http://gilles.dubois10.free.fr/

References on breadth-first logic programming

The README states:

cut causes the current goal to succeed and suppresses all other goals. However, this does not have the same effects as in Prolog because Julog uses breadth-first search during SLD-resolution, unlike most Prolog implementations, which use depth-first search.

No reason for this unusual choice is given, however I'm aware that there are good reasons why one might prefer breadth-first semantics. Three doctoral dissertations explore this choice; in the first and last, the researchers have implemented a breadth-first LPL, while the second explores expressions in Haskell using Wadler's 'list of successes' paradigm:

1. Richard McPhee, 2000. Compositional Logic Programming. DPhil thesis, Programming Research Group, University of Oxford.
2. Silvijia Seres, 2001. The Algebra of Logic Programming. DPhil thesis, Programming Research Group, University of Oxford. http://silvija.net/0000OxfordPublications/seres_thesis.pdf
3. Görkem Paçaci, 2017. Representation of Compositional Relational Programs. PhD thesis, Department of Informatics and Media, Uppsala University.

The issue that drives the preference comes from algebraic semantics: if you regard the semantics of a query as a collection of satisfiers, left-to-right depth-first search gives conjunction a bias where (A,B) might not terminate if A gives an unbounded search, even if B has only finitely many satisfiers consistent with A; the requirement that the semantics lacks this kind of biases is called fairness, and breadth-first search makes this easier to achieve.

It might be worth adding a paragraph to the README mentioning the idea of fairness in logic-programming semantics and gesturing at the literature.

Error: LoadError: $Expr(:incomplete, "...") & How to extend `builtins`?

Hi, I am working on a Reasoning System, it has rules written in SWI-Prolog: nal.pl.
I want to use it in Julia, but there're some predicates like member、nonvar and subtract are not in Julog's builtins.

When I use @prolog to parse nal.pl:

using Julog

rules = @prolog """
     prolog rules in nal.pl
"""

I got an Error:

Expr
  head: Symbol incomplete
  args: Array{Any}((1,))
    1: String "incomplete: premature end of input"
ERROR: LoadError: syntax error in Julog term at $(Expr(:incomplete, "incomplete: premature end of input"))
Stacktrace:
 [1] error(s::String)
   @ Base .\error.jl:33
 [2] parse_term(expr::Expr, esc::typeof(esc))
   @ Julog C:\Users\Axier\.julia\packages\Julog\V6gVn\src\parse.jl:38
 [3] parse_julog(expr::Expr, esc::Function)
   @ Julog C:\Users\Axier\.julia\packages\Julog\V6gVn\src\parse.jl:111
in expression starting at D:\codes\Junars\src\rules\julogrules.jl:3
in expression starting at D:\codes\Junars\src\rules\julogrules.jl:3

How can I make these rules work in Julog?

Resolve does not check for valid optional arguments

Following up from #9, resolve does not actively check to make sure optional arguments are valid, instead checking for specific options (such as :dfs for search) and otherwise using the default option. This can lead to silent "failures" where the user may not know resolve is using different settings than the user intended.

More Documentation or Examples

This looks fantastic btw. Just what I was looking for to learn logic programming.

Parsing for equivalence rules?

I'm trying to recreate in Julog Prolog statements like:

sister(X,Y):-
  parent(Z,X),
  parent(Z,Y),
  female(X),
  X\=Y.

The last term is required or else people can be their own sisters. My initial thought was to translate the last term as X!=Y and the expression was parsed without error, but returned incorrect results (saying that an individual did not have a sister when they did).

My solution has been to use not(unifies(X,Y)) but this seems a little verbose and I'm not sure it's truly equivalent to what I'm looking for. Can the != syntax be implemented without breaking the package, or is using unifies the recommended approach? If != is not the intended approach, can the failure be made more apparent (a throw perhaps?)

Term construction via template?

@ztangent I'm not sure if I'm just missing an easier way to do this (or if there are more Julog-ian ways to do it) but I've been trying to construct some sort of "template logic" that I can then populate with more specific terms. As a short description of what I mean, I've prepared some code 😄 (It does use some Julia 1.5 syntactic sugar though... ;funcs instead of funcs=funcs)

funcs = Dict()
funcs[:sin] = sin
funcs[:square] = x -> x * x

op_def(func,input,comp,output) = @julog $(comp)($(func)($input),$output)

sin_def = op_def(
    :sin,
    π/2,
    Symbol("=="),
    1
)

square_def = op_def(
    :square,
    5,
    Symbol("<="),
    25
)

@assert resolve(sin_def, Clause[]; funcs)[1]==true
@assert resolve(square_def, Clause[]; funcs)[1]==true
@assert resolve(@julog(and(:sin_def, :square_def)), Clause[]; funcs)[1]==true

The idea is more programmatic generation of Julog logic and I didn't see examples like this in the documentation. There were examples on how to use custom functions, but without being able to modify a template, it's impossible to create the and expression with just the funcs argument. Does that make sense, or would it help to elaborate?

As a side note, I've been curious on your vision for Julog. Is the idea to keep it as close to the original Prolog as is feasible, or is greater integration into Julia the goal?

Thanks as always!

Enhancement proposal: use Metatheory.jl

Me and @philzook58 worked on an EGraph implementation in pure Julia: https://github.com/0x0f0f0f/Metatheory.jl
It may be really interesting to write a backend for Julog using Metatheory.EGraphs and Metatheory.EGraphs.AbstractAnalysis to see if it simplifies the Julog codebase and outperforms the original implementation.
You may want to take a read at this paper https://dl.acm.org/doi/pdf/10.1145/3434304
Using Julog the other way, as an analysis for Metatheory.jl (applying rewrite rules only when a goal can be solved) would prove fundamental and useful for a symbolic mathematics/theorem proving framework in pure Julia.
Thanks for your package btw!

Parsing dot character Issue in `convert_prolog_to_julog`

Hey there! Recently I had an issue with Julog trying to parse,

using Julog
s = """state("minnesota","mn","st. paul",4076.0e+3,84.4e+3,32,"minneapolis","st. paul","duluth","Bloomington")."""
Julog.convert_prolog_to_julog(s)

which outputs;

[
"state(\"minnesota\",\"mn\",\"st <<= true", 
"paul\",4076.0e+3,84.4e+3,32,\"minneapolis\",\"st <<= true",
"paul\",\"duluth\",\"bloomington\") <<= true"
]

It seems the issue is caused by the . character in the string. However, using the original ' character for wrapping strings(such as using it as 'st. paul') also causes parsing issue that says;

Base.Meta.ParseError("character literal contains multiple characters")

where, convert_prolog_to_julog seems to parse correctly as follows;

state('alabama','al','montgomery',3894.0e+3,51.7e+3,22,'birmingham','mobile','montgomery','huntsville') <<= true

However, Meta.parse attempting to read ' literal seems to be the cause.

Thanks in advance.