[Из песочницы] Введение в продолжения и макросы на Scheme
Если вы не слышали о call/cc, то вам определённо стоит познакомиться с этим мощным инструментом! Поговорим о продолжении (call/cc), простой, но трудно понимаемой конструкции, обладающей огромной силой в правильных руках. Реализуем с их помощью механизм yield/next/for… in, аналогичный таковому в Python. Обернём внутренности с помощью макроса — ещё одного интересного механизма Scheme.
Статья ориентирована на начинающих программистов. Лисперы вряд ли почерпнут что-то новое, но я буду благодарен за найденные ошибки.
Каждый программист периодически сталкивается с недостаточной выразительностью своего кода, когда простая красивая идея требует написания сотен строк. Это всегда подталкивало на создание новых, более экспрессивных инструментов таких, как ФП, с гораздо большей плотностью смысла на единицу текста программы.
Продолжение (continuation) — это один из механизмов, позволяющих программисту на ходу создавать такие инструменты. История call/cc (call-with-current-continuation, синтаксическая конструкция, отражающая идею продолжений) тесно связана со Scheme, не самым популярным языком, который, однако, несколько десятков лет служит источником вдохновения для программистов. Поэтому повествование будет вестись языком Scheme, а все примеры кода предназначены для интерперетации с помощью Guile (уверен, что с почти нулевыми усилиями заведётся в Racket, Chicken и, наверное, в сотне других интерпретаторов этого диалекта Лиспа).
Начало (суть продолжений)
Продолжение — это страший брат GoTo, оператора, который нельзя использовать. Продолжение даёт возможность:
- Получить (захватить) состояние программы в данный момент
- Сохранить это состояние (есть и другие варианты)
- Вернуться к этому состоянию впоследствии, когда бы вы ни захотели
Но зачем возвращаться к прошлому состоянию?
- Чтобы снова пойти вперёд, организовав цикл. Это довольно наивное применение (фактически, использование GoTo).
- Чтобы понять реальную мощь продолжений, нужно выяснить, что же означает «состояние программы», упомянутое выше. В действительности сохраняется текущий стек вызова функций, т.е текущий контекст. А вот следующая функция, которая должна вернуть значение предыдущей (т.е. та, которую мы фактически оборачиваем конструкцией call/cc — см. ниже), не сохраняется. Впоследствие её можно заменить другим кодом (в частности, некоторой константой). Представьте, что вы можете вернуться к себе из будущего и передать себе прошлому какие-либо знания/материальные объекты/указания для дальнейших действий!
Поясним сказанное на практике:
Представим себе некоторый кусок программы. Функция 1 вызывает функцию 2, та вызывает функцию 3 от каких-то других переменных. Перед вызовом, скажем, функции 2, сохраним состояние (называемое текущим контекстом). Впоследствии в любой момент мы можем вернуться к этому контексту, подменив результат работы цепочки функций (func2 (func3 a b c)) нужным нам значением, например, d.
Проверим, что всё работает действительно так.
Первый пример
Создадим какой-нибудь сферический пример в вакууме. Определим функцию test-func:
; некоторая функция для примера
(define test-func
(if (> 3 5) "true " "false "))
(display test-func)
(newline)
Результат (очевидный):
>> false
Теперь сохраним контекст перед вычислением условия в if. Посмотрим, как это сделать:
(call/cc
(lambda (cc) (Some actions)))
Появление call/cc требует от интерпретатора, чтобы он взял текущий контекст и передал его в лямбда-функцию, опеределённую нами внутри. Лямбда-функция принимает один аргумент (здесь и далее в текстах программ будем называть его cc — сокращённо от «current continuation»). Мы можем сохранить этот контекст:
(define *env* #f)
(call/cc
(lambda (cc)
(begin
(set! *env* cc) ; Берём контекст cc, и сохраняем его в переменную *env*
(Some actions))))
Теперь совершим магию. Возьмём сохранённый контекст, и перейдём к нему. Мы обернули конструкцией call/cc условие в блоке if, поэтому нужно при вызове контекста передать значение, которое должно быть возвращено вместо вычисления (> 3 5).
Это делается так:
(*env* Any_value)
Здесь на месте «Any value» может стоять любой код, возвращающий некоторое значение, или само это значение.
Теперь, если мы напишем:
(*env* #t)
мы вернёмся к точке, где был получен контекст, и всё будет выглядеть для внешнего по отношению к блоку (call/cc ...) коду так, как будто функция, находящаяся внутри этого блока (условие if), вернула #t!
Итак, результат
(define test-func
(if (call/cc (lambda (cc)
(begin
(set! *env* cc)
(> 3 5))
)) "true " "false "))
(display test-func)
(display (*env* #t))
(newline)
>> false true true true true true true true true true true true true true true true true true true true true true true true true true true true ...
Всё работает так, как мы хотели, но… бесконечный цикл?! Спокойно, всё в согласии с теорией. Разбёрём, как работает этот пример.
Мы возвращаемся в состояние программы где-то внутри стека вызова, порождённого (display …). Там мы подставляем угодный нам #t, влияющий на результат (выводится true), производится благополучный выход из (display …), вызывается (*env* #t), и по-новой…
Делаем свой генератор
Первое знакомство с call/cc вызывает понимание силы этого инструмента, но далеко не сразу очевидно, как её использовать и что можно реализовать. Классический список вещей, реализуемых с помощью call/cc, включает циклы, выход из цикла или рекурсии, выход из цикла или рекурсии с возвратом, сопрограммы и коопреативную многозадачность. Таким образом, продолжения способны изменять поток выполннения программы всеми мыслимыми способами.
Попробуем использовать эту возможность для реализации на языке Scheme аналога генераторов в Python. Потребуем, чтобы в результате работало так:
; Определяем функцию генератора
(define-generator (generator-func arg1 arg2 ...)
(...
(yield result) ; Возвращаем очередное значение
...))
; Определяем значения аргументов. Теперь my-gen — генератор:
(define my-gen (generator-func 10 30 ...))
(display my-gen) ; Печатает первое значение
(display my-gen) ; Печатает второе значение
; Или распечатаем всё, что есть
(for item in (generator-func 100 70 ...)
(display item))
Возможно, не так лаконично, как в Python, но Scheme всё же ограничена своим синтаксисом (что не мешает быть ему предельно простым и невероятно универсальным).
Первые заготовки
Реализация функции yield почти очевидна. Нужно сохранить текущий контекст (чтобы потом продолжить с него), затем сделать прыжок туда, откуда был вызван генератор — и вместо этого генератора подставить возвращённое с помощью yield значение:
(define (yield value)
(call/cc
(lambda (cc)
(set! *env* cc) ; сохраним контекст
(*return* value)))) ; совершим прыжок в контекст, сохранённый ранее, с подставновкой value
- Сразу понятно, что у каждого генератора (их может быть несколько в программе), должны быть свои
*env*и*return*, сохранённые внутри некоторой локальной области видимости. - Из первого следует, что
yieldне может быть глобальным, а значит, его нужно передать функции, которая вызываетyield
Реализуем это, заодно написав пример генератора квадратов чисел от 1 до n:
(define (create-generator func)
(define *env* (lambda () (func yield)))
(define *return* #f)
(define (yield value)
(call/cc
(lambda (cc)
(set! *env* cc)
(*return* value))))
(lambda ()
(здесь будет логика генератора)))
; Генератор квадратов чисел
(define (squares-gen n)
(lambda (yield)
(let loop ((n (+ n 1)) (k n))
(if (> k 0)
(begin
(yield (expt (- n k) 2))
(loop n (- k 1)))))))
Почти готово
Дело осталось за малым: нужно записать что-то в переменную *return*. Чтобы вызванный в очередной раз генератор отдал значение, нужно сохранить контекст в самом начале генератора, чтобы потом подменить его внутреннюю часть возвращаемым значением. Именно об этом картинка из начала поста:
Мы находимся в некоторой части программы и хотим идти дальше, вперёд. Но для этого нужно получить очередное значение от генератора (ящик c). Заходим в генератор (сохраняем состояние и поднимаемся по лестнице), подбираем ящик и «телепортируемся» обратно (возвращаемся к сохранённому состоянию), но уже с ящиком! На деле нужно добавить пару строк:
(define (create-generator func)
(define ...)
...
(lambda ()
(call/cc
(lambda (cc)
(set! *return* cc)
(*env*))))) ; Изначально просто входим в функцию func, впоследствии продолжаем с сохраненного места,
; подменив (yield smth) в коде func... ничем!
Результат
Соберём всё вместе:
(define (create-generator func)
(define *env* (lambda () (func yield)))
(define *return* #f)
(define (yield value)
(call/cc
(lambda (cc)
(set! *env* cc)
(*return* value))))
(lambda ()
(call/cc
(lambda (cc)
(set! *return* cc)
(*env*)))))
; Генератор квадратов чисел
(define (squares-gen n)
(lambda (yield)
(let loop ((n (+ n 1)) (k n))
(if (> k 0)
(begin
(yield (expt (- n k) 2))
(loop n (- k 1)))))))
(define my-gen (create-generator (squares-gen 10)))
Проверяем:
; Вызовем my-gen 7 раз
(let loop ((n 7))
(if (> n 0)
(begin
(display (my-gen))
(display " ")
(loop (- n 1)))))
>> 1 4 9 16 25 36 49
Ура! Работает!
Замечание
Я надеюсь, вы заметили одну очевидную ошибку. Если мы вызовем полученный генератор больше 10 раз, мы войдём в бесконечный цикл. Вызывая (*env*), мы полностью возвращаемся к тому состоянию, в котором были при последней итерации, потому что не сохраняем нового, поскольку не доходим в коде функции-генератора до yield. Можно поступить, например, так: если генератор не может выдать очередное значение, он возвращает значение-заглушку, например, «Stop Iteration».
Как это сделать? Проверьте себя на понимание, придумайте сами (добро пожаловать в комментарии). Нужно добавить всего одну строку кода внутри (define (create-generator func) ...).
Зачем?
Мы добились нужного нам поведения. Но синтаксис совсем не тот. Чтобы создать функцию генератора, нам нужно обернуть её лямбда-функцией, сделать много лишних телодвижений… к счастью, в Scheme есть мощный механизм макросов. Макросы, как всегда, зло, если рассовывать их повсюду, но если писать один раз и надолго, почему бы не облегчить себе жизнь красивым синтаксическим сахаром?
Краткое описание
Макросы освещены на просторах интернета гораздо лучше, чем продолжения, поэтому лишь коротко оставновимся на них (вторая причина — неожиданно большой размер статьи; если сообщество посчитает нужным развёрнутое описание макросов в Scheme, я напишу вторую статью).
- Макросы в Scheme подобны препроцессору в C. Макросы раскрываются до трансляции в байт-код.
- Макросы преобразуют синтаксические конструкции, и только их. Мы пишем одни строки кода, на выходе другие.
define-syntaxи иже с ним определяют правила, по которым происходит обозначенное преобразование.
Наверное, будет неправильным по сути дублировать то, что было рассказано не раз, и на Хабре в том числе.
Основы макросов в Scheme (поиск по странице: «Макросы»): habrahabr.ru/company/tcsbank/blog/267113
Здесь же мы рассмотрим тонкость, которая сыграет существенную роль.
Напишем пример макроса, который определяет функцию, просто суммирующую элементы списка (для этого макрос, конечно, не нужен; пример, как всегда, из воздуха, но необходим для понимания):
; сумматор списка конструкцией (sum (list 5 9 1 ...))
(define-syntax sum
(syntax-rules ()
((_ args-list)
(let loop ((res 0) (left-list args-list))
(if (not (null? left-list))
(loop (+ res (car left-list)) (cdr left-list))
res)))))
(display (sum (list 3 4 5 1)))
(newline)
>> 13
Всё работает.
А теперь сделаем вот так:
(define loop (list 3 4 5 1))
(display (sum loop))
Представляете, в какое месиво развернётся этот макрос (из-за совпадения имён — loop, внутри макроса и снаружи)? Эх, сейчас посыпятся ошибки компиляции… Запускаем…
>> 13
Да неужели?! Как это могло сработать? На самом деле, в Scheme макрос — не такая прямая конструкция, как кажется. В нашем случае макрос развернётся в:
(let loop-1 ((res 0) (left-list loop))
(if (not (null? left-list))
(loop-1 (+ res (car left-list)) (cdr left-list))
res))
Макросы умеют определять конфликты имён снаружи и внутри, поэтому внутренняя переменная loop получила другое имя, loop-1.
Syntax-case, with-syntax, datum→syntax
В нашем случае, к сожалению, такой интеллект макроса только мешает. Внутри макроса мы непременно будем использовать yield, который непременно преобразуется к yield-1.
Чтобы заставить макрос работать так, как нам нужно, существует более мощная конструкция, syntax-case.
Статья и так получилась слишком большой, поэтому подробное описание этого инструмента будет в следующей публикации (если будет необходимость).
Синтаксис схож с syntax-rules, разница в обёртке из лямбда-функции и способе возвращения значения, через (syntax something) — функция, возвращающая синтаксическую конструкцию, построенную из «something».
В Scheme существует сокращение для (syntax ...): #'.
Предыдущий пример перепишется так (причём код ниже во всех смыслах эквивалентен коду с использованием syntax-rules):
(define-syntax sum
(lambda (x)
(syntax-case x ()
((_ args-list)
#'(let loop ((res 0) (left-list args-list))
(if (not (null? left-list))
(loop (+ res (car left-list)) (cdr left-list))
res))))))
Ввести идентификатор объекта из внешней по отношению к макросу области видимости (так сказать, из обычного Scheme) во внутреннюю область видимости макроса можно с помощью datum->syntax.
Например, для того, чтобы yield не превращался в yield-1 внутри (syntax ...), можно сделать так:
(define-syntax sum
(lambda (x)
(syntax-case x ()
((pattern)
(syntax-case (datum->syntax x 'yield) ()
(yield (syntax ... yield ...)))))))
Scheme предлагает некоторый синтаксический сахар, чтобы этот код выглядел приятней:
(define-syntax sum
(lambda (x)
(syntax-case x ()
((pattern)
(with-syntax (yield (datum->syntax x 'yield))
(yield (syntax ... yield ...)))))))
В результате мы использовали syntax-case, чтобы, по сути, создать обычный макрос, в котором мы можем без всяких проблем использовать yield, и всё будет работать так, как мы ожидаем.
Наконец, используем макросы в деле
Вспомним синтаксис, которого мы добивались:
; Определяем функцию генератора
(define-generator (generator-func arg1 arg2 ...)
(...
(yield result) ; Возвращаем очередное значение
...))
; Определяем значения аргументов. Теперь my-gen -- генератор:
(define my-gen (generator-func 10 30 ...))
(display my-gen) ; Печатает первое значение
(display my-gen) ; Печатает второе значение
Создадим макрос define-generator, который создаёт функцию от аргументов arg1, arg2 …, которая возвращает генератор. Код аналогичен тому, что мы уже написали:
; Создаём нужный макрос:
(define-syntax define-generator
(lambda (x) ; формальный синтаксис syntax-case
(syntax-case x ()
((_ (name . args) body)
(with-syntax ((yield (datum->syntax x 'yield))) ; введем внешний идентификатор yield в область видиости макроса
(syntax (define (name . args) ; вернём функцию генераатора, принимающую на вход заданные аргументы, и возвращающую генератор
(define *env* (lambda () (body))) ; здесь и далее дублируем код, написанный в статье
(define *return* #f)
(define (yield value)
(call/cc
(lambda (cc)
(set! *env* cc)
(*return* value))))
(lambda ()
(call/cc
(lambda (cc)
(set! *return* cc)
(*env*)))))))))))
(define-generator (squares-gen n)
(let loop ((n (+ n 1)) (k n))
(if (> k 0)
(begin
(yield (expt (- n k) 2))
(loop n (- k 1))))))
(define my-gen (squares-gen 10))
(let loop ((n 7))
(if (> n 0)
(begin
(display (my-gen))
(display " ")
(loop (- n 1)))))
>> 1 4 9 16 25 36 49
Снова ура! Работает!
Послесловие
Если вдруг вы знали немного о продолжениях и макросах, а мне удалось донести до вас то, что написано выше, то вы легко по аналогии напишете реализацию for ... in ... Не забывайте про ошибку, намеренно оставленную в коде.
Спасибо, если дочитали до конца. Надеюсь, что теперь Scheme подарит ещё кому-то немного вдохновения в нашем любимом деле.
