Stack-Based Evaluation in JSL¶

Overview¶

JSL now supports two evaluation strategies: 1. Recursive evaluation - Traditional tree-walking interpreter (simple but limited) 2. Stack-based evaluation - Compiles to postfix bytecode for efficient execution

Why Stack-Based Evaluation?¶

Limitations of Recursive Evaluation¶

The recursive evaluator in jsl/core.py has several fundamental limitations:

No true resumption: When resources are exhausted mid-recursion, we can only capture the top-level expression. The computation restarts from the beginning, making no progress.
Stack overflow risk: Deep recursion can exceed Python's call stack limit.
Difficult optimization: Each node visit involves function calls and environment lookups.
Imprecise resource tracking: Hard to track exact costs mid-recursion.

Advantages of Stack-Based Evaluation¶

Perfect resumption: Save the stack and program counter, resume exactly where you left off.
No recursion limits: Uses a data stack, not the call stack.
Optimization opportunities: Postfix bytecode can be optimized, cached, and analyzed.
Network-friendly: Postfix arrays are more compact than S-expressions for transmission.
Clear execution model: Each instruction is atomic and predictable.
JSON all the way down: Even the paused execution state (stack, PC, environment) is pure JSON - no binary formats, no special serialization.

Architecture¶

Compilation Pipeline¶

S-Expression → Compiler → Postfix → Stack Evaluator → Result
['+', 2, 3]  →          → [2,3,'+'] →               → 5

Key Components¶

jsl/compiler.py: Converts S-expressions to postfix notation
jsl/stack_evaluator.py: Executes postfix using a value stack
jsl/eval_modes.py: Unified interface for both evaluators

N-Arity Handling¶

For operators with variable arity (0 ≤ n < ∞), we encode arity explicitly:

['+']           → [('+', 0)]      # 0-arity: sum() = 0
['+', 5]        → [5, ('+', 1)]    # 1-arity: 5
['+', 1, 2, 3]  → [1, 2, 3, ('+', 3)]  # n-arity: 1+2+3

Usage Examples¶

Basic Evaluation¶

from jsl.compiler import compile_to_postfix
from jsl.stack_evaluator import StackEvaluator

# Compile S-expression to postfix
expr = ['*', ['+', 2, 3], 4]
postfix = compile_to_postfix(expr)  # [2, 3, '+', 4, '*']

# Evaluate
evaluator = StackEvaluator()
result = evaluator.eval(postfix)  # 20

Resumable Evaluation¶

# Execute with limited steps (simulating resource limits)
expr = ['*', ['+', 10, 20], ['-', 100, 50]]
postfix = compile_to_postfix(expr)

evaluator = StackEvaluator()
result, state = evaluator.eval_partial(postfix, max_steps=2)
# result = None, state contains stack and pc

# Resume later
result, state = evaluator.eval_partial(postfix, max_steps=10, state=state)
# result = 1500, state = None (complete)

Unified Interface¶

from jsl.eval_modes import JSLEvaluator, EvalMode

# Use recursive evaluator (default)
eval1 = JSLEvaluator(mode=EvalMode.RECURSIVE)
result = eval1.eval(['+', 2, 3])  # 5

# Use stack evaluator
eval2 = JSLEvaluator(mode=EvalMode.STACK)
result = eval2.eval(['+', 2, 3])  # 5

# Both produce identical results!

Postfix as Primary Representation¶

In distributed/networked scenarios, postfix can become the primary code representation:

# Instead of sharing S-expressions:
send_over_network(['+', [1, 2], [3, 4]])  # Nested structure

# Share postfix directly:
send_over_network([1, 2, '+', 3, 4, '+', '+'])  # Flat array

Benefits: - More compact (flat array vs nested) - No parsing ambiguity - Direct execution without compilation - Trivial serialization

Resumable Execution State¶

The stack evaluator can pause and resume execution at any point. The paused state is pure JSON:

{
  "stack": [10, 20],
  "pc": 2,
  "instructions": [10, 20, 2, "+", 5, 2, "*"],
  "resource_checkpoint": {
    "gas_used": 150,
    "steps_taken": 2
  },
  "user_env": {
    "x": 42,
    "my-func": {
      "type": "closure",
      "params": ["n"],
      "body": ["*", "n", "x"],
      "env": {"x": 42}
    }
  }
}

This represents: - stack: Current operand stack values - pc: Program counter (next instruction to execute) - instructions: The JPN bytecode being executed - resource_checkpoint: Optional resource tracking state - user_env: User-defined variables and functions (not the prelude)

The separation between user environment and prelude means: - User-defined state travels with the paused execution - The prelude (built-in functions) exists on every JSL host - State can be stored, transmitted, and resumed anywhere - Everything remains pure JSON - no binary formats or special serialization

Example resumable execution with user-defined functions:

# Define a user function
evaluator.env['double'] = {
    'type': 'closure',
    'params': ['x'],
    'body': ['*', 'x', 2],
    'env': {}
}

# Compile program that uses it
jpn = compile_to_postfix(['double', 21])  # => [21, 1, 'double']

# Start execution with limited steps
result, state = evaluator.eval_partial(jpn, max_steps=1)

if state:  # Execution paused
    # State includes user-defined 'double' function
    # Everything is pure JSON - can be stored/transmitted
    json_state = json.dumps(state.to_dict())

    # Later, possibly on a different machine
    # Create fresh evaluator with only prelude
    fresh_evaluator = StackEvaluator(env=prelude.to_dict())

    # Restore state (including user environment)
    restored_state = StackState.from_dict(json.loads(json_state))

    # Resume execution - 'double' function is available!
    final_result, _ = fresh_evaluator.eval_partial(jpn, max_steps=100, state=restored_state)
    # final_result = 42

No binary formats, no special protocols - just JSON! User-defined functions travel with the paused state.

Testing¶

The same test suite runs on both evaluators, proving functional equivalence:

# tests/test_both_evaluators.py
@pytest.fixture(params=[RecursiveEvaluator, StackEvaluator])
def evaluator(request):
    return request.param()

def test_arithmetic(evaluator):
    assert evaluator.eval(['+', 2, 3]) == 5
    # This test runs twice - once per evaluator!

Future Work¶

Unify with recursive evaluator: Use the same Env and Closure classes for consistency
Optimize postfix: Dead code elimination, constant folding
JIT compilation: Compile hot paths to native code
Streaming evaluation: Process postfix as it arrives over network
Parallel execution: Some postfix sequences can run in parallel
Tail call optimization: Detect and optimize tail-recursive calls

Conclusion¶

Stack-based evaluation provides a production-ready alternative to recursive evaluation, with better resumption, optimization opportunities, and network characteristics. The postfix representation can serve as JSL's "bytecode" - the actual computational format, with S-expressions as the human-friendly source language.