ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6829
Скачиваний: 51
361
(тип ' (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, Бейсик); пользоваться ими не рекомендуется.
8.5. РЕКУРСИЯ И ЦИКЛ В ПРОГРАММАХ НА ЛИСПЕ
В «чистом» функциональном программировании организация повторяющихся вычислений
должна происходить лишь с помощью условных предложений и определения рекурсивных, вызы-
вающих самих себя, функций. Рассмотрим в качестве примера функцию, просто определяемую
через рекурсию, - факториал 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.
В случае повторяющихся вычислений в Лиспе могут быть использованы не только рекур-
сивные функции, но и известные по процедурным языкам циклы. Самым общим циклическим
362
предложением в Лиспе является 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.
Итеративные (циклические) и рекурсивные программы теоретически одинаковы по своим
вычислительным возможностям, однако свойства итеративных и рекурсивных вариантов про-
грамм могут
существенно различаться. Рекурсивные программы более короткие и содержатель-
ные. Особенно полезно использовать рекурсию в тех случаях, когда решаемая задача и обраба-
тываемые данные по своей сути рекурсивны, например, при обработке списков, так как списки
могут рекурсивно содержать подсписки, при работе с другими динамическими структурами, ко-
торые заранее не полностью известны. Рекурсивные процедуры играют важнейшую роль почти
во всех программах, связанных с искусственным интеллектом.
8.6. ВВОД-ВЫВОД ДАННЫХ
До сих пор рассматривался ввод и вывод данных в лисповских программах через парамет-
ры функций и свободные переменные. Для организации диалога человека с программой в Лиспе
существуют специальные функции READ и PRINT.
Для вывода результатов можно использовать функцию PRINT. Это функция с одним аргу-
ментом, которая сначала вычисляет значение аргумента, а затем выводит это значение.
Например:
(PRINT (* 2 2))
Результат: 4.
Перед выводом происходит переход на новую строку.
Функция READ читает и возвращает выражение: (READ). Как только интерпретатор встре-
чает такое предложение, вычисления приостанавливаются до тех пор, пока не будет введен какой-
либо символ или целиком выражение. Аргументов у функции READ нет, ее использование по-
строено на побочном эффекте, состоящем именно во вводе выражения. Прочитанное выражение
можно сохранить для следующего использования и обработки, например, так:
(setq input (read));
363
прочитанное READ выражение присваивается переменной input.
Лисповские операторы ввода-вывода очень гибки, их можно использовать в качестве аргу-
ментов других функций. Для более эстетичного оформления вывода можно использовать функции
PRINC, печатающую строку без окаймляющих кавычек и со специальными символами, а также
TERPRI, переводящую строку.
Для форматного вывода (в соответствии с некоторым образом) существует функция FOR-
MAT, обладающая гибкими возможностями, описанными в руководствах по языку Лисп.
Помимо стандартных устройств ввода-вывода, может осуществляться обработка файлов на
магнитных носителях, загружаться из файлов определения функций и т.д.
8.7. ПРИМЕР ПРОГРАММИРОВАНИЯ НА ЛИСПЕ
Рассмотрим в качестве примера программирования на Лиспе менее элементарную класси-
ческую задачу, носящую название игры в «ханойские башни».
Игра состоит в следующем. Используются три вертикальных стержня А, В, С и набор N
дисков разного диаметра с отверстием посередине (так что их можно надевать на стержни). В на-
чальном положении все диски надеты на стержень А по порядку убывания диаметров: внизу са-
мый большой, над ним - поменьше и т.д., а наверху - самый маленький. Целью является перенос
всех дисков со стержня А на стержень В по следующим правилам:
1) за один раз можно перенести только один диск;
2) больший по размеру диск нельзя положить на меньший;
3) третий стержень С можно использовать как вспомогательный. Алгоритм решения задачи
можно представить в виде трех следующих рекурсивных подзадач:
1) перенести со стержня А N-1 дисков на вспомогательный стержень С;
5)
перенести нижний диск со стержня А на стержень В;
6)
перенести со стержня С N-1 дисков на стержень В.
Программа состоит из трех последовательно определяемых функций «ханойские-башни»,
«перенос», «выведи» и имеет вид:
Программа 130
(defun ханойские-башни (высота)
(рrоgn (перенос "а "Ь "с высота) "готово))
ХАНОЙСКИЕ-БАШНИ
(defun перенос (из в вспомогательный n)
(cond
((= п 1) ; ветвь 2
(выведи из в) (t (перенос из ; ветвь1
вспомогательный
в
(- n 1))
(выведи из в)
(перенос вспомогательный ; ветвь 3
в
из
(- п 1)))))
ПЕРЕНОС
(defun выведи (из в)
(format t "~S -> ~S~%"из в))
ВЫВЕДИ
Вызов функции «ханойские башни» дает такое решение:
(ханойские-башни 3)
А->В
А->С
В->C
364
А->В
С->А
С->В
А->В
ГОТОВО
Можно убедиться, что определенная нами функция дает правильное решение для произ-
вольного числа дисков, однако время решения задачи с увеличением числа дисков быстро возрас-
тает.
8.8. СВОЙСТВА СИМВОЛОВ
В Лиспе могут
быть определены, так называемые, свойства символов. Список свойств име-
ет вид:
(имя_свойства1 значение1 имя_свойства2 значение2 . .. имя_свойстваN значениеN).
Присваивание нового свойства или изменение значения существующего осуществляется с
помощью функции PUTPROP (или просто PUT):
(PUTPROP символ свойство значение).
Выяснить значение свойства, связанного с символом, можно с помощью функции GET:
(GET символ свойство).
С использованием этой функции можно также присваивать свойства символам:
(SETF (GET символ свойство) значение).
Свойства символов глобальны Эта конструкция языка Лисп полезна во многих типичных
случаях представления данных, в том числе семантических сетей, фреймов и объектов объектно-
ориентированного программирования.
Контрольные вопросы и задания
1. В чем состоит основная идея функционального программирования?
2. Что называется символом в программировании на Лиспе?
3. Что такое атомы в программах на Лиспе?
4. Что такое список?
5. Охарактеризуйте примитивные функции языка Лисп.
6. Как можно связать с символом некоторое значение? Как поместить значение в ячейку
памяти?
7. Приведите примеры 1-выражений в Лиспе.
8. Как можно определить функцию и дать ей имя для последующих вызовов в Лиспе?
9. Охарактеризуйте управляющие формы в Лиспе.
10. Какую роль играет в функциональном программировании рекурсия?
11. Запишите рекурсивные определения функции проверяющую наличие в списке некото-
рого заданного элемента, подсчитывающую число элементов в списке, соединяющую два списка
(с использованием точечной нотации).
§9. ВВЕДЕНИЕ В ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ
ПРОГРАММИРОВАНИЕ
9.1. ОСНОВНЫЕ ПОЛОЖЕНИЯ
365
Как уже отмечалось выше (п. 4.1), в настоящее время растет популярность методологий,
ориентированных на данные. В первую очередь, это объектно-ориентированное программирова-
ние.
Объектно-ориентированная методология проектирования программ основана на концепци-
ях упрятывания информации и абстрактных типов данных. Такой подход рассматривает все такие
ресурсы как данные, модули и системы в качестве объектов. Каждый
объект
содержит некоторую
структуру данных (или тип данных), обрамленную набором процедур (методов), предназначенных
для манипулирования этими данными. Используя эту методологию, программист может создать
свой собственный абстрактный тип и отобразить проблемную область в эти созданные им абст-
ракции вместо традиционного отображения проблемной области в предопределенные управляю-
щие структуры и структуры данных языка программирования. Подобный подход является более
естественным, чем методологии, ориентированные на обработку (на процесс), из-за возможности
использовать в процессе программирования разнообразные виды абстракции типов данных. На
этом пути программист может сконцентрироваться на проекте системы, не беспокоясь о деталях
информационных объектов, используемых в системе.
Основные шаги разработки программы, предусмотренные данной
методологией:
• определить проблему;
• развить неформальную стратегию, представляющую общую последовательность шагов,
удовлетворяющую требованиям к будущей программе;
• формализовать стратегию
• идентифицировать объекты и
их атрибуты;
• идентифицировать операции;
• установить интерфейсы;
• реализовать операции.
Большинство современных языков и систем программирования развивается в направлении
все большего использования объектной методологии в создании программ. Характерными приме-
рами являются универсальные языки Паскаль, СИ и даже Бейсик, в современных версиях которых
появились средства объектно-ориентированного программирования. Так, начиная с версии 5.5,
Турбо-Паскаль
охватывает
метод
проектирования
программ
на
основе
объектно-
ориентированного программирования.
9.2. ОСНОВЫ ОБЪЕКТНОГО ПРОГРАММИРОВАНИЯ В СИСТЕМЕ ТУРБО-ПАСКАЛЬ
Объект
в ТурбоПаскале - это структура данных, содержащая поля данных различных типов
и заголовки методов и обобщающая структуру «Запись» (record).
Синтаксис описания объекта:
<ИмяПотомка>=
оbjесt<ИмяПредка> поле;
поле;
…
метод;
…
метод;
end;
В отличие от записи полями объекта могут быть, кроме данных, еще и методы, обрабаты-
вающие эти данные
Метод
- это процедура или функция, объявленные внутри описания объекта. Синтаксис
описания метода:
procedure <Заголовок>(<Параметр1>, <Параметр2>:integer),
Метод имеет доступ к полям данных объекта, не требуя передачи их ему в виде параметров