Редактирование: Парадигмы программирования, 05 лекция (от 22 октября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 1: | Строка 1: | ||
* '''Аудиозапись:''' http://esyr.org/lections/audio/paradigms_2009_winter/paradigms_09_10_22.ogg | * '''Аудиозапись:''' http://esyr.org/lections/audio/paradigms_2009_winter/paradigms_09_10_22.ogg | ||
- | Сегодня лектор хотел рассказать про континуации. Это, | + | Сегодня лектор хотел рассказать про континуации. Это, моэжет быть, не самое зубодробительное, что есть в схеме, но самое интересное. Самым зубодробительным может лектор назвать макросы, потому что он их так и не смог полностью понать. |
+ | Континуации вещь в принципе тоже нетривиальная, потому что вещь достаточно новая. В отличие от макросов, которые вроде ни уму, ни сердцу ничего не дают, с конт. наоборот: время потратил, но и когда понимаешь, что это такое ... | ||
- | Но | + | Но начёнм не с неё, сначла посмотрим, что можно дедать с помощью лексических замыканий в лиспе. Писать лектор будет на схеме. В частности |
- | * defun в лиспе --- define в схеме. Синтаксис: (defun f (...) ...) -> (define (f ...) ...). Кроме того, define может определять не только функции, но и вещи вроде | + | * defun в лиспе --- define в схеме. Синтаксис: (defun f (...) ...) -> (define (f ...) ...). Кроме того, define может определять не только функции, но и вещи вроде глоб. переменных. Сами по себе символы ничего не вмещают, для этого надо сказать (define x #f), после чего уже можно сказать (set! x 25). Не все реализ. поддерживают эту хитрость, но она есть. |
- | + | На самом деле, нам потребуется ещё пара вещей из схемы: | |
* (map ...) --- то же, что и mapcar в лиспе | * (map ...) --- то же, что и mapcar в лиспе | ||
- | * (for_each fun (...)) --- вызывает функцию ради побочного эффекта. Не возвращает ничего. | + | * (for_each fun (...)) --- она просто вызывает функцию ради побочного эффекта. Не возвращает ничего. |
- | Свойства | + | Свойства лекс. замыканий одинаковы что в схеме, что в лиспе (искл. явл только elisp имени столлмана). |
(define funpair | (define funpair | ||
Строка 22: | Строка 23: | ||
) | ) | ||
- | + | В рез-те вып. этого дела будет нечто хитрое: точечная пара, у которой первый и второй элемент будут функциями. Первая функция — resey, вернуть значение переменной в 0. | |
- | Что в результате получилось: с funpair | + | Что в результате получилось: с funpair свзяана точечная пара, в car лежит (lambda () (set! n 0)), в cdr — (lambda () (set! n (+ n 1)) n). Теперь лектор берёт интерпретатор, скармливает это и начинает экспериментировать (две скобки потому, что нужно вызывать): |
> ((cdr funpair)) | > ((cdr funpair)) | ||
Строка 33: | Строка 34: | ||
3 | 3 | ||
- | И | + | И так далее. |
Что это показывает: что лексический контекст (сост. из одной переменной и её значения) не копируется, а сохраняется и остаётся связанным. | Что это показывает: что лексический контекст (сост. из одной переменной и её значения) не копируется, а сохраняется и остаётся связанным. | ||
Строка 41: | Строка 42: | ||
1 | 1 | ||
- | Получился как будто бы объект с двумя методами. Часто | + | Получился как будто бы объект с двумя методами. Часто моджет такая штука понадобиться --- часто. Это секвенсер. |
- | Это некий фокус, | + | Это некий фокус, позв. понять, что такое лекс. контекст. |
- | Обратите внимание, что обе функции связаны с | + | Обратите внимание, что обе функции связаны с лекс. контекстом, потому что они создавались в нём. |
- | + | А теперь к теме. Что такое континуация? Это последовательность действий, которые осталось выполнить до завершения вычислений. Вот, у нас есть какие-то вычисления. Наверняка, у нас есть какая-то головная функция (в C main, например). Собственно, всё выч. программы можно представлять как: что осталось сделать до завершения программы. Когда мы в начале выполнения, то нам нужно вызвать эту функцию. после того, когда вызвали, мы вошли в её тело. Что осталось? Осталось вычислить первую форму, вторую, и так до конца. Дальше, допустим, первая форма головной функции это что-нибудь такое: | |
(set! x (+ 1 (* 3 5))) (...) ... | (set! x (+ 1 (* 3 5))) (...) ... | ||
- | Что ост. вычислить на след. шаге? Осталось вычислить (+ 1 (* 3 5)), присвоить значений x, и | + | Что ост. вычислить на след. шаге? Осталось вычислить (+ 1 (* 3 5)), присвоить значений x, и высчисл. след. формы. Дальше мы вошли внутрь (+ 1 (* 3 5)). Что осталось вычислить: (* 3 5), прибавить единицу, присвоить иксу, и всё остальное. Далее: Взять 3, взять 5, умножить, результат прибавить единице, результат присвоить икс, вычилстиь дальше. Дальше у нас элементпрное действие, мы его делаем, получаем 15. Дальше --- тоже элементарное действие, получаем результат 16. Далее, загнать 16 в x. Далее --- вычисл. след. формы. |
+ | То есть, при выч. мы желаем элемент. шаги, нам оставался на один шаг меньше, хотя континуация могла становиться больше. | ||
- | + | То есть, ещё раз, что такое континуация: это набор всех действ., которые ост. сделать до конца вычислений. | |
+ | scheme --- один из немногих языков, где континуация явл. объектом первого порядка, то есть с ней можно работать. | ||
- | В схеме есть функция: call-with-current-continuation. Понятно, что программисты люди ленивые, такое они не пишут, поэтому обычно используют call/cc. Как правило, компиляторы и интерпретаторы схемы поддерживают оба имени, но обычно используют второе. | ||
- | call/cc | + | В схеме есть функция, хитрая: call-with-current-continuation. Понятно, что программисты люди ленивые, такое они не пишут, поэтому обычно используют call/cc. Как правило, компиляторы и интерпретаторы схемы поддерживают оба имени, но обычно используют второе. |
- | Что делает call/cc: он вызывает функцию, подав ей в | + | |
+ | Что эта штука делает: call/cc это штука от одного арг. Этим арг. должна быть функция. Причём, эта функция тоже должна быть функцией от одного аргумента. Что делает call/cc: он вызывает функцию, подав ей в кач. единст. аргумента вот этот объект континуации. | ||
(call/cc f) | (call/cc f) | ||
- | Так вот, вызвана будет f | + | Так вот, вызвана будет f, а объектом дадут континуацию. Понятно, что обычно здесь исп. лямбду, но это необязательно. |
- | Как это дело вычисляется: если call/cc | + | Как это дело вычисляется: если call/cc выз. f, а f что-то возвращает ( если успеет), то вся эта форма возвр. то, что вернула f. Здесь ничего сверхъест. нет. Но, есть один момент: внутри функции f доступен этот объект, что с ним можно сделать? Его можно вызвать как функцию одного аргумента, и этот вызов приведёт к тому, что форма эта немедленно вернёт управление ровно в том месте, которое было, и в кач. значения вернёт то, что подали континуации как функции одного аргумента, причём это можно сделать после того, как она вернула управление. |
Достаточно простая иллюстрация: | Достаточно простая иллюстрация: | ||
Строка 83: | Строка 86: | ||
Как это реализуется --- по-разному. Есть, например, реализация для C, которая сделана путём сохранения стека. | Как это реализуется --- по-разному. Есть, например, реализация для C, которая сделана путём сохранения стека. | ||
- | Вначале лекции | + | Вначале лекции летор скзаал, что континуации явл. обобщением многих вещей. Например: |
* Досрочное окончание многих функций. (аналог brake/return в C) | * Досрочное окончание многих функций. (аналог brake/return в C) | ||
Вообще, goto не так и плох, его вполне можно использовать в двух случаях. | Вообще, goto не так и плох, его вполне можно использовать в двух случаях. | ||
* Первый --- cleanup. Например, В начале забирается дин. ресурс, а потом хочется досрочно её завершить. Так вот, не надо дублировать освобождение, нужно сделать goto на cleanup: | * Первый --- cleanup. Например, В начале забирается дин. ресурс, а потом хочется досрочно её завершить. Так вот, не надо дублировать освобождение, нужно сделать goto на cleanup: | ||
- | * Второй — выход из | + | * Второй — выход из неск. вложенных циклов. Тут break не поможет. Обычно это делают посредством флага. Не надо так делать. Это второй и последний случай. |
- | Но в | + | Но в совр. языках случаев может быть меньше. В C++ есть деструкторы, в Ada/Java можно именовать for и прочее. |
- | call/cc является обобщением вариантов с | + | call/cc является обобщением вариантов с доср. выходом из конструкции. Пример: дан предикат от одного аргумента. Дан список из скольких-то элементов. Задача: из этого списка извлечь первый элемент, на котором предикат вернёт истину. Можно ли это сделать с помощью рекурсии? Конечно можно. |
(define (search wanted? lst) | (define (search wanted? lst) | ||
Строка 106: | Строка 109: | ||
Единственное что — значение глобальных переменных не сохраняется. | Единственное что — значение глобальных переменных не сохраняется. | ||
- | Можно так писать? Можно. Но обычно для просмотра | + | Можно так писать? Можно. Но обычно для просмотра вписков хочется исп. мапперы. Можно ли из тут исп.? Можно, но будет не меньше по длине |
(define (search wanted? lst) | (define (search wanted? lst) | ||
Строка 120: | Строка 123: | ||
) | ) | ||
- | Короче ли это? Трудно сказать, строчек больше, но | + | Короче ли это? Трудно сказать, строчек больше, но бук примерно столько же. Понятнее ли? Вопрос. Рекурсия привычнее, но на С мы бы написали примерно то же самое: |
- | int search(int (*pred)(int), int *arr, int n) | + | int search(int (* pred)(int), int * arr, int n) |
{ | { | ||
int i; | int i; | ||
Строка 137: | Строка 140: | ||
} | } | ||
- | Таким | + | Таким обр. мы с помощью call/cc эмулируем выход из циклов. Но возм. на этом не заканчиваются. Что ещё можно: можно заст. прекр. функцию, которая лексически в другом месте. Давайте переделаем функцию search, если у нас не предикат есть, а некая функция. Теперь применим другую парадигму, callback. Мы выбор элемент будем выбирать с помощью функции, которой если элемент понравился, то она будет делать колбэк. |
(define (treat elem callback) | (define (treat elem callback) | ||
Строка 156: | Строка 159: | ||
Делает то же самое, один момент: функция, которая завершает просмотр, находится в другом месте. Называется это "нелокальный выход". | Делает то же самое, один момент: функция, которая завершает просмотр, находится в другом месте. Называется это "нелокальный выход". | ||
- | В явном виде такие вещи есть в языках типа лиспа. В лиспе для этого есть спец. формы, | + | В явном виде такие вещи есть в языках типа лиспа. В лиспе для этого есть для этого спец. формы, мех. континуаций --- строго более общий, чем мех. нел. выхода. |
А вот есть такая вещь, как исключения, они есть во многих языках. Потому, что не смотря на то, что они криво реализованы, сильно облегчают жизнь. | А вот есть такая вещь, как исключения, они есть во многих языках. Потому, что не смотря на то, что они криво реализованы, сильно облегчают жизнь. | ||
- | Ошибочно полагать, что парадигма | + | Ошибочно полагать, что парадигма обр. искл. имеет отношение к ООП. Почему так полагают? Потому что впервые с ним сталк. в С++, но сам мех. не имеет отн. к ООП. Что такое ООП: это когда среда исп. прилож. сост. из объектов, они имеют внутр. сост, могут принимать сообщ., как-то менять внутр. сост., обр. к другим объектам, отвечать на сообщ. Как это соотн. к С++, То, что в теории ООП наз. передачей сообщения, в С++ есть вызов методы. И при чём тут обработка искл.? Ни при чём? К какой же парадигме тогджа они ближе? К функциональной. Что есть искл., как не способ альт. завершения фнукции? Если это альт. способ. возвр. из ф-ции, то думать надо не об объектах, а о функциях, а это точно не из ООП понятие. Поэтому, искл. это парадигма, не имеющ. никакого отношения к ООП. |
- | Лектор напомнит, что такое | + | Лектор напомнит, что такое искл: |
В качестве обозначение искл. ситуации можно исп. объект почти любого типа, в том числе объект типа Class. | В качестве обозначение искл. ситуации можно исп. объект почти любого типа, в том числе объект типа Class. | ||
- | Для | + | Для возбужд. искл. исп. throw ... . Объекты, не допускающие копирования, нельзя исп.. Как поймать исключение? |
- | Почему из курса | + | Почему из курса арзитектура эвм надо знать, что такое стековый фрейм? Потому что такие вещи, как искл. и хвостовая рекурсия, проще объяснять. |
Есть функция из стандартного C++ runtime, __trow_unwind, которая линкуется при исп. искл. Эта функция берёт стековый фрейм и начинает его разматывать, ища обработчик. Если нет, то вызывает деструкторы и схлопывает его. Далее берёт стековый фрейм и так далее. Если дойдёт до вершины стека, то программа завершится. | Есть функция из стандартного C++ runtime, __trow_unwind, которая линкуется при исп. искл. Эта функция берёт стековый фрейм и начинает его разматывать, ища обработчик. Если нет, то вызывает деструкторы и схлопывает его. Далее берёт стековый фрейм и так далее. Если дойдёт до вершины стека, то программа завершится. | ||
- | Можно сымитировать | + | Можно сымитировать искл. в языках, в окторых нет искл. Например, в С. Там есть setjmp/longjmp. |
int setjmp(jmp_buf env); | int setjmp(jmp_buf env); | ||
- | Принимает setjmp на вход буфер, она туда | + | Принимает setjmp на вход буфер, она туда запис. некуюб инф., которая пригодится для возвр. туда потом. На самом деле, она туда запис. Текущий указатель стека. Возвр. при первом вызове 0. |
Когда делается long_jmp(jmp_buf, int), то в след. раз вернёт не 0, а то, что передано. | Когда делается long_jmp(jmp_buf, int), то в след. раз вернёт не 0, а то, что передано. | ||
- | + | Единст. ограничение: стековый фрейм должен существовать. Если его уже нет, то "full chaos guaranteered". | |
- | Эмуляция | + | Эмуляция искл. с call/cc: |
(let ((ret (call/cc ..) ... | (let ((ret (call/cc ..) ... | ||
- | Это всё хорошо, но это всё, что | + | Это всё хорошо, но это всё, что нелок. выходы, что искл --- ситуация, когда мы глубже в стеке. |
- | Гораздо интереснее, когда оно уже отработало, стековый фрейм прибился, но call/cc мощнее тем, что он | + | Гораздо интереснее, когда оно уже отработало, стековый фрейм прибился, но call/cc мощнее тем, что он позв. вернуться и в этой ситуации. |
Что можно с помощью этого сделать: например, сопрограммы (жутко медленно, но красиво). Что для этого нужно сделать: | Что можно с помощью этого сделать: например, сопрограммы (жутко медленно, но красиво). Что для этого нужно сделать: | ||
Строка 213: | Строка 216: | ||
) | ) | ||
- | Есть такой стиль, как continuation past, стиль | + | Есть такой стиль, как continuation past, стиль прогр. с передачей континуаций. Один из языков, который это вроде поддерживает --- Io. Идея такая, что одним из арг. передаются континуации. Стека там нет, там вообще нет возврата. Любопытная штука, бывает и такое. |
+ | |||
+ | След. лекция посв. лямбда-исчислению. | ||
+ | Есть книжка Фил, Харрисон, функц. программирование, там оно изложено. | ||
== Иллюстрации == | == Иллюстрации == | ||
- | <gallery perrow=" | + | <gallery perrow="5" widths="200"> |
Image:paradigm_091022_01.jpg|funpair — пример использования лексического замыкания. | Image:paradigm_091022_01.jpg|funpair — пример использования лексического замыкания. | ||
Image:paradigm_091022_02.jpg|Использование funpair. | Image:paradigm_091022_02.jpg|Использование funpair. |