Этюд для программистов

[spamsink]

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


Вскоре после изобретения Алгола-60 Дональд Кнут придумал ради проверки корректности компиляторов такой камень, который сам не смог поднять - Man or Boy Test. Правильно вычислить, что напечатает эта программа, ему не удалось:

begin
  real procedure A(k, x1, x2, x3, x4, x5);
  value k; integer k;
  begin
    real procedure B;
    begin k := k - 1;
          B := A := A(k, B, x1, x2, x3, x4);
    end;
    if k <= 0 then A := x4 + x5 else B;
  end;
  outreal(A(10, 1, -1, -1, 1, 0));
end;

(он думал -121, а на самом деле -67)

На сайте Rosetta Code переписали этот тест на множество разных языков, а вот статического варианта на C++ (в котором все вычисления делал бы компилятор при отработке templates) там нет. По ссылке видно, что "чистым" языкам типа Haskell и OCaml требуются трюки для модификации переменной k. С первого взгляда кажется, что С++ templates настолько чисты, что в них такой трюк невозможен. Или я чего-то в С++ не знаю/недопонимаю?


Безотносительно к задачке, сайт http://rosettacode.org может пригодиться.

Comments

[yigal_s]

как сурово...

увы, монад я не освоил, и понятия не имею, что мешает (или не мешает) вбить их в С++ темплейты.

[igorek.livejournal.com]

"The x1 through x5 parameters of A may be numeric constants or references to the function B"

Объясни как x1 - x5 может быть "reference to the function B"? Этот момент не понятен.

[spamsink]

Ну вон же, во вложенном вызове B передает сама себя в А по имени (в Алголе по умолчанию параметры передаются по имени, т.е. l-values по reference, а r-values - как безымянные функции). В конце концов, через 3 рекурсии и сдвига аргументов эта B доедет до x4 и будет вызвана.