2008.04.01

Python でSICP4.3 Nondeterministic Computing

あれ、思ったより綺麗に書けたぞ。

# Amb evaluator
# See http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3

# Global variable for amb evaluator
amb_variable_name = []
amb_possible = []

def comb(lol):
  """
  make all combination from a list of lists
  """

  if not lol:
    yield []
  else:
    for x in lol[0]:
      for y in comb(lol[1:]):
        yield [x] + y


def amb(v, l):
  """
  set global variable for amb evaluator
  """

  amb_variable_name.append(v)
  amb_possible.append(l)
  return

def ambeval():
  """
  amb evaluator
  """

  for tp in comb(amb_possible):
    # set variables
    # ex: exec("baker = 0")
    for i in range(len(amb_variable_name)):
      s = amb_variable_name[i] + "= " + str(tp[i])
      exec(s)

    # check requirements
    # ex: eval("baker != 5")
    met = True
    for f in require:
      if not eval(f):
        met = False
        break
      
    # all requiements met
    if met:
      yield tp


### USER FUNCTION ###
def make_distinct(list):
  """
  make string like distinct?
  (See http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#call_footnote_Temp_609 )
  """

  s = ""
  for i in range(len(list)):
    for j in range(len(list)):
      if i <= j:
        continue
      s += list[i] + " != " + list[j] + " and "
  s += "True"
  return s


### main
amb('baker', (1,2,3,4,5))
amb('cooper', (1,2,3,4,5))
amb('fletcher',(1,2,3,4,5))
amb('miller', (1,2,3,4,5))
amb('smith', (1,2,3,4,5))

require = ["baker != 5",
      "cooper != 1",
      "fletcher != 5",
      "fletcher != 1",
      "miller > cooper",
      "abs(smith - fletcher) != 1",
      "abs(fletcher - cooper) != 1",
      ]

# make_distinct resturns the string
# cooper != baker and fletcher != baker and fletcher != cooper and miller != baker and miller != cooper and miller != fletcher and smith != baker and smith != cooper and smith != fletcher and smith != miller and True

distinct = make_distinct(('baker','cooper','fletcher','miller','smith'),)
require.append(distinct)

# solve the problem!
for result in ambeval():
  print "baker = %d, " % int(result[0]),
  print "copper = %d, " % int(result[1]),
  print "fletcher = %d, " % int(result[2]),
  print "miller = %d, " % int(result[3]),
  print "smith = %d" % int (result[4]) 


実行結果がこれ

YUKI.N>python dwelling.py
baker = 3, copper = 2, fletcher = 4, miller = 5, smith = 1

実際にかかった時間が2時間くらい。大半がgeneratorの勘違いで時間を食った。再帰呼び出しをしている中でyieldすると、再帰を一個戻るだけなんだ。ツリーの一番下でyieldしたら、一気に値を返してくれると思って、すごく悩んだ。分かってしまえば当たり前の話。

いらいらしていたら、回答を教えてくれた@kana1さんに感謝。

対話的環境は無いが、SICPのあのごちゃごちゃしたソースが、組み合わせを作るcomb、amb評価器を生成するamb、条件から解を求めるambevalの3つの関数だけでできるんだからたいした物だ。条件も、そのままPythonの文字列書けば良いんだし。Python恐るべし。

言語占いの問い1はYesで確定。

| | Comments (0) | TrackBack (0)

2008.03.31

言語占い

プログラミングGauche」を読んで、再びSchemeの魅力に取り憑かれる。PythonもC++も勉強したいし、勉強したいことが多すぎて困る。

SystemCやるならC++だし、変態を自重するならPythonだし、メタプロするならSchemeが良いよね。でも、メタプロなら、C++のテンプレートも最高だよね。って、あれだ。一緒に遊園地行くならゆうゆだけど、奥さんにするならまみまみだよね、くらいのノリなんだと思う。もちろん、僕は両方ゆうゆですが。分からない人は、冒険に行くならビアンカだけど、結婚するならフローラだよね、でもよい。僕は両方フローラですが。

いい加減男らしくばしっと決めたいので、言語占いで決める事にした。

言語占いってのは、雑誌で良くある奴ね。

問1:最先端の技術を使いたい。YES→問2へ NO→じゃあ、COBOLで
問2:英語は苦手 YES→変数をローマ字で書いてもOKなCOBOLをおすすめ NO→問3へ
問3:Webアプリを作りたい YES→そんなナンパな気持ちは捨てて、COBOLを勉強しろ。NO→圧倒的な実績のあるCOBOLをおすすめ

こんな感じで、YES、NOを答えていくだけですぐに、あなたにおすすめの言語を選んでくれる。こりゃ楽だ。
雑誌の弱点として、いまいち僕を対象にしていないというか、不特定多数を対象にしすぎている。なければ作ってしまえば良くて、自分で占いを作る事にした。前からSICPのAMBが仕事で使えないかな~と思っていたので、題材にしてみる。やる夫は五階に住んでいません、ってやつね。

問1:AMBをPythonで書いてみる。納得いく物ができたか?
   YES→問2へ
   NO→言語レベルで継続をサポートしているGaucheおすすめ。

問2:AMBをC++で書いて見る。納得いく物ができたか?
   YES→C++おすすめ
   NO→君にはC++は10年早い。Pythonがおすすめ。

ちょっと占ってみよう。

# 一応書いておくけど、ネタだからね><

| | Comments (0) | TrackBack (0)

2008.02.08

[minipy] 演算子のオーバーロードを使ってみた

befor

# 特定のトークンを見つけるパーサ
eoi = parser.end_of_input()
nl = parser.lookfor('TOK_NEWLINE')
lk_print = parser.lookfor('TOK_KW_PRINT')
int = parser.lookfor('TOK_LITERAL_INT')
plus = parser.lookfor('TOK_PLUS')
minus = parser.lookfor('TOK_MINUS')

#a_expr ::= integer ( ( "+" | "-" ) integer)*
p_or_n = parser.alt('p_or_n', [plus, minus])
p_or_n_int = parser.cat('p_or_n_int', [p_or_n, int])
p_or_n_int_star = parser.star('p_or_n_int_star', p_or_n_int)
a_expr = parser.cat('a_expr', [int, p_or_n_int_star])

#expression ::= a_expr
expression = parser.cat('expression', [a_expr,])

#print_stmt ::= "print" expression_list_with_comma
print_stmt = parser.cat('print_stmt', [lk_print, expression])

#statement ::= print_stmt NEWLINE
statement = parser.cat('statement', [print_stmt, nl])

#file_input ::= (NEWLINE | statement)* EOF
nl_or_st = parser.alt('nl_or_st', [nl, statement])
nl_or_st_star = parser.star('nl_or_st_star', nl_or_st)
entire_input = parser.cat('file_input',[nl_or_st_star, eoi])

after

# 特定のトークンを見つけるパーサ
eoi = parser.end_of_input()
nl = parser.lookfor('TOK_NEWLINE')
lk_print = parser.lookfor('TOK_KW_PRINT')
int = parser.lookfor('TOK_LITERAL_INT')
plus = parser.lookfor('TOK_PLUS')
minus = parser.lookfor('TOK_MINUS')

#a_expr ::= integer ( ( "+" | "-" ) integer)*
a_expr = int + star((plus | minus) + int)

#expression ::= a_expr
expression = a_expr + None

#print_stmt ::= "print" expression_list_with_comma
print_stmt = lk_print + expression

#statement ::= print_stmt NEWLINE
statement = print_stmt + nl

#file_input ::= (NEWLINE | statement)* EOF
entire_input = star(nl | statement) + eoi

ちゃんと動いた!。
これなら文法を手入力しても良いかなってレベルになった。

文法の名前は自動でつけるようにして、各パーサの基底クラスに下の行加えただけ。動作確認入れても30分。LLって凄いよ。ほんと。
def __add__(self, other):
 if other == None:
  return cat([self,])
 else:
  return cat([self, other])

def __or__(self, other):
 return alt([self, other])

Higher-order-PerlとPython万歳!

| | Comments (0) | TrackBack (0)

2008.02.07

[minipy] パーサを作ろう その2

0回以上の繰り返しは、結局ループで処理した。
print 1 + 1 がそれっぽくパース完了

YUKI.N>python parser.py
[file_input]
 [nl_or_st_star]
  [nl_or_st]
   [statement]
    [print_stmt]
     [TOK_KW_PRINT]TOK_KW_PRINT
     [expression]
      [a_expr]
       [TOK_LITERAL_INT]TOK_LITERAL_INT (1)
       [p_or_n_int_star]
        [p_or_n_int]
         [p_or_n]
          [TOK_PLUS]TOK_PLUS
         [TOK_LITERAL_INT]TOK_LITERAL_INT (1)
    [TOK_NEWLINE]TOK_NEWLINE
  [nl_or_st]
   [TOK_NEWLINE]TOK_NEWLINE
  [nl_or_st]
   [TOK_NEWLINE]TOK_NEWLINE
 [EOF]TOK_EOF
YUKI.N>

文法の定義はこれ
# 特定のトークンを見つけるパーサ
eoi = parser.end_of_input()
nl = parser.lookfor('TOK_NEWLINE')
lk_print = parser.lookfor('TOK_KW_PRINT')
int = parser.lookfor('TOK_LITERAL_INT')
plus = parser.lookfor('TOK_PLUS')
minus = parser.lookfor('TOK_MINUS')

#a_expr ::= integer ( ( "+" | "-" ) integer)*
p_or_n = parser.alt('p_or_n', [plus, minus])
p_or_n_int = parser.cat('p_or_n_int', [p_or_n, int])
p_or_n_int_star = parser.star('p_or_n_int_star', p_or_n_int)
a_expr = parser.cat('a_expr', [int, p_or_n_int_star])

#expression ::= a_expr
expression = parser.cat('expression', [a_expr,])

#print_stmt ::= "print" expression_list_with_comma
print_stmt = parser.cat('print_stmt', [lk_print, expression])

#statement ::= print_stmt NEWLINE
statement = parser.cat('statement', [print_stmt, nl])

#file_input ::= (NEWLINE | statement)* EOF
nl_or_st = parser.alt('nl_or_st', [nl, statement])
nl_or_st_star = parser.star('nl_or_st_star', nl_or_st)
entire_input = parser.cat('file_input',[nl_or_st_star, eoi])

最後のentire_inputに対して、entire_input.parse(tk)で引数のTokenizerからトークンを読み込んでパースする。

mini とはいえ、すべての構文でこれを手書きするのは気が進まないので良い方法を考えよう。BNFを読み込んでこの形式に変更し、importするのがそこそこ楽そうな気がするんだが、気になる点が2つ

・上のやり方だと基本的に前方参照で文法を解決しないいけないので、いったん全部の文法を読み込んでから、順番を変えていかないといけない。言い方を変えると、文法はentire_inputが一番最初にあるけど、ソースに落とすときには一番最後でないとダメ。
・変換をするために、BNFをパースしないといけない。何がなんだか分からなくなる可能性が高い

一瞬S式という単語が浮かんだが、気にしないことにした。

HOPを見ると、演算子のオーバーロードを利用して見やすくしろ、とのこと。

#a_expr ::= integer ( ( "+" | "-" ) integer)*
p_or_n = parser.alt('p_or_n', [plus, minus])
p_or_n_int = parser.cat('p_or_n_int', [p_or_n, int])
p_or_n_int_star = parser.star('p_or_n_int_star', p_or_n_int)
a_expr = parser.cat('a_expr', [int, p_or_n_int_star])

同じ事が、これくらいで表現できるとうれしい
a_expr = int + ( (plus | minus) + int) >> star

ちょっと、演算子のオーバーロード勉強してくる。

| | Comments (0) | TrackBack (0)

2008.02.06

[minipy] 繰り返しの実装

日記を書く[・ _ゝ・]はやみずさんから

> 演習の課題提出のあと、春休みに適当に整理してCodeReposにコミットする予定。
これは期待。

なんとか、HOPの作法にのって、catとaltが出来た。
catは、今あるパーサを組み合わせて長いパーサを返す。

eoi = parser.end_of_input() # end of input (EOF) にマッチするパーサ
nl = parser.lookfor('TOK_NEWLINE') # 改行にマッチするパーサ

nl_eoi = parser.cat('nl_eoi', [nl, eoi])
とすると、改行 + EOFにマッチしたとき成功する。

nl_eoi = parser.alt('nl_eoi', [nl, eoi])
とすると、改行もしくは、EOFにマッチしたとき成功する。
基本的には、この連結(cat)と選択(alt)で再帰していけば良いはず。

次の部品が、任意の繰り返しのアスタリスクだ。
#file_input ::= (NEWLINE | statement)* EOF
#a_expr ::= "integer" ( "+" "integer" )*

上は簡単で0回以上の繰り返しの後、EOFが来れば成功だから終了条件が分かる。
下がちょっと難しい、1回でもintegerに入ってしまうと、終わりの条件をどうして良いのか分からない。

HOPの繰り返しの実装star()を見てみて納得。

nothing → トークンを消費せず、何でもマッチし、常に成功を返す。

こういうパーサをつくって、自分自身と nothingの選択にすればよさそう。で自分自身を先にパースしに行って失敗したとき(*が終了するとき)、nothingにマッチしてパースを完了する。このとき、トークンは消費されない。成功したときは、また自分自身を呼び出してパースをするから、繰り返しを実現できる。なるほど。

だんだん、Higher-order Perlが僕のバイブルになってきた。

| | Comments (0) | TrackBack (0)

2008.02.05

[minipy] パーサーを作ってみる その1

適当にHOPを参考にしながら、(長門の)minipyを始めた。

とりあえず、改行+EOFはパース出来るようになった。
改行+改行+EOFはまだこれから。

改行+EOFの場合
YUKI.N>python parser.py
[file_input]
[TOK_NEWLINE]TOK_NEWLINE
[TOK_EOF]TOK_EOF
YUKI.N>

改行+改行+EOFの場合
YUKI.N>python parser.py
parse error
[file_input]
[TOK_NEWLINE]TOK_NEWLINE
[TOK_EOF]TOK_NEWLINE
error Token:TOK_NEWLINE, line = 2

パースしていったら、順に構文ツリーを作るようにした。最後にエラーの場合はエラー箇所の表示までできた。プログラミングは楽しい。

Python(というかLL)の凄いところは、適当にかけること。Cだったらツリー構造一つとっても結構悩む。構文ツリーはbranchが2個じゃないので、malloc使うか、文法から最大数を抑え行くか、そこを決めないと先に進まない。

実際に手を動かしてパースをして気がついた事。
再帰下降形のパーサってのは、パースに失敗した時点で、パース全体が失敗したのかどうかが分からないこと。パース全体が失敗したか成功したかを返すのは簡単だけど、どのトークンで失敗になったかを返すのはパースの戻り値だけでは分からない。

だから、パース失敗のエラーメッセージを出すためには、順番に失敗を返して行って全体が失敗だったら、再帰のトレースをしないと行けない。これは面白い。

最初はHOPのサンプルそのままに、成功/失敗だけを返すように書いてういた。上に書いた事にに気がついてからは、パースに失敗したらその場所(トークン)にフラグをつけて、失敗した状態の構文ツリーを返すようにした。全体が失敗したなら、そのツリーを下っていってフラグの付いているトークンを元にエラー表示をさせればどこでgive upしたかがわかる。

こういう変更がPythonだったらすぐに出来るのがうれしい。Cだったら今まで0、1を返していた関数を、構文ツリーの構造体を返す仕様に変更したら結構手間だ。ポインターを返すにしても、引数のポインターに入れるにしても、だれが領域を確保するのかを考えないといけない。ツリーを再帰的に下っていくのもこんな簡単にかけて感激。

def dump_tree(self, depth=0):
 print self.string_for_dump(depth)
 for br in self.branches:
  br.dump_tree(depth + 1)

次は、A | Bの部分を作ろう。それができると、複数の改行+EOFがパース出来るはず。

次の目標はこれだ!
#file_input ::=
# (NEWLINE | statement)* EOF

Pythonいいよ。Python。
minipyいいよ。minipy。

| | Comments (0) | TrackBack (0)

2008.01.07

mini py

ようやく始めた、mini pyですが、トークンの切り出しが終わり、これからパーサーに入る所。トークンをシーケンスとして解析するか、選択肢のなかから選ぶかという点で、Higher-Order Perlに出てくるパーサと同じような雰囲気になっている。

Python特有の問題として、行頭の空白は意味がある事。とりあえず空白なんて全飛ばしにしていたらはまった。

twitterで@Yuyarin からアドバイスをもらった。ありがとうございます。
http://twitter.com/Yuyarin/statuses/564874712

次の課題は、トークン列からASTを作って出力し、入力と同じような出力を得ること。作らないといけないのは、トークン列をパースしてASTを作るところと、ASTをPythonのソースとして出力する仕組み。

せっかくだから、pypyのドキュメントでも読んでみようかと思う。VMに関しても資料あるし。

| | Comments (0) | TrackBack (0)

2007.12.26

クリスマスのプログラミングの成果

Nagato_idle_2

ここまできた。

手順
nagato.gifを各自用意して、C:\Python25\Lib\idlelibに置く。
EditorWindow.py 195行目周辺

    text_frame.pack(side=LEFT, fill=BOTH, expand=1)

    #nagato
    self.nagato = PhotoImage(file='nagato.gif')
    text.image_create('1.0', image=self.nagato)
    text.pack(side=TOP, fill=BOTH, expand=1)

    text.focus_set()

太字部分を追加

| | Comments (3) | TrackBack (1)

2007.12.11

[HOP] ちょっと停滞ぎみ

簡単なパーサーを組み合わせて、複雑なパーサーを作るところではまる。
パーツとしてのパーサーは、HOPに合わせてクロージャを使って生成していますが、再帰的なパースが上手くクロージャにならない。

expressin -> INT + expression

という再帰的なルールを、こう書きたい

$expression = concatenate(lookfor('INT'), lookfor(['OP', '+']), $expression));

これは、perlでもエラーになる。HOPでは、my $Expression = parser { $expression->(@_) };と書いて上手くリンクさせているのだが、Pythonでは、僕の実力的にどうにもこうにもならない。クロージャの中には、クロージャのリストがあって、そこを書き換えれば良さそうなんだけど、それが出来たらすでにクロージャじゃない。
しょうがないのでclassで書き直してみた。__setitem__で[]のアクセスができて感激。
それっぽくパースができた。

| | Comments (0) | TrackBack (0)

2007.11.29

ヤター! 長門Pythonできたよー!

Python界では、みんpy、はじpy、pypyといろんなpyがあるなか、次は貧pyだと信じて疑わない私です。
東大ではとっくにmini pyを授業に取り入れている事に気がつき、いろんな意味で勝負にならないと思いました。(主にpy的な意味で)

もうすぐクリスマスなので、PythonのIDLEも長門プロンプトに変えてみました。


C:\Python25\Lib\idlelib以下のファイルを書き換えました。
変更箇所は3箇所です。
・EditorWindow.py 91行目:プロンプトを長門プロンプトに
   sys.ps1 = 'YUKI.N> '
・PyShell.py 2行目:エンコードの指定を追加
# -*- coding: utf-8 -*-
・PyShell.py 990行目:起動メッセージの変更
   self.write("Python %s on %s\n%s\n\nIDLE %s %s(Yuki Nagato)\n" %
         (sys.version, sys.platform, self.COPYRIGHT,
         idlever.IDLE_VERSION, nosub))
   self.console.write(u'YUKI.N> みえてる?\nYUKI.N> うまく言語化できない。情報の伝達に齟齬が発生するかもしれない。でも、聞いて。')

最後に、PyShell.pyをutf-8で保存すればOK。
クリスマスは長門とPythonプログラミングを楽しもう!

| | Comments (1) | TrackBack (0)

より以前の記事一覧

その他のカテゴリー

C++ | FPGA | FreeBSD | Lisp | Perl | pmeteo | Python | Systemc | Verilog | wifehack | お勉強 | プライベート | モバイル | 読書