Пример программирования на лиспе

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

Игра состоит в следующем. Используются три вертикальных стержня А, В, С и набор 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, Турбо-Паскаль охватывает метод проектирования программ на основе объектно-ориентированного программирования.