simple-stack-machine-in-type-system.ts

// Playground link: https://www.typescriptlang.org/play?#code/PTAEHEEsGcBdQG4FMBO1IHsB2AuUALWWAB2hxAHMZYA6K2fAVwCMaBjDAW2ACUelkaVMABMAZgCMbMQDYAHAFZFAQwAmCkWwAMSACwB2VXJHN98hQu1IFAWABQ92AE9iSUAFEAHkjYAeAMJcnMpYqtAANKAAyrDKsG4AvKAA3qBwymwA1ngA2gC6kQA2GGzKhWQpAL6glQB8oAn2oKCBnMGh0KBInvEdoDmQWABmqC1BIaqRNNODIyig-HB5TaAA-B7efouwkV4+re2qvjFxSJEHE7W1K3gn8QDc9o4ubgDygiiQqki+r8wAVpEAHLKThnUAANTKjCQ9SSILBXR6SD6cE+WAoaxSKxyAGlQINQAAKTJIJwYIagP7-ACUoAAPqAEUg8nh8d1emEmaC3OsoYUYaA8NS8aAAGTE0nkynUmnLOzVPBYASoR4OOzOVwQJCwfkw34A4E8uHcxEclFcqUUqkArEi5l5IWgZWCNXPLUAFUYxEKPyBSM5nSwjE4zFQkR4AYtnRCTnyDX6eRNPByAHJfRiGKnHea+v71pG8F6fX7IjlY1Npjwk267IN4ighhk3ECkBQgSGwyhfABBZidXNc4Oh1D1VLKihxSDIPB9zqVd0ttu+D0mj1RvNtjsj7uzUZz+rrOdO9eDoOd0brVvti-d1dOl2qp4al6gOcrtcbrnX7dd3x7+Y53vI9+3XIsv3PHcsTA50VRQWtNTcHtiB9JwokgCgsBXSIAAUMAHZE+mYDAMF9EITTwgjA1AWAUEFdYYOvD8ENfcAdXQzCPwTU9CO-Ldb18Ycu0PUAm3KNw8FomEWK1ABZRhCg4rCe0iAAhE0chU0BVJzXjOhyKTwUMx1GRyMToHBcyWSxQynSsmS3CiENf1QXsIOdW81PcoTRwTHJphoYtfV7WpK0C71gvUvI0wzCgs0dCUfPg59EOiFggp+Ht3NjfIvLPUAcqTBNVPc8ssCcMKAIWJA4B0rEiRWLL8rKirQACqrth7R11ic5gMt8TqIxq2B1KdJjVJilE4vwbNrjsOlZ0mzMZryBy0uYFzuyavSPJ3PKdqSk1ev6-qe1C0B+vU2o1vkwpTuy8rcu0h64wKbTGEpfLCr8oqkhK5qKzamZhlGbY6vWW7TqG2qywC1SPrCrr6jweGhiW6bszWpzOF7NS4Ua7zb3q-6DqJnrnIErTRpR9yfwEqq51G8mNspyJGeR2DBAWgn8rpnd-xBwD+zO4nCag5nNt8VS2eFjmSeovm-wZ-smaZfj+exyW5y09mOcfFBubsZp9axlhce0o6Q3N8arhuhTzdGpJkNQpTfBWSGIp+U7+xC87vegKWrlC92FNdtjYFds7InD12rvsa6UtfPY2AuUJjlieJznGUIjoztx8tSdIslydrBeiWIsje4pSnKPAqoAGRKMp53qlZU9UdzUkQvBU3ryAGzKVNIgQaEkDrsu9Tcap1kLivsn6AKTiySJJ6rpva9ARua5bnA2+zjuC5ol4e6iHUh+dHlx7mU0p-qpfMlK0vr-vyIqtXrFZ4yeeX9Aavm+FD4Xwfhb2bkaMEK9R71EVJzVAhtmjt07kfVwPdw7nywJfAkZdmQ1A-mkOeJdpg-3DpPXwIDyhgNhGvbeeAyE7z3m0CYiDu6gFTD2VQqhUw4PWESe+j9gbPznq-MuWkqrgxSHgr+BCaA-2xg7WoVD-6b3XjvGBBshT0MOEw4+LDeqcOnsSXhzUn6jB-gzIR18xGf2LgvQhgj1pyIURvWhOClRwTgWMBhoQtHIJYbdPRd8558JoFVUxwjzGjEsRI6x-lbFf0iLdBxRRlE0OUS41R7j9b2AWqotaiwFLwCSMnXwOQVhd20amVBkR0Fgh7p4PR4RSlILHiwypF8aksKcPUxpzDUy6JqA0o24iemn1gGgjBqZVCQCGEMLpgyyk+IqWfKp4zJnTNmc0eZzTFmjOWe0iZUyZn9O6eUvxRy5lNJPkstpWyUA1XyXo+wb1kgrD-hvZ5gzmieDwBILQAzmjNCcHgEQWgViVD+VE+e+R7B1DVEAA

type Exec<Commands, State = { stack: [], locals: {} }> =
  Commands extends [infer Command, ...infer Rest]
  ? Exec<Rest, ExecCommand<State, Command>>
  : State;

type Override<Obj, Name, Value> = Name extends string ? {
  [K in (keyof Obj) | Name]: K extends Name ? Value : Obj[K & (keyof Obj)]
} : never;

type GetValue<Obj, Name> = Name extends keyof Obj ? Obj[Name] : never;

type Tuple<N extends number, R extends any[] = []> = R['length'] extends N ? R : Tuple<N, [any, ...R]>;

interface NegNumber<Abs extends number> { negative: Abs }
type Neg<T> = T extends NegNumber<infer Abs> ? Abs : T extends number ? NegNumber<T> : never;

type Abs<T> = T extends NegNumber<infer AbsT> ? AbsT : T extends number ? T : never;

type ApplySign<T, Pos extends boolean> = Pos extends true ? T : Neg<T>;

type GetSign<T> = T extends NegNumber<number> ? false : true;

type MulSign<A, B> = [A, B] extends [true, true] | [false, false] ? true : false;

type SumNumber<A extends number, B extends number> = [...Tuple<A>, ...Tuple<B>]['length'] & number;

type SubTuple<A extends any[], B extends any[]> = B extends [any, ...infer RestB] ? (
  A extends [any, ...infer RestA] ? SubTuple<RestA, RestB> : Neg<B['length']>
) : A['length'];

type SubNumber<A extends number, B extends number> = SubTuple<Tuple<A>, Tuple<B>>;

type MulTuple<A extends any[], B extends any[], Buf extends any[] = []> = B extends [any, ...infer RestB] ? MulTuple<A, RestB, [...Buf, ...A]> : Buf['length'];

type Sum<A, B> =
  A extends number ? (B extends number ? SumNumber<A, B> : B extends NegNumber<infer AbsB> ? SubNumber<A, AbsB> : never) :
  A extends NegNumber<infer AbsA> ? (B extends number ? SubNumber<B, AbsA> : B extends NegNumber<infer AbsB> ? NegNumber<SumNumber<AbsA, AbsB>> : never) :
  never;

type Sub<A, B> = Sum<A, Neg<B>>;

type Mul<A, B> = ApplySign<
  MulTuple<Tuple<Abs<A>>, Tuple<Abs<B>>>,
  MulSign<GetSign<A>, GetSign<B>>
>;

type ExecCommand<State, Command> = State extends { stack: [...infer Stack], locals: infer Locals } ? (
  Command extends { type: 'Literal', value: infer Value } ? { stack: [...Stack, Value], locals: Locals } :
  Command extends { type: 'Set', name: infer Name } ? (Stack extends [...infer Stack, infer Value] ? { stack: Stack, locals: Override<Locals, Name, Value> } : never) :
  Command extends { type: 'Get', name: infer Name } ? { stack: [...Stack, GetValue<Locals, Name>], locals: Locals } :
  Command extends { type: 'Add' } ? (Stack extends [...infer Stack, infer A, infer B] ? { stack: [...Stack, Sum<A, B>], locals: Locals } : never) :
  Command extends { type: 'Sub' } ? (Stack extends [...infer Stack, infer A, infer B] ? { stack: [...Stack, Sub<A, B>], locals: Locals } : never) :
  Command extends { type: 'Mul' } ? (Stack extends [...infer Stack, infer A, infer B] ? { stack: [...Stack, Mul<A, B>], locals: Locals } : never) :
  never
) : never;

type Result = Exec<[
  { type: 'Get', name: 'x' },
  { type: 'Get', name: 'y' },
  { type: 'Sub' },
  { type: 'Set', name: 'diff' },
  { type: 'Get', name: 'diff' },
  { type: 'Get', name: 'diff' },
  { type: 'Mul' },
  { type: 'Set', name: 'result' }
], {
  locals: {
    x: 10,
    y: 20
  },
  stack: []
}>;