Гордеев Александр Петрович.
1. Введение в декларативные языки.
Все языки программирования можно разделить на 2 категории: императивные и декларативные.
Императивные программы описывают то, как программа должна вычислять результат.
В отличии от этого декларативная программа описывает, что нужно получить, т.е. программа формулирует задачу, а вычислительный процесс строится автоматически, исходя из этого определения.
Var a,n,x:integer;
…
N=x;
A=1;
While n>0 do
Begin
A=a*n;
N=n-1;
End;
В этой программе можно увидеть процесс последовательных шагов, причем программа имеет состояние(переменные a, n, x)и на каждом шаге это состояние изменяется. В каждом операторе паскале так или иначе присутствуют присваивания. Императивная программа состоит из приказов команд, которые меняют состояние.
В декларативных языках состояние программы явно не определяется. А есть формальное определение того, что нужно вычислить.
В логической программе это множество формул исчисления предикатов. То что надо вычислить задается логическими формулами.
В функциональном программировании используется определения такие же, как и в математике.
В функциональных программах переменные обладают тем, что они не изменяют свое значение, также как в алгебре.
Функциональная программа – это множество определений функций(возможно рекурсивных) + выражение, которое нужно вычислить.
Пример функц. программы которая вычисляет факториал.
f 0 = 1 (1)
f n = n * (f(n-1)) (2)
Здесь знак = обозначает равенство по определению. Как в алгебре:
A(B+C) = AB+AC.
В этом примере определяется функция f, причем определение рекурсивно.
Здесь видно соответствие между матем.формулировкой и программой.
Функц.программа подчиняется алгебраическим законам.
Более того, процесс вычисления результатов в функциональной программе тоже можно представить, как алгебраическое преобразование.
Свойство программы, заключающейся в том, что с ней можно делать алгебраич.преобразования, называется прозрачностью по ссылкам.
Прозрачность по ссылкам.
Тут видно, как вычисляется факториал от 3. Здесь стараются уйти от скобок.
f 3 =2
3 * (f(3-1)) = ариф
3 * (f 2) = 2
3 * 2 * (f(2-1)) = ариф
3 * 2 * (f 1) = 2
3 * 2 * 1* (f (1-1)) = ариф
3 * 2 * 1 * (f 0) = 1
3 * 2 * 1 * 1 = ариф
Логическое программирование
Самый распространенный язык логич.программирования – Prolog.
Его основа – логика предикатов первого порядка (исчисление предикатов).
Программа – совокупность хорновских дизъюнктов.
Выполнение программы – доказательство утверждения методом резолюций на основе опровержения.
В исчислении предикатов мы использовали прежде всего предметные константы, которые обознач. конкретные вещи, переменные. Переменные и константы входили в состав предикатов.
P(a) – предмет (константа а) обладает свойством P.
q(a,b) – а и b находятся в отношении q.
Из такого вида предикатов строится логич. программа. Предикат или его отрицание называется литерой. А дизъюнкция литер назыв дизъюнктой.
Дизъюнкт назыв хорновским, если он имеет не более одной положительной литеры. Они сокращают пространство перебора….
Т.к. программа должна автоматически выбирать резольвенты, то нужно найти такое представление программы, чтобы это было наиболее простым.
Если программа содержит дизъюнкт с одной положительной литерой, то такой дизъюнкт назыв фактом.
Если дизъюнкт содержит несколько литер, то вид его может быть таким:
НЕ p1 или НЕ p2 или ….. НЕ Pn или P
Одна литера положительная, остальные отрицательные.
Эту формулу можно привести к виду с импликацией:
P1 и Р2 и ….. Pn -> P
В прологе такой дизъюнкт назыв правилом и записывается в виде:
P:-p1,p2,…pn
, конъюнкция
:- импликация
(предикат P истинен если истинен p1, p2 …. pn)
Дизъюнкт не имеющий ни одной положительной литеры назыв списком целей.
Таким образом, факты и правила можно считать процедурами программы, а список целей – главной программой.
Таким образом, выполнение логич программы, это доказательство некого утверждения методом резолюции на основе опровержения.
Граф отношения родитель.
Иван
родитель |
ребенок |
|
Федор |
Марья |
Федор |
Федор |
Павел |
Елизавета |
Павел |
Елизавета |
Павел |
|
|
|
|
Факты:
Каждый факт запис именем предиката а дальше идут параметры.
Каждый список целей заканчивается точкой.
Тут предметные константы – идентификаторы.
Нужно уметь отличать маленькие буквы от больших.
Константы с маленькой, переменные с большой.
Rod (I,f) .
Rod (m,f) .
Rod (f, p) .
Rod () .
Rod () .
Вопросы
?- rod(i, f) .
Yes
?- rod(i, e) .
No
Пишем в блокноте, с раширением .pl.
Запустится пролог система и можем задавать список целей, вопросы.
В вопросах можно использовать переменные:
Кто ребенок Ивана ?
?- rod(i,X) .
X = f
Здесь Х – большая буква и обозначает переменную. Мы должны добавить к нашим фактам утверждение, что у I нет ребенка. Система выдаст контрпример. Мы получим X=f.
Можно задавать и несколько целей, строить сложны вопросы.
Кто родитель родителя Анны?
?- родитель (X,Y), родитель (Y, a) .
X = i
Y = боб
Кто общий родитель Ани и Пат?
Мы можем 2 цели связать так, что…
?- родитель (X, энн), родитель (Х, пат).
Х = боб