Hatena::Groupocaml-nagoya

yoshihiro503の関数的日記

2009-05-02 (Sat)OCamlRuby更新

OCamlRubyをさらに更新

| 22:53 | OCamlRubyをさらに更新 - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - OCamlRubyをさらに更新 - yoshihiro503の関数的日記

OCamlRubyを更新した。

現在コードの行数は512行

http://bitbucket.org/yoshihiro503/ocamlruby/

新しく追加したのはブロック構文とラムダ式、さらに無名クラスなども定義した。

OCamlRubyの特徴は全てのものが式であること。このことによって内部の実装が非常にシンプルになった気がする。

具体的な内部構造は以下。

type expr =
  | Ignore of expr * expr  (* 式 e1を実行して, e2 *)
  | Call of obj * string * expr list    (* 関数呼び出し、またはメソッド呼び出し *)
  | Assign of string * expr    (* 変数へ代入 *)
  | If of expr * expr * expr    (* if 式 *)
  | Literal of literal    (* 数値やブール等の定数値 *)
  | Variable of string    (* 変数 *)
  | FunDef of string * string list * expr    (* 関数定義 *)
  | ClassDef of string * expr    (* クラス定義 *)
  | Const of inst    (* 評価済みのオブジェクト(内部で使用) *)
  | External of (inst -> expr)    (* OCamlの関数(内部で使用) *)
and obj = Obj of expr | Self

パースできるブログラムBNFはこんな形式

	<program> ::= <expr>
	
	<expr> ::= <lterm>*
	<lterm> ::= <rterm> ( [ "&&" | "||" ] <rterm> )*

	<rterm> ::= <aterm> ( [ "==" | "<=" | .. | ">" ] <aterm> )*

	<aterm> ::= <mterm> ( [ "+" | "-" ] <mterm> )*

	<mterm> ::= <factor> ( ["*" | "/" ] <factor> )*

	<factor> ::= <factor1> <factor_next>

	<factor1> ::= <ident> "=" <lterm>
		    | <ident> "(" <expr> "," .. "," <expr> ")"
	    	    | <ident> <block>
		    | <ident>
		    | "def" <ident> "(" <ident> "," .. "," <ident> ")" <expr> "end"
		    | "def" <ident>  <expr> "end"
		    | "class" <ident>  <expr>  "end"
	    	    | "class"  <expr>  "end"
		    | <block>
		    | "lambda" <block>
		    | "(" <expr> ")"
		    | "if" <expr> "then" <expr> "else" <expr> "end"
		    | <literal>
		 
	<factor_next> ::= "." <ident> "(" <expr> "," .. "," <expr> ")"  <factor_next>
		        | "." <ident>  <block> <factor_next>	
			| "." <ident>  <factor_next>
		        | <e>

	<block> ::= "{"  "|" <ident> "," .. "," <ident> "|" <expr> "}"
		  | "do" "|" <ident> "," .. "," <ident> "|" <expr> "end"

	<literal> ::= <string> | <int> | <bool>

実装した構文
================

	- メソッド定義
	- クラス定義
	- 関数呼び出し
	- フィールド参照
	- 変数代入
	- if式
	- リテラル(文字列、数値、真偽値)
	- インスタンス変数
	- 四則演算
	- 大小比較
	- bool演算
	- 引数が無いメソッドの括弧省略
	- ブロック構文、ラムダ式
	- 無名クラス、無名関数


まだないもの
====================
	
	- 配列
	- 特殊なリテラル(範囲、シンボル、正規表現など)
	- 引数カッコの省略
	- 継承、モジュール

OCamlRuby更新

| 17:54 | OCamlRuby更新 - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - OCamlRuby更新 - yoshihiro503の関数的日記

http://bitbucket.org/yoshihiro503/ocamlruby/



実装した構文
================

	- メソッド定義
	- クラス定義
	- 関数呼び出し
	- フィールド参照
	- 変数代入
	- if式
	- リテラル(文字列、数値、真偽値)
	- インスタンス変数
	- 四則演算
	- 大小比較
	- bool演算
	- 引数が無いメソッドの括弧省略


まだないもの
====================
	
	- 配列
	- 特殊なリテラル(範囲、シンボル、正規表現など)
	- ブロック構文
	- 引数カッコの省略
	- 継承、モジュール

2009-04-29 (Wed)RubyのインタープリタをOCamlで実装してみた。

RubyのインタープリタをOCamlで実装してみた。

| 21:48 | RubyのインタープリタをOCamlで実装してみた。 - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - RubyのインタープリタをOCamlで実装してみた。 - yoshihiro503の関数的日記

Ruby言語のことをよく知らないので、CSNagoya読書会に参加している。次回までちょっと日があいていたのでインタープリターを実装してみた。Objective Caml 言語を使って実装した。

外部ライブラリ使用せず、OCamlの標準ライブラリのみを使った。

プログラムの行数は今のところ全部で415行

フィボナッチを実行してみる。

def fib (n)
  if n <= 2 then
    1
  else
    fib (n - 1) + fib (n - 2)
  end
end

puts (fib (20))

実行結果

 $ time ./ocamlruby fib.rb 
6765

real    0m0.038s
user    0m0.034s
sys     0m0.004s

さらに構文を拡張して関数クラスや 式の中で関数定義などができるようにした。

次のようなコードが書ける

def hoge()
  def huga(x)
    class X
      def s ()
        "bunbun "
      end
    end
    (X.new()).s() + x
  end
  puts (huga(x))
end


d =
  class D
    def foo (x)
      x + 5
    end
  end.new()

puts (d.foo(3))

詳しい構文のBNFは以下。すべてを式(expression)と扱うことにしたので、シンプルかつ柔軟性が高くなったと思う。

http://bitbucket.org/yoshihiro503/ocamlruby/src/tip/README

2009-04-26 (Sun)Rubyのパーサーを実装してみた

OCamlでRubyのパーサー

| 00:06 | OCamlでRubyのパーサー - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - OCamlでRubyのパーサー - yoshihiro503の関数的日記

Rubyサブセットmin_rubyのパーサーをOCamlで実装してみた

http://bitbucket.org/yoshihiro503/min_ruby/ (* 引っ越しました *)

http://bitbucket.org/yoshihiro503/ocamlruby/

プログラムは今のところ全部で232行

実装した構文
================

	- メソッド定義
	- クラス定義
	- 関数呼び出し
	- フィールド参照
	- 変数代入
	- if式
	- リテラル(数値、真偽値)
	- 四則演算
	- 大小比較
	- bool演算


まだないもの
====================
	
	- 文字, 文字列, 配列
	- 正規表現
	- ブロック構文
	- 範囲リテラル
	- シンボル
	- 省略可能な引数
	- 引数カッコの省略
	- インスタンス変数
	- 継承
	- モジュール

例えば次のコードパースできる。

class C
  def f (x, y)
    if (4 * x == 4 || 3 * (y+2) >= 6+1) then
      true
    else
      false
    end
  end
  
  def g ()
    f (0, 1)
  end
end

class D
  def foo ()
    puts 5
  end
end

def fib (n)
  if n <= 2 then
    0
  else
    (fib (n - 1)) + (fib (n - 2))
  end
end

puts (fib (3))

字句解析はgenlexモジュールを使って、パーサーはHaskellのParsecのようなコンビーネータを作って、それを使った。参考にしたのは以下の文献