rukhi7 12 фев в 07:07

Откуда взялась хвостовая рекурсия и когда ожидается ее реализация в новом стандарте языка Си. Рекурсия VS Iteration

Простой

7 мин

2.7K

Программирование*Функциональное программирование*C*C++*

Мнение

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

Timick 12 фев в 07:58

Не вижу проблем с рекурсией если количество вызовов строго ограниченно. В противном случае можно оказаться в call stack overflow. Ну это будет сильно дурацкая имплементации как в задаче заливки фигуры.

vadimr 12 фев в 08:14

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

vadimr 12 фев в 08:20

Реализация программ в машинном коде идёт от условных переходов, к которым близок цикл, а теория вычислений идёт от рекурсии. Поэтому цикл проще и естественнее практически, а рекурсия теоретически. Что касается человеческой привычки, то она формируется первым изученным языком программирования.

rukhi7 12 фев в 08:41

Что касается человеческой привычки, то она формируется первым изученным языком программирования.

ну не скажите! первым я изучал Basic (если не рассматривать коды на калькуляторе как язык :) ), практически парралельно Фортран и PL/1, еще Фокал, но родным(так сказать) я для себя ощущаю любой Си-подобный язык от чистого Си через С++, до C# и даже Java-код для меня прост и понятен с первого взгляда. Конечно более менее навороченные конструкции всегда требуют задуматься, но это уже не зависит от языка.

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

vadimr 12 фев в 08:49

Если в привычных вам языках рекурсия является производной конструкцией, то вы её и воспринимаете как таковую.

Я лично начинал изучения программирования в школе с языка Лого, в котором, как и в Scheme, рекурсия является основным механизмом организации циклических вычислений, а цикл в основном реализуется через рекурсию. Поэтому во многих случаях мне проще думать через рекурсию. Если же вы начинали со старого Бейсика и калькуляторных кодов, то конечно рекурсия является для вас крайне неестественным механизмом, искусственным наворотом поверх базовых конструкций.

rukhi7 12 фев в 08:58

Если же вы начинали со старого Бейсика и калькуляторных кодов

На сколько я понимаю Scheme постарше Бейсика будет. Вообще я начинал с алгебры Буля и схем на логических элементах в стиле VHDL, а еще раньше с таблицы умножения (впрочем как и вы наверно) если на то пошло.

vadimr 12 фев в 09:01

Я имел в виду Бейсик с номерами строк, где рекурсия невозможна в принципе.

rukhi7 12 фев в 09:42

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

vadimr 12 фев в 11:03

В бейсике с номерами строк не было функций в обычном понимании и, соответственно, не было и рекурсивного вызова. Там был оператор GOSUB, делающий точно то же, что и call в ассемблере, то есть просто переход с запоминанием адреса возврата.

Что касается того, как вас учили, то это частное мнение вашего преподавателя. Лично я его не одобряю, и нас учили по-другому.

rukhi7 12 фев в 08:50

а теория вычислений идёт от рекурсии

я бы посмотрел как бы вы реализовали, например, Быстрое Преобразование Фурье (FFT) через рекурсию. А это такой хороший пример из теории построения таких практических сложных вычислительных алгоритмов. Теории бывают разные.

vadimr 12 фев в 08:56

Тут в русском языке есть нехорошая неоднозначность. Я говорю о вычислениях в смысле evaluation, а не calculation. То есть именно о теории вычислений, а не о вычислительной математики. Основа теории вычислений – это лямбда-исчисление и оператор неподвижной точки, из которого путём использования именованных функций получается рекурсия. Всё это крутится вокруг чисто синтаксических преобразований кода программы, к которым цикл не относится.

Вызов функции (в том числе и рекурсивный) чисто формально можно представить заменой её имени на её тело с заменой формальных параметров на фактические*. И нас при этом вообще не будет волновать семантика операторов, из которых она состоит. Просто синтаксическая подстановка. Поэтому в лямбда-исчислении бета-редукция не имеет семантики, это чисто синтаксическая операция.

А с циклом надо углубляться в его семантику.

А что касается БПФ, то любой циклический алгоритм элементарно реализуется с помощью рекурсии, это ничем не сложнее циклов. Конкретно на Scheme БПФ будет сложнее написать только из-за отсутствия матриц в ядре языка.

*) Встанет, правда, вопрос с аппликативным порядком вычислений, но это второе дело.

rukhi7 12 фев в 09:29

Я говорю о вычислениях в смысле evaluation, а не calculation.

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

Конкретно на Scheme БПФ будет сложнее написать только из-за отсутствия матриц в ядре языка.

я думаю реализация БПФ на Scheme просто не будет иметь смысла, так как оно не будет быстрым. Да вы смогли бы продемонстрировать универсальность применения рекурсии в том смысле что результат в конце концов получить можно, но в случае БПФ результатом является не только полученные числа, но и время (тоже кстати число в тиках например) за которые эти числа получены.

vadimr 12 фев в 10:52

А тут вас подводит уже неоднозначность английского языка. В наиболее общем смысле evaluation означает просто получение значения чего-либо. Ещё есть третье английское слово из этой же серии, computation.

я думаю реализация БПФ на Scheme просто не будет иметь смысла, так как оно не будет быстрым. Да вы смогли бы продемонстрировать универсальность применения рекурсии в том смысле что результат в конце концов получить можно, но в случае БПФ результатом является не только полученные числа, но и время (тоже кстати число в тиках например) за которые эти числа получены.

Если вы хотите получить наиболее быструю реализацию БПФ, то вам надо писать в машинных кодах (или воспользоваться готовой библиотекой, написанной в машинных кодах). В ней наиболее глубокие повторяющиеся вычисления будут выполняться векторными машинными командами, а более наружные – условными переходами. Понятно, что операторов цикла в машинном коде не будет.

rukhi7 12 фев в 11:20

Если вы хотите получить наиболее быструю реализацию БПФ, то вам надо писать в машинных кодах

а вы разве не знаете что

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

умеют и оптимизацию для:

глубокие повторяющиеся вычисления будут выполняться векторными машинными командами

только все равно надо понимать (пример) когда они способны сделать тот или иной тип оптимизации, а когда нет. И надо понимать как это проконтролировать и как это поправить если что-то не получилось. А то получается что-то вроде:

вот я написал самую правильную рекурсию, а все тормозит потому что это компилятор не справился, напишите мне новый компилятор, который правильно понимает рекурсии.

vadimr 12 фев в 11:28

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

adeshere 12 фев в 13:24

> Но это и к циклам относится в той же самой мере.

Вот как раз на циклы все современные компиляторы натасканы круче некуда. Если эффективность не стоит на последнем месте, конечно. В том же фортране никому и в страшном сне не придет в голову заменять массивный оператор a=f(b), или a=b+c, где a, b и c- многомерные массивы, а f -

элементная функция

т.е. каждый элемент массива a = результат применения функции f к соответствующему элементу массива и b

на рекурсию. Мало того, что далеко не всякий фортранист с этим справится, так еще и машинный код с 99.9999%-ной гарантией получится в разы менее эффективным.

vadimr 12 фев в 13:32

Вы сами себе здесь противоречите. Пишете здравицу за циклы, а приводите в пример массивный оператор.

Если вы основываетесь на представлении, что для массивного оператора можно написать эквивалентный цикл DO, то с тем же успехом для него можно написать и эквивалентную рекурсивную форму. А фактически он реализуется векторными машинными командами и условными переходами.

А так всё зависит от конкретного языка и его реализации. В языке Scheme цикл является макроопределением над рекурсией.

adeshere 12 фев в 14:27

> Пишете здравицу за циклы, а приводите в пример массивный оператор.

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

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

легче понять среднестатистическому программеру/математику?

Я бы сам с удовольствием написал, но вряд ли сумею реализовать рекурсию оптимально. Поэтому мне правда интересно посмотреть на по-настоящему неплохую реализацию

Я уж не говорю, что если вдруг компилятор окажется недостаточно умным, и вдруг все-таки реализует рекурсию через call, то на одной только передаче параметров (которая в фортране реализована максимально эффективно!) мы сразу проиграем не проценты, а много крат.

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

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

среднестатистическом программисте?

У которого, разумеется, есть в том числе и какой-то практический опыт с рекурсией. Лично у меня в таком стиле работа с файловой системой закручена. Ну и плюс к этому еще 500 тысяч строк лично написанного кода в продакте (работающих прямо сейчас). На основании чего я все-таки наберусь наглости выдвинуть свою кандидатуру на должность этого самого "среднего" программиста. Для которого цикл:
а) на порядок естественнее и понятнее, и
б) при решении реальных задач позволяет писать гораздо более эффективный код

А в остальном Вы, конечно же, правы.

vadimr 12 фев в 15:09

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

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

Вот три программы, о которых Вы говорили:

program m1

  integer, parameter :: s = 512
  real (8), allocatable, dimension (:,:,:) :: a, b, c

  allocate (b(s,s,s), c(s,s,s))
  call random_number (b)
  call random_number (c)
  a = b+c
  print *, (sum(a))

end program m1

program m2

  integer, parameter :: s = 512
  real (8), allocatable, dimension (:,:,:) :: a, b, c
  integer :: i,j,k

  allocate (b(s,s,s), c(s,s,s))
  call random_number (b)
  call random_number (c)

  allocate (a(s,s,s))
  do k=1,s
    do j=1,s
      do i=1,s
        a(i,j,k) = b(i,j,k)+c(i,j,k)
      end do
    end do
  end do

  print *, (sum(a))

end program m2

program m3

  integer, parameter :: s = 512
  real (8), allocatable, dimension (:,:,:) :: a, b, c
  integer :: i,j,k

  allocate (b(s,s,s), c(s,s,s))
  call random_number (b)
  call random_number (c)

  allocate (a(s,s,s))

  call recsum(a, b, c, s, s, s)

  print *, (sum(a))

contains

 pure recursive subroutine recsum (a, b, c, i, j, k)

    real (8), dimension (s,s,s) :: a, b, c
    integer :: i, j, k
    intent (in) :: b, c, i, j, k
    intent (out) :: a

    if (i==0) then
      return
    else
      if (j==0) then
        call recsum (a, b, c, i-1, s, s)
      else
        if (k==0) then
          call recsum (a, b, c, i, j-1, s)
        else
          a(k,j,i) = b(k,j,i)+c(k,j,i)
          call recsum (a, b, c, i, j, k-1)
        end if
      end if

  end subroutine recsum

end program m3

adeshere 12 фев в 16:03

> Вот три программы, о которых Вы говорили:

Спасибо, действительно интересно!

Мне конечно сложно оценивать, так как я и мои друзья правда "...привыкли представлять себе массивный оператор таким образом". Но на мой субъективный вкус, тройной цикл в программе m2 все-таки попонятнее, чем нанизанные if - else в m3. Поэтому было бы очень интересно узнать: а как оценивается этот код с точки зрения человека, привыкшего к рекурсивной форме выражения мыслей?

> Но проблема в том, что gfortran не понимает, что здесь рекурсия хвостовая.

Давайте все-таки разделим два эти вопроса? Или даже точнее три:

1) Читаемость и понятность кода с точки зрения типичного программиста
2) Способность конкретного компилятора эффективно оптимизировать рекурсивные вызовы
3) Насколько пострадает задача (1), если мы будем вынуждены искусственно помогать компилятору

справиться с (2)?

допустим, он такое умеет

Мое субъективное мнение:
1) Циклы все же понятнее (Но! это зависит от "воспитания" и предыдущего опыта);
2) Компилятору наверное проще оптимизировать цикл, чем рекурсию?
3) Если такая задача становится актуальной, значит выбран не самый подходящий для данного случая язык программирования

Ну и конечно, наилучшим решением задач (1) и (3) я по-прежнему считаю массивные операторы. А задачу (2) компилятору в этом случае вообще не нужно решать ;-).

vadimr 12 фев в 16:15

С моей точки зрения, если вам надо сложить два трёхмерных массива, то надо брать Фортран и массивный оператор a=b+c и не выпендриваться, так как это инструмент, специально предназначенный для решения этой задачи. А писать рекурсивные подпрограммы на Фортране – извращение, даже притом, что я люблю и ценю рекурсию как способ выражения своих мыслей. В каждом языке существует определённая идиоматика и культура написания кода.

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

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

А для компилятора в принципе что цикл, что рекурсия – один фиг. Другое дело, что компилятор Фортрана гораздо больше ориентирован на оптимизацию циклов, чем рекурсивных вызовов, по чисто прагматической причине.

adeshere 12 фев в 17:30

> Например, массивный оператор не обязан внутри себя выполняться последовательно

Кстати, да! Что резко расширяет свободу компилятора оптимизизировать или распараллеливаать вычисления,

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

Но тогда получается, что оптимизация рекурсивного алгоритма - это на порядок более сложная задача для компилятора, чем даже оптимизация цикла?!

> А для компилятора в принципе что цикл, что рекурсия – один фиг.

Если моя гипотеза выше (в прошлой фразе) верна, то совсем даже нет. Как только мы начинаем оптимизацию, будет две больших разницы?

> Другое дело, что компилятор Фортрана гораздо больше ориентирован на оптимизацию циклов, чем рекурсивных вызовов, по чисто прагматической причине.

А вот тут я бы не подписался безоговорочно. С одной стороны, спору нет: циклы конечно встречаются чаще и оптимизировать их важнее. Но может быть, есть и вторая сторона медали, что оптимизировать циклы банально проще?

vadimr 12 фев в 17:34

Но тогда получается, что оптимизация рекурсивного алгоритма - это на порядок более сложная задача для компилятора, чем даже оптимизация цикла?!

Почему?

adeshere 12 фев в 18:00

Но тогда получается, что оптимизация рекурсивного алгоритма - это на порядок более сложная задача для компилятора, чем даже оптимизация цикла?!

> Почему?

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

В общем, определенные причины так думать у меня есть, но не более того. Для получения обоснованного ответа надо ~~вызывать чистильщика~~ обращаться к специалисту по компиляторам. Такому, как уже упомянутый здесь уважаемый @xortator. Ну или может еще кто-то откликнется?

IUIUIUIUIUIUIUI 12 фев в 20:08

Компилятору наверное проще оптимизировать цикл, чем рекурсию?

Компилятору проще оптимизировать то, смысл чего он «понимает». При этом даже loop-invariant code motion можно делать не всегда, потому что не факт, что цикл выполнится хотя бы один раз, и не факт, что у LICMнутого выражения нет сайд-эффектов.

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

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

vadimr 12 фев в 15:29

Но проблема в том, что gfortran не понимает, что здесь рекурсия хвостовая.

Конечно, фортрановский компилятор по своей природе не предназначен разматывать рекурсию.

vadimr 12 фев в 15:38

Естественно, что цикл и массив – близнецы-братья, и сложение матриц естественнее писать в виде цикла. Но, например, обход мультисписка вы немного замучаетесь делать на циклах. Как Вы сами и говорите про работу с файловой системой.

vadimr 12 фев в 16:02

Если убрать множественные рекурсивные вызовы, дурящие голову компилятору Фортрана, и оставить одномерный массив такого же размера:

program m0

  integer, parameter :: s = 512*512*512
  real (8), allocatable, dimension (:) :: a, b, c

  allocate (b(s), c(s))
  call random_number (b)
  call random_number (c)

  allocate (a(s))

  call recsum(a, b, c, s)

  print *, (sum(a))

contains

  pure recursive subroutine recsum (a, b, c, i)

    real (8), dimension (s) :: a, b, c
    integer :: i
    intent (in) :: b, c, i
    intent (inout) :: a

    if (i==0) then
      return
    else
      a(i) = b(i)+c(i)
      call recsum (a, b, c, i-1)
    end if

  end subroutine recsum

end program m0

то тогда компилятор понимает, что рекурсия является хвостовой, и время работы всех трёх программ оказывается равно между собой.

adeshere 12 фев в 17:19

> Если убрать множественные рекурсивные вызовы, дурящие голову компилятору Фортрана, и оставить одномерный массив такого же размера (...) то тогда компилятор понимает, что рекурсия является хвостовой, и время работы всех трёх программ оказывается равно между собой.

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

Недавно здесь на Хабре был замечательный цикл статей про оптимизирующие компиляторы от уважаемого @xortator. В том числе, там довольно подробно рассматривались циклы и их "размотка". Если вдруг этот мудрый человек нас сейчас слышит, было бы очень интересно узнать его мнение по этим вопросам.. Пожалуйста...

AlexAiZzz 12 фев в 17:45

Учитывая, что оптимизация выполняется в несколько проходов, то компилятор сначала задетектит хвостовую рекурсию (что относительно легко), потом развернет цикл. Может даже больше:

// Type your code here, or load an example.
int factorial(int n) {
    if (n == 1) 
        return 1;
    else
        return n * factorial(n - 1);
}

int main() {
    return factorial(5);
}

factorial:
        mov     eax, 1
        cmp     edi, 1
        je      .L1
.L2:
        mov     edx, edi
        sub     edi, 1
        imul    eax, edx
        cmp     edi, 1
        jne     .L2
.L1:
        ret
main:
        mov     eax, 120
        ret

См. предпоследнюю строку, где функция даже не вызывается, а заменяется вычисленным во время компиляции значением..

adeshere 12 фев в 18:21

$-)

Да, конечно ;-) Но это все-таки довольно простой случай. А мне хочется понять, что произойдет по мере накопления сложности? Есть подозрение, что на каком-то уровне сложности (например, если в вычислениях задействовано много функций, и не все они "чистые", ну или еще почему-то), компилятор перестанет воспринимать задачу в целом, и вместо полной оптимизации ограничится локальными улучшениями кода. Гипотеза состоит в том, что при записи одного и того же алгоритма через циклы и через рекурсию в последнем случае этот момент наступит раньше.

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

Дисклеймер

Главное - это не забывать, что в действительности все не так, как на самом деле (с). На заре моей компьютерной молодости это было моим девизом ;-)

UPD

Я этой фразой много лет пользовался, не зная, кто автор (дело было еще до интернета). А недавно открыл, что это Станислав Ежи Лец. Хорошо топтать плечи гигантов! ;-)

IUIUIUIUIUIUIUI 12 фев в 18:32

Я в хаскеле спокойно пишу условный mapM_/forM_, который, вообще говоря, реализован рекурсией-свёрткой, да ещё и абстрактно поверх любого тайпкласса Foldable. И ничего, получаю производительность на уровне C++. Функциональные компиляторы натасканы на рекурсию так же, как императивные — на циклы.

rukhi7 12 фев в 18:48

А вы попробуйте Быстрое Преобразование Фурье в хаскеле написать с производительностью на уровне С++, вот это будет номер!

Только учтите что вам на слово никто не поверит что вы уже написали, желательно графики продемонстрировать.

IUIUIUIUIUIUIUI 12 фев в 20:18

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

БПФ что на хаскеле, что на плюсах я буду писать не явными поэлементными циклами, а с использованием векторных примитивов.

AlexAiZzz 12 фев в 18:45

В том же фортране никому и в страшном сне не придет в голову заменять массивный оператор a=f(b), или a=b+c, где a, b и c- многомерные массивы, а f - на рекурсию.

Я кажется понял в чем проблема в дискуссии :)

"Человек купивший себе молоток везде видит гвозди" :)

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

Dooez 12 фев в 21:07

БПФ же как раз определен через рекурсию, реализовать его рекурсивно вовсе не сложно.

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

rukhi7 13 фев в 12:10

принцип построения БПФ никак нельзя определить через рекурсию так как принцип БПФ основан на том что мы исследуем вычисления с точки зрения количества элементарных операций состовляющих эти вычисления с тем чтобы сократить количество этих вычислений и определить условия когда такая оптимизация возможна.

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

vadimr 12 фев в 08:30

Согласитесь объявление функции выглядит тяжелее чем объявление переменной в которую по факту трансформируется эта функция при выполнении.

В языке Scheme, использующемся в SICP, это одно и то же.

И, собственно, там и необязательно объявлять функцию для использования рекурсивного вызова. Можно обойтись примитивной рекурсивной формой letrec. Просто примеры даны более многословно для лучшего восприятия.

rukhi7 12 фев в 09:10

Можно обойтись примитивной рекурсивной формой letrec.

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

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

vadimr 12 фев в 10:48

Если в вашей реализации языка хвостовой рекурсивный вызов функции сопряжён с какими-то дополнительными расходами памяти и производительности, то это дефект реализации и ничего больше. Именно потому, что, во-первых, хвостовая рекурсия эквивалентна циклу, а во-вторых, её легко распознать. Современные оптимизирующие компиляторы, как правило, не создают для хвостовой рекурсии дополнительные входы и выходы в функцию. Собственно, если рассматривать дело с точки зрения машинного кода, то и так понятно, что пара команд call/ret прагматически эквивалентна jmp.

В каких-то реализациях языков вход в каждый инстанс рекурсивной функции может подразумевать небесплатное создание нового контекста, но ведь и каждая итерация цикла потенциально может это делать (например, если в языке PL/I поместить внутрь цикла begin-блок). Это не вопрос рекурсии и цикла самих по себе.

rukhi7 12 фев в 11:03

и так понятно, что пара команд call/ret прагматически эквивалентна jmp.

на самом деле эквивалентной jmp командой является только call, именно call позволяет нам вернуться в начало функции, ret и все что с ним связано (загрузка выгрузка контекста) как раз является не нужным довеском в таком случае и, соответственно, является проблемой.

На самом деле call это и есть jmp только с дополнительной нагрузкой (а icall, это расширенный ijmp).

vadimr 12 фев в 11:10

Я говорю о том, что пару непосредственно следующих друг за другом команд call f / ret, представляющую собой реализацию в машинном языке окончания хвостово-рекурсивной функции (рекурсивный вызов и потом сразу выход), прагматически можно заменить на одну команду jmp, что и называется собственно элиминацией хвостовой рекурсии при кодогенерации. Это не совсем формально эквивалентно, потому что пара call/ret ещё оставит адрес возврата над верхушкой стека, что в машинном коде иногда используется для определения своего адреса, но в прагматическом случае обычного рекурсивного вызова так можно сделать.

rukhi7 12 фев в 11:45

представляющую собой реализацию в машинном языке окончания хвостово-рекурсивной функции (рекурсивный вызов и потом сразу выход)

тут я что-то не понял! Как это: "потом сразу выход"? Потом сразу код функций по новой и новый рекурсивный вызов, выходы будут когда-то потом, если будут.

Я на ассемблерах очень много писал, по машинным языкам меня не запутаешь.

vadimr 12 фев в 11:57

Ну вот вы в своей статье привели код на Scheme:

(define (iter product counter)
        (if (> counter n)
            product
            (iter (* counter product)
                (+ counter 1))))

Если писать на ассемблере, то это будет что-то вроде (предполагая, что counter, n и product лежат в регистрах и, соответственно, являются именами регистров):

iter cmp counter, n
     bgt exit
     mul product, counter
     inc counter
     call iter
exit ret

Строки 5 и 6 (пара call/ret) – это собственно реализация хвостовой рекурсии. И их можно заменить просто одним операторомjmp:

iter cmp counter, n
     bgt exit
     mul product, counter
     inc counter
     jmp iter
exit ret

что в точности соответствует реализации цикла с предусловием.

rukhi7 12 фев в 12:39

Строки 5 и 6 (пара call/ret) – это собственно реализация хвостовой рекурсии. И их можно заменить просто одним оператором jmp

вы видимо так увлеклись идеей переубедить меня, что, кажется не заметили что вы заменили только call на jmp! ret остался на месте :) !

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

vadimr 12 фев в 13:04

Это вы невнимательны. ret, оставшийся в коде – это цель условного перехода, не имеющая отношения к реализации рекурсивного вызова. Если тупо формально писать, то в первом случае в программе должно было бы быть две команды ret друг за другом, потому что фактически из-за хвостовой рекурсии выход из функции происходит независимо в двух ветках формы if. Но можно было сэкономить.

rukhi7 12 фев в 13:43

ну да я попал в ту же ловушку - думал о своем! Вы меня все таки запутали :) .

Просто надо было тогда код полностью писать:

с рекурсией:

iter: cmp counter, n
 bgt exit
 mul product, counter
 inc counter
 call iter
 exit: ret

factorial:  set counter, 1
 set n, param
 call iter
 set acc, counter//значение надо вернуть каким то стандартным способом
 ret

без рекурсии

factorial:  set counter, 1
 set n, param
 iter: cmp counter, n
 bgt exit
 mul product, counter
 inc counter
 jmp iter
 exit:  set acc, counter
 ret

все равно ret это довесок к call, действительно без call не нужен ret, только еще код итерации надо заинлайнить.

Все равно , с точки зрения порядка исполнения jmp заменяет только call,

ret заменяется как раз тем что блок кода инлайнится по месту формального вызова. Если бы мы оставили блок итерации вне кода основной функции нам бы понадобился второй jmp.

vadimr 12 фев в 13:54

jmp чисто формально не может заменить только call, так как одним из результатов выполнения call является рост стека. Так что где-то должен быть и ret для обратного уменьшения стека. И вот, в хвостовой рекурсии ret как раз и написан сразу после call.

Я хочу сказать только то, что коды команд call и ret, следующие в тексте программы сразу друг за другом, вместе прагматически эквивалентны одному jmp.

rukhi7 12 фев в 14:09

Теперь я хотя бы понял про что вы толкуете. С этим можно согласиться в общем.

Только в частности надо иметь в виду пример о том что когда мы подставляем вместо вызова функции (обычной не рекурсивной) ее тело, у нас call и ret просто исчезают, то есть ни на что не заменяются, то есть с точки зрения машины это, в каком то смысле, всегда избыточные операции.

adeshere 12 фев в 13:43

> На самом деле call это и есть jmp только с дополнительной нагрузкой (а icall, это расширенный ijmp).

Именно что!

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

и заменит ли циклом

дело даже не в том, что нет времени, но у меня компилятор 2008 года, так что ответ про современные компиляторы мы все равно не получим

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

AlexAiZzz 12 фев в 16:45

Тот же gcc вполне себе распознает хвостовую рекурсию уже достаточно давно, нужно лишь указать тип оптимизации, работает при -O2 и -O3 как минимум

Пожалуйста с codebolt для факториала:

factorial(int):
        mov     eax, 1
        cmp     edi, 1
        je      .L1
.L2:
        mov     edx, edi
        sub     edi, 1
        imul    eax, edx
        cmp     edi, 1
        jne     .L2
.L1:
        ret

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

AlexAiZzz 12 фев в 16:54

И это переведено не верно:

that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while.

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

rukhi7 12 фев в 20:06

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

AlexAiZzz 12 фев в 21:41

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

IUIUIUIUIUIUIUI 13 фев в 01:38

Распознавать-то распознаёт, только иногда делает с этим адовую ерунду, когда там требуются какие-то дополнительные оптимизации: https://gcc.godbolt.org/z/bh6Gx5hxq

Мне лень по ассемблеру строить полный call graph, но у clang есть хотя бы один рекурсивный путь с call, а gcc делает что-то либо очень гениальное, либо очень тупое для -DSHITTY_CODEGEN-случая (и там тоже есть какие-то рекурсивные пути с call — gcc'шный кодген мне понимать сильно тяжелее, чем clangовский в этом случае).

При этом аналогичный SHITTY_CODEGENу (с паттерн-матчингом и вот этим всем) ФП-код компилируется в хвостовую рекурсию без всяких вызовов, как и ожидается.

AlexAiZzz 13 фев в 10:19

Ну если я правильно понял код, то там три концевых рекурсивных выхода и два не рекурсивных. Что теоретически должно приводить к отсутствию рекурсивных вызовов. Clang в обоих случаях не справился, даже в варианте без SHITTY_CODEGEN видно что он оставил GoRec и себя зовет там в 28 строке. В варианте SHITTY_CODEGEN он видать не смог раскрыть один из шаблонов поэтому нагенерил три варианта функций GoRec с тремя разными типами возврата ввиде лямбд, кторые он вынужден вызывать по отдельности, строки 25, 31, 37. Gcc же справился, поэтому он справа все развернул в переходы что позволило ему заинлайнить GoRec в runMatch. Чтобы понять что он сделал слева пришлось сделать так, чтобы было только одно окно с компилятором, иначе godbolt раскрашивает фигово. Тогда видно, что gcc сгенерил только одну функцию GoRec, при этом судя по раскраске он выкинул первые две ветки оставив только [=, this](TCh ch). Поэтому надо смотреть так ли это и если да, то почему. Беглый взгляд показывает, что идет вызов GoRec(nfa.initState, 0), плюс унутре там парсится пустая строка, если я чего-то не проглядел. Попробуй в "std::string_view string" чем то проинициализировать.

PS: О Боже, во что превратили С++ за последние 20 лет :)

IUIUIUIUIUIUIUI 13 фев в 21:57

В варианте SHITTY_CODEGEN он видать не смог раскрыть один из шаблонов поэтому нагенерил три варианта функций GoRec с тремя разными типами возврата ввиде лямбд, кторые он вынужден вызывать по отдельности, строки 25, 31, 37.

У меня есть чувство, что он сначала заинлайнил GoRec в лямбды, а потом всё сломалось, потому что так хвостовую рекурсию увидеть тяжелее, конечно.

Беглый взгляд показывает, что идет вызов GoRec(nfa.initState, 0), плюс унутре там парсится пустая строка, если я чего-то не проглядел. Попробуй в "std::string_view string" чем то проинициализировать.

Match передаётся снаружи, так что компилятор не знает, что будет в string и в nfa.

О Боже, во что превратили С++ за последние 20 лет :)

Лучший в мире инструмент для обеспечения job security.

viordash 12 фев в 11:29

вероятно у вас в сишном коде ошибка, должно быть while ( counter <= n)

rukhi7 12 фев в 11:37

спасибо, поправил! while ( n > counter) мне больше нравится.

AlexAiZzz 12 фев в 17:50

Ну и кстати ближе к исходному определению факториала будет:

int factorial(int n)
{
    int accumulator = n;
    while (--n)
    {
        accumulator *= n;
    }
    return accumulator;
}

rukhi7 12 фев в 18:16

вот интересно это язык Си такой что побуждает тех кто на нем пишет доводить код до совершенства или это те кто останавливают свой выбор на Си подобных языках имеют предрасположенность доводить код до совершенства?

Кажется вопрос еще ждет своего увлеченного исследователя.

AlexAiZzz 12 фев в 18:32

Про совершенство я не знаю :)

Но тот код, что я привел, просто соответствует тому рекурсивному определению, в которое развернется хвостовая рекурсия. Т.е. это раскрытие (всегда?) приводит к циклу с накопителем. Вариант со второй переменной (счетчиком) соответствует факториалу в записи:

$n! = \prod^n_{i=1} i$

AlexAiZzz 12 фев в 19:03

вот интересно это язык Си такой что побуждает тех кто на нем пишет доводить код до совершенства или это те кто останавливают свой выбор на Си подобных языках имеют предрасположенность доводить код до совершенства?
Кажется вопрос еще ждет своего увлеченного исследователя.

Кстати, наверное на это вопрос могу ответить :)

Я язык не выбирал :) это сделали Вы, а я отвечал на том же.

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

rukhi7 12 фев в 19:55

вы еще декларативные языки забыли (видимо) упомянуть. XSLT вот например очень интересно работает, причем работает на практике!

AlexAiZzz 12 фев в 20:22

Ну данном случае, этот декларативный язык не является языком программирования. Хотя это и не отменяет его прикольности. Вот декларативный пролог, это да. Но вот ему в дальнейшем я применений не вижу, хотя он и позиционировался когда-то как язык 4го поколения.

rukhi7 13 фев в 21:44

этот декларативный язык не является языком программирования.

читаю:

XSLT, the Extensible Stylesheet Language for Transformations, is an official recommendation of the World Wide Web Consortium (W3C). It provides a flexible, powerful language for transforming XML documents into something else. That something else can be an HTML document, another XML document, a Portable Document Format (PDF) file, a Scalable Vector Graphics (SVG) file, a Virtual Reality Modeling Language (VRML) file, Java code, ...

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

AlexAiZzz 14 фев в 09:13

То что XSLT - язык никто не спорит. Только не программирования, так то вон из списка и в HTML L - это язык. VRML туда же. Грамматики всякие для описание языков тоже сами по себе являются языками (метаязыками). Я даже скажу больше, если так уж обобщать, то рецепт в поваренной книге - это программа записанная на языке исполнителя, т.е. человека. Но при этом наш язык не становится от этого языком программирования :)

Timick 12 фев в 18:56

Перемножение на единицу тут вижу я.

AlexAiZzz 12 фев в 19:04

В каком месте?

Timick 12 фев в 19:12

когда n==1

AlexAiZzz 12 фев в 20:15

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

rukhi7 12 фев в 19:53

я тоже об этом подумал, но потом подумал что заменять сравнение с нулем на сравнение с 1 испортит совершенство :). Эфект от введения константы в ассемблер может перекрыть эффект от лишнего умножения. Как минимум эти эффекты можно рассматривать как сравнимые по затратам производительности в некоторых случаях, поэтому разницей можно пренебречь, по моему.

Jijiki 12 фев в 13:51

рекурсии и фракталы ) пока делится идёт рекурсия ) интересно будет так работать? или будет упор в стек (просто предположил возможно без рекурсии наверно, я в этом не силён )

https://www.reddit.com/r/GraphicsProgramming/comments/1ijw78c/feature_demo_video_of_surfacestable_fractal/

vadimr 13 фев в 11:33

Между прочим, хотя в C и C++ оптимизация хвостовой рекурсии поддерживается современными компиляторами, но в современном C++ принцип RAII делает оптимизацию хвостовой рекурсии невозможной при своём фактическом применении.

AlexAiZzz 13 фев в 12:15

Можно привести какой-нибудь относительно элементарный пример? При этом предоставив как рекурсивный вариант, так и итеративный вариант, либо объяснить почему переписать на итеративный вариант никак не получится. А то чего то с ходу ничего в голову не приходит.

vadimr 13 фев в 12:23

Ну что-то вроде:

SomeClass1 f (SomeClass2 arg)
  {
    SomeClass3 obj;
    return f (... obj ...);
  }

На первый взгляд функция f осуществляет хвостовую рекурсию. Однако, в силу RAII функция f перед выходом обязана осуществить вызов деструктора для объекта obj, поэтому вызов на самом деле не является хвостовым.

rukhi7 13 фев в 12:32

в чистом Си нет деструкторов, никто не запрещает писать в стиле Си если хочется непременно использовать рекурсию и чтобы ее оптимизировал компилятор.

Это ли не доказательство что когда мы хотим переложить часть работы на кого-то (на компилятор и его разработчиков) нам приходится отказаться от удобств в чем то другом (от автоматически подставляемых деструкторов при выходе из области видимости - от парадигмы объектов).

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

vadimr 13 фев в 12:33

В данном случае это издержки отсутствия сборщика мусора в C++.

AlexAiZzz 13 фев в 12:56

В этом коде есть нестыковочка, сама получает SomeCLass2, а передает SomeClass3. И что происходит с arg? Кто у нее и в какой момент вызывает деструктор?

vadimr 13 фев в 13:02

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

Что происходит с arg – тоже небезынтересный вопрос, конечно.

AlexAiZzz 13 фев в 14:15

То что типы совпадать не обязаны, с этим никто не спорит. Только для демонстрации это существенно или нет? Думаю что нет, так зачем усложнять? Пришлось дольше думать :)

Как я понимаю аргумент в том, что код, если его переводить во что-то С-подобное, должен выглядеть так?:

SomeClass1 f (SomeClass2 arg)
  {
    SomeClass3 obj = SomeClass3_Create();
    SomeClass1 res = f (... obj ...);
    SomeClass3_Destroy(&obj);
    return res;
  }

Так? Тогда смысл утверждения был в том, что хотя компиляторы умеют оптимизировать хвост-рекурсию, то из-за того что C++ вызывает деструкторы когда ему нужно и ты это не контролируешь, то по факту компилятору и нечего оптимизировать, потому что самой хвост-рекурсии никак не записать?

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

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

vadimr 13 фев в 14:20

Если вы руками вызываете конструктор и деструктор, как в вашем примере, то и самого вопроса нет. Понятно, из текста программы, что в данном случае рекурсия не является хвостовой. Но в соответствии с RAII деструктор вызывается неявно при выходе из функции, в которой локализован объект. Поэтому Destroy в вашей программе при использовании RAII руками писать не надо. Поэтому программист не в силах будет понять без огромных усилий, отделяет что-то вызов функции f от возврата этажом выше или нет.

Конечно, в чистом Си такой проблемы нет.

AlexAiZzz 13 фев в 14:31

Ну я код привел только для того чтобы понять, во что должно скомпилироваться из неявного С++ в его явный аналог на С (ну чтоб до асма не спускаться).

Так то и С++ код иногда можно было бы переписать, чтобы obj создавался в вызывающей функции. И я поэтому добавил, что из-за того что в С++ полно объектов поделу и без, и не все можно вынести наверх, и компилятор не знает что там стоит за деструкторами и можно ли поменять последовательность операций, то он за программиста это никак в хвост-рекурсию не превратит.

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

rukhi7 13 фев в 12:22

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

но в современном C++ ...

от вас гораздо интереснее было бы услышать что-то про

современный язык Scheme или LISP, или просто: насколько их сейчас можно считать современными?

vadimr 13 фев в 12:27

Я же написал в статье что разные оптимизации для языков С/С++ могут вступать в противоречие друг с другом

RAII – это не оптимизация, а непосредственно семантика современного C++.

от вас гораздо интереснее было бы услышать что-то про
современный язык Scheme или LISP, или просто: насколько их сейчас можно считать современными?

Я думаю, что современные возможности Scheme и Lisp (вроде недетерминированного программирования) в упрощённом виде появятся в мейнстримных языках лет через 50. Как недавно появились лямбды, придуманные в Лиспе в 1955-м.

rukhi7 13 фев в 12:53

Я думаю, что современные возможности Scheme и Lisp (вроде недетерминированного программирования) в упрощённом виде появятся в мейнстримных языках лет через 50

так вы бы рассказали о них! Я думаю такая статья имела бы успех на Хабре! Может и срок тогда удастся сократить с 50 до 20 лет скажем?

vadimr 13 фев в 12:57

Так я и рассказываю. У меня есть несколько статей, связанных со Scheme.

rukhi7 13 фев в 13:02

Как недавно появились лямбды, придуманные в Лиспе в 1955-м.

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

Если интересно, в одной из моих предыдущих статей найдите как «стейт машину можно заменить простым делегатом», найдите по этой цитате в кавычках. Там пример на C#, но такую же технику можно использовать (я применял) на чистом Си.

vadimr 13 фев в 13:14

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

rukhi7 13 фев в 13:22

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

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

vadimr 13 фев в 13:27

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

Я вот, например, сейчас пишу самомодифицирующийся код, который применяет методы символического продукционного вывода для порождения текста программы в реальном времени. На C++ такие вещи реализовать невозможно.

Всякий инструмент имеет определённую сферу своего применения.