A Lisp-dialect written in Go

Overview

Lispy ✏️

Intro

Lispy is a programming language that is inspired by Scheme and Clojure. It's a simple Lisp-dialect I built to better understand Lisp and, more generally, functional programming.

For a journal documenting my process from not knowing what Lisp was, to building this language, refer to this blog post I wrote.

Here's a taste for what it can do

example

You can tour the language and run it in the browser here

tour

You can find the source code for this sandbox here.

What Lispy supports

  • Basic arithmetic operations (+, -, *, /, %, #)
    • (# a b) means raise a to the power of b
  • Relational operators (>, <, >=, <=, =) and logical operators (and, or, notå)
  • Bindings to variables and state with define, and let for local binding or lexical scope
  • Reading input from the user via readline and string concatenation via str
  • Conditionals via if, when, and cond
  • Lambdas or anonymous functions via fn, functions via define
  • Reading Lispy code from a file
  • Macros (quasiquote, threading via ->. ->>, and a host of other ones)
  • Tail call optimization
  • Lists with a core library that supports functional operations like map, reduce, range and several more
  • Hash maps
  • A meta-circular interpreter to run a (more barebones) version of itself at tests/interpreter.lpy

High Level Overview

Lispy is written as a tree-walk interpreter in Go with a recursive-descent parser. It also has a separate lexer, although most Lisp dialects are simple enough to parse that the lexing and parsing can be combined into one stage.

Because Lispy is interpreted, not compiled, it does not have a separate macro-expansion stage (that would typically be done before code is evaluated). Instead, Lispy handles macros as special functions, which it evaluates twice: once to generate the syntax of the code, and the second to run this generated syntax (as a macro would).

The interpreter code can be found at pkg/lispy/, the integration tests can be found at tests/ and the main Lispy library at lib/lispy.lpy. Here's a short sample of lispy in action:

(each (seq 18)
    (fn [x] 
        (cond
            (and (divisible? x 3) (divisible? x 5)) "FizzBuzz!"
            (divisible? x 3) "Fizz"
            (divisible? x 5) "Buzz"
            (true) x
        )
    )
)

Under The Hood

Under the hood, Lispy implements a high-level S-expression interface with specific structures to reprsent lists, arrays, symbols, integers, and floats. Lists in Lispy are implemented as linked lists of cons cells, from which we derive the axioms of car, cdr, and cons. Everything else is built on top of these building blocks. Lispy also implements a single environment for variables and functions - it does not keep separate namespaces for them. The environment is the core backbone of the interpreter which allows us to bind values to variables and functions. Lispy uses Go's recursive calls as its native stack and does not implement a separate stack frame. Each function call gets its own environment with a pointer to the parent environment. Most Lispy programs are not going to be incredibly long, thus for the sake of significant speed gains, Lispy copies over all of the data from the parent environment into the current environment. Although this is less memory-efficient and probably would not be used for a production-ready language, it made the interpreter at least 10x faster (instead of having to recurse up to parent environments to resolve a function/variable declaration) when I tested it.

Lispy Library

Lispy implements a core library (under lib/lispy.lpy) that builds on top of the core functionality to offer a rich variety of features.

Tail call optimization

Lispy also implements tail call optimization. Since Lispy uses Go's call stack and does not implement its own, it performs tail call elimination or optimization similar to Ink. It does this by expanding a set of recursive function calls into a flat for loop structure that allows us to reuse the same call stack and (theoretically) recurse infinitely without causing a stack overflow.

Running Lispy

To run Lispy, you have a couple of options.

  1. The easiest way is to run it directly in the browser with a sandbox I built.
  2. If you want to experiment with it more freely on your local device, you can launch a repl by running make in the outer directory
  3. If you want to run a specific file, you can run ./run <path/to/file>.
  • For context, run is an executable with a small script to run a passed in file. Note don't include the <> when passing a path (I included it for clarity).
  • You can also add the Lispy executable to your $PATH which will allow you to run lispy <path/to/file> in the terminal. If you're on Linux, you can do this with
$ make build
$ sudo ln -s <full path to ./lispy> usr/local/bin

For context, this creates a symlink (which is just a shortcut or path to a different file) which makes the ./lispy executable available in your path so you can just use lispy instead ./lispy

To Improve

  1. Lispy doesn't handle errors very gracefully, especially in the code sandbox. It's also less strict about code that is incorrect in some way or another, meaning it may still run code that should probably raise an error.
  2. Lispy could probably be a little bit faster with a couple more optimizations, but it's already surprisingly fast. As proof, try running tests/test4.lpy :) I think the speed is more indicative of how far modern computers have come than brilliant language design by me.

Helpful Resources

There were many resources that proved to be invaluable over the course of this project. Here's a short snippet of them:

  1. Glisp
  2. Clojure
  3. Scheme
  4. Klisp
  5. Structure and Interpretation of Computer Programs
  6. Mal
  7. Lisp in Python
  8. On Lisp
  9. Crafting Interpreters
Releases(v0.2.alpha)
Owner
Amir Bolous
CS @ Georgia Tech
Amir Bolous
Simple-lisp - A Simple Lisp Interpreter written in Go

Simple Lisp A simple Lisp interpreter written in Go. The fixed-precision-numbers

Oxygen 5 Jun 21, 2022
The interpreter for qiitan script. Yet another dialect of the Tengo language.

Qiitan は、Qiita ™️ の SNS である「Qiitadonβ」のマスコット・キャラクターです。 キーたん(Qiitan) @ Qiitadon Qiitan-go は Qiitan のファン・アプリであり、Qiita ™️ とは一切関係がありません。 Qiitan-goalpha キー

Qithub - QiitaとQiitadonとGitHubをつなげるBOT 1 Feb 6, 2022
Mini lisp interpreter written in Go.

Mini Go Lisp Mini lisp interpreter written in Go. It is implemented with reference to the d-tsuji/SDLisp repository written in Java. Support System Fu

Tsuji Daishiro 16 Nov 25, 2020
Lisp Interpreter

golisp Lisp Interpreter Usage $ golisp < foo.lisp Installation $ go get github.com/mattn/golisp/cmd/golisp Features Call Go functions. Print random in

mattn 119 Jul 14, 2022
Sabre is highly customisable, embeddable LISP engine for Go. :computer:

Sabre DEPRECATED: This repository is deprecated in favour much better slurp project and will be archived/removed soon. Sabre is highly customizable, e

Shivaprasad Bhat 28 May 23, 2021
Toy Lisp 1.5 interpreter

Lisp 1.5 To install: go get robpike.io/lisp. This is an implementation of the language defined, with sublime concision, in the first few pages of the

Rob Pike 865 Jul 29, 2022
Interactive Go interpreter and debugger with REPL, Eval, generics and Lisp-like macros

gomacro - interactive Go interpreter and debugger with generics and macros gomacro is an almost complete Go interpreter, implemented in pure Go. It of

Massimiliano Ghilardi 1.9k Aug 1, 2022
Scriptable interpreter written in golang

Anko Anko is a scriptable interpreter written in Go. (Picture licensed under CC BY-SA 3.0, photo by Ocdp) Usage Example - Embedded package main impor

mattn 1.3k Aug 1, 2022
Gentee - script programming language for automation. It uses VM and compiler written in Go (Golang).

Gentee script programming language Gentee is a free open source script programming language. The Gentee programming language is designed to create scr

Alexey Krivonogov 95 Jul 22, 2022
A POSIX-compliant AWK interpreter written in Go

GoAWK: an AWK interpreter written in Go AWK is a fascinating text-processing language, and somehow after reading the delightfully-terse The AWK Progra

Ben Hoyt 1.6k Jul 31, 2022
A BASIC interpreter written in golang.

05 PRINT "Index" 10 PRINT "GOBASIC!" 20 PRINT "Limitations" Arrays Line Numbers IF Statement DATA / READ Statements Builtin Functions Types 30 PRINT "

Steve Kemp 280 Jul 14, 2022
A basic Forth parser written in Go.

GoForth ======= I got really interested in Forth and thus I began making a parser, of sorts, in Go. Though I don't intend for it to catch on, it's st

Artem Titoulenko 21 Mar 1, 2022
A customisable virtual machine written in Go

== About GoLightly == GoLightly is a lightweight virtual machine library implemented in Go, designed for flexibility and reuse. Traditionally popular

Eleanor McHugh 216 Aug 6, 2022
A simple virtual machine - compiler & interpreter - written in golang

go.vm Installation Build without Go Modules (Go before 1.11) Build with Go Modules (Go 1.11 or higher) Usage Opcodes Notes The compiler The interprete

Steve Kemp 235 Jul 29, 2022
Genetic Algorithms library written in Go / golang

Description Genetic Algorithms for Go/Golang Install $ go install git://github.com/thoj/go-galib.git Compiling examples: $ git clone git://github.com

Thomas Jager 192 May 26, 2022
Chip-8 emulator written in Go

Welcome to Chippy ?? Chippy is a CHIP-8 emulator that runs Chip-8 public domain roms. The Chip 8 actually never was a real system, but more like a vir

Bradford Lamson-Scribner 56 Jun 10, 2022
❄️ Elsa is a minimal, fast and secure runtime for JavaScript and TypeScript written in Go

Elsa Elsa is a minimal, fast and secure runtime for JavaScript and TypeScript written in Go, leveraging the power from QuickJS. Features URL based imp

Elsa 2.6k Jul 29, 2022
🏃 An x86-64 assembler written in Go.

asm An x86-64 assembler written in Go. It is used by the Q programming language for machine code generation. Architectures Linux x86-64 (ELF binaries)

Eduard Urbach 69 May 10, 2022
Expr – a tiny stack-based virtual machine written in Go

Expr – a tiny stack-based virtual machine written in Go The executor is designed to interpret a simple expression language and it's useful in delegati

Anthony Regeda 25 Apr 10, 2022