— я подумал, что неплохо бы поближе познакомить читателей rsdn со scheme. Пожалуй, лучшим для этого форматом были бы краткие примеры реализации какой-то интересной функциональности. Начну я с пары-тройки вариантов корутин — ну а дальше уж как получится, если получится вообще.
Впрочем, какой я к черту евангелист scheme? Скорее просто тролль. Так что давайте притворимся, что ваш покорный слуга просто форсит на форуме единственный язык, который знает, и не будем сильно пинать его за ошибки.
Сегодня мы реализуем на scheme аналог генераторов из питона. Наш коллега palm mute уже приводил пример реализации в своем блоге: http://palm-mute.livejournal.com/12291.html, и сегодня мы не сильно выйдем за рамки этого поста.
В качестве ленивых списков мы будем использовать потоки из srfi-41. Возможно, это не самая хорошая идея, однако для демонстрации возможностей — вполне подойдет.
Главным нашим инструментом будет shift/reset. Reset, подобно begin, выделяет группу выражений. Shift позволяет прервать выполнение этой группы выражений и сразу выскочить за пределы reset.
В plt scheme, которой мы будем пользоваться, как shift/reset, так и потоки уже реализованы. Нам будет достаточно подключить два модуля.
Основной профит shift заключен в его первом параметре. Первый параметр shift — континуация, невыполненная часть блока reset. С этой континуацийе можно обращаться как с любой другой функцией: вызывать, сохранять где-нибудь на будущее или (как в предыдущем примере) просто выкинуть.
Таким образом понятно, что должен делать yield — захватывать континуацию генератора с помощью shift и сохранять ее в stream-cdr.
(stream->list (reset
(shift k (stream-cons 1 (k (void))))
(shift k (stream-cons 2 (k (void))))
(shift k (stream-cons 3 (k (void))))
stream-null))
>(1 2 3)
Стоит заметить, что при данной семантике yield последним выражением в reset (если, конечно, генератор вообще предполагает выход из блока reset) должен быть stream-null.
Итак, для определения генератора мы напишем такой вот несложный макрос. Во-первых, он заключает тело функции в reset, а во-вторых, заставляет ее всегда возвращать stream-null.
(define-syntax define-generator
(syntax-rules ()
((_ (name args ...) body ...)
(define (name args ...)
(reset body ... stream-null)))))
А yield тогда будет обычной функцией.
(define (yield value)
(shift k (stream-cons value (k (void)))))
Ну и последний на сегодня штрих. Определим хелпер, который позволит из генератора обращаться к другим генераторам (и к себе рекурсивно) и встраивать их выхлоп в собственный.
(define (yield-splice stream)
(shift k (stream-append stream (k (void)))))
На сегодня все, однако с питоновскими генераторами мы еще не закончили. Ведь что делает их по-настоящему интересными — так это возможность извне влиять на выполнение генератора с помощью send(). Send() позволяет указать значение, которое внутри генератора вернет yield. У нас yield возвращает то, что в качестве параметра передается в пойманную шифтом континуацию. То есть мы должны научиться вместо (void) передавать туда что-то полезное. Но это в следующий раз.
Результатом этого выражения будет бесконечный стрим чисел фибоначчи.
Можно было бы еще рекурсивно извратиться с помощью yield-splice, однако в нашем варианте невозможны хвостовые вызовы между генераторами, так что за пределы генератора лучше лишний раз не выходить.
Здравствуйте, DemAS, Вы писали: DAS>А можно перед каждым примером указывать language, который нужно DAS>использовать в drscheme?
В качестве language надо выбрать module. В начало файла, возможно, придется дописать #lang scheme.
MC>Результатом этого выражения будет бесконечный стрим чисел фибоначчи. MC>Можно было бы еще рекурсивно извратиться с помощью yield-splice, однако в нашем варианте невозможны хвостовые вызовы между генераторами, так что за пределы генератора лучше лишний раз не выходить.
Я не спец, извиняюсь за глупые вопросы, но почему нельзя было просто написать бесконечный поток чисел фибоначчи? Зачем нам обязательно yield? Какое оно дает преимущество?
Здравствуйте, Spiceman, Вы писали: S>почему нельзя было просто написать бесконечный поток чисел фибоначчи?
Потому что мы сперва решили реализовать аналог yield, а потом стали придумывать, куда бы его впихнуть.
S>Зачем нам обязательно yield? Какое оно дает преимущество?
Да никакого особо преимущества. Просто другой стиль.
DAS>И еще, что такое fib/iter? Что такое let я представляю, но как работает DAS>конструкция
>> (let fib/iter ((curr 1) >> (next 1))
DAS>уже нет.
Это named let
Mr.Cat wrote: > Здравствуйте, DemAS, Вы писали: > DAS>А как из этого генератора получить необходимый нам диапазон чисел? > Например, с помощью stream-take.
— я подумал, что неплохо бы поближе познакомить читателей rsdn со scheme. Пожалуй, лучшим для этого форматом были бы краткие примеры реализации какой-то интересной функциональности. Начну я с пары-тройки вариантов корутин — ну а дальше уж как получится, если получится вообще.
MC>Впрочем, какой я к черту евангелист scheme? Скорее просто тролль. Так что давайте притворимся, что ваш покорный слуга просто форсит на форуме единственный язык, который знает, и не будем сильно пинать его за ошибки.
А вот другой пример, как делать "не надо", это будет работать в SCM
— я подумал, что неплохо бы поближе познакомить читателей rsdn со scheme. Пожалуй, лучшим для этого форматом были бы краткие примеры реализации какой-то интересной функциональности. Начну я с пары-тройки вариантов корутин — ну а дальше уж как получится, если получится вообще.
MC>Впрочем, какой я к черту евангелист scheme? Скорее просто тролль. Так что давайте притворимся, что ваш покорный слуга просто форсит на форуме единственный язык, который знает, и не будем сильно пинать его за ошибки.
Несколько лет назад была у меня такая же идея, но потом что-то заглохло
Вот сейчас откопал с тех времён самописный чисто функциональный пузырёк:
И снова здрасьте. Сегодня я хотел продолжить компостировать вам мозги генераторами и потоками, однако наш коллега GSergey обратил наше внимание () на другой вариант семантики корутин. Вот примерно такой:
Действительно. Что если "научить" нашу функцию возвращать значение и при этом сохранять свое состояние и при следующем вызове к этому состоянию возвращаться? По-моему, идея хороша. К этой идее мы подойдем с той же стороны, что и наш коллега, с небольшими отличиями в деталях. Кстати, заранее прошу прощения за то, что rsdn в блоках кода заменяет -> на ->;.
Нам снова потребуется shift/reset:
(require scheme/control)
То, что GSergey реализовывал с помощью пары call/cc, мы сделаем через shift/reset. Тело нашей "обладающнй состоянием" функции мы снова заключим в reset, а yield снова будет довольно несложной оберткой над shift. Но на этот раз пойманную шифтом континуацию мы будем просто просто сохранять — на будущее. Итак, начнем писать макрос для определения обладающей состоянием функции, и по ходу дела разберемся с частностями.
(define-syntax stateful-lambda
(syntax-rules ()
((_ yield fin args body ...)
;;В state мы будем хранить континуацию, если функция уже вызывалась
;;и была прервана йилдом и #f в противном случае.
;;Функцию yield будет на этот раз для каждой лямбды своя, поскольку
;;она должна иметь доступ к специфичному для каждой лямбды state
;;При таком раскладе гигиеничность системы макросов заставляет нас
;;явно передавать в макрос имя, которое будет использоваться для yield
;;в качестве параметра.
(let* ((state #f)
(yield (lambda v (shift k (begin (set! state k)
(apply values v))))))
(lambda args1
;;Если в состоянии лежит захваченная ранее шифтом континуация -
;;мы просто ее вызовем
(if state
(apply state (if (= (length args1) 0)
(list (void))
args1))
;;При первом же вызове лямбды-с-состоянием мы просто начнем выполнять
;;ее тело.
;;При выходе из лямбды-с-состоянием не посредством yield, мы обнулим ее
;;состояние и при этом возвратим специальное значение fin, которое мы
;;также указали при объявлении лямбды.
(apply (lambda args (reset body ...
(set! state #f)
fin)) args1)))))))
Добавим к перечисленному более-менее корректную обработку множественных возвращаемых значений — и наш макрос готов к использованию.
Так что теперь — небольшой такой, зато кривой пример. Напишем функцию list-walker, которая, принимая список, возвратит stateful-lambda, которая будет по очереди возвращать элементы этого списка. И когда они закончатся — начнет с начала.
Теперь мы умеем писать функции, которые умеют поддерживать внутри себя состояние, скрывая его от внешнего мира. А когда мы говорим "состояние", на ум сразу приходит что? Правильно, конечный автомат. Так что давайте поверх нашей функции сделаем хелпер для реализации конечных автоматов.
(define-syntax fsm-lambda
(syntax-rules (->)
;;При создании автомата будем задавать начальное состояние и конечное.
;;С начальным все понятно. Конечное мы выделяем затем, чтобы бросать
;;искючение всегда, когда в это состояние приходит сообщение
((_ start fin
;;Правила перехода будем задавать в виде
;;(состояние сообщение -> (новое-состояние . возвращаемое-значение))
;;Понятное дело, что после стрелки не обязательно должна стоять
;;непосредственно пара, достаточно возвращающего ее выражения
(from message -> to) ...)
(stateful-lambda yield final (message1)
(let iter ((state start)
(message2 message1))
(let ((result
(match (cons state message2)
((cons fin _) (error'fin))
((cons from message) to) ...)))
(iter (car result) (yield (cdr result)))))))))
Ну и пример, конечно. И да, снова тривиальный. Сделаем счетчик, который можно перезапускать по команде 'restart.