lisp

README

lisp

Derived from kanaka/mal Go implementation of a Lisp interpreter. kanaka/mal Lisp is Clojure inspired.

Keeping 100% backwards compatibility with kanaka/mal. There almost 100 implementations on almost 100 languages available on repository kanaka/mal.

This derived implementation is focused on embeddability in Go projects. See lisp main for an example on how to embed it in Go code.

Requires Go 1.18.

This implementation uses chzyer/readline instead of C implented readline or libedit, making this implementation pure Go.

Changes

Changes respect to kanaka/mal:

• Using def insted of def!, try instead of try*, etc. symbols
• atom is multithread
• Tests executed using Go test library. Original implementation uses a runtest.py in Python to keep all implementations compatible. But it makes the Go development less enjoyable. Tests files are the original ones, there is simply a new runtest_test.go that substitutes the original Python script
• Some tests are actually in lisp (mal), using the macros commented in Additions section (now only the test library itself). Well, actually not many at this moment, see "Test file specs" below
• Reader regexp's are removed and substituted by an ad-hoc scanner jig/scanner
• core library moved to lib/core
• Using chzyer/readline instead of C readline for the mal REPL
• Multiline REPL
• REPL history stored in ~/.lisp_history (instead of kanaka/mal's ~/.mal-history)
• (let () A B C) returns C as Clojure let instead of A, and evaluates A, B and C
• (do) returns nil as Clojure instead of panicking
• hash-map creates maps or converts a Go object to a map if the marshaler is defined in Go for that object
• reduce-kv added
• take, take-last, drop, drop-last, subvec added

To test the implementation use:

go test ./...

go test actually validates the step*.mal files.

There are some benchmarks as well:

go test -benchmem -benchtime 5s -bench '^.+$' github.com/jig/lisp

Additions

• Debugger: prefix program name with --debug. File to debug is the sole argument supported
• Errors return line position and stack trace
• (range a b) returns a vector of integers from a to b-1
• (merge hm1 hm2) returns the merge of two hash maps, second takes precedence
• (unbase64 string), (unbase64 byteString), (str2binary string), (binary2str byteString) to deal with []byte variables
• (sleep ms) sleeps ms milliseconds
• Support of ¬ as string terminator to simplify JSON strings. Strings that start with {" and end with "} are printed using ¬, otherwise strings are printed as usual (with "). To escape a ¬ character in a ¬ delimited string you must escape it by doubling it: ¬Hello¬¬World!¬ would be printed as Hello¬World. This behaviour allows to not to have to escape " nor \ characters
• (json-decode {} ¬{"key": "value"}¬) to decode JSON to lisp hash map
• (json-encode obj) JSON encodes either a lisp structure or a go. Example: (json-encode (json-decode {} ¬{"key":"value","key1": [{"a":"b","c":"d"},2,3]}¬)). Note that lisp vectors (e.g. [1 2 3]) and lisp lists (e.g. (list 1 2 3) are both converted to JSON vectors always. Decoding a JSON vector is done on a lisp vector always though
• (hash-map-decode (new-go-object) ¬{"key": "value"}¬) to decode hash map to a Go struct if that struct has the appropiate Go marshaler
• (context (do ...)) provides a Go context. Context contents depend on Go, and might be passed to specific functions context compatible
• Test minimal library to be used with maltest interpreter (see ./cmd/maltest/ folder). See below test specs
• Project compatible with GitHub CodeSpaces. Press . on your keyboard and you are ready to deploy a CodeSpace with mal in it
• (assert expr & optional-error) asserts expression is not nil nor false, otherwise it success returning nil
• Errors are decorated with line numbers
• (rename-keys hm hmAlterKeys) as in Clojure
• (get-in m ks) to access nested values from a m map; ks must be a vector of hash map keys
• (uuid) returns an 128 bit rfc4122 random UUID
• (split string cutset) returns a lisp Vector of the elements splitted by the cutset (see ./tests/stepH_strings for examples)
• support of (hashed, unordered) sets. Only sets of strings or keywords supported. Use #{} for literal sets. Functions supported for sets: set, set?, conj, get, assoc, dissoc, contains?, empty?. meta, with-meta (see ./tests/stepA_mal and (see ./tests/stepA_mal for examples). json-encode will encode a set to a JSON array
• update, update-in and assoc-in supported for hash maps and vectors
• Go function READ_WithPreamble works like READ but supports placeholders to be filled on READ time (see ./placeholder_test.go for som samples)
• Added support for finally inside try. finally expression is evaluated for side effects only. finally is optional
• Added spew
• Added future, and future-* companion functions from Clojure
• type? returns the type name string
• go-error, unwrap and panic mapping to Go's errors.New/fmt.Errorf, Unwrap and panic respectively
• getenv, setenv and unsetenv functions for environment variables

Embed Lisp in Go code

You execute lisp from Go code and get results from it back to Go. Example from ./example_test/example_test.go:

func ExampleEVAL() {
	newEnv := env.NewEnv()

	// Load required lisp libraries
	for _, library := range []struct {
		name string
		load func(newEnv types.EnvType) error
	}{
		{"core mal", nscore.Load},
		{"core mal with input", nscore.LoadInput},
		{"command line args", nscore.LoadCmdLineArgs},
		{"core mal extended", nscoreextended.Load},
		{"assert", nsassert.Load},
	} {
		if err := library.load(newEnv); err != nil {
			log.Fatalf("Library Load Error: %v", err)
		}
	}

	// parse (READ) lisp code
	ast, err := lisp.READ(`(+ 2 2)`, nil)
	if err != nil {
		log.Fatalf("READ error: %v", err)
	}

	// eval AST
	result, err := lisp.EVAL(ast, newEnv, nil)
	if err != nil {
		log.Fatalf("EVAL error: %v", err)
	}

	// use result
	if result.(int) != 4 {
		log.Fatalf("Result check error: %v", err)
	}

	// optionally print resulting AST
	fmt.Println(lisp.PRINT(result))
	// Output: 4
}

L notation

You may generate lisp Go structures without having to parse lisp strings, by using Go L notation.

var (
    prn = S("prn")
    str = S("str")
)

// (prn (str "hello" " " "world!"))
sampleCode := L(prn, L(str, "hello", " ", "world!"))

EVAL(sampleCode, newTestEnv(), nil)

See ./helloworldlnotationexample_test.go and ./lnotation/lnotation_test.go.

Test file specs

Execute the testfile with:

$ lisp --test .

And a minimal test example sample_test.mal:

(test.suite "complete tests"
    (assert-true "2 + 2 = 4 is true" (= 4 (+ 2 2)))
    (assert-false "2 + 2 = 5 is false" (= 5 (+ 2 2)))
    (assert-throws "0 / 0 throws an error" (/ 0 0)))

Some benchmark of the implementations:

$ go test -bench ".+" -benchtime 2s

Install

cd cmd/lisp
go install

Execute REPL

lisp

Use Ctrl + D to exit Lisp REPL.

Execute lisp program

lisp helloworld.lisp

Licence

This "lisp" implementation is licensed under the MPL 2.0 (Mozilla Public License 2.0). See LICENCE for more details.

Documentation

Overview

Package lisp provides a minimal Lisp interpreter focused on embedded work in Go code, as config or as a transmission format. Lisp external libraries are loaded from the Go code, and loading them from Lisp code is not allowed (on purpose).

This interpreter is based on kanaka/mal implementation that is inspired on Clojure. It is still mostly compatible with kanaka/mal except that def!, try*, etc. symbols have been changed to def, try, etc. See ./examples/mal.lisp as a port of mal.mal

Overview of this implementation addition to kanaka/mal:

• simpler embedded use with a simple package API (mostly inherited, just code reorganisation)
• testing based on Go tooling (all python tests scripts substituted by Go tests, see ./run_test.go)
• support of Go constructors to simplify extendability
• slightly faster parsing by swapping regex implementation for a text/scanner one
• support of preamble (AKA "placeholders") to simplify parametrisation of Go functions implemented on Lisp
• easier library development (using reflect)
• simple debugger
• line numbers

Functions and file directories keep the same structure as original MAL, this is way main functions READ, EVAL and PRINT keep its all caps (non Go standard) names.

Example (ConfigInLisp)

package main

import (
	"fmt"

	"github.com/jig/lisp"
	"github.com/jig/lisp/env"
	"github.com/jig/lisp/lib/core/nscore"
	"github.com/jig/lisp/types"
)

func main() {
	ns := env.NewEnv()
	nscore.Load(ns)
	config, _ := lisp.READ(
		`{
			:sessions 10
		}`,
		types.NewCursorFile("ExampleFunctionInLisp"),
		ns,
	)

	fmt.Println("sessions:", config.(types.HashMap).Val[types.NewKeyword("sessions")])

}

Output:

sessions: 10

Example (FunctionInLisp)

package main

import (
	"context"
	"fmt"

	"github.com/jig/lisp"
	"github.com/jig/lisp/env"
	"github.com/jig/lisp/lib/core/nscore"
	"github.com/jig/lisp/lnotation"
	"github.com/jig/lisp/types"
)

func main() {
	ns := env.NewEnv()
	nscore.Load(ns)
	ast, _ := lisp.READ(
		`(fn [a] (* 10 a))`,
		types.NewCursorFile("ExampleFunctionInLisp"),
		ns,
	)

	res, _ := lisp.EVAL(context.Background(), ast, ns)
	functionInLisp := func(a int) (int, error) {
		res, err := lisp.EVAL(context.Background(), lnotation.L(res, a), ns)
		if err != nil {
			return 0, err
		}
		return res.(int), nil
	}

	result, _ := functionInLisp(3)
	fmt.Println("result:", result)

}

Output:

result: 30

Index

• Variables
• func AddPreamble(str string, placeholderMap map[string]MalType) (string, error)
• func EVAL(ctx context.Context, ast MalType, env EnvType) (res MalType, e error)
• func PRINT(ast MalType) string
• func READ(sourceCode string, cursor *Position, ns EnvType) (MalType, error)
• func READWithPreamble(str string, cursor *Position, ns EnvType) (MalType, error)
• func REPL(ctx context.Context, env EnvType, sourceCode string, cursor *Position) (MalType, error)
• func REPLWithPreamble(ctx context.Context, env EnvType, sourceCode string, cursor *Position) (MalType, error)
• func ReadEvalWithPreamble(ctx context.Context, env EnvType, sourceCode string, cursor *Position) (MalType, error)

Examples

• Package (ConfigInLisp)
• Package (FunctionInLisp)
• AddPreamble
• EVAL
• READ
• ReadEvalWithPreamble

Variables

var Stepper func(ast MalType, ns EnvType) debuggertypes.Command

Stepper is called (if not null) to stop at each step of the Lisp interpreter.

It might be used as a debugger. Look at lisp/debugger package for a simple implementation.

Functions

func AddPreamble

func AddPreamble(str string, placeholderMap map[string]MalType) (string, error)

AddPreamble combines prefix variables into a preamble to the provided source code.

Source code encoded be readed with READWithPreamble. placeholderMap must contain a map with keys being the variable names on the placeholder and the values the AST assigned to each placeholder. Value ASTs might be generated with READ or EVAL or with the [lnotation] package (most likely). Key names must contain the '$' prefix.

Example

package main

import (
	"context"
	"fmt"
	"log"

	"github.com/jig/lisp"
	"github.com/jig/lisp/env"
	"github.com/jig/lisp/lib/core/nscore"
	"github.com/jig/lisp/types"
)

func main() {
	// incrementInLisp is sample function implemented in Lisp
	result, err := incrementInLisp(2)
	if err != nil {
		log.Fatalf("eval error: %s", err)
	}
	fmt.Printf("result: %d\n", result)

}

const incrementInLispSourceCode = "(+ 1 $ARG)"

func incrementInLisp(arg int) (int, error) {
	ns := env.NewEnv()
	nscore.Load(ns) // to load '+' function

	preamble := map[string]types.MalType{
		"$ARG": arg,
	}
	sourceCode, err := lisp.AddPreamble(
		incrementInLispSourceCode,
		preamble,
	)
	if err != nil {
		return 0, err
	}
	ast, err := lisp.READWithPreamble(
		sourceCode,
		types.NewCursorFile("ExampleREAD"),
		ns,
	)
	if err != nil {
		return 0, err
	}
	result, err := lisp.EVAL(
		context.Background(),
		ast,
		ns,
	)
	if err != nil {
		return 0, err
	}
	return result.(int), nil
}

Output:

result: 3

func EVAL

func EVAL(ctx context.Context, ast MalType, env EnvType) (res MalType, e error)

EVAL evaluates an Abstract Syntaxt Tree (AST) and returns a result (a reduced AST). It requires a context that might cancel execution, and requires an environment that might be modified. AST usually is generated by READ or READWithPreamble.

Example

ns := env.NewEnv()
nscore.Load(ns) // to load '+' function

ast := LS("+", 1, 1)
result, err := lisp.EVAL(
	context.Background(),
	ast,
	ns,
)
if err != nil {
	log.Fatalf("error: %s", err)
}
fmt.Printf("result: %d\n", result)

Output:

result: 2

func PRINT

func PRINT(ast MalType) string

PRINT converts an AST to a string, suitable for printing AST might be generated by EVAL or by READ or READWithPreamble.

func READ

func READ(sourceCode string, cursor *Position, ns EnvType) (MalType, error)

READ reads Lisp source code and generates an AST that might be evaled by EVAL or printed by PRINT.

cursor and environment might be passed nil and READ will provide correct values for you. It is recommended though that cursor is initialised with a source code file identifier to provide better positioning information in case of encountering an execution error.

EnvType is required in case you expect to parse Go constructors

Example

package main

import (
	"context"
	"fmt"
	"log"

	"github.com/jig/lisp"
	"github.com/jig/lisp/env"
	"github.com/jig/lisp/lib/core/nscore"
	"github.com/jig/lisp/types"
)

func main() {
	ns := env.NewEnv()
	nscore.Load(ns) // to load '+' function

	ast, err := lisp.READ(
		"(+ 1 1)",
		types.NewCursorFile("ExampleREAD"),
		ns,
	)
	if err != nil {
		log.Fatalf("read error: %s", err)
	}
	result, err := lisp.EVAL(
		context.Background(),
		ast,
		ns,
	)
	if err != nil {
		log.Fatalf("eval error: %s", err)
	}
	fmt.Printf("result: %d\n", result)

}

Output:

result: 2

func READWithPreamble

func READWithPreamble(str string, cursor *Position, ns EnvType) (MalType, error)

READWithPreamble reads Lisp source code with preamble placeholders and generates an AST that might be evaled by EVAL or printed by PRINT.

cursor and environment might be passed nil and READ will provide correct values for you. It is recommended though that cursor is initialised with a source code file identifier to provide better positioning information in case of encountering an execution error.

EnvType is required in case you expect to parse Go constructors.

Preamble placeholders are prefix the source code and have the following format:

;; <$-prefixed-var-name> <Lisp readable expression>

For example:

;; $1 {:key "value"}
;; $NUMBER 1984
;; $EXPR1 (+ 1 1)

will create three values that will fill the placeholders in the source code. Following the example the source code might look like:

...some code...
(prn "$NUMBER is" $NUMBER)

note that the actual code to be parsed will be:

(prn "$NUMBER is" 1984)

this simplifies inserting Lisp code in Go packages and passing Go parameters to it.

Look for the "L-notation" to simplify the pass of complex Lisp structures as placeholders.

READWithPreamble is used to read code (actually decode) on transmission. Use AddPreamble when calling from Go code.

func REPL

func REPL(ctx context.Context, env EnvType, sourceCode string, cursor *Position) (MalType, error)

REPL or READ, EVAL and PRINT loop execute those three functions in sequence. (but the loop "L" actually must be executed by the caller)

func REPLWithPreamble

func REPLWithPreamble(ctx context.Context, env EnvType, sourceCode string, cursor *Position) (MalType, error)

REPLWithPreamble or READ, EVAL and PRINT loop with preamble execute those three functions in sequence. (but the loop "L" actually must be executed by the caller)

Source code might include a preamble with the values for the placeholders. See READWithPreamble

func ReadEvalWithPreamble

func ReadEvalWithPreamble(ctx context.Context, env EnvType, sourceCode string, cursor *Position) (MalType, error)

ReadEvalWithPreamble or READ and EVAL with preamble execute those three functions in sequence. (but the loop "L" actually must be executed by the caller)

Source code might include a preamble with the values for the placeholders. See READWithPreamble ReadEvalWithPreamble returns the result in AST structure.

Example

package main

import (
	"context"
	"fmt"
	"log"

	"github.com/jig/lisp"
	"github.com/jig/lisp/env"
	"github.com/jig/lisp/lib/core/nscore"
	"github.com/jig/lisp/types"
)

func main() {
	ns := env.NewEnv()
	nscore.Load(ns) // to load '+' function

	sourceCode := `;; $ARG 1
(+ 1 $ARG)`
	result, err := lisp.ReadEvalWithPreamble(
		context.Background(),
		ns,
		sourceCode,
		types.NewCursorFile("ExampleReadEvalWithPreamble"),
	)
	if err != nil {
		log.Fatalf("error: %s", err)
	}
	fmt.Printf("result: %d\n", result)

}

Output:

result: 2