?

Log in

Этюд для программистов - Общество дровосеков Бердичева по изучению Мишны

May. 2nd, 2012

02:54 pm - Этюд для программистов

Previous Entry Share Next Entry

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


Вскоре после изобретения Алгола-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:

[User Picture]
From:yigal_s
Date:May 3rd, 2012 01:52 am (UTC)
(Link)
как сурово...

увы, монад я не освоил, и понятия не имею, что мешает (или не мешает) вбить их в С++ темплейты.
(Reply) (Thread)
[User Picture]
From:igorek
Date:May 3rd, 2012 06:24 am (UTC)
(Link)
"The x1 through x5 parameters of A may be numeric constants or references to the function B"

Объясни как x1 - x5 может быть "reference to the function B"? Этот момент не понятен.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 3rd, 2012 06:36 am (UTC)
(Link)
Ну вон же, во вложенном вызове B передает сама себя в А по имени (в Алголе по умолчанию параметры передаются по имени, т.е. l-values по reference, а r-values - как безымянные функции). В конце концов, через 3 рекурсии и сдвига аргументов эта B доедет до x4 и будет вызвана.
(Reply) (Parent) (Thread)