Оглавление

Предисловие

Мозаика

Алгебраические структуры

Полугруппа

Моноид:

Игра жизнь

Анализ Java кода.

Основные понятия

Системы, переписывающие правила и стратегии

Интерпретатор командной строки

Дерево предметных областей

Java API - начнем не с Hello, world.

Тривиальное преобразование: xyz

Добавляем свою Базу Фактов

Передача информации с помощью пропозициональных переменных.

Более систематическое введение

Встроенные термы

Примитивные типы данных

Списки

Множества

Java-объекты

Пропозициональные переменные

Составные термы

Правила

Множества правил

Импорт

Последовательность применения

Let и Where выражения

Системы

Домены

Что дальше


Предисловие


TermWare - это система символьного программирования, предназначенная для встраивания в Java-приложения. Вычисления основанны на переписывающих правилах с действиями, что позволяет элегантно совместить логический и императивный стили программирования. В этом руководстве пошагово описываются основные элементы языка и Java API TermWare. Для ознакомления, полезными также представляются следующие документы:

Мозаика

Несколько высокоуровневых примеров, которые иллюстрируют язык TermWare. Мы не будем здесь ничего подробно объяснять - просто покажем несколько строк кода, для того, что бы у Вас создалось первое впечатление. Более или менее систематическое введение начнется в следующей главе.

Алгебраические структуры

Полугруппа

Полугруппа - это нечто, обладающее ассоциативностью.



domain(algebra,
system(SemiGroup,default,
ruleset( ($x*$y)*$z -> $x*($y*$z) ),
FirstTop)
);

Моноид:

А моноид - это полугруппа с единицей


domain(algebra,

system(Monoid,default,
ruleset(
import(SemiGroup),
$x*One -> $x,
One*$x -> $x
),
FirstTop)

);


Пора показать что-то более жизненное:

Игра жизнь



domain(examples,
system(Life1,
javaFacts(Life1DB,"ua.kiev.gradsoft.TermWareDemos.Life.Life1Facts"),
ruleset(
# $T - set of pairs to test.
{l($i,$j):$T} [ n($i,$j)==3 ] -> $T [ putCell($i,$j) ],
{l($i,$j):$T} [ n($i,$j)==2 ] -> $T
[ existsCell($i,$j) ? putCell($i,$j) : removeCell($i,$j)] ,

{l($i,$j):$T} [ n($i,$j)>3||n($i,$j)< 2 ] -> $T [ removeCell($i,$j) ],

{ } -> checkEmpty($T) [ [showGeneration(), generateNextTestSet($T) ] ],

checkEmpty({$x:$Y}) -> { $x:$Y },

checkEmpty({}) -> END

),
FirstTop)

);



Или что-то полезное :

Анализ Java кода.

Как найти в программе типичную программистскую ошибку, например игнорирование исключений, т. е. код, соответствующий следующему образцу:


          

try {
.....
}catch(...){ }



С помощью следующей системы:




domain(examples,
system(JECheck,
javaFacts(JECheckDB,"ua.kiev.gradsoft.TermWareDemos.jsa.JECheckFacts"),
ruleset(
Catch($formalParameter, Block([]))->PROBLEM
[found("empty cath statement")]
),
BottomUp
) );


Теперь, как и обещали, перейдем к более систематическому описанию: проиллюстрируем основные понятия языка на примерах, впрочем все еще оставляя низкоуровневые детали на потом.

Основные понятия

Это глава даст нам необходимый базис для того, что бы мы могли перейти к главе 3, где начнется самое интересное.


Системы, переписывающие правила и стратегии

Итак, основным объектом в TermWare является система термов. Что это такое: с точки зрения логики, это четверка < Name, Ruleset, Facts, Strategy >, где:

Зачем нам эти системы нужны ? - что бы интепритировать наборы переписывающих правил. (ruleset).

А что такое переписывающее правило ? - в простейшем случае это выражение типа x->y , которое переписывает терм x в y .

А что такое терм ? - это некоторое символьное выражение. Само понятие терма пришло из математической логики, где принято следующеее определение:

Фактически любое символьное выражение, которое можно записать на бумаге, можно выразить и в виде терма. TermWare в основном следует этому определению, добавляя к множеству базовых термов еще объекты примитивных типов (строки, числа) и инкапсулированные Java-объекты. Для Java-программиста терм выглядит как объект, наследуемый от Term


Пользоваться функциональной нотацией типа fi(x1 ... xn) не всегда удобно, поэтому в TermWare приняты некоторые сокращения:

Вернемся к переписывающим правилам: итак, простое переписывающее правило имеет вид a->b (или rule(a,b) ), следуя ему мы переписываем терм, сопоставимый с a в терм, сопоставимый с b. Особую роль в процессе подстановки играют пропозициональные переменные: xi : они играют роль "пустых мест" в процессе подстановки: мы во время сопоставления с левой частью заполняем их значениями и подставляем эти значения в результат. Пример:

В TermWare пропозициональные переменные имеют вид идентификаторов, начинающихся со знака доллара ($x, $myVariable). Правило из предыдущего примера записывается следующим образом: p($x,$y) -> q($y,$x) .

Этот процесс называется унификацией, подробности можно найти в любой книге по математической логике.

Чем программирование правил отличается от императивного программирования - тем, что мы можем работать с абстрактными символами, а не с предопределенными конструктивными объектами. Вспомним школу и приведем несколько правил для символьного дифференциирования:


Применяя эти правила к терму, скажем diff(x*y+x+1,x) получим 1*y+x*diff(y,x)+diff(1,x) Помнится еще, что производная от константы будет равна нулю. Числа очевидно являются константами.

Это правило с условием -- мы применяем правило только в том случае, если условие истинно. Как видим, c этим правилам наш терм редуцируется к 1*y+x*diff(y,x)+0. Кстати, дифференциал по константе не имеет смысла:

Это правило с условием и действием. - после выполнения подстановки мы выполняем действия, перечень которых указан в квадратных скобках после образца результата.

Что такое правила - уже понятно. Набор правил обозначается как ruleset(r1 ... rn). Запишем наши правила дифференциирования как термальную систему:



domain(examples,
system(Diff,default,
ruleset(
diff($a+$b,$x) -> diff($a,$x)+diff($b,$x) ,
diff($a-$b,$x) -> diff($a,$x)-diff($b,$x) ,
diff(+$a,$x) -> diff($a,$x) ,
diff(-$a,$x) -> - diff($a,$x) ,
diff($a*$b,$x) -> diff($a,$x)*$b+$a*diff($b,$x) ,
diff($x,$x) -> 1 ,
diff($a,$x) [ isInt($a) || isFloat($a) ] -> 0
),
BottomUp
) );



Первое, на что можно обратить внимание - почему-то сама система вписана в domain. Домены - это средства организации информации, подобно package в Java или namespace в С++. Имя системы - Diff , полное имя: examples::Diff . Осталось разобраться что такое default и BottomUp . Сразу скажем, что это имя БД фактов, и имя стратегии. А теперь пояснения :

Определение системы имеет вид system(n,f,r,s), где:

domain(algebra,  
system(Monoid,default,
ruleset(
import(SemiGroup),
$x*One -> $x,
One*$x -> $x
),
FirstTop)

);

В порядке развлечение можно сказать пару слов о математике: видно, что стратегии бывают хорошие и не очень, (очевидно Top-не очень хорошая), и что существуют хорошие наборы правил, которые преобразуют один и тот-же терм в один и тот-же результат, при применении к ним разных хороших стратегий. Такие наборы правил называются Нетеревскими, или говорят что они удлвлетворяют свойству "Черча-Россера" по имени математиков, которые занялись этой областью в 40-х годах прошлого века.


Теперь мы можем что-то сделать руками. Например - поместить нашу систему правил для диффирициирования в в файл Diff.def в каталог $TermWareRoot/systems/examples запустить TermWare.cmd.sh и набрать там examples::Diff.diff(x+x*2,x)

Интерпретатор командной строки


Итак, интерпретатор командной строки называется TermWare.cmd.sh или TermWare.cmd.bat , в зависимости от того, под какой платформой вы работаете, и находится в каталоге $TermWareRoot/bin . Применяется он в основном для отладки систем правил, для прогона тестов и как оболочка, из под которой можно удобно вызывать разные системы. Типичный пример сеанса:


01:TermWare>let x->y

02:true

03:TermWare>x

04:y

05:TermWare>p(x)

06:p(y)

07:TermWare>let p($x,$y) -> $x+$y

08:true

09:TermWare> p(3,2)

10:5

11:TermWare> p(3,x)

12:3+y

13:TermWare>subst("aaab","a+","b")

14:subst("aaab","a+","b")

15:TermWare>String.subst("aaab","a+","b")

16:"bb"

17:TermWare>setProperty(debug,true)

18:true

19:TermWare>x

20:ua.kiev.gradsoft.TermWare.strategies.TopDownStrategy: t=x

21:ua.kiev.gradsoft.TermWare.utils.RuleTransformer: apply rule, term=x

22:rule=[x->y]

23:ua.kiev.gradsoft.TermWare.utils.RuleTransformer:substitution=[]

24:ua.kiev.gradsoft.TermWare.utils.RuleTransformer:result=y

25:ua.kiev.gradsoft.TermWare.strategies.TopDownStrategy: t=y

26:ua.kiev.gradsoft.TermWare.strategies.TopDownStrategy: t=y

27:ua.kiev.gradsoft.TermWare.strategies.TopDownStrategy: t=y

28:y


Обратите внимание на следующее:

Дерево предметных областей


Раз мы уже начали рассказывать о предопределенных системах и именах,

рассмотрим подробнее именование систем.

Мы вскользь упоминали, что если определение системы имеет вид domain(D,system(n,f,r,s)) то полное имя системы имеет вид D::n. 'domain' это

предметная область. Системы как-бы расфасованы по предметным областям.

Естественно, предметные области могут быть вложены. Если интерпретатор

TermWare встречает сложное имя, использующееся в контексте системе, то он ищет

в дереве каталогов операционной системы файл с путем, где директории

соответствуют проблемным областям (domain) а файлы с расширением def - системам. Начальные точки поиска (аналог classpath в Java) задаются либо с

помощью Java-свойства TermWare.path , либо могут быть установлены из языка

Java с помощью методов класса TermWare.getInstance() .


Java API - начнем не с Hello, world.

Перейдем наконец к програмированию. Первый подвох -- классический пример (вывод на экран словосочетания Hello, world не имеет никакой семантики действий (у нас просто нет объекта для анализа с помощью правил), поэтому запрограмировать на TermWare это не получится.

Тривиальное преобразование: xyz

Что кроме Hello, world может быть простым ? Ну, например то, что следующий набор правил:



ruleset(
x->y,
y->z
)



Переводит атом x в атом z . Смотрим на исходный код:



01 package ua.gradsoft.termwareexamples;
02
03 import ua.gradsoft.termware.*;
04 import ua.gradsoft.termware.strategies.*;
05
06
07 /**
08 *Example, which illustrate TermWare using.
09 * let's create system and transform x into z.
10 * @author Ruslan Shevchenko
11 */
12 public class Example1 {
13
14
15 /**
16 *@param args the command line arguments
17 */
18 public static void main(String[] args)
19 {
20 try{
21
22
23
24 TermWare.getInstance().init(args);
25
26 ITermRewritingStrategy strategy=new FirstTopStrategy();
27
28
29 IFacts facts=new DefaultFacts();
30
31
32 TermSystem termSystem=new
33 TermSystem(strategy,facts,TermWare.getInstance());
34
35 termSystem.addRule("x->y");
36 termSystem.addRule("y->z");
37
38 Term inputTerm=TermWare.getInstance().getTermFactory().createAtom("x");
39 Term outputTerm=termSystem.reduce(inputTerm);
40
41 if(outputTerm.getName().equals("z")){
42 System.out.println("success");
43 }else{
44 System.out.println("failure");
45 }
46 }catch(TermWareException ex){
47 System.err.println("eror:"+ex.getMessage());
48 ex.printStackTrace();
49 }
50
51 }
52
53 }

В строках 3-5 - спецификации импорта пакетов TermWare. Практически любая программа, использующая TermWare нуждается в этих пакетах.

Строки 26-28 - Создаем стратегию "FirstTop".

Строки 29-31 - Создаем БД фактов. Для этого используем класс DefaultFacts

Строка 33 - Наконец, создаем термальную систему, перелавая ей програмной окружение, стратегию и факты как аргументы.

Строки 35-36 - добавляем правила. Вот и все. Система готова к работе.

Теперь нам надо что-то подать на вход нашей системы. Строки 38 - создаем терм x с помощью метода класса ITermFactory. (cм. Описание API )

Строка 39 - редуцируем терм. На выходе - получаем результат.

Проверяем, что мы получили z .

Обратите внимание на try/catch блок и на обработку исключения в строках 41-46. Все исключения в TermWare наследованы от TermWareException (cм. Описание API ) .


Повторим, вкратце, что мы выяснили:




ITerm t = termFactory.createTerm("rule",
termFactory.createAtom("x"),
termFactory.createAtom("y")
);

Добавляем свою Базу Фактов

Теперь собственно самое интересное - как организовать обработку данных из внешней среды. Как уже говорилось несколько раз, для системы переписывающих правил внешняя среда преставлена как база фактов, которая может создаваться программистом.

Давайте в нашу систему xyz добавим чтение какого-то значения. Например:


x [ getW() ] -> w,
x [ !getW() ] -> y,
y->z

Т. е. внешняя среда предоставляет нам какую-то информацию getWFlag() , проверяя которую мы в правилах преобразуем x соответственно в w или y .

Создаем БД фактов:


package ua.gradsoft.termwareexamples;

import ua.gradsoft.termware.DefaultFacts;
import ua.gradsoft.termware.TermWareException;


/**
* example of facts database.
*/
public class Example2Facts extends DefaultFacts {

public Example2Facts() throws TermWareException
{}

public boolean getW() { return w_; }

public void setW(boolean w) { w_=w; }

private boolean w_=false;
}

И ее используем:

package ua.gradsoft.termwareexamples;

import ua.gradsoft.termware.IEnv;
import ua.gradsoft.termware.ITermRewritingStrategy;
import ua.gradsoft.termware.Term;
import ua.gradsoft.termware.TermFactory;
import ua.gradsoft.termware.TermSystem;
import ua.gradsoft.termware.TermWare;
import ua.gradsoft.termware.TermWareException;
import ua.gradsoft.termware.strategies.FirstTopStrategy;

/**
*Example, which illustrate TermWare using.
* let's create system and transform x into y or w,
* depend from value in facts database.
* @author Ruslan Shevchenko
*/
public class Example2 {


/**
* @param args the command line arguments
*/
public static void main(String[] args) {
try {

TermWare.getInstance().init(args);

ITermRewritingStrategy strategy=new FirstTopStrategy();

Example2Facts facts=new Example2Facts();

TermSystem termSystem=new
TermSystem(strategy,facts,TermWare.getInstance());

termSystem.addRule("x [ getW() ] -> w");
termSystem.addRule("x [ !getW() ] -> y");
termSystem.addRule("y->z");

TermFactory termFactory=TermWare.getInstance().getTermFactory();

Term inputTerm=termFactory.createAtom("x");
Term outputTerm=termSystem.reduce(inputTerm);

if (outputTerm.getName().equals("z")) {
System.out.println("success");
}else{
System.out.println("failure");
}

facts.setW(true);
outputTerm=termSystem.reduce(inputTerm);

if (outputTerm.getName().equals("w")) {
System.out.println("success");
}else{
System.out.println("failure");
}

}catch(TermWareException ex){
System.err.println("eror:"+ex.getMessage());
ex.printStackTrace();
}

}
}

Как видим, БД фактов представляет собой просто Java-объект, методы которого можно непосредственно вызывать из термальной системы.

Вспомним, что в общем виде правило имеет вид x[condition] -> y[action] . Только что мы проиллюстрировали проверку условия, теперь давайте скажем что-то в БД. Например, рассмотрим такую систему:

        x    [ getW() ] -> w,
x [ !getW() ] -> y,
y->z [ setW(true) ]

При ее интерпретации, во время подстановки y -> z вызовется метод setW . Его аргумент будет автоматически преобразован к типу, соответствующему типу аргумента метода, если это возможно.

Передача информации с помощью пропозициональных переменных.

Естественно, наша среда правил будет неполной, без возможности передачи информации между переписывающтит правилами и Java-средой. Как передавать информацию из правил в Java-методы - просто передавая пропозициональные переменные как аргументы.

Пример:

Рассмотрим следующий набор правил

 access($x,$page) [ allowed($x,$page) ] -> true [ go($page) ],
access($x,$page) [ !allowed($x,$page) ] -> false
[ notice(access atempt:\",$x,$page) ]

Который отделяет плохое от хорошего.

Пусть наша БД будет выглядеть следующим образом:


package ua.gradsoft.termwareexamples;

import java.util.HashMap;
import java.util.HashSet;
import ua.gradsoft.termware.DefaultFacts;
import ua.gradsoft.termware.IEnv;
import ua.gradsoft.termware.TermWareException;



/**
* example of facts database.
*/
public class Example3Facts extends DefaultFacts {

public Example3Facts() throws TermWareException
{ super(); }

public boolean allowed(String name,String page)
{
HashSet<String> hs=acl_.get(name);
if (hs==null) return false;
return hs.contains(page);
}

public void go(String page)
{ System.out.println("go:"+page); }

public void notice(String msg,String name,String page)
{ System.out.println(msg+"("+name+","+page+")"); }

private HashMap<String,HashSet<String>> acl_;
{
acl_=new HashMap<String,HashSet<String>>();
HashSet<String> p1s=new HashSet<String>();
p1s.add("page1");
p1s.add("page2");
p1s.add("page3");
HashSet<String> p2s=new HashSet<String>();
p2s.add("page1");
acl_.put("mark",p1s);
acl_.put("lyuds",p1s);
acl_.put("guest",p2s);
}
}

А вот и сама java программа:


package ua.gradsoft.termwareexamples;

import ua.gradsoft.termware.ITermRewritingStrategy;
import ua.gradsoft.termware.Term;
import ua.gradsoft.termware.TermFactory;
import ua.gradsoft.termware.TermSystem;
import ua.gradsoft.termware.TermWare;
import ua.gradsoft.termware.TermWareException;
import ua.gradsoft.termware.strategies.FirstTopStrategy;


/**
* Example of passing values of propositional variables into facts
*/
public class Example3 {

/**
* @param args the command line arguments
*/
public static void main(String[] args)
{
try {

TermWare.getInstance().init(args);

ITermRewritingStrategy strategy=new FirstTopStrategy();

Example3Facts facts=new Example3Facts();

TermSystem termSystem=new
TermSystem(strategy,facts,TermWare.getInstance());

termSystem.addRule(
"access($x,$page) [ allowed($x,$page) ] -> true [ go($page) ]");
termSystem.addRule(
"access($x,$page) [ !allowed($x,$page) ] -> false [ [go(deny), notice(\"access atempt:\",$x,$page)] ]");


TermFactory termFactory=TermWare.getInstance().getTermFactory();

Term inputTerm=termFactory.createTerm("access",
termFactory.createString("mark"),
termFactory.createString("page1"));
Term outputTerm=termSystem.reduce(inputTerm);

if (outputTerm.isBoolean()) {
if (outputTerm.getBoolean()) {
System.out.println("success");
}else{
System.out.println("failure");
}
}else{
System.out.println("failure");
}


}catch(TermWareException ex){
System.err.println("eror:"+ex.getMessage());
ex.printStackTrace();
}

}

}

Как мы видим, вхождения типа $x заменяются на подстановку переменных.

В предыдущем примере мы показали передачу информации из правил в БД фатов. Не менее важным представляется и обратное направление -- установка пропозициональных переменных из БД фактов.

Усложним немного систему из предыдущего примера: введем понятия группы, к которой принадлежит пользователь. Например так:



access($name,$page)-> groupAccess($group,$name,$page)
[getGroup($group,$name)],



groupAccess($group,$name,$page)
[allowedGroup($group,$page)] -> true [ go($page) ]
!-> false
notice("access atempt:",$name,$page)]

В первом правиле мы определяем группу пользователя, во втором -- проверяем доступ группы. Итого, что у нас нового - надо заполнить пропозициональную переменную $group из метода БД фактов. Для этой цели реализация DefaultFacts предоставляет нам API работы с текущей подстановкой. Метод getCurrentSubstitution() возвращает нам текущую подстановку переменных, в которую мы можем добавить соответствие между переменной и значением с помощью метода put



package ua.gradsoft.termwareexamples;

import java.util.HashMap;
import java.util.HashSet;
import ua.gradsoft.termware.DefaultFacts;
import ua.gradsoft.termware.Substitution;
import ua.gradsoft.termware.Term;
import ua.gradsoft.termware.TermFactory;
import ua.gradsoft.termware.TermWare;
import ua.gradsoft.termware.TermWareException;
import ua.gradsoft.termware.TransformationContext;
import ua.gradsoft.termware.exceptions.AssertException;



/**
* example of facts database.
*/
public class Example4Facts extends DefaultFacts {

public Example4Facts() throws TermWareException
{ super(); }

public void getGroup(TransformationContext ctx, Term groupTerm, String name) throws TermWareException
{
if (!groupTerm.isX()) {
throw new AssertException("first argument of getGroup must be propositional variable");
}
Object o=groups_.get(name);
TermFactory termFactory = TermWare.getInstance().getTermFactory();
Term value = ((o==null) ? termFactory.createNil() : termFactory.createString((String)name) );
Substitution s = ctx.getCurrentSubstitution();
s.put(groupTerm,value);
}


public boolean allowedGroup(String groupName,String page)
{
Object o=acl_.get(groupName);
if (o==null) return false;
HashSet hs=(HashSet)o;
return hs.contains(page);
}


public void go(String page)
{ System.out.println("go:"+page); }

public void notice(String msg,String name,String page)
{ System.out.println(msg+"("+name+","+page+")"); }

private HashMap<String,HashSet<String>> acl_;
private HashMap<String,String> groups_;
{
groups_=new HashMap<String,String>();
groups_.put("mark","admin");
groups_.put("lyuds","admin");
groups_.put("guest","guest");
acl_=new HashMap<String,HashSet<String>>();
HashSet<String> p1s=new HashSet<String>();
p1s.add("page1");
p1s.add("page2");
p1s.add("page3");
HashSet<String> p2s=new HashSet<String>();
p2s.add("page1");
acl_.put("admin",p1s);
acl_.put("guest",p2s);
}
}

Добавление соответствия в текущую подстановку (т. е. установка пропозициональной переменной) приведено в методе getGroup . В начале метода мы проверяем, что первый аргумент является пропозициональной переменной. В конце метода мы добавляем соответствие между groupTerm и value в текущую подстановку.

Приблизим наш пример к реальности - обычно пользователь может принадлежать нескольким разным группам. Модифицируем предыдущий пример так, что бы БД фактов возвращала нам список имен груп:



access($name,$page) -> groupsAccess($group,$name,$page)
[getGroups($group,$name)],
groupsAccess([$group:$rest],$name,$page) ->
groupAccess($group,$name,$page)||groupsAccess($rest,$name,$page),

groupsAccess([],$name,$page) -> deny($name,$page),

groupAccess($name,$group,$page)
[allowedGroup($group,$page)] -> true[ go($name,$page) ]
!-> deny($name,$page),


true || $x -> true ,
$x || true -> true ,

deny($name,$page) -> false [ notice("access attempt") ],

Т. е. правила для groupsAccess сводят проверку списка груп на проверку к принадлежности к какой-то группе. [x:y] это сокращение для cons(x,y) Правила для deny сводят дизъюнкцию deny к первому вхождению. Заметим, что эта система правил зависит от стратегии: если первым у нас редуцируется головной терм (стратегия FirstTop), то правило


 deny($name,$page) -> false [ notice("access attempt") ]


будет выполняться только после того, как редуцировались все дизъюнкции.

Теперь getGroups должна возвратить список групп, а не одну группу. Что такое список - вспомним что [x,y] является сокращением для cons(x,cons(y,NIL)) , NIL и пустой список - синонимы. Т. е. списки в TermWare абсолютно аналогичны списам в языке LISP. Как выглядит генерация такого списка на Java:


  public void getGroups(TransformationContext ctx, Term groupTerm, String name) throws TermWareException
{
TermFactory termFactory=TermWare.getInstance().getTermFactory();
if (!groupTerm.isX()) {
throw new AssertException("first argument of getGroups must be a propositional variable");
}
String[] groups=groups_.get(name);
if (groups==null) {
ctx.getCurrentSubstitution().put(groupTerm, termFactory.createNIL(), true);
}else{
Term retval=termFactory.createNil();
String[] groups=(String[])o;
for(int i=0; i< groups.length; ++i) {
retval=termFactory.createTerm("cons",
termFactory.createString(groups[i]),
retval);
}
ctx.getCurrentSubstitution().put(groupTerm, retval);
}
}




т. е. мы в генерируем елемент списка с помощью termFactory.createTerm

Более систематическое введение

Этот раздел повторяет описание семантики, только не так подробно и без лишней математики, что бы можно было его бегло прочитать.

Встроенные термы

Примитивные типы данных

Это целые числа различной размерности Short, Int, Long, BigInteger, числа с плавающей точкой: Double, Float; числа с фиксированной точкой (BigDecimal), строки (String), символы (Char), логические значения (Boolean), атомы (Atom) и специальный выделенный терм NIL.

В общем – ничего необычного. Если вы заметили, список примитивных типов termware совпадает с аналогичным списком языка Java.

Соответсвующие лексемы тоже очевидны. Одно отличие от Java – можно вводить лексемы, соответсвующие длинным целым числа и числам с десятичной точкой.

Типы чисел и соответствующие суффиксы лексем приведены в таблице:


Тип

Тип Java

Суффикс

Пример

Целое

Int


1

Длинное целое

Long

L

10000000000L

Большое целое

BigInteger

B

1000000000022222B

Число с плавающей точкой двойной точности

Double


1.1


Double

D

1.1D

Чимло с плавающей точкой ординарной точнойти

Float

F

1.1F

Число в десятичном представлении

BigDecimal

B

1.1B

Списки

Опять повторимся - списки это просто "синтаксический сахар" для терма "cons": [ x ] является сокращением для cons(x,NIL) , [ x, y ] - для cons(x, cons(y, NIL()) и. т. д. [ ] (пустой список) и NIL - синонимы.

Для сопоставления списков также существует специальный синтаксис: [ x : y ] является сокращением для cons(x,y) . Поэтому при сопоставления образца [$x: $y] и списка, скажем [1,2,3,4] у нас с $x будет ассоциироваться первый элемент (1), а с $y - остаток списка [2,3,4] .

Рассмотрим следующую систему правил: sum([1,2]) редучируется к 1+sum([2]), что в свою очередь редучируется к 1+2+sum(NIL) . По второму правилу sum(NIL) это 0 - в итоге получим 1+2+0 = 3 .

Множества

Множество - это сокращение для терма set(x1...xN) . Т. е. { 1, 2, 3, 4, 5 } обозначает set(1,2,3,4,5) , { 1, 2 } - set(1,2) , а { } - set() .

Характеристической особенностью множества является то, что каждый элемент множества присутстсует в нем только один раз, т. е. { 1, 2, 2, 3 } - это то-же самое, что и { 1, 2, 3 } .

Да, для того, что бы можно было создавать конструкторы множеств из Java, не прибегая к синтаксическому разбору, существет терм set_pattern(x,y) (он же { x : y }) , обозначающий образец множества.


Java-объекты

Java объекты также могут выступать в роли термов, принимая участие в подстановках и унификации.

Также к Java объекты могут принимать участие в сопоставлении с образцом, для этого предназначен специальный синтаксис: @class("class-name",$v).

Например следующее правило:

@class("java.io.StringStream",$x) -> true !-> false

будет преобразовывать в true экземпляры java.io.StringStream, а все остальное – в false.

Пропозициональные переменные

В языке обозначаются как $x, $y, ... etc. Область действия – правило. Обозначают "место" куда подставляются термы при подстановках. На уровне Jaca кода представленны как экземпляры класса XTerm (описание API). Идентифицируются по номеру. minFv()=maxFv()

Составные термы

Ну и наконец составные термы (т.е. все остальное). Если a1,... an – термы, f – функциональный символ, то f(a1...an) – терм. F будем называть функциональным символом, a1...an – подтермами. Количество подтермов называется арностью (или местностью). Собственно все сложные структуры – это составные термы (возможно с синтаксическим сахаром)


Понятно что образец вида f($x) унифицируется с одноместным термом, где f – функциональный символ.

Еще один необычный и достаточно мощный синтаксис сопостаdления: $f..($x)

$f..($x) унифицируется с любым функциональным термом, притом с $f будет ассоциироваться функциональный символ (как атом), с $x – список агрументов. f..($x) будет ассоциироваться как с f(1), так и с f(1,2), а $f..(NIL) будет ассоциироваться с всеми 0-арными функциями.

Правила

Правило, в общем виде это выражение вида:


Интерпретация следующая: сопоставляем терм с образцом x, если не получилось – праило не применяется. Если получилось – проверяем условия condition. Если условия выполняется – переписываем x в y и выполняем action, иначе проверяем условие condition1, если выполняется – переписываем в y1 и выполняем action1, затем то-же самое с y2 и.т.д. Если ни одно из условий не выполнено, переписываем в уLast и выполняем actionLast. Естественно, в реальной жизни почти все правила сокращенные.

Теперь осталось разобраться – а как именно вычисляются условия и выполняются действия ? Это зависит от класса фактов, ассоцированного с системой. В классе DefaultFacts (описание API) реализован следующий алгоритм:


Условия:

Действия: так-же как и с условиями, только возвращаемый результат игнорируется и несколько действий в списке обрабатывается последовательно.


Множества правил


Несколько правил объединяются в множество правил. (ruleset).

Примеры в избытке были приведены выше, покажем что-то новое:


ruleset(
import(general)

# handle new invoice and set one to paid if possible.
@class("ua.gradsoft.termwaredemos.invoicing.Invoice", $invoice)
[ ! $invoice.isPayed()
&&
$invoice.getCustomer().getAccountBalance()-$invoice.getAmount()+
$invoice.getCustomer().getCreditLimit() > 0
]
-> true
[ $invoice.getCustomer().decrementAccount($invoice.getAmount())
&&
$invoice.setPayed(true)
],

# set credit limit in depend from summary payments.
@class("ua.gradsoft.termwaredemos.invoicing.Customer", $customer)
[ $customer.getAccountBalance() > 0
&& $customer.getSummaryPayments() > 2000
] -> true [ $customer.setCreditLimit(500) ]
)




Эти правила работают над Java объектами, первое смотрит на инвойсы и снимает деньги со счета; второе устанавливает кредитный лимит клиента

Сами классы могут быть определены при этом следующим образом:



/**
*The definition of customer
*/
public class Customer {


/** Get the name of this customer. */
public String getName()
{
.......
}

/** Get the credit limit of this customer. */
public BigDecimal getCreditLimit()
{
........
}

/** set the credit limit of this customer **/
public void setCreditLimit(BigDecimal creditLimit)
{
........
}

/** get current account balance **/
public BigDecimal getAccountBalance()
{
.........
}

public void incrementAccountBalance(BigDecimal amount)
{
.......
}

public void decrementAccountBalance(BigDecimal amount)
{
.......
}

public BigDecimal getSummaryPayments()
{
.........
}

}




Т.е. используемый класс может быть обыкновенным POJO, или инкапсулировать к себе обращения к БД.

$customer.getAccountBalance() работает, так как это сокращение для apply($customer,getAccountBalance()), в общей системе (general) apply для Java объектов интерпретируется как вызов соответсвующего метода. После того, как произошла подстановка, вместо $customer у нас соответсвующий Java объект, соответственно все начинает работать как и было задуманно.


Импорт


Также обратите внимание на выражение import(general). Системы могут импортировать правила из других систем, в целом этот механизм очень похож на механизм наследования в объектно-ориентированном программировании. Еще один вариант импорта – importTransformed, когда мы импортируем правила, сами додверженные некоторым преобразованиям.


Последовательность применения

Точная последовательность применения правил зависит от стратегии. Существует одно правило разрешения конфликтов, которое можно кратко описать как "Сначала разбираем частные случаи", то есть когда одно и то-же предложение можно редуцировать двумя разными правилами (скажет r1 и r2) и одно из этих правил более частное(конкретное) чем второе, (например r1), то оно применяется первым.


Скажем следующая система:

 ruleset(
p(q($x)) -> A,
p($x) -> B
)



Возвратит нам A для p(q(1)) и B для p(1), а следующая система:


ruleset(
p($x,$x) -> same,
p($x,$y) -> different
)



возвратит нам same для p(a,a) и different для p(a,b).


Let и Where выражения

Когда мы говорили, что последовательность редукций определяется стратегией, мы сказали не все: есть виды выражений, редукция которых осуществляется специальным образом. Это так называемые let и where выражения. Рассмотрим выражение вида

let (v1 <- e1, v2 <- e2,... vN <- eN) x

Его редукция происходит следующим образом: сначала максимально редуцируются термы e1 .. eN и их значения ассоциируются с пропозициональными переменными v1 ... vN, затем происходит подстановка их значений в x.

where выражения отличается от let только порядком следования секций переменных и собственно термов, т.е. следующее выражние является просто синонимом:

x where (v1 <- e1, v2 <- e2,... vN <- eN)


Также существуют формы применения let и where выражений в правилах:

x [ condition ] where (v1 <- e1, v2 <- e2,... vN <- eN) -> y | [cn1] -> y1 | ... !-> yK

или альтернативная форма:

x let (v1 <- e1, v2 <- e2,... vN <- eN) [ condition ] -> y | [cn1] -> y1 | ... !-> yK

тогда при успешном сопоставлении образца с x сначала редуцируются e1 ... eN и подставляются в соответствующие пропозициональные переменные, которые можно использовать во всех условиях и правых частях правила;



Системы


Ну и наконец система – это имя + БД фактов + множество правил + стратегия.

Имя – любой иденитификатор.

БД фактов – Java класс, удовлетворяющий интрефейсу IFacts. можно называть их по имени, вначале зарегистрировав в экземляре TermWare;


IFacts facts = new MyFacts();
TermWare.getInstance().addFacts("MyFacts",facts);



после этого можно писать нечто вроде: system(MySystem, MyFacts, ruleset(....), MyStrategy)


Таким подходом полезно пользоваться, когда создается несколько систем, работающих над одним объектом данных. Так как система имен иерархическая, то вызов TermWare.getInstance().addFacts() создаст нам имя фактов самого верхнего уровня. Для создание вложенного имени надо будет воспользоваться таким-же методом в классе Domain, который представляет элемент пространства имен.


Второй способ – использовать загрузку по имени класса: т. е. В определении системы вместо имени зарегистрированного класса фактов написать терм loadFacts(name,className), тогда TermWare загрузит класс с именем className (естественно он должен реализовывать IFacts), создаст его экземпляр, свяжет этот экземпляр с именем name и свяжет его с создаваемой системой.


То-же самое и со стратегиями – вы можете использовать их по имени (существуют предопределенные исена стратегий: FirstTop и BottomTop), либо загрузить свою используя loadStrategy в определении системы.

Домены


Системы могут группироваться в домены. Что такое домен – просто область имен, как namespace в С++ или package в Java. TermWare умеет загружать определениеяиз файловой системы или загрузчика классов, использую структуру каталогов, соответствующую вложенности доменов. Поиск при этом начинается с директории, указанной в свойстве termware.path. Естественно, ничего не мешает установить корень структуры каталогов програмно: TermWare.getInstance().getTermLoader().addSearchPath(String path).


Небольшая иллюстрация:


Пусть у нас есть два подкаталого в termware.path: A и B.

В каталоге A находится файл x.def, со следующим содержимым:


domain(A,
system(X,MyFacts,
ruleset(
a($x) -> A,
b($x) -> B
),
)
)



А в каталоге B – со следующим:

domain(B,
system(X,MyFacts,
ruleset(
a($x) -> B,
b($x) -> C
),
)
)



Тогда вызов apply(A::X,a(1)) нам выдаст A, а вызов apply(B::X,a(1)) – B.

Итого, доступ по полному имени обозначается как C1::C2::...::Cn и обозначает (для систему) систему Сn, которая находится в домене C(n-1) ... который находиться в домене С1. Запись составного имени без синтаксического сахара – как _name(C1,..Cn). Кстати, заметим что apply(x,y) тоже может быть записно по другому (через точку), т. е. apply(A::X,a(1)) эквивалентно A::X.a(1). Такой вид записи применяется довольно часто.


На уровне Java API, обратите внимание на класс Domain (описание API), который предоставляет доступ к содержимому доменов. Еще заметим, что файловая система нас не всегда устраивает как хранилище данных, иногда мы хоти хранить системы в реляционной БД или где-то еще. В таком случае TermWare предоставляет возможность написать свой TermLoader и закрепить его за экземпляром движка.



Что дальше


Ссылки на справочную документацию есть в предисловии. (на всякий случай продублируем):

Для более читабельного описания семантики можно посмотреть стаьи по TermWare на сайте Градсофт (http://www.gradsoft.ua) Следующая статья: TermWare: A Rewriting Framework for Rule-Based Programming Dynamic Applications может быть использована вместо введения.

Еще стоит посмотреть на примеры, находящиеся в директории demo инсталляци. Также существует несколько нетривиальных програмных проектов с открытым кодом, использующих TermWare, к примеру JavaChecker (http://www.gradsoft.ua/products/javachecker_eng.html), там можно подсмотреть типичные паттерны использования.

Если вам необходимо связаться с автором – пишите по адресу Ruslan@Shevchenko.Kiev.UA