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

Я пытаюсь реализовать простой типизированный lisp в системе типов TypeScript, черпая вдохновение из JSON Logic, но с типами. Вот пример того, как это выглядит:

/**
 * Given a context object C, this type will allow you to construct
 * expressions that can reference that context and perform operations
 * on the data therein.
 *
 * Not shown below are the definitions for 
 *   JSONData: A simple typed representation of JSON non-object) in a 
 *   JSONPath: A union type of a terminal paths (i.e. 
 *             given JSON object.
 *   JSONPathValueType: The value type for a given path in a JSONObject
 */

type Expr<A extends JSONData, C extends JSONData> = A extends number
  ?
      | number
      | Ref<number, C>
      | ['+', ...Expr<number, C>[]]
      | ['first', Expr<number[], C>]
  : A extends JSONObject
  ? JSONObject | Ref<JSONObject, C>
  : A extends JSONArray<infer T>
  ?
      | T[]
      | Ref<T[], C>
      | ['map', Expr<JSONArray, C>, Expr<T, C>]
  : never;


type Ref<T, C extends JSONData> = {
  [P in JSONPath<C>]: JSONPathValueType<P, C> extends T ? `$.${P}` : never;
}[JSONPath<C>];

Учитывая вышеприведенное определение, все следующие допустимые типизированные выражения:

type Context = { foo: 1; bar: { baz: 2; bin: [5]; buz: [{ fiz: 3 }] } };
type SampleNumberExpr = Expr<number, Context>;

const two: SampleNumberExpr = ['+', 1, 1];
const three: SampleNumberExpr = ['+', '$.foo', '$.bar.baz'];
const four: SampleNumberExpr = ['first', [4, 5, 6]];
const five: SampleNumberExpr = ['+', 1, ['first', [4, 5, 6]]];
const six: SampleNumberExpr = ['+', '$.foo', ['first', '$.bar.bin']];

Однако у меня начинаются проблемы, когда я пытаюсь реализовать и использовать функциональность map. В идеале я мог бы использовать ту же нотацию Ref $.* в контексте выражения для доступа к каждому элементу в предоставленном списке:

const doesNotWork: SampleNumberExpr = 
  ['first', ['map', '$.bar.buz', ['+', '$.item.fiz', 1]]]

Тем не менее, каждая моя попытка реализовать эту функциональность наталкивается на либо ошибки типа, либо ошибка компилятора Type instantiation is excessively deep and possibly infinite..

В частности, пытаясь создать новый контекст для функциональности map, чтобы иметь возможность Ref, где ключ $.item соответствует типу каждого элемента введенного массива Expr, где Я застрял. Очевидно, что все это выходит за рамки того, для чего на самом деле предназначена система типов TS, но у меня есть интуиция, что это должно быть возможно - я был бы рад любой помощи, чтобы выяснить, так ли это на самом деле.

РЕДАКТИРОВАТЬ Для тех, кто хочет поиграть с этим, вот полный пример игровой площадки

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

jcalz 19.11.2022 21:59

Без чего-то более податливого это выглядит так, как будто вы передаете C как есть в тех местах, где оно должно быть преобразовано во что-то, что детализирует и отслеживает, где вы находитесь в дереве. Смотрите ссылку на игровую площадку. Посмотрите, как я провел рефакторинг, чтобы дать частям ваших вещей имена, так что quickinfo на самом деле дает вам относительно скромные объединения именованных типов вместо резкого взрыва имен. Я достиг места, где у вас есть Expr<number, Context> и ожидание совпадения "$.item.fiz", и, конечно же, это не так, поскольку Context ничего не знает о $.item.

jcalz 19.11.2022 22:25

Но что касается того, как это исправить, ну, я не склонен углубляться в это. Это слишком сложно. Если вы сократите это до игрушечного примера с соответствующей проблемой, с попыткой сделать детализацию, которая отсутствует здесь, может быть, я мог бы взглянуть еще раз? Или, может быть, кто-то еще придет. В любом случае, если вы редактируете и хотите сообщить мне об этом, упомяните @jcalz в комментарии. Удачи!

jcalz 19.11.2022 22:28

Мне кажется, было бы намного проще, если бы вместо типа была функция, т.е. lisp<Context>(...).

vera. 28.11.2022 16:03

Есть ли конкретная причина, по которой вы используете кортежи, содержащие операцию в первой позиции, а не записи?

WolverinDEV 28.11.2022 19:16

@WolverinDEV в основном просто потому, что они больше похожи на S-выражения Lisp. На самом деле я также пробовал типы Record, но они ведут себя примерно так же.

wvandaal 28.11.2022 19:23

Хорошо, я только что спросил, так как я играю с типами записей, поскольку они более удобочитаемы для меня.

WolverinDEV 28.11.2022 19:33

Спасибо @caTS за вдохновение решить эту проблему с помощью функций

wvandaal 28.11.2022 21:55

Я все еще жду, когда кто-то, надеюсь, сделает это без функций. Я также чувствую, что это возможно, но просто вне досягаемости руки. Bounty перейдет к вашему самостоятельному ответу, если никто другой не ответит.

vera. 01.12.2022 21:32
Шаблоны Angular PrimeNg
Шаблоны Angular PrimeNg
Как привнести проверку типов в наши шаблоны Angular, использующие компоненты библиотеки PrimeNg, и настроить их отображение с помощью встроенной...
Освоение принципов SOLID в JavaScript: Пошаговое руководство
Освоение принципов SOLID в JavaScript: Пошаговое руководство
Принцип единой ответственности (SRP): класс должен иметь только одну причину для изменения. Другими словами, у него должна быть только одна...
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Создание собственной системы электронной коммерции на базе Keystone.js - настройка среды и базовые модели
Создание собственной системы электронной коммерции на базе Keystone.js - настройка среды и базовые модели
Прошлая статья была первой из цикла статей о создании системы электронной коммерции с использованием Keystone.js, и она была посвящена главным образом...
2
9
121
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Отвечая на этот вопрос и предоставляя больше контекста в надежде, что это поможет людям, которые также боролись с проблемами такого типа. Я постараюсь также ответить на критические замечания, высказанные @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;
  }
}


Реализация собственного диалекта Лиспа должна быть значительно проще и надежнее, чем держать под прицелом компилятор TypeScript, но, тем не менее, это отличный мысленный эксперимент.

vera. 28.11.2022 22:00

@caTS Вы будете удивлены полезностью такого маленького языка. Чтобы было ясно, это всего лишь Lisp-esque, в самом языке нет поддержки типизированного метапрограммирования внутри самого языка, что было бы реальной предпосылкой для того, чтобы его считали типизированным Lisp в традиционном смысле. Тем не менее, для варианта использования, который я описал в своем ответе, выражения и контексты могут быть довольно сложными, особенно по мере того, как наша система развивается с течением времени. Преимущества того, что команды могут полагаться на компилятор, чтобы убедиться, что генерация выражений безопасна, стоят затраченных усилий.

wvandaal 29.11.2022 00:02

Другие вопросы по теме