Парадигмы программирования, 07 лекция (от 05 ноября)

Материал из eSyr's wiki.

Версия от 18:01, 5 ноября 2009; ESyr01 (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
parent(john, mary).
parent(john, george)
parent(george, tom)

sex(male,john).
sex(male,mary).
sex(female,geroge).
sex(male,tom).

brother(X, Y): sex(male, X), parent(Z, X), parent(Z, Y).

?- brother(george, A)
 A=mary;
 A=geroge;
 No

Таким образом, george является братом себе. Как это исправить?

brother(X, Y): sex(male, X), parent(Z, X), parent(Z, Y), X =\= Y.

В этом лсучае второго паразитнрого решения не булет.

Всё, конечно, хорошо, но можно заметить одну особенность: формально, они связываются конъюнкцией. Но если мы переставим X =\= Y в начало, то работать не будет, будет только для констант. Потому, что хначение Y неизвестно. Поск. нельзя перебрать бесконечность. В этом случае порядок существенен.

Получается, что есть неоторое ограничение. Совсем другео дело -- datalog, он если не может зарезолвить, то запоминает и идёт дальше. Он у меет переставлять выражения, но там поиск вширь и там нет дин. структур данных.

После того, как посмотрели пример, посмотрим более строго. Какими данными оперирует Пролог: прологовские данные, на самом деле, очень похожи на s-выр, понятно, почему: его авторы знали лисп. Пролог придуман всё для того же --- решать задачи ИИ. Ещё бы кто сказал, что это такое, есть некое интуитивное понимание.

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

* Атомы
 * Числа. Насколько помнит лектор, - не явл. частью выражения. 
 * Идентификаторы, набранные с маленькой буквы. В прологе они наз. атомами. Можно и с большой, можно и пробелы, можно вообще что угодно, только нужно взять в апострофы.:
mary, john, parent, 'This is an atom, too'. В те времена, когда придумывался Пролог, ещё, видимо, не устоялись парадигмы, и небыло понимания, что имени иднтификаторов. Пролог вообще компилируемый, и одна из задач компиляции --- избавить программу от идент., введённых программистом. Но в прологе ещё одна роль атомов --- роль строк. Можно ли работать со строками иначе? Да, есть строки в дв. кавычках, но они неатомарные, это список из кодов символов. Н так работать со строками, вообще говоря, не очень эфективно. Поэтому приходится работать так.
* Структуры. Это уже дин. данные. это иден., скобка, и далее уже другие арг., в том числе структуры: triangle(point(0,0), point(1,1), point(2,0)). triangle --- функтор. Они исп. для объед. трёх разных сущностей. Треугольник --- тренарная структура, точки --- бинарные. Интересно, что есть. спец. случай функтора, который наз. точка: .(a,b) Она исп. для того же, для чего и в лиспе --- для форм. списков. В прологе они выгл. неск. иначе: [a, b, c, d] Можно ещё отделить головуот хвоста: [a,b,c|d]. [a,b,c,d] предст. как .(a, .(b, .(c, .(d, [])))) . Но здесь это не единст., а доин из многоих способов городить списки. Более того, здесь можно менять число арг. у функторов. Казалось бы, средства богаче, но ничто не мешает написать в лиспе
(triangle
  (point 0 0)
  (point 1 1)
  (point 2 0)
)

Но это более громоздко. Зачем это сделали в Прологе? Вероятно, для удобства. Аналогично -1 --- -(1), 2+3 --- +(2, 3). Другое дело, что вычисляться оно не будет само.

Как работает пролог? Есть ключевое для пролога понятие: унификация. Это сопоставление двух термов. Под термами понимается произв. прологовское выражение. Есть два терма, их можно скормить на вход унификатору. У нас есть нек. количество перем., некоторые из них могут иметь (а могут не иметь) знач. к нач. унифик. счто явл. рез-том:

* Термы унифиц. нельзя
* Да, можно, для этого нужно, чтобы переменные приняли такие-то значения.

Переменные предст. собой контекст. После работы унифик. контекст может дополниться.

Как работает унификатор:

* Два атома унифиц., если они одинаковые. В противном случае они не унифиц.
 * 1 1 => OK
 * 1 2 => ∅
 * mary mary => OK
* Если имеются две структуры, то первыми унифиц. функторы структуры. Если они унифиц., то идём дальше. Сравниваем арность. Если не равно, то прекращаем это дело, если арность одинаковая, то идём дальше и унфиц. аргументы. Во время унифик. могут появл. новые зн. переменных. 
* Переменная. Если с одной стороны стоит переменная. Первый вариант --- она связана. Тогда унифик. происз. так, как если бы вместо перем. стояло её знач. Несвязанная перем. унифиц. с чем угодно.

Как работает пролог-решатель. Программа на прологе состоит из процедур. Предикат пролога сост. из предложений(?). Если переменных в предл. нет, то это факт, в противном случае --- не факт. Например, parent('Lord', X) --- не факт.

Кроме заголовка у процедуры есть ещё предложения. Чем объединены меджу собой: у них одинак. имя функтора и арность. Например,

a(b,c).    a/2
a(e,f,g,h) a/4

Они принадл. к разным процедурам.

Как работает решательЖ Видя цель, решатель пытается найти в программе процедуру, которая соотв. именем и арносттю цели. Если не найдена такая процедура --- неуспех. Если нашли, что что делаем: мы последовательно перебираем предложения и пытаемся цель унифиц. с головой предлож. по описанному ранее алгоритму. Если не унифиц., то неуспех, если унифиц., то нач. вычисл. цели предлож, одну за другой. Интересно вот что: в каждом случае может получиться неск. решений (предложений-то несколько). Если известно, что дальше есть другие предложения, то появл. точки развилки (они, кстати, отъедают память).

Так пролог и работает. Фактически перебором.

На прологе очень хорошо решаются переборные задачи. Например: классич. задача о 8 ферзях. Понятно, что если доска n×n, то больше n досок быть не может. На прологе пишется строк в 15.

Пролог стоит изучить даже несмотря на то, что он редко где используется. Если на лиспе можно указать проекты и людей, которые на нём пишут, то для пролога Лектор это сделать не готов.

С другой стороны, есть достойные реализации --- swi prolog.

Рассмотрим пару примеров. Коли есть списки, напишем пример на списки. Является ли заданныцй элемент элементом заданного списка?

member(a, [a|_]).
member(a, [_|L]) :- member(a,L).

Как это будет вычисляться? (хреново будет вычисляться, потому что a маленькая --- ManMachine)

member(A, [A|_]).
member(A, [_|L]) :- member(A,L).
цель:member(1, [2, 3, 1])
  member(A, [A|_]). --- унификация не удалась
  member(A, [_|L]) :- member(A,L). --- унификация при A1=1, L1=[3,1]
  
  цель: member(1, [3, 1])
    member(A, [A|_]). --- унификация не удалась
    member(A, [_|L]) :- member(A,L). --- унификация при A2=1, L2=[1]
    цель: member(1, [1])
      member(A, [A|_]). --- унификация при A3=1, _=[]
    OK
  OK
OK

При этом возникнет развилка, будет попытка зарезолвить member(1, []), но оно ни во что не унифицируется.

Гораздо интереснее, если мы сделаем вот так вот:

member(X, [2, 3, 1])

Здесь каждый раз будут появляться развилки. И каждый раз унификация будет проходить:

цель:member(X, [2, 3, 1])
  member(A, [A|_]). --- унификация при X=2
  развилка
  member(A, [_|L]) :- member(A,L). --- унификация при A1=X, L1=[3,1]
  цель: member(X, [3, 1])
    member(A, [A|_]). --- унификация при X=3
    развилка
    member(A, [_|L]) :- member(A,L). --- унификация при A2=X, L2=[1]
    цель: member(X, [1])
      member(A, [A|_]). --- унификация при X=1
      развилка
      member(A, [_|L]) :- member(A,L). --- унификация при A3=X, L3=[]
      цель: member(X, [])
      унификация не удалась для обоих предложений.
    OK
  OK
OK


Введение в парадигмы программирования


01 02 03 04 05 06 07 08 09 10 11


Календарь

Сентябрь
24
Октябрь
01 08 15 22 29
Ноябрь
05 12 19 26
Декабрь
03

Экзамен по курсу пройдёт 10 декабря 2009 года в 18:00 в аудитории 524. | Список экзаменационных вопросов


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
Личные инструменты
Разделы