ftdop.scala

Scala

最近は、かなり Scala にはまっています。Scalaのどこがいい？っていうと、C言語っぽい言語で関数型言語的な機能が使えるということです。おかげで、かなり文法を忘れることなく、しかも、関数的にプログラムをかけます。


ということで、以下、謎の四則演算が可能な計算機を作ってみました。
変わった機能としては、1(2)で1+2の機能が、1(2)で1*2、1[2]で1-2の意味を持っているということです。

Scalaでは正規表現をマッチングの要素として使うことができるので、とてもいい感じに構文解析を書くことができます。
また、関数的に下降型の演算子順位解析法を書くと非常に簡潔に書けました。

関数的ってどういうことかといいますと、

①副作用をなくす。
②構文木と文字列のペアを引数としてパーサに渡して、構文解析した結果を構文木と文字列のペアとして値を返すようにする。
③無限ループは再帰呼び出しで行う。
④マッチング構文を利用する。
⑤タプルを使う。

というようなことやっているということです。


命令的に書いたものから、この形に変換するのに１日かかってしまったのですが、これらの法則を守って書くことで簡潔に書くことができました。いかに、パーサや、評価器を書くのにマッチングが便利かが分かると思います。

今後の改良点は、前置演算子、後置演算子、制御演算子を定義することです。
表の追加と、構文解析のプログラムをそれぞれ数行書くだけで改良が完了するように思います。
あと、型に厳密になってみたり、ならなかったりすることです。
Algol文法を持ったような、Lisp的言語を目指しているので、型はduck typingでいいようにも思うのですが、、、その辺をどう書いたら綺麗なのかが課題です。
あと、このプログラムを命令型のプログラムに書き換えるということをやって見るのも面白いかと思います。

/*
 * ftdop2.scala
 * Functional Top Down Operator Precedence
 */
package ftdop2
import scala.util.matching.Regex

object main {
	def main(argv:Array[String]) {
		println(parse(argv(0)))
		println(eval(argv(0)))
	}

	def parse(src:String) = {

		val numReg = """^[ \r\n\t]*([0-9]+)(.*)""".r
		val opReg = """^[ \r\n\t]*([\+\-\*\/])(.*)""".r
		val prnReg = """^[ \r\n\t]*([\(\{\[])(.*)""".r

		def infixs(op:Any):Int = op match {
			case "*" => 20
			case "/" => 20
			case "-" => 10
			case "+" => 10
			case _	 => -1
		}

		def parens(op:Any):Int = op match {
			case "(" => 100
			case "{" => 100
			case "[" => 100
			case _   => -1
		}

		def endParens(op:Any):Regex = op match {
			case "(" => """^[ \r\n\t]*(\))(.*)""".r
			case "{" => """^[ \r\n\t]*(\})(.*)""".r
			case "[" => """^[ \r\n\t]*(\])(.*)""".r
		}

		sealed case class AS(a:Any, s:String)

		def eat(t:Regex)(as:AS):AS = t.unapplySeq(as.s) match {
			case Some(List(s,s2)) => AS(s, s2)
			case _ => throw new Error("error")
		}

		def exp(p:Int)(as:AS):AS = as match {
			case AS(null, numReg(x, xs)) => exp(p)(AS(x.toInt, xs))
			case AS(null, prnReg(p1, xs)) if (p < parens(p1)) =>
				val AS(y, ys) = exp(0)(AS(null, xs))
				val AS(z, zs) = eat(endParens(p1))(AS(null, ys))
				val bin = (p1,y,z)
				exp(p)(AS(bin,zs))
			case AS(x, prnReg(p1, xs)) if (p < parens(p1)) =>
				val AS(y, ys) = exp(0)(AS(null, xs))
				val AS(z, zs) = eat(endParens(p1))(AS(null, ys))
				val bin = (x,p1,y,z)
				exp(p)(AS(bin,zs))
			case AS(x, opReg(op, xs)) if (p < infixs(op)) =>
				val AS(y, ys) = exp(infixs(op))(AS(null, xs))
				val bin = (x, op, y)
				exp(p)(AS(bin, ys))
			case x => x
		}

		exp(0)(AS(null, src)).a
	}

	def eval(s:String):Int = eval(parse(s))

	def eval(a:Any):Int = a match {
		case (a,"(",b,")") => eval(a) + eval(b)
		case (a,"{",b,"}") => eval(a) * eval(b)
		case (a,"[",b,"]") => eval(a) - eval(b)
		case ("(",a,")") => eval(a)
		case (a,"+",b) => eval(a) + eval(b)
		case (a,"*",b) => eval(a) * eval(b)
		case (a,"-",b) => eval(a) - eval(b)
		case (a,"/",b) => eval(a) / eval(b)
		case a => a.asInstanceOf[Int]
	}
}