I am impressed by the logic language Picat and a recent presentation by Peter Alvaro “Three Things I Wish I Knew When I Started Designing Languages“.
Update 3: November 2022. The language MiniZinc turns out to fulfill the goals of Parasat language. Among its many features the one that stands out when comparing with the goal of Parasat is that MiniZinc adopts relational semantics in the sense that I pointed to below. For the details see the 2009 paper The Proper Treatment of Undefinedness in Constraint Languages by Stuckey and Frisch and the 2013 MiniZinc with Functions by Stuckey and Tack.
Update 2: William Byrd (@webyrd) the author of miniKanren recommended that I use the faster-miniKanren implementation for exploring relational programming. He also recommended this paper: A unified approach to solving seven programming problems (functional pearl) Here is a quote from the paper that illuminates the intent of the Parasat language described below, but using miniKanren terminology: “These interpreters are written as relations in the constraint logic programming language miniKanren. Each interpreter relates two arguments: an expression expr to be evaluated, and the value val to which expr evaluates. These arguments may be only partially complete, containing logic variables representing unknown parts. Our miniKanren implementation will use constraint solving and search to fill in the logic variables with expressions and values consistent with the semantics of Racket. By placing logic variables representing unknowns in different positions within the expr and val arguments we can express a wide range of interesting queries, which provides the flexibility needed to solve the variety of challenges we pose.”
Update 1: Feedback on the Picat Google Group drew attention to the similarities with the ideas in this article with the motivation and goals of miniKanren.
I learned Prolog while at university in the early 80’s and its been refreshing to learn Picat, a language that builds on the Prolog tradition and Datalog, a simplification of Prolog.
At university I was surprised, and disappointed, by the distance between the predicates of mathematical logic and those of Prolog. For example the Prolog interpreter was unable to give the answer
X=1.454545, Y= 4.9090909
to the simultaneous equations 3x + 4y=24 and 5x + 3y=22 expressed in Prolog as this predicate:
simultaneous(X,Y) :- times(3,X,ThreeX),times(4,Y,FourY), plus(ThreeX, FourY, PlusThreeXFourY),equals(PlusThreeXFourY,24), times(5,X,FiveX),times(3,Y,ThreeY), plus(FiveX, ThreeY, PlusFourXThreeY),equals( PlusFourXThreeY ,22)
With the advances made by Picat, I am inspired to rekindle my dream of an ‘ideal’ predicate-based language. Lets call this language Parasat.
Parasat (Kazakh language) means intellect or understanding.
glosb.com definition, google translate definition
Assumed knowledge. This post assumes that the reader has a basic familiarity with Prolog, Datalog and Picat programming languages and with predicates, logic programming and constraint programming.
To a first approximation, Parasat is Picat with:
- all predicates required to be bi-directional (unless a parameter is constrained as “Free”
- all syntactic forms mapped back to predicates
- the constraint solver folded back into the predicate-based core of the language
Parasat has the following three high level features:
- Predicates are reversible and encapsulate the relation among all parameters. All predicate parameters are both input and output
- Everything is a predicate, irrespective of surface form. In other words, all language features are syntactic sugar for predicates. This includes type declarations, formulas, relations, functions and constraints,
- “plug and play” search strategies. Solutions are found by heuristically and transparently applying a “plug and play” range of predicate satisfaction, predicate decomposition and search strategies including pattern matching, unification with backtracking and constraint solving.
At the present time Parasat is an idea for a language. This article sketches out these three language features.
Predicates are reversible.
Parasat’s reversible predicates encapsulate the relation among predicate parameters. This enables the unification of otherwise diverse functions. For example in Parasat, powers, logarithms and roots are all unified in this predicate:
pow(X,Y,XpowY): if X,Y, and XpowY are instantiated, returns true if X**Y==XpowY, false otherwise. If one of the variables is not instantiated then it is instantiated to the missing value. If two or more of the parameters are not instantiated then the instantiation of the free parameters is delegated to the constraint solver.
More specific predicates may be defined using “<=>”, which reads as “may be mutually defined as”. These derived predicates are also reversible.
exp(X,eraisedtothepowerX) <=> pow(X=e, Y=X, XpowY=eraisedtothepowerX)
sqrt(X,SqrtX) <=> pow(X=SqrtX ,Y=2,XpowY=X)
sqr(X,SqrX) <=> pow(X=X, Y=2, XpowY=SqrX)
log(X,LogtothebaseeofX) <=> pow(X=e, Y=LogtothebaseeofX, XpowY=X)
log(B,X, LogtothebaseBofX) <=> pow(X=B, Y=LogtothebaseBofX,XpowY=X)
log10(X,Logtothebase10ofX) <=> pow(X=10,Y=Logtothebase10ofX,XpowY=X)
log2(X,Logtothebase2ofX) <=> pow(X=2,Y=Logtothebase2ofX,XpowY=X)
As you can see from the examples above, Parasat uses named parameters.
Naturally, in the same way addition and subtraction may be unified by the addedto/3 predicate.
addedto(X,Y,XaddedtoY): if X,Y, and XaddedtoY are instantiated, returns true if X+Y==XaddedtoY, false otherwise. If one of the parameters is not instantiated then it is instantiated to the missing value. If two or more of the parameters are not instantiated then the instantiation of the free parameters is delegated to the constraint solver.
And multiplication and division, as times/3.
times(X,Y,XtimesY): if X,Y, and XtimesY are instantiated, returns true if X*Y==XtimesY, false otherwise. If one of the parameters is not instantiated then it is instantiated to the missing value. If two or more of the parameters are not instantiated then the instantiation of the free parameters is delegated to the constraint solver.
And binding and equality testing can be unified, as
equals(X,Y): if X and Y are instantiated returns true if X==Y, false otherwise. If one of the values is not instantiated then it is bound to the same value as the other one. If neither X nor Y are instantiated then instantiation of the free parameters is delegated to the constraint solver.
Everything is a predicate
Parasat unifies infix notation, functions, constraints, and predicates. This can be illustrated by the following equivalent forms of the times(X,Y,XtimesY) predicate:
XtimesY = times(X,Y) X = times(XtimesY,Y) Y = times(X,XtimesY) X,Y = times(XtimesY) XtimesY,X,Y = times()
and with the following definitions added:
A / B <=> times(XtimesY=A,Y=B) A * B <=> times(X=A,Y=B)
the times(X,Y,XtimesY) predicate acquires the following additional equivalent forms:
Y = XtimesY / X XtimesY = X * Y
“plug and play” search strategies
Parasat’s transparent application of different search strategies is illustrated by comparison of the Picat “Send More Money” program:
% PICAT SEND+MORE=MONEY
import cp.
sendmory =>
Vars = [S,E,N,D,M,O,R,Y], % generate variables
Vars :: 0..9,
all_different(Vars), % generate constraints
S #!= 0,
M #!= 0,
1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E
#= 10000*M + 1000*O + 100*N + 10*E + Y,
solve(Vars), % search
writeln(Vars).
with the equivalent Parasat program:
% PARASAT SEND+MORE=MONEY sendmory(S:S,E:E,N:N,D:D,M:M,O:O,R:R,Y:Y) & writeln(S,E,N,D,M,O,R,Y). sendmory(S,E,N,D,M,O,R,Y) <=> type(Var:S, Domain:1..9) & type(Var:E, Domain:0..9) & type(Var:N, Domain:0..9) & type(Var:D, Domain:0..9) & type(Var:M, Domain:1..9) & type(Var:O, Domain:0..9) & type(Var:R, Domain:0..9) & type(Var:Y, Domain:0..9) & all_different(Set:[S,E,N,D,M,O,R,Y]) & 1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E = 10000*M + 1000*O + 100*N + 10*E + Y.
Parasat does not require an explicit “solve” instruction because the all_different predicate delegates finding missing values to the constraint solver. It transparently satisfies the sendmory() predicate using constraint programming to find the solution: [9,5,6,7,1,0,8,2] .
Note that in Parasat:
1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E = 10000*M + 1000*O + 100*N + 10*E + Y
is syntactic sugar for:
times(X:M, Y:1000, XtimesY:T1) &
times(X:O, Y:100, XtimesY:T2) &
times(X:R, Y:10, XtimesY:T3) &
addedto(X:T1, Y:T2, XaddedtoY:T4) &
addedto(X:T3, Y:T4, XaddedtoY:T5) &
addedto(X:E, Y:T5, XaddedtoY:T6) &
times(X:S, Y:1000, XtimesY:T7) &
times(X:E, Y:100, XtimesY:T8) &
addedto(X:T7, Y:T8, XaddedtoY:T9) &
times(X:N, Y:10, XtimesY:T10) &
addedto(X:T9, Y:T10, XaddedtoY:T11) &
addedto(X:D, Y:T11, XaddedtoY:T12) &
addedto(X:T6, Y:T12, XaddedtoY:T13) &
times(X:M, Y:10000, XtimesY:T14) &
times(X:O, Y:1000, XtimesY:T15) &
addedto(X:T14, Y:T15, XaddedtoY:T16) &
times(X:N, Y:100, XtimesY:T17) &
addedto(X:T16, Y:T17, XaddedtoY:T18) &
times(X:E, Y:10, XtimesY:T19) &
addedto(X:T18, Y:T19, XaddedtoY:T20) &
addedto(X:Y, Y:T20, XaddedtoY:T21) &
equals(X:T13, Y:T21)
Conclusion
This brief sketch captures key ideas for an ideal predicate language “Parasat”. Your feedback is welcome in the comments below.