Реализация ALU в системе типов TypeScript

Вычислите число Фибоначчи, используя свой собственный тип

В этой статье мы приводим пример реализации ALU. Некоторые из операций, которые мы будем реализовывать, — это bitwise операции, такие как shifts и arithmetic операции, такие как addition и subtraction.

В конце мы увидим, как мы можем использовать большинство этих операций для реализации типа, который может вычислять число fibonacci.

Все конструкции, которые мы используем, являются типами TS, и все вычисления выполняются во время сборки. Наши типы не работают на JS. Мы полагаемся на систему типизации для выполнения вычислений.

Имея это в виду, давайте начнем.

Базовые типы

Нам нужен способ представить бит. Для этого мы начнем с представления двух состояний, которые может иметь бит (0 или 1).

Следующим шагом является определение бита как типа объединения двух состояний.

После этого мы можем перейти к определению байта. Для этого мы будем использовать кортежи.

type Byte = [Bit, Bit, Bit, Bit, Bit, Bit, Bit, Bit];

Это очень простое представление байта в системе типов TS, но его достаточно, чтобы начать работать над нашими операциями ALU.

Теперь мы можем определить несколько вспомогательных типов, которые мы можем использовать в дальнейшем.

type ZERO_BYTE = [Zero, Zero, Zero, Zero, Zero, Zero, Zero, Zero]
type ONE_BYTE  = [Zero, Zero, Zero, Zero, Zero, Zero, Zero, One]

Побитовые операции

Имея тип для бита, давайте посмотрим, как мы можем реализовать not, and, or и xor для битов.

Для этого будут усиленно использоваться ограниченные дженерики и условные типы.

Давайте немного рассмотрим детали реализации:

Битовое отрицание является самым простым. Мы ограничиваем T значением Bit, а затем проверяем, соответствует ли оно Zero. Если это так, мы определяем тип как One. В противном случае мы определяем тип как Zero.

Это означает, что теперь мы можем использовать BitNot вот так.

type OneNegated = BitNot<One>

И этот тип на самом деле будет Zero.

Мы делаем что-то похожее на BitAnd, но на этот раз нам нужно определить его как имеющий два общих типа: LHS и RHS. Мы используем условные типы, чтобы реализовать ветвление внутри системы типизации. Самый простой способ определить AND — проверить, расширяют ли они оба One и возвращают ли One в этом случае.

Это очень похоже на следующий код:

if (LSH === One) {
 if (RHS === One) {
   return One 
 } else {
   return Zero
 }
} else {
 return Zero
}

Из-за природы условных типов все ветви должны разрешаться в тип. По этой причине Zero появляется два раза. Это делает эту реализацию более подробной.

Мы делаем что-то подобное для BitOr .

BitXor немного более подробен, потому что нет способа сократить вычисление, поэтому мы должны рассмотреть все четыре возможности.

Побайтовые операции

Теперь у нас есть все, что нужно для реализации побайтовых операций.

С этого момента мы будем в значительной степени полагаться на вывод внутри типов условий. Нам нужен способ обойти кортеж и применить операции к каждому компоненту. Этого можно добиться, используя универсальный тип с условными типами и выводя только часть кортежа. Мы можем сделать что-то похожее на это:

type Walkable<T extends Byte> = T extends [infer U extends Bit, ...infer R extends Bit[]] ? U : []

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

Уточняем, что T extends Byte. Это означает, что это кортеж, состоящий из 8 Bit .

Следующим шагом является использование условия с extends для разделения кортежа и возможности ссылаться на заголовок кортежа. В этом контексте the head of the tuple означает первый Bit в Byte.

Мы можем сослаться на этот тип U в истинной ветви условного оператора. То же самое относится к R, который является типом кортежа со всеми остальными Bits.

Самые простые операции, которые мы можем реализовать сейчас, это ShiftLeft и ShiftRight.

Давайте внимательно посмотрим, что происходит с ShiftLeft. Мы выводим тип для самого левого Bit, а затем создаем новый тип, который его игнорирует, распаковывает R и добавляет Zero. Это по существу перемещает наименее старшие 7 битов влево.

Теперь мы можем использовать его так:

ShiftLeft<[Zero, Zero, Zero, One, Zero, Zero, Zero, One]>

или используя помощники, которые мы определили ранее:

ShiftLeft<ONE_BYTE>

и в итоге получится:

[Zero, Zero, One, Zero, Zero, Zero, One, Zero]

Что-то очень похожее делается для ShiftRight.

Байт-нет и Xor

Реализация not и xor для байтов использует аналогичную технику, но немного сложнее.

Причина, по которой not и xor более задействованы, связана с тем фактом, что после разделения head и tail байта нам нужно снова применить то же правило для tail . Проблема в том, что tail больше не Byte, а tuple только с 7 элементами. Выход из этого состоит в том, чтобы использовать другое определение type, которое допускает любое Bit[] .

Вот небольшая реализация для Not:

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

Мы можем использовать это так:

type Flipped = ByteNote<[Zero, One, One, Zero, One, One, One, Zero]>

И Flipped на самом деле будет:

[One, Zero, Zero, One, Zero, Zero, Zero, One]

XOR немного сложнее, так как нам нужно 2 Byte для создания операции. Но мы можем использовать те же понятия, что и раньше:

• ограниченные дженерики
• условные типы
• используя вывод и хвостовую рекурсию для обхода байта

Поскольку у нас есть два оператора и тот факт, что нам нужны условные типы для вывода head и tail из Byte, код труднее читать. Но используемые техники те же.

Одна вещь, которую следует отметить в реализации, это то, что мы останавливаем рекурсию, возвращая пустой массив []. Причина, по которой это работает, заключается в том, что если TS больше не может сделать вывод в предложениях extends, он выберет альтернативный маршрут. В этом случае, используя empty tuple в качестве типа.

Арифметическая операция

Теперь у нас есть все необходимое для реализации арифметических операций. Наша цель — иметь возможность использовать add и subtract байт.

Увеличение

Первое, что мы можем создать, это способность increment . Это означает, что мы хотим добавить 1 к Byte.

Это то, что вы много раз увидите при реализации этих операций:

T extends [...infer U extends Bit[], infer R extends Bit]

На этот раз нам нужно начать обработку Byte с хвоста, поэтому мы будем использовать ту же технику infer, но вместо захвата первого Bit мы будем захватывать последний, а затем использовать рекурсию для оставшихся битов.

Теперь нам нужно проверить, имеет ли R значение One или нет.

Почему это важно?

Если R это Zero, то мы меняем его на One, распаковываем U и готово. С другой стороны, если R равно One, то нам нужно изменить его на Zero, а затем continue добавить One к следующему Bit. Это часть рекурсии.

T extends [...infer U extends Bit[], infer R extends Bit] ? R extends One ? [...PartialAddOne<U>, Zero] : [...U, One] : []

Полная реализация такова:

Теперь мы можем использовать его так:

type ONE = AddOne<[Zero, Zero, Zero, Zero, Zero, Zero, Zero, Zero]>

Результат будет:

[Zero, Zero, Zero, Zero, Zero, Zero, Zero, One]

Обратите внимание, что число, которое мы получаем в итоге, является его представлением Byte, а не числом в том смысле, к которому мы привыкли.

Теперь мы можем сгенерировать положительное число (на самом деле мы можем сгенерировать любое представление Byte, так как то, положительно оно или нет, является семантической проблемой).

Все это действительные операции сейчас:

type ZERO = [Zero, Zero, Zero, Zero, Zero, Zero, Zero, Zero]
type ONE = AddOne<ZERO>
type TWO = AddOne<ONE>
type THREE = AddOne<AddOne
type FOUR = AddOne<THREE>

Добавить с переносом

Прежде чем мы сможем перейти к реализации полного add между 2 Bytes, нам нужно сохранить добавление carry между bits.

ALU обычно должны иметь флаг (CF), который можно использовать для этого. Но с этой точки зрения TS не имеет глобального состояния. Поэтому мы не можем просто хранить это где-то и использовать позже. Мы всегда должны быть в состоянии передать его.

Для этого создадим несколько типов, которые нам помогут:

type CarryFlag = Bit;
type BitWithCarry = {
    cf: CarryFlag
    value: Bit
}

Теперь мы можем обращаться к флагу BitWithCarry, когда это необходимо.

Точно так же, как мы сделали с Bit логическими операциями, чтобы мы могли использовать их на Byte позже, используя tail recursion , мы сделаем то же самое сейчас.

Нам нужно реализовать возможность складывать 2 бита вместе, хранить значение полученного Bit, а также carry value.

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

+------+------+------+------+------+
| Bit1 | Bit2 |  CF  | BitR |  CR  |
+------+------+------+------+------+
| 1    | 1    | 1    | 1    | 1    |
+------+------+------+------+------+
| 1    | 1    | 0    | 0    | 1    |
+------+------+------+------+------+
| 1    | 0    | 1    | 0    | 1    |
+------+------+------+------+------+
| 1    | 0    | 0    | 1    | 0    |
+------+------+------+------+------+
| 0    | 1    | 1    | 0    | 1    |
+------+------+------+------+------+
| 0    | 1    | 0    | 1    | 0    |
+------+------+------+------+------+
| 0    | 0    | 1    | 1    | 0    |
+------+------+------+------+------+
| 0    | 0    | 0    | 0    | 0    |
+------+------+------+------+------+

Теперь нам нужно реализовать это в TS, используя условные типы. Это сложная задача, но в итоге мы получим что-то похожее на это:

Имея это в руках, мы можем приступить к реализации операции add для bytes.

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

• вывести последний бит
• используйте AddBitsWithCarry в последних битах
• используйте вспомогательный тип для головных битов
• передать значение cf вспомогательному типу, так как это необходимо для остальных битов

У нас получается что-то похожее на это:

Несколько вещей, на которые стоит обратить внимание:

• Здесь мы использовали значение по умолчанию для общего параметра CH extends CarryFlag = Zero . В нашем случае это обязательно, но делает PartialAdd более гибким.
• При рекурсивной ссылке на тип мы дважды вызываем AddBitsWithCarry. Сначала получить value, а затем cf, даже если мы передаем одни и те же параметры. Опять же, потому что в системе типов TS нет глобального состояния.

Вычитание и умножение

Теперь, когда у нас есть основа, реализовать другие операции намного проще.

Для вычитания мы будем использовать дополнение до 2. Короче говоря, нам нужно инвертировать Byte, а затем add один к нему. Это очень легко сделать со всеми типами, которые у нас есть:

type Byte2Complement<T extends Byte> = AddOne<ByteNot<T>>

Вычитание теперь становится очень простым. Нам нужно вычислить дополнение до 2 для RHS, а затем добавить его к LHS:

type Subtract<LHS extends Byte, RHS extends Byte> = Add<LHS, Byte2Complement<RHS>>

Для удобства мы можем реализовать decrement:

type SubtractOne<LHS extends Byte> = Subtract<LHS, ONE_BYTE>

Теперь мы находимся в том месте, где мы можем заняться реализацией multiply. Нам нужно думать об умножении как о повторяющемся addition . Мы снова сделаем recursion и будем уменьшать LHS, пока оно не достигнет One.

LHS достижение One — это условие остановки этой рекурсии.

Нам также нужно учитывать случай, когда LHS на самом деле является Zero, поэтому для этого у нас есть специальное условие. В итоге получаем вот это:

type Mul<
  LHS extends Byte,
  RHS extends Byte,
  Result extends Byte = RHS
> = ONE_BYTE extends LHS
  ? Result
  : ZERO_BYTE extends LHS
  ? ZERO_BYTE
  : Mul<SubtractOne<LHS>, RHS, Add<Result, RHS>>;

Обратите внимание, что Result по умолчанию равно RHS. Это значит, что мы покрываем как случай, когда мы останавливаемся из-за рекурсии, так и когда LHS на самом деле One .

Теперь мы можем использовать его так:

Mul<ONE_BYTE, ZERO_BYTE>
Mul<[Zero, Zero, Zero, Zero, Zero, Zero, One, Zero], [Zero, Zero, Zero, Zero, Zero, Zero, One, Zero]>

Что во втором случае получится:

[Zero, Zero, Zero, Zero, Zero, One, Zero, Zero]

Реализация сравнения

Наше АЛУ было бы неполным без некоторых реализаций сравнения (на самом деле, мы могли бы также использовать некоторое деление, но мы сделаем это позже).

Примечание: все операции сравнения выполняются без знака.

EQ

Первое сравнение, которое мы можем реализовать, и самое простое, это EQ. Мы хотим увидеть, равны ли 2 Bytes. Мы можем легко сделать это, вычитая одно Byte из другого и проверяя, равно ли оно нулю. На нашем языке это можно записать так:

type EQ<LHS extends Byte, RHS extends Byte> = ZERO_BYTE extends ByteXOR<LHS, RHS> ? true : false

ЛТ (меньше чем)

Для реализации LT нам сначала понадобится небольшая помощь. Основная идея реализации этого состоит в том, чтобы пройтись по байтам слева направо (от наиболее значимого к наименее значимому) и выбрать другой первый бит.

Пока биты одинаковы, текущая операция undecided . Это означает, что нам нужно перейти к следующей паре.

Чтобы помочь с этим шагом, создадим вспомогательный тип, который будет возвращать true, false или undecided. Это очень поможет при наборе текста в дороге. А пока давайте посмотрим на это в действии:

type BitLTB<LHS extends Bit, RHS extends Bit> = Zero extends LHS
  ? One extends RHS
    ? true
    : "undecided"
  : One extends RHS
  ? "undecided"
  : false;

Теперь мы можем перейти к полной реализации. Идея та же, что и раньше:

• вывести голову и решку из обоих операндов
• используйте BitLTB, чтобы увидеть, можем ли мы разделить, если мы можем вернуть это значение
• если значение равно undecided, то перейти к следующему биту

Как и раньше, на реализацию немного сложно смотреть:

Еще раз, поскольку у нас нет глобального состояния, нам нужно вызывать BitLTB несколько раз. Вероятно, мы могли бы сделать это немного короче, если бы проверили boolean extends BitLTB .

Теперь мы можем использовать его так:

LT<ZERO_BYTE, ONE_BYTE> // will result in true
LT<ONE_BYTE, ZERO_BYTE> // will result in false

С реализованным LT остальные операции сравнения довольно легко реализовать:

LTE

Ничего больше, чем LTE или EQ

type LTE<LHS extends Byte, RHS extends Byte> = true extends LT<LHS, RHS> ? true : EQ<LHS, RHS>

GT

Это просто LT , но с переставленными операндами.

type GT<LHS extends Byte, RHS extends Byte> = LT<RHS, LHS>

ГТД

То же самое, но с помощью LTE.

type GTE<LHS extends Byte, RHS extends Byte> = LTE<RHS, LHS>

Разделение

Последняя операция, которую мы реализуем, — это деление с остатком.

Для этого мы будем использовать LT и Subtraction. Мы вернем тип, который имеет две величины:

• частное
• остаток

Нам нужно принять во внимание division by zero. Итак, мы будем использовать внутренний тип для последующих subtraction и использовать основной тип только для проверки zero. У нас получается что-то вроде этого:

type DivInternal<LHS extends Byte, RHS extends Byte, Q extends Byte = ZERO_BYTE> = true extends LT<LHS, RHS> ? {
    q: Q,
    r: LHS
} : DivInternal<Subtract<LHS, RHS>, RHS, AddOne<Q>>
type Div<LHS extends Byte, RHS extends Byte> = ZERO_BYTE extends RHS ? "Division by 0" : DivInternal<LHS, RHS>

Основной тип Div проверяет, является ли RHS Zero, и возвращает строку "Division by 0".

В случае, когда RHS не является 0, мы откладываем до DivInternal. Он вычитает RHS из LHS до тех пор, пока LHS не станет меньше RHS . Мы знаем, что это можно сделать, поскольку RHS не равно нулю. Теперь мы можем использовать его так:

Div<TWO, ONE> // we get {q: TWO, r: ZERO_BYTE}
Div<ONE, ZERO_BYTE> // we get "Division by 0"
Div<[Zero, Zero, Zero, Zero, One, Zero, One, Zero], TWO> // we get {q:[Zero, Zero, Zero, Zero, Zero, One, Zero, One], r: ZERO_BYTE}

Реализация Фибоначчи

Все это привело нас к моменту, когда мы можем реализовать числа fibonacci.

Идея этой реализации строится на тех же принципах, что и раньше:

• общие ограниченные типы
• условные типы

Мы определяем тип FIBONACCI с тремя общими аргументами.

• C текущий индекс в вычислении
• A текущий номер в последовательности
• B предыдущее число в последовательности

Затем мы просто decrement C вычисляем новый A как сумму A и B, заменяем новый B старым A. Нам также нужно иметь условие остановки. Это представлено, если C равно 1 или 2. Давайте посмотрим на это в действии:

Со всем этим мы можем вычислить fibonacci порядковых номеров, передав двоичное представление числа.

FIBONACCI<[Zero, Zero, Zero, Zero, Zero, One, One, One]>

Он вычислит 7-е значение в последовательности Фибоначчи, а именно:

[Zero, Zero, Zero, Zero, One, One, Zero, One] // 13

Заключительные мысли

Мы показали способ реализации простого АЛУ с использованием системы типов TypeScript.

Основные приемы, которые мы использовали:

• общие ограниченные типы
• условные дженерики для достижения ветвления
• условные дженерики, которые ссылаются на себя для создания циклов (рекурсия)

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

Надеюсь, вам понравилось это читать. Увидимся в следующей статье.