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

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

Текущая версия

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

Сегодня лектор хотел рассказать про континуации. Это, может быть, не самое зубодробительное, что есть в схеме, но самое интересное. Самым зубодробительным может лектор назвать макросы, потому что он их так и не смог полностью понять.

Но начнём не с них, сначала посмотрим, что можно делать с помощью лексических замыканий в лиспе. Писать лектор будет на схеме. В частности

• defun в лиспе --- define в схеме. Синтаксис: (defun f (...) ...) -> (define (f ...) ...). Кроме того, define может определять не только функции, но и вещи вроде глобальных переменных. Сами по себе символы ничего не вмещают, для этого надо сказать (define x #f), после чего уже можно сказать (set! x 25). Не все реализации поддерживают эту хитрость, но она есть.

Нам потребуется ещё пара вещей из схемы:

• (map ...) --- то же, что и mapcar в лиспе
• (for_each fun (...)) --- вызывает функцию ради побочного эффекта. Не возвращает ничего.

Свойства лексических замыканий одинаковы что в схеме, что в лиспе (исключение- elisp Столлмана).

(define funpair
  (let ((n 0))
    (cons
      (lambda () (set! n 0)) ; reset
      (lambda () (set! n (+ n 1)) n) ; next
    )
  )
)

Результат: точечная пара, у которой первый и второй элемент будут функциями. Первая функция — reset, вернуть значение переменной в 0.

Что в результате получилось: с funpair связана точечная пара, в car лежит (lambda () (set! n 0)), в cdr — (lambda () (set! n (+ n 1)) n). Теперь лектор берёт интерпретатор, скармливает это и начинает экспериментировать (две скобки потому, что нужно вызывать):

> ((cdr funpair))
1
> ((cdr funpair))
2
> ((cdr funpair))
3

И т.д.

Что это показывает: что лексический контекст (сост. из одной переменной и её значения) не копируется, а сохраняется и остаётся связанным.

> ((car funpair))
> ((cdr funpair))
1

Получился как будто бы объект с двумя методами. Часто ли может такая штука понадобиться? --- часто. Это секвенсер.

Это некий фокус, позволяющий понять, что такое лексический контекст.

Обратите внимание, что обе функции связаны с лексическим контекстом, потому что они создавались в нём.

Континуация- это последовательность действий, которые осталось выполнить до завершения вычислений. Вот, у нас есть какие-то вычисления. Наверняка, у нас есть какая-то головная функция (в C - main, например). Собственно, всё выч. программы можно представлять так: что осталось сделать до завершения программы. Когда мы в начале выполнения, то нам нужно вызвать эту функцию. после того, когда вызвали, мы вошли в её тело. Что осталось? Осталось вычислить первую форму, вторую, и так до конца. Дальше, допустим, первая форма головной функции это что-нибудь такое:

(set! x (+ 1 (* 3 5))) (...) ...

Что ост. вычислить на след. шаге? Осталось вычислить (+ 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/cc: он вызывает функцию, подав ей в качестве единственного аргумента вот этот объект континуации.

(call/cc f)

Так вот, вызвана будет f("континуация"). Понятно, что обычно здесь используют лямбду, но это необязательно.

Как это дело вычисляется: если call/cc вызывает f, а f что-то возвращает ( если успеет), то вся эта форма вернет то, что вернула f. Здесь ничего сверхъестественного нет. Но, есть один момент: внутри функции f доступен этот объект, что с ним можно сделать? Его можно вызвать как функцию одного аргумента, и этот вызов приведёт к тому, что форма эта немедленно вернёт управление ровно в том месте, которое было, и в качестве значения вернёт то, что подали континуации как функции одного аргумента, причём это можно сделать после того, как она вернула управление.

Достаточно простая иллюстрация:

> (define store #f)
> (define (f arg) (set! store arg) "simple")
> (let ((x (call/cc f)))
>   (write (list x x x))
> )
("simple" "simple" "simple")

Но при этом континуация сохранилась в store.

> (store "complicated")
("complicated" "complicated" "complicated")

Как это реализуется --- по-разному. Есть, например, реализация для C, которая сделана путём сохранения стека.

Вначале лекции лектор сказал, что континуации являются обобщением многих вещей. Например:

* Досрочное окончание многих функций. (аналог brake/return в C)

Вообще, goto не так и плох, его вполне можно использовать в двух случаях.

• Первый --- cleanup. Например, В начале забирается дин. ресурс, а потом хочется досрочно её завершить. Так вот, не надо дублировать освобождение, нужно сделать goto на cleanup:
• Второй — выход из несколько вложенных циклов. Тут break не поможет. Обычно это делают посредством флага. Не надо так делать. Это второй и последний случай.

Но в современных языках случаев может быть меньше. В C++ есть деструкторы, в Ada/Java можно именовать for и прочее.

call/cc является обобщением вариантов с досрочным выходом из конструкции. Пример: дан предикат от одного аргумента. Дан список из скольких-то элементов. Задача: из этого списка извлечь первый элемент, на котором предикат вернёт истину. Можно ли это сделать с помощью рекурсии? Конечно можно.

(define (search wanted? lst)
  (cond
    ((null? lst) #f)
    ((wanted? (car lst)) #t)
    (#t (search wanted? (cdr lst)))
  )
)

В традиции языка scheme — именование предикатов вопр. знаком.

Единственное что — значение глобальных переменных не сохраняется.

Можно так писать? Можно. Но обычно для просмотра списков хочется использовать мапперы. Можно ли их тут использовать? Можно, но будет не меньше по длине:

(define (search wanted? lst)
  (call/cc 
    (lambda (return)
      (for-each
        (lambda (elem) (if (wanted? elem) (return elem)))
        lst
      )
      #f
    )
  )
)

Короче ли это? Трудно сказать, строчек больше, но букв примерно столько же. Понятнее ли? Вопрос. Рекурсия привычнее, но на С мы бы написали примерно то же самое:

int search(int (*pred)(int), int *arr, int n)
{
  int i;

  for (i = 0; i < n; i++)
  {
    if (pred(arr[i]))
    {
      return arr[i];
    }
  }

  return 0;
}

Таким образом мы с помощью call/cc эмулируем выход из циклов. Но возможности на этом не заканчиваются. Что ещё можно: можно заст. прекр. функцию, которая лексически в другом месте. Давайте переделаем функцию search, если у нас не предикат есть, а некая функция. Теперь применим другую парадигму, callback. Мы выбор элемент будем выбирать с помощью функции, которой если элемент понравился, то она будет делать колбэк.

(define (treat elem callback)
  (if (wanted? elem) (callback elem))
)
(define (search treat lst)
  (call/cc
    (lambda (return)
      (for-each
        (lambda (elem) (treat elem return))
        lst
      )
      #f
    )
  )
)

Делает то же самое, один момент: функция, которая завершает просмотр, находится в другом месте. Называется это "нелокальный выход".

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

А вот есть такая вещь, как исключения, они есть во многих языках. Потому, что не смотря на то, что они криво реализованы, сильно облегчают жизнь.

Ошибочно полагать, что парадигма образования исключений имеет отношение к ООП. Почему так полагают? Потому что впервые с ним столкнулись в С++, но сам механизм не имеет отношения к ООП. Что такое ООП: это когда среда использует приложения состоящие из объектов, они имеют внутр. состояния, могут принимать сообщения, как-то менять внутр. сост., обр. к другим объектам, отвечать на сообщ. Как это соотн. к С++, То, что в теории ООП наз. передачей сообщения, в С++ есть вызов метода. И при чём тут обработка исключений? Ни при чём? К какой же парадигме тогда они ближе? К функциональной. Что есть исключение, как не способ альт. завершения функции? Если это альт. способ. возврата из функции, то думать надо не об объектах, а о функциях, а это точно не из ООП понятие. Поэтому, исключения- это парадигма, не имеющая никакого отношения к ООП.

Лектор напомнит, что такое исключение:

В качестве обозначение искл. ситуации можно исп. объект почти любого типа, в том числе объект типа Class.

Для возбуждения исключения исп. throw ... . Объекты, не допускающие копирования, нельзя исп.. Как поймать исключение?

Почему из курса архитектура эвм надо знать, что такое стековый фрейм? Потому что такие вещи, как искл. и хвостовая рекурсия, проще объяснять.

Есть функция из стандартного C++ runtime, __trow_unwind, которая линкуется при исп. искл. Эта функция берёт стековый фрейм и начинает его разматывать, ища обработчик. Если нет, то вызывает деструкторы и схлопывает его. Далее берёт стековый фрейм и так далее. Если дойдёт до вершины стека, то программа завершится.

Можно сымитировать исключение в языках, в которых их нет. Например, в С. Там есть setjmp/longjmp.

int setjmp(jmp_buf env); 

Принимает setjmp на вход буфер, она туда записывает некую информацию, которая пригодится для возврата туда потом. На самом деле, она туда записывает текущий указатель стека, возвращая при первом вызове 0.

Когда делается long_jmp(jmp_buf, int), то в след. раз вернёт не 0, а то, что передано.

Единственное ограничение: стековый фрейм должен существовать. Если его уже нет, то "full chaos guaranteered".

Эмуляция исключений с call/cc:

(let ((ret (call/cc ..) ...

Это всё хорошо, но это всё, что нелокальные выходы, что искл --- ситуация, когда мы глубже в стеке.

Гораздо интереснее, когда оно уже отработало, стековый фрейм прибился, но call/cc мощнее тем, что он позволяет вернуться и в этой ситуации.

Что можно с помощью этого сделать: например, сопрограммы (жутко медленно, но красиво). Что для этого нужно сделать:

(define queue_ '())
(define (empty_queue?) (null? queue))
(define (enqueue x))
  (set! queue (append queue (lest x)))
)
(define (deque)
  (let ((x (car queue)))
    (set! queue (cdr queue))
    X
  )
)
(define (fork proc) ; процедура, которая некую функцию ставит в очередь
  (call/cc (lambda (k) (enqueue k) (proc))) ;в конец процедуры ставим то место той процедуры, которая вызвала fork
)
(define (yield)
  (call/cc (lambda (k) (enqueue k) ((dequeue))))
)
(define (thread_exit)
  (if (empty_queue?) (exit) ((dequeue)))
)

Есть такой стиль, как continuation past, стиль программирования с передачей континуаций. Один из языков, который это вроде поддерживает --- Io. Идея такая, что одним из аргументов передаются континуации. Стека там нет, там вообще нет возврата. Любопытная штука, бывает и такое.

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

funpair — пример использования лексического замыкания.	Использование funpair.	Иллюстрация к объяснению понятия континуация.	Синтаксис вызова call/cc.
Пример использования call/cc. Первая часть.	Пример использования call/cc. Полностью.	Варианты использования goto.	Использование call/cc для досрочного выхода.
Реализация поиска в массиве на C.	Поиск в массиве с использованием callback.	Иллюстрация к рассказу про механизм исключений.	setjmp/longjmp.
Реализация сопрограмм/переключения нитей посредством call/cc.