builtin_match_signatures (#1)

Co-authored-by: Lizzy Hunt <lizzy.hunt@usu.edu>
Reviewed-on: https://git.simponic.xyz/simponic/cps-interpreter/pulls/1
Co-authored-by: Elizabeth Hunt <elizabeth.hunt@simponic.xyz>
Co-committed-by: Elizabeth Hunt <elizabeth.hunt@simponic.xyz>

5 files changed, 409 insertions, 1 deletions

diff --git a/src/interpreter/builtins.ts b/src/interpreter/builtins.ts
new file mode 100644
index 0000000..200131f
--- /dev/null
+++ b/src/interpreter/builtins.ts
@@ -0,0 +1,106 @@
+import {
+  type DenotableFunctionSignature,
+  Environment,
+  type Denotable,
+} from '.';
+
+const addUnaryIntegerOperationsTo = (env: Environment) => {
+  const unaryIntegerOperationSignatures: DenotableFunctionSignature[] = [
+    {
+      arguments: ['int'],
+      return: 'int',
+    },
+  ];
+
+  for (const { name, fn } of [
+    { name: '~', fn: (a: number) => ~a },
+    { name: '!', fn: (a: number) => (!a ? 1 : 0) },
+  ]) {
+    env.set(name, {
+      type: 'function',
+      value: {
+        signatures: unaryIntegerOperationSignatures,
+        body: ({ value }: Denotable) => fn(value as number),
+      },
+    });
+  }
+
+  return env;
+};
+
+const addBinaryIntegerOperationsTo = (env: Environment) => {
+  const binaryIntegerOperationSignatures: DenotableFunctionSignature[] = [
+    {
+      arguments: ['int', 'int'],
+      return: 'int',
+    },
+  ];
+
+  for (const { name, fn } of [
+    { name: '%', fn: (a: number, b: number) => a % b },
+    { name: '>>', fn: (a: number, b: number) => a >> b },
+    { name: '<<', fn: (a: number, b: number) => a << b },
+    { name: '|', fn: (a: number, b: number) => a | b },
+    { name: '^', fn: (a: number, b: number) => a ^ b },
+    { name: '&&', fn: (a: number, b: number) => (a && b ? 1 : 0) },
+    { name: '<=', fn: (a: number, b: number) => (a <= b ? 1 : 0) },
+    { name: '<', fn: (a: number, b: number) => (a < b ? 1 : 0) },
+    { name: '>', fn: (a: number, b: number) => (a > b ? 1 : 0) },
+    { name: '>=', fn: (a: number, b: number) => (a >= b ? 1 : 0) },
+    { name: '||', fn: (a: number, b: number) => (a || b ? 1 : 0) },
+  ]) {
+    env.set(name, {
+      type: 'function',
+      value: {
+        signatures: binaryIntegerOperationSignatures,
+        body: ({ value: a }: Denotable, { value: b }: Denotable) =>
+          fn(a as number, b as number),
+      },
+    });
+  }
+
+  return env;
+};
+
+const addBinaryArithmeticOperationsTo = (env: Environment) => {
+  const binaryArithmeticSignatures: DenotableFunctionSignature[] = [
+    {
+      arguments: ['int', 'int'],
+      return: 'int',
+    },
+    {
+      arguments: [
+        ['int', 'real'],
+        ['int', 'real'],
+      ],
+      return: 'real',
+    },
+  ];
+
+  for (const { name, fn } of [
+    { name: '+', fn: (a: number, b: number) => a + b },
+    { name: '-', fn: (a: number, b: number) => a - b },
+    { name: '*', fn: (a: number, b: number) => a * b },
+    { name: '/', fn: (a: number, b: number) => a / b },
+    { name: '**', fn: (a: number, b: number) => a ** b },
+  ]) {
+    env.set(name, {
+      type: 'function',
+      value: {
+        signatures: binaryArithmeticSignatures,
+        body: ({ value: a }: Denotable, { value: b }: Denotable) =>
+          fn(a as number, b as number),
+      },
+    });
+  }
+
+  return env;
+};
+
+export const putBuiltinsOnEnvironemtn = (env: Environment) => {
+  return [
+    addBinaryArithmeticOperationsTo,
+    addBinaryIntegerOperationsTo,
+    addUnaryIntegerOperationsTo,
+  ].reduce((acc, builtinsAdder) => builtinsAdder(acc), env);
+};
diff --git a/src/interpreter/denotable.ts b/src/interpreter/denotable.ts
new file mode 100644
index 0000000..65aee86
--- /dev/null
+++ b/src/interpreter/denotable.ts
@@ -0,0 +1,93 @@
+import type { Identifier } from '@/parser';
+import { testingLogger } from '@t/logger';
+
+export type UnionDenotableType =
+  | Array<DenotableType | DenotableFunctionSignature>
+  | DenotableType
+  | DenotableFunctionSignature
+  | Array<UnionDenotableType>;
+
+export type DenotableFunctionSignature = {
+  arguments: Array<UnionDenotableType>;
+  return: DenotableType;
+};
+
+export type DenotableFunction = {
+  signatures: Array<DenotableFunctionSignature>;
+  body: Function;
+};
+
+export type DenotableType =
+  | 'null'
+  | 'int'
+  | 'real'
+  | 'string'
+  | 'bytearray'
+  | 'function'
+  | 'reference';
+
+export type DenotableValue =
+  | null
+  | number
+  | string
+  | Uint8Array
+  | DenotableFunction
+  | Identifier;
+
+export type Denotable = {
+  type: DenotableType;
+  value: DenotableValue;
+};
+
+export const denotableTypesEquivalent = (
+  a: UnionDenotableType,
+  b: UnionDenotableType,
+): boolean => {
+  if (typeof a !== typeof b) return false;
+
+  if (Array.isArray(a) && Array.isArray(b)) {
+    if (a.length !== b.length) return false;
+    for (let i = 0; i < a.length; i++) {
+      if (!denotableTypesEquivalent(a[i], b[i])) return false;
+    }
+    return true;
+  }
+
+  if (
+    typeof a === 'object' &&
+    typeof b === 'object' &&
+    'arguments' in a &&
+    'arguments' in b
+  ) {
+    if (a.arguments.length !== b.arguments.length) return false;
+    if (!denotableTypesEquivalent(a.return, b.return)) return false;
+    for (let i = 0; i < a.arguments.length; i++) {
+      if (!denotableTypesEquivalent(a.arguments[i], b.arguments[i])) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  if (a === b) return true;
+
+  return false;
+};
+
+export const matchSignature = (
+  args: Array<UnionDenotableType>,
+  signatures: Array<DenotableFunctionSignature>,
+): DenotableFunctionSignature | undefined => {
+  return signatures.find(signature => {
+    if (args.length !== signature.arguments.length) return false;
+
+    return args.every((arg, i) => {
+      const argSignature = signature.arguments[i];
+      if (Array.isArray(argSignature)) {
+        return argSignature.some(a => denotableTypesEquivalent(a, arg));
+      }
+
+      return denotableTypesEquivalent(arg, signature.arguments[i]);
+    });
+  });
+};
diff --git a/src/interpreter/environment.ts b/src/interpreter/environment.ts
new file mode 100644
index 0000000..1c451aa
--- /dev/null
+++ b/src/interpreter/environment.ts
@@ -0,0 +1,83 @@
+import { UnknownSymbolError, InvalidType, type TracingLogger } from '@/utils';
+import { matchSignature, type Denotable } from '.';
+
+export class Environment {
+  private scope: Map<string, Denotable>;
+  private parent: Environment | null;
+  private logger: TracingLogger;
+
+  constructor(logger: TracingLogger, parent: Environment | null = null) {
+    this.logger = logger;
+    this.parent = parent;
+    this.scope = new Map();
+  }
+
+  public set(name: string, value: Denotable) {
+    this.scope.set(name, value);
+  }
+
+  public get(name: string): Denotable {
+    if (this.scope.has(name)) {
+      this.logger.debug(`Found Name=(${name}) in current scope`);
+      return this.scope.get(name)!;
+    }
+
+    if (this.parent) {
+      this.logger.debug(`Looking for Name=(${name}) in parent scope`);
+      return this.parent.get(name);
+    }
+
+    throw new UnknownSymbolError(`Undefined variable: ${name}`);
+  }
+
+  public has(name: string): boolean {
+    if (this.scope.has(name)) {
+      this.logger.debug(`Found Name=(${name}) in current scope`);
+      return true;
+    }
+
+    if (this.parent) {
+      this.logger.debug(`Found Name=(${name}) in current scope`);
+      return this.parent.has(name);
+    }
+
+    this.logger.debug(`Name=(${name}) not found in any scope`);
+    return false;
+  }
+
+  public createChild(): Environment {
+    return new Environment(this.logger.createChild('Env'), this);
+  }
+
+  public apply(name: string, args: Denotable[]): Denotable {
+    const fn = this.get(name);
+    if (typeof fn.value !== 'object' || !fn.value || !('body' in fn.value)) {
+      throw new InvalidType(name + ' is not a valid function');
+    }
+
+    const argTypes = args.map(arg => {
+      const { type, value } = arg;
+      const isFunction =
+        type === 'function' &&
+        typeof value === 'object' &&
+        value &&
+        'signatures' in value;
+      if (isFunction) {
+        return value.signatures;
+      }
+      return type;
+    });
+
+    const appliedSignature = matchSignature(argTypes, fn.value.signatures);
+    if (!appliedSignature) {
+      throw new InvalidType(`No matching signature for ${name}`);
+    }
+
+    this.logger.debug(
+      `Applying Function=(${name}) with Args=(${JSON.stringify(args)}) with Signature=(${JSON.stringify(appliedSignature)})`,
+    );
+
+    const value = fn.value.body.apply(this, args);
+    return { type: appliedSignature.return, value };
+  }
+}
diff --git a/src/interpreter/index.ts b/src/interpreter/index.ts
index 4178c19..1c7c9db 100644
--- a/src/interpreter/index.ts
+++ b/src/interpreter/index.ts
@@ -1 +1,3 @@
-export const evaluate = async (ast: Program) => {};
+export * from './denotable';
+export * from './environment';
+export * from './interpreter';
diff --git a/src/interpreter/interpreter.ts b/src/interpreter/interpreter.ts
new file mode 100644
index 0000000..ebd605c
--- /dev/null
+++ b/src/interpreter/interpreter.ts
@@ -0,0 +1,124 @@
+import {
+  type ContinuationExpression,
+  type PrimitiveOperationExpression,
+  type Program,
+  type Value,
+} from '@/parser';
+import { Environment, type Denotable } from '.';
+import {
+  BadArgumentError,
+  InvalidStateError,
+  NotImplementedError,
+  type TracingLogger,
+} from '@/utils';
+import { putBuiltinsOnEnvironemtn } from './builtins';
+
+const evaluateValue = (
+  value: Value,
+  env: Environment,
+  logger: TracingLogger,
+): Denotable => {
+  if (typeof value === 'string') {
+    return { type: 'string', value };
+  }
+
+  if ('real' in value) {
+    return { type: 'real', value: value.real };
+  }
+  if ('int' in value) {
+    return { type: 'int', value: value.int };
+  }
+  if ('name' in value) {
+    logger.debug(`Evaluating variable: ${value.name}`);
+    return env.get(value.name);
+  }
+
+  throw new InvalidStateError(`Invalid value: ${value}`);
+};
+
+const evaluatePrimitiveOperation = (
+  { primitiveOperation }: PrimitiveOperationExpression,
+  env: Environment,
+  logger: TracingLogger,
+) => {
+  const { opr, operands, resultBindings, continuations } = primitiveOperation;
+  if (operands.length !== 2) {
+    throw new BadArgumentError('Primitive operations must have 2 operands');
+  }
+
+  const operandValues = operands.map(operand =>
+    evaluateValue(operand, env, logger.createChild('evaluteValue')),
+  );
+
+  const result = env.apply(opr, operandValues);
+  const continuationEnvironment = env.createChild();
+  for (const { name } of resultBindings) {
+    continuationEnvironment.set(name, result);
+  }
+
+  // return the result of the last continuation
+  return continuations.reduce((_, continuation, i) => {
+    const childLogger = logger.createChild(`continuation[${i}]`);
+    return evaluteContinuationExpression(
+      continuation,
+      continuationEnvironment,
+      childLogger,
+    );
+  }, result);
+};
+
+const evaluteContinuationExpression = (
+  expr: ContinuationExpression,
+  env: Environment,
+  logger: TracingLogger,
+): Denotable => {
+  if ('primitiveOperation' in expr) {
+    logger.debug('Evaluating primitive operation');
+    return evaluatePrimitiveOperation(
+      expr,
+      env,
+      logger.createChild('evaluatePrimitiveOperation'),
+    );
+  }
+
+  if ('record' in expr) {
+    throw new NotImplementedError('Continuation records are not supported yet');
+  }
+  if ('select' in expr) {
+    throw new NotImplementedError('Continuation select is not supported yet');
+  }
+  if ('offset' in expr) {
+    throw new NotImplementedError('Continuation offset is not supported yet');
+  }
+  if ('application' in expr) {
+    throw new NotImplementedError(
+      'Continuation application is not supported yet',
+    );
+  }
+  if ('switch' in expr) {
+    throw new NotImplementedError('Continuation switch is not supported yet');
+  }
+  if ('fix' in expr) {
+    throw new NotImplementedError('Continuation fix is not supported yet');
+  }
+
+  throw new InvalidStateError(`Invalid continuation expression: ${expr}`);
+};
+
+export const evaluate = async (
+  ast: Program,
+  logger: TracingLogger,
+): Promise<Denotable> => {
+  const globalEnvironment = putBuiltinsOnEnvironemtn(
+    new Environment(logger.createChild('RootEnv')),
+  );
+
+  return ast.reduce((_, continuation, i) => {
+    const exprLogger = logger.createChild(`statement[${i}]`);
+    return evaluteContinuationExpression(
+      continuation as ContinuationExpression,
+      globalEnvironment,
+      exprLogger,
+    );
+  }, null);
+};