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

  • 22
    いいね
  • 2
    コメント
この記事は最終更新日から1年以上が経過しています。

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行で実装しています。ソースを見るとパースはスペースで分割しているみたいです。賢い!