Разделы | Указатель | Оглавление

О книге помощи

Аннотация

Введение и обзор

Императивное программирование

Императивные языки программирования

Побочный эффект

Функциональное программирование

Что даёт функциональное программирование

Модели вычислений

Понятие функции

Способы задания функций

Список пар (кортежей)

Таблица

Множество уравнений

Правило (определение)

Чёрный ящик

Виды функций

Интуитивные понятия алгоритма и вычислимой функции

Формальные модели вычислений

Тезис Чёрча-Тьюринга

Частично-рекурсивные функции

Примитивные функции

Композиция

Примитивно-рекурсивные функции

Пример: сложение

Упражнения

Класс частично-рекурсивных функций

Пример: квадратный корень

Обсуждение

Функция Аккермана

Лямбда-нотация и лямбда-исчисление

Лямбда-нотация

Неформальное понятие лямбда-выражения

Примеры лямбда-выражений

Формальные системы

Лямбда-исчисление как формальная система

Определение лямбда-терма

Соглашения и обозначения

Примеры лямбда-термов

Свободные и связанные переменные

Определение свободных и связанных

Примеры свободных и связанных

Подстановка

α-конверсия и α-конгруэнтные термы

β-конверсия

Правильно построенные формулы

Правила вывода теории λ

Равенство термов

Теорема о неподвижной точке

Теорема о рекурсии

Экcтенсиональность

Теории λ+ext и λη

Теорема Карри (свойство экстенсиональности)

Редукция и равенство

Примеры редукции

Стратегии редукции

Теорема Чёрча-Россера

Комбинаторы

Комбинáторная полнота

Что дают комбинаторы

Композиция

Лямбда-вычислимость

Натуральные числа

Операции над нумералами - последователь

Прочие операции над нумералами

Пример умножения m * n

Лямбда-определимость числовых функций

Теорема Клини

Введение в Коммон Лисп

Элементы языка

Обзор возможностей

S-выражения языка Лисп

Примеры S-выражений

Аппликация

Префиксная нотация

Формы

Инструменты Лисп-системы

Встроенный текстовый редактор

Цикл чтение-оценивание-печать

Компиляция, загрузка, компоновка

Компоновка образа

Пример Hello World!

Имена и окружение

Константы и переменные

Связывание символов и окружение

Вычисление аппликации

Дерево вычислений

Функциональная абстракция

Определение функций

Примеры вызовов функции square

Равноправность встроенных и именованных функций

Подстановочная модель аппликации

Аппликативный порядок вычислений

Пример аппликативного порядка

Нормальный порядок вычислений

Пример нормального порядка

Функции работы с числами

Частное и остаток от деления

MAX и MIN - наибольшее и наименьшее из чисел

PRINT, PRIN1, PRINC, PPRINT - выдача на печать

Условные выражения и предикаты

Булевы значения - символы

Предикаты

Особый оператор IF

Особый оператор COND

NOT, AND, OR и булевы выражения

Резюме по примитивам Лисп

Процедуры и порождаемые ими процессы

Сложение - итерация

Сложение - линейная рекурсия

Числа Фибоначи - древовидная рекурсия

Дерево вычислений (FIB 5)

Числа Фибоначи - итерация

Ханойские башни - древовидная рекурсия

Функции в качестве аргументов

Пространства имён переменных и функций

Примитивы FUNCTION и FUNCALL

Примеры сумм

Абстракция суммирования и функционал SUM

Примеры использования функционала SUM

Автоаппликация

Безымянные функции и LAMBDA

Локальные переменные и LET

Определение LET через LAMBDA

LET связывает локально

LET связывает параллельно

LET* связывает последовательно

Множественное значение и VALUES

Числа Фибоначи - линейная рекурсия

Задача нахождения квадратного корня

Процесс вычисления квадратного корня

Декомпозиция

Процедуральная абстракция как вид абстракции отображения

Разделение труда

SQRT методом конечных приближений

Локальные функции

Функционал неподвижной точки

Нахождение неподвижной точки и обобщение

Реализация FIXED-POINT

Пример: решение уравнений

SQRT - наивная реализация через FIXED-POINT

SQRT через FIXED-POINT

Функционал AVERAGE-DAMP

SQRT через FIXED-POINT и AVERAGE-DAMP

Примитивные предикаты и функционалы

Унарные предикаты над числами

Функционал CONSTANTLY

Область видимости и время действия

Свободные переменные и модульность

Лексическое связывание

Глобальные переменные

Динамическое связывание

Полноправные элементы языка

Абстракция с помощью данных

Составные данные и абстрактные типы данных

Тип данных LIST (cписок) тип

Селекторы

Примеры списков

Предикаты над списками

Примеры вызова предикатов

LENGTH - длина списка

APPEND - соединение списков

Функции с остаточным параметром

MEMBER - поиск элемента в списке

Отображающие MAP-функционалы

MAPCAR - функционал отображения списков

Определение scale-list через MAPCAR

Иерархические структуры данных

Представление деревьев

Обход деревьев

Отображение деревьев

Отображение деревьев с помощью MAPCAR

Символьные данные

Кавычки в естественных языках

Знак апострофа ' и quote

Примеры использования quote

Тип данных SYMBOL тип

Функции SYMBOL-VALUE и SET функция

BOUNDP проверяет наличие значения

Пакеты символов — пространства имён

Встроенные пакеты Коммон Лисп

Примитивы для работы с пакетами

Полное имя символа

Иерархия встроенных типов Коммон Лисп

Предикаты проверки на равенство

Предикат = и математическое равенство

Предикат EQ и "машинное" равенство

Предикат EQL и числа одного типа

Предикат EQUAL и изоморфизм списков

Предикат EQUALP и наиболее общее равенство

Равенство функций

Пример: гипотеза Коллатца

Рекурсивно-операторное программирование

Присваивание

Оператор SETQ и значения переменных

Присваивание необъявленной переменной

Обобщённый оператор присваивания SETF

Модифицирующие функции (модификаторы)

Модифицирующие макросы

PROG1, PROG2, PROGN - последовательное исполнение

WHEN и UNLESS - условные операторы

CASE - разбор вариантов

DOTIMES - цикл по счётчику

DOLIST - цикл по списку

LOOP - простой цикл и возврат RETURN

Универсальный цикл LOOP

TAGBODY - лексические метки и локальный переход GO

BLOCK - программный блок и нелокальный выход RETURN-FROM

Динамические метки CATCH и нелокальный выход THROW

Сочетание рекурсии и цикла

Пример реверсирования дерева

Векторы, массивы и последовательности

VECTOR - конструктор простого вектора

MAKE-ARRAY - конструктор массива function

Селекторы для массива

Универсальные массивы

Специализированные массивы

PRINT-MATRIX - распечатка матриц

Квадратные скобки []

Параллельное и циклическое присваивание

PSETF - параллельное присваивание

ROTATEF - циклический сдвиг

Хэш-таблицы и действия с ними

MAKE-HASH-TABLE - создание хэш-таблицы

GETHASH - получение элемента хэш-таблицы

REMHASH - удаление элемента хэш-таблицы

Последовательности

MAKE-SEQUENCE - создание последовательности

ELT - доступ к элементу последовательности

SUBSEQ - извлечение подпоследовательности

Функции работы с последовательностями

Ключевые аргументы test и test-not

Ключевой аргумент key

Ключевые аргументы start и end

Ключевой аргумент count

Ключевой аргумент from-end

SORT - сортировка последовательности

Знаки и строки

Тип данных CHARACTER (знак)

Предикаты на знаках

Сравнение кодов

Регистро-независимое сравнение латинских букв

Буква или цифра

Цифра в заданной системе счисления

Функции на знаках

Проверка и преобразование регистра буквы

Преобразование регистра буквы

Регистро-независимое сравнение русских букв

Тип данных STRING (строка)

MAKE-STRING - создание строки

CHAR - доступ к элементу строки

Предикаты на строках

Поэлементное сравнение

Регистро-независимое сравнение

Регистро-независимое сравнение строк с русскими буквами

Функции на строках

Преобразование регистра букв

Удаление знаков с концов

PRINC-TO-STRING - выдача объекта в строку

Функции для строк и последовательностей

COERCE - преобразование объекта к другому типу

COPY-SEQ - копирование последовательности

CONCATENATE - соединение последовательностей

MAP - функционал отображения последовательностей

SEARCH - поиск подпоследовательности

REPLACE - замена подпоследовательности

Функции для строк и векторов

VECTOR-PUSH - добавление в вектор

Слова, предложения и тексты

Пример функций разбиения на слова и подсчёта слов

Пример распечатки частоты употребления слов

Обобщённые функции

Передача сообщений

Программирование, управляемое данными

Легкость управления данными в Лисп

DEFGENERIC вводит обобщённую функцию

DEFMETHOD определяет метод

Особенности методов Коммон Лисп

DEFCLASS определяет класс

MAKE-INSTANCE создаёт экземпляр класса

SLOT-VALUE извлекает значение слота

Извлечение значения слота с помощью селектора

POLAR - точка в полярных координатах

Изменение значения слота и функции доступа

Полярные координаты по декартовым

TO-POLAR - обобщённая функция преобразования к полярным координатам

Декартовые координаты по полярным

ADD2 - обобщённая функция сложения

Сложение радиус-векторов

MUL2 - обобщённая функция умножения

Умножение радиус-вектора на скаляр

Классы геометрических фигур

LINE - отрезок

TRIANGLE - треугольник

Символьная алгебра

Арифметика многочленов (полиномов)

TERM - терм (слагаемое)

POLYNOM - многочлен

Распечатка многочленов

Примеры многочленов

Сложение многочленов

Умножение многочленов

Многочлены в качестве коэффициентов

Сложение многочленов с коэффициентами-многочленами

Примеры использования Коммон Лисп

Лямбда-исчисление и комбинаторная алгебра

Каррирование

Поглотители

Нумералы Чёрча

Графический интерфейс пользователя (GUI)

Графические пакеты в LispWorks

Создание графического порта

Одноразовая визуализация

Непрерывная визуализация и display-callback

Обработка пользовательского ввода

Сессионный протокол FRP (File Retrieval Protocol)

Лабораторные работы

Лабораторная работа 1: Примитивные функции и особые операторы Коммон Лисп

Вариант 1.1 (сложность 1)

Вариант 1.2 (сложность 1)

Вариант 1.3 (сложность 1)

Вариант 1.4 (сложность 1)

Вариант 1.5 (сложность 1)

Вариант 1.6 (сложность 1)

Вариант 1.7 (сложность 1)

Вариант 1.8 (сложность 1)

Вариант 1.9 (сложность 1)

Вариант 1.10 (сложность 1)

Вариант 1.11 (сложность 1)

Вариант 1.12 (сложность 1)

Вариант 1.13 (сложность 1)

Вариант 1.14 (сложность 1)

Вариант 1.15 (сложность 1)

Вариант 1.16 (сложность 1)

Вариант 1.17 (сложность 2)

Вариант 1.18 (сложность 2)

Вариант 1.19 (сложность 2)

Вариант 1.20 (сложность 2)

Вариант 1.21 (сложность 2)

Вариант 1.22 (сложность 2)

Вариант 1.23 (сложность 2)

Вариант 1.24 (сложность 2)

Вариант 1.25 (сложность 2)

Вариант 1.26 (сложность 2)

Вариант 1.27 (сложность 3)

Вариант 1.28 (сложность 3)

Вариант 1.29 (сложность 3)

Вариант 1.30 (сложность 3)

Вариант 1.31 (сложность 3)

Вариант 1.32 (сложность 3)

Вариант 1.33 (сложность 3)

Вариант 1.34 (сложность 3)

Вариант 1.35 (сложность 3)

Вариант 1.36 (сложность 3)

Вариант 1.37 (сложность 3)

Вариант 1.38 (сложность 3)

Вариант 1.39 (сложность 3)

Вариант 1.40 (сложность 3)

Вариант 1.41 (сложность 3)

Вариант 1.42 (сложность 3)

Вариант 1.43 (сложность 4)

Вариант 1.44 (сложность 4)

Вариант 1.45 (сложность 4)

Вариант 1.46 (сложность 4)

Вариант 1.47 (функция Аккермана, сложность 4)

Вариант 1.48 (сложность 4)

Лабораторная работа 2: Простейшие функции работы со списками Коммон Лисп

Вариант 2.1 (сложность 1)

Вариант 2.2 (сложность 1)

Вариант 2.3 (сложность 1)

Вариант 2.4 (сложность 1)

Вариант 2.5 (сложность 1)

Вариант 2.6 (сложность 1)

Вариант 2.7 (сложность 1)

Вариант 2.8 (сложность 1)

Вариант 2.9 (сложность 2)

Вариант 2.10 (сложность 2)

Вариант 2.11 (сложность 2)

Вариант 2.12 (сложность 2)

Вариант 2.13 (сложность 2)

Вариант 2.14 (сложность 2)

Вариант 2.15 (сложность 2)

Вариант 2.16 (сложность 2)

Вариант 2.17 (сложность 2)

Вариант 2.18 (сложность 2)

Вариант 2.19 (сложность 2)

Вариант 2.20 (сложность 2)

Вариант 2.21 (сложность 2)

Вариант 2.22 (сложность 2)

Вариант 2.23 (сложность 2)

Вариант 2.24 (сложность 2)

Вариант 2.25 (сложность 2)

Вариант 2.26 (сложность 2)

Вариант 2.27 (сложность 2)

Вариант 2.28 (сложность 2)

Вариант 2.29 (сложность 2)

Вариант 2.30 (сложность 2)

Вариант 2.31 (сложность 2)

Вариант 2.32 (сложность 2)

Вариант 2.33 (сложность 2)

Вариант 2.34 (сложность 2)

Вариант 2.35 (сложность 3)

Вариант 2.36 (сложность 3)

Вариант 2.37 (сложность 3)

Вариант 2.38 (сложность 3)

Вариант 2.39 (сложность 3)

Вариант 2.40 (сложность 3)

Вариант 2.41 (сложность 3)

Вариант 2.42 (сложность 3)

Вариант 2.43 (сложность 4)

Лабораторная работа 3: Последовательности, массивы и управляющие конструкции Коммон Лисп

Вариант 3.1 (сложность 1)

Вариант 3.2 (сложность 1)

Вариант 3.3 (сложность 1)

Вариант 3.4 (сложность 1)

Вариант 3.5 (сложность 1)

Вариант 3.6 (сложность 1)

Вариант 3.7 (сложность 1)

Вариант 3.8 (сложность 1)

Вариант 3.9 (сложность 1)

Вариант 3.10 (сложность 1)

Вариант 3.11 (сложность 1)

Вариант 3.12 (сложность 1)

Вариант 3.13 (сложность 1)

Вариант 3.14 (сложность 2)

Вариант 3.15 (сложность 2)

Вариант 3.16 (сложность 2)

Вариант 3.17 (сложность 2)

Вариант 3.18 (сложность 2)

Вариант 3.19 (сложность 2)

Вариант 3.20 (сложность 2)

Вариант 3.21 (сложность 2)

Вариант 3.22 (сложность 2)

Вариант 3.23 (сложность 2)

Вариант 3.24 (сложность 2)

Вариант 3.25 (сложность 2)

Вариант 3.26 (сложность 2)

Вариант 3.27 (сложность 2)

Вариант 3.28 (сложность 2)

Вариант 3.29 (сложность 2)

Вариант 3.30 (сложность 2)

Вариант 3.31 (сложность 2)

Вариант 3.32 (сложность 2)

Вариант 3.33 (сложность 2)

Вариант 3.34 (сложность 2)

Вариант 3.35 (сложность 2)

Вариант 3.36 (сложность 2)

Вариант 3.37 (сложность 2)

Вариант 3.38 (сложность 2)

Вариант 3.39 (сложность 2)

Вариант 3.40 (сложность 2)

Вариант 3.41 (сложность 2)

Вариант 3.42 (сложность 3)

Вариант 3.43 (сложность 3)

Вариант 3.44 (сложность 3)

Вариант 3.45 (сложность 3)

Вариант 3.46 (сложность 3)

Вариант 3.47 (сложность 3)

Вариант 3.48 (сложность 3)

Лабораторная работа 4: Знаки и строки

Вариант 4.1 (сложность 1)

Вариант 4.2 (сложность 1)

Вариант 4.3 (сложность 1)

Вариант 4.4 (сложность 1)

Вариант 4.5 (сложность 1)

Вариант 4.6 (сложность 1)

Вариант 4.7 (сложность 1)

Вариант 4.8 (сложность 1)

Вариант 4.9 (сложность 2)

Вариант 4.10 (сложность 2)

Вариант 4.11 (сложность 2)

Вариант 4.12 (сложность 2)

Вариант 4.13 (сложность 2)

Вариант 4.14 (сложность 2)

Вариант 4.15 (сложность 2)

Вариант 4.16 (сложность 2)

Вариант 4.17 (сложность 2)

Вариант 4.18 (сложность 2)

Вариант 4.19 (сложность 2)

Вариант 4.20 (сложность 2)

Вариант 4.21 (сложность 2)

Вариант 4.22 (сложность 2)

Вариант 4.23 (сложность 2)

Вариант 4.24 (сложность 2)

Вариант 4.25 (сложность 2)

Вариант 4.26 (сложность 2)

Вариант 4.27 (сложность 2)

Вариант 4.28 (сложность 2)

Вариант 4.29 (сложность 2)

Вариант 4.30 (сложность 2)

Вариант 4.31 (сложность 2)

Вариант 4.32 (сложность 2)

Вариант 4.33 (сложность 3)

Вариант 4.34 (сложность 3)

Вариант 4.35 (сложность 3)

Вариант 4.36 (сложность 3)

Вариант 4.37 (сложность 3)

Вариант 4.38 (сложность 3)

Вариант 4.39 (сложность 3)

Вариант 4.40 (сложность 3)

Вариант 4.41 (сложность 3)

Вариант 4.42 (сложность 3)

Вариант 4.43 (сложность 3)

Вариант 4.44 (сложность 3)

Вариант 4.45 (сложность 3)

Вариант 4.46 (сложность 3)

Вариант 4.47 (сложность 3)

Вариант 4.48 (сложность 3)

Лабораторная работа 5: Обобщённые функции, методы и классы объектов

Вариант 5.1 (сложность 1)

Вариант 5.2 (сложность 1)

Вариант 5.3 (сложность 1)

Вариант 5.4 (сложность 1)

Вариант 5.5 (сложность 1)

Вариант 5.6 (сложность 1)

Вариант 5.7 (сложность 1)

Вариант 5.8 (сложность 1)

Вариант 5.9 (сложность 1)

Вариант 5.10 (сложность 1)

Вариант 5.11 (сложность 1)

Вариант 5.12 (сложность 1)

Вариант 5.13 (сложность 1)

Вариант 5.14 (сложность 1)

Вариант 5.15 (сложность 1)

Вариант 5.16 (сложность 1)

Вариант 5.17 (сложность 1)

Вариант 5.18 (сложность 1)

Вариант 5.19 (сложность 1)

Вариант 5.20 (сложность 1)

Вариант 5.21 (сложность 1)

Вариант 5.22 (сложность 2)

Вариант 5.23 (сложность 2)

Вариант 5.24 (сложность 2)

Вариант 5.25 (сложность 2)

Вариант 5.26 (сложность 2)

Вариант 5.27 (сложность 2)

Вариант 5.28 (сложность 2)

Вариант 5.29 (сложность 2)

Вариант 5.30 (сложность 2)

Вариант 5.31 (сложность 2)

Вариант 5.32 (сложность 2)

Вариант 5.33 (сложность 2)

Вариант 5.34 (сложность 2)

Вариант 5.35 (сложность 2)

Вариант 5.36 (сложность 2)

Вариант 5.37 (сложность 3)

Вариант 5.38 (сложность 3)

Вариант 5.39 (сложность 3)

Вариант 5.40 (сложность 3)

Вариант 5.41 (сложность 3)

Вариант 5.42 (сложность 3)

Вариант 5.43 (сложность 3)

Вариант 5.44 (сложность 3)

Вариант 5.45 (сложность 3)

Приложение А. История языка Лисп

Цитаты

Известные системы, написанные на Лисп

Лисп и другие языки программирования

Приложение Б. Обзор других функциональных языков

ML (1973)

FP (1977)

Hope (1980)

Miranda (1985)

Haskell (1990)

F# (2005)

Литература

По языку Лисп

Рекомендуемые Лисп-системы

Предметный указатель