Intérprete personalizado para expresiones matemáticas

Question

Tengo que evaluar un gran número de expresiones que contienen variables y estoy pensando en escribir un pequeño intérprete personalizado para mantener la compilación rápida y pequeña. Sin embargo, no tengo experiencia con este tema y tengo algunas preguntas.

Digamos que tenemos un archivo con expresiones matemáticas y un conjunto limitado de objetos. El archivo podría quedar así:

expr[x,y,z] = 2*x*y + x^2 + 28/14*z*(x*y^2 + 15*z) + ... 

me gustaría analizar esto de alguna manera para que pueda evaluar las expresiones numéricamente en mi solicitud simplemente llamando a una función expr(float x, float y, float z). El número de parámetros no debería ser fijo (EDITAR: cada expresión tendría su propia definición con el número apropiado de parámetros o aceptaría una matriz) y se debería permitir que la anidación de paréntesis mantenga los archivos de entrada razonablemente pequeños.

Dado que las expresiones son todas de tipo polinomial, puedo pensar en cómo debería ser la estructura de datos, pero el análisis parece difícil. Ya he encontrado algunas respuestas a preguntas algo similares aquí en SO, por ejemplo usando Lua.

La pregunta más importante, sin embargo, es cuál sería la penalización del rendimiento al crear y llamar a esos objetos en comparación con la compilación directa de estas expresiones del código C generado automáticamente.

¡Gracias de antemano!

EDITAR: Tenga en cuenta el ejemplo de expr() anterior solo como tal. Supongo que la mejor manera sería tener objetos de una clase con plantilla que contenga coeficientes y potencias de las variables en matrices dispersas.

Answer 1

El rendimiento es un poco de un problema de longitud de una cuerda. Los lenguajes interpretados casi siempre son más lentos que el código C compilado para evaluar expresiones aritméticas. Pero no es que muchos programas pasen la mayor parte de su tiempo haciendo aritmética, por lo que la mayoría de las veces eso no importa. También hace una diferencia si analiza la expresión cada vez que la evalúa o (como parece más probable a partir de lo que dice), la analiza en alguna forma intermedia.

Es imposible saber a partir de lo que ha dicho, si le importará o qué tan rápido escribirá un intérprete, pero no esperaría que sea mejor que 10 veces más lento, en cuanto al tiempo dedicado a evaluar las expresiones se refiere. Los primeros intentos de interpretación han sido mucho peores.

En cuanto a esa forma intermedia, el lugar habitual para comenzar es usar el algoritmo de Dijkstra "patio de maniobras" para convertir las expresiones de infijo a una forma polaca inversa. Eso le da una secuencia de "símbolos", "códigos de bytes", llámalos como prefiera, y es fácil escribir un evaluador de expresiones para esa forma: cada operador simplemente saca sus operandos de una pila, realiza el op, luego empuja el resultado en la pila, hasta que el valor final de la expresión sea lo único que quede al final. Los literales numéricos y los nombres de variables son simplemente como "operadores" que no revelan ningún operando, y presionan su valor.

[Editar: dependiendo de quiénes sean sus usuarios, podría ser factible que su programa tome ese archivo de texto, genere un programa C a partir de él, ejecute un compilador y luego ejecute el programa resultante (o, abra y llame al dll resultante). Obviamente, eso depende de muchas cosas específicas del sistema (un compilador está siendo instalado, por ejemplo), y las expresiones deberían evaluarse lo suficiente como para superar la sobrecarga de la compilación.]

Answer 2

Hay un ejemplo simple en el Bison Manual.

Answer 3

Ha declarado el problema como "expresiones complejas grandes" y le preocupan las penalizaciones de rendimiento. Entonces deberías considerar compilarlos, no interpretarlos. (los buenos intérpretes son 10 veces más lentos que el código compilado como regla general, los intérpretes pésimos/ad hoc tienden a ser significativamente peores).

La ruta habitual para esto es "compilar" las expresiones de alguna manera, lo que implica analizadores de construcción, generadores de código, optimizaciones, etc.

compiladores de C ya hacer todo esto. Así que creo que sería mucho mejor traducir estas expresiones a C. La compilación es fácil y la ejecución será increíblemente rápida en comparación con cualquier cosa que se pueda esperar como intérprete. Eso también se puede hacer usando un analizador sintáctico y una traducción dirigida por sintaxis mucho más simple.

Pero Si todas estas expresiones son producidas por Mathematica, tendrán una estructura bastante estándar pero no complicada. En este caso, supongo que podría escribir un traductor basado en expresiones regulares que pudiera asignar los formularios de Mathematica a las funciones C sin muchos problemas; Perl sería ideal para esto. Esto le brinda una solución fácil de implementar y muy rápida.

Por lo que vale, creo que Mathematica tiene una opción para convertir expresiones de Mathematica directamente en C. Parece que eso también valdría la pena echarle un vistazo.