Click HERE to return to our International home page
Концепты Заметки МЕТА Флэнг Онлайн Модули Библио Форум



 Главная >  Флэнг > Описание > Логика  
 





• Факториал
• Арифметика
• Пример логической программы
• Структуры и термы
• Атомы
• Списки во Флэнге
• XML- документы
• Векторы
• Таблицы
• Перечисления
• XML-документы (продолжение)



Описание встроенных функций

 


Пример логической программы (logic.fln)

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


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

  father(X, Y): X - отец Y
и 
  mother(X, Y): X - мать Y
Например, тот факт, что Пол является отцом Джона можно представить в виде следующего правила: 
  father(paul, john) :- true;
Такого вида правила называются фактами и допускают на флэнге упрощенную запись: 
  father(paul, john);
Таким образом, все генеалогическое дерево может быть представлено в виде следующего сегмента Флэнг-программы: 
  father(paul, john);
  father(john, george);
  father(tom, mary);
  father(henk, martha);
  mother(mary, john);
  mother(martha, george);
Определим теперь отношение родитель. Как хорошо известно, родителем является либо мать, либо отец. Это может быть отражено во Флэнг-программе с помощью следующего определения: 
  parent(X, Y) :- father(X, Y);
  parent(X, Y) :- mother(X, Y);
Для Флэнг-системы это правило представляет следующую инструкцию: сначала следует проверить, не является ли X отцом Y. Если проверка закончится неудачей, то нужно проверить, не является ли X матерью. Если вычисление хотя бы одного из вариантов завершится успехом, значит X является родителем Y. Если оба варианта приведут к неудаче, то отношение на данной паре не выполняется. Определем теперь отношение "быть дедушкой", который, как известно, является отцом родителя. Это соображение и отражает следующее правило: 
  grandfather(X) :- parent(Y, X), father(Z, Y), Z;
В теле этого правила появляются две переменные - Y и Z, которых нет в голове правила. Их значения уточняются в процессе вычислений. "Дедушка" в этом правиле определен как функция от своего внука. Если найдется Y, что parent(Y, X) для которого найдется Z такой, что father(Z, Y), то значением функций будет дедушка Z.

Наконец, определим еще одно отношение - предок (ancient). В отличие от предыдущих случаев мы не знаем длины цепочки между предком и потомком в генеалогическом дереве. Это может быть 1 (родитель), 2 (дед), 3 (прадед) и т.д. В таких случаях необходимо использовать рекурсию. Для того чтобы определить правила для предка, заметим, что, во-первых, родитель является предком, а во-вторых, родитель предка также является предком. Это соответствует двум правилам: 

  ancient(X, Y) :- parent(X, Y);
  ancient(X, Y) :- parent(X, Z), ancient(Z, Y);
В программе, приведенной ниже, мы пользуемся только что определенными отношениями для поиска всех пар дедушка-внук и предок-потомок. О том как это делается более подробно поясняется в примечаниях к программе и работе Флэнг-интерпретатора.

Программа на Флэнге (logic.fln):

 
father(paul, john);
father(john, george);
father(tom, mary);
father(henk, martha);
mother(mary, john);
mother(martha, george);

parent(X, Y) :- father(X, Y);
parent(X, Y) :- mother(X, Y);

grandfather(X) :- parent(Y, X), father(Z, Y), Z;

ancient(X, Y) :- parent(X, Y);
ancient(X, Y) :- parent(X, Z), ancient(Z, Y);

allGf()  :-
        Y = grandfather(X),
        write(Y +" is grandfather of "+X+nl()),
        fail;

allAnc()  :-
        ancient(X, Y),
        write(X +" is ancient of "+Y+nl()),
        fail;


mПримечания

  • Функции allGf() и allAnc() перечисляют все пары дед-внук и предок-потомок, соответственно. Функции действуют по следующей схеме: находится очередная пара, затем с помощью функции вывода write информация об этой паре выводится на экран. Затем с помощью "тождественно ложной" функции fail (более точно ее можно охарактеризовать как функцию "вечной неудачи") мы насильственно объявляем, что зашли в тупик, и это заставляет Флэнг-систему возвращаться, чтобы искать альтернативные варианты решения.
  • Когда Флэнг-система выбирает некоторое правило, и если это правило не последнее в определении, система, как говорят, ставит точку выбора, то есть запоминает другие альтернативы. Поэтому если использование выбранного правила не приведет к успешному результату, можно вернуться к другим вариантам. Такую процедуру возврата часто называют бэктрэкингом. Это одно из ключевых средств логического программирования. Это средство полностью реализовано во Флэнге и именно оно позволяет решать подобные логические задачи.


Работа в интерпретаторе:

 
?- load(logic);

 true

?- father(john, george);

 true

?- father(john, X);

 true
 X =  george

?- father(george, X);

 fail

?- parent(martha, X);

 true
 X =  george

?- grandfather(john);

 tom

 ?- grandfather(mary);

 fail

?- ancient(tom, george);

 true

?- ancient(george, tom);

 fail

?- allGf();
  paul is grandfather of george
  tom is grandfather of john
  henk is grandfather of george

  fail

?- allAnc();
  paul is ancient of john
  john is ancient of george
  tom is ancient of mary
  henk is ancient of martha
  mary is ancient of john
  martha is ancient of george
  paul is ancient of george
  tom is ancient of john
  tom is ancient of george
  henk is ancient of george
  mary is ancient of george

  fail


m Что делалось

Запросы и работа Флэнг-интерпретатора вряд ли нуждаются в дополнительных комментариях. Обратим только внимание, что представители семейства обозначались атомами, которые начинаются со строчных букв. Переменные же начинаются с заглавных букв. Отличие между ними ключевое - атомы являются константами, а вместо переменных можно подставлять значения.






Контакты
664003 Иркутск, ул. К. Маркса, 1, Иркутский государственный университет, Центр новых информационных технологий

email

 
Заметки*
• Открытая система
• Пакетирование
• XML
• Тексты
• Естественнонаучные ресурсы
• Ресурсы как модели
• Форматы ресурсов
• Информационные уровни
• Трудности
• Учебные объекты
• "Опыт человечества"
• Коммуникативные системы
• О пользе RSS
• Проблема интернета
• Осмысленный интернет
• Идентификация ресуров
• Метаданные и будущее
• Дублинское ядро
• Метаданные и знания
• Онтологии
*Набор кратких заметок и высказываний, посвященных различным аспектам информатизации образования. Что называется - "заметок по поводу...".

Онлайн-сервисы**
• Сайт кафедры математического анализа
• Форум с поддержкой математических формул.
• Flang-online
• TeX->MathML->GIF.
• MathML->GIF.
• Flang-Meta.
• QTI-тестирование с поддержкой математических формул.
• Meta-ZIP
• UDC
• Font-Test
**список эксперементальных сервисов, на которых апробировались реализуемые группой технологии. Сервисы созданы на основе базовых модулей.
Библиотека***
• Онтологии и метаописания
• Учебные объекты
• Языки программирования и логика
• eLearning and Knowledge
• Digital Libraries and Repositories
• Книжки и учебники
***Коллекция публикаций по тематике, собранная из открытых интернет-источников.

.



Copyright ® 2002-2005, TeaCODE.com