A complete interpreter implementation for the BananaScript programming language, built from scratch in Go. This project follows the excellent book "Writing an Interpreter in Go" by Thorsten Ball.
- Lexical Analysis: Complete tokenization of BananaScript source code
- Parsing: Recursive descent parser with operator precedence
- AST Generation: Abstract Syntax Tree construction and traversal
- Expression Evaluation: Support for arithmetic, boolean, and comparison operations
- Control Flow: If-else expressions with proper scoping
- Variable Binding: Let statements and assignment expressions with environment-based variable storage
- Function Definitions: First-class functions with lexical scoping and closures
- Function Calls: Support for function invocation with arguments
- Return Statements: Early returns with proper value propagation
- Built-in Functions: Core functions like
len,first,last,rest,push,print - Array Support: Array literals, indexing, and manipulation
- String Operations: String literals and concatenation
- Error Handling: Comprehensive error reporting and propagation
- Comments: Single-line comment support with
// - REPL: Interactive Read-Eval-Print Loop for live coding
- Web API: HTTP API server for executing BananaScript code
- CI/CD Pipeline: Automated testing with GitHub Actions
// Variables and Basic Operations
let x = 5;
let y = 10;
let name = "BananaScript";
// Variable Assignment
x = 15; // Update existing variable
// Functions with Closures
let makeCounter = fn() {
let count = 0;
fn() {
count = count + 1;
count;
};
};
let counter = makeCounter();
counter(); // 1
counter(); // 2
// Recursive Functions
let fibonacci = fn(n) {
if (n < 2) {
n;
} else {
fibonacci(n - 1) + fibonacci(n - 2);
}
};
// Higher-Order Functions
let map = fn(arr, f) {
let result = [];
let iter = fn(arr, accumulated) {
if (len(arr) == 0) {
accumulated;
} else {
iter(rest(arr), push(accumulated, f(first(arr))));
}
};
iter(arr, result);
};
// Array Processing
let numbers = [1, 2, 3, 4, 5];
let doubled = map(numbers, fn(x) { x * 2 });
print(doubled);// Composition and Currying
let compose = fn(f, g) {
fn(x) { f(g(x)); };
};
let add = fn(x) {
fn(y) { x + y; };
};
let multiply = fn(x) {
fn(y) { x * y; };
};
let addThenDouble = compose(multiply(2), add(5));
addThenDouble(3); // (3 + 5) * 2 = 16
// Array Transformation Pipeline
let pipeline = fn(arr) {
let filter = fn(arr, predicate) {
let result = [];
let iter = fn(arr, acc) {
if (len(arr) == 0) {
acc;
} else {
let head = first(arr);
let tail = rest(arr);
if (predicate(head)) {
iter(tail, push(acc, head));
} else {
iter(tail, acc);
}
}
};
iter(arr, result);
};
let reduce = fn(arr, initial, reducer) {
let iter = fn(arr, acc) {
if (len(arr) == 0) {
acc;
} else {
iter(rest(arr), reducer(acc, first(arr)));
}
};
iter(arr, initial);
};
let isEven = fn(x) { x - (x / 2) * 2 == 0; };
let sum = fn(a, b) { a + b; };
reduce(filter(arr, isEven), 0, sum);
};
pipeline([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); // 30let estimatePi = fn(samples) {
// Note: Using a simple counter for demonstration
// Real random number generation would require additional built-ins
let insideCircle = 0;
let i = 0;
let loop = fn() {
if (i >= samples) {
return 4 * insideCircle / samples;
}
// Simplified calculation for demonstration
let x = (i * 7 + 13) % 100 / 100.0 * 2 - 1;
let y = (i * 11 + 17) % 100 / 100.0 * 2 - 1;
if (x * x + y * y <= 1) {
insideCircle = insideCircle + 1;
}
i = i + 1;
loop();
};
loop();
};
estimatePi(100); // Rough approximation of πlet asyncOperation = fn(data, callback) {
// Simulate async work with computation
let result = data * data + data;
callback(result);
};
let processData = fn(numbers) {
let results = [];
let processNext = fn(remaining) {
if (len(remaining) == 0) {
return results;
}
let current = first(remaining);
asyncOperation(current, fn(result) {
results = push(results, result);
processNext(rest(remaining));
});
};
processNext(numbers);
};
processData([1, 2, 3, 4, 5]); // Returns [2, 6, 12, 20, 30]// Factorial function
let factorial = fn(n) {
if (n <= 1) {
1;
} else {
n * factorial(n - 1);
}
};
// Power function
let pow = fn(base, exp) {
if (exp == 0) {
1;
} else if (exp == 1) {
base;
} else {
base * pow(base, exp - 1);
}
};
// Greatest Common Divisor
let gcd = fn(a, b) {
if (b == 0) {
a;
} else {
gcd(b, a - (a / b) * b);
}
};
// Prime checker
let isPrime = fn(n) {
if (n < 2) {
false;
} else {
let checkDivisor = fn(divisor) {
if (divisor * divisor > n) {
true;
} else if (n - (n / divisor) * divisor == 0) {
false;
} else {
checkDivisor(divisor + 1);
}
};
checkDivisor(2);
}
};
factorial(5); // 120
pow(2, 10); // 1024
gcd(48, 18); // 6
isPrime(17); // true// Bubble sort implementation
let bubbleSort = fn(arr) {
let length = len(arr);
let sorted = arr; // Copy array (simplified)
let i = 0;
while (i < length) {
let j = 0;
while (j < length - 1) {
if (sorted[j] > sorted[j + 1]) {
// Swap elements (simplified without proper swap)
let temp = sorted[j];
// Note: Direct array modification not fully supported
// This is a conceptual example
}
j = j + 1;
}
i = i + 1;
}
sorted;
};
// Find maximum in array
let findMax = fn(arr) {
if (len(arr) == 0) {
return null;
}
let max = first(arr);
let checkRest = fn(remaining) {
if (len(remaining) == 0) {
max;
} else {
let current = first(remaining);
if (current > max) {
max = current;
}
checkRest(rest(remaining));
}
};
checkRest(rest(arr));
};
findMax([3, 7, 2, 9, 1]); // 9- Go 1.22.2: Modern Go with latest language features
- Standard Library: Pure Go implementation with minimal external dependencies
- godotenv: Environment variable management for the API server
- Test-Driven Development (TDD): Comprehensive test suite with >85% coverage
- Modular Architecture: Clean separation of concerns across packages
- Interface-Driven Design: Extensible architecture using Go interfaces
- Error Handling: Idiomatic Go error handling patterns
- Memory Management: Efficient object allocation and garbage collection
- Continuous Integration: Automated testing with GitHub Actions
- Unit Tests: Individual component testing
- Integration Tests: End-to-end interpreter testing
- Parser Testing: Extensive AST validation
- Evaluator Testing: Expression and statement evaluation verification
- Error Case Testing: Comprehensive error condition coverage
- Automated CI/CD: GitHub Actions workflow for continuous testing
- Code Coverage: Minimum 80% test coverage requirement
- Code Formatting: Automated
go fmtchecks - Static Analysis:
go vetfor potential issues - Race Detection: Concurrent execution testing
- Multi-version Support: Testing on Go 1.22.x and 1.23.x
The interpreter follows a classic three-phase design:
Source Code → Lexer → Tokens → Parser → AST → Evaluator → Result
interpreter-go/
├── .github/
│ └── workflows/ # GitHub Actions CI/CD
├── api/ # HTTP API server
├── lexer/ # Tokenization and lexical analysis
├── token/ # Token definitions and utilities
├── parser/ # Recursive descent parser
├── ast/ # Abstract Syntax Tree definitions
├── object/ # Runtime object system and environment
├── evaluator/ # Tree-walking interpreter
├── repl/ # Read-Eval-Print Loop
├── main.go # REPL entry point
├── Makefile # Build automation
└── index.html # Web interface for API
- Character-by-character source code scanning
- Token recognition and generation
- Support for keywords, operators, and delimiters
- Unicode-aware string processing
- Recursive descent parsing algorithm
- Operator precedence handling
- AST node construction
- Comprehensive error reporting
- Node interface implementation
- Expression and statement types
- String representation for debugging
- Support for assignment expressions and comments
- Runtime value representation
- Environment-based variable scoping
- Type system with integers, booleans, strings, functions, arrays
- Memory-efficient object allocation
- Tree-walking interpretation
- Expression evaluation
- Control flow handling
- Function call resolution
- Built-in function implementations
# Using Go directly
go run main.go
# Using Makefile
make run
make repl # Build first, then run# Using Go directly
go run api/main.go
# Using Makefile
make run-api
make api # Build first, then run# Run all tests
go test ./...
make test
# Run tests with coverage
go test -cover ./...
make test-coverage
# Run tests with race detection
go test -race ./...
make test-race
# Run specific package tests
go test ./lexer
go test ./parser
go test ./evaluator
# Generate coverage report
make test-coverage # Creates coverage.html# Format code
go fmt ./...
make fmt
# Check for potential issues
go vet ./...
make vet
# Run both formatting and vetting
make check
# Full development workflow
make dev
# Run full test suite (same as CI)
go test -v -race -coverprofile=coverage.out ./...
make test-ci# Build REPL
make build
# Build API server
make build-api
# Build both
make build-all
# Build for multiple platforms
make build-cross
# Build optimized release
make releaseHello kitatsu! This is the BananaScript programming language!
Feel free to type in commands
>> let add = fn(x, y) { x + y; };
>> add(2, 3)
5
>> let fibonacci = fn(n) { if (n < 2) { n } else { fibonacci(n-1) + fibonacci(n-2) } };
>> fibonacci(10)
55
>> let numbers = [1, 2, 3, 4, 5];
>> print(numbers)
[1, 2, 3, 4, 5]
This project demonstrates proficiency in:
- Language Implementation: Complete interpreter construction
- Compiler Theory: Lexical analysis, parsing, and evaluation
- Go Programming: Idiomatic Go code and patterns
- Software Architecture: Clean, modular design principles
- Testing: Comprehensive test-driven development
- Data Structures: AST manipulation and environment management
- Web Development: HTTP API implementation
- DevOps: CI/CD pipeline setup and automation
- Hash/Object data structure support for key-value pairs
- Add colors to CLI output
- Implement increment/decrement operators (
++,--) - Add support for floating-point numbers
- Improve error messages with line/column numbers
- Extend multi-line comment support (
/* */) - Add string interpolation support
- Extend built-in function library
- Support Unicode characters in identifiers
- Add ternary expressions (
condition ? expr1 : expr2) - While loop constructs
- For loop constructs
- Bytecode compilation for improved performance
- Garbage collection optimizations
- Symbol table implementation
- Constant folding and dead code elimination
- Tail call optimization
- Add benchmarking tests to track performance
- Implement semantic versioning with automated releases
- Add security scanning with CodeQL
- Create multi-platform builds (Linux, macOS, Windows)
- Docker containerization
This implementation closely follows the methodology and examples from: "Writing an Interpreter in Go" by Thorsten Ball
The book provides excellent guidance on:
- Interpreter design principles
- Go-specific implementation patterns
- Testing strategies for language implementations
- Progressive development approach
While this is primarily a learning project, contributions are welcome! Please ensure:
- All tests pass (
go test ./...ormake test) - Code follows Go conventions (
go fmt,go vetormake check) - Maintain minimum 80% test coverage
- New features include comprehensive tests
- Documentation is updated accordingly
- GitHub Actions CI pipeline passes
The CI pipeline will automatically:
- Run tests on multiple Go versions
- Check code formatting and style
- Verify test coverage meets requirements
- Generate coverage reports
This project is for educational purposes, following the examples and principles from "Writing an Interpreter in Go".