Назад

Парадигмы программирования

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

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

Место и время: среда, 19:20, ауд. 309 СК НГУ.

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

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

Результаты: посещаемость, список сданных задач.

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

N.B.: обновлено задание 9.
  1. Списочные структуры. Реализовать функции LENGTH1, LIST1, APPEND1, REVERSE1, определённые следующим образом:
    • функция LENGTH1 возвращает длину списка:
      > (LENGTH1 '(A B C))
      3
    • функция LIST1 объединяет два аргумента в список:
      > (LIST1 'A 'B)
      (A B)
    • функция APPEND1 объединяет два списка:
      > (APPEND1 '(A B) '(C D))
      (A B C D)
    • функция REVERSE1 «переворачивает» список:
      > (REVERSE1 '(A B C))
      (C B A)

  2. Предикаты сравнения. Объяснить разницу между предикатами сравнения 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).

  3. Ассоциативный список. Реализовать функцию ASSOC1, которая определяет, есть ли в данном списке точечных пар пара с первым элементом, равным данному атому, и возвращающую второй элемент этой пары, если такая пара есть, и NIL, если такой пары нет.
    Пример:
    > (ASSOC1 '((A . 1) (B . 2) (C . 3)) 'B)
    2
    > (ASSOC1 '((A . 1) (B . 2) (C . 3)) 'D)
    NIL
  4. Список атомов. По данному многоуровневому списку сформировать список входящих в него атомов в том порядке, в котором они встречаются в этом S-выражении.
    Пример:
    > (ATOMS '((A B) C NIL (D (E F G))))
    (A B C NIL D E F G)
  5. Сортировка. Дан список из нескольких чисел. Реализовать функцию сортировки этого списка по возрастанию любым способом.
    Пример:
    > (SORT1 '(1 5 2 4 3))
    (1 2 3 4 5)
  6. Слияние. Реализовать функцию, «сливающую» два списка чисел, отсортированных по возрастанию, в один список, отсортированный по возрастанию.
    Пример:
    > (MERGE1 '(1 3 5) '(2 4))
    (1 2 3 4 5)
  7. Суперпозиция 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))
  8. Перестановки. Вывести все возможные перестановки элементов данного списка в произвольном порядке (по одному разу каждую). В приведённом ниже примере перестановки выведены на экран, а NIL — результат функции. Ваша функция может работать иначе.
    Пример:
    > (PERMUT '(1 2 3))
    (1 2 3)
    (1 3 2)
    (2 1 3)
    (2 3 1)
    (3 1 2)
    (3 2 1)
    NIL
  9. Индивидуальные задания (4 штуки) будут выданы на занятиях после сдачи всех предыдущих заданий. Последние два задания на тему «замыкания» описаны в отдельном файле (PDF).