Понимание функции схемы

Следующий вопрос задан на нашем практическом экзамене по языку программирования, и мне трудно понять, как это работает. Может ли кто-нибудь сказать мне, что такое поток кода? Я запускал его в рэкет и знаю, каков ответ. Похоже, что первая лямбда-функция принимает две другие функции в качестве аргумента. Но тогда куда передаются входы (lambda (x) 2) и (lambda (y) 3)?

(((lambda (x y) (x y)) (lambda (y) (lambda (y x) (x (x y)))) (lambda (x) (lambda (x y) (x (y x))))) (lambda (x) 2) (lambda (y) 3))

Ответ на вопрос 3.


lambda scheme racket
person danny    schedule 17.09.2016    source источник

Ответы (3)


arrow_upward
6
arrow_downward

Мы, люди, любим называть вещи. Краткая запись с короткими именами позволяет легко мысленно манипулировать кодом, потому что большая часть наших умственных способностей связана с нашей массивно-параллельной системой визуального распознавания:

(((lambda (x y) (x y))
  (lambda (y) (lambda (y x) (x (x y))))
  (lambda (x) (lambda (x y) (x (y x)))))
 (lambda (x) 2)
 (lambda (y) 3)) =>

((u               where u = (lambda (x y) (x y))
  f                     f = (lambda (y) (lambda (y x) (x (x y))))
  g)                    g = (lambda (x) (lambda (x y) (x (y x))))
 (lambda (x) 2)
 (lambda (y) 3)) =>

((u               where (u x y) = (x y)
  f                     (f y)   = \(y x) -> (x (x y))     ; (*)
  g)                    (g x)   = \(x y) -> (x (y x))
 (lambda (x) 2)
 (lambda (y) 3)) =>

((f               where (f g)   = \(y x) -> (x (x y))
  g)                    (g x)   = \(x y) -> (x (y x))
 (lambda (x) 2)
 (lambda (y) 3)) =>

(h                where h       = \(y x) -> (x (x y))
 p                      p       = \(x) -> 2
 q) =>                  q       = \(y) -> 3

(h                where (h y x) = (x (x y))
 p                      (p x)   = 2
 q) =>                  (q y)   = 3

(q (q p))         where (p x)   = 2
                        (q y)   = 3
    => 

(q 3)             where (q y)   = 3
    => 

3

В определении (*) все переменные связаны в лямбда-выражении (lambda (y x) (x (x y))) — как x, так и y. Таким образом, аргумент y в (f y) игнорируется. На него могла бы ссылаться свободная переменная y в лямбда-выражении, но ее нет.

person Will Ness    schedule 18.09.2016
comment
Спасибо за ответ. Это очень полезно. Сначала я не понял этого, немного погуглив и прочитав, что такое альфа-, бета- и эта-сокращения, я смог это понять. Спасибо еще раз :) - person danny; 19.09.2016
comment
@danny Пожалуйста. Вы должны были сказать, что не уверены в основных правилах, я бы немного разъяснил это. - person Will Ness; 20.09.2016

arrow_upward
4
arrow_downward

Это работа для алгебраического степпера!

Введите это (без строки #lang) в интерактивном окне DrRacket. В левом нижнем углу измените язык на «Студент среднего уровня с лямбдой». Теперь нажмите кнопку «Выполнить». Наконец, нажмите кнопку «Шаг» (крайняя левая кнопка слева от кнопки запуска.

Теперь вы можете пройти программу пошагово (и вернуться назад!).

(((lambda (x y) (x y))
  (lambda (y) (lambda (y x) (x (x y))))
  (lambda (x) (lambda (x y) (x (y x)))))
 (lambda (x) 2)
 (lambda (y) 3))

введите здесь описание изображения

person soegaard    schedule 17.09.2016
comment
Хорошо, так что это действительно полезно. Спасибо! Таким образом, первая функция принимает в качестве аргумента две другие функции, и им передаются входные данные (lambda (x) 2) и (lambda (y) 3). Но чего я не понимаю, так это того, что схема не оценивает функцию (lambda (x) (lambda (x y) (x (y x)))) и возвращает только значение 3 из первого. Я предполагаю, что именно здесь я совершал ошибку, когда запускал код всухую. Я также оценивал 2-ю функцию. Итак, теперь мой вопрос: почему он не оценивает вторую функцию? Спасибо еще раз. - person danny; 17.09.2016
comment
@danny (lambda (x) (lambda (x y) (x (y x)))) одно выражение в теле лямбда-выражения представляет собой лямбда-форму, поэтому, когда вы применяете его, вы можете ожидать, чтобы вернуть процедуру, которая принимает два аргумента. - person Sylwester; 17.09.2016

arrow_upward
1
arrow_downward

Но тогда куда передаются входы (лямбда (x) 2) и (лямбда (y) 3)?

Для этого может помочь добавление операторов println:

(((lambda (x y)
    (println "In Lxy fn")
    (x y))
  (lambda (y)
    (println "In Ly fn")
    (lambda (y x)
      (println "In Lyxi fn")
      (x (x y))))
  (lambda (x)
    (println "In Lx fn")
    (lambda (x y)
      (println "In Lxyi fn")
      (x (y x)))))
 (lambda (x) 2)
 (lambda (y) 3))

Выход:

"In Lxy fn"
"In Ly fn"
"In Lyxi fn"
3

Часть этой функции является избыточной и может быть удалена без какого-либо влияния на вывод. В дальнейшем вместо удаленной части можно поставить буквально любое значение:

(((lambda (x y)
    (println "In Lxy fn")
    (x y))
  (lambda (y)
    (println "In Ly fn")
    (lambda (y x)
      (println "In Lyxi fn")
      (x (x y))))
  ;(lambda (x)
  ;  (println "In Lx fn")
  ;  (lambda (x y)
  ;    (println "In Lxyi fn")
  ;    (x (y x))))
  "any value"
  )
 (lambda (x) 2)
 (lambda (y) 3))

В вашем собственном формате следующий результат дает тот же результат, что и раньше:

(((lambda (x y) (x y))
  (lambda (y) (lambda (y x) (x (x y))))
  ;(lambda (x) (lambda (x y) (x (y x))))
  "any value"
  )
 (lambda (x) 2)
 (lambda (y) 3))
person rnso    schedule 21.09.2016
comment
Поправьте меня, если я ошибаюсь. Насколько я понимаю, после выполнения всего сокращения входы (lambda (x) 2) и (lambda (y) 3) передаются в fn (lambda (y x) (x (x y)) - person danny; 23.09.2016