DemonScript: Основы языка


Введение

DemonScript - это скриптовый язык для описания обыденных знаний в задачах искусственного интеллекта. В нём можно использовать стандартные алгоритмические операторы (условия, циклы, функции и т.п.). Кроме этого DemonScript содержит развитый синтаксис и алгоритмы по работе с графами, которые служат для описания объектов реального мира и отношений между ними. Наконец, DemonScript - это мощный движок проведения логических выводов в рамках интервальной логики множественных миров. Подробнее все эти подходы описаны в последующих документах, справочнике и наборе примеров готовых программ. В данном документе содержится "экспресс-введение" в язык.

Скрипт пишется в любом текстовом редакторе. Приведенные далее примеры могут быть запущены консольной утилитой ds.exe. Так, создадим файл hello.ds и напишем в нём:

   out "Hello real world!"
Запуск в консоли: "ds.exe hello.ds" приведёт к выводу приветствия. Этот и другие примеры можно также запускать непосредственно на сайте.


Переменные и операции

Переменные в DemonScript должны объявляться при помощи оператора var:

   var F = 5                       // вещественное число
   var L = True,  S = "строка"     // логическое значения и строка 
   
   out " L = ", L                  // выводим строку и переменную > L = True
После двойных слешей // идут комментарии, которые компилятор игнорирует до конца строки. Можно также использовать блочные комментарии /* .... */, содержащие несколько строк.

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

С числами можно проводить стандартные вычислительные операции:

   F = (F/2) * 2.3 * Math.pow(2,3) + (F%2) + F++
Методы объекта Math содержат различные математические функции (выше - метод pow возводит 2 в 3-ю степень). Хотя числа в общем случае содержат дробную часть, с ними можно также проводить различные целочисленные операции (выше F%2 равен остатку от деления на 2, а F++ - увеличение F на единицу).

Все базовые типы можно сравнивать друг с другом: X == Y - равенство значений, X != Y - неравенство значений. Результатом этих операций будет бинарное логическое значение (True или False).

Результатом сравнения переменных разных типов (5 == "5") будет False. Логические значения можно объединять при при помощи логического И: X & Y, логического ИЛИ: X | Y, отрицания: !X и импликации: X -> Y. Можно также использовать скобки: X & (Y | ! Z ) и т.д. В простейшем случае DemonScript работает с трёзначной логикой: False, True и Undef:

var X = True
out !X                             //> False
out X & Undef                      //> Undef
out X | Undef                      //> True

Различные выражения и команды DemonScript могут находиться на одной строке. Желательно выражения разделять точкой с запятой: ";", но это не обязательно. Впрочем, если обнаружилась ошибка парсинга скрипта, хорошей идеей будет поставить в этом месте разделитель между командами.


Условный оператор

Условный оператор if анализирует истинность выражения. Если оно истинно (True), то выполняется оператор, идущий после двоеточия ":". Если там должно находиться несколько операторов, то они окружаются фигурными скобками и тогда двоеточие не обязательно:

var X = True

if X == True :                   
   out " ok1 "
   
if X :
   out " ok2 "
   
if X != False {
   X = False
   out " ok3 "
}

out X
В этом примере сработают все три оператора if, и последний внутри себя изменит значение переменной X.

Так как DemonScript использует многозначную логику, кроме стандартного оператора ветвления else, существуют его многочисленные версии. Кроме этого, условные операторы можно использовать внутри выражений (см. следующий документ).


Циклы

В DemonScript существует два вида циклов: while и for. Цикл while выполняется, пока условие, идущее после оператора while истинно:

var I = 1                          // начальное значение
while I < 10                       // повторяем, пока I < 10
{
   out I                           // выводим I
   I = I + 1                       // увеличиваем его (можно также I++)
}

Этот же цикл можно организовать при помощи оператора for:

for I in range(1,10) :               
   out I              

В цикле можно использовать оператор break. Например, если в начале блока поставить строку

   if I > 5: break                 // прервать цикл
она прервёт выполнение цикла, когда переменная I превысит 5.

Цикл for также служит для перебора различных объектов. Например, это могут быть элементы массива:

var Arr = [1,2,3, "привет", True]  // массив из пяти элементов
for A in Arr:                      // бежим по его элементам
   out A                           // выводим их
Между операторами for и in стоит переменная A (её дополнительно объявлять не надо). Она принимает последовательно все значения элементов массива Arr, который содержит пять элементов: три числа, строку и логическое значение.

Кроме этого цикл for используется для перебора узлов графа (см. ниже).


Базовая работа с графом

Основная задача DemonScript - это работа с графами. Граф состоит из узлов, соединённых направленными рёбрами различных типов. В задачах искусственного интеллекта узлы графа могут быть объектами реального мира, находящегося в сознании системы, а рёбра - различными бинарными отношениями между объектами. Эти отношения считаются истинными, ложными или имеют промежуточные значения истинности.

Имена узлов начинаются с символа доллара: $ и состоят из латинских букв, цифр, символа подчёркивания: _ и решётки: #. Например: $box, $chest#1. Имя типа ребра начинается с собачки: @. Например: @in, @above. Если от узла $dog к узлу $box проведено ребро с именем @in, это означает, что объекты состоят в отношении $dog @in $box (собака находится в ящике) . Имена отношений объявляются в начале скрипта при помощи оператора edges, а имена объектов объявляются в любом месте оператором nodes:

edges @in                          // типы рёбер
nodes $box , $chest, $cat          // объявляем узлы

out   GRAPH                        // выводим текущий граф
Оператор out выводит на консоль структуру текущего графа GRAPH:
   graph {
      $box   {},
      $chest {},
      $cat   {}
   }
Пока граф состоит из трёх несвязанных узлов (их имена объявлены в операторе nodes). Добавим код, который устанавливает связь между узлами:
$box.@in.$chest = True            // есть направленное ребро @in из $box в $chest

out GRAPH                         // опять выводим граф
Результирующий граф в "JSON-формате" имеет вид:
   graph {
      $box   { @in: [$chest] },
      $chest { },
      $cat   { }
   }
В узле $box появилась информация об исходящем из него ребре @in. Она хранится в массиве [...] с именем ребра @in, в котором перечисляются узлы, связанные с $box ребром типа @in. Существуют также другие форматы вывода структуры графа.

Каждое ребро графа, кроме названия (типа ребра), содержит логическое значение, которое может быть истинным True, ложным False или неопределённым Undef (или истинно или ложно). Например, запретим сундуку находиться в ящике, а коту в сундуке:

$chest.@in.$box = $cat.@in.$chest = False

out GRAPH
В результате имеем:
   graph {
      $box   { @in : [ $chest] },
      $chest { @in : [!$box]   },
      $cat   { @in : [!$chest] }
   }
При выводе структуры графа истинное ребро отображается в массиве просто именем объекта: $chest, а ребро с "запретом" (ложное значение) помечается восклицательным знаком: !$box. Значение для ребра Undef эквивалентно отсутствию ребра.

Для вывода значения ребра воспользуемся оператором out:

out $cat.@in.$box, $cat.@in.$chest
В результате на экране должно появиться: Undef, False.

Оператор for позволяет перебирать узлы графа, удовлетворяющие определённому условию. Выведем, например, всех кто не находится в сундуке (нет явной информации об этом):

for X in X.@in.$chest != True :
   out X
Этот цикл выдаст два узла: $chest и $cat. Более подробная информация содержится в документе "Работа с графами"


Логическое программирование

При помощи графов описываются факты (объекты и отношения между ними). Используя стандартные алгоритмические методы (условия, циклы и демоны), можно создавать процедурные знания, которые из фактов выводят новые факты. Однако, более эффективным оказывается подход, в котором формулируются аксиомы, а затем новые факты из этих аксиом выводятся "сами по себе".

Рассмотрим небольшой пример из мира закрытых ящиков, которые могут быть вложены друг в друга. Определим отношение @in и сформулируем его свойства при помощи аксиом, которые добавим в объект Mind:

edges @in                                           // типы отношений
 
Mind.add(                                           // свойства отношения in:
  !X.@in.X,                                         // антирефлексивность
   X.@in.Z & Z.@in.Y -> X.@in.Y                     // транзитивность
   Z.@in.X & Z.@in.Y -> X.@in.Y | Y.@in.X | (X==Y), // образует дерево
)
Антирефлексивность означает, что ящик X сам в себе находиться не может, а транзитивность подразумевает возможность сколь угодно глубокой вложенности ящиков, подобно матрёшкам. Третья аксиома древесности звучит так: если Z находится и в X, и в Y, то либо X внутри Y, либо Y внутри X, либо это один и тот же ящик. Этих трёх аксиом достаточно для полного описания свойств отношения X.@in.Y. Рассмотрим пример.

Пусть есть три ящика a, b и с. Известно, что ящик a находится внутри c, а ящик b не находится внутри c. Необходимо ответить на вопросы: находится ли b внутри a?; может ли a находиться в b?.

Cоздадим модель в которой есть три ящика, и установим начальные условия задачи:

nodes $a, $b, $c                                    // объекты
    
$a.@in.$c = True                                    // ящик a внутри ящика c
$b.@in.$c = False                                   // ящик b не внутри ящика c
Теперь можно запустить движок логических выводов и получить ответы на свои вопросы:
 
Mind.set_graph(GRAPH)                               // логический вывод
 
out $b.@in.$a                                       //> False (нет)
out $a.@in.$b                                       //> Undef (возможно) 
Более подробно объект Mind описан в документе "Работа с аксиомами".


Демоны

Демон - это функция языка, которая принимает на вход значения нескольких аргументов и возвращает значение при помощи оператора return. Чтобы объявить демона, перед его именем необходимо поставить оператор def, а после имени демона в круглых скобках перечислить его аргументы. Алгоритм функции окружается фигурными скобками { ... }.

Например, часть кода демона отношения in(X, Y) (объект X находится в объекте Y) имеет вид:

edges @in                     // типы рёбер       

def in (X, Y)
{
   if X == Y :                // сам в себе
      return False            // находится не может
   if X.@in.Y != Undef :      // есть ребро
      return X.@in.Y          // возвращаем его значение
   if Y.@in.X :               // наоборот, Y в X
      return False            // не может находится
}
Если ни один из операторов return не сработал, демон по умолчанию возвращает неопределённое значение Undef. После того как демон определён, его можно использовать в основном коде скрипта или в других демонах:
nodes $cat, $box              // объявляем узлы
$cat.@in.$box  = True

out in($box, $cat)            // находится ли ящик в коте?

Демоны также могут возвращать имена узлов или рёбер:

def who(E, X)
{
   for Z in Z.E.X :
      return Z                // первый же узел по Е из X
   return $UNKNOWN_NODE
}

out who(@in, $box)            // кто в ящике?
В этом случае функция обязана вернуть узел, поэтому в её конце стоит выход с константой предопределённого "несуществующего узла".

Все переменные, объявленные внутри функции, являются локальными и ниже функции не видны. Более того, внутри функции не видны никакие переменные объявленные выше. Демон является "кирпичиком" процедурного знания и должен быть максимально независимым от "окружения".

Исключением являются имена отношений (и в редких случаях узлов). Демон должен быть объявлен до его использования.

Помимо демонов, существует также механизм модульности при помощи подключения других файлов со скриптами:

   #include "file_name.ds"

На самом деле демоны это нечто большее, чем просто функции. Например, возможен следующий код:

def in(X,Y): 
           get: return X.@in.Y 
           set: return X.@in.Y = value

in($a, $b) = True
out in($a, $b)
Подробнее мы обсудим этот синтаксис в документе "Демоны".