Парадигмы программирования, 04 лекция (от 15 октября)

Материал из eSyr's wiki.

• Аудиозапись: http://esyr.org/lections/audio/paradigms_2009_winter/paradigms_09_10_15.ogg

Как мы заметили в прошлый раз, ф-ция является объектом данных.

Есть две вещи:

• Применить функцию к данным.
  • (apply) — первый арг — ф-ция, второй — список аргументов, который надо применять. Например, (apply #'+ '(1 2 3)) => 6
  • (funcall) — параметров не 2, а сколько угодно (вариадическая функция): (apply #'+ 1 2 3)

Задача: дана матрица. Каждая строка предст. в виде списка элементов, вся матрица — в виде списка строк. Априори считаем, что матрица квадратная, задача --- транспонировать.

(apply #'mapcar (cons #'list matrix))

Что произошло: мы применяем mapcar к (#'list (123) (456) (789)). Что получается: применяет list к первым, ко вторым, к третьим, что и требовалось: ((1 4 7) (2 5 8) (3 6 9)).

Есть такая вещь, как редукция списков. На самом деле, она основана на единственной функции (в CL, в других диалектах могут быть варианты). Что такое редукция: дана последовательность и дана функция от двух аргументов. Тогда мы можем определить левую и правую редукцию по функции.

• Левая редукция: f(f(f(...f(s, a_1), ..., a_n-2), a_n-1, a_n), где s — некая затравка. Иначе говоря, получается что-то такое: s_1 = f(s, a_1), s_2 = f(s_1, a_2), ... s_n = f(s_n-1, a_n), s_n — результат.
• Правая редукция: f(a_1, f(a_2, ... f(a_n, s)...)

Что можно с помощью редукций делать: пусть, правая редукция называется rreduce.

(rreduce #'+ '(1 2 3) 0)

Это просто сумма списка.

(rreduce #'cons '(1 2 3) nil)

Получится копия списка. Вообще говоря, это полезно иногда, поскольку у нас в lisp'е есть разрушающая функция.

• rplaca — Замена первого элемента в точечной паре
• rplacd — Замена второго элемента в точечной паре

Левая редукция называется lreduce. Тогда:

(lreduce #'cons '(1 2 3) nil)

Вот здесь мы его перевернём, причём странно: (((nil. 1) 2) 3). Перевернем список :

(lreduce #'(lambda (x y) (cons y x)) '(1 2 3) nil)

Получается список (3 2 1).Найдем максимум:

(lreduce #'(lambda (x y) (if (< x y) y x)) (cdr lst) (car lst))

Одна такая функция, одна идея может создать целую парадигму. Не все программисты этим пользуются, но те, кто пользуются, вытворяют очень многое. Те, кто пользуются, могут получать некий бонус, не выписывая рекурсию в некоторых случаях. Понятно, что сама редукция внутри это рекурсия, но тем не менее. Покажем, как они описаны:

(defun lreduce (func list init)
  (cond
    ((null list) init)
    (t (let ((next (funcall fun init (car list))))
            (lreduce fun (cdr list) next)
    ))
  )
)

Здесь лектор использует специальную форму let которая исп. для объявления переменных. let позволяет дать локальные имена некоторым величинам, чтобы не вычислять их несколько раз и не законфликтовать с именем за пределами фрагмента. Как это делается:

(let (a
      (b (+ x 28))
     )
     ( ... )
     ...
)

Первый аргумент - список переменных или списков из двух элементов --- имени перем. и нач. знач. Потом список форм. Результат let — результат последней формы.

Можно обойтись без let, но было бы громоздко.

Как устроена rreduce:

(defun lreduce (func list init)
  (cond
    ((null list) init)
    (t (funcall fun
                (car list)
                (rreduce fun (cdr list) init)
    ))
  )
)

Тоже, в принципе, очевидно. Но и у той, и у другой проблема --- накапливается стек. Это, конечно, можно обойти используя накапливающий параметр. Желающие могут переписать данные функции с хвостовым параметром.

Интересный вариант: отсортировать список с использованием reduce. Здесь потребуется вспомогательная функция, которая вставляет элемент в упорядоченный список, не нарушая порядка. Понятно, что если такая функция есть, то с помощью редукции сортируется список.

Вспомогательная функция:

(defun ins_to_list (i list)
  (cond ((nul list) (cons i ()))
        ((< i (car list)) (cons i list))
        (t (cons (car list) (ins_to_list i (cdr list))))
  )
)

Как теперь будет выглядеть сортировка списка:

(reduce #"ins_to_list '(...) nil)

Результатом на каждом шаге является отсортированный список. Пример, конечно, отвратительный, из-за сложности.

Здесь мы видим пример функции высшего порядка. Есть и некоторые недостатки у этого момента, причём поняли это отнюдь не сразу. Обнаружили проблему только в середине 60-х (создали в 58, писать начали в начале 60-х). Проблема называется "funarg-проблема", проблема функционального аргумента. Возникает она, если в теле функции есть свободные переменные. Рассмотрим пример. Напишем такую функцию, которая создает функцию "увеличитель на n":

(defun make_adder (n) #'(lambda (x) (+x n)))

(setq a3 (make_adder 3))

Обратите, что значением символа стала функция, поэтому вот так: (a3 2) работать не будет. Но никто не запрещает исп. funcall:

(funcall a3 1)

Результатом этого будет 4. А теперь какая штука получается: в какой-то момент что-то происходит и есть переменная n (кто-то объявил её). И вызвал (funcall a3 7)

(... (setq n 15) (funcall a3 7))

Результатом будет 22. В современных диалектах будет 10. К современным не относится elisp, на котором написан emacs.

Как это работает: входим в контекст, даем новое значение, работаем, возвращаем старое. И здесь проблема: получается результат совсем не тот, который ожидали. В современных версиях лиспа локализация делается иначе: создаётся лексический контекст. Его можно воспроизвести как таблицу "имя-значение". В данном случае оно будет состоять из одной строки "n=3". В случае использования лексический контекст перекрывает динамический. Почему эта штука наз. "лексический контекст"? Потому, что она действует ровно в тех границах, где действ. соответствующая лексема. Но самое интересное не это, просто так оно не работает, поскольку кроме ничего потери произв. не даёт. Самое интересное в том, что лексический контекст может существовать дольше, чем. выполняется соотв. область программы. Созданная функция включает в себя также лексический контекст. Вся эта штука вместе называется замыканием. Совр. версии lisp не теряют эффективность на этом. Там очень интересные способы обращения к этим таблицам. Кроме того, совр. версии лиспа комплируемые, там исчезли имена, добавились указатели. Благодаря тому, что существует не только имя функции, но и контекст, мы получаем то значение, которое ожидаем, 10, не 22. Это наз. лексическое связывание. Интересно, что в CL сохранилось как лекс., так и динамич. связывание.

Обычно, глобальную переменную делают динамически связываемой. Что касается языка scheme, то там всё связывается лексически, дин. связывания нет.

В принципе, на лиспе можно писать, не зная этого. Но интересно тут вот что: например, у нач. программистов на языке лисп возникает вопрос "почему всё так неудобно". Есть один убойный аргумент: "почему я не могу выч. сам?". Нельзя, потому что не сможешь, контекст другой. Например, при вызове (f x) x лексически связана. И выч. нельзя, потому что контекст функции не передаётся. А собственный контекст обычно пустой. Может быть непустой, но точно не тот, который будет в месте вызова.

Другой вопрос, что есть макросы, это хитрая штука. Макрос в CL не вычисляет свои аргументы Макрос не выч. свои арг. Дальше происходит вычисление тела макроса, но оно происходит с телемакроса, а то, что получится, вычисляется в теле вызвавшего. Зачем это надо это отдельный вопрос. В принципе, это мощная штука, но в контексте спецкурса это не очень нужно.

Рассм. обратную ситуацию Здесь мы функцию возвращаем в качестве возвр. значения. Рассм. случай, когда возникает funarg-проблема, но в другую сторону. Лектор попытается написать сейчас свой mapcar (это будет усеченный mapcar, который имеет только два аргумента, соотв., функция одного аргумента).

(defun mapcar1 (fn lst)
  (cond ((null lst) nil)
        (t (cons (funcall fn (car lst)) (mapcar1 fn (cdr lst))))
  )
)

А теперь лектор напишет некую тестовую функцию:

(defun test (lst) (mapcar1 #'(lambda (x) (cons x lst)) '(a b c)))

А вопрос, понятно, в lst. по идее, в результате должен получиться список из трёх списков. Ожидаем мы, что получится ((a) (b) (c)). Но если lst законфликтует, то есть, если здесь делать дин. связывание, получится совсем не то: ((a a b c) (b b c) (c c)). Где-то на этом и была осознана funarg-проблема.

setq — макрос. Хитрая штука, которая как-то хитро вычисляется.

(setq var value)

Существует функция set, которая вычисляет оба своих аргумента. Вычисляет первый аргумент, второй, пркдп., что значением первого является символ, и присвавивает второе. Оказалось, что эта функция совершенно непригодна для модификации переменных, только для глобальных значений. Оказывается, что (set 'x 25) != (setq x 25). Это верно только для глобальных знач. Поскольку set недоступен контекст вызвавшего.

Время есть, поэтому поговорим о scheme.

В принципе, лисп как лисп. Те же скобки, s-выр., правда, сходу на ур. s-выр. есть след. отличие: пустой список имеет только одно обозначение. никакой спец. роли атом nil не играет.

Есть некоторые нюансы.

Значением символа может быть функция, причём функция явлется значением символа. Это позволяет в списке вычислить все элементы списка. В обычном лиспе мы выч. все эл-ты кроме первого, а первый элемент хитрый, мы из него извлекаем функцию хитрым образом. В схеме не так. В схеме мы элементы тупо вычисляем. Это позв. убрать одного из монстриков: мы можем убрать lambda, не потому что у него такое значение, а потому что он lambda. В схеме с этим связан просто синтаксис. Это макрос, и выч. он по обычной схеме. То есть, когда мы пишем

(lambda (x y) (+ (* 2 x) y)

Значением этого явл. функция. Поэтому #' здесь больше нет.

В лиспе по традиции () --- ложь. В схеме для этого есть спецсимвол — #f. Всё, что не ложь — истина, но есть спец. обозначение — #t. И все предикаты возвр. либо одно, либо второе. То есть, это в схеме спец. выделенные атомы для обозн. лжи и истины.

Функции в схеме наз. по-другому: setq -> set!. А предикаты в схеме с вопр. знаком:

• eq -> eq?
• eql -> eql?
• equal -> equal?

В принципе, различия косметические. Единственное отличие --- выч. список. Хотя, всё равно приходится первый элемент выч. немного специально, поскольку это может быть спец синтаксис. Например, set!, cond, и прежде чем выч. первый эл. формы, нужно посм., не обозн. первый элемент что-то хитрое.

Есть ещё один момент. В схеме есть такая вещь, как continuation, т. н. продолжение. Понятие немного трудное для понимания. Лектор скажет зарание, что этот самый cont. оказ. обозением таких вещей, как обр. исключений. Обобщением таких вещей, как нелокальный выход. except, break, long jump --- это всё частные случаи.

[править] Иллюстрации

apply, funcall	Объяснение lreduce, rreduce	Применение lreduce, rreduce	Применение lreduce, rreduce
Определение lreduce	Определение rreduce	Определение ins_to_list	funarg-проблема
funarg-проблема	funarg-проблема	funarg-проблема: mapcar1	funarg-проблема: mapcar1
Scheme