Программы на языке Лисп обычно представляют собой пример применения эвристики редукции: чтобы решить сложную задачу, ее разбивают на несколько более простых. Этот метод можно продемонстрировать на примере простой программы Манипулятор. Распечатка 1 содержит входящую в программу Манипулятор процедуру*, которая разбивает задачу перестановки кубика с места на место на три подзадачи (*Функции, используемые в Лиспе, как правило, являются словами английского языка. Приведем их перевод, чтобы облегчить понимание этой и последующих распечаток: defun — определить функцию, list —список, if — если, null—принятое в Лиспе обозначение пустого списка, first — первый, last — последний, rest — остаток, let—пусть. append—добавить, reverse — обратить, rеmove-if— удалить-сели, cons—сокращение от слова construct — строить, match — сопоставить, cond — имя условного выражения в Лиспе (conditional— условный», and — и, оr — или, equal — равный, second — второй): взять кубик, передвинуть его и опустить.
Рис. 2. Схема взаимодействия процедур, входящих в программу Манипулятор.
Рис. 2 изображает схему взаимодействия процедур, входящих в Манипулятор. Лисп позволяет создавать многоуровневые программы, подобные программе Манипулятор, в которых большие задачи постепенно разбиваются на все более мелкие подзадачи.
Распечатка 1. Процедура, входящая в программу Манипулятор, иллюстрирующая метод редукции