Сопрограммы в языке программирования C

[npak]

npak, как вариант, почему бы тогда не попробовать написать микроядро на Си? по крайней мере платформо-независимую часть

Да, я, наверное, слишком общё выразился. На асме надо написать микро-микро ядро
Что в него должно войти - обработка прерываний, работа с блоками памяти (memcpy/memmove/memset/memcmp), создание и переключение контекстов
Все остальное - планировщик, динамическая память, порты ввода-выввода - можно написать машинно-независимо на С/С++

[RXL]

2. Рекомендую изменить название на менее общее

Если большинство будет "за", то я не против, конечно... Хотя в заголовке обещали сопрограммы на С, начинаем читать - а там и правда сопрограммы на C. Вроде и не обманули.
м анекдоте про песни "Битлз" в перепевке Рабиновича, а не хотелось бы.

IMHO, это решать тебе, как автору перевода и, к тому же, задумки целой серии статей.

[Dale]

IMHO, это решать тебе, как автору перевода и, к тому же, задумки целой серии статей.

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

Ну а если концепция сопрограмм не всем сразу понятна - так это дело поправимое, в литературе на этот счет пробелы. Немного поработаем, и желающие смогут почитать и разобраться. 3-4 статьи, думаю, будет достаточно.

[Sla]

Если мой аргумент послужит  авторитетом - оставляем как есть.
!. С точки зрения Seo поиск будет вестись по сопрограммам.
2. Чайнику - непонятно и хрен с ним, это ему не поможет.
3. Профи? Хм... только в том случае если он не знаком с таким понятием...

зы...
Могу олубликовать перевод на хабре - посмотрим  реакцию. А че? та хрен с ней с репой. В личном блоге сколько хочу

[Dale]

!. С точки зрения Seo поиск будет вестись по сопрограммам.

Логично. Лично у меня глаз зацепился за ключевое сочетание "сопрограмма" и "язык C". То, что оно внутри сделано методом Даффа, - дело десятое. Мне ведь главное - ехать, а не "шашечки"...

зы...
Могу олубликовать перевод на хабре - посмотрим  реакцию. А че? та хрен с ней с репой. В личном блоге сколько хочу

Мне кажется, риск минимален. Материал-то качественный. Если репа треснет пострадает, вывод однозначен: ресурс не созрел, пусть резвятся вокруг "Hello world". Ну а если оценят, выиграют в итоге все.

[Dimka]

Пока читал, меня преследовало чувство дежавю, поэтому возникли дополнения, выходящие за пределы языка C.

Дополнение 1. Урезанным вариантом сопрограммы, тем не менее показывающим "родовую" связь сопрограмм и подпрограмм (subroutines), можно считать подпрограммы языка Basic. Подпрограмма отличается от процедуры и функции тем, что не имеет передаваемых через стек параметров и хранящихся в стеке локальных переменных - все переменные общие с основной программой, однако хранит в стеке адрес возврата - тем отличается от обычного GoTo. Где это можно применять. Например, как в статье, требуется написать некий сложный управляющий алгоритм, в нужные моменты времени передающий управление блоку операторов для выполнения какого-то действия.

Код: (Text)

Sub Control(FlagA, FlagB As Boolean, X As Integer, Y As Double)

  ' Управляющий алгоритм, в разных местах вызывающий ОДНО И ТО ЖЕ действие.
  If Not FlagA And FlagB Then
    If X > 10 And X < 20 Then
      GoSub Action
    End If
  Else
      GoSub Action
  End If
       
  ' Обязательно выход из процедуры, чтобы избежать несанкционированного
  ' выполнения действия.
  Exit Sub
       
Action:
  ' Действие: любая последовательность операторов, недостаточно сложная или
  ' сильно привязанная к текущим значениям локальных переменных, чтобы не
  ' хотелось выносить её в отдельную процедуру/функцию.
  Print Y

  Return
End Sub

Если не делать GoSub, то либо придётся делать copy-paste куска кода под меткой Action, либо выносить этот кусок кода в отдельную процедуру. Первое ухудшает сопровождаемость кода и перегружает деталями управляющий алгоритм, второе не всегда выгодно, если для выполнения действия нужна большая часть локальных переменных.

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

Дополнение 2. Нечто подобное подпрограммам языка Basic мне приходилось реализовывать в языке SQL - и там как раз использовался метод, очень похожий на машину Даффа.

Код: (Text)

CREATE PROCEDURE Control(@FlagA AS bit, @FlagB AS bit, @X AS int, @Y AS float)
AS
        DECLARE @State AS int
        SET @State = 0

Control:
IF @State = 0
        GOTO State0
ELSE IF @State = 1
        GOTO State1
ELSE IF @State = 2
        GOTO State2
ELSE
        RETURN

State0:
        -- Управляющий алгоритм, в разных местах вызывающий ОДНО И ТО ЖЕ действие.
        IF @FlagA = 0 AND @FlagB = 1
                BEGIN
                        IF @X > 10 AND @X < 20
                                BEGIN
SET @State = 1
                                        GOTO Action
State1:
                                END
                END
        ELSE
                BEGIN
SET @State = 2
                        GOTO Action
State2:
                END

        -- Обязательно выход из процедуры, чтобы избежать несанкционированного
        -- выполнения действия.
        RETURN

Action:
        -- Действие: любая последовательность операторов, недостаточно сложная или
        -- сильно привязанная к текущим значениям локальных переменных, чтобы не
        -- хотелось выносить её в отдельную процедуру
        PRINT @Y

        GOTO Control
GO

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

Дополнение 3. В современных языках то же самое может быть реализовано посредством:

• Использования замыканий:

Код: (Ruby)

def control(flag_a, flag_b, x, y)
  action = lambda do
    puts y
  end

  if not flag_a and flag_b then
    if x > 10 and x < 20 then
      action.call
    end
  else
    action.call
  end
end

• yield-конструкций и, опять же, использования замыканий:

Код: (Ruby)

def control(flag_a, flag_b, x)
  if not flag_a and flag_b then
    if x > 10 and x < 20 then
      yield
    end
  else
    yield
  end
end

flag_a, flag_b, x, y = false, true, 15, 3.14
control(flag_a, flag_b, x) do
  puts y
end

Данный пример не совсем точен, поскольку локальные переменные функции control (если бы они там были), пришлось бы передавать через yield-возврат в основную программу, хотя в основной программе доступны все параметры функции control. Следует заметить, что yield return (в том же C#.NET) хотя и выглядит как "временный" выход из процедуры, на самом деле является неявным вызовом анонимного блока кода (или lambda-функции), работающего в замыкании внешней функции - т.е. полностью эквивалентен предыдущему примеру. В языке Ruby это видно более отчётливо.

Однако, повторюсь, что все эти случаи - это не сопрограммы, а подпрограммы.

[npak]

Dale, спасибо за статью.

Сегодня применил этот трюк для кодирования обходчика конечного автомата. Работает отлично.

Выше в теме я агитировал за переключение контекстов, но для обходчиков автоматов трюк Даффа подходит больше, чем "легкие потоки" (fibers).  Дело в том, что каждый легкий поток "весит" порядка мегабайта, так как в контексте хранится отдельный сегмент стека. Когда в автомате тысячи состояний для хранения контекстов потоков нужны гигабайты памяти, а в случае использования сопроцедур объем хранимых данных на порядки меньше. В моем случае это 8 байт - 4 байта на номер строки и 4 байта для итерационной переменной. Гораздо меньше, чем мегабайт, не так ли

Замечание для тех, кто захочет попробовать сопроцедуры в MS Visual Studio: необходимо указывать компилятору опцию Zi (Program Database). Если будет выбрано ZI (Program Database for Edit and Continue), то компиляция вызовет ошибку error C2051: case expression not constant

[Dale]

Dale, спасибо за статью.

Сегодня применил этот трюк для кодирования обходчика конечного автомата. Работает отлично.

Пожалуйста. Рад, что пригодилось

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

Выше в теме я агитировал за переключение контекстов, но для обходчиков автоматов трюк Даффа подходит больше, чем "легкие потоки" (fibers).  Дело в том, что каждый легкий поток "весит" порядка мегабайта, так как в контексте хранится отдельный сегмент стека.

То, что накладно на PC, на "легких" микроконтроллерах в принципе невозможно, поскольку их аппаратные ресурсы на несколько порядков меньше. Это основная причина, по которой я так уцепился за статью и попытался убедить, что методика вовсе не так нелепа, как может показаться при беглом прочтении.

Замечание для тех, кто захочет попробовать сопроцедуры в MS Visual Studio: необходимо указывать компилятору опцию Zi (Program Database). Если будет выбрано ZI (Program Database for Edit and Continue), то компиляция вызовет ошибку error C2051: case expression not constant

На этот счет в статье был намек:

Отметим, что с Visual C++ версии 6 трюк с сопрограммами не проходит, поскольку его отладочное состояние по умолчанию (Program Database for Edit and Continue) делает нечто странное с макросом __LINE__. Чтобы скомпилировать программу с использованием сопрограмм в среде VC++ 6, вы должны выключить опцию «Edit and Continue». (В свойствах проекта перейдите на закладку «C/C++», категория «General», установка «Debug info». Выберите любую опцию, кроме «Program Database for Edit and Continue».)

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

[RXL]

Dale, посмотри начало топика - сделал выделение. Так подойдет?

[Dale]

Да, очень хорошо визуально выделяется на общем фоне. Подходящий стиль для оформления примечаний.

[npak]

Показал первый раз коллегам. Присваивание 

Код:

state=__LINE__; return x; case __LINE__:;

привело народ в экстаз.

[RXL]

npak, в позитивный экстаз или наоборот?

[Алексей++]

в когнитивный диссонанс (модно нонче )

кстати, не совсем понятно расположение case. Ведь, сли __LINE__ - это номер строки, то вернёмся потом опять к оператору state=...;
А не должно ли быть так:

Код:

state=__LINE__+1; return x;
case __LINE__+1:

?

[RXL]

Леш, не к началу строки, а к case!

[Алексей++]

case - это же метка. Я провто не знаю, как там по стандарту расположение метки обрабатывается

[RXL]

Не метки это. Или, во всяком случае, они позиционируются не на строках, а на операторах.

Код:

switch (cond) { case 0: x = 1; break; case 1: x = 10; break; default: x = 0; }

Валидно.

[Алексей++]

тогда понятно. Используется тот факт, что номер строки не повторяется (только в одну строку два таких фокуса нельзя записать)

[RXL]

Если бы был в препроцессоре какой-то генератор уникальных последовательностей, то можно было и несколько в строку. Только ведь так все равно не пишут - значит оно и не нужно.

[Ochkarik]

RXL, вообще.... я подозревал что генератор такой есть но я не смог его найти)

Добавлено через 15 минут и 31 секунду:
кстати... а нельзя дефайном задать что нить  типа:
#ifndef qqq
  #define qqq 1
#else
   #define qqq    ((qqq)+1)  
#endif
чтобы каждый раз переопределялось?


Добавлено через 8 минут и 12 секунд:
кстати....хотя это и бессмысленно в данном случае...
"Директива #line дает команду компилятору сменить хранимые им номер строки и имя файла на данные. "

[Алексей++]

Ochkarik, нет, дефайн не бывает рекурсивным

[npak]

Рома, экстаз был позитивный.  Я вообще затрудняюсь представить негативный экстаз

кстати, не совсем понятно расположение case. Ведь, сли __LINE__ - это номер строки, то вернёмся потом опять к оператору state=...;
А не должно ли быть так:

Код:

state=__LINE__+1; return x;
case __LINE__+1:

Алексей, при подстановке препроцессор вытянет несколько строк макроса в одну. Поэтому должно быть line = __LINE__ а не __LINE__+1 , так как case будет на одной строке с присваиванием.

Разумеется, из этого следует, что несколько возвратов нельзя размещать на одной строке, так как сгенерируются две одинаковые метки.

[Алексей++]

npak, в моём посте был не макрос

[Алексей++]

хотя да, не-макрос и не подставишь несколько раз

[npak]

Попробуйте скомпилировать под MS VC с включенной опцией Debug Database for Edit and Continue - получите незабываемые переживания

[Алексей++]

Попробуйте скомпилировать под MS VC с включенной опцией Debug Database for Edit and Continue - получите незабываемые переживания

хм, у меня в обоих вариантах ведёт себя одинаково -
 error C2051: значение выражения для варианта выбора не является константой
(__LINE__ не определён ) 

[npak]

в обоих - это в каких? Если отключить "Edit and Continue", то у меня собирается

[npak]

В догонку - у меня стоит десятая Visual Studio

[Dale]

Судя по тому, что рекомендацию по отключению "Edit and Continue" сам Тэтхем дает для 6-й версии Visual Studio, имеет смысл предположить, что и в промежуточных версиях это должно работать.

[Алексей++]

в обоих - это с галкой и без. Студия 2008

[Dimka]

Ради интереса собрал в C# решение на основе yield return. Его неудобства:

• сопрограмма обязана возвращать тип IEnumerable, чтобы иметь право использовать внутри себя yield return;
• сопрограмме запрещено использовать внутри себя try-catch (особенности работы yield return);
• yield return формально что-то должен возвращать - хотя бы null;
• запрещено использование анонимных методов (особенности работы yield return).

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

Код: (Text)

    public delegate IEnumerable CoProgram();

    public enum CoProgramState
    {
        Unknown,
        Waiting,
        Running,
        Finished
    }

    public class CoProgramContext: IDisposable
    {
        private enum State
        {
            New,
            Actual,
            Old
        }

        private class CoProgramInfo
        {
            public CoProgram CoProgram;
            public IEnumerator Run;
            public State State;
        }

        private List<CoProgramInfo> coprograms;
        private Thread thread;
        private CoProgramInfo currentCoprogram;

        public CoProgramContext(params CoProgram[] coprograms)
        {
            this.coprograms = new List<CoProgramInfo>();
            this.Add(coprograms);
            this.Run();
        }

        public CoProgramState Check(CoProgram coprogram)
        {
            lock (this.coprograms)
            {
                foreach (CoProgramInfo info in this.coprograms)
                {
                    if (info.CoProgram == coprogram)
                    {
                        if (info.State == State.Old)
                        {
                            return CoProgramState.Finished;
                        }
                        else
                        {
                            if (info.Equals(this.currentCoprogram))
                            {
                                return CoProgramState.Running;
                            }
                            else
                            {
                                return CoProgramState.Waiting;
                            }
                        }
                    }
                }
                return CoProgramState.Unknown;
            }
        }

        public void Dispose()
        {
            this.Stop();
        }

        private void Add(params CoProgram[] coprograms)
        {
            foreach (CoProgram coprogram in coprograms)
            {
                CoProgramInfo info = new CoProgramInfo();
                info.CoProgram = coprogram;
                info.Run = null;
                info.State = State.New;
                lock (this.coprograms)
                {
                    this.coprograms.Add(info);
                }
            }
        }

        private void Run()
        {
            this.thread = new Thread(new ThreadStart(this.Loop));
            this.thread.Start();
        }

        private void Stop()
        {
            this.thread.Abort();
            this.thread = null;
        }

        private void Loop()
        {
            try
            {
                while (true)
                {
                    int i = 0;
                    while (true)
                    {
                        lock (this.coprograms)
                        {
                            if (i >= this.coprograms.Count)
                            {
                                break;
                            }
                            this.currentCoprogram = this.coprograms[i];
                        }
                        switch (this.currentCoprogram.State)
                        {
                            case State.New:
                                this.currentCoprogram.State = State.Actual;
                                this.currentCoprogram.Run = this.currentCoprogram.CoProgram().GetEnumerator();
                                break;
                            case State.Actual:
                                if (!this.currentCoprogram.Run.MoveNext())
                                {
                                    this.currentCoprogram.State = State.Old;
                                    this.currentCoprogram.Run = null;
                                }
                                break;
                        }
                        i += 1;
                    }
                }
            }
            catch
            {
            }
        }
    }

Далее на базе этого класса собрал решение из двух "общающихся" алгоритмов, реализующих игру отгадывания числа.

Код: (Text)

    static class MyCoPrograms
    {
        public static CoProgramContext Run()
        {
            return new CoProgramContext(
                    new CoProgram(MyCoPrograms.Produce),
                    new CoProgram(MyCoPrograms.Consume)
                );
        }

        // Глобальные переменные, управляющие процессом.
        private enum Answer
        {
            Undefined,
            Less,
            Great,
            Equal
        }
        private static int checkNumber = int.MinValue;
        private static Answer answer = Answer.Undefined;

        private static IEnumerable Produce()
        {
            Console.WriteLine("Produce: Начало.");
            Console.WriteLine("Produce: Загадываем число от 1 до 100.");
            Random random = new Random();
            int number = random.Next(100) + 1;
            Console.WriteLine("Produce: Загадано число {0}.", number);
            do
            {
                Console.WriteLine("Produce: Передаём управление Consume для отгадывания числа.");
                yield return null;
                Console.WriteLine("Produce: Проверяем ответ Consume.");
                if (checkNumber == number)
                {
                    Console.WriteLine("Produce: Consume отгадал число.");
                    answer = Answer.Equal;
                }
                else
                {
                    if (checkNumber < number)
                    {
                        Console.WriteLine("Produce: Загаданное число больше предложенного.");
                        answer = Answer.Great;
                    }
                    else
                    {
                        Console.WriteLine("Produce: Загаданное число меньше предложенного.");
                        answer = Answer.Less;
                    }
                }
            }
            while(answer != Answer.Equal);
            Console.WriteLine("Produce: Конец.");
        }

        private static IEnumerable Consume()
        {
            Console.WriteLine("Consume: Начало.");
            int min = 1, max = 100;
            while (answer != Answer.Equal)
            {
                Console.WriteLine("Сonsume: Выбираем число между {0} и {1}.", min, max);
                checkNumber = (min + max) / 2;
                Console.WriteLine("Consume: Предлагаем число {0}.", checkNumber);
                Console.WriteLine("Consume: Передаём управление Produce для проверки числа.");
                yield return null;
                switch (answer)
                {
                    case Answer.Great:
                        Console.WriteLine("Consume: Загаданное число больше предложенного.");
                        min = checkNumber;
                        break;
                    case Answer.Less:
                        Console.WriteLine("Consume: Загаданное число меньше предложенного.");
                        max = checkNumber;
                        break;
                }
            }
            Console.WriteLine("Consume: Конец.");
        }
    }

Сопрограммы обмениваются информацией через глобальные переменные. Эти глобальные переменные и сопрограммы собраны в единый класс, инкапсулирующий всё это хозяйство.

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

Код: (Text)

    class Program
    {
        static void Main(string[] args)
        {
            using(CoProgramContext context = MyCoPrograms.Run())
            {
                Console.ReadKey();
            }
        }
    }

Результат:

Produce: Начало.
Produce: Загадываем число от 1 до 100.
Produce: Загадано число 14.
Produce: Передаём управление Consume для отгадывания числа.
Consume: Начало.
Сonsume: Выбираем число между 1 и 100.
Consume: Предлагаем число 50.
Consume: Передаём управление Produce для проверки числа.
Produce: Проверяем ответ Consume.
Produce: Загаданное число меньше предложенного.
Produce: Передаём управление Consume для отгадывания числа.
Consume: Загаданное число меньше предложенного.
Сonsume: Выбираем число между 1 и 50.
Consume: Предлагаем число 25.
Consume: Передаём управление Produce для проверки числа.
Produce: Проверяем ответ Consume.
Produce: Загаданное число меньше предложенного.
Produce: Передаём управление Consume для отгадывания числа.
Consume: Загаданное число меньше предложенного.
Сonsume: Выбираем число между 1 и 25.
Consume: Предлагаем число 13.
Consume: Передаём управление Produce для проверки числа.
Produce: Проверяем ответ Consume.
Produce: Загаданное число больше предложенного.
Produce: Передаём управление Consume для отгадывания числа.
Consume: Загаданное число больше предложенного.
Сonsume: Выбираем число между 13 и 25.
Consume: Предлагаем число 19.
Consume: Передаём управление Produce для проверки числа.
Produce: Проверяем ответ Consume.
Produce: Загаданное число меньше предложенного.
Produce: Передаём управление Consume для отгадывания числа.
Consume: Загаданное число меньше предложенного.
Сonsume: Выбираем число между 13 и 19.
Consume: Предлагаем число 16.
Consume: Передаём управление Produce для проверки числа.
Produce: Проверяем ответ Consume.
Produce: Загаданное число меньше предложенного.
Produce: Передаём управление Consume для отгадывания числа.
Consume: Загаданное число меньше предложенного.
Сonsume: Выбираем число между 13 и 16.
Consume: Предлагаем число 14.
Consume: Передаём управление Produce для проверки числа.
Produce: Проверяем ответ Consume.
Produce: Consume отгадал число.
Produce: Конец.
Consume: Конец.