Генераторы и акторы

Андрей Власовских

© 2008. Доступно по Creative Commons

Интересные ссылки

• Закончена книга Real World Haskell
• Параллельность в Clojure: синхронная на STM, асинхронная на агентах (!= акторы)
• SE Radio: Simon Peyton Jones on Functional Programming and Haskell

План

1. Генераторы
   • Виды продолжений
   • Генераторы в Python
   • Монадический do-синтаксис на генераторах
   • call/cc, зелёные нити
2. Акторы
   • Акторы как подход к эффектам и параллельности
   • Реализация на Python, Scheme, Haskell
   • Интерфейсы IO

Словарик

• Actor — актор
• Actor model — модель акторов
• Call with current continuation — вызов с текущим продолжением
• Continuation — продолжение
• Continuation-passing style — передача продолжений
• Coroutine — сопроцедура
• Generator — генератор
• List comprehension — порождение списка
• Message passing — передача сообщений

Генераторы

Определения

Продолжение — состояние потока управления, доступное через конструкции языка.

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

Генератор — сопроцедура, которая только возвращает значения.

Виды продолжений

• goto
• Императивные процедуры, return
• for, while, continue, break
• Сопроцедуры (Simula 67, Stackless Python)
  • Генераторы (Icon, Python)
  • call/cc (Scheme, Ruby, Haskell: монада Cont)
  • Продолжаемые исключения (Common Lisp)
• Исключения
• Продолжения в continuation-passing style
• Нити и механизмы синхронизации

Генераторы в Python

• Ленивые списки
• Локализация эффектов
  • Функции вроде ByteString -> a, a -> ByteString
• Сопроцедуры (двусторонние генераторы в Python 2.5)
  • Асинхронность (неблокирующий NIO, события)
  • Многозадачность (зелёные нити, сопроцедурные планировщики)

Интерфейс итератора

Вначале итераторы, интерфейс генераторов с внешним миром.

          class Iterable(object):
    def __iter__(self):
        'Iterable(a) -> Iterator(a)'

class Iterator(Iterable):
    def next(self):
        'Iterator(a) -> a'

        

Abstract Base Classes (ABC), см. PEP 3119.

Протокол итератора

for и порождения списков

Эти конструкции выполняют протокол итератора.

          list = [1, 2, 3]
for x in list:
    print x

# Ленивый range
iterable = xrange(1000000)
for x in iterable:
    print x

sq_of_odds = [square(x) for x in iterable
                        if odd(x)]
print '\n'.join(sq_of_odds)

        

iter

Рассмотрим iter как пример реализации итератора ручками и на генераторах. Он нужен для перебора значений процедуры с эффектами. Использование iter:

          from md5 import md5
def md5_update(md, data):
    md.update(data)
    return md
fd = open(filename 'rb')
contents = iter(lambda: fd.read(block_size), '')
md = reduce(md5_update, contents, md5())
print md.hexdigest()

        

Реализация iter

Интересен iter с 2 аргументами для перебора значений процедуры с эффектами.

          def iter(*args):
    'Iterable(a) -> Iterator(a)'
    '(None -> Eq(a)), Eq(a) -> Iterator(a)'
    if len(args) == 1:
        collection, = args
        return collection.__iter__()
    elif len(args) == 2:
        callable, sentinel = args
        return _Iter(callable, sentinel)
    else:
        raise TypeError('...')

        

_Iter как класс

          class _Iter(object):
    def __init__(self, callable, sentinel):
        self._callable = callable
        self._sentinel = sentinel

    def __iter__(self):
        return self

    def next(self):
        res = self._callable()
        if res == self._sentinel:
            raise StopIteration()
        return res

assert isinstance(_Iter(...), Iterator)

        

_Iter как генератор

Синтаксис генераторов: yield.

          def _Iter(callable, sentinel):
    while True:
        res = callable()
        if res == sentinel:
            raise StopIteration()
        yield res

assert isinstance(_Iter(...), Iterator)

        

Примеры из itertools

           def chain(*iterables):
     for it in iterables:
         for element in it:
             yield element

 def count(n=0):
     while True:
         yield n
         n += 1

        

Порождения генераторов

          sq_of_odds = (square(x) for x in iterable if odd(x))

        

Ср. с порождениями списков:

          sq_of_odds = [square(x) for x in iterable if odd(x)]

        

Генераторы для локализации IO

• Ввод
  • Передаётся аргумент Iterable(a), который реализован в виде генератора, осуществляющего эффекты чтения)
• Вывод
  • Возвращается Iterable(a) в код, который осуществляет эффекты записи

Интерфейс WSGI

          f: environ, start_response -> response

{bytes: object},
(bytes, [(bytes, bytes)] -> (bytes -> None)) ->
Iterable(bytes)

        

Можно думать о нём как о:

          f: environ, request -> status, headers, response

{bytes: object}, Iterable(bytes) ->
bytes, [(bytes, bytes)], Iterable(bytes)

        

WSGI apps and middleware

          def fileread(environ, start_response):
    start_response('200 OK', [...])
    with open(filename, 'rb') as fd:
        for block in iter(lambda: fd.read(block_size), ''):
            yield block

def upper(app):
    def mid(environ, start_response):
        return (s.upper() for s in app(environ, start_response))
    return mid

app = upper(fileread)

        

Двусторонние генераторы

В Python 2.5: передача значений внутрь генератора, сопроцедуры, см. PEP 342. Пример сопроцедурного планировщика — при обсуждении акторов.

          class Generator(Iterator):
    def send(self, value):
        'Generator(a), a -> a'
    def throw(self, type, value=None, traceback=None):
        pass

        

Аргумент send становится значением yield.

Аналог stream-based IO в Haskell

          def dialogue():
    yield append_chan(stdout, 'enter filename\n')
    name = yield read_chan(stdin)
    yield append_chan(stdout, name)
    try:
        contents = read_file(name)
    except IOError:
        yield append_chan(stdout, "can't open file")
    else:
        yield append_chan(stdout, contents)

        

Монады в Python

Интерфейс монад, затем do-синтаксис на генераторах. Класс Monad в виде интерфейса OOP:

          class Monad(object):
    def bind(self, f): 
        'Monad(a), (a -> Monad(b)) -> Monad(b)'
        raise NotImplementedError()

    @staticmethod
    def unit(value):
        'a -> Monad(a)'
        raise NotImplementedError()

        

Можно было и через ABC.

Maybe (1)

          class Maybe(Monad):
    def bind(self, f):
        'Maybe(a), (a -> Maybe(b)) -> Maybe(b)'
        if isinstance(self, Nothing):
            return self
        else:
            return f(self.value)

    @staticmethod
    def unit(value):
        'a -> Maybe(a)'
        return Just(value)

        

Аналогично методы MonadPlus.

Maybe (2)

          class Just(Maybe):
    def __init__(self, value):
        self.value = value

    def __repr__(self):
        return 'Just(%r)' % self.value

class Nothing(Maybe):
    def __repr__(self):
        return 'Nothing()'

        

В Scala и C# это были бы case or final classes.

Сумма значений Monad

          def msum(x, y):
    'Monad(int), Monad(int) -> Monad(int)'
    return (
        x.bind(lambda x_:
        y.bind(lambda y_:
        type(x).unit(x_ + y_))))

        

Сумма с do-синтаксисом

В этом сахаре = yield — аналог <-, а mreturn — return.

          @do
def msum(x, y):
    '(Monad(int), Monad(int)) -> Generator(Monad(int))'
    x_ = yield x
    y_ = yield y
    mreturn(x_ + y_)

        

Декораторы: @do — это foo = do(foo).

do-синтаксис для монад (1)

На основе Monads in Python (with nice syntax). Используются двусторонние генераторы:

          def do(f):
    '(*, ** -> Generator(Monad(a))) -> (*, ** -> Monad(a))'
    def wrapper(*args, **kwargs):
        '*, ** -> Monad(a)'
        gen = f(*args, **kwargs)
        first = gen.next()
        def send(value):
            'a -> Monad(a)'
            try:
                m = gen.send(value)
                return m.bind(send)
            except MonadReturn, ret:
                return type(first).unit(ret.value)
        return first.bind(send)
    return wrapper

        

do-синтаксис для монад (2)

          class MonadReturn(Exception):
    def __init__(self, value):
        Exception.__init__(self)
        self.value = value

def mreturn(value):
    raise MonadReturn(value)

        

call/cc

call/cc — продолжения как полноправные объекты.

          (+ 1 (call/cc
       (lambda (k)
         (+ 2 (k 3)))))

(+1 [])

        

k — остальная программа в момент call/cc, дырка [] в вычислении. Вызов продолжения покидает текущий контекст. См. Fixnum Days. Chapter 13.

break на call/cc

Другие продолжения можно выразить через call/cc:

          (call/cc
  (lambda (break)
    (for-each (lambda (x)
                (if (negative? x)
                    (break x)))
              '(54 0 37 -3 245 19))
    '()))

        

call/cc и нечитаемый код

• С помощью call/cc можно реализовать многие типы продолжений, если не все
• Но call/cc ведёт к очень запутанному коду, сложно следить за потоком управления
• Специальные синтаксисы для частых шаблонов продолжений очень помогают

Продолжения и параллельность

• Один из видов продолжений — зелёные нити
• Нужны для асинхронного NIO, моделирования, игр
• В кооперативной многозадачности — параллелизм управления, не данных
• Если несколько процессоров, нужны уже настоящие нити или даже процессы
• Тут применение call/cc, генераторов и т. д. не схватывает сути взаимодействия — асинхронного обмена сообщениями

Акторы

Кратко об истории

• Хьюитт придумал модель акторов
• Изучали Сассман и Стил, создали Scheme
• Недавно об акторах заговорили из-за Erlang

Взгляды на акторов

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

Мир акторов

• Актор — объект с состоянием и идентичностью, принимающий и отправляющий сообщения, создающий новых акторов
• Акторы естественно представляются как конечные автоматы
• Нет глобального состояния мира (Хьюитт привлёк теорию относительности ;)

Настоящее OOP

• Синхронный вызов метода в одном потоке управления — частный случай
• «I thought of objects being like biological cells and/or individual computers on a network, only able to communicate with messages». /Alan Kay/
• Слабость RPC как подхода
  • Есть разница между локальным и удалённым вызовом
  • Беда с синхронными вызовами
  • Где не работает RPC, работают сетевые протоколы

Почти общий случай в сетевых протоколах

• Вид трафика акторов
  • Без установления соединения, без временных характеристик, датаграммы, ненадёжная доставка
  • Но точка-точка и с проверкой целостности
• На акторах можно смоделировать почти любой протокол с индивидуальным вещанием
• Милое дело описывать протоколы как конечные автоматы и протокольные последовательности

Автомат протокола TCP

Источник: C-Workshop

Пример последовательности TCP

Источник: T/TCP — TCP for Transactions

Акторы на разных языках

• Рассматриваю способы реализации акторов, применимость для разных задач. Наброски и тесты в репозитории Mercurial
• Языки
  • Python
  • Haskell
  • Scheme
• Интересующие фичи
  • Зелёные и обычные нити
  • Асинхронные вызовы
  • Очереди сообщений
  • Затраты ресурсов
  • Таймауты ожидания

Акторы на Python

• Зелёные нити
  • Нити на двусторонних генераторах
  • Передача сообщений на изменяемых списках
• Нити ОС
  • Нити на threading
  • Передача сообщений на Queue
• Ограничения из-за функций-генераторов
• Зелёные нити в 10 раз медленнее, чем вызов процедуры

Ping pong на Python (1)

          def ping(pong, count):
    pid = yield
    for i in xrange(count):
        pong << (pid, i)
        msg = yield
        print 'ping: got %r' % msg
    pong << (pid, Terminate())

def pong():
    pid = yield
    while True:
        sender, msg = yield
        if isinstance(msg, Terminate):
            break
        else:
            print 'pong: got %r' % msg
            sender << 'pong back %r' % msg

        

Ping pong на Python (2)

          sched = SimpleScheduler() # or ThreadedScheduler()
o = sched.spawn(pong())
sched.spawn(ping(o, 10))
sched.start()
sched.stop()

        

Сопроцедурный планировщик на Python

          class SimpleScheduler(Scheduler):
    def __init__(self):
        self.msgs = []
    def send(self, receiver, msg):
        self.msgs.append((receiver, msg))
    def spawn(self, g):
        g_ = Pid(self, g)
        g_.next()
        g_.send(g_)
        return g_
    def start(self):
        while len(self.msgs) > 0:
            receiver, msg = self.msgs.pop(0)
            try:
                receiver.send(msg)
            except StopIteration: pass
    def stop(self): pass

        

Акторы на Haskell

• Зелёные нити
  • Нити на forkIO
  • Передача сообщений через Chan
• Нити ОС
  • Нити на forkOS
  • Передача сообщений через Chan
• Удивило отсутствие join нитей
• Хитрости с типами при мультиплексировании сообщений в один Chan

Ping pong на Haskell (1)

          data Ping = Ping String | Terminate
data Pong = Pong String

pong :: Actor (Pid Pong, Ping) -> IO ()
pong self = do
    (from, msg) <- receive self
    case msg of
        Ping str -> do putStrLn $ "pong: got " ++ str
                       from ! Pong ("pong back " ++ str)
                       pong self
        Terminate -> return ()

        

Ping pong на Haskell (2)

          ping :: Pid (Pid Pong, Ping) -> Integer -> Actor Pong -> IO ()
ping pong 0 self = do
    pong ! (getPid self, Terminate)
ping pong count self = do
    pong ! (getPid self, Ping (show count))
    msg <- receive self
    case msg of
        Pong str -> do putStrLn $ "ping: got " ++ str
    ping pong (count - 1) self

main = do
    o <- spawn pong
    i <- spawn $ ping (getPid o) 10
    join i
    join o

        

Реализация на Haskell (1)

          data Actor a = Actor {
    actorChan :: Chan a,
    actorMVar :: MVar ()
}

type Pid a = a -> IO ()

send :: Pid a -> a -> IO ()
send pid = pid

(!) = send

receive :: Actor a -> IO a
receive a = readChan $ actorChan a

        

Хак с MVar, т. к. нет join.

Реализация на Haskell (2)

          spawn :: (Actor a -> IO ()) -> IO (Actor a)
spawn f = do
    m <- newEmptyMVar
    c <- newChan
    let a = Actor c m in do
        forkIO ((f a) `finally` putMVar m ())
        return a

join :: Actor a -> IO ()
join a = takeMVar $ actorMVar a

getPid :: Actor a -> Pid a
getPid a = writeChan $ actorChan a

        

Пока нет newActor для обменов сообщениями вне очереди актора.

Акторы на Scheme

• Зелёные нити
  • Стандартных нет, наверное можно на call/cc
  • Стандартных нет, зависит от реализации нитей
• Нити ОС
  • Можно на SRFI 18, у меня на нитях PLT Scheme
  • Стандартных очередей нет, у меня на make-async-channel
• Много кода при анализе входящих сообщений

Таймер на Scheme

          (define (async-sleeper self)
  (let ((msg (recv self)))
    (if (message? msg)
        (let ((x (message-body msg)))
          (cond ((number? x)
                 (begin
                   (sleep x)
                   (send (message-from msg) '())
                   (async-sleeper self)))
                ((and (symbol? x) (eq? x 'done))
                 (begin
                   (display "sleep: done\n")
                   '()))
                (else (async-sleeper self))))
        (async-sleeper self))))

        

Интерфейсные функции на Scheme

В стиле Erlang. Выглядят как функции, что не очень хорошо (см. RPC). Надо бы свой синтаксис.

          (define (make-sleeper)
  (spawn async-sleeper))

(define (sleeper-sleep s count)
  (let ((self (new-pid)))
    (send s (cons self count))
    (recv self)))

(define (sleeper-stop s)
  (let ((self (new-pid)))
    (send s (cons self 'done))
    (join s)))

        

Хорошо выразить на акторах

На акторах весьма естественно выражаются следующие задачи:

• Файл в той же нити, в т. ч. и асинхронный IO (aio_read)
• Неблокирующий NIO с > 1K сокетами через select или poll в одной нити
• Пул нитей
• FFI
• События из GUI (hi Smalltalk)

(Хорошо бы показать диаграммы)

Пара идей

• Язык с IO через акторов
• Другой унифицированный интерфейс программ с внешним миром

Язык с IO через акторов

Можно представить потенциальный язык:

• Всё — либо чистая функция, либо актор
• Весь IO выполняется через системные акторы
• Пользовательские акторы тоже «внутри IO», они — конечные автоматы
• Функции не могут вызывать акторов
• Интерфейсные функции акторов — не функции, а специальные группы обменов

Интерфейс программ с внешним миром

• Интерфейсы программы с внешним миром
  • Файлы, сокеты, каналы и др. IPC, ioctl и др. syscalls (shmget не вспоминаем)
• Интерфейс может быть унифицированным, как файлы в Plan 9
• Унифицированный интерфейс может быть другим, например HTTP
  • Глобальные уникальные имена
  • «Файловая» система — граф, а не дерево
  • Динамические ресурсы, метаданные
  • Встроенные кэши, прокси, безопасность
  • Поддержка в любом языке, навыки веб-программистов
  • Но: с подтверждением, заголовочный overhead, непростые серверы