Оценка Lisp операторов let

Question

Я пишу интерпретатор Scheme и столкнулся с допустимым оператором let, например:

;; should print 7
(let ((a 4) (b 3))
    (let ((a (* a a)) 
          (b (* b b)))
       (+ a b)
       (- a b)))

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

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

Answer 1

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

(define (func) (func))

(let ()
  (func) ;; does not return
  1)

Здесь, если вы оставите (func) без оценки, вы получите неправильный результат (равный 1), в то время как вы должны получить неразрывные вычисления.

Другая проблема заключается в том, что call / cc (call-with-current-продолжение) (и да, он принадлежит функциональному подмножеству) может использоваться для фактического возврата из вычисления из нехвостой позиции Например:

(call-with-current-continuation
  (lambda (ret)
    (let ()
      (ret 3)
      4)))

, который вернет 3 , а не 4. Это все еще чисто функционально.

Обратите внимание, что (let () x y z) эквивалентно форме одного утверждения (let () (begin x y z)), поэтому реальный вопрос в том, нужна ли вам begin:)

Answer 2

Вы правы (почти): если вы реализуете чисто функциональное подмножество Scheme (т.е. не set!, set-car!, set-cdr!), тогда любое выражение, кроме последнего в let, будет иметь их возвращаемое значение отбрасывается, и, поскольку вы гарантированно не будете иметь побочных эффектов, не стоит молча игнорировать их.

Однако, есть один маленький случай, который вам нужно рассмотреть, и это когда предшествующие выражения define s:

(let ((x 3))
  (define y 4)
  (+ x y))

Это и законно, и функционально. Однако есть и хорошие новости - внутри блока (например, let) вы должны иметь все свои define наверху. То есть, это не считается законной схемой:

(let ((x 3))
  (+ 2 3)
  (define y 4)
  (+ x y))

Это означает, что при оценке блока все, что вам нужно сделать, это отсканировать верхнюю часть на define s и обернуть их в эквивалентное выражение letrec, а затем продолжить игнорировать все, кроме последнего выражения (которое вы бы сделали затем вернитесь).

edit: antti.huima дает отличное замечание о call / cc. Если вы собираетесь включить продолжения в свою реализацию, вы действительно не сможете сделать много предположений о том, когда что-то будет оцениваться.

Answer 3

Хорошо, let просто создает привязку, как define. Там нет ничего, что изменяет связанную переменную, как set!. Итак, теперь подумайте о том, какова область ваших имен: a из '(+ a b) the same as the a` вы связаны с 4? (Подсказка: нет.)

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

обновление О, я оставил точку. Вы правы, что вызов (+ a b) не имеет длительного эффекта, но тогда вы не можете в общем случае предположить, что это будет правдой, и вы не можете определить, является ли это правдой, изучая только текст программы. (Учтите: там могут быть и другие функции вместо "+".) В остальном, однако, если вы думаете, что получите правильный результат, не оценив различные предложения let, вы не поймете что он пытается сделать.