Порядок оценки лямбда-функций в ракетке - PullRequest
Новая
       77

Порядок оценки лямбда-функций в ракетке

3 голосов
/ 18 февраля 2020

В настоящее время работаем с Racket Guide на https://docs.racket-lang.org и читаем о лямбда-функциях. Объяснение их полезности ясное, но я не уверен, что вполне определил порядок, в котором оцениваются такие функции. Рассмотрим следующий пример из Руководства: 

(define (twice f v)
  (f (f v)))

(define (make-add-suffix s2)
  (lambda (s) (string-append s s2)))

(twice (make-add-suffix "!") "hello")

Вызов функции для twice здесь называется "hello!!". Вот мое предположение о том, как выглядит процесс оценки: 

(twice (make-add-suffix "!") "hello")

((make-add-suffix "!") ((make-add-suffix "!") "hello")

((make-add-suffix "!") (string-append "hello" "!"))

(string-append (string-append "hello" "!") "!")

(string-append "hello!" "!")

"hello!!"

Это точная оценка, или я что-то пропустил?

Ответы [ 2 ]

2 голосов
/ 18 февраля 2020

Слоган : Сначала нужно оценить самое внешнее и левое вложенное выражение. 

(twice (make-add-suffix "!") "hello")

; (define (f x) ...) is short for (define f (lambda (x) ...)) so,
; = { substitute twice with  (lambda (f v) (f (f v)))}

((lambda (f v) (f (f v))) (make-add-suffix "!") "hello")

; = { substition of make-add-suffix with (lambda (s2) (lambda (s) (string-append s s2)))}

((lambda (f v) (f (f v)))
 ((lambda (s2) (lambda (s) (string-append s s2))) "!")
 "hello")

Терминология, прежде чем мы продолжим:

  • Beta Reduction: ((lambda (x-1 ... x-n) f-body) v-1 ... v-n) == f-body со всеми вхождениями x-1 ... x-n, замененными на v-1 ... v-n соответственно.

  • Вызов по значению: Аргументы вызова функции оцениваются перед бета-редукцией. 

; = { beta-reduction of ((lambda (s2) (lambda (s) (string-append s s2))) "!") }

((lambda (f v) (f (f v))) (lambda (s) (string-append s "!")) "hello")

; = { beta-reduction of the whole expression }

((lambda (s) (string-append s "!"))
 ((lambda (s) (string-append s "!")) "hello"))

; = { beta-reduction of the expression in the argument position first }

((lambda (s) (string-append s "!")) (string-append "hello" "!"))

; ... and the rest is easy:
((lambda (s) (string-append s "!")) "hello!")
(string-append "hello!" "!")
"hello!!"
1 голос
/ 21 февраля 2020

Другой способ получить тот же ответ: DrRacket включает инструмент «Stepper» именно для этой цели. Если вы установите уровень языка «Intermediate Student with Lambda» и нажмете кнопку «Step», вы сможете увидеть оценку вашей программы в виде последовательности шагов, как описывает thrvshl.

EDIT : стратегия оценки, которую вы описываете, где первый аргумент twice заменяется для каждого из экземпляров x в определении twice, называется оценкой "по имени" и связана с ленью a Ла Haskell. Чтобы увидеть разницу, рассмотрим версию make-add-suffix, которая включает printf во внутреннем lambda

...