[thebeast] r728 committed - started to describe ptree using logic
codesite...@google.com
Author: sebastian.riedel
Date: Sun Mar 21 13:01:44 2010
Log: started to describe ptree using logic
http://code.google.com/p/thebeast/source/detail?r=728
Modified:
/branches/thefuture-modules/thebeast-apps/src/main/scala/org/riedelcastro/thebeast/apps/DependencyParsing.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/Playground.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/TheBeastEnv.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/booleans/BooleanTerm.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/doubles/DoubleTerm.scala
=======================================
---
/branches/thefuture-modules/thebeast-apps/src/main/scala/org/riedelcastro/thebeast/apps/DependencyParsing.scala
Sun Mar 21 11:26:30 2010
+++
/branches/thefuture-modules/thebeast-apps/src/main/scala/org/riedelcastro/thebeast/apps/DependencyParsing.scala
Sun Mar 21 13:01:44 2010
@@ -80,6 +80,7 @@
sum += marginals.belief(FunAppVar(link,(h,1))).belief(true)
}
println(sum)
+ println(ptree(link,token,0,LessThan(Tokens)).asLogic)
}
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/Playground.scala
Fri Sep 25 23:42:36 2009
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/Playground.scala
Sun Mar 21 13:01:44 2010
@@ -36,7 +36,7 @@
println(env(k(1)(2) + x))
println(Quantification(IntAdd, x, f(x), 0).unroll)
- println(intSum(Ints) {x => f(x)})
+ //println(intSum(Ints) {x => f(x)})
println(forall(Ints) {x => f(x) === 1})
println(sum(Ints) {x => {f(x) === 1} @@})
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/TheBeastEnv.scala
Sun Mar 21 11:26:30 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/TheBeastEnv.scala
Sun Mar 21 13:01:44 2010
@@ -15,16 +15,10 @@
object TheBeastImplicits extends TheBeastEnv {
}
-trait TheBeastEnv {
- private var varCount = 0;
-
+trait TheBeastEnv extends QuantificationShortCuts {
val Bools = booleans.Bools
//val Bools = Values(false,true)
- private def createVariable[T](values: Values[T]): Var[T] = {
- varCount += 1;
- values.createVariable("x_" + varCount.toString)
- }
def unit(key: Term[Any]*) = UnitVector(key: _*)
@@ -35,7 +29,7 @@
def ptree[V](edges: Term[FunctionValue[(V, V), Boolean]],
vertices: Term[FunctionValue[V, Boolean]],
root: Term[V],
- order: Term[FunctionValue[(V, V), Boolean]]) =
SpanningTreeConstraint(edges,vertices,root,order)
+ order: Term[FunctionValue[(V, V), Boolean]]) =
SpanningTreeConstraint(edges, vertices, root, order)
implicit def string2varbuilder(name: String) = new {
def <~[T](values: Values[T]) = Var(name, values)
@@ -150,7 +144,7 @@
def apply(t: Term[Any]) = BooleanFunApp(fun, t)
}
- def genericTerm2booleanFunAppBuilder[T](fun: Term[FunctionValue[T,
Boolean]]) = new (Term[T] => BooleanFunApp[T]) {
+ implicit def genericTerm2booleanFunAppBuilder[T](fun:
Term[FunctionValue[T, Boolean]]) = new (Term[T] => BooleanFunApp[T]) {
def apply(t: Term[T]) = BooleanFunApp(fun, t)
}
@@ -234,9 +228,15 @@
def $$(term: BooleanTerm) = AlchemyIndicator(term)
- def intSum[T](values: Values[T])(formula: Var[T] => Term[Int]) = {
- val variable = createVariable(values)
- Quantification(IntAdd, variable, formula(variable), 0)
+}
+
+trait QuantificationShortCuts {
+ private var varCount = 0;
+
+
+ private def createVariable[T](values: Values[T]): Var[T] = {
+ varCount += 1;
+ values.createVariable("x_" + varCount.toString)
}
def sum[T](values: Values[T])(formula: Var[T] => DoubleTerm) = {
@@ -246,6 +246,20 @@
def sum[T1, T2](values1: Values[T1], values2: Values[T2])(formula:
(Var[T1], Var[T2]) => DoubleTerm): QuantifiedSum[T1] =
sum(values1) {x1 => sum(values2) {x2 => formula(x1, x2)}}
+
+
+ def prod[T](values: Values[T])(formula: Var[T] => DoubleTerm) = {
+ val variable = createVariable(values)
+ QuantifiedMultiplication(variable, formula(variable))
+ }
+
+ def prod[T1, T2](values1: Values[T1], values2: Values[T2])(formula:
(Var[T1], Var[T2]) => DoubleTerm): QuantifiedMultiplication[T1] =
+ prod(values1) {x1 => prod(values2) {x2 => formula(x1, x2)}}
+
+
+ def prod[T1, T2, T3](values1: Values[T1], values2: Values[T2], values3:
Values[T3])(
+ formula: (Var[T1], Var[T2], Var[T3]) => DoubleTerm):
QuantifiedMultiplication[T1] =
+ prod(values1) {x1 => prod(values2) {x2 => prod(values3) {x3 =>
formula(x1, x2, x3)}}}
def vectorSum[T](values: Values[T])(formula: Var[T] => VectorTerm) = {
@@ -253,29 +267,32 @@
QuantifiedVectorSum(variable, formula(variable))
}
- def vectorSum[T1, T2](values1: Values[T1], values2: Values[T2])(formula:
(Var[T1], Var[T2]) => VectorTerm): QuantifiedVectorSum[T1] =
+ def vectorSum[T1, T2](values1: Values[T1], values2: Values[T2])
+ (formula: (Var[T1], Var[T2]) => VectorTerm):
QuantifiedVectorSum[T1] =
vectorSum(values1) {x1 => vectorSum(values2) {x2 => formula(x1, x2)}}
- def vectorSum[T1, T2, T3](v1: Values[T1], v2: Values[T2], v3:
Values[T3])(formula: (Var[T1], Var[T2], Var[T3]) => VectorTerm):
QuantifiedVectorSum[T1] =
+ def vectorSum[T1, T2, T3](v1: Values[T1], v2: Values[T2], v3: Values[T3])
+ (formula: (Var[T1], Var[T2], Var[T3]) =>
VectorTerm): QuantifiedVectorSum[T1] =
vectorSum(v1) {x1 => vectorSum(v2, v3) {(x2, x3) => formula(x1, x2,
x3)}}
- def vectorSum[T1, T2, T3, T4](v1: Values[T1], v2: Values[T2], v3:
Values[T3], v4: Values[T4])(formula: (Var[T1], Var[T2], Var[T3], Var[T4])
=> VectorTerm): QuantifiedVectorSum[T1] =
+ def vectorSum[T1, T2, T3, T4](v1: Values[T1], v2: Values[T2], v3:
Values[T3], v4: Values[T4])
+ (formula: (Var[T1], Var[T2], Var[T3],
Var[T4]) => VectorTerm): QuantifiedVectorSum[T1] =
vectorSum(v1) {x1 => vectorSum(v2, v3, v4) {(x2, x3, x4) =>
formula(x1, x2, x3, x4)}}
- def forall[T](values: Values[T])(formula: Var[T] => Term[Boolean]) = {
+ def forall[T](values: Values[T])(formula: Var[T] => BooleanTerm) = {
val variable = createVariable(values)
- Quantification(And, variable, formula(variable), true)
+ Forall(variable, formula(variable))
}
- def forall[T1, T2](values1: Values[T1], values2: Values[T2])(formula:
(Var[T1], Var[T2]) => Term[Boolean]) = {
- val v1 = createVariable(values1)
- val v2 = createVariable(values2)
- Quantification(And, v1, Quantification(And, v2, formula(v1, v2),
true), true)
+ def forall[T1, T2](v1: Values[T1], v2: Values[T2])
+ (formula: (Var[T1], Var[T2]) => BooleanTerm):
Forall[T1] = {
+ forall(v1) {x1 => forall(v2) {x2 => formula(x1, x2)}}
}
- def exists[T](values: Values[T])(formula: Var[T] => Term[Boolean]) = {
- val variable = createVariable(values)
- Quantification(Or, variable, formula(variable), false)
- }
+ def forall[T1, T2, T3](v1: Values[T1], v2: Values[T2], v3: Values[T3])
+ (formula: (Var[T1], Var[T2], Var[T3]) =>
BooleanTerm): Forall[T1] = {
+ forall(v1) {x1 => forall(v2) {x2 => forall(v3) {x3 => formula(x1, x2,
x3)}}}
+ }
+
}
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/booleans/BooleanTerm.scala
Tue Mar 16 19:15:51 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/booleans/BooleanTerm.scala
Sun Mar 21 13:01:44 2010
@@ -4,6 +4,8 @@
import doubles.Indicator
import functions._
import org.riedelcastro.thebeast.util.{Util, SimpleNamed}
+import java.lang.String
+
/**
* @author Sebastian Riedel
*/
@@ -17,6 +19,8 @@
def <~>(rhs: BooleanTerm) = EquivalenceApp(this, rhs)
+ def unary_! = negate
+
def ground(env: Env): BooleanTerm
@@ -287,6 +291,29 @@
override def simplify = this
}
+
+case class Forall[T](override val variable: Var[T], override val formula:
BooleanTerm)
+ extends Quantification(Constant(And), variable, formula,
Constant(true)) with BooleanTerm {
+ override lazy val unroll = {
+ val env = new MutableEnv
+ Conjunction(variable.values.map(value => {env += variable -> value;
formula.ground(env)}).toSeq)
+ }
+
+ def upperBound = unroll.upperBound
+
+ override def ground(env: Env) = unroll.ground(env)
+
+ override def simplify = Forall(variable,formula.simplify)
+
+ def flatten = this
+
+ def moveInNegation: BooleanTerm = this
+
+ def negate: BooleanTerm = NotApp(this)
+
+
+ override def toString: String
= "{forall %s: %s}".format(variable,formula)
+}
case class ImpliesApp(lhs: BooleanTerm, rhs: BooleanTerm) extends
Disjunction(Seq(NotApp(lhs), rhs)) {
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala
Sun Mar 21 11:26:30 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/combinatorics/SpanningTreeConstraint.scala
Sun Mar 21 13:01:44 2010
@@ -25,6 +25,26 @@
if (constant.isDefined) DoubleConstant(constant.get) else simplified
}
+ def asLogic: DoubleTerm = {
+ import TheBeastImplicits._
+ val domain =
vertices.values.asInstanceOf[FunctionValues[V,Boolean]].domain
+ val uniqueHead = forall(domain,domain,domain) {
+ (h,i,o)=> vertices(i) && vertices(h) && vertices(o) && edges(h,i)
~> !edges(o,i)}
+ val dominates = Predicate("dominates",domain x domain)
+ val linkAndDominates = forall(domain,domain) {
+ (h,i) => vertices(i) && vertices(h) && edges(h,i) ~> dominates(h,i)}
+ val transitive = forall(domain,domain,domain){
+ (h,m,g)=> vertices(h) && vertices(m) && vertices(g) &&
dominates(h,m) && edges(m,g) ~> dominates(h,g)}
+ val acyclic = forall(domain) {
+ i => vertices(i) ~> !dominates(i,i)}
+ val projective1 = forall(domain,domain,domain) {
+ (h,m,i)=> vertices(h) && vertices(m) && vertices(i) && edges(h,m) &&
order(h,i) && order(i,m) ~> dominates(h,i)}
+ val projective2 = forall(domain,domain,domain) {
+ (h,m,i)=> vertices(h) && vertices(m) && vertices(i) && edges(h,m) &&
order(m,i) && order(i,h) ~> dominates(h,i)}
+ ${uniqueHead && linkAndDominates && transitive && acyclic &&
projective1 && projective2}
+ }
+
+
def upperBound = 1.0
def subterms = Seq(edges, vertices, root)
=======================================
---
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/doubles/DoubleTerm.scala
Mon Mar 15 10:46:14 2010
+++
/branches/thefuture-modules/thebeast-core/src/main/scala/org/riedelcastro/thebeast/env/doubles/DoubleTerm.scala
Sun Mar 21 13:01:44 2010
@@ -135,6 +135,22 @@
override def simplify = QuantifiedSum(variable,formula.simplify)
}
+
+case class QuantifiedMultiplication[T](override val variable: Var[T],
override val formula: DoubleTerm)
+ extends Quantification(Constant(Times), variable, formula,
Constant(1.0)) with DoubleTerm {
+ override lazy val unroll = {
+ val env = new MutableEnv
+ Multiplication(variable.values.map(value => {env += variable -> value;
formula.ground(env)}).toSeq)
+ }
+
+ def upperBound = unroll.upperBound
+
+ override def ground(env: Env) = unroll.ground(env)
+
+ override def simplify =
QuantifiedMultiplication(variable,formula.simplify)
+}
+
+
case class Indicator(boolTerm: BooleanTerm) extends
FunApp(Constant(CastBoolToDouble), boolTerm)
with DoubleTerm {
def upperBound = if (boolTerm.upperBound) 1.0 else 0.0