Rustで作るプログラミング言語処理系 導入編

Rustの練習がてら、授業で作ったプログラミング言語処理系のトレースをしようと思います。

授業ではScalaで実装したが、 Built in Rustっていうとすごそうに見えるのでRustで書いていきます。

今回対象とする言語は以下の機能を持ちます。文法はScalaに似せています。

• 変数に値を代入
• 変数から値を読み出す
• 関数定義、関数適用
• Int, Bool, List[Int]の型を持つ
• List[Int]はheadに先頭の値を、tailに残りの要素のListを持つ
• 四則演算、比較演算(==, <)、結合演算(::)
• if else式
• 再帰関数

コード例(挿入ソート)

def insert(x: Int, l: List[Int]): List[Int] =
  if (l.isEmpty)
    x::Nil
  else if (x<l.head)
    x::l
  else
    l.head::insert(x, l.tail)

def sort(l: List[Int]): List[Int] =
  if (l.isEmpty)
    Nil
  else
    insert(l.head, sort(l.tail))

def test(n: Int): List[Int] =
  if (n == 0)
    Nil
  else
    insert(n, test(n-1))

授業ではnonscalaと呼んでいましたが、一般にそう呼ばれているかは知りません。

次回から実装に入ります。まずは字句解析から、どうかよろしくお願いします。