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

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

Версия 13:52, 16 октября 2009

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

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

• Применить функцию к данным.
  • (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)).

В принципе, на лиспе так делается не атк часто, по крайней мере, функция list в таких обстоятельстав используется часто.

Есть такая вещь, как редукция списков. На самом деле, она основана на единственной функции (в 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 — если бы он всето next вставил значение, получилось бы слишком громоздко. Так бы можно было бы без 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