Назад

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

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

В 1 семестре 2008-2009 учебного года на практических занятих по обязательному спецкурсу «Парадигмы программирования» изучался язык LISP.

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

Рекомендуемая литература: Э. Хювёнен, Й. Сеппянен «Мир Лиспа».
То же самое в сети НГУ: раз, два.
Курсы лекций Л.В.Городней на intuit.ru: Функциональное программирование, Парадигмы программирования, Введение в программирование на Лиспе.

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

# Фамилия, имя  1   2   3   4   5   6   7   8   9   10   11   12   13   14   15  Итого
Оценка за практику
1
Афонина Алиса
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
2
Батурин Алексей
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
3
Должикова Анастасия
+
+
+
+
+
+
+
+
+
+
+
+
+
 
+
14
хорошо
4
Зайков Александр
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
5
Исаев Валерий
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
6
Кременная Ольга
+
+
+
+
+
+
+
+
+
+
+
+
 
 
 
12
удовл
7
Кузькоков Владислав
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
8
Ломакин Сергей
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
9
Лысяк Александр
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
10
Носова Дарья
+
+
+
+
+
+
+
+
+
+
+
+
 
 
 
12
удовл
11
Полушкин Михаил
+
+
+
+
+
+
+
+
+
+
+
+
+
+
 
14
хорошо
12
Сорокин Роман
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
13
Тищенко Николай
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
14
Часовщикова Анна
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
15
отлично
Гистограмма

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

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

  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. Условия задач находятся в отдельном файле, распределение задач — здесь.