Lisp Interpreter In Java

This is a small Lisp/Scheme-like interpreter written in Java. It reads a single S-expression from stdin and evaluates it in a persistent environment (REPL).

Features

• Interactive REPL
• Numeric literals: integers (e.g. 42, -7)
• Boolean literals: true / false
• Variables: symbols like x, myVar
• Special forms
  • define: define/update a variable
  • lambda: create procedures (lexical closures)
  • if: conditional evaluation
  • begin: evaluate multiple expressions sequentially
• Primitive procedures (built in)
  • +, *, = (binary, two arguments)

Quick start

Requirements

• Java: JDK 8+ (any recent JDK should work)

Compile

From the repository root:

javac -d out $(find src -name "*.java")

Run

java -cp out interpreter.Main

You should see the prompt:

λ >

Usage (REPL examples)

Arithmetic

λ > (+ 1 2)
3
λ > (* 6 7)
42
λ > (= 10 10)
true
λ > (= 10 11)
false

Variables and define

λ > (define x 5)
5
λ > (+ x 3)
8

Conditionals with if

λ > (if true 1 2)
1
λ > (if (= 1 2) 10 20)
20

Procedures with lambda

lambda takes a parameter list and one or more body expressions.

λ > (define inc (lambda (x) (+ x 1)))
backend.CompoundProcedure@...
λ > (inc 41)
42

Sequencing with begin

λ > (begin (define x 1) (define y 2) (+ x y))
3

Supported language (current)

Grammar model

Input is parsed as a single expression per line:

• Atoms: integers, true/false, or symbols
• Lists: parenthesized forms like (operator arg1 arg2 ...)

Special forms are recognized by the first word in a list:

• (define <name> <expr>)
• (lambda (<params...>) <body1> <body2> ...)
• (if <predicate> <consequent> <alternative>)
• (begin <expr1> <expr2> ...)

Everything else is treated as application:

• (<operator> <operand1> <operand2> ...)

Notes / limitations

• Only one expression per REPL line (no multi-line forms).
• No quoting: '(...) / (quote ...) is not supported yet.
• No lists/cons: there is no list data type beyond syntax; you should create it using lambdas.
• +, *, = currently require exactly two arguments.
• Error handling: the REPL catches exceptions and prints the exception value.

Project structure

• src/interpreter/Main.java: starts the REPL, initializes the global environment, registers primitive procedures.
• src/forntend/Parser.java: tokenizes a one-line program string and parses it into a RawExpression AST.
• src/interpreter/RawExpressionTranslator.java: lowers RawExpression into backend Expression nodes.
• src/backend/*: evaluation model (AST nodes, environment, procedures, primitive procedures).

Implementation overview

Data flow

• Tokenize: Parser.programStrToList adds spaces around parentheses and splits the line into tokens.
• Parse: Parser.parse builds a RawExpression tree.
• Translate: RawExpressionTranslator.translateToExpression converts raw nodes into typed backend Expressions.
• Evaluate: each backend Expression implements eval(Environment) and returns a SelfEvaluating value.

Environment and evaluation model

• Environment is a HashMap<String, SelfEvaluating>.
• define mutates the current environment (Environment.addMut). This makes definitions persist across REPL inputs.
• Procedures are SelfEvaluating values. A lambda captures an environment and evaluates its body in an extended environment during application.

Troubleshooting

• Syntax Error
  • Likely indicates mismatched parentheses.
• Too few arguments supplied!!! / Too many arguments supplied!!!
  • Your procedure call arity does not match the procedure's parameter list.

Roadmap ideas

• Add quoting (quote / ') and list primitives (cons, car, cdr).
• Add variadic primitives for + and *.
• Add better error messages with line context.

License

MIT