Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные

Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные

^ Несколько слов о программной реализации
Настало время уделить некое внимание рассмотрению программной реализации спис­ков и списочных структур. Это нужно для более узкого осознания того, что про­исходит во время работы многофункциональной Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные программки, как на каком-либо ре­а­ли­зо­ван­ном многофункциональном языке, так и на абстрактном языке.

Каждый объект занимает в памяти машины какое-то место. Но атомы пред­с­тав­ля­ют Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные собой указатели (адреса) на ячейки, в каких содержатся объекты. В данном случае пара z = x : y графически может быть представлена так, как показано на последующем рисунке.

А
дрес ячейки, которая содержит указатели Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные на x и y, и есть объект z. Как видно на ри­сун­ке, пара представлена 2-мя адресами — указатель на голову и указатель на хвост. Тра­диционно 1-ый указатель (на рисунке выделен голубым Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные цветом) именуется a-поле, а 2-ой указатель (на рисунке — зеленый) именуется d-поле.

Для удобства представления объекты, на которые указывают a- и d-поля, в предстоящем бу­дут записываться конкретно в Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные сами поля. Пустой перечень будет обозначаться пе­ре­черкнутым квадратом (указатель ни на что не показывает).

Таким макаром, списочная структура, которая рассмотрена несколькими параграфами ра­нее ([a1, [a2, a3, [a4]], a5]) может быть представлена Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные так, как показано на последующем ри­сун­ке:

На этом рисунке также отлично проиллюстрировано понятие уровня вложенности — ато­мы a1 и a5 имеют уровень вложенности 1, атомы a2 и a3 — 2, а Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные атом a4 — 3 со­от­вет­с­т­вен­но.

Остается отметить, что операция prefix просит расхода памяти, ибо при кон­с­т­ру­и­ро­ва­нии пары выделяется память под Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные указатели. С другой стороны обе операции head и tail не тре­буют памяти, они просто возвращают адресок, который содержится соответственно в a- либо d-поле.
Примеры
^ Пример 3. Операция prefix.

Для начала нужно разглядеть более Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные тщательно работу операции prefix. По­яс­не­ние работы будет проведено на трёх более либо наименее общих примерах:

1. prefix (a1, a2) = a1 : a2 (при всем этом итог не является элементом List Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные_str (A)).

2. prefix (a1, [b1, b2]) = [a1, b1, b2]

3. prefix ([a1, a2], [b1, b2]) = [[a1, a2], b1, b2]

^ Пример 4. Функция определения длины перечня Length.

Перед тем, как фактически начать реализовывать функцию Length, нужно осознать Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные, что она должна возвращать. Понятийное определение результата функции Length может зву­чать как «количество частей в перечне, который передан функции в качестве па­ра­мет­ра». Тут появляется два варианта Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные — функции передан пустой перечень и функции передан не­пустой перечень. С первым случаем все ясно — итог должен быть нулевым. Во вто­ром случае задачку можно разбить на две подзадачи, методом разделения переданного перечня на Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные голову и хвост с помощью операций head и tail.

Осмысленно, что операция head возвращает 1-ый элемент перечня, а операция tail воз­вращает перечень из оставщихся частей. Пусть известна длина перечня Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные, приобретенного с помощью операции tail, тогда длина начального перечня будет равна известной длина, уве­личенной на единицу. В данном случае можно просто записать определение самой фун­к­ции Length:

Length ([]) = 0

Length Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные (L) = 1 + Length (tail (L))


^ Типы в многофункциональных языках
Как понятно, аргументами функций могут быть не только лишь переменные базисных типов, да и другие функции. В данном случае возникает понятие функций высшего порядка Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные. Но для рассмотрения функций высшего порядка нужно ввести понятие фун­к­ци­о­наль­но­го типа (либо тип, возвращаемый функцией). Пусть некая функция f — это функция од­ной переменной из огромного количества Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные A, принимающая значение из огромного количества B. Тогда по оп­ре­делению:

#(f) : A  B

Символ #(f) обозначает «тип функции f». Таким макаром, типы, в каких есть знак стрел­ки , носят заглавие многофункциональных типов Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные. Время от времени для их обозначения ис­поль­зу­ет­ся более утонченная запись: BA (дальше будет употребляться только стрелочная запись, т.к. для неких функций их типы очень трудно представить с Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные помощью сте­пе­ней).

К примеру: #(sin) : Real  Real

#(Length) : List (A)  Integer

Для функций многих аргументов определение типа можно выводить с помощью опе­ра­ции декартового произведения (к примеру, #(add(x, y)) : Real  Real Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные  Real). Но в фун­кциональном программировании таковой метод определения типов функций многих пе­ре­менных не прижился.

В 1924 году М. Шёнфинкель предложил представлять функции многих аргументов как последовательность функций 1-го аргумента Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные. В данном случае тип функции, которая складывает два реальных числа, смотрится так: Real  (Real  Real). Т.е. тип таких функций выходит поочередным применением знака стрелки . Объяснить этот процесс можно на последующем примере Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные:

^ Пример 5. Тип функции add (x, y).

Предположительно, любой из аргументов функции add уже означен, пусть x = 5, y = 7. В данном случае из функции add методом удаления первого аргумента выходит новенькая фун Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные­к­ция — add5, которая добавляет к собственному единственному аргументу число 5. Ее тип по­лу­ча­ется просто, он по определению такой: Real  Real. Сейчас, ворачиваясь вспять, можно по­нять, почему тип функции add равен Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные Real  (Real  Real).

Для того чтоб не ухищряться с написанием функций типа add5 (как в прошлом при­мере), была выдумана особая аппликативная форма записи в виде «оператор – опе­ранд». Предпосылкой для этого послужило Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные новое видение на функции в фун­к­ци­о­на­ль­ном программировании. Ведь если обычно числилось, что выражение f (5) обозначает «при­менение функции f к значению аргумента, равному 5» (т.е Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные. рассчитывается только ар­гу­мент), то в многофункциональном программировании считается, что значение функции также вы­числяется. Так, ворачиваясь например 8, функцию add можно записать как (add (x)) y, а ког­да аргументы Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные получают определенные значения (к примеру, (add (5)) 7), поначалу вы­чис­ля­ют­ся все функции, пока не появится функция 1-го аргумента, которая применяется к пос­леднему.

Таким макаром, если функция f имеет тип A Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные1  (A2  ( ... (An  B) ... )), то чтоб пол­нос­тью вычислить значение f (a1, a2, ..., an) нужно поочередно провести вы­чис­ле­ние ( ... (f (a1) a2) ... ) an. И результатом вычисления будет объект типа B Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные.

Соответственно выражение, в каком все функции рассматриваются как функции од­но­го аргумента, а единственной операцией является аппликация (применение), на­зы­ва­ют­ся выражениями в форме «оператор – операнд». Такие функции получили заглавие Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные «кар­ри­ро­ванные», а сам процесс сведения типа функции к виду, приведенному в прошлом аб­за­це — каррированием (по имени Карри Хаскелла).

Если вспомнить -исчисление, то обнаружится, что в Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные нем уже есть математическая аб­с­т­ракция для аппликативных форм записей. К примеру:

f (x) = x2 + 5  x.(x2 + 5)

f (x, y) = x + y  y.x.(x + y)

f (x, y Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные, z) = x2 + y2 + z2  z.y.x.(x2 + y2 + z2)

И т.д....
^ Несколько слов о нотации абстрактного языка Эталоны и клозы
Стоит отметить, что в нотации абстрактного многофункционального языка, который ис­пользовался до сего Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные времени для написнаия примеров функций, можно было бы использовать та­кую конструкцию, как if-then-else. К примеру, при описании функции Append (см. при­мер 7), её тело можно было Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные бы записать последующим образом:

Append (L1, L2) = if (L1 == []) then L2

else head (L1) : Append (tail (L1), L2)

Но данная запись чревата недопониманием и сложным разбором. Потому даже в примере 7 была применена нотация Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные, которая поддерживает так именуемые «образцы».

Определение

Прототипом именуется выражение, построенное при помощи операций конструирования дан­ных, которое употребляется для сравнения с данными. Переменные обозначаются про­писными знаками, константы — строчными.

Примеры образцов:

5 — просто числовая константа
X Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные — просто переменная
X : (Y : Z) — пара
[X, Y] — перечень

К образчикам предъявляется одно требование, которое должно производиться бес­пре­ко­с­лов­но, по другому сравнение с эталонами будет выполнено ошибочно. Требование это звучит Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные сле­дующим образом: при сравнении эталона с данными означивание переменных дол­жно происходить единственным образом. Т.е., к примеру, выражение (1 + X  5) мож­но использовать как эталон, т.к. означивание переменной X происходит единственным Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные об­разом (X = 4), а выражение (X + Y  5) использовать в качестве эталона нельзя, ибо оз­на­чить переменные X и Y можно разным образом.

Не считая образцов в многофункциональном программировании вводится Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные такое понятие, как «клоз» (от англ. «clause»). По определению клозы смотрятся так:

def f p1, ..., pn = expr

где:

def и = — константы абстрактного языка
f — имя определяемой функции
pi — последовательность образцов (при всем этом n  0)
expr — выражение

Т
аким Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные образом, определение функции в многофункциональном программировании есть прос­то последовательность клозов (может быть состоящая из 1-го элемента). Для того, чтоб уп­ростить запись определений функций, дальше слово def будет опускаться.

^ Пример 6. Эталоны и Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные клозы в функции Length.

Length ([]) = 0

Length (H:T) = 1 + Length (T)

Пусть вызов функции Length произведен с параметром [a, b, c]. В данном случае начнет свою работу механизм сравнения с прототипом Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные. Поочередно перебираются все кло­зы и делаются пробы сравнения. В этом случае удачное сравнение будет толь­ко во 2-м клозе (т.к. перечень [a, b, c] не пуст).

Интерпретация вызова функции заключается в Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные нахождении первого по порядку сверху вниз эталона, удачно сравнимого с фактическим параметром. Значение переменных об­разца, означиваемые в итоге сравнения, подставляются в правую часть клоза (вы­ражение expr), вычисленное значение которой Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные в данном контексте объявляется зна­че­ни­ем вызова функции.
Охрана
При написании функций в абстрактной нотации допустимо использовать так на­зы­ва­е­мую охрану, т.е. ограничения на значения переменных Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные эталона. К примеру, при ис­поль­зо­ва­нии охраны функция Length будет смотреться приблизительно последующим образом:

Length (L) = 0 when L == []

Length (L) = 1 + Length (tail (L)) otherwise

В рассмотренном коде слова when (когда) и Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные otherwise (в неприятном случае) являются за­резервированными словами языка. Но внедрение этих слов не является не­об­хо­ди­мым условием для организации охраны. Охрану можно организовывать разными спо­собами, в том Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные числе и при помощи -исчисления:

Append = [].(L.L)

Append = (H:T).(L.H : Append (T, L))

Представленная запись не очень читабельна, потому употребляться она будет исключительно в последних случаях по необходимости.
^ Локальные Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные переменные
Как уже говорилось, внедрение локальных переменных представляет собой по­боч­ный эффект, потому оно неприемлимо в многофункциональных языках. Но в неких слу­чаях внедрение локальных переменных носит оптимизирующий нрав, что Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные поз­во­ляет сберечь время и ресурсы во время вычислений.

Пусть f и h — функции, и нужно вычислить выражение h (f (X), f(X)). Если в язы­ке нет оптимизирующих способов, то в Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные данном случае произойдет двойное вычисление вы­ра­же­ния f (X). Чтоб этого не вышло, можно прибегнуть к такому утонченному спо­со­бу: (v.h (v, v))(f (X)). Естественно, что Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные в этом случает выражение f (X) вычислится пер­вым и один раз. Для того, чтоб минимизировать внедрение -исчисления, дальше бу­дет применяться последующая форма записи:

let v = f (X) in h (v, v)

(слова Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные let, = и in — зарезервированы в языке). В данном случае v будет называться ло­каль­ной переменной.
^ Накапливающий параметр — аккумулятор
Случается так, что при выполнении функции только серьезно встает неувязка рас­хода памяти Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные. Эту делему можно объяснить на примере функции, вычисляющей фак­то­риал числа:

Factorial (0) = 1

Factorial (N) = N * Factorial (N – 1)

Если провести пример вычисления этой функции с аргументом 3, то можно будет уви­деть последующую Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные последовательность:

Factorial (3)

3 * Factorial (2)

3 * 2 * Factorial (1)

3 * 2 * 1 * Factorial (0)

3 * 2 * 1 * 1

3 * 2 * 1

3 * 2

6

На примере этого вычисления наглядно видно, что при рекурсивных вызовах функций очень очень употребляется память. В этом случае количество памяти пропорционально зна­чению аргумента, но аргументов Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные может быть большее число, например. Появляется ре­зон­ный вопрос: можно ли так написать функцию вычисления факториала (и ей подобные), что­бы память использовалась мало?

Чтоб ответить на данный вопрос положительно, нужно разглядеть понятие Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные аккума (накопителя). Для этого можно разглядеть последующий пример:

^ Пример 7. Функция вычисления факториала с аккумом.

Factorial_A (N) = F (N, 1)


F (0, A) = A

F (N, A) = F ((N – 1), (N * A))

В этом Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные примере 2-ой параметр функции F играет роль аккумулирующей пе­ре­мен­ной, конкретно в ней содержится итог, который ворачивается по окончании ре­кур­сии. Сама же рекурсия в данном случае воспринимает вид «хвостовой», память Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные при всем этом рас­хо­ду­ется лишь на хранение адресов возврата значения функции.

Хвостовая рекурсия представляет собой особый вид рекурсии, в какой имеется един­ственный вызов рекурсивной функции и при Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные всем этом этот вызов производится после всех вы­числений.

При реализации вычисления хвостовой рекурсии могут производиться с помощью итераций в неизменном объеме памяти. На практике это обозначает, что «хороший» транслятор многофункционального языка Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные должен «уметь» распознавать хвостовую рекурсию и реализовывать её в виде цикла. В свою очередь, способ накапливающего параметра не всегда приводит к хвостовой рекурсии, но он совершенно точно помогает уменьшить общий объём памяти.
^ Принципы Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные построения определений с накапливающим параметром

  1. Вводится новенькая функция с дополнительным аргументом (аккумом), в котром на­капливаются результаты вычислений.

  2. Изначальное значение аккумулирующего аргумента задается в равенстве, связывающем ста­рую и новейшую Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные функции.

  3. Те равенства начальной функции, которые соответствуют выходу из рекурсии, за­ме­ня­ют­ся возвращением аккума.

  4. Равенства, надлежащие рекурсивному определению, смотрятся как воззвания к но­вой функции, в каком аккумулятор получает то значение Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные, которое ворачивается ис­ходной функцией.

Появляется вопрос: всякую ли функцию можно конвертировать для вычисления с ак­ку­му­ля­тором? Разумеется, что ответ на этот вопрос отрицателен. Построение функций с Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные на­кап­ли­вающим параметром — приём не универсальный, и он не гарантирует получения хвос­то­вой рекурсии. С другой стороны, построение определений с накапливающим па­ра­мет­ром является делом творческим Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные. В этом процессе нужны некие эвристики.

Определение:

Вид рекурсивных определений, позволяющих при трансляции обеспечить вы­чис­ления в неизменном объёме памяти через итерацию, именуется равенствами в ите­ра­тив­ной форме.

Вид равенств в итеративной Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные форме может быть описан последующим образом:

fi (pij) = eij

При всем этом на выражения eij накладываются последующие ограничения:

  1. eij — «простое» выражение, т.е. оно не содержит рекурсивных вызовов, а только опе­ра Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные­ции над данными.

  2. eij имеет вид fk (vk), при всем этом vk — последовательность обычных выражений. Это и есть хвос­товая рекурсия.eij — условное выражение с обычным выражением в условии, ветки которого Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные оп­ре­де­ля­ют­ся этими же 3-мя пт. Конструирование функций»

Для конструирования функций употребляются разные формализмы, одним из которых является синтаксически-ориентированное конструирование. Чтоб использовать последнюю методику, можно пользоваться способом, который Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные в свое время предложил Хоар.

Ниже приводится описание метаязыка, применяемого для определения структур данных (в абстрактном синтаксисе):

  1. ^ Декартово произведение: Если C1, ..., Cn — это типы, а C — это тип, состоящий из мно Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные­жества n-ок вида , ci  Ci, i = 1,n, то говорится, что C — декартово про­из­ве­дение типов C1, ..., Cn и обозначается как C = C1  ...  Cn. При всем этом подразумевается, что определены селекторы Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные s1, ..., sn для типа C, что записывается как s1, ..., sn = selectors C.

Таким же образом записывается конструктор g: g = constructor C. Конструктор — это фун­кция, имеющая тип (С1  ... (Cn  C) ... ), т Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные.е. для ci  Ci, i = 1,n : g c1 ... cn = .

Будет считаться, что справедливо равенство:

x  C : constructor C (s1, x) ... (sn, x) = x

Это равенство именуется теоремой тектоничности. Не считая того, время от Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные времени эту теорему записывают последующим образом:

si (constructor C c1 ... cn) = ci

  1. ^ Размеченное объединение: Если C1, ..., Cn — это типы, а C — это тип, состоящий из объ­единения типов C1, ..., Cn, при условии выполнения «размеченности», то Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные C на­зы­ва­ет­ся размеченным объединением типов C1, ..., Cn. Обозначается данный факт как C = C1 + ... + Cn. Условие размеченности обозначает, что если из C взять какой-либо эле­мент ci, то Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные совершенно точно определяется тип этого элемента Ci. Размеченность можно оп­ределить с помощью предикатов P1, ..., Pn таких, что:

(x  C) & (x  Ci)  (Pi x = 1) & (j  i : Pj x = 0)

Размеченное объединение гарантирует наличие Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные таких предикатов. Данный факт указывается записью: P1, ..., Pn = predicates C. Ещё есть части типа, которые обоз­на­ча­ют­ся так: N1, ..., Nn = parts C.

Как видно, в представленном метаязыке Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные употребляется два конструктора типов:  и +. Да­лее рассматриваются несколько примеров определения новых типов.

^ Пример 8. Формальное определение типа List (A).

List (A) = NIL + (A  List (A))

null, nonnull = predicates List (A)

NIL Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные, nonNIL = parts List (A)

head, tail = selectors List (A)

prefix = constructor List (A)

Смотря на это описание (быстрее — определение) типа, можно обрисовать внешний облик функций, обрабатывающих структуры типа List (A):

Любая функция должна содержать как Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные минимум два клоза, 1-ый обрабатывает NIL, вто­рой — nonNIL соответственно. Этим двум частям типа List (A) в абстрактной записи со­ответствуют селекторы [] и (H : T). Два клоза можно соединить в один с Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные ис­поль­зо­ва­ни­ем охраны. В теле второго клоза (либо второго выражения охраны) обработка элемента T (либо tail (L)) производится той же самой функцией.

^ Пример 9. Формальное определение типа List_str Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные (A).

List_str (A) = A + List (List_str (A))

atom, nonAtom = predicates List_str (A)

Функции над List_str (A) обязаны иметь по последней мере последующие клозы:

1. A  when (atom (A))

2. []  when Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные (null (L))

3. (H : T)  head (L), tail (L)

3.1. atom (head (L))

3.2. nonAtom (head (L))

Пример 10. Формальное определение деревьев и лесов с помеченными верхушками.

Tree (A) = A  Forest (A)

Forest (A) = List (Tree Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные (A))

root, listing = selectors Tree (A)

ctree = constructor Tree (A)

Пример 11. Формально определение деревьев с помеченными верхушками и дугами.

MTree (A, B) = A  MForest (A, B)

MForest (A, B Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные) = List (Element (A, B))

Element (A, B) = B  MTree (A, B)

mroot, mlist = selectors MTree (A, B)

null, nonNull = predicates MForest (A, B)

arc, mtree = selectors Element (A, B)

Утверждается, что неважно какая Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные функция, работающая с типом MTree (A, B), может быть пред­ставлена только через упомянутые 6 операций независимо от того, как она ре­а­ли­зована. Это утверждение можно проверить с помощью диаграммы (быстрее Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные, это ги­пер­граф), на которой ясно вид­но, что к хоть какой части типа MTree (A, B) можно «добраться», ис­пользуя только эти 6 опе­раций.

Для конструирования функций, обрабатывающих структуры Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные данных MTree, не­об­хо­ди­мо ввести несколько дополнительных понятий и обозначений для их. Это делается для прос­тоты. Исходная верхушка, верхушка MForest и верхушка MTree (выходящая из Ele­ment) обозначаются как S Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные0, S1 и S2 соответственно. Для обработки этих вершин не­об­хо­ди­мы три функции — f0, f1 и f2, при этом f0 — это исходная функция, а две последних — ре­кур­сивные Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные.


Набросок 1. Гиперграф для представления структуры MTree

Конструирование функции f0 смотрится просто — у этой функции один параметр T, ко­то­рый соответствует исходной верхушке S0. Две другие функции сконструировать слож­нее.

Функция f1 получает последующие характеристики Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные:

A — метка верхушки;

K — параметр, содержащий итог обработки просмотренной части дерева;

L — лес, который нужно обработать.

f1 A K L = g1 A K when null L

f1 A K L = f1 A Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные (g2 (f2 A (arc (head L)) (mtree (tail L)) K) A (arc L) K) (tail L) otherwise

Эта функция организует режим просмотра дерева «сначала в глубину».

Функция f2 получает последующие характеристики Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные (и это уже должно быть ясно из её вызова во 2-м клозе функции f1):

A — метка верхушки;

B — метка дуги;

T — поддерево для обработки;

K — итог обработки просмотренной части дерева.

f2 A B Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные T K = f1 (mroot T) (g3 A B K) (mlist T)

Стоит отметить, что это вид функций для обработки структур данных MTree. Реализация дополнительных функций g1, g2 и g3 находится в зависимости от определенной Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные задачки. Сейчас можно сконструировать и вид функции f0:

f0 T = f1 (root T) k (mlist T)

где k — это изначальное значение параметра K.

«Доказательство параметров функций»

Формальная задачка: пусть имеется набор Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные функций f = , определённых на об­лас­тях D = . Требуется обосновать, что для хоть какого набора значений d имеет мес­то некое свойство, т.е.:

,

где P — рассматриваемое свойство. К примеру Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные:







Вводится принципное ограничение на рассматриваемые характеристики — характеристики толь­ко полные, т.е. справедливые для всей области D.

Дальше рассматриваются некие виды областей определения D...
^ 1. D — линейно упорядоченное огромное количество.
Полуформально линейно упорядоченное огромное количество Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные можно найти как такое мно­жес­тво, для каждых частей которого можно сказать, какой меньше (либо больше), или они равны, т.е.:

.

В качестве примера можно привести огромное количество целых чисел Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные. Но линейно упо­ря­до­чен­ные огромного количества встречаются в мире многофункционального программирования очень изредка. Взять хотя бы простейшую структуру, которую очень обожают обрабатывать в фун­к­ци­о­наль­ном Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные программировании — перечень. Для списков уже достаточно трудно найти от­но­шение порядка.

Для подтверждения параметров функций на линейно упорядоченных огромных количествах дос­та­точ­но провести индукцию по данным. Т.е. довольно Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные обосновать два пт:

1. — базис индукции;

2. — шаг индукции.

В силу того, что структуры данных изредка образуют линейно упорядоченные мно­жес­тва, более действенным методом оказывается применение способа индукции по пос­т­ро­е­нию Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные типа D.
^ 2. D — определяется как индуктивный класс
Из прошлой лекции понятно, что индуктивный класс определяется через ввод базиса клас­са (это или набор каких или констант di = 0,n  D, или Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные набор первичных типов Ai = 0,n : d  Ai  d  D. Также индуктивный класс определяется с помощью шага ин­дук­ции — заданы конструкторы g1, ..., gm, определённые над Ai и D, и справедливо, что:

.

В Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные данном случае подтверждение параметров функций также резонно проводить в виде ин­дук­ции по даным. Способ индукции по даным в данном случае также очень прост:

1. P (f (d)) нужно обосновать для базиса класса;

2. Шаг индукции Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные: P (f (d)) = P (f (gi (d))).

К примеру, для подтверждения параметров функций для списков (тип List (A)), довольно до­казать рассматриваемое свойство для 2-ух последующих случаев:

1. P (f ([])).

2. .

Подтверждение параметров функций Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные над S-выражениями (тип S-expr (A)) можно про­во­дить на базе последующей индукции:

1. .

2. .

^ Пример 12. Обосновать, что .

Для подтверждения этого характеристики можно использовать только определение типа List (A) и Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные самой функции append (в инфиксной записи употребляется знак *).

1. L = [] : [] * [] = [] = L. Базис индукции подтвержден.

2. . Сейчас пусть применяется конструктор: a : L. Не­об­хо­димо обосновать, что (a : L) * [] = a : L. Это делается с помощью Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные внедрения второго кло­за определения функции append:

«Формализация Многофункционального Прог­рам­ми­ро­вания на базе -исчисления»

  • Объект исследования: огромное количество определений функций.

  • Предположение: будет считаться, что неважно какая функция Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные может быть определена при по­мо­щи некого -выражения.

  • Цель исследования: установить по двум определениям функций и их тож­дес­т­во на всей области определения — . (Тут применена такая но­та­ция: f — некая Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные функция, — определения этой функции в определениях -ис­чис­ле­ния).

Неувязка состоит в том, что обычно при описании функций задается интенсионал этих функций, а позже требуется установить экстенсиональное равенство. Под эк­с Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные­тен­си­о­на­лом функции понимается её график (ну либо таблица в виде огромного количества пар ). Под интенсионалом функции понимаются правила вычисления значения фун­к­ции по данному аргументу Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные.

Появляется вопрос: как учитывать семантику интегрированных функций при сопоставлении их эк­с­тен­сионалов (т.к. очевидно определения этих функций не известны)? Варианты ответов:

  1. Можно попробовать выразить семантику интегрированных функций с помощью механизма -ис Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные­чис­ле­ния. Этот процесс можно довести до варианта, когда все интегрированные функции не содержат непроинтерпретированных операций.

  2. Молвят, что и семантически равны (данный факт обозначается как |= f1 = f2), ес­ли f1 (x) = f Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные2 (x) при хоть какой интерпретации непроинтерпретированных иден­ти­фи­ка­то­ров.
^ Понятие формальной системы
Формальная система представляет собой четверку:

P = , где

V — алфавит.

Ф — огромное количество верно построенных формул.

А — теоремы Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные (при всем этом А  Ф).

R — правила вывода.

В рассматриваемой задачке формулы имеют вид (t1 = t2), где t1 и t2 — -выражения. Если не­которая формула выводима в формальной системе, то данный Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные факт записывается как (|  t1 = t2).

Молвят, что формальная система корректна, если (|  t1 = t2)  (|= t1 = t2).

Молвят, что формальная система полна, если (|= t1 = t2)  (|  t1 = t2).

Семантическое определение понятия «конструкция» (обозначение — Exp):

1. .

2. .

3. .

4. .

5. Никаких других Exp Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные нет.

Примечание: Id — огромное количество идентификаторов.

Молвят, что v свободна в M  Exp, если:

1. M = v.

2. M = (M1M2), и v свободна в M1 либо в M2.

3. M = v’.M Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные’, и v  v’, и v свободна в M’.

4. M = (M’), и v свободна в M’.

Огромное количество идентификаторов v, свободных в M, обозначается как FV (M).

Молвят, что v связана в M Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные  Exp, если:

1. M = v’.M’, и v = v’.

2. M = (M1M2), и v связана в M1 либо в M2 (т.е. один и тот же идентификатор может быть свободен и связан в Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные Exp).

3. M = (M’), и v связана в M’.

Пример 13. Свободные и связанные идентификаторы.

  1. M = v. v — свободна.

  2. M = x.xy. x — связана, y — свободна.

  3. M = (v.v)v. v заходит в это Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные выражение как свободно, так и связанно.

  4. M = VW. V и W — свободны.

Правило подстановки: подстановка в выражение E выражения E’ заместо всех сво­бод­ных вхождений переменной x обозначается как E[x Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные  E’]. Во время подстановки время от времени слу­чается так, что выходит конфликт имён, т.е. коллизия переменных. Примеры кол­ли­зий:

(x.yx)[y  z.z] = x.(z.z)x Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные = x.x — корректная подстановка

(x.yx)[y  xx] = x.(xx)x — коллизия имён переменных

(z.yz)[y  xx] = z.(xx)z — корректная подстановка

Четкое определение базовой подстановки:

1. x[x  E’] = E’

2. y[x  E’] = y

3. (x Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные.E)[x  E’] = x.E

4. (y.E)[x  E’] = y.E[x  E’], при условии, что y  FV (E’)

5. (y.E)[x  E’] = (z.E[y  z])[x  E’], при условии, что y  FV (E’)

6. (E Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные1E2)[x  E’] = (E1[x  E’]E2[x  E’])
^ Построение формальной системы
Таким макаром, на данный момент уже все готово для того, чтоб перейти к построению фор­маль­ной системы, определяющей Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные Функциональное Программирование в определениях -ис­чис­ле­ния.

Верно построенные формулы смотрятся так: Exp = Exp.

Теоремы:

|- x.E = y.E[x  y] ()

|- (x.E)E’ = E[x  E’] ()

|- t = t, в случае Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные, если t — идентификаторы ()

Правила вывода:

t1 = t2  t1t3 = t2t3 ()

t1 = t2  t3t1 = t3t2 ()

t1 = t2  t2 = t1 ()

t1 = t2, t2 = t3  t1 = t3 ()

t1 = t2  x.t1 = x Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные.t2 ()

Определения:

  • Выражение вида x.M именуется -редексом.

  • Выражение вида (x.M)N именуется -редексом.

  • Выражения, не содержащие -редексов, именуются выражениями в обычной форме.
^ Стратегия редукции
1. Обычная редукционная стратегия. На каждом шаге Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные редукции выбирается тек­с­ту­аль­но самый левый -редекс. Подтверждено, что обычная редукционная стратегия га­ран­ти­ру­ет получение обычной формы выражения, если она существует.

2. ^ Аппликативная редукционная стратегия Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные. На каждом шаге редукции выбирается  ре­декс, не содержащий в себе других -редексов. Дальше будет показано, что ап­пли­ка­тивная редукционная стратегия не всегда позволяет получить нормальную форму вы­ра­жения Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные.
^ Соответствие меж вычислениями многофункциональных программ и ре­дук­цией
Работа интерпретатора описывается несколькими шагами:

  1. В выражении нужно выделить некое воззвание к рекурсивной либо встро­ен­ной функции с стопроцентно означенными аргументами. Если выделенное воззвание Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные к встро­енной функции существует, то происходит его выполнение и возврат к началу первого шага.

  2. Если выделенное на первом шаге воззвание к рекурсивной функции, то заместо него под­ставляется тело Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные функции с фактическими параметрами (т.к. они уже означены). Да­лее происходит переход на начало первого шага.

  3. Если больше воззваний нет, то происходит остановка.

В принципе, вычисления в многофункциональной парадигме повторяют шаги редукции, но Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные до­полнительно содержат вычисления интегрированных функций.
^ Представление определений функций в виде -выражений
Показано, что хоть какое определение функции можно представить в виде -выражения, не со­держащего рекурсии. К примеру:

fact = n Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные.if n == 0 then 1 else n * fact (n – 1)

То же самое определение можно обрисовать с помощью использования некого фун­к­ци­онала:

fact = (f.n.if n == 0 then 1 else n * f (n – 1)) fact

в представленном Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные выражении выделен функционал F. Таким об­ра­зом, функцию вычисления факториала можно записать так: fact = F fact. Можно созидать, что хоть какое рекурсивное определение некой функции f можно представить в таком ви Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные­де:

f = F f

Это выражение можно трактовать как уравнение, в каком рекурсивная функция f яв­ля­ется недвижной точкой функционала F. Соответственно интерпретатор фун­к­ци­о­наль­но­го языка можно в Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные таком же ключе рассматривать как численный способ решения этого урав­нения.

Аксиома (без подтверждения):

Хоть какой -терм имеет недвижную точку.

-исчисление позволяет выразить всякую функцию через незапятнанное -выражение без Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные использования интегрированных функций.



ЛИТЕРАТУРА

  1. Братко И. Программирование на языке Пролог для искусственного ума. –

М.: Мир, 1990

  1. Ин Ц., Соломон Д. Внедрение Турбо – Пролога: Пер. с англ. – М.: Мир, 1990

  2. Стобо Дж. Язык программирования Пролог: Пер Несколько слов о программной реализации - Лекция введение. Логическая программа. Основные. с англ. – М.: Радио и связь, 1993

  3. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог: Пер. с англ. –

М.: Мир, 1990



nervnaya-sistema-referat.html
nervnaya-sistema-u-razlichnih-organizmov.html
nervnaya-tkan-nejrociti-gliociti-nervnie-volokna.html