¿Qué son los combinadores y cómo se aplican a los proyectos de programación? (explicación práctica)

¿Qué son los combinadores?

Estoy buscando:

• una explicación práctica
• ejemplos de cómo se usan
• ejemplos de cómo los combinadores mejoran la calidad / generalidad del código

No estoy buscando

• explicaciones de los combinadores que no me ayudan a hacer el trabajo (como el combinador Y)

Desde un punto de vista práctico, los combinadores son construcciones de programación que le permiten armar piezas de lógica de maneras interesantes y a menudo avanzadas. Por lo general, usarlos depende de la posibilidad de poder empaquetar código ejecutable en objetos, a menudo llamados (por razones históricas) funciones lambda o expresiones lambda, pero su kilometraje puede variar.

Un ejemplo simple de un combinador (útil) es uno que toma dos funciones lambda sin parámetros y crea una nueva que las ejecuta en secuencia. El combinador real se ve en pseudocódigo genérico como este:

func in_sequence(first, second):
  lambda ():
    first()
    second()

Lo crucial que hace de esto un combinador es la función anónima (función lambda) en la segunda línea; cuando usted llama

a = in_sequence(f, g)

el objeto resultante a no es el resultado de ejecutar primero f () y luego g (), pero es un objeto al que puede llamar más tarde para ejecutar f () y g () en secuencia:

a() // a is a callable object, i.e. a function without parameters

De manera similar, puede tener un combinador que ejecuta dos bloques de código en paralelo:

func in_parallel(first, second):
  lambda ():
    t1 = start_thread(first)
    t2 = start_thread(second)
    wait(t1)
    wait(t2)

Y luego otra vez,

a = in_parallel(f, g)
a()

Lo bueno es que 'in_parallel' e 'in_sequence' son ambos combinadores con el mismo tipo / firma, es decir, ambos toman dos objetos de función sin parámetros y devuelven uno nuevo. De hecho, puedes escribir cosas como

a = in_sequence(in_parallel(f, g), in_parallel(h, i))

y funciona como se esperaba

Básicamente, los combinadores le permiten construir el flujo de control de su programa (entre otras cosas) de manera procesal y flexible. Por ejemplo, si usa el combinador in_parallel (..) para ejecutar paralelismo en su programa, puede agregar la depuración relacionada con eso a la implementación del combinador in_parallel. Más tarde, si sospecha que su programa tiene un error relacionado con el paralelismo, puede simplemente volver a implementar in_parallel:

in_parallel(first, second):
  in_sequence(first, second)

¡y con un solo golpe, todas las secciones paralelas se han convertido en secuenciales!

Los combinadores son muy útiles cuando se usan correctamente.

Sin embargo, el combinador Y no es necesario en la vida real. Es un combinador que le permite crear funciones auto recursivas, y puede crearlas fácilmente en cualquier lenguaje moderno sin el combinador Y.

Está mal calificar a Y-combinator como algo que no "ayudará a hacer el trabajo". Lo he encontrado muy útil en varias ocasiones. El caso más obvio es cuando tiene que arrancar rápidamente algún lenguaje interpretado incrustado. Si usted proporciona un conjunto mínimo de primitivas, es decir sequence, select, call, consty una closure allocation, que ya es suficiente para la construcción de un lenguaje complejo completo, arbitraria. No se necesita soporte especial para la recursividad: se puede agregar a través de un combinador de punto fijo. De lo contrario, necesitarás primitivas mucho más complicadas.

Otro caso obvio para los combinadores es la ofuscación. Un código traducido al cálculo de SKI es prácticamente ilegible. Si realmente tiene que ofuscar una implementación de un algoritmo, considere usar combinadores, aquí hay un ejemplo .

Y, por supuesto, los combinadores son una herramienta importante para implementar lenguajes funcionales. El enfoque más fácil (como en el ejemplo anterior) es a través de SKI o cálculo equivalente. Los supercombinatores se usan en algunas otras implementaciones. Este libro habla de ello en profundidad.

Esto es una broma , pero vale la pena leerlo con mucho cuidado, ya que allí se cubren muchas técnicas y teorías de programación arcana.

Excavando un poco, encontré una pregunta de StackOverflow, buena explicación de "Combinadores" (para no matemáticos) que es un primo cercano de esta pregunta. Una de las respuestas apuntaba al blog de Reginald Braithwaite, Homoiconic , que enlaza con varios ejemplos útiles de combinadores en código (por ejemplo, el combinador K , implementado por el Object#tapmétodo de Ruby ; lea la página para ver ejemplos de por qué es útil).

La página de Wikipedia sobre la lógica combinatoria describe los combinadores de manera más global.