Можно ли реализовать простой типизированный лисп в системе типов TypeScript?

Отвечая на этот вопрос и предоставляя больше контекста в надежде, что это поможет людям, которые также боролись с проблемами такого типа. Я постараюсь также ответить на критические замечания, высказанные @jcalz в разделе комментариев исходного вопроса.

Сначала немного контекста

В настоящее время я работаю над механизмом правил для автоматизации выполнения задач в управляемом событиями облачном бэкэнде AWS. Цель состоит в том, чтобы пользователь мог указать абстрактное определение того, что он хотел бы сделать в ответ на определенное событие, сохранить это определение в базе данных, а затем выполнить конкретное действие, когда экземпляр события (s) о котором идет речь.

ПРИМЕР: Пользователь регистрируется на веб-сайте, и мы отправляем ему серию электронных писем с интервалами, установленными пользователем (например, через 3, 5 и 7 дней после — останавливая автоматизацию, если и когда они отвечают).

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

Наивный подход

Имея некоторый опыт работы с Clojure/Scheme в прошлом и учитывая мой многолетний опыт разработки ряда DSL/движков правил, я в целом обнаружил, что S-выражения, используемые в Lisps, являются наиболее гибким и простым способом реализации. такой язык.

Конечный результат может иметь следующий вид:

type Event = {
  timestampMillis: number;
  data: JSONObject;
};

type Context = Readonly<{
  priorEvents: Event[];
  currentEvent: Event
}>

type Expr<ReturnType extends JSONData, Context extends JSONObject> = ???

const DAY_MILLIS = 86400000;

const isThreeDaysAfterRegistration: Expr<boolean, Context> = 
  { "> = ": 
    { "ref": "$.currentEvent.timestampMillis" }, 
    { "+": [
      { "*": [ 3, DAY_MILLIS ] },
      { "first", { "map": {
        "$collection": { "ref": "$.priorEvents" }, 
        "$fn": { "ref": "$.item.timestampMillis" }
    ]}
  } as const;

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

type Expr<ReturnType extends JSONData, Context extends JSONObject> = 
  ReturnType extends boolean ?
    | { "or": readonly Expr<boolean, Context>[] }
    | { "and": readonly Expr<boolean, Context>[] }
    // ...
  : ReturnType extends number ?
    | { "+": readonly Expr<number, Context>[] }
    | { "-": readonly [Expr<number, Context>, ...Expr<number, Context>[]] }
    // ...
  : never;

Однако мы сталкиваемся с проблемами, когда начинаем иметь дело с типами более высокого порядка и рекурсией, а именно с JSONData[] и { readonly [S in string]: JSONData }, то есть массивами JSON и вложенными объектами.

Большая проблема в (маленьких) дженериках

Рассмотрим следующую простую формулировку: я хотел бы получить доступ и вернуть значение timestampMillis из первого Event в массиве priorEvents.

Мы можем структурировать небольшой набор структур выражений, чтобы попытаться закодировать это:

// Reference a value from the context
type Ref<T, C extends JSONData> = {
  [P in JSONPath<C>]: JSONPathValueType<P, C> extends T ? `$.${P}` : never;
}[JSONPath<C>];

type Expr<ReturnType extends JSONData, Context extends JSONObject> = 
  ReturnType extends number ?
    { "get": any extends Expr<infer B, Context> ? B extends JSONObject ? {
        "obj": Expr<B, Context>;
        "path": Ref<ReturnType, B>;
      } : never : never;
    }
    // ...
  : ReturnType extends JSONData[] ? 
    { "ref": Ref<ReturnType, Context> }
  : ReturnType extends JSONObject ? 
    { "first": Expr<ReturnType[], Context> }
  : never;

// Compilation Error: 
// Type 'string' is not assignable to type 'never'.
//
// The expected type comes from property 'path' which is declared here 
// on type '{ obj: { first: { ref: "$.priorEvents"; }; }; path: never; }'
const firstTimestamp: Expr<number, Context> = {
  get: {
    obj: { first: { ref: '$.priorEvents' } },
    path: '$.timestampMillis',
  },
};

Оказывается, лучшее, что компилятор Typescript может сделать с переменной path, — это сказать вам, что это строка. Поскольку тип path является функцией предполагаемого универсального типа B, а тип B может быть сужен только до конкретного типа JSONObject, мы не можем сделать никаких выводов о конкретных строках пути, которые вернули бы подмножество вложенных значений типа number (в данном случае). Более того, использование infer выше совершенно не нужно, поскольку его использование является просто неудачной попыткой создать общий ранг 2 в системе исключительно типа ранга 1.

Разглагольствования о рангах

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

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

1. Конечный набор строк, представляющих действительные пути в данном объекте.
2. Подмножество набора допустимых путей, которые содержат значение, соответствующее заданному ReturnType.

Второе ограничение имеет особое значение, поскольку оно позволяет нам фактически ввести выражение get конкретным образом; например если я хочу сказать, что firstTimestamp является выражением типа number

const firstTimestamp: Expr<number, Context> = {
  get: {
    obj: { first: { ref: '$.priorEvents' } },
    path: '$.timestampMillis',
  },
};

Я хочу быть уверенным, что ограничиваю значения path только теми путями внутри obj, которые возвращают значение типа number.

К сожалению, именно из-за двух перечисленных выше ограничений у нас возникают проблемы. По своей сути они утверждают, что некоторый неизвестный и произвольный тип B, подтип JSONObject, может быть получен из значения obj в месте создания конкретного Expr и в дальнейшем использоваться для получения набора допустимых path строк. . Эта зависимая формулировка общей типизации называется полиморфизмом ранга 2 (см. также этот полезный объяснитель от сообщества Swift).

Я пропущу здесь высокотехнические объяснения, так как есть другие, которые сделали это гораздо более справедливо, чем я когда-либо мог надеяться. Достаточно сказать, что система типов TypeScript не полностью поддерживает полиморфизм выше ранга 1 в определениях типов. Чтобы проиллюстрировать, что это значит, рассмотрим следующий практический пример:

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

function generateArrays<A, B, C>(
  arrayBuilder: (a: A) => A[],
  first: B,
  second: C,
): [B[], C[]] {
  return [arrayBuilder(first), arrayBuilder(second)];
}

Однако выполнение этого через компилятор TS выдаст предупреждение о том, что тип A в вашей arrayBuilder функции не соответствует типам B или C. К счастью, TypeScript (в отличие от многих других языков) предоставляет нам механизм, чтобы обойти это, а именно полиморфный тип функции:

function generateArrays<B, C>(
  arrayBuilder: <A>(a: A) => A[], // Conjuring a rank-2 generic type 
  first: B,
  second: C,
): [B[], C[]] {
  return [arrayBuilder(first), arrayBuilder(second)];
}

"Какая замечательная новость!" вы говорите: «Теперь все, что мне нужно сделать, это использовать это, чтобы помочь мне определить что-то эквивалентное для типа выражения get». К сожалению, это колдовство недоступно нам в строгом царстве типов. Попытка использовать infer B в предыдущей формулировке недостаточна для получения какой-либо полезной информации о форме введенных данных в месте создания экземпляра для конкретного экземпляра Expr.

Заключение: мечта о S-выражениях

К счастью, не все потеряно! Мы можем использовать то, что мы только что узнали о специальных функциях, для определения и использования дженериков для определения набора функций (@caTS ловко подметил это в своем комментарии), которые помогут нам построить этот DSL данных, сохраняя при этом все безопасности типов мы хотим оставаться честными при создании сложных наборов правил. С поправкой на небезопасное приведение типов это решение должно достичь всех заявленных нами целей с чистым и читаемым синтаксисом, использующим композицию функций (прищурьтесь, и это будет выглядеть как S-выражения):

/*
 * Working implementation of prior example
 */
const { get, ref, first } = new Expression<Context>();

const firstTimestamp: Expr<number, Context> = get(
  'timestampMillis',
  first(ref<Event[]>('$.priorEvents'))
);


/*
 * Encoding the DSL types and factory functions
 */
type Expr<
  Type extends Readonly<JSONData>,
  Context extends Readonly<JSONObject> = Readonly<Record<string, never>>
> = Type | Ref<Type, Context>;

// Utility namespace for all Expr factory functions
class Expression<C extends Readonly<JSONObject>> {
  get<
    O extends JSONObject,
    K extends JSONPath<O>,
    V extends JSONPathValueType<K, O>
  >(key: K, obj: Expr<O, C>): Expr<V, C> {
    return {
      '(get)': {
        '(obj)': obj,
        '(key)': key,
      },
    } as const as unknown as Expr<V, C>;
  }

  first<T extends JSONData>(list: Expr<T[], C>): Expr<T, C> {
    return {
      '(first)': list,
    } as const as unknown as Expr<T, C>;
  }

  ref<T extends JSONData>(ref: Ref<T, C>): Expr<T, C> {
    return ref;
  }
}