¿Cuál es el nombre de este combinador?

Question

Recientemente comencé a leer casualmente en la lógica combinatoria, y noté que una función de orden superior que uso regularmente es un combinador. Este combinador es realmente bastante útil (puede usarlo para definir la adición de ecuaciones polinomiales, por ejemplo), pero nunca le di un nombre decente. ¿Alguien reconoce este combinador? (ignorando las diferencias en el curry de la función)

unknown = function (h, f, g)
    function (x) h( f(x), g(x) )
}

En el cálculo de Lambda, la implementación completamente curriada sería $ lambda h. lambda f. lambda g. lambda x. H (FX) (GX) $. En otras palabras, si $ M $ es este combinador misterioso, entonces su ecuación definitoria es $ M , H , F , G , X = H , (F , X) , (G , X) ps

Si se necesita más información, o mi pregunta carece de información clave, deje un comentario y editaré mi pregunta.

Answer 1

Este no es probablemente un nombre estándar, pero en La implementación de lenguajes de programación funcional En la sección 16.2.4 Simon Peyton Jones lo llama S'. Se define como un combinador de optimización

S (B x y) z = S' x y z

El siguiente ejemplo es de la sección mencionada. Considerar

λx_n...λx_1.PQ

dónde P y Q son una expresión complicada que ambos usan todas las variables. Eliminar las abstracciones de lambda conduce al aumento cuadrático de los tamaños de los términos en n:

P Q
S P1 Q1
S (B S P2) Q2
S (B S (B (B S) P3)) Q3
S (B S (B (B S) (B (B (B S)) P4))) Q4

etc., donde Pi y Qi son algunos términos. Con la ayuda de S' Esto solo se vuelve lineal:

P Q
S P1 Q1
S' S P2 Q2
S (S' S) P3 Q3
S (S' (S' S)) P4 Q4