Почему `let 'не работает для именования внутренних рекурсивных процедур? - PullRequest
Новая
       37

Почему `let 'не работает для именования внутренних рекурсивных процедур?

3 голосов
/ 03 июля 2010

Рассмотрим следующую реализацию функции для вычисления факториала: [1] 

(define fac-tail
  (lambda (n)
    (define fac-tail-helper
      (lambda (n ac)
        (if (= 0 n)
            ac
            (fac-tail-helper (- n 1) (* n ac)))))
    (fac-tail-helper n 1)))

Я попытался переписать, используя let для внутреннего определения: 

(define fac-tail-2
  (lambda (n)
    (let ((fac-tail-helper-2
            (lambda (n ac)
              (if (= 0 n)
                  ac
                  (fac-tail-helper-2 (- n 1) (* n ac))))))
    (fac-tail-helper-2 n 1))))

Существуетнет ошибки во время define, но выполнение приводит к: 

#;> (fac-tail-2 4)
Error: undefined variable 'fac-tail-helper-2'.
{warning: printing of stack trace not supported}

Как заставить работать версию let?

Версия схемы - SISC v 1.16.6

[1] На основе итерационной версии factorial в разделе 1.2.1 SICP http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1

Ответы [ 3 ]

8 голосов
/ 03 июля 2010

Как сделать так, чтобы версия работала?

Используйте letrec вместо let.

6 голосов
/ 03 июля 2010

R. Кент Двбвиг говорит:

На самом деле выражение let является синтаксическим расширение определено в терминах лямбда и процедура применения, которая обе основные синтаксические формы. В общем, любое выражение вида 

(let ((var expr) ...) body1 body2 ...)

эквивалентно следующему. 

((lambda (var ...) body1 body2 ...)
 expr ...)" [1]

Это означает, что fac-tail-2 эквивалентно: 

(define fac-tail-2
  (lambda (n)
    ((lambda (fac-tail-helper-2)
       (fac-tail-helper-2 n 1)) ;; <== scope where fac-tail-helper-2 is visible.
     (lambda (n ac) ;; this lambda is assigned to fac-tail-helper-2
       (if (= 0 n)
           ac
           (fac-tail-helper-2 (- n 1) (* n ac))))))) ;; <=== problem

И становится ясно, что проблема в том, что имя fac-tail-helper-2 отображается как параметр в теле lambda выделен выше, но не является именем внутри lambda, назначенного параметру fac-tail-helper-2.

[1] Раздел 2.5, «Лямбда-выражения» из Язык программирования схем, 4-е издание http://scheme.com/tspl4/start.html#SECTGSLAMBDA

0 голосов
/ 06 июля 2010

Две другие альтернативы, добавляемые для полноты.

Язык программирования схем, 4-е издание В разделе 3.2 есть две другие альтернативы для использования let и рекурсивных функций. http://scheme.com/tspl4/further.html#./further:h2

Первый умный и не рекомендуется. Он включает в себя добавление параметра к лямбда-выражению, которое он вызывает, а затем передачу себя для начала работы. 

(define fac-tail-4
  (lambda (n)
    (let ((fac-tail-helper
            (lambda (fac-tail-helper n ac)
              (if (= 0 n)
                  ac
                  (fac-tail-helper fac-tail-helper (- n 1) (* n ac))))))
      (fac-tail-helper fac-tail-helper n 1))))

И более простым является имя let, которое можно использовать вместо letrec для однократной рекурсии. 

(define fac-tail-3
  (lambda (x)
    (let fac-tail-helper ((n x) (ac 1))
      (if (= 0 n)
          ac
          (fac-tail-helper (- n 1) (* n ac))))))

Хотя эта версия скрывает неявное лямбда-определение, которое привязано к fac-tail-helper.

...