OP, кажется, интересуется языками, которые обрабатывают деревья и имеют некоторую поддержку параллелизма.
Наш набор инструментов для реинжиниринга программного обеспечения DMS - это анализ программ общего назначения идвигатель трансформации.Он анализирует исходный текст программирования на деревьях (первый интерес OP), позволяет анализировать и обрабатывать эти деревья, а также восстанавливать исходный текст из этих деревьев.В основе DMS лежат явные грамматики, описывающие обрабатываемый язык, и для него доступно множество определений языка производственного качества.
Механизм обработки дерева DMS обеспечивает поддержку параллелизма на двух разных уровнях, один из которых поддерживается напрямую.базовым языком параллельного программирования DMS, PARLANSE , который вдохновлен LISP, но не настолько динамичен.
PARLANSE предусматривает «команды» параллельных действий, называемых «зернами» (как в песке на пляже, идея заключается в том, что зерна много).Команды могут быть структурированы динамически, путем (классически) разветвления новых зерен и добавления их в (динамическую) команду;это полезно, но не очень быстро.Команды могут быть структурированы статически, включая «разделить этот набор зерен фиксированного размера как чистую параллель»:
(|| a b c)
и «создать набор зерен, порядок выполнения которых контролируется указанным частичным порядком» (! | ...) .Частичный порядок вы записываете непосредственно в вызове fork:
(!| step1 a
step2 b
step3 (>> step1 step2) c
step4 (>> step2) d )
, который кодирует тот факт, что действие c происходит после (позднее >> во времени)) действий a и b завершено.Статически сформированные команды прекомпилируются компилятором PARLANSE в довольно эффективные структуры, в которых зерна могут быть запущены и уничтожены очень быстро, что позволяет довольно маленький размер зерна (несколько сотен инструкций).У стандартных библиотек параллелизма намного больше издержек, чем у этого.
Основной метод обработки деревьев довольно обычен: есть библиотека PARLANSE для проверки узлов дерева, обхода дерева вверх и вниз, создания новых узлов и их объединения.на месте.Рекурсивные процедуры часто используются для посещения / обновления дерева.
Ключевое наблюдение здесь заключается в том, что посещение дерева, которое посещает некоторый набор детей, может быть закодировано последовательно или легко закодировано как статическая параллельная команда.Так что довольно легко вручную кодировать параллельные посещения дерева, за счет написания множества особых случаев для параллельной ветвления для каждого типа узла дерева.Есть «разделяй и властвуй», который кажется интересным для ОП.(Конечно, вы можете перечислить childern узлов и использовать динамическую команду, чтобы разбить зерна для каждого ребенка, но это не так быстро).Это первый уровень параллелизма, используемый для обработки деревьев в DMS.
Второй уровень параллелизма осуществляется через DSL, поставляемый DMS, который реализует грамматику атрибутов (AG).
AG - это функциональные языки, которые украшают BNF набором вычислений.Можно написать простой калькулятор с AG в DMS:
sum = sum + product;
<<Calculator>>: sum[0].result = sum[1].result + product.result;
Это приводит к вычислению атрибута «result» для корня (sum [0]) путем объединения атрибута result из первого дочернего элемента(сумма [1]) и второй ребенок (product.result).Так называемые синтезированные атрибуты распространяют информацию вверх по дереву из листьев;Унаследованные атрибуты распространяют информацию от родителей.Грамматики атрибутов вообще и AG DMS позволяют смешивать их, поэтому информация может перемещаться вверх и вниз по дереву в произвольном порядке.
Большинство АГ являются чисто функциональными, например, без побочных эффектов;DMS допускает побочные эффекты, которые усложняют обозначения, но довольно полезны на практике.Хорошим примером является построение таблиц символов путем оценки атрибута;current-scope передается по дереву, блоки локальных объявлений создают новые текущие области и передают их, а отдельные объявления сохраняют данные таблицы символов в записи таблицы символов, полученной от родителя.
Компилятор DMS AG анализирует вычисления атрибутов, определяет, как информация перемещается по всему дереву, а затем генерирует параллельную программу PARLANSE для реализации потока информации по типу узла дерева.Он может выполнить анализ потока данных по каждому правилу AG, чтобы определить поток информации и то, что должно произойти сначала по сравнению с последним по сравнению с последним.Для нашего простого правила суммирования, приведенного выше, должно быть ясно, что атрибуты потомков должны быть вычислены до того, как атрибут для корня может быть вычислен.Оказывается, что создание частичного порядка в PARLANSE является идеальным способом кодирования этой информации и даже прекрасно справляется с побочными эффектами, которые мы добавили в AG.
В результате DMS компилирует спецификацию AG в высокопараллельную PARLANSE.программа.Наш распознаватель имен / типов внешнего интерфейса C ++ реализован в виде примерно 150 тыс. Строк DMS AG (да, для описания того, как используется информация о типах C ++, требуется столько времени), который компилируется в приблизительно 700 тыс. SLOC параллельного кода PARLANSE.И он работает (и работает параллельно на многоядерных машинах x86) без какой-либо мысли или отладки, и, похоже, он хорошо масштабируется.