diff options
Diffstat (limited to 'js/baba-yaga/tests/turing_completeness.test.js')
| -rw-r--r-- | js/baba-yaga/tests/turing_completeness.test.js | 270 |
1 files changed, 270 insertions, 0 deletions
diff --git a/js/baba-yaga/tests/turing_completeness.test.js b/js/baba-yaga/tests/turing_completeness.test.js new file mode 100644 index 0000000..04daa03 --- /dev/null +++ b/js/baba-yaga/tests/turing_completeness.test.js @@ -0,0 +1,270 @@ +const assert = require('assert'); +const { createLexer } = require('../src/core/lexer'); +const { createParser } = require('../src/core/parser'); +const { createInterpreter } = require('../src/core/interpreter'); + +describe('Turing Completeness Tests', () => { + function interpret(code) { + const lexer = createLexer(code); + const tokens = lexer.allTokens(); + const parser = createParser(tokens); + const ast = parser.parse(); + const interpreter = createInterpreter(ast); + interpreter.interpret(); // Execute the code + return interpreter; // Return the interpreter instance to access scope + } + + describe('Church Numerals (Basic)', () => { + it('should implement basic Church numerals', () => { + const code = ` + // Church numerals: represent numbers as functions + // Zero: applies function 0 times + zero : f x -> x; + + // One: applies function 1 time + one : f x -> f x; + + // Test with increment function + inc : x -> x + 1; + + // Convert Church numeral to regular number + toNumber : n -> n inc 0; + + // Test conversions + result0 : toNumber zero; + result1 : toNumber one; + `; + + const interpreter = interpret(code); + + assert.strictEqual(interpreter.scope.get('result0').value, 0); + assert.strictEqual(interpreter.scope.get('result1').value, 1); + }); + }); + + describe('Lambda Calculus (Basic)', () => { + it('should implement basic lambda calculus operations', () => { + const code = ` + // Basic lambda calculus operations + + // Identity function + id : x -> x; + + // Constant function + const : x y -> x; + + // Function composition + compose : f g x -> f (g x); + + // Test identity + testId : id 42; + + // Test constant + testConst : const 10 20; + + // Test composition + testCompose : compose (x -> x + 1) (x -> x * 2) 5; + `; + + const interpreter = interpret(code); + + assert.strictEqual(interpreter.scope.get('testId').value, 42); + assert.strictEqual(interpreter.scope.get('testConst').value, 10); + assert.strictEqual(interpreter.scope.get('testCompose').value, 11); // (5*2)+1 = 11 + }); + }); + + describe('Universal Function (Basic)', () => { + it('should implement a basic universal function', () => { + const code = ` + // Simple universal function using function encoding + // This demonstrates that our language can simulate any computable function + + // Function registry + functionRegistry : { + inc: x -> x + 1; + double: x -> x * 2; + }; + + // Universal function that can simulate any registered function + universal : funcName input -> + when funcName is + "inc" then (functionRegistry.inc input) + "double" then (functionRegistry.double input) + _ then input; + + // Test the universal function + result1 : universal "inc" 5; + result2 : universal "double" 5; + `; + + const interpreter = interpret(code); + + assert.strictEqual(interpreter.scope.get('result1').value, 6); + assert.strictEqual(interpreter.scope.get('result2').value, 10); + }); + }); + + describe('Turing Machine Simulator (Basic)', () => { + it('should simulate a basic Turing machine', () => { + const code = ` + // Simple Turing machine that counts 1s on the tape + // States: "start", "halt" + + // Initialize Turing machine + initTM : { + tape: [1, 1, 0, 1], + head: 0, + state: "start" + }; + + // Transition function + transition : tm -> + when tm.state is + "start" then when (tm.head >= (length tm.tape)) is + true then { tape: tm.tape, head: tm.head, state: "halt" } + _ then { tape: tm.tape, head: tm.head + 1, state: "start" } + _ then tm; + + // Run Turing machine + runTM : tm -> + when tm.state is + "halt" then tm + _ then runTM (transition tm); + + // Test + result : runTM initTM; + `; + + const interpreter = interpret(code); + const result = interpreter.scope.get('result'); + + // Should reach halt state + assert.strictEqual(result.state, "halt"); + }); + }); + + describe('Recursive Functions (Turing Complete)', () => { + it('should demonstrate Turing completeness through recursion', () => { + const code = ` + // Ackermann function - a classic example of a computable but not primitive recursive function + // This demonstrates that our language can compute any computable function + + ackermann : m n -> + when m is + 0 then n + 1 + _ then + when n is + 0 then ackermann (m - 1) 1 + _ then ackermann (m - 1) (ackermann m (n - 1)); + + // Test with small values (larger values would cause stack overflow) + result1 : ackermann 0 5; + result2 : ackermann 1 3; + result3 : ackermann 2 2; + `; + + const interpreter = interpret(code); + + assert.strictEqual(interpreter.scope.get('result1').value, 6); + assert.strictEqual(interpreter.scope.get('result2').value, 5); + assert.strictEqual(interpreter.scope.get('result3').value, 7); + }); + }); + + describe('Higher-Order Functions (Turing Complete)', () => { + it('should demonstrate Turing completeness through higher-order functions', () => { + const code = ` + // Higher-order functions that can simulate any computable function + + // Test with factorial using fixed point + factorialHelper : f n -> + when n is + 0 then 1 + _ then n * (f (n - 1)); + + // Test with small values + testFactorial : factorialHelper (n -> 1) 0; + testFactorial2 : factorialHelper (n -> n * 1) 1; + `; + + const interpreter = interpret(code); + + assert.strictEqual(interpreter.scope.get('testFactorial').value, 1); + // The helper calls f(0) when n=1; with f = (n -> n * 1), this evaluates to 0 + assert.strictEqual(interpreter.scope.get('testFactorial2').value, 0); + }); + }); + + describe('SKI Combinator Calculus (Basic)', () => { + it('should implement basic SKI combinators', () => { + const code = ` + // SKI Combinator Calculus - basic version + + // K combinator: Kxy = x + K : x y -> x; + + // I combinator: Ix = x + I : x -> x; + + // Test I combinator + testI : I 42; + + // Test K combinator + testK : K 10 20; + + // Test composition + compose : f g x -> f (g x); + testCompose : compose (x -> x + 1) (x -> x * 2) 5; + `; + + const interpreter = interpret(code); + + assert.strictEqual(interpreter.scope.get('testI').value, 42); + assert.strictEqual(interpreter.scope.get('testK').value, 10); + assert.strictEqual(interpreter.scope.get('testCompose').value, 11); // (5*2)+1 = 11 + }); + }); + + describe('Mutual Recursion (Turing Complete)', () => { + it('should demonstrate Turing completeness through mutual recursion', () => { + const code = ` + // Mutual recursion example - isEven and isOdd + // This demonstrates that our language can handle complex recursive patterns + + isEven : n -> + when n is + 0 then true + 1 then false + _ then isOdd (n - 1); + + isOdd : n -> + when n is + 0 then false + 1 then true + _ then isEven (n - 1); + + // Test mutual recursion + result1 : isEven 0; + result2 : isEven 1; + result3 : isEven 2; + result4 : isEven 3; + result5 : isOdd 0; + result6 : isOdd 1; + result7 : isOdd 2; + result8 : isOdd 3; + `; + + const interpreter = interpret(code); + + assert.strictEqual(interpreter.scope.get('result1'), true); + assert.strictEqual(interpreter.scope.get('result2'), false); + assert.strictEqual(interpreter.scope.get('result3'), true); + assert.strictEqual(interpreter.scope.get('result4'), false); + assert.strictEqual(interpreter.scope.get('result5'), false); + assert.strictEqual(interpreter.scope.get('result6'), true); + assert.strictEqual(interpreter.scope.get('result7'), false); + assert.strictEqual(interpreter.scope.get('result8'), true); + }); + }); +}); \ No newline at end of file |