From 7cc3ef5fa1feec8087618c899441a11052f84c48 Mon Sep 17 00:00:00 2001 From: Elizabeth Hunt Date: Wed, 28 Feb 2024 14:59:28 -0500 Subject: builtin_match_signatures (#1) Co-authored-by: Lizzy Hunt Reviewed-on: https://git.simponic.xyz/simponic/cps-interpreter/pulls/1 Co-authored-by: Elizabeth Hunt Co-committed-by: Elizabeth Hunt --- src/interpreter/builtins.ts | 106 +++++++++++++++++++++++++++++++++++ src/interpreter/denotable.ts | 93 +++++++++++++++++++++++++++++++ src/interpreter/environment.ts | 83 +++++++++++++++++++++++++++ src/interpreter/index.ts | 4 +- src/interpreter/interpreter.ts | 124 +++++++++++++++++++++++++++++++++++++++++ 5 files changed, 409 insertions(+), 1 deletion(-) create mode 100644 src/interpreter/builtins.ts create mode 100644 src/interpreter/denotable.ts create mode 100644 src/interpreter/environment.ts create mode 100644 src/interpreter/interpreter.ts (limited to 'src/interpreter') 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 + | Array; + +export type DenotableFunctionSignature = { + arguments: Array; + return: DenotableType; +}; + +export type DenotableFunction = { + signatures: Array; + 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, + signatures: Array, +): 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; + 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 => { + 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); +}; -- cgit v1.2.3-70-g09d2