Hatena::Groupocaml-nagoya

yoshihiro503の関数的日記

2010-10-21 (Thu)

Scalaで戻り値の型でオーバーロードする

| 21:15 | Scalaで戻り値の型でオーバーロードする - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - Scalaで戻り値の型でオーバーロードする - yoshihiro503の関数的日記

JavaScalaなどでオーバーロードする場合は引数の数、または型が異なっていなければならない。例えば次のようなコードはコンパイルエラーになる。

class C {
  def foo() : Int = 3
  def foo() : Long = 3L
  def foo() : String = "3"
}
Main.scala:4: error: method foo is defined twice
  def foo() : String = "3"
      ^
one error found

参考: no title

こんなときJavaでは別名のメソッドにするしかないが、Scalaではimplicit parameterを使ってこれを実現できる。

class C {
  def foo[X](implicit f : X) : X = f

  private implicit def f1 : Int = 3
  private implicit def f2 : Long = 3L
  private implicit def f3 : String = "3"
}

参考: no title

このクラスの使用者はfooという名前でいろいろなところで使うことができるようになる。

2010-06-09 (Wed)

haXeで怠惰(lazy)を実装してみた

| 23:31 | haXeで怠惰(lazy)を実装してみた - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - haXeで怠惰(lazy)を実装してみた - yoshihiro503の関数的日記

haXeには組み込みでは怠惰(lazy)評価 機能が備わっていないようだったので実装してみた。

関数型言語ではthunkを簡単に扱うことができ、評価を遅延させることができるが、それだとタダの遅延評価(delay evaluation)になってしまい、無駄な計算が発生してしまうかもしれない。そこで評価は遅らせるけれど、一回計算したら覚えておくというLazy型を定義した。コンストラクタにはthunkをわたして使う。

enum Option<X> {
    None;
    Some(x : X);
}

class Lazy<A> {
    var _x : Option<A>;
    var _getter : Void -> A;

    public function new (getter) {
        this._x = None;
        this._getter = getter;
    }

    public function force() {
        switch (this._x) {
            case None:
                var x = this._getter();
		this._x = Some(x);
		return x;
	    case Some(x):
		return x;
	}
    }
}

そして、それを使って怠惰リストを実装したのが次。

enum LListT<A> {
    LNil;
    LCons(x : A, tl : Lazy<LListT<A>>);
}

class LList{
    static public function from(n : Int) : LListT<Int> {
	return LCons(n, new Lazy(function() return from(n+1)));
    }

    public static function take<A>(n:Int,xs:LListT<A>) : List<A> {
	var ys = new List();
	var xs0 = xs;
	for (i in 0...n) {
	    switch (xs0) {
		case LCons(x, xs1):
		    xs0 = xs1.force();
		    ys.push(x);
		case LNil:
		    break;
	    }
	}
	return Util.list_reverse(ys);
    }

    public static function filter<A> (xs : LListT<A>, f:A -> Bool) {
	return switch(xs) {
	    case LNil: LNil;
	    case LCons(x, xs):
		if (f(x)) LCons(x, new Lazy(function ()
		   return filter(xs.force(), f)));
		else filter(xs.force(), f);
	}
    }
}

以上の怠惰評価と怠惰リストをUtil.hxというファイルにまとめて、これを試してみるために素数の無限列を作ってみた。

import Util;

class Test {
    static function main() {
	trace("primes: "+LList.take(100,primes));
    }

    static var primes = seive(LList.from(2));
		
    static function seive(xs) {
	return switch(xs) {
	    case LNil: Util.failwith("");
	    case LCons(x,xs): LCons(x, Util.lazy(function() {
		return LList.filter(seive(xs.force()), function(a) return a%x!=0);
	    }));
	}
    }
}

TestクラスはTest.hxに保存。実行結果は以下。

 $ haxe -main Test -neko Test.n
 $ neko Test.n
Test.hx:7: primes: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 
193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 
311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 
433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541}

2010-03-27 (Sat)

TwitterクライアントOCamltterを作ってみた

| 10:24 | TwitterクライアントOCamltterを作ってみた - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - TwitterクライアントOCamltterを作ってみた - yoshihiro503の関数的日記

[追記: 2010 09/13]

この記事は古いです。最新版は ProofCafe - ocamltter をごらんください。

続きを読む

camlspottercamlspotter2010/03/27 21:45toplevel で日本語が表示されている例という意味で貴重だなと思いました。

yoshihiro503yoshihiro5032010/03/28 11:24すみません。標準出力にprint_endlineで出しています。

DeryaDerya2012/04/09 01:27It's a pleasure to find soomene who can think so clearly

2009-12-13 (Sun)

オブジェクト指向言語モデルFJのラムダ計算への埋め込みを使ったFJへの構造的部分型の導入

| 21:02 | オブジェクト指向言語モデルFJのラムダ計算への埋め込みを使ったFJへの構造的部分型の導入 - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - オブジェクト指向言語モデルFJのラムダ計算への埋め込みを使ったFJへの構造的部分型の導入 - yoshihiro503の関数的日記

Rubyなどの動的型を持つオブジェクト指向言語は便利でお手軽なため多岐に利用されているが, 静的なチェックがないために単純なミスによる不具合(バグ)が起こることがある. でも静的なチェックによってRubyの柔軟性が失われることは嫌だ.

本文書ではなるべくRubyの柔軟性を生かしつつ, しかしより高信頼なプログラム開発を実現する検証器を実装するために型システムを考えた. この検証器を使えば、存在しないメソッドの呼び出しや引数の数の間違いを防ぐだけでなく, インターフェイスの記述によって大規模開発や拡張を可能とすると考えている.

この型システムを使えば次の様なコードが検証できる. 次のFJのコードの例を見てみよう.

まずDuckとCarというclassを定義したとする.

class Duck
  def sound
    'クワックワッ'
  end
  def swim
    ...
  end
end
class Car
  def sound
    'ブーブー'
  end
  def putOil(oil)
    ...
  end
end

両クラスともsoundというメソッドを持っている. ここで, 引数で与えられたオブジェクトのsoundメソッドを呼ぶ関数を次の様に定義した.

def test(x)
  puts x.sound
end

このとき以下の実行は両方共有効なはずである.

test(new Duck)
test(new Car)

Javaなどの静的型チェックはこのようなコードをはじいてしまうが、本型システムはこれを型付け可能である. もちろんメソッドの呼び出しが定義されていない場合は型エラーである.

前回同様TeXで書いた。

http://www.itpl.co.jp/ocaml-nagoya/index.php?plugin=attach&refer=%C8%AF%C9%BD%BB%F1%CE%C1&openfile=doc2.pdf

2009-12-07 (Mon)

オブジェクト指向言語モデルFJのラムダ計算への埋め込み

| 23:05 | オブジェクト指向言語モデルFJのラムダ計算への埋め込み  - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - オブジェクト指向言語モデルFJのラムダ計算への埋め込み  - yoshihiro503の関数的日記

2009-05-07を読んで「オブジェクト指向言語より関数型言語の方が表現力が高い」と思ったので証明してみた。

OO言語のモデルはこのまえid:keigoiさんと飲んだときに教えてくれたFJ(Featherweight Java)を使用した。そして、関数型言語のモデルはおなじみラムダ計算にレコードと不動点演算を入れた単純拡張ラムダ計算(λ+と呼ぶ)を利用した。

2節ではFJをサーベイし、3節ではλ+をサーベイする。そして4節で埋め込み関数を定義し、それがうまいこと行ってることを証明した。

証明とかはハテダよりTeXの方が書きやすかったのでTeXで書いてみた。http://www.itpl.co.jp/ocaml-nagoya/index.php?plugin=attach&refer=%C8%AF%C9%BD%BB%F1%CE%C1&openfile=doc.pdf

2009-07-11 (Sat)JavaでParserモナド

JavaでParserモナド

| 20:47 | JavaでParserモナド - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - JavaでParserモナド - yoshihiro503の関数的日記

Java で Parser モナドを書いてみた。

JavaGenerics(ポリモルフィズム)があるのでほとんどcastを使わず型安全に実装できたが型推論がないので型が非常に冗長になった。

このパーサーライブラリを使えば、例えばラムダ式のパーサーが次のように30行くらいで書ける。P.mbind, P.dbind, P.mor, P.mreturn はそれぞれ Haskellでいう >>=, >>, <|>, return に対応する。

    static Parser<LAMBDA> lambda () {
	return P.mor(P.map (T.ident, new Fun<String,LAMBDA>() {
		    public LAMBDA apply (final String v) {
			return new VAR(v);
		    } }),
	    P.mor (P.dbind(T.symbol('('), P.dbind(T.symbol('\\'), P.bind (T.ident, new Fun<String,Parser<LAMBDA>>() {
				public Parser<LAMBDA> apply (final String v) {
				    return P.dbind(T.symbol('.'), P.bind (lambda(), new Fun<LAMBDA,Parser<LAMBDA>>() {
						public Parser<LAMBDA> apply (final LAMBDA t) {
						    LAMBDA abs = new ABS(v,t);
						    return P.dbind(T.symbol(')'), P.mreturn (abs));
						} }));
				} }))),
		   P.bind(T.symbol('('), new Fun<Unit,Parser<LAMBDA>>() {
			   public Parser<LAMBDA> apply(Unit _) {
			       return P.bind(lambda(), new Fun<LAMBDA,Parser<LAMBDA>>() {
				       public Parser<LAMBDA> apply (final LAMBDA t1) {
					   return P.bind(lambda(), new Fun<LAMBDA,Parser<LAMBDA>>() {
						   public Parser<LAMBDA> apply (final LAMBDA t2) {
						       LAMBDA app = new APP(t1, t2);
						       return P.dbind(T.symbol(')'), P.mreturn (app));
						   } });
				       } });
			   } })));
    }

使い方

 $ java Main '((\x.x) ( \ y. (y y)) )'
パース成功: ((λx.x) (λy.(y y)))

パースした結果は以下の記事にかいてあったラムダ式を利用しようかと思ったけど、ちょっとそのままじゃ使えなかったので諦めた。

Java でラムダ - IT戦記

ソースコード全体は300行くらい

http://bitbucket.org/yoshihiro503/parsecinjava/src/

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/


  • ファイル読み込みからパージングを lazy list を使った実装に変えた。文字の lazy list として読み込み、トークンの lazy list にして、 パースするようにした。
  • シンボルテーブルをHashにした。
  • フィールドをたくさんつなげれるようにした。(a.foo().bar().hoge("hallo"))
  • インスタンス変数を実装した。
  • newしたときにinitialize関数が呼ばれるようにした。

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

	- メソッド定義
	- クラス定義
	- 関数呼び出し
	- フィールド参照
	- 変数代入
	- 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のようなコンビーネータを作って、それを使った。参考にしたのは以下の文献

2008-12-12 (Fri)

haXe2scheme コンパイラ in haXe

10:43 | haXe2scheme コンパイラ in haXe - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - haXe2scheme コンパイラ in haXe - yoshihiro503の関数的日記

なんとなくできました。

http://www.bitbucket.org/yoshihiro503/myhaxe/

とりあえず neko VM 用にコンパイルした myhaxe.n を実行してみる。

使い方: <ファイル名.hx> を <ファイル名.scm> にコンパイル(変換)する

  $ neko myhaxe.n -scheme <ファイル名.hx>

Hello, world!の例

Test.hx:

class Test {
  static function main () {
    trace("Hello, world!");
  }
}

コンパイルして生成した Test.scm:

(define trace (lambda (x) (display x)))
(define ignore (lambda (x y) y))
(define app (lambda (f l) (cond ((pair? l) (app (f (car l)) (cdr l))) (f))))
#| -- my lib -- |#
(define main (lambda (args) (trace "Hello, world!")))

実行してみた:

$ gosh Test.scm
Hello, world!

今回実装したこと

これから実装予定のこと

  • コメント
  • 型パラメータ
  • 標準ライブラリ
  • その他の言語への変換

ShojiroShojiro2012/04/09 09:42This is exactly what I was looking for. Thanks for wriitng!