¿Cuáles son las estructuras de datos detrás de una hoja de cálculo?

Me gustaría entender cómo se resuelve una hoja de cálculo (un grupo de celdas con nombre o identificadas que contienen valores o fórmulas que hacen referencia a otras celdas). Intenté mirar los proyectos existentes, pero sucedía tanto con la GUI, la serialización, los eventos, etc., que no pude encontrar la hoja de cálculo.

En su forma más simple, ¿cómo funciona?

En esencia, una hoja de cálculo es un lenguaje funcional con tipeo dinámico y cada función o valor puede ser referenciado como una celda en la matriz.

En lugar de cosas como (defn some-name ...)la some-nameparte se coloca en una celda.

Si va a una actualización dinámica de ide de lenguaje funcional (como lighttable para clojure), verá mucha de la misma funcionalidad que una hoja de cálculo. Vincula un valor a un nombre, escribe una función que use ese valor, cambia el valor y la salida de la función cambia inmediatamente. Esto es lo mismo que hacer algo como escribir =A1 + B2en la ubicación de C3in excel.

Por lo tanto, a los programadores funcionales a menudo les gusta escribir hojas de cálculo como programas de juguetes ... y también el tema de trabajos de investigación. (Sí, lo siento, todos están detrás de un muro de pago de ACM.org)

• Programación funcional de hoja de cálculo

  La comunidad de programación funcional ha mostrado cierto interés en las hojas de cálculo, pero sorprendentemente nadie parece haber considerado hacer que una hoja de cálculo estándar, como Excel, funcione con un lenguaje de programación funcional estándar, como Haskell. En este documento, mostramos una forma en que esto se puede hacer. Esperamos que al hacerlo, podamos lograr que los programadores de hojas de cálculo prueben la programación funcional.

• Formas / 3: un lenguaje visual de primer orden para explorar los límites del paradigma de la hoja de cálculo

  Aunque los detractores de la programación funcional a veces afirman que la programación funcional es demasiado difícil o contraintuitiva para que la mayoría de los programadores la entiendan y la utilicen, se puede encontrar evidencia de lo contrario al observar la popularidad de las hojas de cálculo. El paradigma de la hoja de cálculo, un subconjunto de primer orden del paradigma de la programación funcional, ha encontrado una amplia aceptación entre los programadores y los usuarios finales. Aún así, existen muchas limitaciones con la mayoría de los sistemas de hojas de cálculo. En este documento, discutimos las características del lenguaje que eliminan varias de estas limitaciones sin desviarse del modelo de evaluación declarativa de primer orden.

• Implementando hojas de cálculo de funciones

  Una gran cantidad de desarrollo del usuario final se realiza con hojas de cálculo. La metáfora de la hoja de cálculo es atractiva porque es visual y acomoda la experimentación interactiva, pero como lo observaron Peyton Jones, Blackwell y Burnett, la metáfora de la hoja de cálculo no admite ni la abstracción más básica: la de convertir una expresión en una función con nombre. Por lo tanto, propusieron una forma de definir una función en términos de una hoja de trabajo con celdas designadas de entrada y salida; lo llamaremos una hoja de funciones.

El inicio de la hoja de cálculo en Wikipedia ofrece algunos consejos sobre cómo implementar uno:

Una hoja de cálculo es un programa interactivo de aplicación informática para la organización y el análisis de datos en forma de tabla. Hojas de cálculo desarrolladas como simulaciones computarizadas de hojas de trabajo de contabilidad en papel. El programa funciona con datos representados como celdas de una matriz, organizados en filas y columnas. Cada celda de la matriz es un elemento modelo-vista-controlador que puede contener datos numéricos o de texto, o los resultados de fórmulas que calculan y muestran automáticamente un valor basado en el contenido de otras celdas.

Partiendo de esto a partir del esquema del paradigma Modelo-Vista-Controlador como se expresa en las bibliotecas Java . El autor continúa mencionando applets (un poco anticuado, fue escrito en '93 -'96) y menciona su página web que va a http://csis.pace.edu/~bergin/Java/applets.htm (sí , applets) para el código de hoja de cálculo correspondiente http://csis.pace.edu/~bergin/Java/Spreadsheet.java

Señalaré que la totalidad de la hoja de cálculo no es tan grande en este applet 570 líneas, incluida la documentación.

Dicho esto, dependiendo del idioma, probablemente podría hacerlo todo con solo punteros de función en una matriz dispersa.

Conceptualmente, cada celda es un nodo de un gráfico acíclico dirigido , y las referencias a otras celdas crean bordes en ese gráfico. Cuando cambia una celda, una clasificación topológica de todos los nodos accesibles desde la celda que cambió le dará el orden que necesita para evaluar las celdas. Una vez que haya determinado el orden correcto, es solo el análisis de expresiones estándar.

Como ya se mencionó, una hoja de cálculo se implementa fácilmente como un DAG (gráfico acíclico dirigido) almacenado en un simple hash o diccionario. Algún código simple para jugar es probablemente la forma más fácil de entenderlo:

Una versión muy simple de Python: http://code.activestate.com/recipes/355045-spreadsheet/

Esto fue explicado y elaborado en esta publicación de blog: http://ralsina.me/weblog/posts/BB585.html

También hay una versión simple de JavaScript con una GUI aquí: http://jsfiddle.net/ondras/hYfN3/

He codificado un paquete de Python que le permite convertir la estructura de celdas de función objetivo del archivo MS Excel en Python. XL2py

Los valores de celda se analizan en un objeto tipo dict () que agrega sus valores. Las celdas con referencias a otras celdas por fórmulas comprenden nodos. Los nodos se refieren a una celda cuyo valor está definido por su fórmula. A partir de cada fórmula de nodo, se define una estructura de dependencia para definir si existen referencias circulares o no. Las órdenes de cálculo de nodos se definen teniendo en cuenta las estructuras de dependencia de las células involucradas.

A partir de la estructura de árbol de E / S, puede utilizar cualquier algoritmo de minimización implementado en Python como lo desee.

Te sugiero que eches un vistazo a https://github.com/gusmaogabriels/XL2py

Saludos cordiales, Gabriel