Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп

Московский государственный университетимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиЕ.И. Большакова, Н.В. ГруздеваОсновы программированияна языке ЛиспУчебное пособиеМосква – 20101УДКББКРецензенты:доцент, к.ф.-м.н. В.В. Малышкост. научный сотрудник, к.ф.-м.н. Ю.С. ВладимироваБольшакова Елена Игоревна,Груздева Надежда ВалерьевнаОсновы программирования на языке Лисп: Учебное пособие.

– М.:Издательский отдел факультета ВМК МГУ имени М.В.Ломоносова(лицензия ИД № 05899 от 24.09.2001); МАКС Пресс, 2010 – 112 с.В учебном пособии излагаются основные понятия и базовые механизмыфункционального языка программирования Лисп, ориентированного на решениезадач обработки символьных данных. Рассматриваются приемы рекурсивногопрограммирования, в том числе с использованием функционалов.

Подробноразбираются примеры лисп-программ. В пособие включено также описаниезаданий практикума по программированию на языке Лисп, проводимого длястудентов факультета ВМК МГУ.Печатается по решению Редакционно-издательского совета факультетавычислительной математики и кибернетики МГУ им. М. В. ЛомоносоваISBN 978-5-89407-441-2© Издательский отдел факультетавычислительной математики и кибернетикиМГУ им.

М. В. Ломоносова, 2010© Большакова Е.И., Груздева Н.В., 20102Содержание1. Базовый Лисп ............................................................................................. 51.1. Атомы и списки, функции .................................................................. 51.2. Базовый набор функций ..................................................................... 81.3. Определение функций ......................................................................

131.4. Встроенные функции ........................................................................ 171.5. Рекурсивные функции ...................................................................... 221.6. S-выражения ...................................................................................... 271.7. Внутреннее представление S-выражений ....................................... 311.8. Лисп-программа ................................................................................ 362. Рекурсивное программирование .............................................................

412.1. Простая рекурсия .............................................................................. 412.2. Косвенная рекурсия ......................................................................... 442.3. Параллельная рекурсия .................................................................... 462.4. Накапливающий параметр ............................................................... 512.5.

Рекурсия более высокого порядка ................................................... 552.6. Задачи на программирование рекурсии .......................................... 593. Функционалы ........................................................................................... 623.1. Понятие функционала ...................................................................... 623.2. Встроенные функционалы................................................................ 643.3. Замыкание функционального аргумента .........................................

673.4. Применение функционалов ............................................................. 713.5. Функционалы с функциональным значением ................................. 774. Дополнительные возможности ............................................................... 804.1. Список свойств атома .......................................................................

804.2. Функции ввода, вывода и работы с символами .............................. 844.3. Общий вид функций cond, defun, let ................................................ 884.4. Определение особых функций ......................................................... 914.5. Макросредства ..................................................................................

954.6. Циклы, блоки и присваивания ....................................................... 1005. Задания практикума .............................................................................. 1046. Литература ............................................................................................. 111Приложение: Встроенные функции языка Лисп ........................................

1123ПредисловиеЯзык Лисп – один из старейших языков программирования и первыйфункциональный язык, получивший широкое распространение. Ядро языкабыло создано в 60-х годах прошлого века известным ученымДж. Маккарти для решения задач обработки символьной информации[1, 2].

Основная структура данных языка Лисп – список, отсюда и названиеязыка: Lisp – List Processing.Пик популярности Лиспа пришёлся на 70-е и 80-е годы, когда онприменялся как основной язык для научных исследований в областиискусственного интеллекта. В эти годы было разработано несколькодостаточно развитых диалектов языка, из которых наиболее известныInterLisp, MacLisp, Common Lisp. Одна из первых реализаций Лиспа вРоссии была осуществлена для ЭВМ БЭСМ-6 [8]. На базе концепцийЛиспа был создан ряд других функциональных языков, в частности – языкPlanner [10] для задач искусственного интеллекта и язык Scheme [3].Хотя язык Лисп существует и развивается давно, тем не менее, он небыл стандартизован, и его диалекты различаются по ряду аспектов.Официальный стандарт разработан только для языка Common Lisp[4, 5, 16], возникшего в результате попытки объединить в одном языкесредства нескольких диалектов Лиспа, а также языка Scheme.

В настоящеевремя кроме нескольких реализаций языка Common Lisp используетсядиалект AutoLisp [12] известного пакета AutoCAD, а также достаточностарый, но удачный диалект MuLisp, частично описанный в [13].Несмотря на то, что Лисп потерял главенствующую роль как языкпрограммирования задач искусственного интеллекта, в силу ряда своихкачеств он остается языком, удобным для изучения функциональногопрограммирования. Лисп – один из наиболее ярких представителейфункциональной парадигмы программирования [14, 15]. Простота иясность синтаксиса сочетаются в нём с мощностью языковых средств иестественностью его расширения.

Одна из наиболее удивительныхособенностей Лиспа – это единая синтаксическая форма записи программи данных, что позволяет обрабатывать структуры данных как программы имодифицировать программы как данные.В основу данного учебного пособия легли лекции пофункциональному программированию на базе языка Лисп, неоднократночитавшиеся Е.И. Большаковой на факультете ВМК МГУ им. Ломоносова.Основное внимание в пособии уделяется базовым функциональнымсредствам языка Лисп, позволяющим изучить основополагающиепринципы функциональной парадигмы. Поскольку непременнойсоставляющейфункциональногопрограммированияявляетсяиспользование рекурсии, в учебном пособии подробно разбираютсяприёмыпостроениярекурсивныхпрограмм,иллюстрируемые4многочисленными примерами.Рассматриваютсятакжевопросыпостроения функционалов – функций, аргументами и значением которыхявляются функции.Учебное пособие не ставит своей целью описание какого-токонкретного диалекта языка Лисп, однако в нём освещается ряд важныхособенностей двух его известных диалектов – Common Lisp и MuLisp, вслучае их принципиальных отличий.

Существующие в современныхдиалектах Лиспа конструкции, нарушающие принципы строгойфункциональности и внесённые в язык под давлением императивнойпарадигмы программирования (присваивания, блоки и др.), описываютсялишь для полноты картины языка и сравнительно кратко.В последнем разделе пособия приводятся задания практикума попрограммированию на языке Лисп, поддерживающие его изучение.Авторы благодарят Н.В. Баеву за помощь в подготовке пособия.1. Базовый ЛиспВ данном разделе рассматриваются основы языка Лисп – в своёмбольшинстве это функциональные средства, предложенные автором языкаДж. Маккарти и составившие чисто функциональный диалект Lisp 1.5[2, 9].

Эти базовые средства представлены во всех современных диалектахязыка Лисп.1.1. Атомы и списки, функцииОбрабатываемые в языке Лисп данные можно разделить наскалярные (простые) и структурные (составные). К скалярным даннымотносятся атомы (атом – неделимое целое), а к структурным – списки,или списочные структуры. В свою очередь атомы подразделяются на:•символьные, т.е.

идентификаторы (например: BETA , A , SYM_1);•числовые, т.е. целые и вещественные числа (-25, 375.08 и др.).Символьные атомы состоят из букв, цифр и других символов иотличаются от числовых атомов первым символом. Если атом начинается сцифры и знаков + и -, то он считается числом, которое должно бытьзаписано по общепринятым правилам.