MØSS/Implementation draft

So far, MØSS hasn't been implemented, but we can give a rough framework for an interpreter. Maybe someday, the author of MØSS, User:PrySigneToFry, will actually implement the language.

Generic Framework

This interpreter should have an architecture like this: source code → lexer → token stream → parser → abstract syntax tree → semantic analyzer → symbol table → interpreter → final program result. During the execution engine running the program, the environment (scope), object model, built-in functions, I/O, and memory management are also really important parts.

Core Modules

Lexer

Input: source file string

Output: stream of tokens

Responsibilities: recognize keywords (if, while, func, etc.), operators (+, -, *, /, =, ==), literals (numbers, strings, booleans, nil), identifiers, and separators (braces, brackets, parentheses, commas and periods).

Design points: support single-line comments with #; ignore whitespace and newlines; provide position info (line number, column number) for error reporting.

Parser

Input: Token stream

Output: Abstract Syntax Tree (AST)

Responsibilities: Build AST nodes based on context-free grammar (using recursive descent or Pratt parsing).

AST Node Types (simplified):

Program

contains multiple statements

Statement

expression statements, variable assignments (=), if, while, for, return, break, continue, import, block

Expression

literals (Number, String, Boolean, Nil), identifiers, binary operations, unary operations, function calls, member access (.), index access ([]), new operations, object literals, list literals, list comprehensions, function definitions, this, __proto__ access, etc.

Design Points: Handle operator precedence and associativity; distinguish between l-values and r-values; support statement blocks as scopes.

Semantic Analyzer (Optional but Recommended)

Input: AST

Output: Annotated AST (or symbol table)

Responsibilities:

• Variable scope resolution (static scope)
• Check for undefined variables (can be deferred to runtime, but early checking helps with debugging)
• Prototype chain integrity check (optional)
• Detect infinite loops, etc. (simple implementation can be skipped to keep the interpreter simple)

Interpreter

Input: AST (usually a Program node)

Output: Program execution result (or side effects)

Responsibility: Traverse the AST, execute each statement, and manage the execution context.

Core algorithm: The eval function recursively traverses AST nodes and performs actions based on node type:

• Literal → return the value
• Identifier → look it up in the current environment
• Assignment → modify the variable in the environment
• Function definition → create a function object (closure)
• Function call → create a new environment, bind arguments, execute the function body
• new → create an object, set its prototype, call init (if any)
• Member access → look up object properties (traverse the prototype chain)
• List operations → indexing/slicing/comprehensions
• Control flow → jump based on conditions (if, while, for)

Execution model: tree-walking interpreter (not bytecode), simple and straightforward; can switch to bytecode VM later for better performance.

Environment and Scope

Role: Stores variable bindings and manages the scope chain.

Data Structure: Nested hash tables (dictionaries), where each environment points to its outer environment.

Operations:

• define(name, value): Creates a new binding in the current scope (used for var or assignment)
• assign(name, value): Finds and updates the variable in the current or outer scope if it exists
• lookup(name): Looks up the variable from inside out, throws an undefined error if not found

Special Environments: Global environment, function local environments (created anew with each call), block environments ({} create a new scope)

Object System (Object Model)

Core concept: All values (including primitives) are objects or can be wrapped; but for simplicity, we can distinguish between value types and reference types.

Object (MossObject):

• Property table (hash table): string -> Value
• Internal prototype pointer (__proto__)
• Special methods (init as constructor)
• Value representation (all unified as Value type):
  • Primitive types: Number, String, Boolean, Nil
  • Composite types: List (inherits from built-in List prototype), Object (regular object), Function (callable object), NativeFunction (built-in function)
• Prototype chain lookup: When accessing a property, if the current object doesn't have it, recursively check __proto__.

new operation:

• Create a new object and set its __proto__ to the constructor's __proto__ (the prototype)
• Call init method (if any) with the new object as this
• Return the new object

Built-in Features

Built-in Functions

Standard I/O

print, input, input_int, open, file.read, file.write, file.close

List methods

len, append, remove, sort, reverse, contains, index

Math functions

sqrt, sin, cos, pow, rand, random, etc.

Type conversion

number, floor, ceil, round, str, bool

Object operations

type, has_attr, get_attr, set_attr

Runtime

time.now, time.sleep

I/O Subsystem

• Standard input/output: Interacts with the host language (like Python's sys.stdout.write and input)
• File system: Provides File objects, wrapping open, read, write, and close operations, running in safe mode (only allows the current directory)

Memory Management

• Reference counting and cycle detection (or simple mark-and-sweep), since the language supports circular references (object prototype chains, lists referencing each other).
• To simplify implementation, you can rely on the host language's GC (like Python's); if the interpreter is written in Python, it's automatically managed; if it's written in C++, you'll have to implement it manually.

Execution Flow (using source code to result as an example)

1. Read the source file (or input line by line in REPL)
2. Lexical analysis → Token stream
3. Syntax analysis → AST (Program)
4. Create the global environment, register all built-in functions/objects
5. Call the execution engine's eval(program, globalEnv):
6. Execute each statement in the AST one by one
   • Assignment statement → modify the environment
   • Function definition → create a function object, store it in the environment
   • Function call → create a new environment (closure captures outer environment)
   • Object creation → create a new object, set prototype, call init
   • Control flow → modify execution path (use exceptions or return values to control loops/function returns)
7. Program ends, return the final value (usually nil or main's return value)
8. If REPL, print the result of the expression evaluation and go back to step 2

Key Data Types (in Pseudo Code)

# Value unified type
class Value:
    pass

class Number(Value):
    def __init__(self, value): self.value = float(value)

class String(Value):
    def __init__(self, value): self.value = str(value)

class Boolean(Value):
    def __init__(self, value): self.value = bool(value)

class Nil(Value):
    pass

class List(Value):
    def __init__(self, elements=None):
        self.elements = elements or []

class Object(Value):
    def __init__(self, proto=None, props=None):
        self.__proto__ = proto
        self.properties = props or {}

class Function(Value):
    def __init__(self, params, body, env, is_native=False):
        self.params = params
        self.body = body          # AST node
        self.closure_env = env
        self.is_native = is_native
        self.native_func = None   # If native then point to the host function

# Environment
class Environment:
    def __init__(self, outer=None):
        self.store = {}
        self.outer = outer

    def define(self, name, value): self.store[name] = value
    def assign(self, name, value):
        if name in self.store: self.store[name] = value
        elif self.outer: self.outer.assign(name, value)
        else: raise NameError
    def lookup(self, name):
        if name in self.store: return self.store[name]
        elif self.outer: return self.outer.lookup(name)
        else: raise NameError

Error Handling and Debugging

Use a unified exception mechanism (RuntimeError, SyntaxError) that includes location info. Provide friendly error messages (line number, column number, error description). Support try/catch extensions (optional, can be skipped at first). Add a debug mode: output AST or execution trace.

Scalability and Portability

• Module System: Dynamically load other MØSS source files via import, with module objects being cacheable.
• FFI (Foreign Function Interface): Reserved extension interface, allowing functions to be registered from the host language.
• Cross-Platform: Interpreter core is platform-independent, with the I/O layer adapting to different operating systems (using the host language’s standard library).

Performance Considerations (Brief)

• For production-grade, you might consider compiling the AST to bytecode and implementing a VM, but it's not necessary at the framework stage.
• Cache prototype chain lookup results (optimize property access).
• Pay attention to the efficiency of common list and string operations (like concatenation with plus).
• Tail recursion optimization (optional), since recursion is part of the Turing completeness proof.

Development Roadmap Suggestions

• Phase 1: Implement lexical analysis, syntax parsing (supporting only variables, arithmetic, function calls), basic execution engine (no objects), and test small programs (Fibonacci).
• Phase 2: Add control flow (if, while), func definitions and closures, built-in print/input.
• Phase 3: Implement object system (prototype, this, new), list type and basic methods.
• Phase 4: Improve standard library (file, time, random), error handling, REPL.
• Phase 5: Optimization, debugging tools, documentation.