Парадигмы программирования, группы 920x: язык LISP

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

29.12.2011 г.: занятия в семестре окончены, зачёты выставлены.
Вынужден констатировать, что в этом году объём списывания заданий был выше среднего. В связи с этим после первой волны списываний я разослал студентам предупреждение о том, что следующие пойманные на сдаче чужих решений получат оценку не выше «тройки» и их фамилии будут особо отмечены на сайте. К моему глубокому сожалению, вынужден исполнить это обещание и сообщить, что

  • Виноградов Владимир, гр. 9202
  • Макаров Максим, гр. 9202

не прислушались к моей просьбе и сдали мне в конце семестра чужие решения. Надеюсь, что им будет достаточно стыдно :)

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

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

Загрузка файлов:

В настоящее время загрузка файлов отключена.

Время и место: четверг, 14:15, ауд. 309 с.к. НГУ.

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

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

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

Внимание! Если вы не прислали мне письмо, вашего имени нет в таблице. Если вашего имени нет в таблице, вы не можете сдавать задачи. Если вы не можете сдавать задачи, вы не можете получить зачёт. Пришлите письмо!
Subject: Парадигмы программирования

# Фамилия, имя  1   2   3   4   5   6   7   8   9   10   11   12   13  Итого
Оценка за практику
1
Алимов Артём
+
+
+
+
+
+
+
+
+
+
 
 
 
10
хорошо
2
Андреев Игорь
+
+
+
+
 
+
 
+
 
+
 
 
 
7
удовл
3
Афонасов Никита
+
+
+
+
 
+
+
+
+
+
+
 
 
10
хорошо
4
Ахмадеева Ирина
+
+
+
+
+
+
+
+
+
+
 
 
 
10
хорошо
5
Виноградов Владимир
+
+
+
+
+
+
+
+
+
+
 
 
 
10
удовл (списал!)
6
Джумагазиев Тимур
+
+
+
+
 
+
+
+
+
+
+
 
 
10
хорошо
7
Климов Антон
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
8
Ковалёв Данила
+
+
+
+
+
+
+
+
+
+
+
 
 
11
хорошо
9
Колбин Ярослав
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
10
Колесникова Кристина
+
+
+
+
+
+
+
+
+
+
 
 
 
10
хорошо
11
Кондратьев Дмитрий
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
12
Курлаев Ярослав
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
13
Макаров Максим
+
+
+
+
+
+
+
+
+
+
 
 
 
10
удовл (списал!)
14
Мачульскис Сергей
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
15
Мезин Александр
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
16
Миронов Владимир
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
17
Плеханов Андрей
+
+
+
+
+
+
+
+
+
+
 
 
 
10
хорошо
18
Скворцов Максим
+
+
+
+
+
+
+
+
+
+
+
+
+
13
отлично
19
Сумбатянц Илья
+
+
+
+
+
+
+
+
+
+
 
 
 
10
хорошо
20
Тарасова Ирина
+
+
+
+
+
+
+
+
+
+
 
 
 
10
хорошо
21
Усольцева Мария
+
+
+
+
+
+
+
+
+
+
+
 
 
11
хорошо
22
Шелепов Алексей
+
+
+
+
+
+
+
+
+
+
 
 
 
10
хорошо
23
Шелухина Евгения
+
+
+
+
+
+
+
+
+
+
 
 
 
10
хорошо
24
Яковлев Михаил
+
+
+
+
+
+
+
+
+
+
+
+
+
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. Поиск пути к атому. Реализуйте функцию, принимающую список и атом и возвращающую функцию, которая, будучи применённой к этому списку, вернёт этот атом.
    Условие сформулировано несколько неудачно. Чтобы понять, что имеется в виду, посмотрите формулировку задания 10 здесь, а затем задания 13 здесь.
    Пример:
    > (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++, если желаете, но в этом случае прошу внимательно следить за выделением-освобождением памяти при работе со списками).