Комбинатор U
Я опоздал на вечеринку, но заинтересовался и потратил некоторое время на то, чтобы понять, как это сделать на языке семейства Лисп, в частности Ракетка , и подумал, что, возможно, другие люди могут быть заинтересованы.
Я подозреваю, что есть много информации об этом, но сейчас серьезно сложно найти что-то, что выглядит как * комбинатор (даже сейчас я создание группы компаний под названием «Интеграция по частям» и т. д.)
Вы можете, как вы говорите, сделать это с помощью комбинатора Y, но я не хотел этого делать, потому что Y - это то, что я Я понимаю, что могу понять по несколько часов за один раз, а потом мне нужно все это проработать снова. Но оказывается, что вы можете использовать нечто гораздо более простое: комбинатор U. Кажется, что это еще труднее найти, чем Y, но вот цитата об этом:
В теории языков программирования U комбинатор, U, является математической функцией, которая применяет его аргумент к своему аргументу; то есть U (f) = f (f) или, что то же самое, U = λf. f (f).
Самостоятельное применение позволяет моделировать рекурсию в λ-исчислении, что означает, что U-комбинатор обеспечивает универсальные вычисления. (Комбинатор U на самом деле более примитивен, чем более известный комбинатор Y с фиксированной точкой.)
Выражение U (U), читаемое как U of U, является самой маленькой не завершающей программой, [.. .].
(текст здесь , который, к сожалению, не является сайтом, посвященным комбинатору U, кроме этой цитаты.)
Предпосылки
Все следующие примеры кода находятся в Racket. Макросы, безусловно, являются специфичными для Racket c. Чтобы заставить работать макросы, вам понадобится syntax-parse через:
(require (for-syntax syntax/parse))
Однако обратите внимание, что мое использование syntax-parse крайне наивно: я на самом деле просто незамороженный пещерный пещерный человек, притворяющийся, что понимаю Ракетта система макросов.
Также обратите внимание, что я не безжалостно превратил все в λ: в этом коде есть let s, использование нескольких значений, включая let-values, (define (f ...) ...) и т. д.
Две версии U
Первая версия U очевидна:
(define (U f)
(f f))
Но это столкнется с некоторыми проблемами с языком аппликативного порядка, которым по умолчанию является Racket. , Чтобы избежать этого, мы можем сделать предположение, что (f f) будет функцией, и обернуть эту форму в другую функцию, чтобы отложить ее оценку до тех пор, пока она не понадобится: это стандартный трюк, который вы должны сделать для Y в аппликативном язык заказа также. Я буду использовать аппликативный порядок U только тогда, когда мне нужно, поэтому я дам ему другое имя:
(define (U/ao f)
(λ args (apply (f f) args)))
Обратите внимание, что я допускаю более одного аргумента вместо выполнения вещь чисто λ-исчисления.
Использование U для построения рекурсивных функций
Для этого мы делаем аналогичный трюк, который вы делаете с Y: напишите функцию, которая, если дана функция в качестве аргумента, который имеет дело с рекурсивными случаями, вернет рекурсивную функцию. И, очевидно, я буду использовать функцию Фибоначчи в качестве канонической рекурсивной функции.
Итак, рассмотрим эту вещь:
(define fibber
(λ (f)
(λ (n)
(if (<= n 2)
1
(+ ((U f) (- n 1))
((U f) (- n 2)))))))
Это функция, которая, учитывая другую функцию, U из который вычисляет меньшие числа Фибоначчи, вернет функцию, которая вычислит число Фибоначчи для n.
Другими словами, U этой функции - функция Фибоначчи !
И мы можем проверить это:
> (define fibonacci (U fibber))
> (fibonacci 10)
55
Так что это очень приятно.
Завершение U в макрос
Итак, спрятать все это первым делом для этого нужно удалить явные вызовы U в рекурсии. Мы можем полностью вывести их из внутренней функции:
(define fibber/broken
(λ (f)
(let ([fib (U f)])
(λ (n)
(if (<= n 2)
1
(+ (fib (- n 1))
(fib (- n 2))))))))
Не пытайтесь вычислить U этого : оно будет бесконечно повторяться, потому что (U fibber/broken) -> (fibber/broken fibber/broken) и это включает в себя вычисления (U fibber/broken), и мы обречены.
Вместо этого мы можем использовать U/ao:
(define fibber
(λ (f)
(let ([fib (U/ao f)])
(λ (n)
(if (<= n 2)
1
(+ (fib (- n 1))
(fib (- n 2))))))))
И все в порядке ((U fibber) 10) это 55 (и заканчивается!).
И это действительно все, что вам нужно для написания макроса:
(define-syntax (with-recursive-binding stx)
(syntax-parse stx
[(_ (name:id value:expr) form ...+)
#'(let ([name (U (λ (f)
(let ([name (U/ao f)])
value)))])
form ...)]))
И это прекрасно работает:
(with-recursive-binding (fib (λ (n)
(if (<= n 2)
1
(+ (fib (- n 1))
(fib (- n 2))))))
(fib 10))
Предупреждение о привязках
Одна довольно очевидная вещь здесь состоит в том, что есть две привязки, построенные этим макросом: внешняя и внутренняя с тем же именем. И они не связаны с одной и той же функцией в смысле eq?:
(with-recursive-binding (ts (λ (it)
(eq? ts it)))
(ts ts))
является #f. Это имеет значение только на языке, где привязки могут быть видоизменены: язык с присваиванием другими словами И внешние, и внутренние привязки, если они не были мутированы, относятся к функциям, которые идентичны функциям : они вычисляют одинаковые значения для всех значений своих аргументов. На самом деле, трудно понять, для каких целей eq? будет использоваться в языке без присваивания.
Это предостережение будет применяться и ниже.
Две версии U для многих функций
Очевидное обобщение U, U * для многих функций состоит в том, что U * (f1, ..., fn) является кортежем (f1 (f1, ..., fn), f2 (f1, ...) , фн), ...). И хороший способ выразить это в Racket - это использовать несколько значений:
(define (U* . fs)
(apply values (map (λ (f)
(apply f fs))
fs)))
И нам также понадобится аппликативный порядок:
(define (U*/ao . fs)
(apply values (map (λ (f)
(λ args (apply (apply f fs) args)))
fs)))
Обратите внимание, что U * является истинное обобщение U: (U f) и (U* f) одинаковы.
Использование U * для построения взаимно-рекурсивных функций
Я буду работать с тривиальной парой функций:
- объект является цифрой c деревом , если это минусы и его автомобиль и cdr являются цифрами c объектов;
- объект является цифра c объект , если это число или дерево цифр c.
Таким образом, мы можем определить функции 'maker' (с помощью '-er' 'соглашение: функция, которая делает x значением x er или, если x содержит дефисы, x - э-э) которые будут выполнять подходящие функции:
(define numeric-tree-er
(λ (nter noer)
(λ (o)
(let-values ([(nt? no?) (U* nter noer)])
(and (cons? o)
(no? (car o))
(no? (cdr o)))))))
(define numeric-object-er
(λ (nter noer)
(λ (o)
(let-values ([(nt? no?) (U* nter noer)])
(cond
[(number? o) #t]
[(cons? o) (nt? o)]
[else #f])))))
Обратите внимание, что для обоих из них я немного повысил вызов до U*, просто чтобы сделать вызов с соответствующим значением U* меньше непрозрачный.
И это работает:
(define-values (numeric-tree? numeric-object?)
(U* numeric-tree-er numeric-object-er))
А теперь:
> (numeric-tree? 1)
#f
> (numeric-object? 1)
#t
> (numeric-tree? '(1 . 2))
#t
> (numeric-tree? '(1 2 . (3 4)))
#f
Упаковка U * в макрос
Та же проблема, что и раньше, возникает, когда мы поднимаем внутренний вызов U* с тем же результатом: нам нужно использовать U*/ao. Кроме того, макрос становится значительно более волосатым, и я немного удивлен, что так легко все понял. С концептуальной точки зрения это не сложно: для меня просто не очевидно, что сопоставление с образцом работает.
(define-syntax (with-recursive-bindings stx)
(syntax-parse stx
[(_ ((name:id value:expr) ...) form ...+)
#:fail-when (check-duplicate-identifier (syntax->list #'(name ...)))
"duplicate variable name"
(with-syntax ([(argname ...) (generate-temporaries #'(name ...))])
#'(let-values
([(name ...) (U* (λ (argname ...)
(let-values ([(name ...)
(U*/ao argname ...)])
value)) ...)])
form ...))]))
И теперь, в потоке искр, мы можем написать:
(with-recursive-bindings ((numeric-tree?
(λ (o)
(and (cons? o)
(numeric-object? (car o))
(numeric-object? (cdr o)))))
(numeric-object?
(λ (o)
(cond [(number? o) #t]
[(cons? o) (numeric-tree? o)]
[else #f]))))
(numeric-tree? '(1 2 3 (4 (5 . 6) . 7) . 8)))
и get #t.
Как я уже сказал, я уверен, что есть хорошо известные более эффективные способы сделать это, но я подумал, что это было достаточно интересно, чтобы не проиграть.