Julia Language
Комбинаторы

замечания

Комбинатор Y или Z

Хотя Julia не является чисто функциональным языком, она полностью поддерживает многие из краеугольных камней функционального программирования: первоклассные функции , лексический охват и закрытие .

Комбинатор с фиксированной запятой является ключевым комбинатором в функциональном программировании. Поскольку у Джулии очень интересная семантика оценки (как и многие функциональные языки, включая Scheme, в которой Джулия сильно вдохновлена), оригинальный Y-combinator от Curry не будет работать из коробки:

Y(f) = (x -> f(x(x)))(x -> f(x(x)))

Однако близкий родственник Y-комбинатора, Z-комбинатор, действительно будет работать:

Z(f) = x -> f(Z(f), x)

Этот комбинатор принимает функцию и возвращает функцию, которая при вызове с аргументом x передается сама и x . Почему было бы полезно использовать функцию для себя? Это позволяет рекурсии, фактически не ссылаясь на имя функции вообще!

fact(f, x) = x == 0 ? 1 : x * f(x)

Следовательно, Z(fact) становится рекурсивной реализацией факториальной функции, несмотря на то, что в определении этой функции не видно рекурсии. (Конечно, рекурсия очевидна в определении комбинатора Z , но это неизбежно на нетерпеливом языке.) Мы можем убедиться, что наша функция действительно работает:

julia> Z(fact)(10)
3628800

Не только это, но и так же быстро, как мы можем ожидать от рекурсивной реализации. Код LLVM демонстрирует, что результат скомпилирован в обычную ветвь, вычитает, вызывает и умножает:

julia> @code_llvm Z(fact)(10)

define i64 @"julia_#1_70252"(i64) #0 {
top:
  %1 = icmp eq i64 %0, 0
  br i1 %1, label %L11, label %L8

L8:                                               ; preds = %top
  %2 = add i64 %0, -1
  %3 = call i64 @"julia_#1_70060"(i64 %2) #0
  %4 = mul i64 %3, %0
  br label %L11

L11:                                              ; preds = %top, %L8
  %"#temp#.0" = phi i64 [ %4, %L8 ], [ 1, %top ]
  ret i64 %"#temp#.0"
}

Комбинированная система SKI

Система комбинаторов SKI достаточна для представления любых членов лямбда-исчисления. (На практике, конечно, абстракции лямбда взрываются до экспоненциального размера, когда они переводятся в SKI.) Из-за простоты системы реализация комбинаторов S, K и I необычайно проста:

Прямой перевод из исчисления Лямбды

const S = f -> g -> z -> f(z)(g(z))
const K = x -> y -> x
const I = x -> x

Мы можем подтвердить, используя модульную систему тестирования , что каждый комбинатор имеет ожидаемое поведение.

Комбинатор I проще всего проверять; он должен возвращать заданное значение без изменений:

using Base.Test
@test I(1) === 1
@test I(I) === I
@test I(S) === S

Комбинатор K также довольно прост: он должен отказаться от своего второго аргумента.

@test K(1)(2) === 1
@test K(S)(I) === S

Комбинатор S является самым сложным; его поведение можно обобщить как применение первых двух аргументов к третьему аргументу, применение первого результата ко второму. Мы можем наиболее легко проверить комбинатор S, проверив некоторые его карри-формы. S(K) , например, должен просто вернуть свой второй аргумент и отбросить его первый, как мы видим, происходит:

@test S(K)(S)(K) === K
@test S(K)(S)(I) === I

S(I)(I) должен применить свой аргумент к себе:

@test S(I)(I)(I) === I
@test S(I)(I)(K) === K(K)
@test S(I)(I)(S(I)) === S(I)(S(I))

S(K(S(I)))(K) применяет свой второй аргумент к первому:

@test S(K(S(I)))(K)(I)(I) === I
@test S(K(S(I)))(K)(K)(S(K)) === S(K)(K)

Комбинатор I, описанный выше, имеет имя в стандартном Base Julia: identity . Таким образом, мы могли бы переписать приведенные выше определения со следующим альтернативным определением I :

const I = identity

Отображение комбайнов SKI

Одна из недостатков подхода, описанного выше, заключается в том, что наши функции не проявляются так хорошо, как хотелось бы. Можем ли мы заменить

julia> S
(::#3) (generic function with 1 method)

julia> K
(::#9) (generic function with 1 method)

julia> I
(::#13) (generic function with 1 method)

с некоторыми более информативными дисплеями? Ответ - да! Давайте перезапустим REPL, и на этот раз определим, как каждая функция должна быть показана:

const S = f -> g -> z -> f(z)(g(z));
const K = x -> y -> x;
const I = x -> x;
for f in (:S, :K, :I)
    @eval Base.show(io::IO, ::typeof($f)) = print(io, $(string(f)))
    @eval Base.show(io::IO, ::MIME"text/plain", ::typeof($f)) = show(io, $f)
end

Важно не показывать ничего, пока мы не закончим определение функций. В противном случае мы рискуем аннулировать кеш метода, и наши новые методы, похоже, не сразу вступят в силу. Вот почему мы поставили точки с запятой в приведенные выше определения. Точки с запятой подавляют вывод REPL.

Благодаря этому функции отображаются хорошо:

julia> S
S

julia> K
K

julia> I
I

Тем не менее, мы все еще сталкиваемся с проблемами, когда пытаемся отобразить закрытие:

julia> S(K)
(::#2) (generic function with 1 method)

Было бы лучше показать это как S(K) . Чтобы сделать это, мы должны использовать, что у закрытий есть свои индивидуальные типы. Мы можем получить доступ к этим типам и добавить методы к ним посредством отражения, используя typeof и primary поле name поля типа. Перезапустите REPL снова; мы внесем дальнейшие изменения:

const S = f -> g -> z -> f(z)(g(z));
const K = x -> y -> x;
const I = x -> x;
for f in (:S, :K, :I)
    @eval Base.show(io::IO, ::typeof($f)) = print(io, $(string(f)))
    @eval Base.show(io::IO, ::MIME"text/plain", ::typeof($f)) = show(io, $f)
end
Base.show(io::IO, s::typeof(S(I)).name.primary) = print(io, "S(", s.f, ')')
Base.show(io::IO, s::typeof(S(I)(I)).name.primary) =
    print(io, "S(", s.f, ')', '(', s.g, ')')
Base.show(io::IO, k::typeof(K(I)).name.primary) = print(io, "K(", k.x, ')')
Base.show(io::IO, ::MIME"text/plain", f::Union{
    typeof(S(I)).name.primary,
    typeof(S(I)(I)).name.primary,
    typeof(K(I)).name.primary
}) = show(io, f)

И теперь, наконец, все выглядит так, как мы хотели бы, чтобы они:

julia> S(K)
S(K)

julia> S(K)(I)
S(K)(I)

julia> K
K

julia> K(I)
K(I)

julia> K(I)(K)
I