Парадигмы программирования, группы 8201–8203: язык LISP

Общая информация

В 1 семестре 2010-2011 учебного года на практических занятих по спецкурсу кафедры систем информатики «Парадигмы программирования» изучается язык LISP. В связи с большим количеством студентов в группе занимаемся по принципу «пришёл, сдал, ушёл» (либо приходим со своим ноутбуком, на котором установлен Common LISP). О занятиях, на которых будет рассказываться теория, я буду сообщать заранее.

Условия: задачи 1, 2, 3, 4, 6, 8, 10 являются обязательными и получить зачёт, не сдав их, невозможно. Оценка «удовлетворительно» ставится за 7, 8 или 9 сданных задач (включая все обязательные). Оценка «хорошо» ставится за 10–12* сданных задач (включая все обязательные). Оценка «отлично» ставится за 12 13* сданных задач.

* Ранее было написано иначе (по историческим причинам): я решил разбить последнюю задачу на две, но не обновил главную страницу.

Время и место: среда, 9:00, ауд. 309 с.к. НГУ.

Преподаватель: Александр Геннадьевич Фенстер, fenster@fenster.name, +7 913 9053295.
Лекции по курсу читает Лидия Васильевна Городняя.

Рекомендуемая литература:

Таблица результатов

# Фамилия, имя  1   2   3   4   5   6   7   8   9   10   11   12   13  Итого
Оценка за практику
1
Балабанов Артём
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
2
Бовкун Екатерина
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
3
Добросельский Максим
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
4
Жиров Александр
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
5
Зырянов Константин
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
6
Ивлев Александр
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
7
Косырькова Ольга
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
8
Кошелев Анатолий
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
9
Крупин Сергей
+
+
+
+
+
+
+
+
+
+
 
 
 
10
хорошо
10
Полунин Денис
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
11
Свиридов Валентин
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
12
Стененко Александр
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
13
Степанкевич Евгений
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
14
Федотов Виктор
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично

Гистограмма

Список семестровых заданий

Часть 1. Основы языка LISP, простейшая рекурсия, функциональный базис

  1. Склеивание списков. Напишите функцию append1, которая объединяет два списка:
    > (append1 '(a b) '(c d))
    (A B C D)
     Функция с именем append является стандартной, поэтому ваша функция может называться append1 или как-то иначе. То же самое верно для следующих заданий, в которых имя функции содержит единицу.

  2. Разворот списка. Напишите функцию reverse1, которая «переворачивает» список:
    > (reverse1 '(a b c))
    (C B A)

  3. Список атомов. Напишите функцию, возвращающую список атомов из данного S-выражения в том же порядке, в котором они в него входят.
    Пример:
    > (atoms '((a b) c nil (d (e f g))))
    (A B C NIL D E F G)

  4. Сравнение. Используя предикат eql, умеющий сравнивать два атома, реализуйте предикат equal1, сравнивающий два S-выражения. Пример:
    > (equal1 '(1 3 5) '(1 3 5))
    T
    > (equal1 '(1 3 5) '(1 (3 5)))
    NIL

  5. Перестановки. Выведите все возможные перестановки элементов данного списка в произвольном порядке (по одному разу каждую). В приведённом ниже примере функция возвращает список из перестановок. Ваша функция может работать иначе (например, выводить перестановки на экран).
    Пример:
    > (permut '(1 2 3))
    ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

Часть 2. Функции высших порядков

  1. Сортировка. Напишите функцию, сортирующую список элементов любого типа любым способом (сложность алгоритма не важна, но имейте в виду, что реализовать вариант quicksort'а, возможно, даже чуть проще и при этом намного интереснее, чем простую сортировку за O(N2)). Функция должна принимать список и предикат сравнения.
    Пример:
    > (sort1 '(1 5 2 4 3) '<)
    (1 2 3 4 5)

  2. Поиск пути к атому. Реализуйте функцию, принимающую список и атом и возвращающую функцию, которая, будучи применённой к этому списку, вернёт этот атом.
    Пример:
    > (setq arg '(a (b c) d))
    ARG
    > (find-in-list arg 'c)
    #<FUNCTION :LAMBDA (L) .....>
    > (funcall (find-in-list arg 'c) arg)
    C

Часть 3. Функции map, reduce, filter

В Common LISP функции из заголовка называются, соответственно, mapcar, reduce и remove-if-not. При реализации следующих двух заданий старайтесь не использовать рекурсию, пользуясь для перебора элементов списка указанными в заголовке функциями.

  1. Простые числа. Реализуйте функцию, возвращающую список простых чисел, не превышающих N. Для получения списка всех натуральных чисел от 2 до N можно использовать (loop for i from 2 to N collect i).
    Пример:
    > (primes 15)
    (2 3 7 11 13)

  2. Калькулятор обратной польской записи. Реализуйте функцию, вычисляющую значение выражения, записанного в обратной польской записи в виде списка. Для вычисления арифметических операций в данном случае удобно использовать funcall: (funcall '+ 1 3) равно четырём.
    Пример:
    > (calc '(1 2 + 1 3 + *))
    12

Часть 4. Замыкания

Теория по этой теме находится в отдельном файле.

  1. Генератор простых чисел. Реализуйте генератор простых чисел. Должно быть возможно создать неограниченное количество независимых друг от друга генераторов: каждый из них «помнит» число, на котором он остановился.
    Пример:
    > (setq gen1 (make-primes-generator))
    GEN1
    > (funcall gen1)
    2
    > (funcall gen1)
    3

Часть 5. Индивидуальные задания

Распределение заданий приведено в таблице, формулировки задач находятся в отдельном файле.

  1. Индивидуальное задание. Задание из первой половины списка дополнительных задач; решайте на лиспе.

  2. Индивидуальное задание. Задание из второй половины списка дополнительных задач; решайте на лиспе.

  3. Индивидуальное задание. Решите предыдущую задачу на любом императивном языке (или языке, который в сознании среднего программиста является императивным). Постарайтесь не придумывать новый алгоритм, а именно переписать решение с лиспа на другой язык. Если вы не знаете, какой язык выбрать, попробуйте JavaScript, Perl или Python (хотя никто не мешает использовать C или C++, если желаете, но в этом случае прошу внимательно следить за выделением-освобождением памяти при работе со списками).