Срок заказа для сложного абстрактного синтаксического дерева

Question

У меня есть вопрос об абстрактных синтаксических деревьях.
В частности, я хочу отсортировать несколько деревьев с определенным порядком терминов.

Как определить порядок терминов для AST со следующими свойствами:

1. Для всех почти всех терминов порядок ведет себя точно так же, как стандартный встроенный порядок терминов.
2. В AST глубоко вложены термины функтора pos / 6, обозначающие источник-positions.Эти функторы следует игнорировать в порядке следования терминов, то есть все члены функтора pos должны сравниваться как равные.

Возможно расширение встроенного порядка терминов с помощью специального случая для 'pos'?

Какое наиболее эффективное решение, какое решение наиболее читабельно?

Может быть, я должен также упомянуть, что наши AST могут быть довольно большими, я только что проверил один AST, у которого 217479функторы (игнорируя нулевые атомы)

Answer 1

Я бы определил отношение ast_without_pos / 2, которое связывает AST A0 с термином A, который совпадает с A0, за исключением того, что все подтермы pos / 6 заменены одним и тем же термином, скажем, atom t, а затем используйте стандартный порядок терминов на этих результирующих терминах. Я думаю, что это очень читабельно, а также достаточно эффективно.

Answer 2

Вы могли бы посмотреть на молнии над АСТ?

Вот пример над списками:

http://blog.logtalk.org/2013/04/zipper-lists-in-prolog/

Если вы получите исходники для Termite, я думаю, вы найдете более общую реализацию над деревьями.

http://www.complang.tuwien.ac.at/adrian/termite/Manual/Contents.html

Вам нужна помощь?