LISP Interpreter - Created by Cline and Qwen 3 Coder for less than $1 🤯

0.README.md

Lisp Interpreter

A simple Lisp (Scheme-like) interpreter implemented in Rust.

Created by Eleanor Berger using Cline and Qwen 3 Coder, for less than $1 and in 10 minutes.

Features

• REPL (Read-Eval-Print Loop) interface
• Basic data types: numbers, booleans, strings, symbols, lists
• Arithmetic operations: +, -, *, /
• Comparison operations: =, <, >
• List operations: cons, car, cdr, list
• Type predicates: number?, symbol?, boolean?, list?, null?
• Control structures: if, define, lambda, begin
• Quoting: 'expr syntax
• Variables and function definitions

Usage

Running the Interpreter

To run the interpreter, use:

cargo run

This will start the REPL where you can enter Lisp expressions.

Exiting the Interpreter

Press Ctrl+D to exit the interpreter.

Getting Help

Type (help) in the interpreter to display a help message with usage examples.

Examples

;; Arithmetic
(+ 1 2 3)  ; => 6
(- 10 3)   ; => 7
(* 2 3 4)  ; => 24
(/ 20 2)   ; => 10

;; Comparisons
(= 5 5)    ; => true
(< 3 5)    ; => true
(> 7 2)    ; => true

;; Lists
(cons 1 '(2 3))     ; => (1 2 3)
(car '(1 2 3))      ; => 1
(cdr '(1 2 3))      ; => (2 3)
(list 1 2 3)        ; => (1 2 3)

;; Quoting
'hello              ; => hello
'(1 2 3)            ; => (1 2 3)

;; Variables
(define x 10)       ; => x
x                   ; => 10

;; Functions
((lambda (x) (* x 2)) 5)  ; => 10

;; Conditionals
(if (> x 5) "big" "small")  ; => "big"

;; Sequences
(begin 1 2 3)       ; => 3

Building

To build the project, use:

cargo build

Running Tests

To run the project with a test file, use:

cargo run < test-file.lisp

Project Structure

• src/main.rs - Entry point with REPL implementation
• src/ast.rs - Abstract Syntax Tree definitions
• src/environment.rs - Variable and function storage
• src/parser.rs - Lexer and parser for Scheme expressions
• src/builtins.rs - Built-in functions implementation
• src/evaluator.rs - Expression evaluation engine

1.cline-qwen3-coder-lisp.png

ast.rs

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    Number(f64),
    Boolean(bool),
    String(String),
    Symbol(String),
    List(Vec<Expr>),
    Lambda {
        params: Vec<String>,
        body: Box<Expr>,
    },
    Nil,
}

impl Expr {
    pub fn is_nil(&self) -> bool {
        matches!(self, Expr::Nil)
    }
}

impl std::fmt::Display for Expr {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            Expr::Number(n) => write!(f, "{}", n),
            Expr::Boolean(b) => write!(f, "{}", b),
            Expr::String(s) => write!(f, "\"{}\"", s),
            Expr::Symbol(s) => write!(f, "{}", s),
            Expr::List(exprs) => {
                write!(f, "(")?;
                for (i, expr) in exprs.iter().enumerate() {
                    if i > 0 {
                        write!(f, " ")?;
                    }
                    write!(f, "{}", expr)?;
                }
                write!(f, ")")
            },
            Expr::Lambda { .. } => write!(f, "#<lambda>"),
            Expr::Nil => write!(f, "nil"),
        }
    }
}

builtins.rs

use crate::ast::Expr;

pub fn add(args: Vec<Expr>) -> Result<Expr, String> {
    let mut sum = 0.0;
    for arg in args {
        match arg {
            Expr::Number(n) => sum += n,
            _ => return Err("Arguments to + must be numbers".to_string()),
        }
    }
    Ok(Expr::Number(sum))
}

pub fn subtract(args: Vec<Expr>) -> Result<Expr, String> {
    if args.is_empty() {
        return Err("- requires at least one argument".to_string());
    }
    
    let mut result = match &args[0] {
        Expr::Number(n) => *n,
        _ => return Err("Arguments to - must be numbers".to_string()),
    };
    
    if args.len() == 1 {
        return Ok(Expr::Number(-result));
    }
    
    for arg in &args[1..] {
        match arg {
            Expr::Number(n) => result -= n,
            _ => return Err("Arguments to - must be numbers".to_string()),
        }
    }
    Ok(Expr::Number(result))
}

pub fn multiply(args: Vec<Expr>) -> Result<Expr, String> {
    let mut product = 1.0;
    for arg in args {
        match arg {
            Expr::Number(n) => product *= n,
            _ => return Err("Arguments to * must be numbers".to_string()),
        }
    }
    Ok(Expr::Number(product))
}

pub fn divide(args: Vec<Expr>) -> Result<Expr, String> {
    if args.is_empty() {
        return Err("/ requires at least one argument".to_string());
    }
    
    let mut result = match &args[0] {
        Expr::Number(n) => *n,
        _ => return Err("Arguments to / must be numbers".to_string()),
    };
    
    if args.len() == 1 {
        if result == 0.0 {
            return Err("Division by zero".to_string());
        }
        return Ok(Expr::Number(1.0 / result));
    }
    
    for arg in &args[1..] {
        match arg {
            Expr::Number(n) => {
                if *n == 0.0 {
                    return Err("Division by zero".to_string());
                }
                result /= n;
            },
            _ => return Err("Arguments to / must be numbers".to_string()),
        }
    }
    Ok(Expr::Number(result))
}

pub fn equal(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() < 2 {
        return Err("= requires at least two arguments".to_string());
    }
    
    let first = &args[0];
    for arg in &args[1..] {
        if first != arg {
            return Ok(Expr::Boolean(false));
        }
    }
    Ok(Expr::Boolean(true))
}

pub fn less_than(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() < 2 {
        return Err("< requires at least two arguments".to_string());
    }
    
    for i in 0..args.len() - 1 {
        let (left, right) = (&args[i], &args[i + 1]);
        match (left, right) {
            (Expr::Number(a), Expr::Number(b)) => {
                if a >= b {
                    return Ok(Expr::Boolean(false));
                }
            }
            _ => return Err("Arguments to < must be numbers".to_string()),
        }
    }
    Ok(Expr::Boolean(true))
}

pub fn greater_than(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() < 2 {
        return Err("> requires at least two arguments".to_string());
    }
    
    for i in 0..args.len() - 1 {
        let (left, right) = (&args[i], &args[i + 1]);
        match (left, right) {
            (Expr::Number(a), Expr::Number(b)) => {
                if a <= b {
                    return Ok(Expr::Boolean(false));
                }
            }
            _ => return Err("Arguments to > must be numbers".to_string()),
        }
    }
    Ok(Expr::Boolean(true))
}

pub fn cons(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() != 2 {
        return Err("cons requires exactly two arguments".to_string());
    }
    
    let car = args[0].clone();
    let cdr = args[1].clone();
    
    match cdr {
        Expr::List(mut list) => {
            list.insert(0, car);
            Ok(Expr::List(list))
        }
        Expr::Nil => Ok(Expr::List(vec![car])),
        _ => Err("Second argument to cons must be a list or nil".to_string()),
    }
}

pub fn car(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() != 1 {
        return Err("car requires exactly one argument".to_string());
    }
    
    match &args[0] {
        Expr::List(list) => {
            if list.is_empty() {
                Err("Cannot take car of empty list".to_string())
            } else {
                Ok(list[0].clone())
            }
        }
        _ => Err("Argument to car must be a list".to_string()),
    }
}

pub fn cdr(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() != 1 {
        return Err("cdr requires exactly one argument".to_string());
    }
    
    match &args[0] {
        Expr::List(list) => {
            if list.is_empty() {
                Err("Cannot take cdr of empty list".to_string())
            } else {
                Ok(Expr::List(list[1..].to_vec()))
            }
        }
        _ => Err("Argument to cdr must be a list".to_string()),
    }
}

pub fn is_null(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() != 1 {
        return Err("null? requires exactly one argument".to_string());
    }
    
    Ok(Expr::Boolean(matches!(args[0], Expr::Nil)))
}

pub fn is_number(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() != 1 {
        return Err("number? requires exactly one argument".to_string());
    }
    
    Ok(Expr::Boolean(matches!(args[0], Expr::Number(_))))
}

pub fn is_symbol(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() != 1 {
        return Err("symbol? requires exactly one argument".to_string());
    }
    
    Ok(Expr::Boolean(matches!(args[0], Expr::Symbol(_))))
}

pub fn is_boolean(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() != 1 {
        return Err("boolean? requires exactly one argument".to_string());
    }
    
    Ok(Expr::Boolean(matches!(args[0], Expr::Boolean(_))))
}

pub fn is_list(args: Vec<Expr>) -> Result<Expr, String> {
    if args.len() != 1 {
        return Err("list? requires exactly one argument".to_string());
    }
    
    Ok(Expr::Boolean(matches!(args[0], Expr::List(_))))
}

pub fn display_help() -> Result<Expr, String> {
    let help_text = r#"
Lisp Interpreter Help
=====================

This is a simple Scheme-like interpreter with the following features:

Basic Data Types:
- Numbers: 1, 3.14, -5
- Booleans: true, false
- Strings: "hello"
- Symbols: x, hello-world
- Lists: (1 2 3), (a b c)

Arithmetic Operations:
- (+ a b c ...) - Addition
- (- a b c ...) - Subtraction
- (* a b c ...) - Multiplication
- (/ a b c ...) - Division

Comparison Operations:
- (= a b c ...) - Equality
- (< a b c ...) - Less than
- (> a b c ...) - Greater than

List Operations:
- (cons a b) - Construct a list
- (car lst) - Get first element
- (cdr lst) - Get rest of elements
- (null? x) - Check if null
- (list a b c ...) - Create a list

Type Predicates:
- (number? x) - Check if number
- (symbol? x) - Check if symbol
- (boolean? x) - Check if boolean
- (list? x) - Check if list

Control Structures:
- (if condition then-expr else-expr) - Conditional
- (define symbol value) - Define variable
- (lambda (params) body) - Create function
- (begin expr1 expr2 ...) - Execute expressions in sequence

Quoting:
- 'expr - Quote an expression (equivalent to (quote expr))
- Quoting prevents evaluation of expressions

Special Commands:
- (help) - Show this help
- Ctrl+D - Exit interpreter

Examples:
- (+ 1 2 3) => 6
- (define x 10) => x
- (if (> x 5) "big" "small") => "big"
- ((lambda (x) (* x 2)) 5) => 10
- 'hello => hello
- '(1 2 3) => (1 2 3)
"#;
    
    println!("{}", help_text);
    Ok(Expr::Nil)
}

Cargo.toml

[package]
name = "lisp-interpreter"
version = "0.1.0"
edition = "2021"

[dependencies]
rustyline = "14.0.0"

environment.rs

use std::collections::HashMap;
use crate::ast::Expr;

#[derive(Debug, Clone)]
pub struct Environment {
    vars: HashMap<String, Expr>,
    parent: Option<Box<Environment>>,
}

impl Environment {
    pub fn new() -> Self {
        Environment {
            vars: HashMap::new(),
            parent: None,
        }
    }

    pub fn new_with_parent(parent: Environment) -> Self {
        Environment {
            vars: HashMap::new(),
            parent: Some(Box::new(parent)),
        }
    }

    pub fn define(&mut self, name: String, value: Expr) {
        self.vars.insert(name, value);
    }

    pub fn get(&self, name: &str) -> Result<Expr, String> {
        if let Some(value) = self.vars.get(name) {
            Ok(value.clone())
        } else if let Some(ref parent) = self.parent {
            parent.get(name)
        } else {
            Err(format!("Variable '{}' not defined", name))
        }
    }
}

evaluator.rs

use crate::ast::Expr;
use crate::environment::Environment;
use crate::builtins;

pub fn eval(expr: Expr, env: &mut Environment) -> Result<Expr, String> {
    match expr {
        Expr::Number(_) | Expr::Boolean(_) | Expr::String(_) | Expr::Nil => Ok(expr),
        Expr::Symbol(ref name) => {
            // Check if it's a built-in function
            match name.as_str() {
                "+" | "-" | "*" | "/" | "=" | "<" | ">" | "cons" | "car" | "cdr" | 
                "null?" | "number?" | "symbol?" | "boolean?" | "list?" | "list" => {
                    // Built-in functions are handled during application
                    Ok(expr)
                }
                "help" => {
                    // Special case for help
                    builtins::display_help()?;
                    Ok(Expr::Nil)
                }
                _ => {
                    // Look up in environment
                    env.get(name)
                }
            }
        }
        Expr::List(ref list) => {
            if list.is_empty() {
                return Ok(expr);
            }
            
            // Special forms
            if let Expr::Symbol(ref head) = list[0] {
                match head.as_str() {
                    "define" => return eval_define(&list[1..], env),
                    "lambda" => return eval_lambda(&list[1..], env),
                    "if" => return eval_if(&list[1..], env),
                    "begin" => return eval_begin(&list[1..], env),
                    "quote" => return eval_quote(&list[1..]),
                    "help" => {
                        builtins::display_help()?;
                        return Ok(Expr::Nil);
                    }
                    _ => {} // Fall through to function application
                }
            }
            
            // Function application
            eval_application(list, env)
        }
        Expr::Lambda { .. } => Ok(expr),
    }
}

fn eval_define(args: &[Expr], env: &mut Environment) -> Result<Expr, String> {
    if args.len() != 2 {
        return Err("define requires exactly two arguments".to_string());
    }
    
    let name = match &args[0] {
        Expr::Symbol(name) => name.clone(),
        _ => return Err("First argument to define must be a symbol".to_string()),
    };
    
    let value = eval(args[1].clone(), env)?;
    env.define(name.clone(), value);
    Ok(Expr::Symbol(name))
}

fn eval_lambda(args: &[Expr], _env: &mut Environment) -> Result<Expr, String> {
    if args.len() != 2 {
        return Err("lambda requires exactly two arguments".to_string());
    }
    
    let params = match &args[0] {
        Expr::List(param_list) => {
            let mut params = Vec::new();
            for param in param_list {
                match param {
                    Expr::Symbol(name) => params.push(name.clone()),
                    _ => return Err("Lambda parameters must be symbols".to_string()),
                }
            }
            params
        }
        _ => return Err("First argument to lambda must be a list of parameters".to_string()),
    };
    
    let body = Box::new(args[1].clone());
    Ok(Expr::Lambda { params, body })
}

fn eval_if(args: &[Expr], env: &mut Environment) -> Result<Expr, String> {
    if args.len() < 2 || args.len() > 3 {
        return Err("if requires 2 or 3 arguments".to_string());
    }
    
    let condition = eval(args[0].clone(), env)?;
    let truthy = match condition {
        Expr::Boolean(false) | Expr::Nil => false,
        _ => true,
    };
    
    if truthy {
        eval(args[1].clone(), env)
    } else if args.len() == 3 {
        eval(args[2].clone(), env)
    } else {
        Ok(Expr::Nil)
    }
}

fn eval_begin(args: &[Expr], env: &mut Environment) -> Result<Expr, String> {
    let mut result = Expr::Nil;
    for arg in args {
        result = eval(arg.clone(), env)?;
    }
    Ok(result)
}

fn eval_quote(args: &[Expr]) -> Result<Expr, String> {
    if args.len() != 1 {
        return Err("quote requires exactly one argument".to_string());
    }
    Ok(args[0].clone())
}

fn eval_application(list: &[Expr], env: &mut Environment) -> Result<Expr, String> {
    if list.is_empty() {
        return Ok(Expr::Nil);
    }
    
    // Evaluate the function
    let func = eval(list[0].clone(), env)?;
    
    // Evaluate the arguments
    let mut args = Vec::new();
    for arg in &list[1..] {
        args.push(eval(arg.clone(), env)?);
    }
    
    // Apply the function
    match func {
        Expr::Lambda { params, body } => {
            // Create a new environment for the function call
            let mut new_env = Environment::new_with_parent(env.clone());
            
            // Bind parameters to arguments
            if params.len() != args.len() {
                return Err(format!("Expected {} arguments, got {}", params.len(), args.len()));
            }
            
            for (param, arg) in params.iter().zip(args.iter()) {
                new_env.define(param.clone(), arg.clone());
            }
            
            // Evaluate the body in the new environment
            eval(*body, &mut new_env)
        }
        Expr::Symbol(ref name) => {
            // Built-in functions
            match name.as_str() {
                "+" => builtins::add(args),
                "-" => builtins::subtract(args),
                "*" => builtins::multiply(args),
                "/" => builtins::divide(args),
                "=" => builtins::equal(args),
                "<" => builtins::less_than(args),
                ">" => builtins::greater_than(args),
                "cons" => builtins::cons(args),
                "car" => builtins::car(args),
                "cdr" => builtins::cdr(args),
                "null?" => builtins::is_null(args),
                "number?" => builtins::is_number(args),
                "symbol?" => builtins::is_symbol(args),
                "boolean?" => builtins::is_boolean(args),
                "list?" => builtins::is_list(args),
                "list" => Ok(Expr::List(args)),
                _ => Err(format!("Unknown function: {}", name)),
            }
        }
        _ => Err("Cannot apply non-function".to_string()),
    }
}

main.rs

mod ast;
mod environment;
mod parser;
mod builtins;
mod evaluator;

use rustyline::error::ReadlineError;
use rustyline::DefaultEditor;
use environment::Environment;
use parser::parse;
use evaluator::eval;

fn main() {
    println!("Lisp Interpreter");
    println!("Type (help) for help, Ctrl+D to exit");
    
    // Create a new environment
    let mut env = Environment::new();
    
    // Create a new readline editor
    let mut rl = DefaultEditor::new().expect("Failed to create readline editor");
    
    loop {
        let readline = rl.readline("lisp> ");
        match readline {
            Ok(line) => {
                // Add line to history
                rl.add_history_entry(line.as_str()).expect("Failed to add history entry");
                
                // Skip empty lines
                if line.trim().is_empty() {
                    continue;
                }
                
                // Parse and evaluate the expression
                match parse(&line) {
                    Ok(expr) => {
                        match eval(expr, &mut env) {
                            Ok(result) => {
                                if !result.is_nil() {
                                    println!("{}", result);
                                }
                            }
                            Err(error) => {
                                eprintln!("Error: {}", error);
                            }
                        }
                    }
                    Err(error) => {
                        eprintln!("Parse Error: {}", error);
                    }
                }
            }
            Err(ReadlineError::Interrupted) => {
                // Ctrl+C - continue
                println!("^C");
                continue;
            }
            Err(ReadlineError::Eof) => {
                // Ctrl+D - exit
                println!();
                break;
            }
            Err(err) => {
                eprintln!("Error: {:?}", err);
                break;
            }
        }
    }
}

parser.rs

use crate::ast::Expr;

#[derive(Debug)]
pub enum ParseError {
    UnexpectedEOF,
    UnexpectedChar(char),
}

impl std::fmt::Display for ParseError {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            ParseError::UnexpectedEOF => write!(f, "Unexpected end of input"),
            ParseError::UnexpectedChar(c) => write!(f, "Unexpected character: {}", c),
        }
    }
}

impl std::error::Error for ParseError {}

pub fn parse(input: &str) -> Result<Expr, ParseError> {
    let tokens = tokenize(input)?;
    let (expr, _) = parse_expr(&tokens, 0)?;
    Ok(expr)
}

fn tokenize(input: &str) -> Result<Vec<String>, ParseError> {
    let mut tokens = Vec::new();
    let mut chars = input.chars().peekable();
    
    while let Some(ch) = chars.next() {
        match ch {
            ' ' | '\n' | '\t' | '\r' => {
                continue;
            }
            '(' | ')' | '\'' => {
                tokens.push(ch.to_string());
            }
            '"' => {
                let mut string = String::new();
                string.push(ch);
                
                while let Some(next_ch) = chars.next() {
                    string.push(next_ch);
                    if next_ch == '"' {
                        break;
                    }
                }
                tokens.push(string);
            }
            ';' => {
                // Comment - skip to end of line
                while let Some(next_ch) = chars.next() {
                    if next_ch == '\n' {
                        break;
                    }
                }
            }
            _ => {
                let mut token = String::new();
                token.push(ch);
                
                while let Some(&next_ch) = chars.peek() {
                    if next_ch == ' ' || next_ch == '\n' || next_ch == '\t' || next_ch == '\r' 
                        || next_ch == '(' || next_ch == ')' || next_ch == '\'' {
                        break;
                    }
                    token.push(next_ch);
                    chars.next();
                }
                tokens.push(token);
            }
        }
    }
    
    Ok(tokens)
}

fn parse_expr(tokens: &[String], pos: usize) -> Result<(Expr, usize), ParseError> {
    if pos >= tokens.len() {
        return Err(ParseError::UnexpectedEOF);
    }
    
    let token = &tokens[pos];
    
    match token.as_str() {
        "(" => {
            let mut exprs = Vec::new();
            let mut current_pos = pos + 1;
            
            while current_pos < tokens.len() && tokens[current_pos] != ")" {
                let (expr, next_pos) = parse_expr(tokens, current_pos)?;
                exprs.push(expr);
                current_pos = next_pos;
            }
            
            if current_pos >= tokens.len() {
                Err(ParseError::UnexpectedEOF)
            } else {
                Ok((Expr::List(exprs), current_pos + 1))
            }
        }
        "'" => {
            // Quote syntax
            let (expr, next_pos) = parse_expr(tokens, pos + 1)?;
            Ok((Expr::List(vec![Expr::Symbol("quote".to_string()), expr]), next_pos))
        }
        ")" => Err(ParseError::UnexpectedChar(')')),
        "nil" => Ok((Expr::Nil, pos + 1)),
        "true" => Ok((Expr::Boolean(true), pos + 1)),
        "false" => Ok((Expr::Boolean(false), pos + 1)),
        _ => {
            if token.starts_with('"') && token.ends_with('"') && token.len() > 1 {
                // String literal
                Ok((Expr::String(token[1..token.len()-1].to_string()), pos + 1))
            } else if let Ok(num) = token.parse::<f64>() {
                // Number
                Ok((Expr::Number(num), pos + 1))
            } else {
                // Symbol
                Ok((Expr::Symbol(token.clone()), pos + 1))
            }
        }
    }
}

test.lisp

;; Test arithmetic operations
(+ 1 2 3)
(- 10 3 2)
(* 2 3 4)
(/ 20 2 5)

;; Test comparisons
(= 5 5)
(< 3 5)
(> 7 2)

;; Test list operations
(cons 1 '(2 3))
(car '(1 2 3))
(cdr '(1 2 3))
(list 1 2 3)

;; Test type predicates
(number? 42)
(symbol? 'hello)
(boolean? true)
(list? '(1 2 3))
(null? '())

;; Test quoting
'hello
'(1 2 3)

;; Test string
"hello"

;; Test lambda and function application
((lambda (x) (* x 2)) 5)

;; Test define and variable reference
(define x 10)
x

;; Test if expression
(if (> x 5) "big" "small")

;; Test begin
(begin 1 2 3)