Quais são as estruturas de dados por trás de uma planilha?

Gostaria de entender como é resolvida uma planilha (um grupo de células nomeadas ou identificadas contendo valores ou fórmulas que referenciam outras células). Tentei analisar os projetos existentes, mas havia muita coisa acontecendo com a GUI, serialização, eventos etc. que não consegui encontrar a planilha.

Na sua forma mais simples, como funciona?

Em sua essência, uma planilha é uma linguagem funcional com digitação dinâmica e cada função ou valor pode ser referenciado como uma célula na matriz.

Em vez de coisas como (defn some-name ...)a some-namepeça é colocada na própria célula.

Se você acessar um ide de linguagem funcional com atualização dinâmica (como lighttable para clojure), verá a mesma funcionalidade de uma planilha. Vincule um valor a um nome, escreva uma função que use esse valor, altere o valor e a saída da função muda imediatamente. É o mesmo que fazer algo como escrever =A1 + B2no local do C3excel.

Assim, programadores funcionais geralmente gostam de escrever planilhas como programas de brinquedos ... e também o assunto de trabalhos de pesquisa. (Sim, desculpe, todos eles estão por trás de um paywall do ACM.org)

• Programação funcional da planilha

  A comunidade de programação funcional mostrou algum interesse em planilhas, mas surpreendentemente ninguém parece ter considerado fazer uma planilha padrão, como o Excel, trabalhar com uma linguagem de programação funcional padrão, como Haskell. Neste artigo, mostramos uma maneira de fazer isso. Nossa esperança é que, ao fazer isso, possamos obter programadores de planilhas para experimentar a programação funcional.

• Forms / 3: uma linguagem visual de primeira ordem para explorar os limites do paradigma da planilha

  Embora os detratores da programação funcional às vezes afirmem que a programação funcional é muito difícil ou contra-intuitiva para a maioria dos programadores entender e usar, evidências contrárias podem ser encontradas observando a popularidade das planilhas. O paradigma da planilha, um subconjunto de primeira ordem do paradigma de programação funcional, encontrou ampla aceitação entre programadores e usuários finais. Ainda assim, existem muitas limitações na maioria dos sistemas de planilhas. Neste artigo, discutimos características da linguagem que eliminam várias dessas limitações sem se desviar do modelo de avaliação declarativa de primeira ordem.

• Implementando planilhas de funções

  Uma grande quantidade de desenvolvimento do usuário final é feita com planilhas. A metáfora da planilha é atraente porque é visual e acomoda experimentação interativa, mas conforme observado por Peyton Jones, Blackwell e Burnett, a metáfora da planilha não admite nem mesmo a abstração mais básica: transformar uma expressão em uma função nomeada. Por isso, eles propuseram uma maneira de definir uma função em termos de uma planilha com células de entrada e saída designadas; chamaremos de folha de funções.

O início da planilha na Wikipedia fornece algumas dicas de como implementar uma:

Uma planilha é um aplicativo de computador interativo para organização e análise de dados em forma de tabela. Planilhas desenvolvidas como simulações computadorizadas de planilhas de contabilidade em papel. O programa opera com dados representados como células de uma matriz, organizadas em linhas e colunas. Cada célula da matriz é um elemento de modelo-visualização-controlador que pode conter dados numéricos ou de texto ou os resultados de fórmulas que calculam e exibem automaticamente um valor com base no conteúdo de outras células.

Aproveitando isso a partir do paradigma Outline of Model-View-Controller, conforme expresso nas bibliotecas Java . O autor continua mencionando applets (um pouco datado, foi escrito em 93-96) e menciona sua página da web que vai para http://csis.pace.edu/~bergin/Java/applets.htm (sim , applets) para o código da planilha correspondente http://csis.pace.edu/~bergin/Java/Spreadsheet.java

Apontarei que a totalidade da planilha não é tão grande neste applet 570 linhas, incluindo a documentação.

Dito isto, dependendo do idioma, você provavelmente poderia fazer tudo isso apenas com ponteiros de função em uma matriz esparsa.

Conceitualmente, cada célula é um nó de um gráfico acíclico direcionado e as referências a outras células criam arestas nesse gráfico. Quando você altera uma célula, uma classificação topológica de todos os nós alcançáveis ​​a partir da célula que você alterou dará a ordem necessária para avaliar as células. Depois de determinar a ordem correta, é apenas a análise de expressão padrão.

Como já mencionado, uma planilha é facilmente implementada como um DAG (gráfico acíclico direcionado) armazenado em um hash ou dicionário simples. Algum código simples para brincar é provavelmente a maneira mais fácil de entendê-lo:

Uma versão muito simples do Python: http://code.activestate.com/recipes/355045-spreadsheet/

Isso foi explicado e elaborado nesta postagem do blog: http://ralsina.me/weblog/posts/BB585.html

Há também uma versão JavaScript simples com uma GUI aqui: http://jsfiddle.net/ondras/hYfN3/

Eu codifiquei um pacote python que permite converter a estrutura de células da função objetivo do arquivo do Microsoft Excel em Python. XL2py

Os valores das células são analisados ​​para um objeto do tipo dict () anexa seus valores. Células com referências a outras células por fórmulas compreendem nós. Os nós se referem a uma célula cujo valor é definido por sua fórmula. A partir de cada fórmula de nó, uma estrutura de dependência é definida para definir se as referências circulares existem ou não. As ordens de cálculo dos nós são definidas considerando as estruturas de dependência das células envolvidas.

A partir da estrutura em árvore de E / S, você pode usar qualquer algoritmo de minimização implementado no Python como desejar.

Eu sugiro que você dê uma olhada em https://github.com/gusmaogabriels/XL2py

Atenciosamente, Gabriel