Quelles sont les structures de données derrière une feuille de calcul?

J'aimerais comprendre comment une feuille de calcul (un groupe de cellules nommées ou autrement identifiées contenant des valeurs ou des formules faisant référence à d'autres cellules) est résolue. J'ai essayé de regarder des projets existants, mais il y avait tellement de choses avec l'interface graphique, la sérialisation, les événements, etc. que je n'ai pas pu trouver la feuille de calcul.

Au plus simple, comment ça marche?

Un tableur est essentiellement un langage fonctionnel avec typage dynamique, chaque fonction ou valeur pouvant être référencée sous forme de cellule dans la matrice.

Au lieu de choses comme (defn some-name ...)la some-namepièce est placée dans une cellule elle-même.

Si vous passez à un ide de langage fonctionnel à mise à jour dynamique (tel que lighttable for clojure), vous verrez une grande partie des mêmes fonctionnalités qu'un tableur. Liez une valeur à un nom, écrivez une fonction qui utilise cette valeur, changez la valeur et la sortie de la fonction change immédiatement. C’est la même chose que de faire quelque chose comme écrire =A1 + B2à l’emplacement d’ C3excellent.

Ainsi, les programmeurs fonctionnels aiment souvent écrire des tableurs sous forme de programmes de jouets ... et aussi de sujets de recherche. (Oui, je suis désolé, ils sont tous derrière un paywall ACM.org)

• Programmation fonctionnelle de tableur

  La communauté de programmation fonctionnelle a manifesté un certain intérêt pour les feuilles de calcul, mais étonnamment, personne ne semble avoir envisagé de faire fonctionner une feuille de calcul standard, telle qu'Excel, avec un langage de programmation fonctionnel standard, tel que Haskell. Dans cet article, nous montrons une façon de faire cela. Nous espérons que, ce faisant, nous pourrions convaincre les programmeurs de tableurs d’essayer la programmation fonctionnelle.

• Forms / 3: Un langage visuel de premier ordre pour explorer les limites du paradigme du tableur

  Bien que les détracteurs de la programmation fonctionnelle prétendent parfois que la programmation fonctionnelle est trop difficile ou contre-intuitive à comprendre et à utiliser pour la plupart des programmeurs, la preuve du contraire peut être trouvée en regardant la popularité des feuilles de calcul. Le paradigme tableur, un sous-ensemble de premier ordre du paradigme de la programmation fonctionnelle, a été largement accepté par les programmeurs et les utilisateurs finaux. Néanmoins, la plupart des systèmes de tableurs présentent de nombreuses limitations. Dans cet article, nous discutons des fonctionnalités de langage qui éliminent plusieurs de ces limitations sans s'écarter du modèle d'évaluation déclaratif de premier ordre.

• Mise en œuvre des feuilles de calcul

  Une grande partie du développement de l'utilisateur final se fait avec des feuilles de calcul. La métaphore de la feuille de calcul est attrayante car visuelle et permet l’expérimentation interactive, mais comme l’observent Peyton Jones, Blackwell et Burnett, la métaphore de la feuille de calcul n’admet même pas l’abstraction la plus élémentaire: transformer une expression en une fonction nommée. Par conséquent, ils ont proposé un moyen de définir une fonction en termes de feuille de calcul avec des cellules d'entrée et de sortie désignées; nous l'appellerons une feuille de fonction.

Le début de Spreadsheet sur Wikipedia donne quelques astuces pour en implémenter un:

Un tableur est un programme d’application informatique interactif permettant d’organiser et d’analyser des données sous forme de tableau. Les tableurs ont été développés sous forme de simulations informatisées de feuilles de calcul comptables. Le programme fonctionne sur des données représentées sous forme de cellules d'un tableau, organisées en lignes et en colonnes. Chaque cellule du tableau est un élément modèle – vue – contrôleur pouvant contenir des données numériques ou textuelles, ou les résultats de formules qui calculent et affichent automatiquement une valeur en fonction du contenu des autres cellules.

S'appuyant sur ceci à partir du schéma du paradigme Model-View-Controller tel qu'il est exprimé dans les bibliothèques Java . L’auteur mentionne ensuite les applets (un peu daté, il a été écrit de 1993 à 1996) et mentionne sa page Web qui se trouve sur http://csis.pace.edu/~bergin/Java/applets.htm (oui , applets) pour le code de feuille de calcul correspondant http://csis.pace.edu/~bergin/Java/Spreadsheet.java

Je ferai remarquer que l'intégralité du tableur n'est pas si grande dans cette applet 570 lignes, y compris la documentation.

Cela dit, selon la langue, vous pouvez probablement tout faire avec uniquement des pointeurs de fonction dans un tableau fragmenté.

Conceptuellement, chaque cellule est un nœud d'un graphe acyclique dirigé , et les références à d'autres cellules créent des arêtes dans ce graphe. Lorsque vous modifiez une cellule, un tri topologique de tous les nœuds accessibles depuis la cellule modifiée vous donnera l'ordre nécessaire pour évaluer les cellules. Une fois que vous avez déterminé le bon ordre, il ne reste plus que l'analyse syntaxique standard.

Comme mentionné précédemment, un tableur est facilement implémenté sous forme de DAG (graphe acyclique dirigé) stocké dans un simple hachage ou un dictionnaire. Un code simple à utiliser est probablement le moyen le plus simple de le comprendre:

Une version très simple de Python: http://code.activestate.com/recipes/355045-spreadsheet/

Ceci a été expliqué et développé dans ce billet de blog: http://ralsina.me/weblog/posts/BB585.html

Il existe également une version JavaScript simple avec une interface graphique ici: http://jsfiddle.net/ondras/hYfN3/

J'ai codé un paquet Python qui vous permet de convertir la structure de cellules de fonction d'objectif de fichier MS Excel en Python. XL2py

Les valeurs de cellule sont analysées dans un objet de type dict () qui ajoute leurs valeurs. Les cellules avec des références à d'autres cellules par des formules comprennent des nœuds. Les nœuds font référence à une cellule dont la valeur est définie par sa formule. A partir de chaque formule de nœud, une structure de dépendance est définie afin de définir si les références circulaires existent ou non. Les ordres de calcul de nœud sont définis en prenant en compte les structures de dépendance des cellules impliquées.

À partir de l'arborescence des E / S, vous pouvez utiliser à votre guise n'importe quel algorithme de minimisation implémenté en Python.

Je vous suggère de jeter un coup d'œil sur https://github.com/gusmaogabriels/XL2py

Cordialement, Gabriel