Compiler API Reference¶

The compiler module (jsl.compiler) transforms JSL S-expressions into JPN (JSL Postfix Notation) for execution by the stack evaluator.

Overview¶

The compiler performs several transformations: - Infix to postfix conversion for operators - Special form compilation with control flow - Arity tracking for n-ary operations - Optimization of common patterns

Functions¶

`compile_to_postfix`¶

The main compilation function:

`jsl.compiler.compile_to_postfix(expr)` ¶

Compile a JSL S-expression to JPN (JSL Postfix Notation).

Examples:

['+', 2, 3] → [2, 3, '+'] # Binary (no arity needed) ['', 2, ['+', 1, 2]] → [2, 1, 2, '+', ''] # Nested binary ops ['+', 1, 2, 3, 4] → [1, 2, 3, 4, 4, '+'] # N-ary (arity before op) ['+'] → [0, '+'] # 0-arity ['list', 'a', 'b'] → ['a', 'b', 2, 'list'] # List creation

Parameters:

Name	Type	Description	Default
`expr`	`Any`	S-expression in JSL format	required

Returns:

Type	Description
`List[Any]`	JPN - list of instructions in postfix order (JSON-compatible)

Source code in jsl/compiler.py

def compile_to_postfix(expr: Any) -> List[Any]:
    """
    Compile a JSL S-expression to JPN (JSL Postfix Notation).

    Examples:
        ['+', 2, 3]           → [2, 3, '+']        # Binary (no arity needed)
        ['*', 2, ['+', 1, 2]] → [2, 1, 2, '+', '*'] # Nested binary ops
        ['+', 1, 2, 3, 4]     → [1, 2, 3, 4, 4, '+'] # N-ary (arity before op)
        ['+']                 → [0, '+']           # 0-arity
        ['list', 'a', 'b']    → ['a', 'b', 2, 'list'] # List creation

    Args:
        expr: S-expression in JSL format

    Returns:
        JPN - list of instructions in postfix order (JSON-compatible)
    """
    result = []

    def compile_expr(e):
        """Recursively compile expression, appending to result."""
        if isinstance(e, (int, float, bool, type(None))):
            # Literals are pushed directly
            result.append(e)
        elif isinstance(e, str):
            # Strings could be variables or operators
            # For now, just push them
            result.append(e)
        elif isinstance(e, list) and len(e) > 0:
            # Check if this is a special form that needs special handling
            if detect_special_form(e):
                # Special forms can't be compiled to regular postfix
                # because they have special evaluation rules
                result.append(Opcode.SPECIAL_FORM)
                result.append(e)
            else:
                # Regular S-expression: [operator, arg1, arg2, ...]
                op = e[0]
                args = e[1:]

                # If operator is itself a list (like [["lambda", ...], arg]), compile it too
                if isinstance(op, list):
                    # Compile the operator expression
                    compile_expr(op)
                    # Compile all arguments
                    for arg in args:
                        compile_expr(arg)
                    # Use special APPLY marker
                    result.append(len(args))
                    result.append('__apply__')
                else:
                    # Regular operator - compile arguments first
                    for arg in args:
                        compile_expr(arg)

                    # Always append arity before operator for consistency
                    result.append(len(args))
                    result.append(op)
        elif isinstance(e, list) and len(e) == 0:
            # Empty list - use special marker with arity format
            result.append(0)
            result.append('__empty_list__')
        elif isinstance(e, dict):
            # Dictionary literal - compile keys and values
            # Push each key-value pair, then use __dict__ operator
            for key, value in e.items():
                compile_expr(key)  # Compile key expression
                compile_expr(value)  # Compile value expression
            result.append(len(e) * 2)  # Total number of items (keys + values)
            result.append('__dict__')  # Dictionary creation operator
        else:
            # Other types - push as-is
            result.append(e)

    compile_expr(expr)
    return result

`decompile_from_postfix`¶

Reconstructs S-expressions from JPN (for debugging):

`jsl.compiler.decompile_from_postfix(postfix)` ¶

Convert JPN back to S-expression (for debugging/display).

This is the inverse of compile_to_postfix: compile_to_postfix(decompile_from_postfix(jpn)) == jpn

Parameters:

Name	Type	Description	Default
`postfix`	`List[Any]`	List of JPN instructions	required

Returns:

Type	Description
`Any`	Equivalent S-expression

Examples:

[2, 3, 2, '+'] → ['+', 2, 3][1, 2, 3, 3, '+'] → ['+', 1, 2, 3]['x', 'y', 2, '+'] → ['+', 'x', 'y'][0, '+'] → ['+'] # 0-arity addition

Source code in jsl/compiler.py

def decompile_from_postfix(postfix: List[Any]) -> Any:
    """
    Convert JPN back to S-expression (for debugging/display).

    This is the inverse of compile_to_postfix:
    compile_to_postfix(decompile_from_postfix(jpn)) == jpn

    Args:
        postfix: List of JPN instructions

    Returns:
        Equivalent S-expression

    Examples:
        [2, 3, 2, '+'] → ['+', 2, 3]
        [1, 2, 3, 3, '+'] → ['+', 1, 2, 3]
        ['x', 'y', 2, '+'] → ['+', 'x', 'y']
        [0, '+'] → ['+']  # 0-arity addition
    """
    stack = []
    i = 0

    # Set of known operators (anything that can be an operator)
    operators = {'+', '-', '*', '/', '%', '=', '!=', '<', '>', '<=', '>=',
                 'and', 'or', 'not', 'cons', 'append', 'first', 'rest', 
                 'length', 'str-length', 'list', 'if', 'lambda', 'let', 
                 'def', 'quote', '@', 'do', '__empty_list__'}

    while i < len(postfix):
        item = postfix[i]

        # Check if this could be an arity (number followed by operator)
        if isinstance(item, int) and i + 1 < len(postfix) and postfix[i + 1] in operators:
            # This is an arity-operator pair
            arity = item
            operator = postfix[i + 1]
            i += 2  # Skip both arity and operator

            # Pop arguments from stack
            if len(stack) < arity:
                raise ValueError(f"Stack underflow: {operator} needs {arity} args, have {len(stack)}")

            args = []
            for _ in range(arity):
                args.insert(0, stack.pop())

            # Create S-expression or handle special cases
            if operator == '__empty_list__' and arity == 0:
                # Special case: empty list
                stack.append([])
            elif arity == 0:
                stack.append([operator])
            else:
                stack.append([operator] + args)
        else:
            # It's a literal or variable - push to stack
            stack.append(item)
            i += 1

    if len(stack) != 1:
        raise ValueError(f"Invalid JPN: expected 1 item on stack, have {len(stack)}: {stack}")

    return stack[0]

Compilation Examples¶

Simple Expressions¶

from jsl.compiler import compile_to_postfix

# Arithmetic
expr = ["+", 1, 2, 3]
jpn = compile_to_postfix(expr)
print(jpn)  # [1, 2, 3, 3, "+"]

# Nested expressions
expr = ["*", ["+", 2, 3], 4]
jpn = compile_to_postfix(expr)
print(jpn)  # [2, 3, 2, "+", 4, 2, "*"]

Special Forms¶

from jsl.compiler import compile_to_postfix
from jsl.stack_special_forms import Opcode

# If expression
expr = ["if", ["=", "x", 5], "yes", "no"]
jpn = compile_to_postfix(expr)
# Result includes jump instructions for control flow

# Lambda expression
expr = ["lambda", ["x", "y"], ["+", "x", "y"]]
jpn = compile_to_postfix(expr)
# Result: [["x", "y"], ["+", "x", "y"], Opcode.SPECIAL_FORM, "lambda"]

Function Calls¶

from jsl.compiler import compile_to_postfix

# Simple function call
expr = ["square", 5]
jpn = compile_to_postfix(expr)
print(jpn)  # [5, 1, "square"]

# Multiple arguments
expr = ["add", 1, 2, 3]
jpn = compile_to_postfix(expr)
print(jpn)  # [1, 2, 3, 3, "add"]

JPN Format¶

Instruction Types¶

Literals: Push themselves onto stack

42           # Push number
"hello"      # Push string
True         # Push boolean
None         # Push null

Operators with Arity: Arity precedes operator

[1, 2, 3, 3, "+"]     # Add 3 numbers
[5, 1, "square"]      # Call square with 1 argument

Special Forms: Use Opcode.SPECIAL_FORM marker

[condition, Opcode.SPECIAL_FORM, "if", ...]
[params, body, Opcode.SPECIAL_FORM, "lambda"]

Control Flow: Jump instructions

[Opcode.JUMP_IF_FALSE, offset]  # Conditional jump
[Opcode.JUMP, offset]           # Unconditional jump

Compilation Rules¶

S-Expression	JPN Output	Notes
`42`	`[42]`	Literals compile to themselves
`"x"`	`["x"]`	Variables compile to strings
`["+", 1, 2]`	`[1, 2, 2, "+"]`	Args, arity, operator
`["if", c, t, f]`	Complex with jumps	Control flow compilation
`["lambda", params, body]`	`[params, body, Opcode.SPECIAL_FORM, "lambda"]`	Closure creation

Decompilation¶

For debugging, JPN can be decompiled back to S-expressions:

from jsl.compiler import compile_to_postfix, decompile_from_postfix

# Original expression
original = ["*", ["+", 1, 2], 3]

# Compile to JPN
jpn = compile_to_postfix(original)
print(jpn)  # [1, 2, 2, "+", 3, 2, "*"]

# Decompile back
reconstructed = decompile_from_postfix(jpn)
print(reconstructed)  # ["*", ["+", 1, 2], 3]

assert original == reconstructed  # True (for most expressions)

Advanced Topics¶

Optimization Opportunities¶

The compiler could optimize common patterns: - Constant folding: Evaluate constant expressions at compile time - Dead code elimination: Remove unreachable code after if - Tail call optimization: Convert tail calls to jumps

Custom Operators¶

Adding new operators requires: 1. Add to prelude with known arity 2. Compiler automatically handles them 3. No special compilation logic needed

# In prelude
def custom_op(a, b, c):
    return a + b * c

# Register in prelude
prelude["my-op"] = custom_op

# Automatically compiles correctly
expr = ["my-op", 1, 2, 3]
jpn = compile_to_postfix(expr)  # [1, 2, 3, 3, "my-op"]

Integration with Stack Evaluator¶

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

# Compile and execute
expr = ["do",
    ["def", "x", 10],
    ["*", "x", 2]
]

jpn = compile_to_postfix(expr)
evaluator = StackEvaluator()
result = evaluator.eval(jpn)
print(result)  # 20