Рассмотрим в качестве примера программирования на Лиспе менее элементарную классическую задачу, носящую название игры в «ханойские башни».
Игра состоит в следующем. Используются три вертикальных стержня А, В, С и набор 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
А->В
С->А
С->В
А->В
ГОТОВО
Можно убедиться, что определенная нами функция дает правильное решение для произвольного числа дисков, однако время решения задачи с увеличением числа дисков быстро возрастает.
СВОЙСТВА СИМВОЛОВ
В Лиспе могут быть определены, так называемые, свойства символов. Список свойств имеет вид:
(имя_свойства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. Запишите рекурсивные определения функции проверяющую наличие в списке некоторого заданного элемента, подсчитывающую число элементов в списке, соединяющую два списка (с использованием точечной нотации).
ВВЕДЕНИЕ В ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ
ОСНОВНЫЕ ПОЛОЖЕНИЯ
Как уже отмечалось выше (п. 4.1), в настоящее время растет популярность методологий, ориентированных на данные. В первую очередь, это объектно-ориентированное программирование.
Объектно-ориентированная методология проектирования программ основана на концепциях упрятывания информации и абстрактных типов данных. Такой подход рассматривает все такие ресурсы как данные, модули и системы в качестве объектов. Каждый объект содержит некоторую структуру данных (или тип данных), обрамленную набором процедур (методов), предназначенных для манипулирования этими данными. Используя эту методологию, программист может создать свой собственный абстрактный тип и отобразить проблемную область в эти созданные им абстракции вместо традиционного отображения проблемной области в предопределенные управляющие структуры и структуры данных языка программирования. Подобный подход является более естественным, чем методологии, ориентированные на обработку (на процесс), из-за возможности использовать в процессе программирования разнообразные виды абстракции типов данных. На этом пути программист может сконцентрироваться на проекте системы, не беспокоясь о деталях информационных объектов, используемых в системе.
Основные шаги разработки программы, предусмотренные даннойметодологией:
• определить проблему;
• развить неформальную стратегию, представляющую общую последовательность шагов, удовлетворяющую требованиям к будущей программе;
• формализовать стратегию
• идентифицировать объекты иих атрибуты;
• идентифицировать операции;
• установить интерфейсы;
• реализовать операции.
Большинство современных языков и систем программирования развивается в направлении все большего использования объектной методологии в создании программ. Характерными примерами являются универсальные языки Паскаль, СИ и даже Бейсик, в современных версиях которых появились средства объектно-ориентированного программирования. Так, начиная с версии 5.5, Турбо-Паскаль охватывает метод проектирования программ на основе объектно-ориентированного программирования.
