Lispの勉強がてらCoffeeScriptで作ってみました。
仕様は http://ja.wikipedia.org/wiki/LISP や http://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行で実装しています。ソースを見るとパースはスペースで分割しているみたいです。賢い！