Редактирование: Парадигмы программирования, 05 лекция (от 22 октября)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 3: | Строка 3: | ||
Сегодня лектор хотел рассказать про континуации. Это, может быть, не самое зубодробительное, что есть в схеме, но самое интересное. Самым зубодробительным может лектор назвать макросы, потому что он их так и не смог полностью понять. | Сегодня лектор хотел рассказать про континуации. Это, может быть, не самое зубодробительное, что есть в схеме, но самое интересное. Самым зубодробительным может лектор назвать макросы, потому что он их так и не смог полностью понять. | ||
+ | Континуации вещь в принципе тоже нетривиальная, потому что вещь достаточно новая. В отличие от макросов, которые вроде ни уму, ни сердцу ничего не дают, с конт. наоборот: время потратил, но и когда понимаешь, что это такое ... | ||
- | Но начнём не с | + | Но начнём не с неё, сначала посмотрим, что можно делать с помощью лексических замыканий в лиспе. Писать лектор будет на схеме. В частности |
- | * 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 связана точечная пара, в car лежит (lambda () (set! n 0)), в cdr — (lambda () (set! n (+ n 1)) n). Теперь лектор берёт интерпретатор, скармливает это и начинает экспериментировать (две скобки потому, что нужно вызывать): | Что в результате получилось: с funpair связана точечная пара, в car лежит (lambda () (set! n 0)), в cdr — (lambda () (set! n (+ n 1)) n). Теперь лектор берёт интерпретатор, скармливает это и начинает экспериментировать (две скобки потому, что нужно вызывать): | ||
Строка 33: | Строка 34: | ||
3 | 3 | ||
- | И | + | И так далее. |
Что это показывает: что лексический контекст (сост. из одной переменной и её значения) не копируется, а сохраняется и остаётся связанным. | Что это показывает: что лексический контекст (сост. из одной переменной и её значения) не копируется, а сохраняется и остаётся связанным. | ||
Строка 41: | Строка 42: | ||
1 | 1 | ||
- | Получился как будто бы объект с двумя методами. Часто | + | Получился как будто бы объект с двумя методами. Часто может такая штука понадобиться --- часто. Это секвенсер. |
- | Это некий фокус, | + | Это некий фокус, позв. понять, что такое лекс. контекст. |
- | Обратите внимание, что обе функции связаны с | + | Обратите внимание, что обе функции связаны с лекс. контекстом, потому что они создавались в нём. |
- | + | А теперь к теме. Что такое континуация? Это последовательность действий, которые осталось выполнить до завершения вычислений. Вот, у нас есть какие-то вычисления. Наверняка, у нас есть какая-то головная функция (в C main, например). Собственно, всё выч. программы можно представлять как: что осталось сделать до завершения программы. Когда мы в начале выполнения, то нам нужно вызвать эту функцию. после того, когда вызвали, мы вошли в её тело. Что осталось? Осталось вычислить первую форму, вторую, и так до конца. Дальше, допустим, первая форма головной функции это что-нибудь такое: | |
(set! x (+ 1 (* 3 5))) (...) ... | (set! x (+ 1 (* 3 5))) (...) ... | ||
Строка 53: | Строка 54: | ||
Что ост. вычислить на след. шаге? Осталось вычислить (+ 1 (* 3 5)), присвоить значений x, и вычисление след. формы. Дальше мы вошли внутрь (+ 1 (* 3 5)). Что осталось вычислить: (* 3 5), прибавить единицу, присвоить иксу, и всё остальное. Далее: Взять 3, взять 5, умножить, результат прибавить единице, результат присвоить икс, вычислить дальше. Дальше у нас элементарное действие, мы его делаем, получаем 15. Дальше --- тоже элементарное действие, получаем результат 16. Далее, загнать 16 в 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) | ||
Строка 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 эмулируем выход из циклов. Но | + | Таким образом мы с помощью call/cc эмулируем выход из циклов. Но возм. на этом не заканчиваются. Что ещё можно: можно заст. прекр. функцию, которая лексически в другом месте. Давайте переделаем функцию search, если у нас не предикат есть, а некая функция. Теперь применим другую парадигму, callback. Мы выбор элемент будем выбирать с помощью функции, которой если элемент понравился, то она будет делать колбэк. |
(define (treat elem callback) | (define (treat elem callback) | ||
Строка 156: | Строка 159: | ||
Делает то же самое, один момент: функция, которая завершает просмотр, находится в другом месте. Называется это "нелокальный выход". | Делает то же самое, один момент: функция, которая завершает просмотр, находится в другом месте. Называется это "нелокальный выход". | ||
- | В явном виде такие вещи есть в языках типа лиспа. В лиспе для этого есть спец. формы, | + | В явном виде такие вещи есть в языках типа лиспа. В лиспе для этого есть для этого спец. формы, мех. континуаций --- строго более общий, чем механизм нел. выхода. |
А вот есть такая вещь, как исключения, они есть во многих языках. Потому, что не смотря на то, что они криво реализованы, сильно облегчают жизнь. | А вот есть такая вещь, как исключения, они есть во многих языках. Потому, что не смотря на то, что они криво реализованы, сильно облегчают жизнь. | ||
- | Ошибочно полагать, что парадигма образования исключений имеет отношение к ООП. Почему так полагают? Потому что впервые с ним столкнулись в С++, но сам | + | Ошибочно полагать, что парадигма образования исключений имеет отношение к ООП. Почему так полагают? Потому что впервые с ним столкнулись в С++, но сам мех. не имеет отношения к ООП. Что такое ООП: это когда среда использует приложения состоящие из объектов, они имеют внутр. состояния, могут принимать сообщения, как-то менять внутр. сост., обр. к другим объектам, отвечать на сообщ. Как это соотн. к С++, То, что в теории ООП наз. передачей сообщения, в С++ есть вызов метода. И при чём тут обработка искл.? Ни при чём? К какой же парадигме тогда они ближе? К функциональной. Что есть исключение, как не способ альт. завершения функции? Если это альт. способ. возвр. из функции, то думать надо не об объектах, а о функциях, а это точно не из ООП понятие. Поэтому, исключения- это парадигма, не имеющая никакого отношения к ООП. |
Лектор напомнит, что такое исключение: | Лектор напомнит, что такое исключение: | ||
Строка 176: | Строка 179: | ||
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, а то, что передано. | ||
Строка 213: | Строка 216: | ||
) | ) | ||
- | Есть такой стиль, как continuation past, стиль программирования с передачей континуаций. Один из языков, который это вроде поддерживает --- Io. Идея такая, что одним из | + | Есть такой стиль, как 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. |