Особая форма letrec

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

(define (f x)
  (letrec ((even?
            (lambda (n)
              (if (= n 0)
                  true
                  (odd? (- n 1)))))
           (odd?
            (lambda (n)
              (if (= n 0)
                  false
                  (even? (- n 1))))))
    <rest of body of f>))

Выражение letrec имеет вид

(letrec ((<var1> <exp1>) ... (<varn> <expn>))
  body)

и является вариантом let , в котором выражения <expk> , устанавливающие начальные значения для переменных <vark> , вычисляются в окружении, которое включает все связывания letrec . Это делает возможным рекурсию между связываниями, к примеру, взаимную рекурсию even? и odd? в последнем примере, или вычисление факториала 10 через

(letrec ((fact
          (lambda (n)
            (if (= n 1)
                1
                (* n (fact (- n 1)))))))
  (fact 10))

а. Реализуйте letrec как производное выражение, переводя выражение letrec в выражение let , как показано в тексте раздела или в упражнении 4.18 . То есть переменные letrec должны создаваться в let , а затем получать значение через set! .

б. Хьюго Дум совсем запутался во всех этих внутренних определениях. Ему кажется, что если кому-то не нравятся define внутри процедуры, то пусть пользуются обычным let . Покажите, что в его рассуждениях неверно. Нарисуйте диаграмму, показывающую окружение, в котором выполняется <rest of body of f> во время вычисления выражения (f 5) , если f определена как в этом упражнении. Нарисуйте диаграмму окружений для того же вычисления, но только с let на месте letrec в определении f .

---