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

Desde un punto de vista práctico, los combinadores son una especie de construcciones de programación que le permiten armar piezas de lógica de maneras interesantes y a menudo avanzadas. El uso típico de ellos depende de la posibilidad de poder empaquetar código ejecutable en objetos, a menudo llamadas (por razones históricas) funciones lambda o expresiones lambda, pero su millaje puede variar.

Un ejemplo simple de un combinador (útil) es uno que toma dos funciones lambda sin parámetros, y crea uno nuevo que los 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 que esto sea un combinador es la función anónima (función lambda) en la segunda línea; cuando llamas

a = in_sequence(f, g)

el objeto resultante a es no el resultado de ejecutar primero f () y luego g (), pero es un objeto al que puede llamar más tarde para ejecutar f () yg () 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' y 'in_sequence' son 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 flexible y de procedimiento. Por ejemplo, si usa el combinador in_parallel (..) para ejecutar el paralelismo en su programa, puede agregar la depuración relacionada con eso a la implementación del propio combinador in_parallel. Más adelante, si sospecha que su programa tiene un error relacionado con el paralelismo, en realidad puede simplemente reimplementar in_parallel:

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

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

Los combinadores son muy útiles cuando se usan correctamente.

El combinador Y, sin embargo, 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 en Y.

Es incorrecto etiquetar 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 tienes que arrancar rápidamente un lenguaje interpretado incrustado. Si proporciona un conjunto mínimo de primitivas, a saber, sequence , select , call , const y un closure allocation , ya es suficiente para construir un lenguaje complejo completo y arbitrario. No se necesita soporte especial para la recursión, 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 en el 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. Supercombinators se utilizan en algunas otras implementaciones. Este libro trata este tema en profundidad.

Esto es una broma , pero vale la pena una lectura muy cuidadosa, ya que hay muchas programaciones arcanas. Técnicas y teorías están cubiertas allí.

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

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