Programación Funcional y Computación Científica

Pido disculpas si esta es una pregunta vaga, pero aquí va:

En los últimos años, la programación funcional ha recibido mucha atención en la comunidad de Ingeniería de Software. Muchos comenzaron a usar lenguajes como Scala y Haskell y afirmaron tener éxito sobre otros lenguajes y paradigmas de programación. Mi pregunta es: como expertos en informática de alto rendimiento / informática científica, ¿deberíamos estar interesados ​​en la programación funcional? ¿Deberíamos participar en esta mini revolución?

¿Cuáles son los pros y los contras de la programación funcional en el dominio de trabajo SciComp?

Solo he hecho un poco de programación funcional, así que tome esta respuesta con un poco de sal.

Pros:

• La programación funcional se ve muy matemática; Es un buen paradigma para expresar algunos conceptos matemáticos
• Hay buenas bibliotecas disponibles para cosas como la verificación formal de programas y la prueba de teoremas, por lo que es posible escribir programas que razonen sobre programas; este aspecto es bueno para la reproducibilidad
• Puede hacer programación funcional en Python y C ++ a través de expresiones lambda; También puedes hacer programación funcional en Julia y Mathematica
• No muchas personas lo usan, por lo que puede ser un pionero. Al igual que los primeros usuarios de MATLAB, Python, R y ahora Julia, es necesario que los primeros adopten la programación funcional para que se ponga al día

Contras:

• Los lenguajes que generalmente se consideran lenguajes de programación funcionales, como Haskell, OCaml (y otros dialectos de ML) y Lisp generalmente se consideran lentos en relación con los lenguajes utilizados para la informática científica crítica del rendimiento. OCaml es, en el mejor de los casos, aproximadamente la mitad de rápido que C.
• Estos lenguajes carecen de infraestructura de biblioteca en comparación con los lenguajes comúnmente utilizados en ciencia computacional (Fortran, C, C ++, Python); Si desea resolver un PDE, es mucho más fácil hacerlo en un lenguaje más comúnmente utilizado en ciencia computacional que uno que no lo es.
• No hay tanta comunidad de ciencia computacional que use lenguajes de programación funcionales como la que usa lenguajes de procedimiento, lo que significa que no obtendrá mucha ayuda para aprenderlo o depurarlo, y la gente probablemente le dará basura por usándolo (lo merezca o no)
• El estilo de la programación funcional es diferente del estilo utilizado en la programación de procedimientos, que generalmente se enseña en las clases introductorias de informática y en las clases de tipo "MATLAB para científicos e ingenieros".

Creo que muchas de las objeciones en la sección "Contras" podrían superarse. Como es un punto de discusión común en este sitio de Stack Exchange, el tiempo de desarrollador es más importante que el tiempo de ejecución. Incluso si los lenguajes de programación funcional son lentos, si las partes críticas para el rendimiento se pueden delegar a un lenguaje de procedimiento más rápido y si se pueden demostrar ganancias de productividad a través del desarrollo rápido de aplicaciones, entonces valdría la pena usarlas. Vale la pena señalar aquí que los programas implementados en Python puro, MATLAB puro y R puro son considerablemente más lentos que las implementaciones de estos mismos programas en C, C ++ o Fortran. Lenguajes como Python, MATLAB y R son populares precisamente porque intercambian velocidad de ejecución por productividad, e incluso entonces, Python y MATLAB tienen facilidades para implementar interfaces para el código compilado en C o C ++ para que el código crítico para el rendimiento pueda implementarse para ejecutarse rápidamente. La mayoría de los lenguajes tienen una interfaz de función ajena a C, que sería suficiente para interactuar con la mayoría de las bibliotecas de interés para los científicos informáticos.

¿Deberías estar interesado en la programación funcional?

Todo depende de lo que creas que es genial. Si eres el tipo de persona que está dispuesto a romper la convención y estás dispuesto a pasar por el trabajo de evangelizar a las personas sobre las virtudes de lo que sea que quieras hacer con la programación funcional, yo diría que anímate . Me encantaría ver a la gente hacer cosas geniales con la programación funcional en la ciencia computacional, aunque solo sea para demostrar que todos los detractores están equivocados (y habrá muchos detractores). Si no eres el tipo de persona que quiere lidiar con un grupo de personas que te preguntan: "¿Por qué demonios estás usando un lenguaje de programación funcional en lugar de (inserta aquí su lenguaje de programación de procedimiento favorito)?", Entonces no lo haría molestar

Se han utilizado algunos lenguajes de programación funcionales para el trabajo intensivo de simulación. La firma comercial cuantitativa Jane Street utiliza OCaml para el modelado financiero y la ejecución de sus estrategias comerciales. OCaml también se usó en FFTW para generar algún código C utilizado en la biblioteca. Liszt es un lenguaje específico de dominio desarrollado en Stanford e implementado en Scala que se utiliza para resolver PDE. La programación funcional se usa definitivamente en la industria (no necesariamente en ciencia computacional); queda por ver si despegará en la ciencia computacional.

Tal vez tengo una perspectiva única sobre esto porque soy un profesional de HPC con experiencia en computación científica y un usuario de lenguaje de programación funcional. No quiero equiparar el HPC con el cálculo científico, pero existe una intersección considerable, y ese es el punto de vista que tomo al responder esto.

Por ahora, es poco probable que los lenguajes funcionales se adopten en HPC principalmente porque los usuarios y clientes de HPC realmente se preocupan por lograr el máximo rendimiento posible. Es cierto que cuando el código se escribe de manera funcional, naturalmente expone un paralelismo que puede explotarse, pero en HPC eso no es suficiente. El paralelismo es solo una pieza del rompecabezas para lograr un alto rendimiento, también debe tener en cuenta una amplia gama de detalles micro-arquitectónicos y hacer esto generalmente requiere un control muy detallado sobre la ejecución del código, ese control no está disponible en ninguna lenguajes funcionales que yo sepa.

Dicho esto, tengo grandes esperanzas de que esto pueda cambiar. He notado una tendencia de que los investigadores están comenzando a darse cuenta de que muchas de estas optimizaciones micro arquitectónicas pueden automatizarse (hasta cierto punto). Esto ha generado un zoológico de tecnología de compilación de fuente a fuente donde un usuario ingresa una "especificación" del cómputo que quiere que suceda, y el compilador emite código C o Fortran que realiza ese cómputo con las optimizaciones y el paralelismo necesarios para eficientemente usa la arquitectura objetivo. Por cierto, esto es lo que los lenguajes funcionales están bien adaptados para hacer: modelar y analizar lenguajes de programación. No es casualidad que los primeros grandes usuarios de lenguajes funcionales fueran desarrolladores de compiladores. Con algunas excepciones notables, no he visto que esto realmente se apodere todavía, pero las ideas están ahí,

Me gustaría agregar un aspecto a las otras dos respuestas. Dejando a un lado el ecosistema, la programación funcional brinda una gran oportunidad para la ejecución paralela, como el subprocesamiento múltiple o la computación distribuida. Sus propiedades inmutables inherentes lo hacen adecuado para el paralelismo, que generalmente es un verdadero dolor en el * bleep * cuando se trata de lenguajes imperativos.

Dado que la mejora en el rendimiento del hardware en los últimos años se ha centrado en agregar núcleos a los procesadores en lugar de impulsar frecuencias más altas, la computación paralela se está volviendo mucho más popular (apuesto a que todos lo saben).

Otra cosa que menciona Geoff es que el tiempo del desarrollador a menudo es más importante que el tiempo de ejecución. Trabajo para una empresa que construye un SaaS computacionalmente intensivo e hicimos una prueba de rendimiento inicial cuando comenzamos, enfrentando C ++ frente a Java. Descubrimos que C ++ proporcionó aproximadamente un 50% de reducción en el tiempo de ejecución sobre Java (esto fue para la geometría computacional y las cifras probablemente variarán dependiendo de la aplicación), pero de todos modos elegimos Java debido a la importancia del tiempo del desarrollador y esperábamos que Las optimizaciones y las futuras mejoras en el rendimiento del hardware nos ayudarían a llegar al mercado. Puedo decir con confianza que si hubiéramos elegido lo contrario, aún no estaríamos en el negocio.

Ok, pero Java no es un lenguaje de programación funcional, entonces, ¿qué tiene que ver con algo? Bueno, más adelante, a medida que empleamos más defensores del paradigma funcional y tropezamos con la necesidad de paralelización, migramos progresivamente partes de nuestro sistema a Scala, que combina los aspectos positivos de la programación funcional con el poder del imperativo y se combina bien con Java. Nos ha ayudado enormemente al aumentar el rendimiento de nuestro sistema con un mínimo dolor de cabeza y probablemente continuará obteniendo beneficios de mayores aumentos de rendimiento en el negocio del hardware cuando haya más núcleos en los procesadores del mañana.

Tenga en cuenta que estoy totalmente de acuerdo con los inconvenientes mencionados en las otras respuestas, pero pensé que la facilitación de la ejecución paralela es un profesional tan poderoso que no podría dejar de mencionarse.

Geoff ya ha dado una buena descripción de las razones a las que tengo poco que agregar aparte de enfatizar uno de sus puntos: ecosistema. Ya sea que esté abogando por la programación funcional o cualquier otro paradigma, una de las preguntas importantes que debe abordar es que hay una increíble cantidad de software que todos los demás pueden construir sobre el que tiene que volver a escribir. Ejemplos son MPI, PETSc o Trilinos para álgebra lineal, o cualquiera de las bibliotecas de elementos finitos, todas escritas en C o C ++. Hay una gran cantidad de inercia en el sistema, tal vez no porque todos piensen que C / C ++ es, de hecho, el mejor lenguaje para escribir software computacional, sino porque muchas personas han pasado años de sus vidas creando algo útil para mucha gente.

Creo que la mayoría de las personas informáticas estarán de acuerdo en que es muy valioso probar nuevos lenguajes de programación y evaluar su idoneidad para este problema. Pero será un momento difícil y solitario porque no podrá producir resultados que sean competitivos con lo que todos los demás están haciendo. También puede otorgarle una reputación como alguien que comenzó el próximo movimiento hacia un paradigma de programación diferente. ¡Oye, C ++ solo tardó unos 15 años en reemplazar a Fortran!

El resumen rápido es que

1. La computación numérica utiliza mutabilidad / efectos secundarios para lograr la mayoría de sus aceleraciones y reducir las asignaciones (muchas estructuras de programación funcional tienen datos inmutables)
2. La evaluación diferida puede ser difícil de usar con códigos numéricos.
3. O está desarrollando un paquete en el que la caída a los niveles más bajos para el rendimiento realmente importa (C / Fortran o ahora Julia) (en estos también puede editar el código del ensamblador según sea necesario), o está escribiendo un script que utiliza estas bibliotecas rápidas por lo que generalmente le importa el tiempo de desarrollo (y elige Julia / MATLAB / Python / R). Los lenguajes funcionales tienden a situarse en un punto medio extraño que es útil en otras disciplinas, pero no tan útil aquí.
4. $x_n$$x_{n+1}$

Estos hechos juntos hacen que la programación funcional no parezca necesaria para la mayoría de los usuarios.

Creo que es interesante notar que el uso de la programación funcional en Computational Science no es nuevo. Por ejemplo, este documento de 1990 mostró cómo mejorar el rendimiento de los programas numéricos escritos en Lisp (posiblemente el lenguaje de programación funcional más antiguo) utilizando una evaluación parcial. Este trabajo fue parte de una cadena de herramientas utilizada en un artículo de 1992 por GJ Sussman (de la fama del SICP ) y J Wisdom que proporcionó evidencia numérica del comportamiento caótico del Sistema Solar . Puede encontrar más detalles sobre el hardware y el software involucrados en ese cálculo aquí .

R es un lenguaje funcional y también un lenguaje de estadísticas (y ahora aprendizaje automático) y, de hecho, el idioma número 1 para estadísticas. Sin embargo, no es un lenguaje HPC: no se usa para la "combinación de números" tradicional como simulaciones físicas, etc. Pero se puede hacer que se ejecute en grupos masivos (por ejemplo, a través de MPI) para simulaciones estadísticas masivas (MCMC) de aprendizaje automático.

Mathematica también es un lenguaje funcional, pero su dominio principal es la computación simbólica en lugar de la computación numérica.

En Julia también puede programar en un estilo funcional (junto al procedimiento y su sabor de OO (envío múltiple)) pero no es puro (las estructuras de datos base son mutables (excepto las tuplas), aunque hay algunas bibliotecas con inmutables estructuras de datos funcionales. Más importante aún, es mucho más lento que el estilo de procedimiento, por lo que no se usa mucho.

No llamaría a Scala un lenguaje funcional, sino más bien un híbrido objeto-funcional. Puede usar muchos conceptos funcionales en Scala. Scala es importante para la computación en la nube debido a Spark ( https://spark.apache.org/ ).

Tenga en cuenta que Fortran moderno tiene en realidad algunos elementos de programación funcional: tiene una semántica de puntero estricta (a diferencia de C), puede tener funciones puras (sin efectos secundarios) (y marcarlo como tal) y puede tener inmutabilidad. Incluso tiene una indexación inteligente donde puede especificar condiciones para los índices de matriz. Esta es una consulta similar y normalmente solo se encuentra en un lenguaje de alto nivel como R de LINQ en C # o mediante funciones de filtro de orden superior en lenguajes funcionales. Por lo tanto, Fortran no es tan malo en absoluto, incluso tiene algunas características bastante modernas (por ejemplo, arreglos conjuntos) que no se encuentran en muchos idiomas. De hecho, en futuras versiones de Fortran, preferiría ver más características funcionales agregadas en lugar de características OO (que ahora es generalmente el caso) porque OO en Fortran es realmente incómodo y feo.

Los profesionales son las "herramientas" integradas en cada lenguaje funcional: es muy fácil filtrar datos, es muy fácil iterar sobre los datos y es mucho más fácil encontrar una solución clara y concisa a sus problemas.

La única desventaja es que tienes que entender este nuevo tipo de pensamiento: podría tomar algo de tiempo aprender lo que tienes que saber. Otros en el dominio SciComp realmente no usan esos idiomas, lo que significa que no puede obtener tanta ayuda :(

Si está interesado en lenguajes científicos funcionales, desarrollé uno https://ac1235.github.io

Aquí están mis argumentos sobre por qué la programación funcional puede y debe utilizarse para la ciencia computacional. Los beneficios son enormes, y las desventajas están desapareciendo rápidamente. En mi mente solo hay una estafa:

Con : falta de soporte de lenguaje en C / C ++ / Fortran

Al menos en C ++, esta estafa está desapareciendo, ya que C ++ 14/17 ha agregado potentes funciones para admitir la programación funcional. Es posible que deba escribir un código de biblioteca / soporte usted mismo, pero el idioma será su amigo. Como ejemplo, aquí hay una biblioteca (advertencia: plug) que hace arreglos multidimensionales inmutables en C ++: https://github.com/jzrake/ndarray-v2 .

Además, aquí hay un enlace a un buen libro sobre programación funcional en C ++, aunque no está enfocado en aplicaciones científicas.

Aquí está mi resumen de lo que creo que son los profesionales:

Pros :

• Exactitud
• Comprensibilidad
• Actuación

En términos de corrección , los programas funcionales están claramente bien planteados : te obligan a definir adecuadamente el estado mínimo de tus variables físicas y la función que avanza ese estado hacia adelante en el tiempo:

int main()
{
    auto state = initial_condition();

    while (should_continue(state))
    {
        state = advance(state);
        side_effects(state);
    }
    return 0;
}

Resolver una ecuación diferencial parcial (u ODE) es perfecta para la programación funcional; solo está aplicando una función pura ( advance) a la solución actual para generar la siguiente.

En mi experiencia, el software de simulación física es, en general, cargado por una mala gestión del estado . Por lo general, cada etapa del algoritmo opera en alguna parte de un estado compartido (efectivamente global). Esto hace que sea difícil, o incluso imposible, garantizar el orden correcto de las operaciones, dejando el software vulnerable a errores que pueden manifestarse como seg-faults, o peor, términos de error que no bloquean su código pero comprometen silenciosamente la integridad de su ciencia. salida. Intentar administrar el estado compartido en una simulación física también inhibe el subprocesamiento múltiple, lo cual es un problema para el futuro, ya que las supercomputadoras se están moviendo hacia conteos de núcleos más altos, y la ampliación con MPI a menudo supera las ~ 100k tareas. En contraste, la programación funcional hace que el paralelismo de memoria compartida sea trivial, debido a la inmutabilidad.

El rendimiento también mejora en la programación funcional debido a la evaluación perezosa de los algoritmos (en C ++, esto significa generar muchos tipos en tiempo de compilación, a menudo uno para cada aplicación de una función). Pero reduce la sobrecarga de accesos y asignaciones de memoria, así como elimina el despacho virtual, lo que permite que el compilador optimice un algoritmo completo al ver a la vez todos los objetos de función que lo componen. En la práctica, experimentará con diferentes arreglos de los puntos de evaluación (donde el resultado del algoritmo se almacena en caché en un búfer de memoria) para optimizar el uso de la CPU frente a las asignaciones de memoria. Esto es bastante fácil debido a la alta localidad (vea el ejemplo a continuación) de las etapas del algoritmo en comparación con lo que normalmente verá en un módulo o código basado en la clase.

Los programas funcionales son más fáciles de entender en la medida en que trivializan el estado físico. ¡Eso no quiere decir que su sintaxis sea fácilmente comprensible por todos sus colegas! Los autores deben tener cuidado de usar funciones bien nombradas, y los investigadores en general deben acostumbrarse a ver algoritmos expresados ​​funcionalmente en lugar de procedimientos. Admito que la ausencia de estructuras de control puede ser desagradable para algunos, pero no creo que eso nos impida avanzar hacia el futuro para poder hacer ciencia de mejor calidad en las computadoras.

A continuación se muestra una advancefunción de ejemplo , adaptada de un código de volumen finito utilizando el ndarray-v2paquete. Tenga en cuenta los to_sharedoperadores: estos son los puntos de evaluación a los que me refería anteriormente.

auto advance(const solution_state_t& state)
{
    auto dt = determine_time_step_size(state);
    auto du = state.u
    | divide(state.vertices | volume_from_vertices)
    | nd::map(recover_primitive)
    | extrapolate_boundary_on_axis(0)
    | nd::to_shared()
    | compute_intercell_flux(0)
    | nd::to_shared()
    | nd::difference_on_axis(0)
    | nd::multiply(-dt * mara::make_area(1.0));

    return solution_state_t {
        state.time + dt,
        state.iteration + 1,
        state.vertices,
        state.u + du | nd::to_shared() };
}