Учебник по Lisp (Материалы к экзамену и коллоквиумам 2013-го года)

Введение в программирование на языке ЛиспУчебное пособие для начинающихЛидия ГородняяGorod@iis.nsk.suНовсибирск, 20051СодержаниеПредисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31. Рекурсивные функции и структуры . . . . . . . . . . .2. Идеальный Лисп . . . . . . . .

. . . . . . . . . . . . . . . . . .3. Запись программ . . . . . . . . . . . . . . . . . . . . . . . . . . .4. Определение языка . . . . . . . . . . . . . . . . . . . . . . . . .5. Интерпретатор. . . . . . . . . . . . . . . . . . . . . . . . . . . . .6. Отображения и функционалы . . .

. . . . . . . . . . . . .7. Имена и контексты . . . . . . . . . . . . . . . . . . . . . . . .8. Управление процессами . . . . . . . . . . . . . . . . . . . . .9. Традиционное программирование . . . . . . . . . . . .10. Парадигмы программирования . . . . . . . . . . . . . .5102032435164768089История и выводы. . . .

. . . . . . . . . . . . . . . . . . . . . . . . . 93Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94Термины . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95Учебное пособие разработано при поддержке Российского фонда переподготовки кадров и сдано впечать в 2004 году.Курс разработан на базе Высшего колледжа информатики Новосибирского госуниверситета.Содержание курса соответствует PF4, PL7, PL5 классификатора CC2001CS.2ПредисловиеЦелью курса является изучение идей языка Лисп и методов функциональногопрограммирования. В курсе будут рассмотрены:-История языка Лиспа.Идеи символьной обработки информации.Принципы функционального программирования.Методы программирования на Лиспе.Автор языка Лисп – профессор математики и философии Джон Мак-Карти,выдающийся ученый в области искусственного интеллекта.

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

Понятие функции отчасти содержит концепциювремени: сначала вычисляются аргументы в порядке перечисления, затем всоответствии с заданным алгоритмом строится значение функции - ее результат.Лаконизм рекурсии может скрывать нелегкий путь к элегантному решениюзадачи. А. П. Ершов в предисловии к русскому переводу книги П.Хендерсонапривел поучительный пример задачи о рекурсивной формуле, сводящейвычитание единицы из натурального числа к прибавлению единицы:{1 –1 = 0 ; ( n +1 ) -1 = n } ,не поддавшейся А.Чёрчу и решенной С.Клини лишь в 1932 году:{ F (x, y, z) = если (x = 1) то 0иначеесли ((y +1) = x) то zиначе F (x, y +1, z +1) ;n –1 = F (n, 0, 0) }алг F ( цел x, y, z) арг x, y, zначесли (x = 1)то знач := 03инес (y +1) /= xто знач := F (x, y +1, z +1)коналг N-1 (цел N) арг N нач знач := F (N, 0, 0) конРешение получилось через введение формально усложненной вспомогательнойфункции с накопительными парметрами, что противоречит интуитивномустремлению к монотонности движения от простого к сложному.В настоящее время наблюдается устойчивый рост рейтинга интерпретируемыхязыков программирования и включение в компилируемые языки механизмовсимвольной обработки и средств динамического анализа, что повышает интерес кЛиспу и функциональному программированию.В этом курсе мы сконцентрируемся на ключевой идее Лиспа - сведении понятия“программа” к взаимодействию разных категорий функций, а также на основах иметодах функционального программирования.

Курс может быть адресованстудентам, любителям экспериментального программирования, преподавателяминформатики и старшеклассникам. Подробно познакомимся с базисом Лиспа,проанализируем конструктивность методов программирования на Лиспе, изучимпостроение Лисп-системы и узнаем ее архитектурные особенности, рассмотримметоды эффективного и прикладного программирования в функциональномстиле. С математическими основами Лиспа можно ознакомиться подробнее настраницах журнала “Компьютерные инструменты в образовании” [5,6].41.

Рекурсивные функции и структуры“Вот дом, который построил Джек …”Этот парагарф адресован новичкам, не знакомым с математическими основамипрограммирования и методами реализации систем программирования. Наигровых, почти шуточных, моделях рассмотрим понятия:-Рекурсия.Иерархия.Список.Функция.Модель 1.

"Матрешки"Представим, что перед нами сувенир “матрешки”, вкладывающиеся друг в друга.Эта модель достаточна для показа типовых явлений, вызывающих к жизнирекурсивные функции.Задача 1. Как узнать, сколько матрешек внутри?Предварительный анализ и описание процесса решения:1) Глядя на большую матрешку трудно сказать, сколько в ней спрятано ееменьших подруг. Но можно ее потрясти и по звуку понять, есть ли что-то внутриили она пуста.2) Если матрешка не пуста, то ее можно разнять и вынуть внутреннююматрешку, а части внешней матрешки соединить и поставить в сторонку, чтобы немешали дальнейшему эксперименту.3) Возвращаемся к исходной задаче, но с меньшей матрешкой, что гарантируетзавершение процесса. (Реальные вещи не могут уменьшаться до бесконечности.)4) Если матрешка пуста, то имеющиеся матрешки можно пересчитать – они всена виду.Такого рода процесс может быть представлен как рекурсивная функция,основанная на повторении действий и уменьшении данных до тех пор, покауменьшение становится невозможным.

В таком случае выполняется завершающеедействие. При решении задачи понадобились следующие базовые функции(действия):- Разбираем внешнюю матрешку и убираем ее.- Вынимаем внутренний комплект матрешек.- Трясем матрешку, чтобы узнать, есть ли что-то внутри.5Примечание [D1]: Примечание. Этот парагарф адресованчитателям, не знакомым сматематическими оснвоамипрограммирования и мтеодамиреализации рекурсивныхфункций в системахпрограммирования.Задача 2. Пусть все матрешки разобраны. Надо их собрать в одну.Предварительный анализ и описание процесса решения:Для решения такой задачи понадобится еще две функции:-Прячем меньшую матрешку в большуюСравниваем матрешки1) Выбираем самую маленькую матрешку.2) Сравниваем матрешки, ищем ближайшую к выбранной по размеру.3) Прячем меньшую матрешку в большую.4) Если еще остались матрешки, то возвращаемся к исходной задаче суменьшенным числом матрешек.5) Если матрешка всего одна, то процесс сборки завершен.Здесь рекурсивная функция решения задачи включает в себя поискподходящего элемента из набора, уменьшающегося на каждом витке процесса.Задача будет решена, когда обнаружится, что не из чего выбирать очереднойэлемент.Задача 3.

Надо выяснить сколько матрешек, а потом снова собрать их в одну.Предварительный анализ и описание процесса решения:При описании решения сразу учитываем, что понадобится не только разбиратьматрешек, но и собрать их обратно.1) Решаем задачу 1, но с небольшой поправкой в пункте 2:-Если матрешка не пуста, то ее можно разнять и вынуть внутреннююматрешку, а части внешней матрешки ставить рядом по очереди, чтобы потомих было удобно брать для сборки.2) Решаем задачу 2, но с учетом, что части разобранных матрешек стоят попорядку.

Значит, пункт 2 можно уточнить:-Берем части очередной матрешки.Согласованное решений двух задач для более общей задачи здесь выражено ворганизационных решениях по расположению промежуточных результатов, атакже в уточнении ранее существовавшего представления базовых функций.Модель 2. “Конверты и карточки”.6Другой ряд иллюстраций дает модель из конвертов, вкладываемых друг в друга.Конверты можно надписывать. Пустой конверт можно заменить карточкой с тойже надписью – это атом.

Внутрь коверта можно, как в матрешки, вкладыватьконверты или карточки. Подобным образом устроены иерархические структурыданных - символьные выражения (S-выражения). Вкладывание объекта вконверт - простейшая модель консолидации двух данных, сцепления их в одноболее сложное данное.Примеры:Пусть в конверт с надписью «ГОЛОВА» вложен пустой конверт с написью«ХВОСТ». Такую структуру данных можно изобразить в виде S-выражения:( ГОЛОВА .

ХВОСТ)Заключение в скобки символизирует целостность структуры. Если конверт снаписью «ХВОСТ» заранее вложить в конверт с написью «СЕРЕДИНА», а еговложить в конверт с надписью «ГОЛОВА», то соотвествующую структуруданных можно записать в виде S-выражения:( ГОЛОВА . (СЕРЕДИНА . ХВОСТ))Пустой конверт или карточку без написи можно изображать парой скобок.()Модель 3. “Кошелек”.Наклеим на лицевую сторону конверта большой карман. Получится нечто вродекошелька. Вместо надписи на конверте можно в карман кошелька вкладыватьнадписанную карточку.Возьмем карточку с написью «ЭЛЕМЕНТ» и вложим ее в карман пустогокошелька без написи – получится модель одноэлементного списка:(ЭЛЕМЕНТ)Многократным применениемпроизвольной длины.такогопроцессаможностроитьсписки(ЧЕМОДАН ПОРТФЕЛЬ РЮКЗАК ПОРТМОНЕ)Если разрешить в карман кошелька вместо карточек вкладывать другие кошельки,то элементы списка можно конструировать и получать многоуровневые спискивида:((ЭЛ1-1 ЭЛ1-2) ЭЛ 2 (ЭЛ3-1 ЭЛ3-2 ЭЛ3-3) ЭЛ4)По традиции в Лиспе пустой список изображается атомом NIL.

Атомарностьпустого списка вполне естественна в мире вещей – это прямой аналог упаковки.7Пустой конверт - обычная вещь, которую можно наполнить, тогда она становитсясложной, или опустошить, тогда она становится простой.Модель 4. “Форма , вид и пометки”.При организации процессов функции и их аргументы используются совместнои каждый комплект аргументов функции надо выделять.