LoginSignup
26

More than 5 years have passed since last update.

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

Posted at

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
26