Julia Language
Combinadores

Observaciones

El combinador Y o Z

Aunque Julia no es un lenguaje puramente funcional, que tiene soporte completo para muchas de las piedras angulares de la programación funcional: primera clase de funciones , ámbito léxico, y cierres .

El combinador de punto fijo es un combinador clave en la programación funcional. Debido a que Julia tiene una ávida evaluación semántica (al igual que muchos lenguajes funcionales, incluido Scheme, que inspira mucho a Julia), el combinador en Y original de Curry no funcionará de forma inmediata:

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

Sin embargo, un pariente cercano del combinador en Y, el combinador en Z, funcionará:

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

Este combinador toma una función y devuelve una función que cuando se llama con el argumento x , se pasa a sí misma x . ¿Por qué sería útil que una función se pase a sí misma? ¡Esto permite la recursión sin hacer referencia al nombre de la función!

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

Por lo tanto, Z(fact) convierte en una implementación recursiva de la función factorial, a pesar de que no hay recursión visible en esta definición de función. (La recursión es evidente en la definición del combinador Z , por supuesto, pero eso es inevitable en un lenguaje entusiasta). Podemos verificar que nuestra función realmente funciona:

julia> Z(fact)(10)
3628800

No solo eso, sino que es lo más rápido que podemos esperar de una implementación recursiva. El código de LLVM demuestra que el resultado se compila en una rama antigua simple, resta, llama y multiplica:

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"
}

El sistema combinador SKI

El sistema combinador SKI es suficiente para representar cualquier término de cálculo lambda. (En la práctica, por supuesto, las abstracciones lambda explotan hasta un tamaño exponencial cuando se traducen en SKI). Debido a la simplicidad del sistema, la implementación de los combinadores S, K e I es extraordinariamente simple:

Una traducción directa de Lambda Calculus

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

Podemos confirmar, utilizando el sistema de prueba unitaria , que cada combinador tiene el comportamiento esperado.

El combinador I es el más fácil de verificar; debe devolver el valor dado sin cambios:

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

El combinador K también es bastante sencillo: debe descartar su segundo argumento.

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

El combinador S es el más complejo; su comportamiento puede resumirse aplicando los dos primeros argumentos al tercer argumento, y aplicando el primer resultado al segundo. Podemos probar el combinador S más fácilmente probando algunas de sus formas al curry. S(K) , por ejemplo, simplemente debe devolver su segundo argumento y descartar el primero, como vemos que sucede:

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

S(I)(I) debería aplicar su argumento a sí mismo:

@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) aplica su segundo argumento a su primer argumento:

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

El combinador I descrito anteriormente tiene un nombre en la Base Julia estándar: identity . Por lo tanto, podríamos haber reescrito las definiciones anteriores con la siguiente definición alternativa de I :

const I = identity

Mostrando SKI Combinadores

Una debilidad con el enfoque anterior es que nuestras funciones no se muestran tan bien como nos gustaría. Podríamos reemplazar

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

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

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

¿Con algunas pantallas más informativas? ¡La respuesta es sí! Vamos a reiniciar el REPL, y esta vez definamos cómo se mostrará cada función:

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

Es importante evitar mostrar nada hasta que hayamos terminado de definir funciones. De lo contrario, corremos el riesgo de invalidar el caché de métodos, y nuestros nuevos métodos no parecerán tener efecto de inmediato. Por eso hemos puesto punto y coma en las definiciones anteriores. Los puntos y coma suprimen la salida del REPL.

Esto hace que las funciones se muestren muy bien:

julia> S
S

julia> K
K

julia> I
I

Sin embargo, todavía nos encontramos con problemas cuando intentamos mostrar un cierre:

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

Sería mejor mostrar eso como S(K) . Para hacer eso, debemos explotar que los cierres tienen sus propios tipos individuales. Podemos acceder a estos tipos y agregarles métodos a través de la reflexión, utilizando typeof y el campo primary campo de name del tipo. Reinicie el REPL otra vez; Vamos a hacer más cambios:

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)

Y ahora, por fin, las cosas se muestran como nos gustaría:

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