Lisp in V
Published .. 24-06-2024
Type ....... article
Tags ....... v, lisp
Type ....... article
Tags ....... v, lisp
Here are a Lisp implemented in V.
I needed to try to make some code with some complexity, and try out sum types in V.
The implementation takes its inspiration in Peter Norvigs Lispy interpreter. When i learned Python some 15 years ago i really likes how easy it was to read. But after a few years with Go, i really miss the types. When i read a Python function it's not emidietly clear what types the argument has and which type the function returns. V, like Go, is a typed language and it makes it more readable, but also limits what you can do, so this is not a total clone of Lispy.
You can start the interpreter like this:
v run . exec "(prog (define test (lambda (n) (* 2 n))) (test 10))"
Here are the V code:
module main
import os
import strconv
import arrays
import cli
type LispValue = Function | List | Nil | Number | NumberFloat | NumberInt | Symbol
fn (n LispValue) str() string {
match n {
Number {
return '${n.str}'
}
NumberInt {
return '${n.value}'
}
NumberFloat {
return '${n.value:0.3f}'
}
Symbol {
return '${n.name}'
}
List {
mut l := []string{}
for i in n.values {
l << i.str()
}
return '(${l.join(' ')})'
}
Function {
return 'FN'
}
Nil {
if n.error != '' {
return 'NIL(${n.error})'
}
return 'NIL'
}
}
}
fn (n LispValue) f64() f64 {
match n {
NumberInt {
return f64(n.value)
}
NumberFloat {
return n.value
}
else {}
}
return 0
}
type Number = NumberFloat | NumberInt
fn (n Number) str() string {
match n {
NumberInt {
return '${n.value}'
}
NumberFloat {
return '${n.value:0.3f}'
}
}
}
// fn (n Number) f64() f64 {
// match n {
// NumberInt {
// return f64(n.value)
// }
// NumberFloat {
// return n.value
// }
// }
// }
struct NumberInt {
value i64
}
struct NumberFloat {
value f64
}
struct Symbol {
name string
}
struct List {
mut:
values []LispValue
}
fn (lst List) same_type() bool {
if lst.values.len == 0 {
return true
}
tn := lst.values[0].type_name()
for i in lst.values[1..] {
if i.type_name() != tn {
return false
}
}
return true
}
type FunctionFunc = fn (args List) LispValue
struct Function {
func ?FunctionFunc
}
struct Nil {
// nil is the lisp false value, and here it can also carry an error value
error string
}
fn new_lispvalue(token string) LispValue {
if token == '' {
return Nil{
error: 'empty token'
}
} else {
if token.contains_only('+-*/') {
return Symbol{token}
}
if token.contains_only('-0123456789') {
if i := strconv.parse_int(token, 10, 64) {
// return Number{
// tpe: .integer
// i_value: i
// }
return NumberInt{i}
}
}
if token.contains_only('-0123456789.') {
if f := strconv.atof64(token) {
// return Number{
// tpe: .float
// f_value: f
// }
return NumberFloat{f}
}
}
return Symbol{token}
}
}
fn parse(program string) LispValue {
// "Read a Scheme expression from a string."
mut tokens := tokenize(program)
// println('TOKENS : ${tokens}')
return read_from_tokens(mut tokens)
}
fn tokenize(program string) []string {
// Convert a string into a list of tokens.
return program.replace('(', ' ( ').replace(')', ' ) ').split(' ').filter(fn (t string) bool {
return t != ''
})
}
fn pop(tokens []string) !(string, []string) {
if tokens.len == 0 {
println('unexpected EOF while reading')
return error('unable to pop')
}
t := tokens[0]
ts := tokens[1..].clone()
return t, ts
}
fn read_from_tokens(mut tokens []string) LispValue {
// println('read_from_tokens : ${tokens} , ${tokens.len}')
mut token := ''
token, tokens = pop(tokens) or { return Nil{
error: 'unable to pop'
} }
if token == '(' {
mut l := List{}
// println('new list : ${l}')
if tokens.len > 0 {
mut loop_break := true
for loop_break {
l.values << read_from_tokens(mut tokens)
loop_break = tokens.len > 0 && tokens[0] != ')'
}
}
_, tokens = pop(tokens) or { return Nil{
error: 'unable to pop'
} }
// println('return1 : ${l} ')
return l
} else if token == ')' {
// panic('unexpected )')
return Nil{
error: 'unexpected )'
}
} else {
// println('return2 : ${token} ')
return new_lispvalue(token)
}
}
// environment
struct Environment {
mut:
items map[string]LispValue
}
// fn (env Environment) find(name string) Environment {
// // println('env.find ${name}')
// if name in env.items {
// // println('found')
// return env
// }
// // todo: return outer
// return env
// }
fn lisp_bool(val bool) LispValue {
if val {
return Symbol{
name: 'T'
}
}
return Nil{}
}
fn op_reduce(op fn (a f64, b f64) f64) fn (List) LispValue {
return fn [op] (args List) LispValue {
// println(args.values)
res := arrays.reduce[LispValue](args.values, fn [op] (acc LispValue, elem LispValue) LispValue {
return NumberFloat{ value: op(acc.f64(), elem.f64()) }
}) or { return NumberInt{
value: 0
} }
return res
}
}
fn op_less(args List) LispValue {
a := args.values[0].f64() // as NumberInt
b := args.values[1].f64() // as NumberInt
// println('${a} < ${b}')
return lisp_bool(a < b)
}
fn op_greater(args List) LispValue {
a := args.values[0].f64() // as NumberInt
b := args.values[1].f64() // as NumberInt
// println('${a} > ${b}')
return lisp_bool(a > b)
}
fn op_eq(args List) LispValue {
a := args.values[0].f64() // as NumberInt
b := args.values[1].f64() // as NumberInt
return lisp_bool(a == b)
}
fn standard_env() Environment {
mut e := Environment{}
e.items['+'] = Function{
func: op_reduce(fn (a f64, b f64) f64 {
return a + b
})
}
e.items['-'] = Function{
func: op_reduce(fn (a f64, b f64) f64 {
return a - b
})
}
e.items['*'] = Function{
func: op_reduce(fn (a f64, b f64) f64 {
return a * b
})
}
e.items['/'] = Function{
func: op_reduce(fn (a f64, b f64) f64 {
return a / b
})
}
e.items['>'] = Function{
func: op_greater
}
e.items['<'] = Function{
func: op_less
}
e.items['='] = Function{
func: op_eq
}
return e
}
// eval
fn eval(x LispValue, mut env Environment) LispValue {
match x {
Symbol {
return env.items[x.name] or {
return Nil{
error: 'unable to eval missing ${x.name}'
}
}
}
List {
// Continue
}
else {
// it's either : Function | Nil | NumberFloat | NumberInt
return x
}
}
// we have a List
lst := x as List
first := lst.values[0]
if first is Symbol {
rest := lst.values[1..]
match first.name {
'quote' {
return List{
values: rest
}
}
'if' {
match eval(rest[0], mut env) {
Nil { // nil is false
return eval(rest[2], mut env)
}
else { // everything else is true
return eval(rest[1], mut env)
}
}
}
'define' {
name := rest[0] as Symbol
env.items[name.name] = eval(rest[1], mut env)
return Nil{}
}
'set!' {
// set value of predefined symbol
name := rest[0] as Symbol
if name.name in env.items {
env.items[name.name] = rest[1]
return rest[1]
} else {
return Symbol{
name: 'error unknown '
}
}
}
'lambda' {
// println(' -- lambda -- ')
params := rest[0]
if params is List {
body := rest[1..]
lbody := body[0] as List
f := Function{
func: fn [mut env, params, lbody] (args List) LispValue {
// println('lambda env ::: ${env}')
// mut e := env // standard_env()
if params is List {
for idx, p in params.values {
if p is Symbol {
env.items[p.name] = args.values[idx]
} else {
// println('!!!!!!!!!! param should be symbol')
return Nil{
error: 'param should be symbol'
}
}
}
}
// println('going to eval lambda body : ${lbody} (with env: ${env})')
res := eval(lbody, mut env)
// println('res : ${res} , env : ${env}')
// env = e
return res
}
}
return f
} else {
println('params not a list ${params}')
return Symbol{
name: '?'
}
}
}
'prog' {
// run elements in form sequentially
mut r := new_lispvalue('0')
for p in rest {
r = eval(p, mut env)
}
return r
}
'int' {
return NumberInt{
value: i64(eval(rest[0], mut env).f64())
}
}
else {
// println(' -- proc -- ')
// println('env : ${env}')
proc := eval(first, mut env)
mut args := List{}
for arg in rest {
args.values << eval(arg, mut env)
}
// println('${first.name} about to be called with args : ${args.values}')
if proc is Function {
f := proc.func or { panic('no func!!!') }
res := f(args)
// println('${first.name} returned with res : ${res} and env after is: ${env}')
return res
} else {
// println('!!!!!!!!!!!! error missing function')
return Symbol{
name: 'error missing function ${first.name}'
}
}
}
}
} else {
return Symbol{
name: 'error first element in form is not a symbol'
}
}
}
// repl
fn repl(prompt string) {
mut global_env := standard_env()
for (true) {
x := eval(parse(os.input(prompt)), mut global_env)
println('${x}')
}
}
fn main() {
mut app := cli.Command{
name: 'vlisp'
description: 'a lisp-like language'
execute: fn (cmd cli.Command) ! {
repl('vlisp> ')
return
}
commands: [
cli.Command{
name: 'exec'
required_args: 1
execute: fn (cmd cli.Command) ! {
mut global_env := standard_env()
for c in cmd.args {
println('vlisp> ${c}')
println(eval(parse(c), mut global_env))
}
return
}
},
]
}
app.setup()
app.parse(os.args)
}