Реализовать семантику вычислительной системы без синтаксиса (почти)

Рассмотрим задачу вычисления предикатов, в духе \(A \lor B \wedge C\) и так далее.

Итак, пусть есть программная система, которая подгружат комментарии с сайтов, чтобы пользователь (например, модератор), мог их отслеживать в едином интерфейсе и выполнять над ними какие-то действия. Список этих действий известен и предопределён.

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

Текст.
Имя пользователя.
Числоо отметок "Мне нравится" у комментария.
Дата редактирования.

Есть некоторый базовый набор утвеждений (операторов сравнения) для каждого признака:

Число отметок "Мне нравится" на комментарии =, ≠, >, <, ≥, ≤ заданному числу
Имя пользователя = заданной строке
Имя пользователя содержит строку Х
Текст комментария содержит строку Х

и так далее.

Эти базовые утверждения пользователь может объединять с помощью логических операторов \(\wedge\) или \(\lor\).

Задача программиста — реализовать API, позволяющий выполнять такие утверждения. API этот создаётся для другого программиста, который отвечает за интерфейс пользователя.

Как решать такую задачу?

Вместо того, чтобы идти от синтаксиса, пойдём сразу от семантики. Рассмотрим выражение \[ \text{Текст содержит "Банан"} \wedge "Мне нравится" > 15 \lor \text{Текст содержит "Много бананов"} \]

Приоритет операторов привычный:

операторы сравнения
конъюнкция
дизъюникция

Эту строку можно закодировать в виде стрyктуры данных, а приоритет определять положением каждого отдельного оператора в итоговой структуре.

Булев оператор мы представим как структуру из двух полей:

Оператор
Массив операндов

А операцию сравнения определим набором:

Оператор
Поле. Свойство комментария, значение которого будем сравнивать
Значение. Константа, с которой будем сравнивать

{
  Оператор: Или,
  операнды: [
  {
	Оператор: И,
	операнды: [
	{
		Оператор: Содержит,
		Поле: Текст,
		Значение: "Банан"
	},
	{
	      Оператор: Больше,
	      Поле: "Мне нравится",
	      Значение: 15
	}
	],
  },
  {
	 Оператор: Содержит,
	 Поле: Текст,
	 Значение: "Много бананов"
  }
  ]
}

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

Эту стурктуру, вместе с правилами построения, уже можно отдавать программисту интерфейсов, чтобы он уже начал работать над интерфейсом, а нам остаётся только реализовать вычисления выражений.

Фактически, такая структура определяет функцию от 1го аргумента: комментария. Для начала определим функции ЯП, ответственные за каждую операцию:

И(список значений подвыражений) ⇒ bool
Или(список значений подвыражений) ⇒ bool
Содержит(поле, значение, комментарий) ⇒ bool

и так далее…

Теперь в зависимости от того, какие инструменты предоставляет язык (и возможных оптимизаций, которые возможно придётся выполнять), у нас есть несколько вариантов развития событий.

Если есть возможность работать с функциями, как объектами первого порядка, то мы можем с помощью частичного применения, выполнить композицию, выбирая функции и известные значения операндов из структуры. Для нашего примера, результатом выполнения такого преобразования будет функция, определённая примерно вот так:

func = lambda Комментарий: Или(
    [
        И([
            Содержит("Текст", "Банан", Комментарий),
            Больше("Мне_нравится", 15, Комментарий)
        ]),
        Содержит("Текст", "Много бананов", Комментарий)
    ]
)

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

Теперь это правило можно вычислять для самых разных комментариев, просто вызывая func(комментарий).

А что если язык работает с фукнциями таким образом? Тогда один из доступных вариантов — интерпретация. Мы реализуем функцию-вычислитель, которая принимает уже 2 аргумента: структуру предиката и комментарий, который нужно обработать.

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

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

tag: Категория:Реализация на основе модели