STAR-LANG-RESEARCH-000 Star-Lang Language Design Foundations

• STAR-RESEARCH-PIPELINE-INDEX-000 Adaptive Research
• STAR-RESEARCH-PIPELINE-001 Adaptive Research DAG and Evaluation Harness
• STAR-RESEARCH-001 Logic Engine Selection for ADARD
• STAR-SERVER-000 Composable Intelligence GServer Domains
• STAR-INDEX-000 StarIntel Fourth Generation

What is the smallest language architecture that lets StarIntel authors declare resumable analysis runs¹, coordinate supervised actors², invoke Prolog³ through explicit reasoning capabilities, preserve complete provenance, and recover through declared Common Lisp conditions and restarts without becoming a new general-purpose programming language?

Star-Lang should be a declarative domain-specific language⁴ embedded in Common Lisp⁵. Its source syntax should use S-expressions⁶, but source forms must be treated as data and compiled through a private reader, syntax objects, a checked core intermediate representation⁷, and an immutable execution plan. Star-Lang source must never be passed directly to Common Lisp EVAL.

The first version should provide:

• a small closed set of declarative forms
• source locations on every syntax and plan node
• schema and contract checking
• explicit effect and capability declarations
• deterministic orchestration separated from effectful actor work
• append-only run history and compatible checkpoints
• named, typed, auditable conditions and restarts
• actor message envelopes with idempotency keys
• an isolated Prolog capability boundary
• expansion, checking, planning, tracing, and replay tools

The first version should not provide:

• arbitrary Common Lisp escapes
• user-defined reader macros
• unrestricted compile-time execution
• raw continuation persistence
• a general distributed workflow engine
• unrestricted plugin loading
• native-code generation
• automatic architecture promotion
• full polymorphic type or effect inference

Star-Lang is a language for declaring an analysis and its recovery policy. It is not the actor implementation language, rule language, storage query language, or user-interface language.

A Star-Lang program declares:

1. typed inputs and expected outputs
2. allowed effects and capabilities
3. bounded resource policy
4. deterministic control relationships
5. actor commands and awaited results
6. reasoning requests
7. checkpoint boundaries
8. conditions and permitted restarts
9. emitted artifacts and provenance

Common Lisp implements the compiler, interpreter, runtime adapters, actors, and tooling. Prolog implements selected logic capabilities. Actor libraries implement collection, normalization, model invocation, and storage effects.

(star:analysis investigate-target
  (:version 1)
  (:inputs ((target star:target-document)))
  (:outputs ((report star:analysis-report)))
  (:effects (:read-dataset
             :network
             :llm
             :prolog
             :write-artifact
             :human-approval))
  (:policy ((:max-wall-time "PT30M")
            (:max-cost-usd 5.00)
            (:max-parallelism 4)))

  (star:checkpoint :accepted-input)

  (star:parallel
    (star:collect
      :actor star.actors.news:collector
      :request (star:news-request :target target)
      :as news)
    (star:collect
      :actor star.actors.registry:collector
      :request (star:registry-request :target target)
      :as registry))

  (star:let ((documents
              (star:normalize :inputs (news registry))))
    (star:reason
      :capability :deterministic-rule-evaluation
      :facts documents
      :query (star:query (risk target ?reason))
      :as proofs))

  (star:on-condition star:source-unavailable
    (star:restart :retry :max-attempts 2)
    (star:restart :use-value :value ())
    (star:restart :request-human))

  (star:checkpoint :reasoning-complete)
  (star:emit :type star:analysis-report
             :from (documents proofs)
             :as report))

This syntax is illustrative. Form names and argument schemas become stable only after parser and core-model fixtures pass review.

The surface language may add convenience forms, but every form must expand into this small core:

Convenience forms such as collect, normalize, choose, and on-condition must be syntax transformations⁸ over the core rather than independent runtime mechanisms.

@startuml
skinparam componentStyle rectangle

artifact "Star-Lang Source\nS-expressions" as Source
component "Safe Reader" as Reader
component "Syntax Objects\nwith Source Spans" as Syntax
component "DSL Expander" as Expander
component "Schema, Type, and\nEffect Checker" as Checker
component "Core IR" as IR
component "Plan Compiler" as Compiler
artifact "Immutable Run Plan" as Plan
component "Interpreter / Replay Engine" as Runtime

Source --> Reader
Reader --> Syntax
Syntax --> Expander
Expander --> Checker
Checker --> IR
IR --> Compiler
Compiler --> Plan
Plan --> Runtime

note bottom of Reader
*READ-EVAL* = NIL
private readtable
closed literal grammar
end note

note bottom of Expander
No file, network, model,
actor, or Prolog effects
end note
@enduml

The compiler must use the following phases:

1. The safe reader⁹ converts text into syntax objects¹⁰ carrying source spans¹¹.
2. The expander resolves only registered Star-Lang forms and rewrites convenience syntax into the core.
3. The checker validates names, schemas, contracts¹², types, effect declarations, capability requirements, restart legality, and bounded policies.
4. The core intermediate representation contains no reader or macro objects and no executable host-language forms.
5. The plan compiler assigns stable node identifiers, dependencies, effect sets, checkpoints, and command templates.
6. The interpreter executes or replays the immutable plan against an append-only history.

Common Lisp reading is programmable and can execute read-time evaluation through sharpsign-dot when *READ-EVAL* is true.¹³ Star-Lang must therefore use all of these controls:

• bind *READ-EVAL* to NIL
• use a private readtable¹⁴
• permit only parentheses, symbols, keywords, strings, integers, bounded ratios, booleans, and explicitly registered literals
• reject circular notation, pathname literals, structure literals, arbitrary dispatch macros, and implementation-specific objects
• intern language symbols in a private package or resolve them without interning untrusted names globally
• preserve the original file, line, column, and byte range
• impose maximum source size, nesting depth, token length, collection length, and numeric magnitude
• return structured parse conditions rather than entering an interactive debugger

The reader produces data. It never invokes COMPILE, LOAD, EVAL, actor code, Prolog, the network, or storage.

Racket demonstrates that a language can define its own module boundary, reader, and hygienic macro system while preserving source-aware tooling.^{15, 16} Star-Lang should adopt the separation of reader, expander, and runtime, but it does not need to reproduce Racket's complete macro system.

Version 0.1 should use registered expander functions with these rules:

• one expander owns one surface form
• input and output are syntax objects
• output must contain only registered core forms and checked literals
• expansion is deterministic and side-effect free
• expansion has a bounded step count and output size
• every generated node retains an origin chain to the source form
• bindings are represented by compiler-issued identifiers, not text substitution
• an expansion cannot inspect the repository, environment variables, clock, random generator, network, model, or Prolog database

This provides the binding safety normally associated with hygienic macros¹⁷ without committing the first implementation to a general macro language.

Version 0.1 should use explicit schemas and algebraic data types¹⁸, not a full Hindley-Milner-style inference engine.

Required classes of type:

• scalar values: string, integer, boolean, timestamp, duration, identifier, hash, URI
• document references: dataset, schema, document, artifact, evidence, actor, capability
• collections: list, set, map, optional, result
• domain records: target document, collection request, proof trace, review, report
• runtime records: run, plan node, command, event, checkpoint, condition, restart

Each actor command and result must name a versioned input and output schema. The compiler checks declared relationships; the runtime revalidates data crossing an actor or process boundary.

A contract failure before plan creation is a compile error. A contract failure in an external result is a runtime condition and cannot be silently coerced.

An effect system¹⁹ records which externally observable operations an expression may perform. A capability²⁰ is an explicit authority to perform a particular operation. Star-Lang needs a bounded version of both concepts rather than a research-grade general effect calculus.

Initial effect set:

• :read-repository
• :read-dataset
• :network
• :llm
• :prolog
• :write-transient
• :write-artifact
• :write-canonical-proposal
• :human-approval
• :clock
• :random

Rules:

1. Every effectful core node declares its required effect.
2. The analysis header declares the maximum effect set.
3. The compiler rejects a node whose effect is not declared.
4. Runtime policy narrows, but never widens, the compiled effect set.
5. Actor routing requires a matching capability token or policy grant.
6. Effects that can change external state require an idempotency key²¹.
7. Clock and random values are effects whose results are written to history.
8. Replay reuses recorded effect results instead of repeating the operation.

Koka's effect typing demonstrates that effect information can be attached to function types and used to reason about control effects.^{22, 23} Star-Lang only needs explicit declared sets in version 0.1. Inference can be added after real programs expose repeated annotation problems.

The runtime state is:

<plan, cursor, bindings, history, pending-commands, status>

The formal semantics²⁴ should define a small-step transition relation²⁵:

<plan, state, history> -> <plan, state', history'>

Required rules:

• Pure nodes compute deterministically from immutable bindings.
• A command node appends one command event and moves to AWAITING.
• A matching result event binds the checked result and advances the cursor.
• A previously completed command is not dispatched again during replay.
• A parallel block may advance any ready node whose declared effects do not conflict.
• A condition node records the condition and the set of legal restarts.
• A restart event selects one legal transition and records its parameters.
• An emit node records the artifact identifier, schema, content hash, and provenance.
• The same plan hash and event history must reconstruct the same logical state.

The reference interpreter is authoritative in version 0.1. Any later optimizer or compiled executor must produce the same observable event history for the same plan and effect results.

An analysis run is a durable logical execution of one immutable plan. It is not a queue job whose only meaningful states are pending, running, and finished.

Temporal's workflow model shows the useful separation: deterministic orchestration is reconstructed from event history, while external operations execute separately and return recorded results.^{26, 27} Star-Lang should implement that semantic boundary without importing Temporal as a required runtime.

@startuml
skinparam componentStyle rectangle

component "Plan Interpreter" as Interpreter
database "Append-Only Event Journal" as Journal
database "Checkpoint Store" as Checkpoints
queue "Command Outbox" as Outbox
component "Effect Actor" as Actor

Interpreter --> Journal : append command event
Interpreter --> Outbox : publish idempotent command
Outbox --> Actor : deliver
Actor --> Journal : append result or condition
Journal --> Interpreter : wake matching run
Interpreter --> Checkpoints : write compatible snapshot

component "Restarted Interpreter" as Restarted
Journal --> Restarted : replay authoritative history
Checkpoints --> Restarted : optional acceleration
Restarted --> Journal : continue from reconstructed state

note bottom of Journal
Source of truth for logical state
end note

note bottom of Checkpoints
Optimization, never authority
end note
@enduml

The event journal²⁸ is authoritative. A checkpoint²⁹ accelerates recovery but may be discarded and rebuilt by replay³⁰.

Each event must contain:

• event identifier
• run identifier
• analysis definition identifier and version
• plan hash³¹
• plan-node identifier
• event type and schema version
• causation and correlation identifiers
• attempt number
• actor or runtime identity
• timestamp supplied as a recorded clock effect
• input and output hashes
• effect and capability identifiers
• structured payload or artifact reference

A checkpoint must store declarative runtime state, not an implementation continuation³². It contains:

• plan hash and analysis version
• interpreter and checkpoint schema versions
• current cursor or ready-node set
• immutable bindings or references to hashed values
• completed command identifiers and result references
• pending awaits and correlation identifiers
• active condition and legal restart descriptors
• resource counters
• last included journal event identifier

Resume is allowed when:

• the plan hash matches; or
• a reviewed migration explicitly maps the old plan and checkpoint schema to the new version.

A changed plan must never silently resume from an old cursor. The runtime must either replay a compatible version, apply a recorded migration, or begin a new run linked to the prior run.

The Common Lisp condition system³³ separates detecting a condition from selecting a recovery action. A restart³⁴ exposes a recovery transfer that handlers may choose without forcing the signaling code to own policy.^{35, 36, 37}

Star-Lang should preserve that separation while making it durable and non-interactive.

Initial conditions:

• source-unavailable
• rate-limited
• schema-mismatch
• capability-unavailable
• reasoner-timeout
• budget-exhausted
• policy-denied
• artifact-write-failed
• human-decision-required
• incompatible-checkpoint

Initial restarts:

• retry
• retry-after
• use-value
• skip-branch
• select-fallback-capability
• request-human
• abort-analysis

@startuml
[*] --> RUNNING
RUNNING --> AWAITING : command emitted
AWAITING --> RUNNING : valid result recorded
RUNNING --> CONDITION : condition recorded
AWAITING --> CONDITION : failure recorded

CONDITION --> RUNNING : retry / use-value / fallback
CONDITION --> WAITING_HUMAN : request-human
WAITING_HUMAN --> RUNNING : approved restart event
CONDITION --> FAILED : abort-analysis
RUNNING --> COMPLETED : outputs emitted

COMPLETED --> [*]
FAILED --> [*]
@enduml

Rules:

1. Conditions and restart arguments have versioned schemas.
2. The compiler verifies that each declared restart is legal for the condition and surrounding form.
3. The runtime records the available restart set when signaling the condition.
4. An unattended policy may select only a restart explicitly allowed by the analysis and runtime policy.
5. Human selection is recorded as an event with identity and supplied parameters.
6. A retry preserves the original command identifier and increments the attempt number according to the actor protocol.
7. Restarts are declarative descriptors; raw Common Lisp restart closures are not persisted.

@startuml
skinparam componentStyle rectangle

component "Analysis Run Supervisor" as Supervisor
component "Plan Interpreter" as Interpreter
component "Capability Router" as Router
queue "Durable Command Outbox" as Outbox
component "Collection / Model / Storage Actors" as Actors
component "Prolog Adapter Actor" as Adapter
component "Logic Capability Router" as LogicRouter
component "Isolated Logic Engine Worker" as Logic
component "Event Journal" as Journal

Supervisor --> Interpreter
Interpreter --> Router : checked command
Router --> Outbox
Outbox --> Actors
Outbox --> Adapter : reasoning command
Adapter --> LogicRouter : capability + immutable facts/query
LogicRouter --> Logic : selected engine request
Actors --> Journal : result / condition
Logic --> Adapter : answers + proof + engine metadata
Adapter --> Journal : checked reasoning result
Journal --> Interpreter : correlated event
Supervisor --> Journal : lifecycle events
@enduml

The analysis run supervisor³⁸ owns lifecycle, budget, cancellation, and child actors. It does not perform collection or reasoning itself.

Every actor command envelope must include:

(:star-command
 (:schema-version 1)
 (:run-id "run-uuid")
 (:plan-hash "sha256")
 (:plan-node-id "node-id")
 (:command-id "stable-command-id")
 (:attempt 1)
 (:causation-id "event-id")
 (:correlation-id "correlation-id")
 (:idempotency-key "stable-key")
 (:capability :news-collection)
 (:effects (:network :write-transient))
 (:input-schema "star.news-request/1")
 (:input-hash "sha256")
 (:payload-ref "artifact-or-inline-reference"))

The Prolog foreign-function interface³⁹ or process adapter must expose a capability request rather than a shared mutable Prolog database. SWI-Prolog provides explicit foreign frames and predicate-call interfaces, which are suitable implementation primitives when embedding is selected.^{40, 41}

A reasoning request contains:

• capability identifier such as deterministic rule evaluation, probabilistic query, tabled recursion, explanation, or bulk Datalog closure
• isolated fact set or immutable fact artifact
• rule-set identifier and version
• query and output schema
• time, inference, and memory limits
• required proof-trace⁴² level
• engine selection policy

A reasoning result contains:

• selected engine and version
• adapter version
• answer bindings
• proof, explanation, or derivation artifact
• input, rule-set, and output hashes
• completeness or approximation status
• resource use
• structured warnings and conditions

The engine is selected through the capability-routing study in STAR-RESEARCH-001 Logic Engine Selection for ADARD. Star-Lang must not encode engine-specific syntax in the core language.

Erlang/OTP supervision trees separate worker behavior from restart policy and organize processes into bounded fault domains.^{43, 44} Star-Lang should declare the logical recovery policy, while the actor runtime implements process supervision.

Required separation:

• actor crash: actor supervisor restarts or replaces the worker
• command failure: actor emits a structured result condition
• analysis recovery: Star-Lang policy selects a declared restart
• journal failure: stop state advancement; never acknowledge unrecorded progress
• checkpoint failure: continue from journal when safe and record degraded operation
• Prolog worker crash: discard isolated engine state and retry only through a legal restart
• cancellation: record cancellation request and completion; do not infer cancellation from process death alone

Every syntax, core, plan, command, event, condition, restart, and output node must retain a source map from generated representation to the original source span. LLVM's debug metadata demonstrates the value of preserving source-level locations through transformed representations.⁴⁵

Required commands or Emacs entry points:

• star-lang expand: show surface syntax expanded to core forms
• star-lang check: report parse, name, schema, type, effect, capability, and restart errors
• star-lang plan: show the immutable execution directed acyclic graph⁴⁶
• star-lang trace: show events grouped by source form, actor, command, and causation
• star-lang replay: reconstruct state at an event or checkpoint
• star-lang explain: show why a node is ready, blocked, skipped, retried, or failed

Trace output must distinguish:

• source expansion
• pure evaluation
• command creation
• delivery attempts
• actor execution
• result validation
• condition signaling
• restart selection
• checkpoint creation
• replayed versus newly executed effects

Incremental compilation⁴⁷ should begin with content-addressed phase caches rather than a complex dependency engine.

Version 0.1 cache keys:

• parsed syntax: source content hash + reader version
• expanded core: syntax hash + expander registry hash
• checked core: core hash + schema registry hash + checker version
• run plan: checked-core hash + plan compiler version + policy schema version

Salsa's red-green algorithm and the Rust compiler's dependency graph show how a later query-directed incremental system can validate only dependencies that may have changed.^{48, 49} Star-Lang should add that complexity only after profiling shows phase-cache invalidation is too broad.

Optimization is permitted only after type, effect, and dependency checking. Initial semantics-preserving passes:

• constant folding of pure literal expressions
• dead-step elimination⁵⁰ for unreachable pure nodes
• common-subexpression reuse⁵¹ for identical pure queries
• parallel scheduling of dependency-independent nodes with non-conflicting effects
• immutable artifact reuse by content hash
• checkpoint coalescing when recovery guarantees are unchanged

Forbidden without a proof or explicit semantic rule:

• reordering network, storage, model, clock, random, approval, or canonical-write effects
• combining commands with different idempotency or provenance requirements
• removing an effect because its result appears unused when the effect itself is externally observable
• changing retry counts or restart selection
• dropping proof or negative-result artifacts

Required test layers:

1. Reader rejection fixtures for every forbidden reader form and size limit.
2. Golden tests⁵² for source-to-core expansion and source maps.
3. Positive and negative schema, type, effect, capability, and restart checks.
4. Property tests⁵³ for parser round trips, identifier stability, event replay, and idempotency.
5. State-machine tests for every legal and illegal run transition.
6. Differential tests comparing the reference interpreter with any optimized executor.
7. Replay tests that crash after every event boundary and reconstruct identical logical state.
8. Fault injection for actor crashes, duplicate delivery, delayed results, journal failure, corrupt checkpoints, Prolog timeout, and human-decision waits.
9. Actor adapter contract tests using mock and replay transports.
10. Prolog adapter tests covering isolation, proof metadata, timeout, cancellation, and engine fallback.
11. Concurrency tests for parallel branches, effect conflicts, and deterministic final bindings.
12. Migration tests for every accepted analysis, event, plan, and checkpoint schema change.

A test that performs an external effect must record whether it used a mock, replay fixture, sandbox, or live service. Tests must never claim replay safety from a run that did not inject failures.

• Star-Lang source cannot execute Common Lisp reader or evaluator code.
• Every accepted form expands into the closed core.
• Every core and plan node maps back to a source span.
• Undeclared effects, unavailable capabilities, invalid schemas, and illegal restarts fail before execution.
• A fixed plan and event history reconstruct identical logical state after a crash.
• Replayed runs do not repeat completed external effects.
• Duplicate actor delivery does not create duplicate logical results or external writes.
• Checkpoints can be deleted without destroying recoverability.
• An incompatible checkpoint is rejected or migrated explicitly.
• Conditions expose only declared, typed restarts.
• Actor crashes and logical recovery remain separate recorded events.
• Prolog reasoning runs in an isolated scope and returns engine, rule, proof, and hash metadata.
• The reference interpreter and optimized executor pass differential event-history tests.
• Tooling can expand, check, plan, trace, replay, and explain one fixture analysis.
• No Star-Lang construct may write a canonical design or implementation file without the existing promotion and human-approval controls.

A later numbered design should freeze only these interfaces:

1. source grammar and closed core forms
2. syntax object and source-span schema
3. checked core intermediate representation
4. effect and capability vocabulary
5. immutable run-plan schema
6. command, result, condition, restart, event, and checkpoint schemas
7. actor routing and idempotency protocol
8. Prolog capability request and result protocol
9. replay compatibility and migration rules
10. reference interpreter observable semantics

The design should begin with executable fixtures for one serial analysis, one parallel analysis, one Prolog query, one retry, one human restart, and one crash-and-replay run. It should not add more syntax until those fixtures are deterministic and inspectable.