ztangent / julog.jl Goto Github PK
View Code? Open in Web Editor NEWA Julia package for Prolog-style logic programming.
License: Apache License 2.0
A Julia package for Prolog-style logic programming.
License: Apache License 2.0
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
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!
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
Hello there,
I was trying member
example like this,
resolve(@julog(member(b, [a, b, c])),Clause[])
Is this a bug or feature?
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/
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:
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.
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
?
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.
This looks fantastic btw. Just what I was looking for to learn logic programming.
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?)
@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!
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!
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.