Julia Language
결합 자

비고

Y 또는 Z 결합 자

Julia는 순전히 기능적인 언어는 아니지만, 기능 프로그래밍의 초석, 즉 어휘 기능의 범위, 어휘 범위, 클로저에 대한 완벽한 지원을 제공합니다.

고정 소수점 결합 자는 기능 프로그래밍의 핵심 결합 자입니다. Julia는 열심히 평가되는 의미론을 가지고 있기 때문에 (Julia가 크게 영향을받은 Scheme을 포함한 많은 함수 언어와 마찬가지로) Curry의 원래 Y-combinator는 기본적으로 작동하지 않습니다.

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

그러나 Y- 연결자 인 Z- 연결자의 가까운 친척이 실제로 작동합니다.

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

이 결합 자 (combinator)는 함수를 취하여 인수 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 Combinator 시스템

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)

제가 위에서 설명 콤비 표준에 이름이있다 Base : 줄리아 identity . 따라서 위의 정의를 I 의 다음 대체 정의로 다시 작성할 수있었습니다.

const I = identity

SKI Combinators보기

위의 접근 방식의 한 가지 약점은 우리의 기능이 우리가 좋아할만큼 멋지게 보이지 않는다는 것입니다. 우리가 대체 할 수 있을까요?

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 및 유형의 name 필드의 primary 필드를 사용하여 리플렉션을 통해 메소드를 추가 할 수 있습니다. 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