Posted at

((200行で)作る(Lisp)インタプリタ)

More than 5 years have passed since last update.

Lispの勉強がてらCoffeeScriptで作ってみました。

仕様は http://ja.wikipedia.org/wiki/LISPhttp://ja.wikipedia.org/wiki/純LISP を参考にググりながらやったので、違うところがあるかもしれません。

ソースは https://github.com/long-long-float/lisp-js/tree/limit200 で、 http://long-long-float.github.io/lisp-js/index.html で実際に動かすことができます。

class Symbol

constructor: (@name) ->
toString: -> @name

class Nil
toString: -> 'nil'
nil = new Nil
class T
toString: -> 't'
t = new T

class List
constructor: (@values) ->
toString: -> "(#{@values.map((v) -> v.toString()).join(' ')})"

class CallFun
constructor: (@funname, @args) ->
toString: -> "(#{@funname} #{@values.map((v) -> v.toString()).join(' ')})"

SF_NAMES = ['cond', 'quote', 'lambda', 'defun']
class SpecialForm
constructor: (@name, @args) ->
toString: -> "(#{@name} #{@args.map((v) -> v.toString()).join(' ')})"

class Lambda
constructor: (@params, @body) ->

class Environment
constructor: (@variables) ->
get: (name) ->
val = @variables[name]
throw "undefined #{name}" unless val
return val
set: (name, val) -> @variables[name] = val

isAtom = (val) ->
typeof val == 'string' or typeof val == 'number' or
val instanceof Nil or val instanceof T

envstack = []
currentEnv = ->
throw "envstack is empty" unless envstack.length > 0
envstack[envstack.length - 1]

class @Parser
skip: ->
@pos++ while @code[@pos]?.match /[ \r\n\t]/

isEOF: ->
@pos == @code.length

expects: (pattern, throwing = false) ->
valid = @code[@pos] && (pattern instanceof RegExp and pattern.test @code[@pos]) || pattern == @code[@pos...@pos + pattern.length]
if !valid && throwing
throw "unexpected \"#{@code[@pos]}\", expects \"#{pattern}\""

return valid

forwards: (pattern) ->
@expects pattern, true
@code[@pos]
@pos += if pattern instanceof RegExp then 1 else pattern.length

forwards_if: (pattern) ->
@forwards pattern if @expects pattern

atom: ->
#number
if @expects /[0-9]/
num = ''
num += @code[@pos++] while @expects /[0-9]/
return parseInt(num)

#string
if @forwards_if '"'
str = ''
str += @code[@pos++] until @expects '"'
@forwards '"'
return str

return nil if @forwards_if 'nil'
return t if @forwards_if 't'

#var
return new Symbol(@symbol())

symbol: ->
ret = ''
ret += @code[@pos++] while @expects /[\w!#$%&=-~^|*+<>?_]/
return ret

list: ->
@forwards '('
values = []
until @expects(')') or @isEOF()
values.push @expr()
@skip()
@forwards ')'
return new List(values)

call_fun: ->
@forwards '('
args = []
funname = @expr()

isSF = SF_NAMES.indexOf(funname.name) != -1
until @expects(')') or @isEOF()
@skip()
args.push @expr(isSF)

@forwards ')'

klass = if isSF then SpecialForm else CallFun
return new klass(funname, args)

expr: (isSF) ->
if @expects("'") or isSF #value
@forwards "'" unless isSF
if @expects '(' #list
return @list()
else #atom
return @atom()
else if @expects '(' #calling function or special form
return @call_fun()
else #atom
return @atom()

program: ->
ret = []
until @isEOF()
@skip()
ret.push @expr()
return ret

parse: (@code) ->
@pos = 0
@program()

class Evaluator
exec_lambda: (lambda, args) ->
envstack.push new Environment(lambda.params.values.reduce(
((env, param, index) -> env[param.name] = args[index]; env), {}))
[name, args...] = lambda.body.values
ret = @eval_expr(new CallFun(name, args))
envstack.pop()
return ret

eval_expr: (expr) ->
switch expr.constructor.name
when 'SpecialForm'
args = expr.args
{
'cond': => args.filter((arg) => !(@eval_expr(arg.values[0]) instanceof Nil))[0]?.values[1] || nil
'quote': -> args[0]
'lambda': -> new Lambda(args[0], args[1])
'defun': -> currentEnv().set(args[0].name, new Lambda(args[1], args[2]))
}[expr.name.name]()

when 'CallFun'
args = expr.args.map (arg) => @eval_expr(arg)
funname = if expr.funname instanceof SpecialForm then @eval_expr(expr.funname) else expr.funname
switch funname.constructor.name
when 'Lambda'
@exec_lambda(funname)
when 'Symbol'
funcs = {
'+': -> args.reduce(((sum, n) -> sum + n), 0),
'car': -> args[0].values[0]
'cdr': -> new List args[0].values[1..]
'cons': -> new List [args[0], args[1].values...]
'eq': -> if args[0] == args[1] then t else nil
'atom': -> if isAtom(args[0]) then t else nil
}
if funs = funcs[funname.name]
funs()
else
if lambda = currentEnv().get(funname.name)
@exec_lambda(lambda, args)
else
throw "undefined function : #{funname.name}"
else
throw "#{JSON.stringify(funname)}(#{funname.constructor.name}) is not a function"
when 'Symbol'
currentEnv().get(expr.name)
else
expr

eval: (ast) ->
envstack.push new Environment({})
ast.map((expr) => @eval_expr(expr)).pop().toString()

class @Lisp
@eval: (code) ->
ast = (new Parser).parse(code)
{ast: ast, body: (new Evaluator).eval(ast)}

#support script tag
$ ->
$('script[type="text/lisp"]').each ->
Lisp.eval $(this).text()


説明

今回は勉強目的だったのでパーサーは手書きしました。再帰下降パーサーです。Parserクラスがこの役割を担っています。内部表現としてSymbol, Nil等のクラスを作りました。

内部表現に変換したらEvaluatorクラスが評価します。再帰で普通にやっているだけです。


短くするために

きりのいい200行にするためにやったこと

この時点で、247行


何度も登場する部分を関数として抽出する

基本中の基本ですね。

if @expects xxx

@forwards xxx
#...

が結構多かったので、forwards_ifを作って、

if @forwards_if xxx

#...

に書き換えました。ついでに、後置ifに置き換えました。

#nil

if @expects 'nil'
@forwards_str 'nil'
return nil

return nil if @forwards_if 'nil'

にしました。

この時点で、221行


Switch文 -> functionを値としたオブジェクト

switch文は行数を食うという事が分かりました。具体的には、

switch x

when 'hoge'
console.log 'hoge~'
when 'piyo'
console.log 'piyo~'
when 'foo'
console.log 'foo~'

{

hoge: -> console.log 'hoge~'
piyo: -> console.log 'piyo~'
foo -> console.log 'foo~'
}[x]()

にしました。whenの数だけ行数が減ります。

あとconsの実装を

newList = args[1].values[..]

newList.unshift(args[0])
new List newList

から

new List [args[0], args[1].values...]

に書き換えました。CoffeeScriptはこういう便利な構文が多いですね!

この時点で、204行


mapを使う

for expr in ast

ret = @eval_expr(expr)
return ret.toString()

ast.map((expr) => @eval_expr(expr)).pop().toString()

にした。配列の末尾をとるメソッドが見当たらなかったのでpopをつかいました。ここでついに200行!


感想

処理系としては最低限だが、思ったよりあっさりできました。特にパーサーを手書きで書いたのは初めてだったのですが、特につまることなくできてしまいました。ということで、初めて作る処理系としてLispを勧めてみたいと思いました。

パーサーを実装してからみつけたのですが、((Pythonで) 書く (Lisp) インタプリタ)はわずか90行で実装しています。ソースを見るとパースはスペースで分割しているみたいです。賢い!