Введення в продовження і макроси на Scheme

Якщо ви не чули про call/cc, то вам дійсно варто познайомитися з цим потужним інструментом! Поговоримо про продовження (call/cc), простий, але важко розуміється конструкції, що володіє величезною силою в правильних руках. Реалізуємо з їх допомогою механізм yield/next/for… in, аналогічний такому в Python. Обернем нутрощі з допомогою макросу — ще одного цікавого механізму Scheme.

Стаття орієнтована на початківців програмістів. Лисперы навряд чи почерпнуть щось нове, але я буду вдячний за знайдені помилки.

image

Що і навіщо
Кожен програміст періодично стикається з недостатньою виразністю свого коду, коли проста гарна ідея вимагає написання сотень рядків. Це завжди спонукало на створення нових, більш експресивних інструментів таких, як ФП, з набагато більшою щільністю сенсу на одиницю тексту програми.

Продовження (continuation) — це один з механізмів, що дозволяють програмісту на ходу створювати такі інструменти. Історія call/cc (call-with-current-continuation, синтаксична конструкція, що відображає ідею продовжень) тісно пов'язана з Scheme, не найпопулярнішою мовою, який, однак, кілька десятків років служить джерелом натхнення для програмістів. Тому розповідь буде вестися мовою Scheme, а всі приклади коду призначені для интерперетации з допомогою Guile (впевнений, що з майже нульовими зусиллями заведеться в Racket, Chicken і, напевно, в сотні інших інтерпретаторів цього діалекту Лиспа).

Частина I. Продовження
Початок (суть продовжень)
Продовження — це старший брат 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 ...)
кодом так, як ніби функція, що знаходиться всередині цього блоку (умова), повернула #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 (генератор-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*
. Щоб викликаний в черговий раз генератор віддав значення, потрібно зберегти контекст в самому початку генератора, щоб потім підмінити його внутрішню частину її обчислене значення. Саме про це картинка з початку поста:

image

Ми знаходимося в деякій частині програми і хочемо йти далі, вперед. Але для цього потрібно отримати чергове значення від генератора (ящик 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) ...)
.

Частина II. Макроси
— Навіщо?
Ми досягли потрібного нам поведінки. Але синтаксис зовсім не той. Щоб створити функцію генератора, нам потрібно обернути її лямбда-функцією, зробити багато зайвих рухів… на щастя, в 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
):

sum через syntax-case
(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 (генератор-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 подарує ще комусь трохи натхнення в нашій улюбленій справі.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.