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

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

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

Время и место: четверг, 17:45, ауд. 309 СК НГУ.

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

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

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

# Фамилия, имя  1   2   3   4   5   6   7   8   9   10   11   12   13   14   15  Итого
Оценка за практику
1
Артиков Артур
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
2
Артиков Тимур
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
3
Архинчеева Светлана
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
4
Бондарев Семён
+
+
+
+
+
+
+
+
+
+
 
 
 
 
 
10
 
5
Боровский Виктор
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
6
Васькин Юрий
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
7
Грехов Герман
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
8
Заречнева Юлия
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
хорошо
9
Зеленчук Андрей
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
10
Золотухин Тимур
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
11
Зятьков Николай
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
12
Клименко Александр
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
13
Колбин Дмитрий
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
14
Комышев Евгений
+
+
+
+
+
+
+
+
+
+
+
+
+
 
 
13
удовл
15
Кузнецов Илья
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
16
Кузьмин Павел
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
17
Мартьянов Андрей
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
18
Матвиенко Сергей
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
19
Никитин Виктор
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
20
Сердюк Константин
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
21
Скуридина Валентина
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
22
Суслопаров Денис
+
+
+
+
+
+
+
+
+
+
+
+
+
 
 
13
удовл
23
Татаринцев Павел
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
24
Тейтельбаум Дмитрий
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
25
Хлебников Сергей
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
26
Царапкин Михаил
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично

Гистограмма

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

  1. Списочные структуры. Реализовать функцию LENGTH1, которая возвращает длину списка:
    > (LENGTH1 '(A B C))
    3
     Функция с именем LENGTH является стандартной, поэтому ваша функция может называться LENGTH1 или как-то иначе. То же самое верно для следующих заданий, в которых имя функции содержит единицу.

  2. Списочные структуры. Реализовать функцию LIST1, которая объединяет два аргумента в список:
    > (LIST1 'A 'B)
    (A B)

  3. Списочные структуры. Реализовать функцию APPEND1, которая объединяет два списка:
    > (APPEND1 '(A B) '(C D))
    (A B C D)

  4. Списочные структуры. Реализовать функцию REVERSE1, которая «переворачивает» список:
    > (REVERSE1 '(A B C))
    (C B A)

  5. Предикаты сравнения. Объяснить разницу между предикатами сравнения EQ, EQL, =, EQUAL, EQUALP. Привести примеры S-выражений A и B таких, что
    1. истинно (EQ A B);
    2. истинно (EQL A B), но ложно (EQ A B);
    3. истинно (= A B), но ложно (EQL A B);
    4. истинно (EQUAL A B), но ложно (EQL A B);
    5. истинно (EQUALP A B), но ложно (EQUAL A B);
    6. ложно (EQUALP A B).

  6. Ассоциативный список. Реализовать функцию ASSOC1, которая определяет, есть ли в данном списке точечных пар пара с первым элементом, равным данному атому, и возвращающую второй элемент этой пары, если такая пара есть, и NIL, если такой пары нет.
    Пример:
    > (ASSOC1 '((A . 1) (B . 2) (C . 3)) 'B)
    2
    > (ASSOC1 '((A . 1) (B . 2) (C . 3)) 'D)
    NIL
  7. Список атомов. По данному многоуровневому списку сформировать список входящих в него атомов в том порядке, в котором они встречаются в этом S-выражении.
    Пример:
    > (ATOMS '((A B) C NIL (D (E F G))))
    (A B C NIL D E F G)
  8. Слияние. Реализовать функцию, «сливающую» два списка чисел, отсортированных по возрастанию, в один список, отсортированный по возрастанию.
    Пример:
    > (MERGE1 '(1 3 5) '(2 4))
    (1 2 3 4 5)
  9. Сортировка. Дан список из нескольких чисел. Реализовать функцию сортировки этого списка по возрастанию любым способом.
    Пример:
    > (SORT1 '(1 5 2 4 3))
    (1 2 3 4 5)
  10. Суперпозиция CAR и CDR. Реализовать функцию MAKE-CAR-CDR, которая принимает три аргумента:
    • S — произвольное S-выражение
    • X — произвольный атом
    • Q — произвольный атом
    и возвращает S-выражение из атомов CAR, CDR и Q, такое, что если бы значением атома Q было S, то результатом вычисления этого выражения был бы атом X. Проще говоря, функция должна показывать, как при помощи суперпозиции вызовов CAR и CDR «выделить» X из выражения S, обозначенного как Q.
    Пример:
    > (MAKE-CAR-CDR '(A X B) 'X 'Q)
    (CAR (CDR Q))
  11. Перестановки. Вывести все возможные перестановки элементов данного списка в произвольном порядке (по одному разу каждую). В приведённом ниже примере функция возвращает список из перестановок. Ваша функция может работать иначе (например, выводить перестановки на экран).
    Пример:
    > (PERMUT '(1 2 3))
    ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
  12. Замыкания — 1. Теория по этой теме находится в отдельном файле. Реализуйте генератор простых чисел или чисел Фибоначчи при помощи замыкания.
  13. Замыкания — 2. Реализуйте при помощи замыкания конечный автомат или машину Тьюринга. В результате должна получиться функция-замыкание, сохраняющая состояние (соответственно, автомата или машины) и выполняющая переход к следующему состоянию в зависимости от аргумента очередного вызова функции.

  14. Индивидуальное задание — 1.
  15. Индивидуальное задание — 2. Условия задач находятся в отдельном файле, распределение задач — здесь.