DIY Корутины. Часть 1. Ленивые генераторы

    В мире JVM про корутины знают в большей степени благодаря языку Kotlin и Project Loom. Хорошего описания принципа работы котлиновских корутин я не видел, а код библиотеки kotlin-coroutines совершенно не понятен неподготовленному человеку. По моему опыту, большинство людей знает о корутинах только то, что это "облегченные потоки", и что в котлине они работают через умную генерацию байткода. Таким был и я до недавнего времени. И мне пришла в голову идея, что раз корутины могут быть реализованы в байткоде, то почему бы не реализовать их в java. Из этой идеи, впоследствии, появилась небольшая и достаточно простая библиотека, в устройстве которой, я надеюсь, может разобраться практически любой разработчик. Подробности под катом.



    Исходный код


    Проект я назвал Microutines, что получилось из слов Micro и Coroutines.


    Весь код доступен на github. Изначально я хотел построить повествование в соответствии с развитием моего собственного понимания темы, рассказать о моих неправильных решениях и идеях, о развитии api, но тогда код в статье очень сильно бы отличался от кода с github (что в любом случае неизбежно, статью я пишу один раз, а на гитхаб комичу время от времени). Поэтому я в большей степени буду описывать конечный вариант библиотеки, и если некоторые части api не очень понятны с первого взгляда, то, скорее всего, они нужны для решения проблем, которые мы будем рассматривать в следующих статьях.


    Disclaimer


    Это своего рода учебный проект. Я буду рад, если кто-то из читателей склонирует его, чтобы поиграться или даже закинет пулл реквест. Но использовать его в продакшне не стоит. Лучший способ глубоко разобраться в какой-нибудь технологии — реализовать ее самому, в чем и заключается единственная цель этого проекта.


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


    Что такое корутины


    Как я уже заметил, про корутины часто говорят, что это "облегченные потоки". Это не совсем верное определение. Верного определения я правда тоже давать не буду, но попробую описать, какие они, корутины. Называть корутины потоками будет не совсем корректно. Корутина это меньшая чем поток единица планирования, а поток, в свою очередь, меньшая чем процесс единица планирования (scheduling). Планированием процессов и потоков занимается операционная система. Планированием корутин занимается… мы сами займемся их планированием. Корутины работают поверх обычных потоков, и их главная фишка в том, что они не блокируют поток, когда ждут выполнения какой-то другой задачи, а освобождают его для другой корутины. Такой подход называется кооперативной многозадачностью. Корутина может работать сначала в одном потоке, потом в другом. Поток для корутины выступает в роли ресурса, и миллион корутин может работать на одном единственном потоке. Вы могли видеть такую картинку:



    Задачи contribs 1 и contribs 2 выполняют какие-то запросы и на время ожидания ответов не блокируют поток, а приостанавливают свою работу и продолжают её уже после получения ответов. Мы можем написать такой код с помощью колбеков, скажете вы. Так и есть, но суть корутин в том, что мы пишем код без колбеков, мы пишем обычный последовательный код, который выполняется асинхронно.


    Генераторы


    Разработку начнем от простого к сложному. Первая вещь, которую мы сделаем, будет ленивая генерация коллекции, реализуемая в некоторых языках с помощью ключевого слова yield. Генераторы тут не случайно, как мы увидим дальше, и генераторы и корутины могут быть реализованы с помощью одного и того же механизма.


    Рассмотрим пример на python, просто потому что генераторы там есть из коробки.


    def generator():
        k = 10
        yield k
        k += 10
        yield k
        k += 10
        yield k
    
    for i in generator():
        print(i)

    Цикл разворачивается в нечто такое (может не совсем так, но нам важен принцип):


    gen = generator()
    while True:
        try:
            i = next(gen)
            print(i)
        except StopIteration:
            break

    Вызов generator() создаст особый итератор, который называется генератор. При первом вызове next(gen) выполняется код от начала функции generator до первого yield, и в переменную i запишется значение локальной переменной k из genertator(). Каждый следующий вызов next продолжит исполнение функции с инструкции, стоящей сразу за предыдущим yield и так далее. При этом между вызовами next сохраняются значения всех локальных переменных внутри generator.


    Вот примерно тоже самое, но на языке Kotlin.


    val seq = sequence {
        var i = 10 
        yield(i)
        i += 10
        yield(i)
        i += 10
        yield(i)
    }
    
    for (i in seq) {
        println(i)
    }

    На Java ленивую генерацию мы могли бы сделать как-то так:


    Iterable<Integer> seq = DummySequence.first(() -> {
        final int i = 10;
        return DummySequence.next(i, () -> {
                final int i1 = i + 10;
                return DummySequence.next(i1, () -> DummySequence.end(i1 + 10));
        });
    });
    
    for(int i: seq) {
        System.out.println(i);
    }

    Реализация DummySequence
    import org.junit.Assert;
    import org.junit.Test;
    
    import java.util.Iterator;
    import java.util.List;
    import java.util.function.Supplier;
    import java.util.stream.Collectors;
    import java.util.stream.StreamSupport;
    
    public class DummySequenceTest {
    
        @Test
        public void dummySequenceTest() {
            DummySequence<Integer> sequence = DummySequence.first(() -> {
                final int i = 10;
                return DummySequence.next(10, () -> {
                    final int i1 = i + 10;
                    return DummySequence.next(i1, () -> DummySequence.end(i1 + 10));
                });
            });
    
            List<Integer> list = StreamSupport.stream(sequence.spliterator(), false)
                    .collect(Collectors.toList());
    
            Assert.assertEquals(10, ((int) list.get(0)));
            Assert.assertEquals(20, ((int) list.get(1)));
            Assert.assertEquals(30, ((int) list.get(2)));
        }
    
        private static class DummySequence<T> implements Iterable<T>, Iterator<T> {
            private Step<T> step;
    
            public DummySequence(Step<T> step) {
                this.step = step;
            }
    
            @Override
            public Iterator<T> iterator() {
                return this;
            }
    
            @Override
            public boolean hasNext() {
                if (step instanceof EndStep)
                    return false;
                step = step.nextStep();
                return true;
            }
    
            @Override
            public T next() {
                return step.getValue();
            }
    
            public static <T> DummySequence<T> first(Supplier<Step<T>> next) {
                return new DummySequence<>(new FirstStep<T>(next));
            }
    
            public static <T> Step<T> next(T value, Supplier<Step<T>> next) {
                return new IntermediateStep<>(value, next);
            }
    
            public static <T> Step<T> end(T value) {
                return new EndStep<>(value);
            }
        }
    
        private interface Step<T> {
            T getValue();
    
            Step<T> nextStep();
        }
    
        public static class FirstStep<T> implements Step<T> {
            Supplier<Step<T>> nextStep;
    
            public FirstStep(Supplier<Step<T>> next) {
                this.nextStep = next;
            }
    
            @Override
            public T getValue() {
                throw new IllegalStateException();
            }
    
            @Override
            public Step<T> nextStep() {
                return nextStep.get();
            }
        }
    
        public static class IntermediateStep<T> implements Step<T> {
            T value;
            Supplier<Step<T>> nextStep;
    
            public IntermediateStep(T value, Supplier<Step<T>> nextStep) {
                this.value = value;
                this.nextStep = nextStep;
            }
    
            @Override
            public T getValue() {
                return value;
            }
    
            @Override
            public Step<T> nextStep() {
                return nextStep.get();
            }
        }
    
        public static class EndStep<T> implements Step<T> {
            T value;
    
            public EndStep(T value) {
                this.value = value;
            }
    
            @Override
            public T getValue() {
                return value;
            }
    
            @Override
            public Step<T> nextStep() {
                throw new IllegalStateException();
            }
        }
    }

    Каждая следующая вложенная лямбда захватывает все переменные из всех предыдущих лямбд и выполняется только при запросе следующего элемента. Результатом работы каждой лямбды будет сгененрированный элемент и следующий блок кода. Выглядит это очень странно, и я сомневаюсь, что кто-либо станет так писать. Обозначим идеал, к которому мы будем стремиться (и мы его достигнем, за исключением того, что вместо лямбд будем использовать анонимный класс).


    Sequence<Integer> sequence = new Sequence<Integer>(() -> {
        int i = 10; 
        yield(i);
        i += 10;
        yield(i);
        i += 10;
        yield(i);
    });

    Функция, переданная в конструктор Sequence, должна идти от yield к yield только при необходимости, значения локальных переменных должны сохраняться между вызовами sequence.next(). Вот это сохранение стека и номера последней выполненной инструкции называется вытеснение (yield так и переводится на русский) или приостановка.


    Континуации


    Штука, которая умеет вытесняться, называется Continuation. На русский continuation переводится как 'продолжение', но я буду называть ее континуацией. В Википедия про континуации написано:


    Продолжение (англ. continuation) представляет состояние программы в определённый момент, которое может быть сохранено и использовано для перехода в это состояние. Продолжения содержат всю информацию, чтобы продолжить выполнения программы с определённой точки.

    Предположим, что у нас уже каким-то волшебным способом реализован механизм континуаций, который представлен следующим интерфейсом. Метод run умеет останавливать свой выполнение. Каждый следующий вызов возобновляет выполнение с последнего yield. Можем думать о континуации как о Runnable, который умеет выполняться по частям.


    interface Continuation<T> {
        void run(SequenceScope<T> scope);
    }

    Континуацию мы будем использовать так:


    Sequence<Integer> sequence = new Sequence<>(new Continuation<>() {
        void run(SequenceScope<Integer> scope) {
            int i = 1;
            System.out.println("Continuation start");
            scope.yield(i++);
            System.out.println("Continuation resume");
            scope.yield(i++);
            System.out.println("Continuation resume");
            scope.yield(i++);
            System.out.println("Continuation end");
        }       
    });     
    
    for(Integer i: sequence) {
        System.out.println("Next element :" + i);
    }

    И мы ожидаем получить такой вывод:


    Output
    Continuation start
    Next element: 1
    Continuation resume
    Next element: 2
    Continuation resume
    Next element: 3
    Continuation end

    Sequence при запросе следующиего элемента будет вызывать Continuation.run(scope), который будет выполнять блок кода до следующего yield и вытесняться. Следующий вызов Continuation.run(scope) будет начинать работу с места последнего вытеснения и выполнять код до очередного yield. Код Sequence может быть таким:


    class Sequence implements Iterator<T>, SequenceScope<T>, Iterable<T> {
        private static final Object STOP = new Object();
        private Object next = STOP;
        private Continuation<T> nextStep;
    
        public Sequence(Continuation<T> nextStep) {
            this.nextStep = nextStep;
        }
    
        @Override
        public boolean hasNext() {
            if (next == STOP) {
                nextStep.run(this);
            }
            return next != STOP;
        }
    
        @Override
        public T next() {
            if (next == STOP) {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
            }
    
            T result = (T) next;
            next = STOP;
            return result;
        }
    
        @Override
        void yield(T t) {
            next = t;
        }
    
        public Iterator<T> iterator() { // сомнительная реализация, но сейчас это не имеет значения
            return this;
        }
    
    }
    
    interface SequenceScope<T> {
        void yield(T t);
    }

    Все прекрасно, кроме того, что java не умеет останавливать выполнение метода в произвольном месте, чтобы потом продолжить выполнение с места последней остановки. Поэтому нам придется сделать это вручную. Введем поле label, в котором будем хранить номер последнего вызванного yield.


    class IntegerSequenceContinuation implements Continuation<Integer> {
        private int label = 0;
        private int i = 0;
        void run(SequenceScope<Integer> scope) {
            int i = this.i;
            switch (label) {
                case 0:
                    System.out.println("Continuation start");
                    scope.yield(i++);
                    label = 1;
                    this.i = i;
                    return;
                case 1:
                    System.out.println("Continuation resume");
                    scope.yield(i++);
                    label = 2;
                    this.i = i;
                    return;
                case 2:
                    System.out.println("Continuation resume");
                    scope.yield(i++);
                    label = 3;
                    this.i = i;
                    return;
                case 3:
                    System.out.println("Continuation end");
                    label = 4;
                default:
                    throw new RuntimeException();
            }
        }
    }

    У нас получилась state machine (конечный автомат), и по большому счету именно это делает котлин в своих корутинах (можете декомпилировать и посмотреть, если, конечно, что-нибудь поймете). У нас есть 4 состояния, каждый вызов run выполняет часть кода и делает переход к следующему состоянию. Локальную переменную i нам приходится сохранять в поле класса. Кроме неоправданной сложности у этого кода есть еще одна проблема: мы можем передать в качестве параметра scope разные значения при каждом вызове run. Поэтому, хорошо бы, и параметр scope сохранить в поле класса при первом вызове, и дальше работать с ним.


    Континуация на java у нас реализована, но достаточно странным способом и только в одном экземпляре. Каждый раз писать нечто подобное никто не будет, редактировать такой код сложно, читать такой код сложно. Поэтому конечный автомат мы будем строить уже после компиляции.


    Suspendable & Continuation


    Как нам понять, завершила ли континуация работу или приостановила? Пусть метод run возвращает специальный объект SUSPEND в случае приостановки.


    public interface Continuation<T> {
        Object SUSPEND = new Object() {
            @Override
            public String toString() {
                return "[SUSPEND]";
            }
        };
    
        T run();
    }

    Заметим, что я убрал входной параметр у континуации. Мы должны гарантировать, что параметры не будут меняться от вызова к вызову, лучший способ сделать это — удалить их. Пользователю, напротив, нужен параметр scope (он будет много для чего использоваться, но сейчас на его место передается SequenceScope, из которого вызывается наш yield). Кроме того, ни про какой SUSPEND пользователь знать не хочет и не хочет ничего возвращать. Введем интерфейс Suspendable.


    public abstract class Suspendable<C extends Scope> {
        abstract public void run(C scope);
    }
    
    interface Scope {}

    Почему абстрактный класс, а не интерфейс?

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


    Suspendable это Continuation в дизайн тайме, a Continuation это Suspendable в рантайме. Пользователь пишет код на уровне Suspendable, а низкоуровневый код библиотеки работает с Continuation. Одно в другое превращается после модификации байткода.


    Прежде мы говорили про вытеснение после вызова yield, но в будущем нам надо будет вытесняться и после некоторых других методов. Будем помечать такие методы аннотацией @Suspend. Это применимо и к самому yield:


    public class SequenceScope<T> implements Scope {
        @Suspend
        public void yield(T t) {...}
    }

    Помним, что континуации у нас будут построены на конечных автоматах. Остановимся здесь немного подробнее. Конечным автомат называется, потому что у него конечное количество состояний. Для хранения текущего состояния будем использовать специальное поле label. Изначально поле label равно 0 — нулевое (начальное) состояние. Каждый вызов Continuation.run будет выполнять какой-то код и переходить в какое-то состояние (в любое кроме начального). После каждого перехода континуация должна сохранить все локальные переменные, номер текущего состояния и выполнить return SUSPEND. Переход к конечному состоянию будет обозначаться return null (в следующих статьях мы будем возвращать не только null). Вызов Continuation.run из конечного состояния должен завершаться исключением ContinuationEndException.


    Итак, пользователь пишет код в Suspendable, после компиляции он превращается в Continuation, с которым работает библиотека, и, в частности, наши генераторы. Создание нового генератора для пользователя выглядит так:


    Sequence<Integer> seq = new Sequence(new Suspendable() {...});

    Но самому генератору нужна континуация, ведь ему нужно проинициализировать поле Continuation<T> nextStep;. Для получения Continuation из Suspendable в коде я написал специальный класс Magic.



    package microutine.core;
    
    import microutine.coroutine.CoroutineScopeImpl;
    
    import java.lang.reflect.Field;
    
    public class Magic {
        public static final String SCOPE = "scope$S";
    
        private static <C extends Scope, R> Continuation<R> createContinuation(Suspendable<C> suspendable, C scope) {
            try {
                Field contextField = suspendable.getClass().getDeclaredField(SCOPE);
                contextField.setAccessible(true);
    
                if (contextField.get(suspendable) != null)
                    throw new IllegalArgumentException("Continuation already created");
    
                contextField.set(suspendable, scope);
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
    
            return getContinuation(suspendable);
        }
    
        public static <R, C extends Scope> Continuation<R> getContinuation(Suspendable suspendable) {
            if (getScope(suspendable) == null)
                throw new RuntimeException("No continuation created for provided suspendable");
            //noinspection unchecked
            return ((Continuation<R>) suspendable);
        }
    
        private static Scope getScope(Suspendable suspendable) {
            try {
                Field contextField = suspendable.getClass().getDeclaredField(SCOPE);
                contextField.setAccessible(true);
                return (Scope) contextField.get(suspendable);
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
    }

    Как эта магия работает? Параметром scope через рефлексию инициализируется поле scope$S (синтетическое поле, которое мы создадим уже в байткоде). Инициализируется континуация единственный раз в createContinuation, и повторная попытка инициализации приведет к эксепшну. Дальше происходит обыкновенное приведение типа к Continuation. Вообще я вас обманул, вся магия не здесь. Раз такое приведение типа возможно, то конкретный переданный Suspendable уже реализует Continuation. И произошло это во время компиляции.


    Структура проекта


    Проект будет состоять из трех частей:


    • Код библиотеки (Низкоуровневый и высокоуровневый API)
    • Тесты (Фактически, только в них сейчас можно использовать это библиотеку)
    • Конвертер Suspendable -> Continuation (Реализован в виде gradle таски в gradle buildSrc)

    Так как конвертер пока что находится в buildSrc, использовать его где-то за пределами самой библиотеки будет невозможно. Но пока нам это и не надо. В будущем у нас будет два варианта: вынести его в отдельный градл плагин, или сделать свой java agent (как это делает Quasar) и выполнять трансформации в рантайме.


    build.gradle
    plugins {
        id "java"
    }
    
    group 'microutines'
    version '1.0-SNAPSHOT'
    
    sourceCompatibility = 1.8
    
    task processYield(type: microutine.ProcessSuspendableTask) {
        classPath = compileJava.outputs.files + compileJava.classpath
        inputs.files(compileJava.outputs.files)
    }
    
    task processTestYield(type: microutine.ProcessSuspendableTask) {
        classPath = compileJava.outputs.files + compileTestJava.classpath
        inputs.files(compileTestJava.outputs.files)
    }
    
    compileJava.finalizedBy(processYield) // после компиляции запускаем байткод модификации
    compileTestJava.finalizedBy(processTestYield)
    
    repositories {
        mavenCentral()
    }
    
    dependencies {
        testCompile group: 'junit', name: 'junit', version: '4.12'
        compile group: 'junit', name: 'junit', version: '4.12'
    }

    Конвертацией Suspendable в Continuation будет заниматься градл таска ProcessSuspendableTask. В классе градл таски нет ничего интересного, она просто отбирает нужные классы и отправляет их на преобразование в класс SuspendableConverter. Именно он нас сейчас и интересует.


    Генерация байткода


    Для работы с байткодом будем использовать библиотеку OW2 ASM. Библиотека работает по принципу SAX парсера. Мы создаем новый ClassReader, скармливаем ему скомпилированный класс в виде массива байтов, и вызываем метод accept(ClassVisitor visitor). ClassReader будет парсить байткод и вызывать соответствущие методы у переданного визитора (visitMethod, visitClass, visitInsn). Визитор может работать в режиме адаптера и делегировать вызовы следующему визитору. Обычно, последним визитором является ClassWriter, в котором формируется конечный байткод. Если задача нелинейная (у нас как раз такая), может потребоваться несколько проходов по классу. Другой подход, предоставляемый asm — записать класс в специальный ClassNode, и делать преобразования уже над ним. Первый подход быстрее, но может не подойти для решений нелинейных задач, поэтому я использовал оба подхода.


    Преобразованием Suspendable в Continuation занимаются 3 класса:


    • SuspendInfoCollector — анализирует метод Suspendable.run, собирает информацию о всех вызовах @Suspend методов и об используемых локальных переменных.
    • SuspendableConverter — создает нужные поля, меняет сигнатуру и дескриптор метода Suspendable.run, чтобы получить Continuation.run.
    • SuspendableMethodConverter — преобразовывает код метода Suspendable.run. Дописывает код сохранения и восстановления локальных переменных, сохранения текущего состояния в поле label и перехода к нужной инструкции.

    Опишем некоторые моменты поподробней.


    Поиск метода run выглядит вот так:


    MethodNode method = classNode.methods.stream()
            .filter(methodNode -> methodNode.name.equals("run") && (methodNode.access & Opcodes.ACC_BRIDGE) == 0)
            .findFirst()
            .orElseThrow(() -> new RuntimeException("Unable to find method to convert"));

    Ожидается, что в конвертируемом классе будет два метода run, и один из них с модификатором bridge (что это такое читаем здесь). Нас интересует метод без модификатора.


    В JVM байткоде условный (и безусловный) переход можно выполнить в любое место. ASM имеет специальную абстракцию Label (метка), которая представляет собой позицию в байткоде. По всему коду после каждого вызова @Suspend методов мы расставим метки, к которым будем делать условный переход в начале метода run.


    
    @Override
        public void visitCode() { // событие начала метода
            super.visitCode();
    
            Label startLabel = new Label();
    
            super.visitVarInsn(Opcodes.ALOAD, THIS_VAR_INDEX); // Помещаем в стек this
            super.visitFieldInsn(Opcodes.GETFIELD, myClassJvmName, "label$S$S", "I");  //Запрашиваем поле label$S$S
            super.visitVarInsn(Opcodes.ISTORE, labelVarIndex); // Сохраняем поле в локальную переменную
    
            super.visitVarInsn(Opcodes.ILOAD, labelVarIndex); // помещаем переменную label в стек
            super.visitIntInsn(Opcodes.BIPUSH, 0); // помещаем 0 в стек
            super.visitJumpInsn(Opcodes.IF_ICMPEQ, startLabel); // делаем условный переход к метке startLabel если два последних значения в стеке равны (label == 0)
    
            for (int i = 0; i < numLabels; i++) { // делаем тоже самое, но для следующих меток
                super.visitVarInsn(Opcodes.ILOAD, labelVarIndex);
                super.visitIntInsn(Opcodes.BIPUSH, i + 1);
                super.visitJumpInsn(Opcodes.IF_ICMPEQ, labels[i]);
            }
    
            super.visitTypeInsn(Opcodes.NEW, "microutine/core/ContinuationEndException"); // run был вызван после завершения работы континуации, выкидываем эксепшн
            super.visitInsn(Opcodes.DUP);
            super.visitMethodInsn(Opcodes.INVOKESPECIAL, "microutine/core/ContinuationEndException", "<init>", "()V", false);
            super.visitInsn(Opcodes.ATHROW);
    
            super.visitLabel(startLabel); // метка, после которой начинается пользовательский код 
        }

    Расставляем метки после вызовов @Suspend методов.


    @Override
    public void visitMethodInsn(int opcode, String owner, String name, String descriptor, boolean isInterface) {
        boolean suspendPoint = Utils.isSuspendPoint(classLoader, owner, name);
    
        super.visitMethodInsn(opcode, owner, name, descriptor, isInterface);
        if (suspendPoint) {
            super.visitVarInsn(Opcodes.ALOAD, THIS_VAR_INDEX); // помещаем в стек this
            super.visitIntInsn(Opcodes.BIPUSH, suspensionNumber); // помещаем номер метки, в которую вернемся в следующий раз
            super.visitFieldInsn(Opcodes.PUTFIELD, myClassJvmName, "label$S$S", "I"); // сохранем ее в поле label$S$S
    
            saveFrame(); // сохраняем локальные переменные
    
            suspend(); 
            super.visitLabel(labels[suspensionNumber - 1]); // метка, в которую мы вернемся 
            restoreFrame(); // восстанавливаем локальные переменные
            suspensionNumber++;
        }
    }
    
    private void suspend() {
        super.visitFieldInsn(Opcodes.GETSTATIC, "microutine/core/Continuation", "SUSPEND", "Ljava/lang/Object;"); // помещаем в стек Continuation.SUSPEND
        super.visitInsn(Opcodes.ARETURN); // возвращаем его
    }

    Тесты


    Напишем генератор, который выдает подряд три числа.


    testIntSequence
    public class YieldTest {
        @Test
        public void testIntSequence() {
            Sequence<Integer> sequence = new Sequence<Integer>(new SequenceSuspendable<Integer>() {
                @Override
                public void run(SequenceScope<Integer> scope) {
                    scope.yield(10);
                    scope.yield(20);
                    scope.yield(30);
                }
            });
    
            List<Integer> list = new ArrayList<>();
            for (Integer integer : sequence) {
                list.add(integer);
            }
    
            assertEquals(10, (int) list.get(0));
            assertEquals(20, (int) list.get(1));
            assertEquals(30, (int) list.get(2));
        }
    }

    Сам тест ничего интересного не представляет, зато достаточно интересно декомпилировть class файл.


    testIntSequence decompiled
    public class YieldTest {
        public YieldTest() {
        }
    
        @Test
        public void testIntSequence() {
            class NamelessClass_1 extends SequenceSuspendable<Integer> implements Continuation {
                private SequenceScope scope$S;
    
                NamelessClass_1() {
                }
    
                public Object run(Object var1) {
                    int label = this.label$S$S;
                    SequenceScope var2;
                    if (label != 0) {
                        if (label != 1) {
                            if (label != 2) {
                                if (label != 3) {
                                    throw new ContinuationEndException();
                                } else {
                                    var2 = this.scope$S;
                                    this.label$S$S = 4;
                                    return null;
                                }
                            } else {
                                var2 = this.scope$S;
                                this.yield(30);
                                this.label$S$S = 3;
                                this.scope$S = var2;
                                return Continuation.SUSPEND;
                            }
                        } else {
                            var2 = this.scope$S;
                            this.yield(20);
                            this.label$S$S = 2;
                            this.scope$S = var2;
                            return Continuation.SUSPEND;
                        }
                    } else {
                        var2 = this.scope$S;
                        this.yield(10);
                        this.label$S$S = 1;
                        this.scope$S = var2;
                        return Continuation.SUSPEND;
                    }
                }
            }
    
            Sequence<Integer> sequence = new Sequence(new NamelessClass_1());
            List<Integer> list = new ArrayList();
            Iterator var3 = sequence.iterator();
    
            while(var3.hasNext()) {
                Integer integer = (Integer)var3.next();
                list.add(integer);
            }
    
            Assert.assertEquals(10L, (long)(Integer)list.get(0));
            Assert.assertEquals(20L, (long)(Integer)list.get(1));
            Assert.assertEquals(30L, (long)(Integer)list.get(2));
        }
    }

    Код очень сильно раздулся, большинство инструкций — это сохранение и восстановление стекового кадра (локальных переменных). Однако, он работает. Приведенный пример отлично бы работал и без ленивой генерации. Рассмотрим пример посложнее.


    fibonacci
    public class YieldTest {
        @Test
        public void fibonacci() {
            Sequence<Integer> sequence = new Sequence<>(new Suspendable<Integer>() {
                @Override
                public void run(SequenceScope<Integer> scope) {
                    scope.yield(1);
                    scope.yield(1);
    
                    int a = 1;
                    int b = 1;
    
                    while (true) {
                        b += a;
                        scope.yield(b);
                        a += b;
                        scope.yield(a);
                    }
                }
            });
    
            //noinspection OptionalGetWithoutIsPresent
            Integer tenthFibonacci = StreamSupport.stream(sequence.spliterator(), false)
                    .skip(9).findFirst().get();
    
            assertEquals(55, ((int) tenthFibonacci));
        }
    }

    Приведенный код генерирует бесконечную последовательность фибоначчи. Компилируем и декомпилируем:


    fibonacci decompiled
    public class YieldTest {
        public YieldTest() {
        }
    
         @Test
         public void fibonacci() {
             class NamelessClass_1 extends SequenceSuspendable<Integer> implements Continuation {
                 private SequenceScope scope$S;
                 private int aa$S;
                 private int ba$S;
    
                 NamelessClass_1() {
                 }
    
                 public Object run(Object var1) {
                     int label = this.label$S$S;
                     SequenceScope var2;
                     if (label != 0) {
                         if (label != 1) {
                             int var3;
                             int var4;
                             if (label != 2) {
                                 if (label == 3) {
                                     var2 = this.scope$S;
                                     var3 = this.aa$S;
                                     var4 = this.ba$S;
                                     var3 += var4;
                                     var2.yield(var3);
                                     this.label$S$S = 4;
                                     this.scope$S = var2;
                                     this.aa$S = var3;
                                     this.ba$S = var4;
                                     return Continuation.SUSPEND;
                                 }
    
                                 if (label != 4) {
                                     throw new ContinuationEndException();
                                 }
    
                                 var2 = this.scope$S;
                                 var3 = this.aa$S;
                                 var4 = this.ba$S;
                             } else {
                                 var2 = this.scope$S;
                                 var3 = 1;
                                 var4 = 1;
                             }
    
                             var4 += var3;
                             var2.yield(var4);
                             this.label$S$S = 3;
                             this.scope$S = var2;
                             this.aa$S = var3;
                             this.ba$S = var4;
                             return Continuation.SUSPEND;
                         } else {
                             var2 = this.scope$S;
                             var2.yield(1);
                             this.label$S$S = 2;
                             this.scope$S = var2;
                             return Continuation.SUSPEND;
                         }
                     } else {
                         var2 = this.scope$S;
                         var2.yield(1);
                         this.label$S$S = 1;
                         this.scope$S = var2;
                         return Continuation.SUSPEND;
                     }
                 }
             }
    
             Sequence<Integer> sequence = new Sequence(new NamelessClass_1());
             Integer tenthFibonacci = (Integer)StreamSupport.stream(sequence.spliterator(), false).skip(9L).findFirst().get();
             Assert.assertEquals(55L, (long)tenthFibonacci);
         }
    }

    Понять что делает декомпилированный класс достаточно сложно. Как и в прошлый раз, большинство инструкций гоняют туда сюда локальные переменные. Некоторые из присвоений бесполезные, и переменные сразу перетираются другими значениями. Для решения этой проблемы требуется более глубокий анализ байткода, который сейчас мы делать не будем.


    Одной из интересных особенностей полученного кода является отсутствие цикла while, хотя он есть в исходном коде. Ничего удивительного в этом нет. Тело цикла состоит из двух состояний конечного автомата. В конце тела цикла в байткоде должен стоять безусловный переход к коду проверки условия, но у нас оно 'разбито' двумя return SUSPEND.


    Резюме


    Задача, которую я поставил, на мой взгляд, выполнена весьма хорошо. Мы реализовали возможность писать ленивые генераторы через yield. Это может быть очень удобно как в примере с числами фибоначчи, но реальный код, который мы получаем на выходе — монструозен, непонятен и неоптимален. Проблемой я бы назвал только неоптимальность, но решать ее (по крайней мере ближайшее время) мы не будем. Можно понадеяться, что разогретый JIT компилятор сам пропустит бесполезные присвоения. Кроме yield я реализовал yieldAll — метод, который позволяет вкладывать одну последовательность в другую, но я не стал разбирать принцип его работы, потому что он прост до безобразия и без проблем реализуется поверх всего того, что мы уже сделали. Если все написанное до этого момента вам понятно, то вы без труда разберетесь сами, если загляните на гитхаб.


    Самая сложная часть всей библиотеки — континуации — практически полностью реализована, и фактически является синтаксическим сахаром. Построение генераторов поверх континуаций в принципе дело достаточно простое, а для создания корутин осталось уже не так много. Я надеюсь, что уже на этом этапе ясна связь корутин и генераторов: и там и там пишется последовательный код, который выполняется асинхронно.

    Haulmont
    Создаем современные корпоративные системы

    Комментарии 22

      0
      как вы расцениваете свой проект по сравнению с ea-async и coroutines in pure java?
        +1
        Если посмотреть на coroutines in pure java, то он больше похож на то что я обозвал DummySequence, разработчик должен сам явно обособлять каждое состояние из конечного автомата в отедльный шаг. Не думаю, что это удобно.
        То что сделал я, гораздо больше похоже на ea-async, но у них нет поддержки yield. Зато их решение production-ready.
        +2

        Спасибо за статью! На мой взгляд, покрыто более-менее все однопоточное — continuation, state-machine, spilling-unspilling локальных переменных. Осталось только покрыть ContinuationInterceptor и вся магия котлиновских корутин развеется.


        Хорошего описания принципа работы котлиновских корутин я не видел.

        Видели ли вы мою лекцию по котлиновским корутинам, которую я читал на Физтехе: https://www.youtube.com/watch?v=UzzH4biTEbY?

          +1
          Лекцию не видел, посмотрю, спасибо!

          покрыто более-менее все однопоточное
          Многопоточное будет во второй части, но в либе все уже есть, в некотором жизнеспособном виде.
          0
          У нас получилась state machine (конечный автомат), и по большому счету именно это делает котлин в своих корутинах (можете декомпилировать и посмотреть, если, конечно, что-нибудь поймете).
          Спасибо, ради этого я и продирался через половину статьи. Всё оказывается не так сложно. Выбрали путь скрытого глубокого препроцессинга с преобразованием синтаксиса.
            +2
            Да другого пути особо и не было, ведь котлин запускается в jvm, в котором нет континуаций. А вот project loom пошел по пути пропатчить рантайм, но там все намного сложнее.
            +1
            Спасибо, сам хотел писать что-то вроде, но теперь не буду, потому что ваша статья гораздо лучше :) Сам я копался в теме, но разобрался примерно на 1/3 от того, что у у вас написано. Пытаясь понять дзен континуаций (а для этого реализовать их на том языке, что имеется) я дошел примерно до того места, где у вас в статье находится IntegerSequenceContinuation. То есть управляющая конструкция у меня выглядела примерно как
            if (step.equals(^_^quotquot^_^) {
            ...
            }
            else if (step.equals(^_^quotquot^_^) {
            ...
            }
            //todo: сделать по-нормальному, а пока добавлять шагов столько, сколько надо
            

            , а то, что играло роль переменных стэка, я сохранял вообще в БД. Ну, чисто ради proof of concept.

            До нормальной технической реализации (генерация байт-кода это для меня черная магия) я не дошел, но слова «multiple stacks» и «континуации позволяют писать асинхронный код как синхронный» стали менее загадочными.

            Честно говоря, не знаю, хорошо или плохо, что технология вырулила на этот путь, где мы сейчас находимся (React, Angular, JSON, shadow DOM, change detection, вот это вот все). Как разработчику мне ясно, что синхронный код писать значительно проще, чем асинхронный («реактивный»). В альтернативной истории мы, может быть, разрабатывали бы сейчас веб-приложения на чем-то вроде Seaside, где континуации встроены были с самого начала. Или вообще на каком-нибудь LISP-фреймворке с call/cc.
              0
              Встретилось знакомое слово — автомат… А это то, что я просто обожаю. Ниже код так, как я писал бы, пишу (прошу прощения на С++) и использую автоматы. И только, написав свой код, прочитав статью, я только утвердился в мысли, что другие языки меня, думаю, еще долго не будут интересовать (в практическом смысле). Уже за это спасибо. А то, когда читаешь… котлин, роутины и т.д. и т.д. чувствуешь себя несколько, что там скрывать,… отсталым и несколько туповатым. Хотя, не исключаю, что, возможно, так оно и есть (это я так, похоже, комплексую из-за С++?)…
              А теперь буквально пару слов по делу. Только написав аналог, я понял сколько и какие можно задать вопросы по поводу подобной «роутины». И их довольно много. Но если в рамках моего кода, который их содержит (как и исходный код), я знаю ответы, то про исходный код?.. То, что на С++ для меня очевидно, тривиально, подобные «облегченные потоки» — это какой-то «вынос мозга»… И как мне после этого бросать С++?
              Код автоматов на С++
              LArc TBL_gen[] {
              	LArc(^_^quotquot^_^, ^_^quotquot^_^, "--", "y1"),
              	LArc(^_^quotquot^_^, ^_^quotquot^_^, "--", "y2"),
              	LArc(^_^quotquot^_^, ^_^quotquot^_^, "--", "y2"),
              	LArc()
              }
              class generator(): public LFsaAppl
              {
              public:
              	generator():LFsaAppl(TBL_gen) {}
              	int k;
              	void y1() { k = 10; }
              	void y2() { k +=10; }
              }
              
              LArc TBL_for[] {
              	LArc("f", "f", "^x1", "y1"),
              	LArc()
              }
              class ForFor(): public LFsaAppl
              {
              public:
              	generator *gen;
              	ForFor():LfsAppl(TBL_for) {}
              	int x1() { return gen->FGetState() == ^_^quotquot^_^; }
              	void y1() { print (gen->i); }
              }
              


              Можете кидать в меня «какашками», но я не столько для критики написанного, а больше о том, что где-то есть и другая жизнь… С другими автоматами… На «каменно-топорном» С++…
                +1

                Когда будете переползать на C++20 и попытаетесь понять, как работают горрутины, вспомните эту статью.

                0
                Зачем же так путать и пугать мудреными словечками… Нет, чтобы написать просто и по-русски...:( Все же, почувствовав подвох, я набрал в поиске «сопрограммы и корутины». Сразу же вышел на статью: Сопрограммы в Python (https://habr.com/ru/post/196918/) и… Им же лет 60 минимум, как о них пошли разговоры! Можно же было, в конце концов, за эти годы придумать что-то и получше?.. Неужели, чтобы понять, что автоматы перекрывают «с головой» сопрограммы и многопоточность, нужно столько бродить «по пустыне» и так и не набрести?
                Может, лучше сразу реализовать автоматы? Не пробовали?
                  +2

                  С разморозкой. Корутины уже не те, что были 60 лет назад.
                  Я как-то уже пошутил про те корутины, которые были 60 лет назад: https://youtu.be/UzzH4biTEbY?t=117.


                  Может, лучше сразу реализовать автоматы? Не пробовали?

                  Может, сразу писать на ассемблере? Не пробовали? Компилятор, в отличие от человека, более внимателен и всегда правильно расставит переходы между состояниями автомата, даже в случае сложного потока управления. И у меня еще был бы вопрос к читаемости получившегося кода, но я привык читать байткод корутин, который генерируется котлиновским компилятором. Вы, кстати, пытались отлаживать кучу автоматного кода? А это то, что я делаю по работе, когда мне присылают баг с прикрепленной ссылкой на гитхаб. Ибо даже минимизировать код, воспроизводящий баг не так-то просто. Да, я тоже человек и мой код тоже содержит ошибки, но после их исправления я могу быть уверен, что в подобных случаях автоматы, генерируемые компилятором будут валидными. Если бы я писал их руками каждый раз и заставлял бы своих пользователей писать их руками, никто бы не использовал корутины.


                  И сделайте, пожалуйста, что-то вроде structured concurrency https://vorpus.org/blog/notes-on-structured-concurrency-or-go-statement-considered-harmful/ на голых автоматах. На корутинах же его возможно сделать (пруф: kotlinx.coroutines).

                  0
                  А чем нынешние принципиально отличаются от тех — прошлых. Там были сопрограммы, а ныне — корутины? Названием? Языком? В Вашем видео плохой звук и как-то сложно себя заставить вникнуть, чтобы разобраться в таком, на мой взгляд, весьма тривиальном вопросе — сопрограммы. Можно как-то кратко сформулировать отличие? Принципиальное. Вне привязки к языку.

                  Когда-то мои автоматы были, действительно, на ассемблере. Точнее интерпретатор автоматов. Сейчас на С++ и, конечно, медленнее, но есть масса других преимуществ. Код теперь понятнее, компактнее, но, главное, скорости — «за глаза». Даже для управления в реальном времени. А язык — не принципиально. Был ассемблер, затем С, а сейчас С++. Последний в сравнении с первым, конечно, лепота. Ну и что. Идея-то что там, что там — одна.

                  По поводу генерации компиляторами. Автомат я ему не доверю. И не уговаривайте :) Таблицу переходов (ТП) и код действий пишу сам (см. приведенный пример). Компилятор создает только удобную структуру ТП, которую исполняет интерпретатор. Он реализует любой автомат, как отдельный процесс, а любое их множество — как множество параллельных процессов. Валидность, отладка — просто мечта многопоточного программиста! Любую «кучу автоматов» разгребаю легко и просто. Делал это тысячекратно, наверное;)

                  Что такое «голый автомат»? Голый, возможно, и не сделает, а нормальные автоматы — все что угодно и влет. Только такими автоматами и только этим и занимаюсь. И пока не было проблем. От слова — совсем ;) От сопрограмм отказался еще до заморозки, а многопоточностью не пользуюсь и после оттайки :) Правда, вот пришлось немножко позаниматься и ею. Не все, к сожалению, влезает в один поток. Да и то пока отложил, т.к. не понадобилось что-то…

                    +3
                    Код теперь понятнее, компактнее

                    Вот вы и ответили на свой же вопрос


                    Может, лучше сразу реализовать автоматы?

                    Сравните


                    suspend fun dummy() {}
                    
                    suspend fun bar() {
                        for (i in 1..10) {
                            dummy()
                        }
                    }

                    С получившимся


                       @Nullable
                       public static final Object dummy(@NotNull Continuation $completion) {
                          return Unit.INSTANCE;
                       }
                    
                       @Nullable
                       public static final Object bar(@NotNull Continuation $completion) {
                          Object $continuation;
                          label35: {
                             if ($completion instanceof <undefinedtype>) {
                                $continuation = (<undefinedtype>)$completion;
                                if ((((<undefinedtype>)$continuation).label & Integer.MIN_VALUE) != 0) {
                                   ((<undefinedtype>)$continuation).label -= Integer.MIN_VALUE;
                                   break label35;
                                }
                             }
                    
                             $continuation = new ContinuationImpl($completion) {
                                // $FF: synthetic field
                                Object result;
                                int label;
                                int I$0;
                                int I$1;
                    
                                @Nullable
                                public final Object invokeSuspend(@NotNull Object $result) {
                                   this.result = $result;
                                   this.label |= Integer.MIN_VALUE;
                                   return JvmKt.bar(this);
                                }
                             };
                          }
                    
                          Object $result = ((<undefinedtype>)$continuation).result;
                          Object var5 = IntrinsicsKt.getCOROUTINE_SUSPENDED();
                          int i;
                          int var2;
                          switch(((<undefinedtype>)$continuation).label) {
                          case 0:
                             ResultKt.throwOnFailure($result);
                             i = 1;
                             var2 = 10;
                             break;
                          case 1:
                             var2 = ((<undefinedtype>)$continuation).I$1;
                             i = ((<undefinedtype>)$continuation).I$0;
                             ResultKt.throwOnFailure($result);
                             ++i;
                             break;
                          default:
                             throw new IllegalStateException("call to 'resume' before 'invoke' with coroutine");
                          }
                    
                          while(i <= var2) {
                             ((<undefinedtype>)$continuation).I$0 = i;
                             ((<undefinedtype>)$continuation).I$1 = var2;
                             ((<undefinedtype>)$continuation).label = 1;
                             if (dummy((Continuation)$continuation) == var5) {
                                return var5;
                             }
                    
                             ++i;
                          }
                    
                          return Unit.INSTANCE;
                       }

                    Что понятнее и компактнее?


                    Можно как-то кратко сформулировать отличие? Принципиальное. Вне привязки к языку.

                    Там же большими буквами название статьи: "Design of a Separable Transition-Diagram Compiler". И там как раз дается определение корутин тогдашних. В чем отличие тогдашних корутин от тогдашних сопрограм? Его нет — это два способа назвать одно и то же. Вот оно, определение, кстати:
                    Modules which communicate with each other according to the following restrictions:
                    (I) the only communication between modules is in the form of discrete items of information;
                    (2) the flow of each of these items is along fixed, one-way paths;
                    (3) the entire program can be laid out so that the input is at the left extreme, the output is at the right extreme, and everywhere in between all information items flowing between modules have a component of motion to the right.
                    Сравните это с определением современных корутин: suspendable unit of computation.


                    По поводу генерации компиляторами. Автомат я ему не доверю.

                    Могу я узнать причину кроме "я не доверяю компиляторам, лучше уж я ручками"?


                    Он реализует любой автомат, как отдельный процесс.

                    То есть у вас по сути акторы. Что опять же, не равно корутинам. Отличие от корутин — корутины могут общаться не только методом передачи сообщений.


                    нормальные автоматы — все что угодно и влет

                    "Настоящий шотландец такого никогда не сделает", ага. Если вы такое утверждаете (на автоматах можно сделать structured concurrency), то, разумеется, у вас есть пруфы. "Где пруфы, Билли, нам нужны пруфы".


                    И да, под сообщением есть ссылка "ответить". Не имеет смысла каждый новый ответ писать на верхнем уровне комментариев.

                      0
                      Сравните это с определением современных корутин: suspendable unit of computation.

                      Прошу прощения, я после заморозки и с английским туговато. Давайте больше на русском общаться. Так избежим толкований и быстрее разберемся. Пока я не уловил не то, что разницы, а даже сходства. Потоки тоже приостанавливаются. Они тоже корутины? Но то, что потоки не сопрограммы это, надеюсь, еще не поменялось?
                      Могу я узнать причину кроме «я не доверяю компиляторам, лучше уж я ручками»?

                      Алгоритм (логику его работы) пишет всегда программист. Только поэтому. Конечно, есть методы, например, автоматического распараллеливания, генетические алгоритмы или нейронные сети там или что-то этому подобное, но… все это «от лукавого». Искусственного интеллекта еще нет и будет ли он когда-нибудь? Так что пока автоматы приходится пилить самому :(
                      То есть у вас по сути акторы.

                      У меня — автоматы. Точнее автоматные процессы. Т.е. это обычные процессы, в которых вместо модели блок-схем используется модель автомата (таблица переходов автомата). Т.е. вместо if, else и т.п. ТП, как в коде примера. Для описании логики процесса я не использую обычные операторы управления. Состояния КА — это, можно сказать, и есть точки приостанова вычислений, чтобы передать управление другому автомату и т.д.
                      Общаются между собой автоматы любыми известными способами. Хоть сообщениями, хоть через переменные, могут использовать текущие состояния, глобальные переменные, локальные свойства объектов и т.д. и т.д. Т.е. ограничений на общение нет, все те общения, что доступны в рамках потока (да хоть между потоками), те и могут использоваться.
                      разумеется, у вас есть пруфы.

                      Не знаю Не знаком. Может есть. Поясните безграмотному, что такое пуфы.
                      Более того. Если много автоматов работают параллельно в одном потоке, то и приостановка и возобновление вычислений такое же, как у сопрограмм: выхожу из одной точки и возвращаюсь в ту же. А вот логика (алгоритм) работы процесса представлен автоматом.
                      PS
                      Уж коли речь зашла о событиях…
                      Отличие от корутин — корутины могут общаться не только методом передачи сообщений.

                      Посмотрите мою статью на хабре, как к подобным вещам отношусь — habr.com/ru/post/483610.
                        +3

                        Вот корутины — это то, что вы описали, только генерируется компилятором. Каждое состояние — это либо вызов другой корутины либо явное указание, что здесь можно уснуть и передать управление другой корутине и при каком условии надо эту корутину разбудить.


                        Плюс корутин, по сравнению с автоматным программированием (термин, который я встречал только в отечественном computer science, на западе такого термина нет. Если и был, то он изжил себя. Там ему и место — на свалке истории) в том, что не надо самостоятельно строить автомат. Это сделает компилятор. Точно так же, как от программ с кучей переходов по меткам перешли на структурное программирование, а переходы теперь расставляет компилятор, так и от ручного построения автоматов в 60-80-х перешли на генерацию автоматов компилятором. И даже этого недостаточно. Structured concurrency (даже не просите перевести, не могу. В русском языке нет аналогичного понятия. И даже термин сопрограммы ужасен с точки зрения семантики, потому что программа все равно одна, чему там "со-". Поэтому я использую кальку "корутины", которую можно перевести как "софункции" или "сопроцедуры") решает те же проблемы, что и структурное программирование решало во времена Дейктры — делает понимание чужого кода более простым. Основная идея в том, что если поток/корутина запускает несколько других потоков/корутин, то он/она должен/должна дождаться их работы. Это очень сильно облегчает параллельное и асинхронное программирование, в частности, упрощает обработку ошибок, так как количество состояний, в котором может пребывать программа, уменьшается.


                        Сейчас разница между корутиной и потоком становится все более и более размытой. В go, D, raku и в назревающем loom (жалко, что я не пишу этот комментарий по-английски, могла бы быть неплохая игра слов), например, корутины ведут себя практически как потоки. Их становится не отличить. В kotlin, c++20, javascript, C# и rust разница между корутинами и потоками еще остается явной.


                        Пруф — ссылка на код, который реализует structured concurrency, желательно, неявно. Хотя неявно в автоматном программировании невозможно — это все равно, что программировать на языке ассемблера без макроассемблера, ручками считая адреса переходов.

                          –2
                          Сейчас разница между корутиной и потоком становится все более и более размытой.

                          Это в принципе не верно. Есть 1) поток/потоки, которые не являются по определению вычислительными моделями 2) сопрограммы, которые в сравнении с потоками вводят точки приостанова/возобновления вычислений, но тоже не модель вычислений 3) есть блок-схемы/автоматы, которые формируют вычислительную модель.
                          Как может «размываться» то, что в принципе не смешивается. В данном случае (3) используется для реализации (1) и (2). Из этого и надо строго исходить. Могут быть разные подходы к реализации, порождающие тот или иной язык, то это только так — автоматы (речь о них) реализуют потоки, автоматы реализуют сопрограммы, но никак наоборот. Это азы теории. Если рассуждать по-другом, то и будет та самая «размытая каша».
                          Вы упомянули параллельное и асинхронное программирование, которое что-то там облегчает реализовать. Те же «корутины». Чтобы понять, как они это делают, нужны формулировки понятий параллельного и асинхронного программирования. А есть еще и синхронное программирование. Чем оно отличается от упомянутых двух? (Нет параллельного И асинхронного программирования. Есть параллельное программирование, которое может быть асинхронным или синхронным). И какая здесь роль «корутин». Понятно как создать любую параллельную модель (синхронную, асинхронную и т.п.) с помощью автоматов. Но ни потоки, ни сопрограммы не являются вычислительными моделями. Они вводят лишь некую структурную организацию в вычисления. И не более того. С их помощью ничего нельзя вычислить. Вычисления создает блок-схемная модель (автоматы Вы не используете), которую вы и «размываете» между потоками и сопрограммами. Вот «на пальцах» процесс работы всего это «серпентария». Все остальная «реализация» — от лукавого. Под капотом может быть все что угодно. Чтобы отделить «мух от котлет» нужно именно этим и руководствоваться, а не смешивать все в одну кучу.
                          Там ему и место — на свалке истории
                          «Этого не может быть потому, что этого быть не может». Просто потому, что его «история» только начинается. Это UML, это Stateflow в MATLAB. И то это только-только начало. Не спешите «выплескивать» то, что еще только нарождается.
                          И давайте меньше оглядываться на «запад», а больше работать своей головой, создавая адекватные, понятные русскоязычные понятия. А то все эти «пруфы», «корутины» и т.п. только мешают понять смысл обсуждаемого да и как-то смешно звучат (какие-то песенки Винни-Пруфа).
                            +2
                            Это в принципе не верно.

                            Назовите хотя бы одну ОС, в которой потоки/треды реализованы не через приостановку вычислений вне зависимости от того, что этот поток сейчас делает. Где здесь автомат? ОС может остановить поток в (теоретически) любой ассемблерной инструкции. Или вы каждую инструкцию собираетесь сделать состоянием в автомате?


                            Есть параллельное программирование, которое может быть асинхронным или синхронным

                            А как быть с однопоточной асинхронной моделью (как вы могли про нее не слышать? В каком манямирке вы живете?). И, разумеется, многопоточный != параллельный. Вот хорошее объяснение: https://codewala.net/2015/07/29/concurrency-vs-multi-threading-vs-asynchronous-programming-explained/.


                            Вычисления создает блок-схемная модель

                            Да хоть Господь Бог. Это не имеет значения ни для потоков, ни для корутин. Почти любой код можно преобразовать в приостанавливаемый. Посмотрите, как те же корутины реализованы в go. В kotlin они реализованы с явными точками останова, но это особенности реализации, иначе было сделать нельзя. В go же таких проблем нет и там нет явных точек останова, совсем как в потоках. Где, черт возьми, здесь автоматы?


                            И давайте меньше оглядываться на «запад»,

                            А давайте вы не будете разглагольствовать с умным видом о том, в чем очевидно не разбираетесь. У меня еще была надежда, что вы просто ни разу не программировали на языке с корутинами, но эта надежда уже развеялась после "автоматы реализуют потоки, автоматы реализуют сопрограммы". Это уже давно не так, и, скорее всего, лет как минимум 40 не так. Те же потоки линукса как пруф (возьмите любой словарь английского, хоть 50-го года издания и посмотрите значение слова proof).


                            Это азы теории.

                            Когда теория расходится с наблюдениями, теорию принято дополнять, а не игнорировать наблюдения. Это азы эпистомологии.


                            больше работать своей головой

                            Я за. Только когда это работает в обе стороны. Давайте вы сначала посмотрите как реализованы корутины хотя бы в двух языках, скажем, в kotlin и go, а также как реализованы потоки в линуксе, найдете 10 отличий корутин в go от потоков в линуксе, потом мы возобновим беседу, иначе это разговор немого с незнающим.


                            И да, я не могу игнорировать "запад", я живу на "западе". И я все еще не увидел реализации structured concurrency на автоматах. Ответы без ссылки на реализацию я буду впредь игнорировать. Не вижу смысла спорить без железных аргументов, ваши "верю-не верю, ибо это, мой взгляд, азы" за железные аргументы не сойдут.

                              –2
                              Назовите хотя бы одну ОС, в которой потоки/треды реализованы...

                              У Вас перемешаны логическое описание и его реализация. На уровне представления потоки не приостанавливаются нигде. На уровне реализации — везде. Мысль понятна? На уровне логического описания потоки и в Африке потоки. Как они реализованы, что там «под капотом» меня совершенно не интересует. Это дело разработчиков реализовать корректно идею тех же потоков, сопрограмм, корутин, автоматов и далее по списку. Как еще Вам это сказать. Вы тянете меня в реализацию, в разные языки, но мне это «до фонаря», т.к. важно, чтобы рассматриваемая абстракция везде работала одинаково. Еще раз — одинаково. Да, язык ее описания может различаться, но логика работы — нет.
                              А давайте вы не будете разглагольствовать с умным видом о том, в чем очевидно не разбираетесь. У меня еще была надежда, что вы просто ни разу не программировали на языке с корутинами...

                              Еще раз и еще раз я использую автоматную модель. Примитивные вещи вроде потоков и корутин мне не нужны ни разу. Ну, совсем. Автоматное программирование все это покрывает, «как бык овцу». Собственно своим приведенным примером я это и показал.
                              И я все еще не увидел реализации structured concurrency на автоматах.
                              Когда Вы разберетесь наконец-то с этим понятием и опишите его на великом и могучем, чтобы его можно было трактовать однозначно, то, заверяю Вас, увидите сразу же. Автоматы, как аналог машины Тьюринга, реализует все, что могут придумать и задумать Ваши «западные мозги». Это доказано ими же (мозгами самого Тьюринга). Потоки и корутины не эквивалентны ни какой машине. Поэтому в чистом виде они ограничены по определению. Чтобы что-то сделать осмысленное Вы разбавляете их моделью блок-схем. Вот и все «на пальцах». Как все это реализовано — программно, аппаратно, ездит на бензине, жрет ли солому — без разницы. Главное, чтобы реализовало задуманное на уровне своего представления. И какие при этом будут проблемы — вот, что важно. Как будет реализовано — не важно. Это обязанность разработчика, чтобы все работало одинаково в любой ОС и на любом языке. Причем так, чтобы у меня не было желания лезть под капот. Мне главное доехать. И чтобы машины с точки зрения управления ими были одинаковы. Когда все «размыто», то не ясно чего ожидать от самой продвинутой «машины». Если продолжить ассоциацию, то потоки — машины, которые едут только прямо, корутины — прямо, но приостанавливаясь, и только автоматы имеют полную свободу передвижения (как у товарища Тьюринга).
                                +1
                                Поток это последовательность инструкций, которые выполняются друг за другом. Инструкции могут быть как на тьюринг полном языке, так и нет. Утверждение «Потоки эквивалентны (не эквиваленты) машине Тьюринга» не несет смысла. Это как сравнивать кислое и квадратное.
                                  0
                                  Это как сравнивать кислое и квадратное.

                                  Вы правы. Сравнивать несравнимое лучше не надо. Но тут вынужденно ;) Только я бы сказал так — дорогу и машину. Или дорогу с пробками и машину, если речь про «корутины». А вот автоматы и есть та самая машина, а множество автоматов — множество машин ;)
                    0
                    Кстати… Что-то в коде моего примера первая ТП совсем извратилась (имена состояний). И как поправить — не знаю :( Но вторая таблица переходов отобразилась нормально. Похоже, имена состояний в виде цифр воспринимаются как-то своеобразно. Знал бы — использовал буковки ;)
                      –3
                      Заинтересовала реклама книги на Хабре: C++. Практика многопоточного программирования. habr.com/ru/company/piter/blog/484818. Хотел прикупить хотя бы электронный вариант. Но перед этим в инете нашел предыдущее издание — 2012 года. В новом, похоже, термин «параллелизм» заменили на «конкурентность», а «многопоточнось» на «параллелизм». Желание резко улетучилось. А все от того, что кое-кто берется за переводы, не разобравшись в смысле того, что переводит. Все это напомнило наши «терминологические споры»… «Конкурентный корутинизм» какой-то…
                      И еще. Ни в одном из изданий (в первом так точно) ни про корутины, ни про сопрограммы нет ни слова. Поэтому, предлагая реализацию «корутин», нужно привести более весомые аргументы в пользу необходимости заниматься ими. Т.к. по словам одних корутины «размываются» с потоками, т.е. мигрируют в их сторону, а те, кто рассматривает потоки, похоже, корутины игнорируют напрочь.
                      Может лучше потратить силы на реализацию чего-то более полезного и понятного?

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое