@naomik Я принял ответ Алана, потому что моей главной целью было использовать «ванильный Clojure как лямбда-исчисление». В своем ответе вы прекрасно перечислите недостатки этого подхода, и он очень помогает. Вы также предоставляете 3 варианта и даже предоставляете реальную оценку! Это действительно отличный ответ, я бы хотел отметить оба варианта как правильные!

чаю лямбда-исчисление с книгой Грега Майклсона «Введение в функциональное программирование через лямбда-исчисление».

Я реализую примеры в Clojure, используя только подмножество языка. Я разрешаю только:

символылямбда-функции с одним аргументомфункция приложенияопределение вар для удобства.

Пока у меня работают эти функции:

(def identity (fn [x] x))
(def self-application (fn [s] (s s)))

(def select-first (fn [first] (fn [second] first)))
(def select-second (fn [first] (fn [second] second)))
(def make-pair (fn [first] (fn [second] (fn [func] ((func first) second)))))    ;; def make-pair =  λfirst.λsecond.λfunc.((func first) second)

(def cond make-pair)
(def True select-first)
(def False select-second)

(def zero identity)
(def succ (fn [n-1] (fn [s] ((s False) n-1))))
(def one (succ zero))
(def zero? (fn [n] (n select-first)))
(def pred (fn [n] (((zero? n) zero) (n select-second))))

Но сейчас я застрял на рекурсивных функциях. Точнее на реализациюadd, Первая попытка, упомянутая в книге, такова:

(def add-1
  (fn [a]
    (fn [b]
      (((cond a) ((add-1 (succ a)) (pred b))) (zero? b)))))

((add zero) zero)

Правила лямбда-исчисления редукции силы для замены внутреннего вызоваadd-1 с фактическим определением, которое содержит само определение ... бесконечно.

В Clojure, который является языком заказа приложений,add-1 также с нетерпением оценивается перед любым исполнением любого рода, и мы получилиStackOverflowError.

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

(def add2 (fn [f]
            (fn [a]
              (fn [b]
                (((zero? b) a) (((f f) (succ a)) (pred b)))))))
(def add (add2 add2))

Определениеadd расширяется до

(def add (fn [a] 
           (fn [b]
             (((zero? b) a) (((add2 add2) (succ a)) (pred b)))))) 

Что совершенно нормально, пока мы не попробуем! Вот что будет делать Clojure (ссылочная прозрачность):

((add zero) zero)
;; ~=>
(((zero? zero) zero) (((add2 add2) (succ zero)) (pred zero)))
;; ~=>
((select-first zero) (((add2 add2) (succ zero)) (pred zero)))
;; ~=>
((fn [second] zero) ((add (succ zero)) (pred zero)))

На последней строчке(fn [second] zero) лямбда, которая ожидает один аргумент при применении. Здесь аргумент((add (succ zero)) (pred zero)), Clojure является языком «аппликативного порядка», поэтому аргумент оценивается перед применением функции, даже если в этом случае аргумент вообще не будет использоваться. Здесь мы повторяем вadd это повторится вadd... пока стек не взорвется. На языке, подобном Хаскеллу, я думаю, что это было бы хорошо, потому что это ленивый (нормальный порядок), но я использую Clojure.

После этого в книге подробно описывается вкусный Y-комбинатор, который избегает шаблонов, но я пришел к такому же ужасному выводу.

РЕДАКТИРОВАТЬ

Как подсказывает @amalloy, я определил комбинатор Z:

(def YC (fn [f] ((fn [x] (f (fn [z] ((x x) z)))) (fn [x] (f (fn [z] ((x x) z)))))))

Я определилadd2 нравится :

(def add2 (fn [f]
            (fn [a]
              (fn [b]
                (((zero? b) a) ((f (succ a)) (pred b)))))))

И я использовал это так:

(((YC add2) zero) zero)

Но я все еще получаю StackOverflow.

Я пытался расширить функцию «вручную», но после 5 раундов сокращения бета-версии, похоже, что она бесконечно расширяется в лесу паренов.

Так в чем же смысл сделать Clojure «нормальным порядком», а не «аппликативным порядком» без макросов. Это вообще возможно? Это даже решение моего вопроса?

Этот вопрос очень близок к этому:Как реализовать итерацию лямбда-исчисления по схеме lisp? , За исключением того, что моя речь идет о Clojure и не обязательно о Y-Combinator.

 Demeter Purjon07 сент. 2017 г., 21:19
@JohannesKuhn: я буду смотреть в этом направлении в ближайшие дни.
 user63318307 сент. 2017 г., 08:03
я могу помочь тебе, когда я проснусь завтра; если тебе все еще это нужно
 Johannes Kuhn07 сент. 2017 г., 17:21
Вы должны использовать батут или использоватьrecur чтобы избежать переполнения стека.
 user63318307 сент. 2017 г., 21:28
@DemeterPurjon я только что проснулся; чувствую себя очень больным сегодня; не волнуйтесь, я пишу для вас
 Demeter Purjon07 сент. 2017 г., 21:21
@naomik Если у вас есть решение ... любая помощь приветствуется, спасибо :)

Ответы на вопрос(2)

Решение Вопроса

Z комбинатор вместо Y комбинатор. Это та же основная идея, но замена(x x) с участием(fn [v] (x x) v) так что самоссылка обернута в лямбду, то есть она оценивается только при необходимости.

Вам также нужно исправить определение булевых переменных, чтобы заставить их работать на строгом языке: вы не можете просто передать ему два значения, которые вас интересуют, и выбрать между ними. Вместо этого вы передаете ему thunks для вычисления двух значений, которые вам нужны, и вызываете соответствующую функцию с фиктивным аргументом. То есть, точно так же, как вы исправляете Y-комбинатор путем расширения рекурсивного вызова через eta, вы исправляете логические значения путем расширения eta-расширения двух ветвей if и eta-Reduction самого логического значения (я не уверен на 100%, что eta-сокращающий это правильный термин здесь).

(def add2 (fn [f]
            (fn [a]
              (fn [b]
                ((((zero? b) (fn [_] a)) (fn [_] ((f (succ a)) (pred b)))) b)))))

Обратите внимание, что обе ветви if теперь обернуты(fn [_] ...), и если сама обернута с(... b)где b - значение, которое я выбрал произвольно для передачи; ты мог пройтиzero вместо этого или что-нибудь вообще.

 amalloy07 сент. 2017 г., 21:35
@DemeterPurjon Это помогает?
 amalloy07 сент. 2017 г., 22:18
Но теперь вы обманули: ваше определение вар больше не просто для удобства, так какnaive-add относится к себе. Задача комбинаторов Y и Z состоит в том, чтобы избежать таких круговых определений.
 Demeter Purjon07 сент. 2017 г., 21:23
Здравствуйте, я уже получил это решение из другого вопроса, который я упоминал, но я не мог что-то сделать из этого. Я знаю, что это немного настойчиво, чтобы спросить это, но не могли бы вы улучшить свое решение с примером кода? Большое спасибо.
 amalloy07 сент. 2017 г., 23:20
Я имею в виду, что вы тот, кто решает, как сопоставить понятия в лямбда-исчислении с семантикой Clojure. Но LC не допускает самоссылки, и поэтому, как правило, люди, выполняющие это упражнение, также не допускают самоссылки в Clojure. Проблема была бы более очевидной, если бы вместоdef ты использовалlet для всех ваших "удобных" переменных, потому чтоlet не разрешает самостоятельную ссылку.
 Demeter Purjon07 сент. 2017 г., 22:14
Да ! Оно работает ! Но в этом случае это означает, что я могу просто забыть все о Y или Z комбинаторах и перейти к простой реализации:(def naive-add (fn [a] (fn [b] ((((zero? b) (fn [_] a)) (fn [_] ((naive-add (succ a)) (pred b)))) 42))))

которую я вижу, в том, что у вас слишком сильная связь между вашей программой Clojure и вашей программой Lambda Calculus

вы используете Clojure lambdas для представления LC lambdasвы используете переменные / определения Clojure для представления переменных / определений LCвы используете прикладной механизм Clojure (оценщик Clojure) в качестве прикладного механизма LC

Так тыфактически написание программы clojure (не программы LC), которая зависит от эффектов компилятора / оценщика clojure, что означаетстрогая оценка а такженерекурсия в постоянном пространстве Давайте посмотрим на:

(def add2 (fn [f]
            (fn [a]
              (fn [b]
                (((zero? b) a) ((f (succ a)) (pred b)))))))

Как программа Clojure, в строго оцененной среде,каждый раз мы звонимadd2мы оцениваем

(zero? b) какvalue1(value1 a) какvalue2(succ a) какvalue3(f value2) какvalue4(pred b) какvalue5(value2 value4) какvalue6(value6 value5)

Теперь мы можем видеть, что призыв кadd2 всегда приводит к вызову механизма рекурсииf - конечно, программа никогда не завершается, и мы получаем переполнение стека!

У вас есть несколько вариантов

за предложения @ amalloy, используйте thunks длязадержка вычисление определенных выражений, а затем принудительное выполнение (запуск) их, когда вы будете готовы продолжить вычисления - хотя я не думаю, что это многому вас научит

вы можете использовать Clojure'sloop/recur или жеtrampoline для рекурсий в постоянном пространстве для реализации вашегоY или жеZ комбинатор - здесь есть небольшое зависание, потому что вы хотите поддерживать только лямбды с одним параметром, и это будет сложно (возможно, невозможно) сделать в строгом оценщике, который не оптимизирует хвостовые вызовы

Я выполняю большую часть такого рода работы в JS, потому что большинство машин JS сталкиваются с той же проблемой; если вы заинтересованы в поиске обходных путей для домашнего приготовления, проверьте:Как заменить циклы while функциональной альтернативой программирования без оптимизации хвостового вызова?

написать реальный оценщик - это означает, что вы можете отделить представление вашей программы Lambda Calculus от типов данных и поведения Clojure и компилятора / оценщика Clojure - вы получитевыбирать как эти вещи работают, потому что вы тот, кто пишет оценщик

Я никогда не делал это упражнение в Clojure, но я делал это пару раз на JavaScript - опыт обучения преобразителен. Только на прошлой неделе я написалhttps://repl.it/Kluo который использует нормальную модель подстановки порядка оценки. Оценщик здесь не безопасен для стека для больших программ LC, но вы можете видеть, что рекурсия поддерживается через Curry'sY в строке 113 - он поддерживает ту же глубину рекурсии в программе LC, что и базовая машина JS. Вот еще один оценщик, использующий запоминание и более знакомую модель среды:https://repl.it/DHAT/2 - также наследует предел рекурсии базового компьютера JS

Сделать рекурсию безопасным для стека действительно сложно в JavaScript, как я упоминал выше, и (иногда) в вашем коде должны произойти значительные преобразования, прежде чем вы сможете сделать его безопасным для стека. У меня занялодва месяца из многих бессонных ночей, чтобы адаптировать это к безопасному для стека, нормальному порядку, по требованию оценщику:https://repl.it/DIfs/2 - это как Хаскель или Ракет#lang lazy

Что касается этого в Clojure, код JavaScript может быть легко адаптирован, но я не знаю достаточно Clojure, чтобы показать вам, чтоздравомыслящий Программа оценки может выглядеть так: - В книгеСтруктура и интерпретация компьютерных программ, (глава 4), авторы показывают, как написать оценщик для Scheme (Lisp), используя саму Scheme. Конечно, это в 10 раз сложнее, чем примитивное лямбда-исчисление, поэтому вполне понятно, что если вы можете написать оценщик Scheme, вы можете написать и LC. Это может быть более полезным для вас, потому что примеры кода больше похожи на Clojure

отправная точка

Я изучил немного Clojure для вас и придумал это - это только начало строгого оценщика, но он должен дать вам представление о том, как мало работы нужно, чтобы приблизиться к работающему решению.

Обратите внимание, что мы используемfn когда мы оцениваем'lambda но эта деталь не раскрывается пользователю программы. То же самое верно дляenv - т. Е. Env - это просто деталь реализации и не должна интересовать пользователя.

Чтобы победить мертвую лошадь, вы можете видеть, что как оценщик замещения, так и оценщик на основе среды приходят к эквивалентным ответам для одной и той же программы ввода - я не могу не подчеркнуть, насколько эти варианты подходятвы - в SICP авторы даже продолжают изменять оценщик, чтобы использовать простую модель на основе регистров для привязки переменных и вызова процедур. Возможности безграничныпотому что мы решили контролировать оценку; писать все в Clojure (как вы делали изначально) не дает нам такой гибкости

;; lambda calculus expression constructors
(defn variable [identifier]
  (list 'variable identifier))

(defn lambda [parameter body]
  (list 'lambda parameter body))

(defn application [proc argument]
  (list 'application proc argument))

;; environment abstraction
(defn empty-env []
  (hash-map))

(defn env-get [env key]
  ;; implement
)

(defn env-set [env key value]
  ;; implement
)

;; meat & potatoes
(defn evaluate [env expr]
  (case (first expr)
    ;; evaluate a variable
    variable (let [[_ identifier] expr]
               (env-get env identifier))

    ;; evaluate a lambda
    lambda (let [[_ parameter body] expr]
             (fn [argument] (evaluate (env-set env parameter argument) body)))

    ;; evaluate an application
    ;; this is strict because the argument is evaluated first before being given to the evaluated proc
    application (let [[_ proc argument] expr]
                  ((evaluate env proc) (evaluate env argument)))

    ;; bad expression given
    (throw (ex-info "invalid expression" {:expr expr}))))


(evaluate (empty-env)
          ;; ((λx.x) y)
          (application (lambda 'x (variable 'x)) (variable 'y))) ;; should be 'y

* или может выдать ошибку для несвязанного идентификатора 'y; твой выбор

 amalloy07 сент. 2017 г., 23:39
Разумный набросок оценщика, но у Clojure нетmatch как встроенная схема, как это делает Scheme, вам нужно сделать что-то еще там; типичноcond является конструкцией, используемой для реализации оценщика lisp в lisp.
 user63318307 сент. 2017 г., 23:41
@amalloy это в основном предназначено для того, чтобы быть отправной точкой псевдокода для ученика - извините, я не знаю достаточно слов, чтобы сделать это более идиоматическим способом - любые изменения, которые сохраняют простоту, горячо приветствуются
 user63318308 сент. 2017 г., 00:01
@amalloy спасибо, куча! вcase выражения, мы должны совпадать (в кавычках)'variable, 'lambdaи т. д. вместоvariable, lambda...
 amalloy08 сент. 2017 г., 00:13
Нет.case может соответствовать только буквальным значениям, которые вы можете воспринимать как неявно заключенные в кавычки. Более подробно, цитата там не нужна, потому что формы в этом контексте никогда не оцениваются, и, следовательно, вам не нужна цитата, чтобы предотвратить оценку.
 Demeter Purjon09 сент. 2017 г., 11:54
@naomik Я принял ответ Алана, потому что моей главной целью было использовать «ванильный Clojure как лямбда-исчисление». В своем ответе вы прекрасно перечислите недостатки этого подхода, и он очень помогает. Вы также предоставляете 3 варианта и даже предоставляете реальную оценку! Это действительно отличный ответ, я бы хотел отметить оба варианта как правильные!

Ваш ответ на вопрос