Каковы структуры данных за электронной таблицей?

Я хотел бы понять, как решается электронная таблица (группа именованных или иным образом идентифицированных ячеек, содержащих значения или формулы, ссылающиеся на другие ячейки). Я пытался посмотреть на существующие проекты, но с GUI, сериализацией, событиями и т. Д. Происходило так много всего, что я не смог найти электронную таблицу.

На самом простом, как это работает?

По своей сути электронная таблица представляет собой функциональный язык с динамической типизацией, и на каждую функцию или значение можно ссылаться как на ячейку в матрице.

Вместо того , чтобы такие вещи , как (defn some-name ...)в some-nameчасти помещается в самой клетке.

Если вы перейдете к динамически обновляемому функциональному языку ide (например, lighttable for clojure), вы увидите большую часть тех же функций, что и в электронной таблице. Свяжите значение с именем, напишите функцию, которая использует это значение, измените значение, и результат функции изменится немедленно. Это то же самое, что делать что-то вроде письма =A1 + B2в месте расположения C3в Excel.

Таким образом, функциональным программистам часто нравится писать электронные таблицы в виде игрушечных программ ... и предметом научных исследований тоже. (Да, извините, они все за платным доступом ACM.org)

• Функциональное программирование электронных таблиц

  Сообщество функционального программирования проявило некоторый интерес к электронным таблицам, но, как ни странно, никто не задумывался над тем, чтобы заставить стандартную электронную таблицу, такую ​​как Excel, работать со стандартным функциональным языком программирования, таким как Haskell. В этой статье мы покажем, как это можно сделать. Мы надеемся, что таким образом мы сможем заставить программистов электронных таблиц попробовать функциональное программирование.

• Формы / 3: визуальный язык первого порядка для изучения границ парадигмы электронных таблиц

  Хотя хулители функционального программирования иногда утверждают, что функциональное программирование слишком сложно или нелогично для большинства программистов, чтобы понять и использовать, доказательства обратного можно найти, посмотрев на популярность электронных таблиц. Парадигма электронных таблиц, подмножество парадигмы функционального программирования первого порядка, нашла широкое признание как среди программистов, так и среди конечных пользователей. Тем не менее, есть много ограничений в большинстве систем электронных таблиц. В этой статье мы обсуждаем языковые возможности, которые устраняют некоторые из этих ограничений, не отклоняясь от декларативной модели оценки первого порядка.

• Реализация электронных таблиц функций

  Большое количество разработок для конечных пользователей выполняется с помощью электронных таблиц. Метафора электронной таблицы привлекательна тем, что она визуальна и вмещает интерактивные эксперименты, но, как отмечают Пейтон Джонс, Блэквелл и Бернетт, метафора электронной таблицы не допускает даже самой основной абстракции: преобразования выражения в именованную функцию. Следовательно, они предложили способ определить функцию в терминах рабочего листа с назначенными ячейками ввода и вывода; мы назовем это функциональным листом.

Запуск Spreadsheet в Википедии дает несколько советов о том, как его реализовать:

Электронная таблица - это интерактивная компьютерная прикладная программа для организации и анализа данных в табличной форме. Электронные таблицы разрабатываются как компьютерное моделирование бумажных учетных листов. Программа работает с данными, представленными в виде ячеек массива, организованных в строки и столбцы. Каждая ячейка массива представляет собой элемент модель-представление-контроллер, который может содержать числовые или текстовые данные, или результаты формул, которые автоматически рассчитывают и отображают значение на основе содержимого других ячеек.

Основываясь на этом из парадигмы Outline of Model-View-Controller, как это выражено в библиотеках Java . Далее автор упоминает апплеты (немного устаревшие, они были написаны в 93–96 годах) и упоминает свою веб-страницу, которая находится по адресу http://csis.pace.edu/~bergin/Java/applets.htm (да , апплеты) для соответствующего кода электронной таблицы http://csis.pace.edu/~bergin/Java/Spreadsheet.java

Я укажу, что вся таблица не так велика в этом апплете, 570 строк, включая документацию.

Тем не менее, в зависимости от языка, вы, вероятно, могли бы делать все это только с помощью указателей на функции в разреженном массиве.

Концептуально каждая ячейка является узлом ориентированного ациклического графа , а ссылки на другие ячейки создают ребра в этом графе. Когда вы меняете ячейку, топологическая сортировка всех узлов, доступных из ячейки, которую вы изменили, даст вам порядок, необходимый для оценки ячеек. Как только вы определили правильный порядок, это просто стандартный анализ выражения.

Как уже упоминалось, электронная таблица легко реализуется как DAG (ориентированный ациклический граф), хранящийся в простом хеше или словаре. Некоторый простой код для игры, вероятно, самый простой способ понять это:

Очень простая версия Python: http://code.activestate.com/recipes/355045-spreadsheet/

Это было объяснено и разработано в этом сообщении в блоге: http://ralsina.me/weblog/posts/BB585.html

Здесь также есть простая версия JavaScript с графическим интерфейсом: http://jsfiddle.net/ondras/hYfN3/

Я кодировал пакет Python, который позволяет преобразовывать структуру ячеек целевой функции файла MS Excel в Python. XL2py

Значения ячеек анализируются для объекта типа dict (), к которому добавляются их значения. Клетки со ссылками на другие клетки по формулам составляют узлы. Узлы относятся к ячейке, значение которой определяется ее формулой. Из каждой формулы узла определяется структура зависимости, чтобы определить, существуют ли циклические ссылки или нет. Порядок расчета узлов определяется с учетом структур зависимостей участвующих ячеек.

Что касается древовидной структуры ввода / вывода, вы можете использовать любой алгоритм минимизации, реализованный в Python, по своему желанию.

Я бы посоветовал вам взглянуть на https://github.com/gusmaogabriels/XL2py

С наилучшими пожеланиями, Габриэль