bomba - a prototype Answer Set Programming Scala DSL
Bomba is an Answer Set Programming dialect in the form of a Scala DSL. It is intended, currently, as a prototype to experiment with possible syntax and semantic variants, as well as language integration.
Usage
-
- If your build system is m2-compatible, you can now get bomba directly out of Central.
Just add it to your dependencies:
- SBT:
libraryDependencies += org.bomba-lang % bomba % 0.3.1
- Maven:
<dependency> <groupId>org.bomba-lang</groupId> <artifactId>bomba</artifactId> <version>0.3.1</version> </dependency>
- Otherwise:
mvn clean package
- Add the resulting JAR to the build path of your project.
- If your build system is m2-compatible, you can now get bomba directly out of Central.
Just add it to your dependencies:
- Add:
import org.bomba_lang.proto._
to your Scala import statements.
-
IMPORTANT: add the
macro-paradise
compiler plugin to your Maven/SBT build - as described in the macro documentation.
Syntax
The syntax is similar to other Answer Set Programming dialects.
A literal is of the form
name(x1,...,xn)
-name(x1,...,xn)
where n >= 0
(if n=0
, the parenthesis are optional), and x1,...,xn
are of the type Any
. -
means "strong negation".
An xm
(1 <= m <= n
) of type Symbol (e.g. 'X ), is a variable.
A rule is of the form
hP1 v ... v hPl :- (bP1,...,bPm,~nbP1,...,~nbPn)
hP1 ∨ ... ∨ hPl ⟵ bP1 ∧ ... ∧ bPm ∧ ~nbP1 ∧ ... ∧ ~nbPn
where hP1,...,hPl, bP1,...,bPm, nbP1,...,nbPn
are literals. ~
means "default negation".
A program is a Scala code block of the form
@bomba
val progName = {
r1
...
rn
}
where r1,...,rn
are rules. Note that:
- the rules are treated as standard Scala expressions, i.e. they must be either in
separate lines, or separated with
;
when on the same line. - the names of the literals "shadow" any same-named
val
s and/ordef
s in the program's local scope.
Note: yes, this means you can use Unicode symbols for logical operators in your program!
Semantics
Semantics depend on the solver used. The current reference implementation, org.bomba_lang.proto.NaiveSolver
, uses standard
disjunctive semantics, with the Ferraris and Lifschitz resolution variant for strong negation. To generate all answer sets, use:
program.solve
The idiomatic way of interfacing your logic programs with the rest of your code is to define your "oracle" program, and then inject the data you wish to provide in the solve method, e.g.:
@bomba
val oracle = {...}
@bomba
val data = {...}
oracle.solve(data)
Examples
Here's the source from the main class of the demo project, to give you an idea of the syntax and semantics:
package org.bomba_lang.bomba_demo
import org.bomba_lang.proto._
object Demo {
def main(args: Array[String]): Unit = {
@bomba
val prog1 = { z(1, 2) }
println(prog1)
@bomba
val prog2 = {
y v z
}
println(prog2.solve)
@bomba
val prog3 = {
rain :- wet
wet
}
println(prog3.solve)
println("canonical program extension")
@bomba
val r0 = {
rain :- wet
}
println(r0.solve)
@bomba
val r1 = {
wet
}
println(r0.solve(r1))
println("-------------------")
println("canonical program extension with default negation")
@bomba
val rn0 = {
rain :- wet & ~sprinkler
}
println(r0.solve)
@bomba
val rn1 = {
wet
}
println(rn0.solve(rn1))
@bomba
val rn2 = {
wet
sprinkler
}
println(rn0.solve(rn2))
println("-------------------")
println("variables")
@bomba
val varProg = {
x(1)
y(2)
z('X, 'Y) :- x('X) & y('Y)
}
println("Ungrounded: " + varProg)
val varProgGround = new GroundProgram(varProg)
println("Grounded: " + varProgGround)
println("Result: " + varProgGround.solve)
println("-------------------")
println("Constraints")
@bomba
val constProg = {
x
Nil :- x
}
println(constProg)
println(constProg.solve) //empty set (*no* answer sets)
println("-------------------")
println("\"Formal\" notation")
@bomba
val formalProg = {
a ∨ b ⟵ x ∧ y ∧ z
⊥ ⟵ z ∧ d
}
println(formalProg)
}
}
Why "bomba"?
Two reasons:
- more obviously, it's a lame reference to a "logic bomb" (since it's a logic programming DSL - geddit, geddit?)
- less obviously, the name alludes to the cryptologic "bomba", a machine invented by Marian Rejewski (member of the Polish Cipher Bureau) for making the process of breaking Enigma ciphers more efficient.
Comments? Issues?
All welcome.