Chapter 1 Basic usage: Algebraic terms and Pattern matching
1.1 Algebraic terms in Java – %gom
// import class.module.types.* whith lower case names
import algebraic.logic.types.*;
public class Algebraic {
%gom { // algebraic signature definition
module Logic
imports int String
abstract syntax
/* P, Q and implies are 'constructors'
for the 'sort' Proposition */
Proposition = P(t:Term)
| Q(t:Term)
| implies(p1:Proposition, p2:Proposition)
Term = nat(i:int)
| var(name:String)
| plus(t1:Term, t2:Term)
}
public static void main(String[] args) {
// ` (backquote) allows to build algebraic terms
Proposition p = `implies(P(plus(nat(1),nat(2))), Q(var("x")));
System.out.println(p);
// constant time equality check thanks to maximal sharing
Proposition p1 = `Q(nat(3));
Proposition p2 = `Q(nat(3));
System.out.println(p1 == p2);
}
}
polux@huggy$ tom Algebraic.t && javac Algebraic.java && java Algebraic
implies(P(plus(nat(1),nat(2))),Q(var("x")))
true
1.2 A pretty printer – %match
import matching.logic.types.*;
public class Matching {
%gom {
module Logic
imports int String
abstract syntax
Proposition = P(t:Term)
| Q(t:Term)
| implies(p1:Proposition, p2:Proposition)
Term = nat(i:int)
| var(name:String)
| plus(t1:Term, t2:Term)
}
public static String prettyProposition(Proposition p) {
// the sort of p is inferred out of the patterns
%match(p) {
// variable instances are accessed with `
P(t) -> { return "P(" + prettyTerm(`t) + ")"; }
Q(var("x")) -> { System.out.println("I was here !"); }
/* since the previous rule does not break the flow (with a return statement),
tom still looks for matching patterns in their declaration order */
Q(t) -> { return "Q(" + prettyTerm(`t) + ")"; }
implies(p1,p2) -> { return "(" + prettyProposition(`p1)
+ " => " + prettyProposition(`p2) + ")"; }
}
return ""; // this case never occurs, but javac isn't aware of it
}
public static String prettyTerm(Term t) {
%match(t) {
nat(i) -> { return Integer.toString(`i); }
var(x) -> { return `x; }
plus(t1,t2) -> { return prettyTerm(`t1) + " + " + prettyTerm(`t2); }
}
return "";
}
public static void main(String[] args) {
Proposition p = `implies(P(plus(nat(1),nat(2))), Q(var("x")));
System.out.println(prettyProposition(`p));
}
}
polux@huggy$ tom Matching.t && javac Matching.java && java Matching
I was here !
(P(1 + 2) => Q(x))
1.3 Antipatterns
import anti.cars.types.*;
public class Anti {
%gom {
module Cars
abstract syntax
Vehicle = car(interior:Colors, exterior:Colors, type:Type)
| bike()
Type = ecological()
| polluting()
Colors = red()
| green()
}
/* anti-pattern matching works just like pattern matching
except that we may introduce complement symbols, denoted by '!',
in the patterns
*/
private static void searchCars(Vehicle subject){
%match(subject){
!car(x,x,_) -> {
System.out.println(
"- Not a car, or car with different colors:\t\t" + `subject);
}
car(x,!x,!ecological()) -> {
System.out.println(
"- Car that is not ecological and that does not\n"+
" have the same interior and exterior colors: \t\t" + `subject);
}
car(x@!green(),x,ecological()) -> {
System.out.println(
"- Ecological car and that has the same interior\n"+
" and exterior colors, but different from green: \t" + `subject);
}
}
}
public static void main(String[] args) {
Vehicle veh1 = `bike();
Vehicle veh2 = `car(red(),green(),ecological());
Vehicle veh3 = `car(red(),red(),ecological());
Vehicle veh4 = `car(green(),green(),ecological());
Vehicle veh5 = `car(green(),red(),polluting());
searchCars(veh1);
searchCars(veh2);
searchCars(veh3);
searchCars(veh4);
searchCars(veh5);
}
}
polux@huggy$ tom Anti.t && javac Anti.java && java Anti
- Not a car, or car with different colors: bike()
- Not a car, or car with different colors: car(red(),green(),ecological())
- Ecological car and that has the same interior
and exterior colors, but different from green: car(red(),red(),ecological())
- Not a car, or car with different colors: car(green(),red(),polluting())
- Car that is not ecological and that does not
have the same interior and exterior colors: car(green(),red(),polluting())
1.4 Computing a fixpoint – %strategy, RepeatId
import rmdoubles.mylist.types.*;
import tom.library.sl.*; // imports the runtime strategy library
public class RmDoubles {
// includes description of strategy operators for tom (RepeatId here)
%include { sl.tom }
%gom {
module mylist
imports String
abstract syntax
StrList = strlist(String*)
}
/* we define a 'user strategy' which should be seen as
a rewrite system (composed of only one rule here) */
%strategy Remove() extends `Identity() {
visit StrList { (X*,i,Y*,i,Z*) -> { return `strlist(X*,i,Y*,Z*); } }
}
public static void main(String[] args) throws VisitFailure {
StrList l = `strlist("framboisier","eric","framboisier","remi",
"remi","framboisier","rene","bernard");
System.out.println(l);
/* We compute a fixpoint for the rewrite system 'Remove'
applied in head of l thanks to the strategy 'RepeatId'
which takes another strategy (here Remove) as an
argument. */
System.out.println(`RepeatId(Remove()).visit(l));
}
}
polux@huggy$ tom RmDoubles.t && javac RmDoubles.java && java RmDoubles
strlist("framboisier","eric","framboisier","remi","remi","framboisier","rene","bernard")
strlist("framboisier","eric","remi","rene","bernard")
1.5 An expression evaluator – %strategy, InnerMostId
import eval.mydsl.types.*;
import tom.library.sl.*;
public class Eval {
%include { sl.tom }
%gom {
module mydsl
imports int String
abstract syntax
Expr = val(v:int)
| var(n:String)
| plus(Expr*)
| mult(Expr*)
}
/* EvalExpr is a rewrite system which simplifies expressions.
It is meant to be applied on any sub-expression of a bigger one,
not only in head. */
%strategy EvalExpr() extends Identity() {
visit Expr {
plus(l1*,val(x),l2*,val(y),l3*) -> { return `plus(l1*,l2*,l3*,val(x + y)); }
mult(l1*,val(x),l2*,val(y),l3*) -> { return `mult(l1*,l2*,l3*,val(x * y)); }
plus(v@val(_)) -> { return `v; }
mult(v@val(_)) -> { return `v; }
}
}
public static void main(String[] args) throws VisitFailure {
Expr e = `plus(val(2),var("x"),mult(val(3),val(4)),var("y"),val(5));
/* We choose to apply the rewrite system in an innermost way
(aka. call by value). The InnermostId strategy does the
job and stops when a fixpoint is reached.
Since the visit method of strategies returns a Visitable,
we have to cast the result. */
Expr res = (Expr) `InnermostId(EvalExpr()).visit(e);
System.out.println(e + "\n" + res);
}
}
polux@huggy$ tom Eval.t && javac Eval.java && java Eval
plus(val(2),var("x"),mult(val(3),val(4)),var("y"),val(5))
plus(var("x"),var("y"),val(19))
1.6 Variable Collector – %strategy with mutable parameters
import collect.logic.types.*;
import tom.library.sl.*;
import java.util.LinkedList;
import java.util.HashSet;
public class Collect {
%include { sl.tom }
/* Since strategies arguments (Collection c here)
have to be seen as algebraic terms by tom, we
include the tom's java Collection description */
%include { util/types/Collection.tom }
%gom {
module logic
imports String
abstract syntax
Term = var(name:String)
| f(t:Term)
Prop = P(t: Term)
| implies(l:Prop, r:Prop)
| forall(name:String, p:Prop)
}
/* This strategy takes a java Collection as an argument
and performs some side-effect (add). */
%strategy CollectVars(Collection c) extends `Identity() {
visit Term { v@var(_) -> { c.add(`v); } }
}
public static void main(String[] args) throws VisitFailure {
Prop p = `forall("x", implies(implies(P(f(var("x"))), P(var("y"))),P(f(var("y")))));
/* We choose an HashSet as a collection and we
apply the collector to the proposition p
in a TopDown way */
HashSet result = new HashSet();
`TopDown(CollectVars(result)).visit(p);
System.out.println("vars: " + result);
}
}
polux@huggy$ tom Collect.t && javac Collect.java && java Collect
vars: [var("x"), var("y")]
1.7 Collecting free variables – µ operator, composed strategies
import advanced.logic.types.*;
import tom.library.sl.*;
import java.util.LinkedList;
public class Advanced {
%include { sl.tom }
%include { util/types/Collection.tom }
%gom {
module logic
imports String
abstract syntax
Term = var(name:String)
| f(t:Term)
Prop = P(t: Term)
| implies(l:Prop, r:Prop)
| forall(name:String, p:Prop)
}
/* - If the strategy encounters 'forall name, ...', then it
returns the identity.
- If it encounters 'name', then it adds its position to the collection c.
- By default, it fails. (extends Fails) */
%strategy CollectFree(String name, Collection c)
extends Fail() {
visit Prop { p@forall(x,_) -> {
if(`x == name)
return `p; } }
visit Term { v@var(x) -> {
if(`x == name) c.add(getEnvironment().getPosition()); } }
}
private static LinkedList<Position>
collectFreeOccurences(String name, Prop p)
throws VisitFailure {
LinkedList res =
new LinkedList();
/* This strategy means:
- try to apply CollectFree on the current term
- if it worked then stop here
- else apply yourself (mu operator) on all the
subterms of the current term */
`mu(MuVar("x"), Choice(CollectFree(name,res),All(MuVar("x")))).visit(p);
return res;
}
public static void main(String[] args)
throws VisitFailure {
Prop p = `forall("x", implies(implies(P(f(var("x"))), P(var("y"))),P(f(var("y")))));
System.out.println("free occurences of x: " + collectFreeOccurences("x",p));
System.out.println("free occurences of y: " + collectFreeOccurences("y",p));
}
}
polux@huggy$ tom Advanced.t && javac Advanced.java && java Advanced
free occurences of x: []
free occurences of y: [[2, 1, 2, 1], [2, 2, 1, 1]]