■

Pugs Pugs

オードリーたんは、一ヶ月でHaskellマスターして一ヶ月でPugs書いたとか聞いたので、どんだけ仕事速いねんと思ったら、Pugs-6.0.0はすっごいシンプルだった。
http://search.cpan.org/src/AUTRIJUS/Perl6-Pugs-6.0.0/
これなら一ヶ月というのも理解できる。

   ______
 /\   __ \
 \ \  \/\ \ __  __  ______  ______     (P)erl6
  \ \   __//\ \/\ \/\  __ \/\  ___\    (U)ser's
   \ \  \/ \ \ \_\ \ \ \/\ \ \___  \   (G)olfing
    \ \__\  \ \____/\ \____ \/\_____\  (S)ystem
     \/__/   \/___/  \/___/\ \/____/
                       /\____/               Version: 6.2.13
                       \/___/    Copyright 2005-2006, The Pugs Contributors
--------------------------------------------------------------------
 Web: http://pugscode.org/           Email: perl6-compiler@perl.org

Welcome to Pugs -- Perl6 User's Golfing System
Type :h for help.

Golfing Systemて。PerlはPolymorphic Existential Recursive Lambdasらしい


本題。WindowsでのPugsビルドリベンジ。正直こういう作業はちっとも楽しくないよな〜ほえー。適当に調べてると、cygwinでビルドできなくもないらしいけど、色々めんどくさそうなので、まあやめといた方がよさげ。

http://wiki.kn.vutbr.cz/mj/index.cgi?Pugs%20on%20MS%20Windows
を見ると、ActivePerlとnmake(とGHC)があればいけると書いてあったので、試したらあっさりできた。GHCのバージョンは6.6。Pugsのバージョンは6.2.13。一応インストールまでしておいた方がいいっぽい。Perlのライブラリの関係で

で、

C:\ghc\Perl6-Pugs-6.2.13>cp third-party\fps\Setup.hs third-party\filepath
C:\ghc\Perl6-Pugs-6.2.13>cd third-party\filepath
C:\ghc\Perl6-Pugs-6.2.13\third-party\filepath>runhaskell Setup.hs configure
C:\ghc\Perl6-Pugs-6.2.13\third-party\filepath>runhaskell Setup.hs build
C:\ghc\Perl6-Pugs-6.2.13\third-party\filepath>runhaskell Setup.hs install
C:\ghc\Perl6-Pugs-6.2.13\third-party\filepath>cd ..\fps
C:\ghc\Perl6-Pugs-6.2.13\third-party\fps>runhaskell Setup.hs configure
C:\ghc\Perl6-Pugs-6.2.13\third-party\fps>runhaskell Setup.hs build
C:\ghc\Perl6-Pugs-6.2.13\third-party\fps>runhaskell Setup.hs install
C:\ghc\Perl6-Pugs-6.2.13\third-party\fps>cd ..\HsSyck
C:\ghc\Perl6-Pugs-6.2.13\third-party\HsSyck>runhaskell Setup.hs configure
C:\ghc\Perl6-Pugs-6.2.13\third-party\HsSyck>runhaskell Setup.hs build
C:\ghc\Perl6-Pugs-6.2.13\third-party\HsSyck>runhaskell Setup.hs install
C:\ghc\Perl6-Pugs-6.2.13\third-party\HsSyck>cd ..\..
C:\ghc\Perl6-Pugs-6.2.13>runhaskell Setup.lhs configure
C:\ghc\Perl6-Pugs-6.2.13>runhaskell Setup.lhs build
C:\ghc\Perl6-Pugs-6.2.13>runhaskell Setup.lhs install
C:\ghc\Perl6-Pugs-6.2.13>ghc-pkg list
C:/ghc/ghc-6.6\package.conf:
    Cabal-1.1.6, GLUT-2.0, HUnit-1.1, OpenGL-2.1, Pugs-6.2.13,
    QuickCheck-1.0, Win32-2.0, base-2.0, cgi-2006.9.6, fgl-5.2,
    (ghc-6.6), haskell-src-1.0, haskell98-1.0, html-1.0, mtl-1.0,
    network-2.0, objectio-1.0, parsec-2.0, pugs-HsSyck-0.2,
    pugs-filepath-0.1, pugs-fps-0.7, readline-1.0, regex-base-0.71,
    regex-compat-0.71, regex-posix-0.71, rts-1.0, stm-2.0,
    template-haskell-2.0, time-1.0, xhtml-2006.9.13

buildはいらん気もするけど、まあ一応。Pugs-6.2.13,　pugs-HsSyck-0.2,　pugs-filepath-0.1, pugs-fps-0.7が追加されてればOK


んで、

import Pugs
main = eval "2+3;"

とかをコンパイルしようとすると、C:\ghc\ghc-6.4.1\include\HsBase.hの__hscore_d_nameがどーたらというエラーが出る。

http://folksonomy.sakura.ne.jp/perl/pugs_build.html
によると、これは使われてない関数なのでコメントアウトしていいらしい。あと、libperl58.aがないので、同じリンク先に書いてあるようにExtUtils::FakeConfigをダウンロードして展開してインストール(libperl58.aはghc6.6/gcc-libとかにいれとくといいかもしれない)。んで、あとは適当にpackageとライブラリ指定してコンパイルすればOKっぽい。んだけど、普通にlibperl58.a指定するとなんでかリンクがうまくいかない。何かすごいアホなことな気がするんだけど、なんだろうな〜


注意
・コンパイルが非常に時間かかる。
・cygwin-bash上ではうまく実行できない
・GHCiでインタラクティブに開発できない

1つ目と3つ目はものっそいやる気なくなる。



できれば、GHCi上で、":set -package Pugs"で使えるようにしたいんだけど、うまくいかない。ぬー、なんとかやりようはあるんじゃないかと思ったりするんだけど。 unknown symbol `__imp__Perl_win32_init`。しらべんのめんどくせ。Ubuntuの方も

>ghci -lperl DynaLoader.o
Loading package base-1.0 ... linking ... done.
Loading object (static) DynaLoader.o ... done
Loading object (dynamic) perl ... done
final link ... ghc-6.4.2: DynaLoader.o: unknown symbol `_GLOBAL_OFFSET_TABLE_'
ghc-6.4.2: linking extra libraries/objects failed

はぁ・・・対策はそのうち。ここらへんも障害になりそうだ



Parrotとは。Parrotとか聞いたことすらなかった
http://www.namikilab.tuat.ac.jp/~sasada/prog/parrot-intro.html

第一に、とにもかくにも、Parrot って何？　なんでみんなこれについて大騒ぎしてんの？　えーと。もしあなたが箱の中で暮らしてでもいなければ、Perl コミュニティが新しい Perl のデザインと、その実装をしているのを知ってるよね。新バージョンのPerl、言語と実行処理系の両方。

すいません、箱の中で暮らしていたようです。まあ、Perl6のVMになるらしい。ふーん、どうでもいいや。なんかcompileがどうとかあるのは、要するにParrotのコード吐くのか。中間言語のJakoがいいな


で、Pugsのソースを眺めた。重要なのは、Exp,Val,Evalモナド(多分)。Expの定義はなんか2箇所にあるけど、Pugs.AST.Internalsにある方が本物っぽい

-- | Represents an expression tree.
data Exp
    = Noop                              -- ^ No-op
    | App !Exp !(Maybe Exp) ![Exp]      -- ^ Function application
                                        --     e.g. myfun($invocant: $arg)
    | Syn !String ![Exp]                -- ^ Syntactic construct that cannot
                                        --     be represented by 'App'.
    | Ann !Ann !Exp                     -- ^ Annotation (see @Ann@)
    | Pad !Scope !Pad !Exp              -- ^ Lexical pad
    | Sym !Scope !Var !Exp              -- ^ Symbol declaration
    | Stmts !Exp !Exp                   -- ^ Multiple statements
    | Prim !([Val] -> Eval Val)         -- ^ Primitive
    | Val !Val                          -- ^ Value
    | Var !Var                          -- ^ Variable
    | NonTerm !Pos                      -- ^ Parse error
    deriving (Show, Eq, Ord, Typeable) {-!derive: YAML_Pos!-}

ふむ。Haskellの値をPugsの値に変換したり、逆も簡単にできそうな感じ

decision procedure for intuitionistic propositional logic

http://d.hatena.ne.jp/m-a-o/20070122#p6
で知った、Roy Dyckhoffによる、直観主義命題論理のdecision procedureというのを調べて見た。Roy DyckhoffによるContraction-Free Sequent Calculi for Intuitionistic Logicという論文があるようなのだけど、入手できない。1992年とかの論文らしいので、意外と新しい。

論文は入手できなかったけど、200~300行程度のコードを見つけた
Some benchmark formulae for intuitionistic propositional logic
経由で
http://www.dcs.st-and.ac.uk/~rd/logic/nonmac/LJT.pl.html
Prologだけど。読めぬ・・・

諦めてDjinnのコードでも読もうかと思ったけど、別に直観主義命題論理なんてどうでもいいなーと思ってやめた

narrowingとresiduation

http://alohakun.blog7.fc2.com/blog-entry-635.html
カレー好きとしては黙ってられないというか、narrowingとresiduationって聞いたこともなかったので。普通に論文読んでも全く分からなかったが
Functional Logic Languages: Basic Concepts and Operational Semantics
あたりで何か理解できた気分に。


まあ、例えば関数型言語っぽく

app [] ys = ys
app (x:xs) ys = x:(append xs ys)

とかいう定義があったら、これを等式系と見て、項書換え計算で、appを計算できたりするというのは多分40年以上前から知られてたんではないかと思うけど、与えられたリストlsに対して、app x y = lsとかapp x (app y z) =lsを満たす解を全部求めるとか、そういうことは項書換えではできない(リストの「分割」を全部求めてほげほげとか、リストの部分列を全部求めてほげほげという処理は、まああるんじゃないだろうか。もっとも、特に後者に関しては、ほんとに部分列を全部求めてたら、大富豪プログラミングとは、越後屋ぬしも悪よの〜ハハハというレベルでは済まなくなる気がするけど、そのへんはあとで考える)。

で、例えば、app x y = [1,2]という面白くない例を取ると、まず、解きたい等式の左辺と上の定義の等式の左辺と単一化を行って(パターン変数とかは衝突しないように適当にリネームされてるとする)、成功するものを見つける。"app x y"と"app [ ] ys"は、{x=[ ],y=ys}によって、単一化可能で、定義から、
app x y = app ys = ys
になる。で、次に、ys=[1,2]を解けばいいのだけど、これはもう解けてるので、{x=,y=[1,2]}という解が見つかる。"app x y"は"app (x:xs) ys"とも単一化可能で、{x=(x':xs),y=ys}とすると、
app x y = app (x':xs) ys = x':(app xs ys) = [1,2]
となる。で、(:)は型構成子なので、単純なパターンマッチで、{x'=1,app xs ys = [2]}が解くべき式となる。でまあ、以下同様にしていくと、結局、{(x,y)=([ ],[1,2]),([1],[2]),([1,2],[ ])}と解ける。という感じのが、naiveなnarrowingの手続きらしい。ただ普通にやると、重いだけでなく、簡単に停止しないコードがかけてしまうというので、何か色々ある模様。まあ、SLD-resolutionと変わらないという気がする。SLD-resolutionと大体等価だけど、Normalizing Innermost Narrowingというのは、SLD-resolutionより探索空間が狭くて、pure logic programmingより効率がいいぜheheとか書いてあるっぽい

あと、上のような等式系は、Prologに翻訳できる(flattening)と書いてあるけど、逆にprologコードは、述語(?というのか、用語がわからんが)をBool値の関数と見なせば、

append([],L,L).
append ([W|X1],Y,[W|Z1]) :- append(X1,y,Z1).

だったら

append [] x y = (x==y)
append (w1:x1) y (w2:z1) = (w1==w2) && (append x1 y z1)

とかで、等式系に変換できる気がする。まあ、prologとか知らんけど。cutとかはよくわからんので、そういうのがあると無理かもしらんが、上のPrologコードでresolutionするのと、下のコードでnarrowingするのとは等価なんでないだろうか


residuationについては、ページ数が殆ど裂かれてないせいか、よく分からなかった。というか、FLPって関数と述語がわかれてんのか？それまで関数のみで書いてたので、些か唐突な感が。リンク先に載ってる例は

0+x = x
s(x)+y = s(x+y)
nat(0)
nat(s(x)) <= nat(x)

で、+が関数、natが述語、0とsは型構成子ということらしい。

x+0=s(0),nat(x)
を解く場合には、narrowingだと、"x+0"と単一化可能なのは、"0+x"と"s(x)+y"で、前者は、0+0=s(0)となって失敗する。後者は、x=s(0)という解を得る。更に、nat(x)は、nat(0)とnat(s(x))の両方と単一化可能で、前者からは、x=0となるが、これは解でないので失敗する。後者から同様にして、x=s(0)を得る、という手続きになる。で、residuationは、述語に対してしか単一化を行わないらしい。上の例だと、"x+0"と単一化可能な式を探さなくていいので、処理は半分で済む。効率はいいけど、一般には解が求まるとは限らない(imcomplete)ということらしい、たぶん