個人的Go雑感&メモ

GoogleがGoという新しいプログラミング言語を出したようで。早速、インストールして軽くドキュメントを流し読みしてみました。

英語なんて読みたくないよ、という人もいるかもしれないし、誰かの役に立つかもしれないので自分用メモおいときます。完全に自分用なんである程度他の言語の知識がある人向けな上、ざっくり流し読みなんで間違ってるかも。

どんな言語？

  • ネイティブコードを吐く、コンパイル型。
  • 速度はCレベル。
  • GC搭載。ポインタはあるけど、ポインタ演算はできません。
  • 各種アーキに最適化された、それぞれのコンパイラセットを持ちます。例：
    • 6g, 6l : amd64
    • 8g, 8l : i386
  • linux, mac, naclに対応。
  • 動的型言語と静的型言語のおいしいとこどり。
  • concurrent処理が組み込まれてます。

個人的雑感

  • こんな言語設計思想かなあと感じたり
    • とにかく、シンプルな言語に。
      • C++の複雑な部分などはできるだけはずしているような。
        • いわゆるクラスベースのオブジェクト指向はない。
          • 継承はない。
          • あるのはフラットなインタフェース空間のみ。
        • 例外もない。
    • 低レイヤからは離れすぎたくない。
    • concurrentを言語的にサポートしたい。
  • 以下の言語からの影響を感じたり
    • 言語コアはC。
    • C++はパッケージの書き方、記法に影響がみられる。
    • 命名規則や記法にPythonの影響がみられる。
    • concurrentな部分はErlangから影響をうけている。

言語仕様

自分なりに簡単にまとめて見ます。

変数への代入

下へ行くほど省略形。varもあるからconstもあるでよ。

 code
  1. var s string = "";
  2. var s = "";
  3. s := "";
  4.  

オブジェクト構造

値扱いの型と参照型があります。

  • 値扱い : 代入、関数への私はコピーとなる。配列もまるごとコピーされる。
    • 各種数値 : int, floatといったプラットフォームごとにサイズがきまる型とint32のようにサイズ固定の型。
    • string : 不変、UTF8、ただのバイト配列
    • 配列
    • struct : ユーザ定義型
    • などなど
  • 参照 : 3つのみ
    • map : 辞書
    • slice : 明示的なサイズを持たない、配列のようなもの
    • channel : concurrentで使う

値扱い型のアロケート方法 : new -> T*を返す

 code
  1. var t *T = new(T);
  2.  

参照型のアロケート方法 : make -> Tを返す

 code
  1. m := make(map[string]int);
  2. // これはダメ
  3. var m map[string]int;
  4.  

配列とスライス

  • 配列は「値」。でユーザがメモリ構造などを読める。スライスはコンパイラがよしなに確保する、参照型。

例えばint型配列のポインタを受け取る場合。

標準配列(&がいる)

 code
  1. s := sum(&[3]int{1,2,3});
  2. s := sum(&[...]int{1,2,3});
  3.  

スライス

 code
  1. s := sum([]int{1,2,3});
  2.  

辞書型

 code
  1. timeZone := map[string]int{
  2.   "UTC": 0*60*60,
  3.   "EST": -5*60*60,
  4.   "CST": -6*60*60,
  5.   "MST": -7*60*60,
  6.   "PST": -8*60*60,
  7. }
  8.  
  9. seconds, ok = timeZone[tz]
  10. //値がなければokはfalse
  11. if seconds, ok := timeZone[tz]; ok {
  12.     return seconds
  13. }
  14. //消す場合
  15. timeZone["UTC"] = 0, false;
  16.  

パッケージ、制御構造、型定義、関数とメソッド、インタフェース

命名規則に特徴があります。大文字始まり以外は外部から見えないが原則。単なる命名規則ではなく、そういう仕様。

パッケージ

パッケージ文でファイルの先頭に書きます。これが基本的な単位となります。

 code
  1. package file
  2.  
制御構造

特徴は

  • ()がいらない。
  • ifやswitchなどの条件部に複数の文がかける
  • ループはforのみ(whileやdoはない)
  • switchが強力に(内容的にif-else if-elseチェイン)
  • concurrent用にselectがある

という点。かと。

ifの例

 code
  1. if i % prime != 0 {
  2.     fmt.Printf("%d", i);
  3. }
  4.  

switchの例

 code
  1. switch nr, er := f.Read(&buf); true {
  2.            case nr < 0:
  3.                fmt.Fprintf(os.Stderr, "cat: error reading from %s: %s\n", f.String(), er.String());
  4.                os.Exit(1);
  5.            case nr == 0: // EOF
  6.                return;
  7.            case nr > 0:
  8.                if nw, ew := file.Stdout.Write(buf[0:nr]); nw != nr {
  9.                    fmt.Fprintf(os.Stderr, "cat: error writing from %s: %s\n", f.String(), ew.String());
  10.                }
  11. }
  12.  

caseに条件式がかける。breakは自動でされる。

型定義

type,structキーワードを組み合わせる。メンバにメソッドは含みません。

 code
  1. type File struct {
  2.     fd int; // file descriptor number
  3.     name string; // file name at Open time
  4. }
  5.  

メンバ名が小文字なので、パッケージ外からは見えません。

関数とメソッド
  • 両方ともfuncキーワードで定義。
  • 違いはレシーバを指定するか否か。 レシーバを明示的に書くところはPythonっぽい。
  • 多値が返せる。

この多値がかえせる、というのがGoでは非常に重要な意味をもっています。

関数定義: 多値を返しています。大文字始まりなので、外部に公開されます。

 code
  1. func Open(name string, mode int, perm int) (file *File, err os.Error) {
  2.      r, e := syscall.Open(name, mode, perm);
  3.      if e != 0 {
  4.          err = os.Errno(e);
  5.      }
  6.      return newFile(r, name), err
  7. }
  8.  

返す型に(file *File, err os.Error)と変数名がついてますね。これをつけておけばreturn;ってかくだけでその名前の変数を返してくれます。

 code
  1. func Open(name string, mode int, perm int) (file *File, err os.Error) {
  2.      r, e := syscall.Open(name, mode, perm);
  3.      if e != 0 {
  4.          err = os.Errno(e);
  5.      }
  6.      file = newFile(r, name)
  7.      return;
  8. }
  9.  

こんな風にもかけるってことです。おそらく、エラー処理が絡む場合とかこっちのほうが書きやすかったりするんじゃないですかね。

クロージャにもなります。いわゆる関数ポインタをとるようなところで、関数がそのままかけて外部変数も見えます。

 code
  1. startServer(func(a, b int) int { return a + b });
  2.  

メソッド定義。(file *File)がレシーバの指定。

 code
  1. func (file *File) Close() os.Error {
  2.     if file == nil {
  3.         return os.EINVAL
  4.     }
  5.     e := syscall.Close(file.fd);
  6.     file.fd = -1; // so it can't be closed again
  7.     if e != 0 {
  8.         return os.Errno(e);
  9.     }
  10.     return nil
  11. }
  12.  

メソッド定義がstructでの型定義時ではないことに注目。つまり組み込み型などに対してもあとからメソッドを作成できるのです。こんな感じ。

 code
  1. type IntArray []int
  2. func (p IntArray) Len() int { return len(p); }
  3.  
インタフェース

これ重要。Goはいわゆるクラスがないので、継承などもなくインタフェースによるダックタイピングでそれらを片付けます。 interfaceキーワードで定義。

 code
  1. type reader interface {
  2.      Read(b []byte) (ret int, err os.Error);
  3.      String() string;
  4. }
  5.  

このように、ReadとStringが定義されていればそれはreaderなんだ、と考えます(ダックタイピング)。

実行時、動的にインタフェースが実装されているかも検査できます。

 code
  1. s, ok := v.(Stringer);
  2.  

vがStringerインタフェースを満たしていれば

  • sにStringerオブジェクトとしてのv
  • okにtrueが

がかえってきます。

Concurrency

concurrentプログラミングはGoの大きな特徴。CSP(Communicating Sequential Processes)に基づいてます。並行して動く「goroutines」という軽量プロセスが「channel」を介してやりとり。ガードと多重化のためにselect文があります。

channelは単体ではなくchan 受け渡しする型という感じで書きます。以下はチュートリアルのコードまんまです。

 code
  1. func generate(ch chan int) {
  2.     for i := 2; ; i++ {
  3.         ch <- i // Send 'i' to channel 'ch'.
  4.     }
  5. }
  6.  

intを扱うchannelを受け取ってそれにiを送っていきます。

 code
  1. func filter(in, out chan int, prime int) {
  2.     for {
  3.         i := <-in; // Receive value of new variable 'i' from 'in'.
  4.         if i % prime != 0 {
  5.             out <- i // Send 'i' to channel 'out'.
  6.         }
  7.     }
  8. }
  9.  

送られたiが一定の条件を満たしていたら、intを扱うoutというchannelに送ります。

 code
  1. func main() {
  2.     ch := make(chan int); // Create a new channel.
  3.     go generate(ch); // Start generate() as a goroutine.
  4.     for {
  5.         prime := <-ch;
  6.         fmt.Println(prime);
  7.         ch1 := make(chan int);
  8.         go filter(ch, ch1, prime);
  9.         ch = ch1
  10.     }
  11. }
  12.  

channelは参照型なのでmakeで作ります。goで実行します。これは丁寧に書いた感じ。クロージャを使えばもっとシンプル。

 code
  1. func generate() chan int {
  2.     ch := make(chan int);
  3.     go func(){
  4.         for i := 2; ; i++ {
  5.             ch <- i
  6.         }
  7.     }();
  8.     return ch;
  9. }
  10.  
多重化とガード

複数のチャンネルをとりあつかって、それらをガードにより振り分けられます。ErlangやScalaでおなじみの書き方です。

 code
  1. func server(op binOp, service chan *request, quit chan bool) {
  2.     for {
  3.         select {
  4.         case req := <-service:
  5.             go run(op, req); // don't wait for it
  6.         case <-quit:
  7.             return;
  8.         }
  9.     }
  10. }
  11.  

request型のポインタを扱うchannelとbool型を扱うchannelを使って、多重化しています。quitチャンネルに値が送られてくるまでは、送られてきたものから良しなに処理してくれる、という感じですね。

というわけで

なぐり書きしたメモでした。変なことかいてたらすみません。まぁこんな感じな言語かなあ、という程度で。

繰り替えしになりますが、C言語を元にシンプルに保ちながらconcurrentプログラミングしやすくしてます、って感じですね。完全にダックタイピングベースで多値を多様するスタイルはおもしろいですね。なんとなく見た目がキモく感じるのは私の気のせいでしょう。

というか数ヶ月もブログ放置してたのかー。コード書いてないわけじゃないんですけど、たいしたもんかいてないんですよね。割合的には8割がたCかな。月一くらいはブログ書いていきたいなあ・・・

01.06.10/12am
Posted at:
11.11.09/08pm
Tags:
Comments:
0
Permalink

Scalaでスタック指向言語をサクッと実装する

Scalaにはご存知のとおりscala.util.parsing.combinatorというパーサコンビネータライブラリがある。さらにはscala.util.parsing.astというのもあるわけだけど、これは激しく開発中な感じ。Scalaはバージョンがあがるとこういう開発中ライブラリはごそっと変わったりするので今はおいておく。ちなみに、2.7.1では前のパーサコンビネータはscala.util.parsing.combinatoroldといういかにも使いたくない名前にされてしまった。

パーサコンビネータといえば言語処理系だ（そうか？）。というわけでscala.util.parsing.astは置いておいて、とりあえずASTについてほとんど考える必要がない、簡単なスタック指向言語を実装してみることにする。実行はScala 2.7.1.finalで。

スタック指向言語とは

こんなブログを見ている人は、だいたいスタック指向言語を知っているだろうから俺みたいな素人が書いてもなんだけど、一応。 スタック指向言語にはForthやPostScriptやFactorがある。素晴らしく簡単にいうと、「とりあえずスタックがあればなんとかなるよね」という言語だ。

んでスタック使うなら逆ポーランドで書いてあったら、処理も楽だしいいんじゃね、読みにくい？Lispだって慣れてる人は無問題なんだし、慣れの問題じゃね、という感じである。

関数（スタック指向言語ではwordという）もスタックに値をつんで実行すればいい。wordから値を返すときも返したい分だけスタックにつめばいい。というわけで、非常に単純なのである。

今回はFactorライクなスタック指向言語処理系（インタプリタ）「SimpleFactor」を作ってみることに。文法とかはだいたいFactorと一緒なのでさきにFactorの文法を学んでおくと分かりやすい。

まずはレクサ

まずはレクサを作る。サポートするリテラルは文字列、整数値、真偽値で以下のような感じ。

  • 文字列："hoge"
  • 整数値：10, -10
  • 真偽値：t,f

あと、コメントは!から行末までとする。ソースはこんな感じで、ScalaのDSL構築能力を生かしてかなり定義どおりに書ける。

scala code
  1. import scala.util.parsing.combinator._
  2. import scala.util.parsing.combinator.syntactical._
  3. import scala.util.parsing.combinator.lexical._
  4. import scala.util.parsing.input.CharArrayReader.EofCh
  5. class Lexer extends StdLexical with ImplicitConversions {
  6.   override def token: Parser[Token] =
  7.     ( string ^^ StringLit
  8.     | '-' ~> number ^^ { case num => NumericLit("-" + num) }
  9.     | number ^^ NumericLit
  10.     | EofCh ^^^ EOF
  11.     | delim
  12.     | '\"' ~> failure("Unterminated string")
  13.     | rep(chrAny) ^^ checkKeyword
  14.     | failure("Illegal character")
  15.     )
  16.  
  17.  
  18.   def number = zero | (nonzero ~ rep(digit) ^^ {case x ~ y => mkS(x::y)})
  19.   def string = '\"' ~> rep(charSeq | chrExcept('\"', '\n', EofCh)) <~ '\"' ^^ {case x => mkS(x)}
  20.   def checkKeyword(xs : List[Any]) = {
  21.     val strRep = mkS(xs)
  22.     if (reserved contains strRep){ Keyword(strRep) }
  23.     else if(identiferRe.findFirstIn(strRep) != None ) { Identifier(strRep) }
  24.     else {ErrorToken("Not a Identifier: " + strRep)}
  25.   }
  26.  
  27.   override def whitespace: Parser[Any] =
  28.     rep( whitespaceChar | '!' ~ rep( chrExcept(EofCh, '\n') ))
  29.   def nonzero = elem("nonzero digit", d => d.isDigit && d != '0')
  30.   def zero: Parser[String] = '0' ^^^ "0"
  31.   def charSeq: Parser[String] =
  32.     ('\\' ~ '\"' ^^^ "\"" |'\\' ~ '\\' ^^^ "\\" |'\\' ~ '/' ^^^ "/" |'\\' ~ 'b' ^^^ "\b" | '\\' ~ '0' ^^^ ""
  33.     |'\\' ~ 'f' ^^^ "\f" |'\\' ~ 'n' ^^^ "\n" |'\\' ~ 'r' ^^^ "\r" |'\\' ~ 't' ^^^ "\t")
  34.   def identiferRe = """^(\w|[^"])+$""".r
  35.   def chrAny = chrExcept(EofCh, ' ', '\n', '\t', '\r', '\"', '!')
  36.  
  37.   def mkS[A](seq: Seq[A]) = seq mkString ""
  38. }
  39.  

Scalaで処理系を作る場合はとりあえずStdLexicalを継承して拡張すれば、だいたいOK。ここではTokenを返すパーサを定義する。KeywordやStringLitといったTokenを継承したケースクラスはscala.util.parsing.sytax.StdTokensで定義されていて、StdLexicalはStdTokensをMix-inしている。

抽象構文木をつくる

次に、このトークンの並びから文法を定義して、それに従って抽象構文木を作るわけだけど、スタック指向言語の場合、ここで難しいことはあまりない。

とりあえず、処理(といっても4種類、しかもうち2種類は意味なし）と、抽象構文木をあらわすケースクラスを作る。インタプリタなのでオペコードとかする意味はないけど、こうしとくとVMにしようと思ったとき楽なのでそうした。というよりエミュとかを作ることが好きなので、こういう数値を見ると安心するのである。

scala code
  1. import scala.util.logging.ConsoleLogger
  2. import scala.collection.mutable.{Stack, ArrayBuffer, HashMap}
  3. trait Opecode {
  4.   final val OP_NOP : byte = 0x00
  5.   final val OP_PUSH : byte = 0x01
  6.   final val OP_CALL : byte = 0x50
  7.   final val OP_RTN : byte = 0x51
  8. }
  9.  
  10. abstract class Node {
  11.   type Value
  12.   val v:Value
  13.   def value = v
  14. }
  15. abstract class NodeValue extends Node
  16. case class NodeStr(v:String) extends NodeValue { type Value = String }
  17. case class NodeInt(v:int) extends NodeValue { type Value = int }
  18. case class NodeBool(v:boolean) extends NodeValue { type Value = boolean }
  19. case class NodeSymbol(override val v:String) extends NodeStr(v)
  20. case class NodeQuotation(val v:List[Node]) extends Node{ type Value = List[Node] }
  21. case class NodeOpe(v:byte, operand:List[Node]) extends Node { type Value = byte }
  22. case class NodeNamed(v:Named) extends NodeValue with Opecode{ type Value = Named }
  23. case class NodeProgram(v:List[Node]) extends Node with Opecode{
  24.   type Value = List[Node]
  25.   var quotIndex = 0
  26.   def nextQuotSym = { quotIndex += 1; "quot"+quotIndex }
  27.  
  28.   def toplevel = {
  29.     val nullsf = List[NodeSymbol]()
  30.     val words = new ArrayBuffer[Node]
  31.     def visitNode(n:Node):List[Node] = n match {
  32.       case NodeNamed(NamedWord(name, sin, sout, body)) =>
  33.          words += NodeNamed(NamedWord(name, sin, sout, body.flatMap(visitNode)))
  34.          List[Node]()
  35.       case NodeQuotation(nodes) =>
  36.         val name = nextQuotSym
  37.         words += NodeNamed(NamedWord(name, nullsf, nullsf, nodes.flatMap(visitNode)))
  38.         List(NodeOpe(OP_PUSH, List(NodeSymbol(name))))
  39.       case x => List(x)
  40.     }
  41.     value.flatMap(visitNode)
  42.     words.toList
  43.   }
  44. }
  45.  
  46. abstract class Named(name:String)
  47. case class NamedWord(name:String, stackin:List[NodeSymbol], stackout:List[NodeSymbol], body:List[Node]) extends Named(name)
  48. case class NamedNativeWord[T](name:String, stackin:List[NodeSymbol],
  49.   stackout:List[NodeSymbol], body:()=>T) extends Named(name)
  50. class NamedTable extends HashMap[String, Named] {
  51. }
  52.  

Nodeという抽象クラスを継承して、いろんなノードを定義する。だいたい名前をみてのとおりだけど、わかりにくいところだとこんな感じ。

  • NodeNamed：名前付けされた値への参照
  • NodeSymbol：word名
  • NodeQuotation：無名関数(quotationという)
  • NodeProgram：プログラム全体

Namedは名前付けされた値なわけだけど、今回変数にあたるものはないので、wordのみがコレにあたる。NamedWordがSimpleFactorで書かれたふつーのword、NamedNativeWordはいわゆる組み込みwordでScalaで書いたものをあらわす。NamedTableはその対応を保存する単なるハッシュマップ。

さて、ではこいつらを使って構文木を作って実行する。

scala code
  1. class SimpleFactorInterp extends StdTokenParsers with ImplicitConversions with Opecode{
  2.   type Tokens = Lexer
  3.   val lexical = new Tokens
  4.   lexical.reserved ++= List("t", "f", "(", ")", "[", "]", ":", ";", "--")
  5.   lexical.delimiters ++= List("\n", " ", "\t")
  6.   import lexical.{NumericLit, StringLit, Keyword, Identifier}
  7.  
  8.   def program = rep(lWord) ^^ { case nodes => NodeProgram(nodes) }
  9.   def lWord = ":" ~ lSymbol ~ "(" ~ rep(lSymbol) ~ "--" ~ rep(lSymbol) ~ ")" ~ rep(lExpr) ~ ";" ^^
  10.                         { case ":" ~ name ~ "(" ~ sin ~ "--" ~ sout ~ ")" ~ body ~ ";" =>
  11.                             NodeNamed(NamedWord(name.value, sin, sout, body+NodeOpe(OP_RTN, List[Node]()))) }
  12.   def lExpr:Parser[Node] = (lString | lNumber | lBool | lInvokeWord | lQuotation)
  13.   def lString = accept("string", { case StringLit(n) => NodeOpe(OP_PUSH, List(NodeStr(n))) })
  14.   def lNumber = accept("number", { case NumericLit(n) => NodeOpe(OP_PUSH, List(NodeInt(n.toInt))) })
  15.   def lBool = accept("boolean",{ case Keyword("t") => NodeOpe(OP_PUSH, List(NodeBool(true)))
  16.                                        case Keyword("f") => NodeOpe(OP_PUSH, List(NodeBool(false))) })
  17.   def lInvokeWord = accept("symbol", { case Identifier(n) => NodeOpe(OP_CALL, List(NodeSymbol(n))) })
  18.   def lQuotation = "[" ~> rep(lExpr) <~ "]" ^^ { case expr => NodeQuotation(expr+NodeOpe(OP_RTN, List[Node]())) }
  19.  
  20.   def lSymbol = accept("symbol", { case Identifier(n) => NodeSymbol(n) })
  21.  
  22.   protected val stack = new Stack[Node]
  23.   protected var namedTable = new NamedTable
  24.  
  25.   def parse(input: String) =
  26.     phrase(program)(new lexical.Scanner(input)) match {
  27.       case Success(programNode, _) => initTopLevel(programNode.toplevel)
  28.       case x => error(x.toString)
  29.     }
  30.  
  31.   def initTopLevel(toplevelNodes:List[Node]) = {
  32.     def sl(v:String) = v.split(" ").map(NodeSymbol).toList
  33.     def nword[T](n:String, sin:String, sout:String, m:()=>T) =
  34.       (n, NamedNativeWord(n, sl(sin), sl(sout), m))
  35.     namedTable ++= List(
  36.       nword("drop", "x", "", ()=>{ pop }),
  37.       nword("dup", "x", "x x", ()=>{ val v = pop; npush(v,v) }),
  38.       nword("rotate", "x y z", "y z x", ()=> npop(3) match {
  39.         case List(x, y, z) => npush(y, z, x)
  40.       }),
  41.       nword("swap", "x y", "y x", ()=> npop(2) match {
  42.         case List(x, y) => npush(y, x)
  43.       }),
  44.  
  45.       nword("+", "x y", "z", ()=>{ iArI2(_+_) }),
  46.       nword("-", "x y", "z", ()=>{ iArI2(_-_) }),
  47.       nword("*", "x y", "z", ()=>{ iArI2(_*_) }),
  48.       nword("/", "x y", "z", ()=>{ iArI2(_/_) }),
  49.  
  50.       nword(">", "x y", "?", ()=>{ ilB2(_>_) }),
  51.       nword("<", "x y", "?", ()=>{ ilB2(_<_) }),
  52.       nword("==", "x y", "?", ()=>{ ilB2(_==_) }),
  53.       nword(">=", "x y", "?", ()=>{ ilB2(_>=_) }),
  54.       nword("<=", "x y", "?", ()=>{ ilB2(_<=_) }),
  55.  
  56.       nword("not", "?", "?", ()=> pop match {
  57.         case NodeBool(v) => push(NodeBool(!v))
  58.       }),
  59.       nword("and", "? ?", "?", ()=> (pop, pop) match {
  60.         case (NodeBool(true), NodeBool(true)) => push(NodeBool(true))
  61.         case (NodeBool(_), NodeBool(_)) => push(NodeBool(false))
  62.       }),
  63.       nword("or", "? ?", "?", ()=> (pop, pop) match {
  64.         case (NodeBool(false), NodeBool(false)) => push(NodeBool(false))
  65.         case (NodeBool(_), NodeBool(_)) => push(NodeBool(true))
  66.       }),
  67.  
  68.       nword(".", "obj", "", ()=>{ println(pop.value) }),
  69.       nword("call", "quot", "", ()=> pop match {
  70.         case NodeSymbol(qname) => callWord(qname)
  71.       }),
  72.  
  73.       nword("if", "? quot quot", "", ()=> (pop, pop, pop) match {
  74.         case (_, NodeSymbol(qname), NodeBool(true)) => callWord(qname)
  75.         case (NodeSymbol(qname), _, NodeBool(false)) => callWord(qname)
  76.       }),
  77.  
  78.       nword("string>number", "str", "x", ()=> pop match {
  79.         case NodeStr(str) => push(NodeInt(str.toInt))
  80.       }),
  81.       nword(">string", "obj", "str", ()=> { push(NodeStr(pop.value.toString)) })
  82.  
  83.     )
  84.     toplevelNodes.foreach {
  85.       case NodeNamed(n@NamedWord(name, _, _, _)) => namedTable(name) = n
  86.       case _ => ()
  87.     }
  88.   }
  89.  
  90.   def evaluate(input:String, args:Array[String]) = {
  91.     parse(input)
  92.     args.map(NodeStr).foreach(push _)
  93.     callWord("main")
  94.   }
  95.  
  96.   def callWord(wordName:String):unit =
  97.     namedTable(wordName.ensuring(namedTable.contains _, "word '"+wordName+"' is not defined.")) match {
  98.       case NamedNativeWord(_, sin, sout, body) => try {
  99.           body()
  100.         } catch {
  101.           case e => wordError(wordName, sin, sout)
  102.                     throw e
  103.         }
  104.       case NamedWord(_, sin, sout, body) =>
  105.         body foreach {
  106.           case NodeOpe(OP_PUSH, List(v, _*)) => push(v)
  107.           case NodeOpe(OP_CALL, List(NodeSymbol(name), _*)) =>
  108.             try {
  109.               callWord(name)
  110.             }catch {
  111.               case e => wordError(wordName, sin, sout)
  112.                         throw e
  113.             }
  114.           case NodeOpe(OP_RTN, _) => ()
  115.         }
  116.     }
  117.  
  118.   def npop(n:int):List[Node] = (1 to n).map(x=>pop).reverse.toList
  119.   def npush(ns:Node*) = ns.reverse.foreach(push(_))
  120.  
  121.   def iArI2(f:(int,int)=>int) = (pop, pop) match {
  122.     case (NodeInt(v1), NodeInt(v2)) => push(NodeInt(f(v2,v1)))
  123.   }
  124.   def ilB2(f:(int,int)=>boolean) = (pop, pop) match {
  125.     case (NodeInt(v1), NodeInt(v2)) => push(NodeBool(f(v2,v1)))
  126.   }
  127.   def wordError(name:String, sin:List[NodeSymbol], sout:List[NodeSymbol]) = {
  128.     printf("word '%s' ( %s -- %s ).\n", name, sin.map(_.value).mkString(" "),
  129.                                               sout.map(_.value).mkString(" "))
  130.   }
  131.   def push(a:Node) = stack.push(a)
  132.   def pop = stack.pop
  133.  
  134. }
  135.  

はじめの方でプログラムの文法を定義し、TokenからNodeのリストへ変換し、NodeProgramにする。処理の簡単さのため、プログラムはwordから構成されていて、プログラム開始時にはmain wordから実行が開始されるとするので

scala code
  1. def program = rep(lWord) ^^ { case nodes => NodeProgram(nodes) }
  2.  

wordは

 code
  1. : add ( x y -- z )
  2.  +
  3. ;
  4.  

という感じに定義するのでlWordの定義になっている。ほとんどそのまま書いた感じだ。( x y -- z )の部分はスタックエフェクトといって、このwordがスタックにどのような影響を与えるのかを記述している。あくまで説明であって本質的な意味はない。( x y -- z )ならスタックから2個取り出されて、結果が1個詰まれるのだな、ということがわかる。

あとは自明なので省略。

実行

そんなこんなでソースコードからNodeProgramが作れるようになった。次にNodeProgramからTOPレベル環境を作る。

ここでは、NodeProgramに含まれるquotationを(実行する際の）簡単さのためNamedWordに変換し、変換後のNamedWordの呼び出しに変換する。組み込みwordもここで定義している。これはこの部分で定義すると、クロージャになるため定義が簡単だから(popやpushといったSimpleFactorInterpのメソッドがそのまま書ける)である。また、パターンマッチを活用することで非常に直感的に書けていることが見て取れるかと。やっぱりパターンマッチ最高だわぁ･･･。そして出揃ったTOPレベルのwordをNamedTableにマッピングし、TOPレベル環境の作成が完了する。

あとはmain wordを呼び出すだけ。

サンプルコード

こんな感じ。サンプルでは10の階乗を計算している。

scala code
  1. object SimpleFactor extends ConsoleLogger{
  2.   def main(args: Array[String]) = {
  3.     log("Starting SimpleFactor.")
  4.     log("-"*40)
  5.     val ip = new SimpleFactorInterp
  6.     ip.evaluate("""
  7. ! Performs a factorial calculation.
  8. : main ( str -- )
  9. string>number fact .
  10. ;
  11.  
  12. : fact ( x -- y ) dup factit ;
  13.  
  14. : factit ( x y -- z )
  15. dup 1 <=
  16. [ drop ]
  17. [ 1 - dup rotate * swap factit ] if
  18. ;
  19.  
  20. """, args)
  21.   }
  22. }
  23.  
  24. SimpleFactor.main(Array("10"))
  25.  

ここで使っているwordを簡単に説明すると

  • string>number:スタックからpopし、文字列を数値に変換してpushする
  • *: スタックから2個popし、掛けたものをpushする
  • -: スタックから2個popし、引き算したものをpushする
  • <=:スタックから2個popし、<=な比較をして真偽値をpushする
  • .: スタックからpopし、文字列表現を表示する
  • dup:スタックからpopし、それを2回pushする
  • drop:スタックからpopする
  • rotate:「x y z」というスタックのトップ部分を、「y z x」にローテーションする
  • swap:「x y」というスタックのトップ部分を「y x」に入れ替える
  • if:「真偽値 真のとき実行するquotation 偽のとき実行するquotation」というスタックのトップ部分から条件を判定しquotationを実行する

てな感じ。これだけの命令でもちゃんとプログラムが書けて、条件分岐、ループが実現できるのはスタック指向言語を知らない人から見ると面白い部分かも。3 factなら

  • [ 3 3 ] : fact内dup
  • [ 3 3 3 ] : factit内dup
  • [ 3 3 3 1 ] : 1
  • [ 3 3 f ] : <=
  • [ 3 3 f quot ] : [ drop ]
  • [ 3 3 f quot quot ] : [1 - ... ]
  • [ 3 3 ] : if
  • [ 3 3 1 ] : 1
  • [ 3 2 ] :
    -
  • [ 3 2 2 ] : dup
  • [ 2 2 3 ] : rotate
  • [ 2 6 ] : *
  • [ 6 2 ] : swap
  • factitに戻る

こんな感じで計算される。

またLispのS式とマクロによる拡張性は名高いと思うが、スタック指向言語も単純に空白で区切られたwordが並んでいる、という点で非常に自己拡張性が高い。こういう変態的(?)な部分も魅力の一つ。

ForthはSUNのOpen Firmware、Firefox4で採用が予定されているJavascriptの処理系Tamarinの中など、今でもあまり表には見えてこない部分で使用されているので、これを機会にスタック指向言語を嗜んでみては。Forthは基本だけど、今なら注目され始めている(？)Factorかなあ。

簡単に作れます

というわけでScalaで簡単なスタック指向言語処理系を作ってみたわけだけど、非常に簡単。さくっと作れる。scala.util.parsing.astができたら、またなんか処理系を試し書きしてみようかな。

  • 20080519:ryugateさんの指摘を受けてソースコードのコピペミスを修正、また少し説明を足しました。
07.27.08/12am
Posted at:
05.17.08/10pm
Tags:
Comments:
(3)
Permalink

About

Author:yuin(http://inforno.net/)

文学部文化学科卒という生粋の文系趣味プログラマ。

主にRuby、Javascript、PHP、JAVA,Python,C,Scala,Schemeなどを使っています。今はPythonな感じかもしれない。今後作曲活動なども復活するかもしれない。

Links

Pages

Recently

Tags

DHT1 SF1 activesupport1 api4 binary3 blog1 book1 cltc1 compiler1 craftlaunch2 cui1 development9 drecom1 electronics1 emulator6 erlang1 essay10 fckeditor1 feed1 framework1 gae3 go1 gui2 javascript14 job4 kademlia1 language2 library14 life5 lingr1 linux1 nes5 network1 nicovideo1 nlp1 ocaml1 p2p1 parser6 programing2 prototype_js7 python39 python30001 rayphe1 ruby5 rubyonrails2 scala6 scheme1 scrap1 scriptaculous1 sexp1 tasktools1 template3 text3 tk1 typo2 vim2 webpy2 windows4 wordpress2 xrea2 yahoo4

Monthly Archives