((Rubyで) 書く (Lisp) インタプリタ)

最近Rubyを始めました。

手始めにLispインタプリタを書いてみます。

元ねたはPeter Norvigの (How to Write a (Lisp) Interpreter (in Python)) （日本語訳: ((Pythonで) 書く (Lisp) インタプリタ)）です。

(ちなみに以前、Rでも同じことをやりました: ((Rで) 書く (Lisp) インタプリタ))

コード

Gistに上げておきました。 変なところがあったら教えてください。

	# -*- coding: utf-8 -*-
	# Scheme Interpreter in Ruby
	# (a Ruby port of the Peter Norvig's "lis.py")
	class Env < Hash
	def initialize(parms = [], args = [], outer = nil)
	@outer = outer
	update(Hash[parms.zip(args)])
	end
	def find(var)
	if self.has_key? var
	self
	else
	@outer.find(var)
	end
	end
	end
	def add_globals(env)
	[:+, :-, :*, :/].each do |s|
	env[s] = ->(*x) { x.reduce { |a, e| a.send(s, e) } }
	end
	[:>, :<, :>=, :<=].each do |s|
	env[s] = ->(x, y) { x.send(s, y) }
	end
	env.update({
	:not => ->(x) { !x },
	:'=' => ->(x, y) { x == y },
	:equal? => ->(x, y) { x == y },
	:eq? => ->(x, y) { x.equal? y },
	:length => ->(x) { x.length },
	:cons => ->(x, y) { [x] + y },
	:car => ->(x) { x[0] },
	:cdr => ->(x) { x[1..-1] },
	:append => ->(x, y) { x + y },
	:list => ->(*x) { x },
	:list? => ->(x) { x.is_a? Array },
	:null? => ->(x) { x == [] },
	:symbol? => ->(x) { x.is_a? Symbol }
	})
	end
	def evaluate(x, env)
	if x.is_a? Symbol # variable reference
	env.find(x)[x]
	elsif !x.is_a? Array # constant literal
	x
	elsif x[0] == :quote # (quote exp)
	x[1]
	elsif x[0] == :if # (if test conseq alt)
	_, test, conseq, alt = x
	evaluate(evaluate(test, env) ? conseq : alt, env)
	elsif x[0] == :set! # (set! var exp)
	_, var, exp = x
	env.find(var)[var] = evaluate(exp, env)
	elsif x[0] == :define # (define var exp)
	_, var, exp = x
	env[var] = evaluate(exp, env)
	elsif x[0] == :lambda # (lambda (var*) exp)
	_, vars, exp = x
	->(*args) { evaluate(exp, Env.new(vars, args, env)) }
	elsif x[0] == :begin # (begin exp*)
	x[1..-1].map { |exp| evaluate(exp, env) }[-1]
	else # (proc exp*)
	exps = x.map { |exp| evaluate(exp, env) }
	exps[0].call(*exps[1..-1])
	end
	end
	def read(s)
	read_from(tokenize(s))
	end
	alias parse read
	def tokenize(s)
	s.gsub('(', ' ( ').gsub(')', ' ) ').split
	end
	def read_from(tokens, cont_tokens_proc = nil)
	raise 'unexpected EOF while reading' if tokens.empty?
	token = tokens.shift
	if '(' == token
	l = []
	while tokens[0] != ')'
	if tokens.empty? && !cont_tokens_proc.nil?
	tokens.concat(cont_tokens_proc.call) while tokens.empty?
	break if tokens[0] == ')'
	end
	l << read_from(tokens, cont_tokens_proc)
	end
	tokens.shift # pop off ')'
	l
	elsif ')' == token
	raise 'unexpected )'
	else
	atom token
	end
	end
	def atom(token)
	begin
	Integer(token)
	rescue
	begin
	Float(token)
	rescue
	token.to_sym
	end
	end
	end
	def to_string(exp)
	if exp.is_a? Array
	'(' + exp.map { |x| to_string x }.join(' ') + ')'
	else
	exp.to_s
	end
	end
	def repl(prompt = 'lisp.rb> ')
	env = add_globals(Env.new)
	tokens_proc = ->() { tokenize(gets) }
	while true
	print prompt
	puts to_string(evaluate(read_from(tokens_proc.call, tokens_proc), env))
	end
	end
	if __FILE__ == $0
	repl
	end

view raw lisp.rb hosted with ❤ by GitHub

遊び方

$ ruby lisp.rb 
lisp.rb> (+ 1 2 3)
6
lisp.rb> (define add2 (lambda (x) (+ x 2)))
#<Proc:0x00000001647958@lisp.rb:62 (lambda)>
lisp.rb> (add2 40)
42
lisp.rb> (define map (lambda (f l) (if (null? l) (quote ()) (cons (f (car l)) (map f (cdr l))))))
#<Proc:0x0000000164f1a8@lisp.rb:62 (lambda)>
lisp.rb> (map add2 (list 10 20 30))
(12 22 32)
lisp.rb> 

感想

Rubyを使ってみて思ったことをメモしておきます。

• Perlっぽい

  • メソッドのかっこを省略できる
  • ifとかwhileを後置できる

• Lisp(関数型)っぽい

  • Symbol
  • いろんなものが値を返す(ifとか)
  • returnを省略できる

• オブジェクト指向

  • 何でもオブジェクト!
  • mapとかの高階関数がメソッドなのはなんだか違和感があるけど、 メソッドチェインができるのは良いかも。

割と良い感じです。もうちょっと使ってみます。 ワンライナーとかちょっとしたスクリプトとかPerlのかわりに使ってみようかな。

参考文献

同じことをやっている方は他にもいます。
元ねたのページ のコメントで紹介されていた 以下の実装が簡潔で素敵です。 わからないところはこちらをチラ見しながら作りました。

• Index of /rispy

(追記)

その後少し手を加えて、REPLで式の途中に改行を入れられるようにしました。
(上に貼ってあるGistは修正後です。)

こんな感じに入力できます。

lisp.rb> (+ (* 3
               (+ (* 2 4)
                  (+ 3 5)))
            (+ (- 10 7)
               6))
57
lisp.rb> 

思ったより少ない変更で実現できました。 (Gistの履歴)