Логическое и функциональное программирование (стр. 11 из 16)

Атомы и списки будем называть S – выражениями.

Для представления списков будем использовать совокупность ячеек памяти, каждая из которых содержит два указателя. Первый указатель играет роль указателя на сына, второй – на брата. Например, список (А В) будет иметь вид.

Отсутствие указателя будем обозначать символом y.

Список (* (+ 2 3) с) будет иметь представление:

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

При записи выражения каждой стрелке, не заканчивающейся на атоме, соответствует открывающаяся скобка, каждому символу y - закрывающаяся скобка, каждому атому – сам атом.

Этой схеме соответствует список ((А)(В)).

Вернемся к определению атома. Фактически атомы являются функциями, аргументы которых представляют собой следующие за ними S – выражения. В свою очередь аргумент сам может быть функцией, которую надо вычислить. Поэтому возникает необходимость определять, что представляет собой данный элемент: значение выражения L или символьное имя L какого-то S – выражения. В первом случае перед выражением ставится‘ или указатель QUOTE. Апостроф запрещает вычисление следующего за ним S- выражения, которое воспроизводится без изменений.

Для задания выражений введем функцию Setq:

(Setq <атом> <S – выражение>)

(Setq <атом> ‘<S – выражение>)

В первом случае выражение должно быть вычислено, во втором – на вычисляется. Кроме того, Setq связывает полученный результат с атомом.

(Setq L1 (+ 4 5))

(Setq L1 ‘(+ 4 5))

В первом случае L1 связано с (9), во втором – с (+ 4 5).

Функция CAR возвращает в качестве значения первый элемент списка, то есть его голову. Функция имеет смысл, только для аргументов, являющихся списками, имеющими голову.

(CAR ‘ (A B C)) ® A

(CAR ‘ A) ® ошибка, А не список.

Функция CDR возвращает хвост списка. Если список состоит из одного элемента, то результатом является Nil.

(CDR ‘ (A B C)) ® (B C)

Комбинация вызовов CAR и CDRвыделяет произвольный элемент списка. Для простоты эту комбинацию записывают в виде:

(C…R список)

Вместо многоточия записывается комбинация из букв А (для CAR) и D (для CDR).

(CADDAR L) = (CAR (CDR (CDR (CAR L))))

Функция CONS строит новый список из переданных ему головы и хвоста.

(CONS голова хвост)

(CONS ‘a ‘(b c)) ® (a b c)

(CONS ‘(a b) ‘(c d)) ® ((a b) c d)

(CONS (+ 1 2) ‘(+ 4)) ® (3 + 4)

Здесь первый аргумент без апострофа, поэтому берется как значение.

(CONS ‘(+ 1 2) ‘(+ 4)) ® ((+ 1 2) + 4)

(CONS ‘(a b c) Nil) ® ((a b c))

(CONS Nil ‘(a b c)) ® (Nil a b c)

Предикат ATOMиспользуется для анализа списков, а именно, для идентификации является ли объект атомом или нет.

(ATOM ‘x) ® T

(ATOM (CDR ‘(A B C))) ® Nil. Атом от списка (BC) естественно False.

(ATOM (ATOM (+ 2 3))) ®T.

Результат сложения чисел атом. Т также является атомом.

(EQUAL <S-выр1> <S-выр2>) ®T, если и только если значения обоих выражений равны.

(EQ <S-выр1> <S-выр2>) ®T, если и только если значения обоих выражений равны и представляют один физический список.

(AND <S-выр1> <S-выр2> … <S-вырn>) – если встречается Nil,, возвращается Nil, иначе значение последнего выражения.

(OR <S-выр1> … <S-вырn>) – если при просмотре встречается выражение отличное от Nil, то оно возвращается, иначе Nil.

(NOT <S-выр>) ®T, если и только если значение выражения есть Nil.

Определять функции будем согласно l - исчислению.

(l (x₁, x₂, …, x_n) f)

x_i – формальный параметр.

f – тело функции.

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

(l (x y) (+ (* x x) (* y y))).

Чтобы произвести вычисления будем осуществлять l - вызов.

(l - выражение a₁, …, a_n),

Здесь a_i – форма , задающая фактические параметры.

((l (xy) (+ (* xx) (* yy))) 2 3) - дает 13.

Для того чтобы определить новую функцию будем использовать запись:

(DEFUN <имя> <l - выражение>).

Для удобства исключим значок l и внешние скобки.

(DEFUN проценты (часть целое) (* (/ часть целое) 100)).

Вызов:

(проценты 4 20)

Результат: 20.

Условное выражение COND имеет следующий вид:

(COND (p1 a1)

(p2 a2)

. . .

(pn an))

Значение COND определяется следующим образом:

1. Выражения pi вычисляются последовательно слева направо (сверху вниз) до тех пор, пока не встретится выражение, значение которого отлично от Nil.

2. Вычисляется результирующее выражение ai соответствующее этому pi и полученное значение возвращается в качестве результата.

3. Если нет ни одного pi, значение которого отлично от Nil, то значение COND равно Nil/

В более общем виде:

(COND (p1 a1)

…

(pj)

…

(pk ak₁ … ak_n)

…)

В этом случае:

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

- если условию соответствует несколько S – выражений, то при его истинности они вычисляются слева направо и результатом будет значение последнего S – выражения.

Реализуем логические связки И, ИЛИ, ®.

(defun И(x y) (COND (x y) (T Nil)))

(defun ИЛИ (x y) (COND (x T) (T y)))

(defun ® (x y) (COND (x y) (T T)))

С помощью COND можно реализовать различные варианты условных выражений.

(if <условие> <то-выр> <иначе-выр>) º (COND (<условие> <то-выр>) (T <иначе-выр>))

Чтобы говорить о некотором свойстве, связанным с некоторым объектом и его значением, будем использовать функцию:

(PUTPROP <атом1> <список> <атом2>).

Эта функция связывает свойства, выраженные списком <атом2>, с конкретным объектом с именем <атом1>. Конкретные значения свойства задаются в объекте <список>.

(PUTPROP ‘Петр ‘(Иван Ирина) ‘Дети).

Чтобы узнать обладает ли объект данным свойством, будем использовать функцию GET:

(GET <атом1> <атом2>) ® значение свойства.

(GET ‘Петр ‘Дети) ® (Иван Ирина)

Теперь сформулируем алгоритм для вычисления списков. Алгоритм должен вычислять значение списка в последовательности, задаваемой указателями – «сыновьями», а затем учитывается последний из встреченных указателей «братьев». После этого учитываются указатели «сыновья», связанные с этим последним, и так далее, пока не получается окончательное значение для данной ветви. Затем вычисления повторяются снова, охватывая выражения более высокого уровня, и так до тех пор пока не будет определено значе ние всего списка. Те части всего выражения, которые ожидают вычисления значений их аргументов, называются квазарами.

Этот алгоритм представим в вида процедуры Eval(S), где S – выражение.

Sub Eval(S)

If S естьатом then

Возврат ¬ значение S

Else

If S1 = QUOTE then

Возврат ¬S2

Else

S1 есть функция

IfS1 указывает на специальную обработку, выполнить эту обработку

Else

Применить Eval ко всем элементам S2 последовательно и затем рекуррентно использовать их найденные значения.

Окончательный возврат ¬S1 (Eval (S2))

End If

End If

EndIf

S1 – первый сын для S. S2 – элементы выражения S, представляющие собой множество братьев выражения S1.

3.4.1 Практические задания

1.Создать машинное представление для списков:

(a (b c) ( (d) e (f)))

( + a (* b (/ (+ c (/ d e)) f)))

(/ (+ ( a (- (b c)))) (* (/ (d b)) a))

(flat (hd (a) flat (tl (a) b)))

(cons (copy (hd (l) )) copy (tl (l)))))

2.Определить значения списков:

(car ‘(a (b c) ((d) e (f))))

(cdr ‘(a (b c) ((d) e (f))))

(cdadr ‘(a (b c) ((d) e (f))))

(consnil ‘(суть пустой список))

(cons (car ‘(a b))(cdr ‘(a b)))

(car ‘(car (a b c)))

(cdr (car (cdr ‘(a b c))))

3.Запишите последовательность вызовов CAR и CDR, выделяющих из приведенных списков символ «цель». Упростите эти последовательности с помощью функций C…R.

(1 2 цель 3 4)

((1) (2 цель ) (3 4 цель)))

((1 (2 (3 4 цель))))

4.Определить вид списка, имеющего следующее машинное представление:

4. Реализовать с помощью COND логические операции: эквивалентность, штрих Шеффера, стрелка Пирса.

5. Реализовать функцию reverse, переставляющую местами элементы списка.

3.4.2 Компьютерное задание

Создать БД для индуктивного вывода и реализовать программу заполнения этой базы для оператора Setq. Возможная структура таблицы для хранения списков:

Имя поля	Тип	Комментарий
List	Text	Наименование списка
BeginList	Boolean	Является ли началом списка, если да -TRUE
SonPointer	Long	Указатель на сына
BrotherPointer	Long	Указатель на брата
ValueEl	Text	Значение. Для указателей Nil
ValueType	Text	Тип значения: ячейка, список, пустой список, атом, функция

Пример заполнения:

Пусть последовательно создаются 2 списка:

Setq a (* (+ 2 3) c)

Setq Second ((a) (b))

Структура списков: Список а

Список Second

Таблица для этих списков будет иметь вид:

List	BeginList	SonPointer	BrotherPointer	ValueEl	ValueType
a	true	2	4	Nil	ячейка
a	false	3	0	Nil	ячейка
a	false	0	0	*	функция
a	false	5	11	Nil	ячейка
a	false	6	7	Nil	ячейка
a	false	0	0	+	функция
a	false	8	9	Nil	ячейка
a	false	0	0	2	атом
а	false	10	0	Nil	ячейка
а	false	0	0	3	атом
а	false	12	0	Nil	ячейка
a	false	0	0	c	Пустой список
Second	true	14	16	Nil	ячейка
Second	false	15	0	Nil	ячейка
Second	false	0	0	a	список
Second	false	17	0	Nil	ячейка
Second	false	18	0	Nil	ячейка
Second	false	0	0	b	Пустой список

Порядок выполнения