Реляционное программирование с мемоизацией и отрицанием

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