Funciones Do orden superior proporcionan más potencia a la programación funcional?

Question

Le he pedido a una pregunta similar en cstheory.SE .

De acuerdo con esta respuesta en Stackoverflow existe un algoritmo que en un lenguaje de programación funcional pura no tiene un vago $ \ Omega (n \ log n) $ complejidad, mientras que el mismo algoritmo de programación imperativa es $ \ Omega (n) $. La adición de pereza a la lengua FP haría que el algoritmo de $ \ Omega (n) $.

¿Hay alguna relación equivalente comparando un lenguaje FP con y sin funciones de orden superior? ¿Sigue siendo Turing completo? Si es así, lo hace la falta de orden superior de FP hace que el lenguaje menos "potente" o eficiente?

Answer 1

En un lenguaje de programación funcional que es lo suficientemente potente (por ejemplo, con tipos de datos para implementar cierres ) se puede eliminar todos los usos de orden superior mediante la transformación de desfuncionalización . Puesto que se utiliza este método para compilar este tipo de lenguaje, se puede asumir razonablemente que esto no afecta a las actuaciones y que en este entorno de orden superior no hace que el lenguaje sea menos potente. Sin embargo sí afecta a la forma de escribir código.

Sin embargo, si el idioma no es lo suficientemente potente, entonces sí, de orden superior proporciona potencia expresiva. Considere el cálculo lambda:. Sin ninguna función de orden superior, lo que realmente no puede hacer nada, sobre todo porque los tipos de datos básicos la mayoría (enteros, booleanos) se implementan utilizando funciones

En conclusión, lo que realmente depende del idioma.

---

Por encima es mi respuesta. A continuación, un comentario acerca de un supuesto habitual en los lenguajes imperativos.

sobre un algoritmo que en un lenguaje de programación funcional no tiene un vago $ \ Omega (n \ log n) $ complejidad, mientras que el mismo algoritmo de programación imperativa es $ \ Omega (n) $. La adición de pereza a la lengua FP haría que el algoritmo de $ \ Omega (n) $.

Me gustaría ver esta referencia. La suposición habitual es que un acceso a una matriz de longitud $ n $ en una RAM está en el tiempo $ O (1) $ y el equivalente en FP pura está en en el tiempo $ O (\ log n) $. Eso no es del todo cierto: el tiempo de acceso en una memoria RAM es de $ O (\ log m), donde $ $ $ m es el tamaño de la memoria. Por supuesto, m=n $ $. En la práctica el acceso a un elemento de una matriz es mucho más rápido. Una razón podría ser que $ m $ está delimitada, pero también lo es ... $ n $

EDIT: gracias por el enlace (el enlace para el artículo sobre la pereza no está disponible, aquí es otro ). Como se ha escrito en los comentarios y por encima en mi respuesta, el modelo de memoria RAM es un poco injusto FP pura proporcionando $ O (1) $ - tiempo look-ups, incluso cuando el tamaño de una dirección no está acotado. Estoy todavía a entender cómo funciona el truco perezosos pero yo creo que es importante tener en cuenta que esto es sólo para este problema en particular.

Answer 2

Depende de lo que entendemos por la expresividad.

Aquí es un argumento que de orden superior se le añade algo: con lenguajes de primer orden, recursión primitiva no es suficiente para expresar la función de Ackermann . Sin embargo, en la presencia de funciones de orden superior, la recursión primitiva es suficiente:

$$ \ Begin {array} {lcl} \ Textit {Ackermann} \ 0 & = & \ lambda x. x + 1 \\ \ Textit {Ackermann} \ (m + 1) & = & \ textit {Iter} \ (\ textit {Ackermann} \ m) \\ \ Textit {Iter} \ f \ 0 & = & f \ 1 \\ \ Textit {Iter} \ f \ (n + 1) & = & f \ (\ textit {Iter} \ f \ n) \ End {array} $$

Esto define la función de Ackermann utilizando sólo recursión primitiva.

Tenga en cuenta que $ \ textit {} $ Iter no es definible en teoría de la repetición convencional, ya que $ \ textit {} $ Iter es de orden superior. En teoría de la repetición convencional todas las funciones definibles tienen el tipo $ \ mathbb {N} ^ k \ rightarrow \ mathbb {N} $ para algunos $ k $, mientras que $ \ textit {Iter} $ tiene tipo $ (\ mathbb {N} \ rightarrow \ mathbb {N}) \ rightarrow (\ mathbb {N} \ rightarrow \ mathbb {N}) $.