Лекция №7. Функциональное и логическое программирование

7.1 Функциональное программирование на языке ЛИСП

НАЗНАЧЕНИЕ И ОБЩАЯ ХАРАКТЕРИСТИКА ЯЗЫКА

В программировании помимо процедурного подхода, представителями которого являются такие универсальные языки высокого уровня как Бейсик, Паскаль, Си, и логического подхода, представленного языком Пролог, существует еще одно направление - функциональное. Оно возникло в 1962 г. вместе с созданием Дж. Маккарти языка программирования Лисп (Lisp). Долгое время этот язык занимал особое место. Подавляющее большинство программ искусственного интеллекта составлено на языке Лисп. До сих пор он считается стандартным языком разработки систем искусственного интеллекта. Его популярность особенно велика в США. В нашей стране этот язык не получил широкого распространения (одна из причин - недостаток литературы о нем на русском языке), однако в настоящее время популярность этого языка быстро растет. Несмотря на то, что Лисп - один из самых старых используемых языков программирования, у него многое еще впереди.

Язык Лисп - один из первых языков обработки данных в символьной форме. Его название происходит от английских слов «list processing » - «обработка списков». В Лиспе и программа, и обрабатываемые ею данные представляются в одной и той же форме - в форме списка. Таким образом, программы могут обрабатывать и преобразовывать другие программы и даже самих себя.

Используемый в Лиспе, так называемый, функциональный подход к программированию основывается на той простой идее, что вся обработка информации и получение искомого результата могут быть представлены в виде вложенных и/или рекурсивных вызовов функций, выполняющих некоторые действия, так что значение одной функции используется как аргумент другой. Значение этой функции становится аргументом следующей и т.д. пока не будет получен конечный результат - решение задачи.

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

Имеется большое число систем программирования на Лиспе, реализованных для компьютеров различных типов. Как правило, это интерпретирующие системы, работающие в интерактивном (диалоговом) режиме. Соответствующие описания и команды вводятся с клавиатуры после приглашения ("_"), затем прочитывается результат.

ОСНОВНЫЕ ЭЛЕМЕНТЫ ПРОГРАММЫ НА ЛИСПЕ. СПИСКИ

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

Символ - это имя, состоящее из букв, цифр и специальных знаков, которое обозначает какой-нибудь предмет или действие из реального мира, а также число, функцию (программу) и другие объекты. Наряду с символами используются и числа (значения), которые могут быть целыми (например, 543), десятичными (например, 3.789) и в представлении с мантиссой и порядком (например, 1.0243Е-6).

Главной структурой в Лиспе является список.

Списком называется упорядоченная последовательность, элементами которой являются либо атомы, либо списки (подсписки). Списки заключаются в круглые списки, а их элементы разделяются пробелами. Например,

(ab(cd)e)

(В группе 18 студентов)

(((((первый) 2) третий) 4) 5).

Список, в котором нет ни одного элемента, называется пустым списком и обозначается "( )" или специальным символом NIL. Список - это структура данных, представляющая некоторую иерархическую связь (дерево) с помощью строго соответствующих друг другу открывающих и закрывающих скобок.

Имеется и альтернативный способ записи списков - с использованием, так называемой, точечной нотации. Точка при этом отделяет начальный элемент списка -его голову - от остальной части списка - хвоста: (голова, хвост) или

(а1 а2 ... aN) = (а1. (а2.... (aN.Nil)...)).

Здесь Nil - это предопределенная константа, означающая пустой список (и одновременно логическое значение «Ложь»).

Атомы и списки называются S-выражениями. Все вышесказанное можно обобщить в следующих формах Бэкуса - Наура

<S-выражение> :: = <атом> | <список>

<список> :: = (<внутренняя часть>)

<внутренняя часть> :: = NIL | <S-выражение> [{внутренняя часть}}

<атом> :: = цепочка алфавитно-цифровых символов без пробелов или специальных символов (,);.

Списки в Лиспе - основное средство представления знаний. Например, с помощью вложенных списков может быть представлена характеристика человека:

(сотрудник

(имя Петр)

(отчество Петрович )

(фамилия Иванов)

( образование ( среднее (с 1969 по 1979))

(высшее ( ВГУ г.Воронеж (с 1979 по 1982)

(МГУ г. Москва (с 1982 по 1984)) ( специальность

(техническая кибернетика)

(программирование )

(стаж (с 1984 по 1997)

)

ФУНКЦИИ

Функции в Лиспе аналогично математическим функциям ставят в соответствие элементам из одного множества - определения (аргументов) - единственный элемент из множества значений. В программах следует различать определение функций и вызов (применение) функции.

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

(f x)

(g x y) (сумма_квадратов 2 3).

Аналогично записываются и арифметические действия:

(+ х у)

(*x(+yz))

(+ (^ х х) (+ у у)).

Определение функций и их вычисление в Лиспе основано на лямбда-исчислении Черча. В 1-исчислении Черча функция записывается в виде

1(х1,х2,... ,xn) .fn

В Лиспе 1-выражение имеет вид (LAMBDA (xl, x2,..., xn).fn).

Символ LAMBDA означает, что мы имеем дело с определением функции. Символы xi являются формальными параметрами, они образуют список, называемый лямбда-списком; fn - это тело функции, которая может иметь произвольную форму, допускаемую интерпретатором Лиспа. Телом функции может быть, например, константа или композиция из вызовов функций. Функцию, вычисляющую сумму квадратов двух чисел, можно, например, определить так:

(lambda(xy)(+(*xx)(*yy))).

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

(лямбда-выражение а1 а2 ... an)

Здесь ai - фактические параметры, с которыми происходит вычисление.

Например

((lambda (х у) (+ (* х х) (* у у))) 3 4).

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

Определить новую функцию и дать ей имя для последующих вызовов можно с помощью функции DEFUN (define function):

(DEFUN имя лямбда-список тело).

DEFUN соединяет символ с лямбда-выражением, и символ начинает представлять (именовать) определенные этим лямбда-выражением вычисления. Значением этой формы является имя новой функции:

(defun sumsquare (х у) (+ (* х х) (* у у))) .

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

Вызов (применение) этой функции:

(sumsquare 34)

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

Определение функции задается списком, поэтому его можно модифицировать в ходе выполнения программы. Кроме того, некоторый символ может быть и именем функции и переменной.

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

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

CAR, CDR, CONS, ATOM, EQ, EQL, =

и другие, смысл которых отражен в табл. 7.1

Таблица 7.1

Базовые функции обработки S-выражений

Функция	Вызов	Действие	Пример использования
CAR	(CAR список)	Возвращает головною часть списка - его 1-й элемент	(CAR(1 234)) Результат:1
CDR	(CDR список)	Возвращает хвостовую часть списка- все. кроме 1-го элемента	(CDR(! 234)) Результат:(2 3 4)
CONS	(CONS S-выражение список)	Строит список из переданных в качестве аргументов головы и хвоста	(CONS I (2 3 4)) Результат: (1234)
ATOM	(ATOMS-выражение -)	Предикат; проверяет, является ли аргумент атомом, и возвращает либо t (истина), либо Nil или ("(ложь)	(ATOM A) : t (ATOM (1 2 3)): Nil
EQ	(EQ символ Символ)	Предикат: проверяет тождественность символов-аргументов, неприменим для чисел	(EQ A A): (EQ X (CAR (X Y Z))): t t
EQL	(EQL число число)	Предикат, проверяет тождественность чисел одного типа	(EQL 3.0 3.0): t
=	(= число число)	Предикат, проверяет тождественность чисел различных типов	(=30.3el):t
EQUAL	(EQUAL число или список число или список)	Аналогична EQL, но, кроме того, проверяет идентичность списков	(EQUAL(xyz)(xyz)):t
EQUALP	(EQUALP объект объект)	Проверка наиболее общего равенства
NULL	(NULL список)	Проверка, является ли аргумент пустым списком
NOT	(NOT логическая величина)	Логическое отрицание
NTH	(NTH n список)	Выделение n-го элемента списка	(NTH 2 (1 2 3)): 3 (индексы начинаются с 0)
FIRST		Предикаты, выделяющие
SECOND		Соответствующие элементы списка
LAST
LIST	(LIST apr арг2 ...)	Строит из аргументов список	(LIST a b (с)): (a b c)

Отметим, что в программах на Лиспе надо тщательно отличать значения от их обозначений.

В Лиспе константы обозначают самих себя. Выражения типа (* 2 2) сразу вычисляются. Чтобы избежать нежелательного вычисления выражения используется функция QUOTE или знак апострофа (') перед выражением:

(* 2 2) : 4

' (* 2 2) :' (* 2 2) - список

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

(SET 'операции' (+ - * /))

Знак ' используется для подавления вычисления аргументов функции SET. Функция SETQ не вычисляет значения 1-го аргумента (а 2-го вычисляет).

На значение символа можно сослаться, указав его без апострофа (').

Для занесения значений в ячейку памяти, связанной с символом, можно пользоваться обобщенной функцией присваивания SETF, размещающей значения в соответствующей ячейке памяти:

(SETF ячейка_памяти значение).

Переменная «ячейка_памяти» без апострофа указывает на ячейку памяти. Присвоение, выполняемое функциям» SET, SETQ и SETF, является побочным эффектом , этих функций, помимо того, данные функции возвращают присваиваемые значения.

ФОРМЫ. УПРАВЛЯЮЩИЕ КОНСТРУКЦИИ В ЛИСП-ПРОГРАММЕ

Программа состоит не только из функций, но и из форм. Простейшими формами являются константы, переменные, лямбда-вызовы, вызовы функций.

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

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

работа с контекстом

* QUOTE или блокировка вычисления,

* вызов функции и лямбда-вызов,

* предложения LET и LET*;

последовательное исполнение

* предложения PROG1, PROG2 и PROGN;

разветвление исполнения

* условные предложения COND, IF, WHEN, UNLESS,

* выбирающее предложение CASE;

итерации

* циклические предложения DO, DO*, LOOP, DOTIMES, DOUNTIL;

передачи управления

* предложения PROG, GO и RETURN;

динамическое управление вычислением

* THROW, CATCH, а также BLOCK.

Эти управляющие формы (кроме QUOTE и лямбда-вызова, а также вызовов функций), в основном, используются в теле лямбда-выражений, определяющих функции.

Предложение LET используется для создания связи переменных внутри формы:

(LET ((пep1 знач1) (пер2 знач2)...) форма1 форма2 ...).

При вычислении этого выражения статические переменные пep1, пер2, ... связываются (одновременно) с соответствующими значениями знач1, знач2, ..., а затем вычисляются значения форм форма1, форма2, ... Значение последней формы возвращается как общий результат. Форма LET* отличается от LET лишь тем, что связывание переменных и вычисление форм происходит не одновременно, а последовательно, вначале 1-е, потом 2-е и т.д.

Например:

(let*((x2)(y(*3x)))

(list x у)

Результат: (2 6).

Предложения PROG1, PROG2 и PROGN позволяют организовывать последовательные вычисления из нескольких вычисляемых форм:

(PROG1 форма1 форма2 ... формаn)

(PROG2 форма1 форма2 .. формаn)

(PROGN форма1 форма2 . формаn).

Различие этих форм лишь в возвращаемых ими в качестве общего значения результатах. Форма PROG1 возвращает значение формы1, PROG2-формы2, PROGN -последней формы n.

Например:

(progn (setq x 2) (setq у (* 3 х)))

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

Предложение COND является основным средством разветвления обработки. Структура условного предложения такова:

(COND (р1 а1) (р2 а2)... (pn an)).

pi - это предикаты (выражения-условия, которые могут быть либо истинными (Т), либо ложными (NIL)). Их значения вычисляются слева направо, пока не будет получено значение «истина» (Т), затем вычисляется и возвращается в качестве результата результирующее выражение ai. соответствующее 1-му истинному предикату pi. Если истинного предиката нет. то значение COND - NIL. Форма ai для соответствующего предиката может отсутствовать (тогда возвращается значение этого предиката в случае его истинности), или, наоборот, может быть задана последовательность форм для предиката pi - тогда эти формы вычисляются последовательно и возвращается значение последней.

В следующем примере с помощью предложения COND определена функция, устанавливающая тип выражения:

(defun тип (1)

(cond ((null 1) 'пусто)

((atom 1) 'атом)

(t 'список)))

Результат: ТИП.

Примеры применения этой функции:

(тип ' (a b с))

Результат: СПИСОК.

(тип (atom ' (а т о м)))

Результат: ПУСТО.

Для организации ветвления можно использовать и формулы IF, WHEN, UNLESS:

(IF условие то-форма иначе-форма),

что эквивалентно

(COND (условие то-форма) (Т иначе форма));

(WHEN условие форма1 форма2 ...),

что эквивалентно

(UNLESS (NOT условие) форма! форма2 ...)

или

(COND (условие форма1 форма2 ...)).

Можно применять и выбирающее предложение CASE:

(CASE ключ (список ключей1 форма11 форма12 ...)

(список ключей2 форма21 форма22 . . .)

В этой форме сначала вычисляется значение ключевой формы «ключ», затем происходит сравнение с элементами списков ключей и, если найдено значение ключевой формы, вычисляется последовательность соответствующих форм, значение последней из которых возвращается как значение всего выражения CASE.

Предложения PROG, GO и RETURN аналогичны конструкциям неструктурных языков программирования (типа FORTRAN, Бейсик); пользоваться ими не рекомендуется.

РЕКУРСИЯ И ЦИКЛ В ПРОГРАММАХ НА ЛИСПЕ

В «чистом» функциональном программировании организация повторяющихся вычислений должна происходить лишь с помощью условных предложений и определения рекурсивных, вызывающих самих себя, функций. Рассмотрим в качестве примера функцию, просто определяемую через рекурсию, - факториал n!=1*2 * 3 *...* (n-1) * n = (n-1)! т n (0! = 1 по определению):

(defun ! (n) (if(= п 0) 1 (* п (! (. п 1))))) .

Имя функции - "!", ее аргументом является переменная n. Лямбда-выражение, определяющее функцию, представляет собой условную if-форму, которая в случае n=0 возвращает 1, а в противном случае вычисляет произведение n и результата вызова этой же функции ! для аргумента n-1.

Пример вызова этой функции:

(!5)

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

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

(DO ((nepi знач! шаг1) (пер2 знач2 шаг 2) ...)

(условие-окончания форма11 форма12 ...)

форма21 форма22 ...)

Вычисление предложения DO начинается с присваивания переменным пep1, пер2, ... начальных значений знач1, знач2, . . . соответственно; потом вычисляется условие окончания и, если оно истинно, последовательно вычисляются формы форма1i, и значение последней возвращается как результат DO-предложения. В противном случае вычисляются формы форма2i из тела предложения DO, затем значения переменных пep1, пер2, . . . изменяются на величину шага шаг1, шаг2, ... и все повторяется.

Для примера с помощью предложения DO определим функцию expt, вычисляющую n-ю степень числа х (n - целое положительное):

(defun expt (х n)

(do ((результат 1)) ; начальное значение

((= n 0 ) результат ) ; условие окончания

(setq результат (* результат х))

(setqn(^nl))))

Результат задания функции: EXPT.

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

(expt 2 3)

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

Итеративные (циклические) и рекурсивные программы теоретически одинаковы по своим вычислительным возможностям, однако свойства итеративных и рекурсивных вариантов программ могут существенно различаться. Рекурсивные программы более короткие и содержательные. Особенно полезно использовать рекурсию в тех случаях, когда решаемая задача и обрабатываемые данные по своей сути рекурсивны, например, при обработке списков, так как списки могут рекурсивно содержать подсписки, при работе с другими динамическими структурами, которые заранее не полностью известны. Рекурсивные процедуры играют важнейшую роль почти во всех программах, связанных с искусственным интеллектом.

ВВОД-ВЫВОД ДАННЫХ

До сих пор рассматривался ввод и вывод данных в лисповских программах через параметры функций и свободные переменные. Для организации диалога человека с программой в Лиспе существуют специальные функции READ и PRINT.

Для вывода результатов можно использовать функцию PRINT. Это функция с одним аргументом, которая сначала вычисляет значение аргумента, а затем выводит это значение.

Например:

(PRINT (* 2 2))

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

Перед выводом происходит переход на новую строку.

Функция READ читает и возвращает выражение: (READ). Как только интерпретатор встречает такое предложение, вычисления приостанавливаются до тех пор, пока не будет введен какой-либо символ или целиком выражение. Аргументов у функции READ нет, ее использование построено на побочном эффекте, состоящем именно во вводе выражения. Прочитанное выражение можно сохранить для следующего использования и обработки, например, так:

(setq input (read));

прочитанное READ выражение присваивается переменной input.

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

Для форматного вывода (в соответствии с некоторым образом) существует функция FORMAT, обладающая гибкими возможностями, описанными в руководствах по языку Лисп.

Помимо стандартных устройств ввода-вывода, может осуществляться обработка файлов на магнитных носителях, загружаться из файлов определения функций и т.д.

ПРИМЕР ПРОГРАММИРОВАНИЯ НА ЛИСПЕ

Рассмотрим в качестве примера программирования на Лиспе менее элементарную классическую задачу, носящую название игры в «ханойские башни».

Игра состоит в следующем. Используются три вертикальных стержня А, В, С и набор N дисков разного диаметра с отверстием посередине (так что их можно надевать на стержни). В начальном положении все диски надеты на стержень А по порядку убывания диаметров: внизу самый большой, над ним - поменьше и т.д., а наверху - самый маленький. Целью является перенос всех дисков со стержня А на стержень В по следующим правилам:

1) за один раз можно перенести только один диск;

2) больший по размеру диск нельзя положить на меньший;

3) третий стержень С можно использовать как вспомогательный. Алгоритм решения задачи можно представить в виде трех следующих рекурсивных подзадач:

1) перенести со стержня А N-1 дисков на вспомогательный стержень С;

перенести нижний диск со стержня А на стержень В;

перенести со стержня С N-1 дисков на стержень В.

Программа состоит из трех последовательно определяемых функций «ханойские-башни», «перенос», «выведи» и имеет вид:

Программа 130

(defun ханойские-башни (высота)

(рrоgn (перенос "а "Ь "с высота) "готово))

ХАНОЙСКИЕ-БАШНИ

(defun перенос (из в вспомогательный n)

(cond

((= п 1) ; ветвь 2

(выведи из в) (t (перенос из ; ветвь1 вспомогательный

в

(- n 1))

(выведи из в)

(перенос вспомогательный ; ветвь 3

в

из

(- п 1)))))

ПЕРЕНОС

(defun выведи (из в)

(format t "~S -> ~S~%"из в))

ВЫВЕДИ

Вызов функции «ханойские башни» дает такое решение:

(ханойские-башни 3)

А->В

А->С

В->C

А->В

С->А

С->В

А->В

ГОТОВО

Можно убедиться, что определенная нами функция дает правильное решение для произвольного числа дисков, однако время решения задачи с увеличением числа дисков быстро возрастает.

СВОЙСТВА СИМВОЛОВ

В Лиспе могут быть определены, так называемые, свойства символов. Список свойств имеет вид:

(имя_свойства1 значение1 имя_свойства2 значение2 . .. имя_свойстваN значениеN).

Присваивание нового свойства или изменение значения существующего осуществляется с помощью функции PUTPROP (или просто PUT):

(PUTPROP символ свойство значение).

Выяснить значение свойства, связанного с символом, можно с помощью функции GET:

(GET символ свойство).

С использованием этой функции можно также присваивать свойства символам:

(SETF (GET символ свойство) значение).

Свойства символов глобальны Эта конструкция языка Лисп полезна во многих типичных случаях представления данных, в том числе семантических сетей, фреймов и объектов объектно-ориентированного программирования.

7.2 Логическое программирование на языке ПРОЛОГ

Язык Пролог является представителем семейства языков логического программирования и в сравнении с традиционными языками программирования, предназначенными для записи алгоритмов, такими как Бейсик, Фортран, Паскаль, Си, обладает существенными особенностями:

* программа на Прологе не является алгоритмом, а представляет собой запись условия задачи на языке формальной логики (т.е. это дескриптивный, описательный язык программирования);

* язык Пролог предназначен не для решения вычислительных или графических задач, а для решения логических задач, для моделирования процесса логического умозаключения человека; вычисления же и графические построения выполняются в Прологе как побочный продукт логического вывода;

* Пролог требует особого стиля мышления программиста, что затрудняет изучение его теми, кто уже привык к процедурному программированию, поэтому, так называемые, практические программисты не стремятся переходить на этот язык, что мешает росту популярности Пролога; однако во многих странах (Японии, Англии, Франции, Германии, Израиле и т.д.) расширяется практика применения Пролога в образовании как первого изучаемого языка программирования; переход к процедурным языкам типа Паскаля в этом случае трудностей не вызывает.

Все это позволяет отнести Пролог в существующем делении языков программирования на языки низкого и высокого уровня к языкам сверхвысокого уровня. В японском проекте создания в 90-х годах XX века компьютеров 5-го поколения (обладающих искусственным интеллектом) Пролог положен в основу аппаратной организации и разработки программного обеспечения. Нынешний Пролог, безусловно, не является окончательным вариантом языка программирования ЭВМ 5-го поколения и в ближайшие годы получит существенное развитие. По-видимому, он сыграет роль Бейсика дескриптивного программирования: его значение и возможности в популяризации и распространении идей логического программирования чрезвычайно велики.

Изучению языка Пролог очень способствует предшествующее изучение математической логики, понятийной системой которой он пользуется.

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

1) объявление фактов об объектах и отношениях между ними;

2) определение правил взаимосвязи объектов и отношений между ними;

3) формулировка вопроса об объектах и отношениях между ними.

Имена - это последовательности букв и цифр, начинающиеся с буквы (строчной !). Системы программирования на Прологе для компьютеров допускают использование лишь латинских строчных и прописных букв: а .. z, A .. Z. Использование русских строчных и прописных букв: а .. я, А .. Я не допускается. При практической работе с интерпретатором рекомендуется, чтобы смысл имен оставался понятным, использовать в качестве имен запись русских слов латинскими буквами. В данном параграфе мы будем записывать все имена русскими буквами, чтобы сделать смысл программ наиболее понятным. При запуске этих программ в «англо-язычных» системах программирования нужно заменять русские буквы в именах на латинские.

Типы данных включают переменные, атомарные значения и структуры (рис. 3.15).

Рис.3.1 5. Классификация типов данных Пролога

Примеры специальных атомов:

: - ( обозначающая импликацию),

? (вопрос, обозначающий отрицание),

! (предикат отсечения, рассматривается далее).

Переменные обозначаются последовательностью буквой и цифр, начинающейся с заглавной буквы. Особый вид переменной - анонимная переменная _ , используемая в качестве аргумента предиката, когда конкретное значение переменной несущественно.

Структура - это конструкция, состоящая из имени структуры и заключенного в скобки списка ее аргументов, разделенных запятыми. Элементами структур могут быть числа, атомы, переменные, другие структуры и списки. Примеры структур: str(A,B,C), носит(юрий,пиджак).

Списки представляют собой объединение элементов произвольных видов, разделенных запятыми и заключенных в квадратные скобки. Списки отличаются от структур тем, что количество элементов может меняться при выполнении программы. Примеры списков: [1,3,5,7], [красный,желтый,зеленый].

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

* константа сопоставляется только с равной ей константой;

* идентичные структуры сопоставляются друг с другом;

* переменная сопоставляется с константой или с ранее связанной переменной (и становится связанной с соответствующим значением);

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

Примеры: 5 сопоставляется с 5, «имеет» сопоставляется с «имеет», «сергей» не сопоставляется с «юрий», «имеет(сергей,машина)» не сопоставляется с «имеет(сергей, телевизор)», «имеет(сергей,машина)» сопоставляется с «имеет(Х,машина)», в этом случае переменная Х получает в качестве значения атом «сергей».

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

Пример 1. Факты, описывающие телефонные номера:

телефон(иванов,т561532).

телефон(петров,т642645).

телефон(сидоров,т139833).

Это означает: телефон Иванова - 56-15-32 и т.п. Заметим, что перед цифрами номера идет буква ''т". Она делает номер телефона литерной константой, так как числа 561532,642645, 139833 слишком велики, чтобы быть числовыми константами.

Пример 2, Факты, описывающие студентов:

нравится(сергей,рэп).

нравится(юрий,джаз).

носит(сергей,блейзер).

носит(юрий,пиджак).

Это означает: «Сергею нравится рэп», «Юрию нравится джаз» и т.п.

Правила - это хорновские фразы с заголовком и одной или несколькими подцелями-предикатами. Правила имеют форму

<голова правила> : - <список подцелей>

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

крутойпарень(Х):- нравится(Х,рэп),носит(Х,блейзер).

Это означает «любой Х - крутой парень, если Х нравится рэп и Х носит блейзер». Еще примеры правил:

ест(Х,Y): - пища(Y), любит(Х,Y). («Каждый Х ест любой Y, если Y - пища,

и Х любит Y»)

владелец(А,В) : - купил(А,В). («Любой А есть владелец каждого В, если А купил В»)

В Прологе все предложения программы - факты, правила, вопрос - заканчиваются точкой.

Отметим, что в Прологе вместо оператора присваивания имеется более общий и мощный механизм задания значений переменных. Переменные в Прологе получают свои значения в результате сопоставления с константами в фактах и правилах. До тех пор. пока переменная не получила какого-либо значения, она называется «свободной». Когда переменная примет значение, она становится «связанной». Однако, она остается связанной только в течение времени, необходимого для получения одного ответа на запрос, после этого Пролог «развязывает» ее, возвращается и ищет альтернативные решения. Это очень важный момент: нельзя хранить информацию, задавая значения переменных. Переменные служат частью процесса сопоставления, а не «хранилищем» информации. Область действия переменной -ровно одно предложение (правило или запрос программы).

Вопрос - отправная точка логического вывода, происходящего при выполнении программы. На любой вопрос компьютер будет пытаться дать ответ «Да» или «Нет» в зависимости от того. согласуется или нет утверждение, стоящее в вопросе, с фактами и правилами базы знаний. Вопрос, не содержащий переменных, является общим: «имеет ли место факт... ?». Так, например, к базе знаний примера 1 можно поставить вопрос

?-телефон(иванов,т123456).

и ответ будет «Нет», так как константа т123456 не согласуется ни с одним фактом.

Если к базе знаний (пример 3)

нравится(сергей ,рэп).

нравится(юрий,джаз).

носит(сергей,блейзер).

носит(юрий,пиджак).

крутойпарень(Х) : - нравится(Х,рэп),носит(Х,блейзер).

задать вопрос

?-крутойпарень(юрий).

то будет получен ответ «Нет». В самом деле, в результате резолюции утверждение в этом вопросе согласно правилу заменится конъюнкцией утверждений

нравнтся(юрий,рэп), носит(юрий,блейзер).

(переменная Х в правиле получила значение «юрий»). Эти утверждения не согласуются с остальными фактами базы знаний. Для вопроса

? - крутойпарень(сергей).

будет получен ответ «Да», так как в этом случае противоречий при согласовании вопроса и базы знаний не возникает.

Вопрос, в котором имеются переменные, является частным: «для каких значений переменных факт ... имеет место ?». В процессе сопоставлений при выполнении программы переменные получат значения тех констант (конкретизируются), для которых сопоставление запроса, в целом, успешно, и будут выведены на экран. Так, в ответ на вопрос

? - телефон(иванов,Х).

к базе знаний примера 1 на экране появится сообщение Х=т561532 и будет дан ответ «Да».

Если к базе знаний примера 3 задать вопрос в форме

?- крутойпарень(А).

то свободная переменная А в вопросе сопоставляется со свободной переменной Х в правиле и совмещается с ней, т.е. становится одним и тем же. В результате резолюции согласно правилу произойдет замена

крутойпарень(А)

на

нравится(А,рэп), носит(А,блейзер),

а затем предикат «нравнтся(А.рэп)» успешно согласуется с фактом «нравится(сергей,рэп)>>, и при этом переменная А конкретизируется значением «Сергей»; от вопроса теперь остается «носит(сергей,блейзер)», а в базе знаний имеется соответствующий факт. Ответ: «Да» и на экране появится значение присутствовавшей в вопросе переменной А:

А=сергей.

Отметим, что машина «не понимает» используемых в программе имен: «нравится», «носит», «сергей» и т.д. Мы могли бы вместо них использовать любые другие обозначения. Для интерпретатора Пролога существенны только совпадения и различия имен, а также связи между предикатами, устанавливаемые с помощью конъюнкций и импликаций. Осмысленные имена мы будем использовать только для того, чтобы облегчить чтение и понимание программ самим себе. Однако, в Прологе существуют предопределенные имена (встроенные предикаты), которые позволяют выполнить арифметические операции, сравнения, графические построения, ввод-вывод и другие полезные операции как побочный продукт выполнения программы. Встроенные предикаты Arity-Prolog описаны в справке по системе программирования, вызываемой нажатием клавиши F1.

Аналогичный набор встроенных предикатов имеется в других версиях языка Пролог.

АЛГОРИТМ ВЫПОЛНЕНИЯ ПРОГРАММ НА ПРОЛОГЕ

Факты и правила программы на Прологе являются описанием отношений и связей между объектами некоторой предметной области, т.е. записью условия некой логической задачи, которую предстоит решить. Описанные отношения и связи рассматриваются статически. Такой подход к программе называется декларативным. Порядок следования фактов, правил и подцелей в правилах не влияет на декларативный смысл программы.

Вместе с тем, программу можно рассматривать с точки зрения последовательности сопоставлений, конкретизации переменных и резолютивных выводов, происходящих при ее выполнении. Такой подход называется процедурным. Процедурный смысл программы обязательно должен учитываться при программировании на Прологе. Так, факт можно рассматривать как полностью определенную процедуру, для выполнения которой больше ничего не нужно. Правило

А:-В1,В2,...,Вn.

можно рассматривать как определение процедуры А, утверждающее, что для ее выполнения надо определить Bl, B2, ... , Вn. Процедуры Bl, B2, ... , Вn должны выполняться в определенном порядке - слева направо. Если выполнение очередной процедуры завершается успешно, то происходит переход к следующей процедуре. Если же по какой-либо причине очередная процедура выполняется неуспешно, то происходит переход к следующему варианту описания этой процедуры, и порядок поиска такого варианта в Прологе задан - сверху вниз. Поиск подходящих для согласования фактов и правил в базе знаний происходит последовательно сверху-вниз, и если подходящих фактов не найдено - ответ отрицательный. Эта стратегия согласования называется «сверху-вниз» и «замкнутый мир».

Рассмотрим процесс выполнения программы более подробно на примере.

Программа 112

а : - b, с, d.

b : - е, f.

с. d. е. f.

? - а.

Выполнение программы начинается с применения метода резолюций к целевому и одному из предложений программы для получения их резольвенты. Подходящее предложение программы подбирается перебором сверху-вниз так, чтобы сопоставление его заголовка с целевым предложением было успешным. В результате резолюции получается новое целевое предложение и метод резолюции применяется к нему и к другому предложению программы. Процесс продолжается до тех пор, пока не будут согласованы с фактами все возникшие при резолюции подцели, табл. 3.6.

Таблица 3.6

К процессу выполнения программы на Прологе

Номер шага резолюции	Целевое предложение	Исходное предложение	Резольвента
1	?-а.	a:-b,c,d.	?-b,c,d.
2	?-b,c,d.	b:-c,f.	?-e,f,c,d.
3		?-е,f,с,d	e. ?-f,c,d.
4		?-f,c,d.	f. ?-c.d.
5		?-c,d.	c. ?-d.
6		?-d.	d. Пустая

При выполнении логического вывода, если необходимо, происходит конкретизация переменных. Рассмотрим пример.

Программа 113

любит(юрий,музыку).

любит(сергей,спорт).

любит(А,книги):-читатель(А),любопытный(А).

любит(сергей,книги).

любит(сергей,кино).

читатель(юрий).

любопытный(юрий).

?- любит(X,музыку), любит(X,книги).

Двойной запрос в этой программе может быть представлен целевым деревом:

Вначале, просматривая программу сверху вниз. Пролог находит первое предложение, соответствующее первой подцели запроса:

Переменная Х конкретизируется значением «юрий». Начинается согласование 2-й подцели запроса с условием Х=юрий. 1-е и 2-е предложения программы не соответствуют подцели. В 3-ем предложении:

любит(А,книги):-читатель(А), любопытный(А).

аргумент А заголовка есть переменная, поэтому она может соответствовать X, т.е. получает значение А=юрин; вторые аргументы совпадают. Теперь тело правила образует новое множество целей для согласования. Получаем целевое дерево:

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



Рассмотрим еще один пример.

Программа 114

любит(оля,чтение).

любит(света,бадминтон).

любит(для,бадминтон).

любит(лена,плавание).

любит(лена,чтение).

?- любит(X,чтение), любит(X,плавание).

Запрос означает: есть ли люди, которым нравится и чтение, и плавание? Сначала Пролог ищет факт, сопоставимый с первой частью вопроса: любит(Х, чтение). Подходит первый же факт программы

любит(оля,чтение).

и переменная Х связывается значением «оля». В то же время Пролог фиксирует в списке фактов указатель, показывающий состояние процедуры поиска. Далее Пролог пытается согласовать вторую часть запроса при условии Х = оля, т.е. ищет с самого начала программы факт «любит(оля, плавание)». Такого факта в программе нет, и поиск заканчивается неуспешно. Тогда Пролог возвращается к первои части запроса: любнт(Х,чтение) , «развязывает» переменную Х и продолжает поиск подходящих фактов, начиная с ранее установленного в списке фактов указателя Подходит факт «любит(лена,чтение)», переменная Х конкретизируется значением «лена», и далее вторая часть вопроса успешно согласуется с фактом «любит(лена, плавание)». Пролог выполнил в данном примере поиск с возвратом.

Графически процесс выполнения программы представляется в виде обхода бинарного дерева - дерева вывода, типа изображенного на рис.3.16. Вершины дерева обозначают вопросы, а ребра показывают возможные пути вывода, причем для каждого ребра характерны свои правила и унифицирующая подстановка значений переменных.

Рис.3.16. Дерево вывода программы на Прологе

Обход дерева начинается с движения от вершины (запроса) по самой левой ветви вниз до конца (abed), при этом запоминаются все точки ветвления (точки возврата). При достижении конца ветви решение будет либо найдено, либо нет. В обоих случаях Пролог продолжает дальнейший поиск решений. Выполняется возврат в последнюю точку ветвления с. При этом конкретные значения, присвоенные переменным при движении вниз на сегменте c-d. отменяются, и движение вниз продолжается по расположенной справа ветви с-е до конца дерева вниз. Затем произойдет возврат в предыдущую точку ветвления b и движение продолжится по ветви bfg, и так до тех пор, пока все дерево вывода не будет пройдено.

Лекция №8. Технологии разработки программного обеспечения

8.1 Классификация методов проектирования программных продуктов

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

Переход к графической среде работы конечного пользователя типа Windows или Macintosh потребует создания пользовательского интерфейса с элементами управления в виде пиктограмм, кнопок, выпадающих меню, обязательного применения манипулятора мышь и др. Отсутствие в программном продукте уже ставших стандартом подобных элементов свидетельствует о том, что в будущем потребуются значительные затраты на модификацию этого продукта, иначе будет падать его конкурентоспособность и привлекательность для конечного пользователя.

Методы проектирования алгоритмов и программ очень разнообразны, их можно классифицировать по различным признакам, важнейшими из которых являются:

степень автоматизации проектных работ;

принятая методология процесса разработки.

По степени автоматизации проектирования алгоритмов и программ можно выделить:

методы традиционного (неавтоматизированного) проектирования;

методы автоматизированного проектирования (CASE-технология и ее элементы).

Неавтоматизированное проектирование алгоритмов и программ преимущественно используется при разработке небольших по трудоемкости и структурной сложности программных продуктов, не требующих участия большого числа разработчиков. Трудоемкость разрабатываемых программных продуктов, как правило, небольшая, а сами программные продукты имеют преимущественно прикладной характер.

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

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

Автоматизация проектирования может охватывать все или отдельные этапы жизненного цикла программного продукта, при этом работы этапов могут быть изолированы друг от друга либо составлять единый комплекс, выполняемый последовательно во времени. Как правило, автоматизированный подход требует технического и программного "перевооружения" труда самих разработчиков (мощных компьютеров, дорогостоящего программного инструментария, а также повышения квалификации разработчиков и т.п.).

Автоматизированное проектирование алгоритмов и программ под силу лишь крупным фирмам, специализирующимся на разработке определенного класса программных продуктов, занимающих устойчивое положение на рынке программных средств.

Проектирование алгоритмов и программ может основываться на различных подходах, среди которых наиболее распространены:

* структурное проектирование программных продуктов;

* информационное моделирование предметной области и связанных с ней приложений;

* объектно-ориентированное проектирование программных продуктов.

В основе структурного проектирования лежит последовательная декомпозиция, целенаправленное структурирование на отдельные составляющие. Начало развития структурного проектирования алгоритмов и программ падает на 60-е гг. Методы структурного проектирования представляют собой комплекс технических и организационных принципов системного проектирования.

Типичными методами структурного проектирования являются:

нисходящее проектирование, кодирование и тестирование программ;

модульное программирование;

структурное проектирование (программирование) и др.

В зависимости от объекта структурирования различают:

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

методы структурирования данных.

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

Для методов структурирования данных осуществляется анализ, структурирование и создание моделей данных, применительно к которым устанавливается необходимый состав функций и процедур обработки. Программные продукты тесно связаны со структурой обрабатываемых данных, изменение которой отражается на логике обработки (алгоритмах) и обязательно требует перепроектирования программного продукта.

Структурный подход использует:

диаграммы потоков данных (информационно-технологические схемы) -- показывают процессы и информационные потоки между ними с учетом "событий", инициирующих процессы обработки;

интегрированную структуру данных предметной области (инфологическая модель, ER-диаграммы);

диаграммы декомпозиции -- структура и декомпозиция целей, функций управления, приложений;

структурные схемы -- архитектура программного продукта в виде иерархии взаимосвязанных программных модулей с идентификацией связей между ними, детальная логика обработки данных программных модулей (блок-схемы).

Для полного представления о программном продукте необходима также текстовая информация описательного характера.

Еще большую значимость информационные модели и структуры данных имеют для информационного моделирования предметной области, в основе которого положение об определяющей роли данных при проектировании алгоритмов и программ. Подход появился в условиях развития программных средств организации хранения и обработки данных -- СУБД.

Один из основоположников информационной инженерии -- Дж. Мартин -- выделяет следующие составляющие данного подхода:

информационный анализ предметных .областей (бизнес-областей),

информационное моделирование -- построение комплекса взаимосвязанных моделей данных;

системное проектирование функций обработки данных;

детальное конструирование процедур обработки данных.

Первоначально строятся информационные модели различных уровней представления:

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

даталогические модели, ориентированные на среду хранения и обработки данных.

Даталогические модели имеют логический и физический уровни представления. Физический уровень соответствует организации хранения данных в памяти компьютера. Логический уровень данных применительно к СУБД реализован в виде:

концептуальной модели базы данных -- интегрированные структуры данных под управлением СУБД;

внешних моделей данных -- подмножество структур данных для реализации приложений.

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

Выбор средств реализации базы данных определяет вид даталогических моделей и, следовательно, алгоритмы преобразования данных. В большинстве случаев используется реляционное представление данных базы данных и соответствующие реляционные языки для программирования (манипулирования) обработки данных СУБД и реализации алгоритмов обработки (см. гл. 19). Данный подход использован во многих CASE-технологиях.

Объектно-ориентированный подход к проектированию программных продуктов основан на:

* выделении классов объектов;

* установлении характерных свойств объектов и методов их обработки;

* создании иерархии классов, наследовании свойств объектов и методов их обработки.

Каждый объект объединяет как данные, так и программу обработки этих данных и относится к определенному классу. С помощью класса один и тот же программный код можно использовать для относящихся к нему различных объектов. Объектный подход при разработке алгоритмов и программ предполагает:

* объектно-ориентированный анализ предметной области;

* объектно-ориентированное проектирование.

Объектно-ориентированный анализ -- анализ предметной области и выделение объектов, определение свойств и методов обработки объектов, установление их взаимосвязей.

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

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

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

Объектно-ориентированная технология разработки программных продуктов объединяет данные и процессы в логические сущности -- объекты, которые имеют способность наследовать характеристики (методы и данные) одного или более объектов, обеспечивая тем самым повторное использование программного кода. Это приводит к значительному уменьшению затрат на создание программных продуктов, повышает эффективность жизненного цикла программных продуктов (сокращается длительность фазы разработки).При выполнении программы объекту посылается сообщение, которое инициирует обработку данных объекта.

8.2 Этапы создания программных продуктов

При традиционной неавтоматизированной разработке программ независимо от принятого метода проектирования и используемого инструментария выполняют следующие работы.

1. Составление технического задания на программирование

Данная работа соответствует этапу анализа и спецификации программ жизненного цикла программных продуктов. При составлении технического задания требуется:

определить платформу разрабатываемой программы -- тип операционной системы (например, для IBM PC-совместимых машин делается выбор операционной среды: MS DOS, Windows, Windows NT либо Unix, OS/2);

оценить необходимость сетевого варианта работы программы (определяется программное обеспечение (ПО) вычислительной сети -- Windows NT, допустимая номенклатура программного обеспечения сетевой обработки);

определить необходимость разработки программы, которую можно переносить на различные платформы;

обосновать целесообразность работы с базами данных под управлением СУБД.

На этом же этапе выбирают методы решения задачи; разрабатывают обобщенный алгоритм решения комплекса задач, функциональную структуру алгоритма или состав объектов, определяют требования к комплексу технических средств системы обработки информации, интерфейсу конечного пользователя.