イネムリネズミ日記

_ Terence Tao さん、2008 IEEE Information Theory Society Paper Award 受賞おめでとう

Terence Tao ってどこかで聞いたことある名前だと思ったら、2006 年の Fields 賞受賞者じゃないか。しかも、経歴と仕事がものすごい人。2006 年はペレルマンとポアンカレ予想解決の話題で隠れてしまったけれども、Terence Tao さんは僕と同い年なんだよなー。

「数学者が工学に乗り込んでくると、良い仕事をしない」の反例がこれでまた一つ増えましたね。嬉しい限りです。Tao は世界一特別だと思うけれども。

受賞した論文は、Emmanuel Candès 氏との共著で、"Near-optimum signal recovery from random projections: Universal encoding strategies?", IEEE Trans. Info. vol. 52, no. 12, pp. 5406--5425, 2006 Dec.[PDF] ということで、ユニバーサル符号化のブレイクスルーみたいです。ユニバーサル符号化については、習ったけど私の研究対象ではないので、タイトルだけではよくわからない。後で読む。2004 年に投稿されて、2006 年末に受理とかどうなってるんだ。そんだけ理解するのが難しかったということか。

ところで、ブログ書いているのが今風の人らしくて好感持てる。Zornの補題から選択公理を導く(2009 Jan 28)とかは、授業に使っているんですかね。Tao さんからこういう授業を聞くというのはもったいないスギというか、ありがたいというか。今後はフィードを読むことにする。あと、著書を一冊買いました。数学とは無縁の人にもお勧めできるかもしれないエントリを三つ見つけた：

• On time management
• On writing
• Write a rapid prototype first

いや、読み返してみたけど、数学的読者向けか。rapid prototype について、論文や文章を書くことと、ソフトウエア開発手法がリンクするところは何にでも通用することではないかと思う。逆に言えば、こういう仮説が成り立つかもしれない：「ソフトウエア開発に特化したテクニック（他、たとえば文章を書くことや掃除洗濯料理など、に応用が利かない）は、実はソフトウエア開発にも役に立っていない」

_ 人工言語 ロジバン Lojban

解析表現文法 PEG を調べていたら、Lojban に出会った。

Lojban is a constructed, syntactically unambiguous human language based on predicate logic. (発音は EUC-JP で書けないので省略、強調は筆者による)

[Lojban - Wikipedia, the free encyclopediaより引用]

形式仕様記述 formal specification はさまざまなものがあるが、どれも現場では役に立たない。机上の空論である。というのは、実際に用いられている仕様は曖昧 unambiguous で、論理 logic に基づくというよりは、むしろ自然言語に基づいているからである。

形式仕様記述を現場に投入しようと躍起になっている人々は、自然言語で書かれた仕様から形式仕様記述に翻訳して無駄足を踏んでいる（情報が欠落したり、矛盾が生じたり、元々の仕様から外れたりする）。

あるいは、仕様を記述する人間に形式仕様記述を教育すればよいと考えている人もいる。しかし、実装が人間や環境を含む以上、形式仕様記述という砂場から飛び出てしまうのだから、そういう努力は無駄なことだ。

これは知ってはいけない事実なのだが、形式手法を呪文のように唱えている人は皆この実態をわかっているのである。では、なぜ無駄だと知りつつも、それを繰り返すのか？この宇宙に永久機関はないが、日本という狭い国には永久機関が存在するのですよ。そして、その永久機関からエネルギーを取り出せば…これはこの世の熱力学の法則に背く大罪である。おお神様。

さて、理想と現実がマッチしないという現象は、工学ではありふれた出来事である。この世は理想郷でもなければエデンの園でもない。そこで、ネズミーランドはいかがですか、という発想が必要になる。

38. Now it came to pass, as they went, that he entered into a certain village: and a certain woman named Martha received him into her house.
39. And she had a sister called Mary, which also sat at Jesus' feet, and heard his word.
40. But Martha was cumbered about much serving, and came to him, and said, Lord, dost thou not care that my sister hath left me to serve alone? bid her therefore that she help me.
41. And Jesus answered and said unto her, Martha, Martha, thou art careful and troubled about many things:
42. But one thing is needful: and Mary hath chosen that good part, which shall not be taken away from her.

[OT Luke 10:38-42より引用]

にもかかわらず、「理想郷を作れ」という仕事に就いているポスドク人はあわれである。ひとつのことをすればよいのに、あれこれせわしなく働いた挙句、それは無意味なのだ。まるで Martha のようだ。

Lojban は状態を持つ Packrat parser で解析できると主張する人がいる。もしそうならば、少なくともバラバラにすることはできる。意味は曖昧さが残るが、自然言語ほど曖昧ではない。工学的には、ここらへんで満足するというのも一手なのではなかろうか。実際、 IBM でそういうことを考えている人がいたようだ。

あなたが Lojban を学ぶべき 7 つの理由

1. 新しい思考法を習得する
2. 自然言語から離れ、「仕様」に関して考察が深まる
3. 計算機に命令できるようになる(ソフトウエアとは別の意味で)
4. 奇妙な言語ではなく、形式的な言語である
5. 表現能力が高い
6. 単純さゆえに、学ぶことは難しくない
7. 楽しい！

[Pin Stack: Top 7 Reasons to Learn Lojbanより引用]

ロジバンを学ぶ人を Lojbanist というそうである。ここから始めよう。Everyday Lojban.

coi lojbo tadni

_ まつもとゆきひろが語る「ビューティフルコード」×「プログラマ35歳定年説」を聞いてないんだけど、どんなコードを見せていたのだろうか？

聞きに行った人と、それに対する反応を見つけた。

聴講記 - TrinityT's LABO

よいまとめ、すばらし。

まつもとゆきひろ氏が語る「ビューティフルコード」セミナーに行って来た

もひとつのまとめ。

まつもとゆきひろが語る「ビューティフルコード」×「プログラマ35歳 - siroi_mogutanの日記

写真たくさん、すばらし。

[Haskell] 思考の流れについて - mono-hate の週記

まつもとさんが言ったらしいフレーズ「思考の流れ」に関する考察と Haskell コードの添削

どのような発表をされたのか、もっと詳しく知るには、聞きにいった別の人にも聞いてみるか、あるいはまつもとさんが発表資料を公開していただかないとわからない。

思考の流れ

○をして、〜をして、〜をする

Ruby での例

puts ARGF.each.take（n)

Haskell での例

main = do cs < - getContents

putStr (unlines (take n lines cs))

[思考の流れ Ruby と Haskell の比較 : 聴講記 - TrinityT's LABOより引用]

僕の個人的な意見だが、この Haskell のコードは「ビューティフルではない」と思う。さらに、この二つのプログラムの振る舞いは異なるため、「Ruby だとこうなり、Haskell だとこうなる」という説明に出すのは不公平である。

すぐに気がつくことは、両者のコードに現れる n についての言及がなされていないという点だが、 n が何を意味するのかは発表のときに話されたのだろう。たぶん。僕が指摘したいのは違う部分である。

Haskell には Ruby の ARGF に相当するものはない。Haskell では、プログラムに与えられるコマンドライン引数が空か、そうでないかは厳密に区別する。まつもとさんが例にだしたと思われる getContents は Ruby の ARGF が空だったときの Ruby の振る舞いに対応する(標準入力からの読み込み)。このことは説明されたのであろうか。

発表に現れた Ruby のコードを尊重して、同様の振る舞いをするコードを Haskell で書いてみると次のようになる。

	
import Control.Monad (liftM, replicateM_, sequence)
import System.Environment (getArgs)
  
n :: Int
n = 5 -- 適当につけた
  
{- Haskell において、開発はトップダウンに行われる -}
main :: IO ()
main = getArgs                    -- (1) とりあえず引数を見るよね
         >>= argfEachTake         -- (2) Haskell で ARGF.each.take 
         >>= printUnlinedStrings  -- (3) refactoring の結果 puts
  
{- まず、空 [] のときだけ考えてコードを書く。
     コーディング作業を分割
   refactoring 前は argfEachTakeAndPuts :: [FilePath] -> IO () だった
-}
argfEachTake :: [FilePath] -> IO [String]
argfEachTake [] = replicateM_ (n-1) getLine >> sequence [getLine]  -- (4) ARGF が空のとき
argfEachTake fs = liftM (take n . lines) $ readFile $ head fs      -- (5) ARGF が空でない
  
{- (6) : (4) と (5) に共通して現れたプログラムを独立させた。
   ARGF が空のときも、そうでないときも、表示する部分は同じということに気がつく -}
printUnlinedStrings :: [String] -> IO ()
printUnlinedStrings = putStr . unlines

ここで明らかになるのは、Ruby の advantage/disadvantage と Haskell の advantage/disadvantage である。

Ruby の長所であり短所

長所:ARGF の特徴、かつ(Ruby 1.9 および 1.8.7 から) Enumerable#take が使えるようになった。それらのこと全てを知っている人は、まつもとさんが示したコードを書くことができる。短く、可読性が高い。

短所: (私の知る限り)プログラミング言語に、このような ARGF が用意されているのは Ruby だけ。しかも、Ruby のバージョンによっては動かないコード。ユーザは、Ruby のバージョンが変わるたびに学習しなければならない。そういう意味で、学習曲線はなだらかとは言いがたい。

Haskell の長所であり短所

長所: プログラムをトップダウンに開発できる。型安全。 ARGF の振る舞いを、空のときと空でないときで段階的にかつ安心して開発できる。重複するコードのリファクタリングが容易。DRY を黒魔術なしで実現。

短所: 記述量は増え、学習曲線は急である。特に、IO と遅延評価の両方が必要になるときの(今回のような場合)、コーディングは簡単ではない。ていうか、今回のコードを見る限り、Haskell を知らない人は絶望しそうである。こういうコードは Ruby 向きだなあ、と感じる。

もし、まつもとさんが ARGF の引き合いに getContents を出したのだとしたら、それはあまりにも不公平で、というのは ARGF はかくに複雑な仕様を持っているのだから、「言語組み込みの便利なマクロがあるにすぎない」ことで「コーディングにおける思考方法の説明」という筋違いなことをしている、と主張したい。

で、実際はどうだったんでしょうかね。Ruby も Haskell も好きなだけに気になります。

_ auto-complete.el for Haskell

The auto-complete.el changes your Emacs as an integrated development environment for not only some programming languages but also Haskell.

As you know, Emacs is a great editor. Recently, the auto-complete.el for editing codes as a minor mode has been developed by Matsuyama (the first release announce in his blog). He made a demo how it works.

The auto-complete minor mode is still alpha, but stable. Here, I show you some pictures, while editing a Haskell code with the helpful guidance.

The reason why the color of the current editing line is red because I also use another minor mode "flymake" for Haskell. This mode warns by the red color if the current line is not complete yet.

I recommend you the following minor modes with the haskell-mode. It makes easy and fast to write type-safe Haskell codes.

• flymake for Haskell as I said already.
• auto-insert-tkld.el for templates (Cabal, Setup.lhs and so on)
• Yet another snippet extension helps also the auto-complete mode.

Now I'll show you my .emacs setting how to use the auto-complete.el for Haskell. Too many and long keywords are embedded. It's a quite dirty hack. How about getting them on the fly?

We will discuss AutoComplete on the EmacsWiki and the IRC channel #haskell@freenode. Comments are welcome. Have a fun for writing codes with Emacs!

;; see also
;; http://www.enigmacurry.com/2009/01/21/autocompleteel-python-code-completion-in-emacs/
;; about auto-complete-mode for python-mode
(defconst my/haskell-reserved-keywords
  (sort 
   (list "case" "class" "data" "default" "deriving" "do" "else" "if" "import" "in" "infix"
   "infixl" "infixr" "instance" "let" "module" "newtype" "of" "then" "type" "where" "as"
   "qualified" "hiding")
   #'(lambda (a b) (> (length a) (length b))))
  "Reserved keywords in Haskell.")
  
(defconst my/haskell-defined-types
  (sort 
   (list "Bool" "False" "True" "Char" "String" "IO" "IOError" "Maybe" "Just" "Nothing"
   "Either" "Right" "Left" "Ordering" "LT" "EQ" "GT" "Integer" "Int" "Ratio" "Float"
   "Double" "Complex")
   #'(lambda (a b) (> (length a) (length b))))
  "Defined types in Haskell.")
  
(defconst my/haskell-defined-classes
  (sort 
   (list "Eq" "==" "/=" "Ord" "compare" "max" "min" "<=" ">=" "ReadS" "ShowS" "Read"
   "read" "readsPrec" "readList" "showsPrec" "show" "showList" "Enum" "succ" "toEnum"
   "fromEnum" "enumFrom" "enumFromThen" "enumFromTo" "enumFromThenTo" "Functor" "fmap"
   "Monad" ">>=" ">>" "return" "fail" "Bounded" "minBound" "maxBound" "Num" "negate" "abs"
   "signum" "fromInteger" "Real" "toRational" "Integral" "quot" "rem" "div" "mod"
   "quotRem" "divMod" "toInteger" "Fractional" "recip" "fromRational" "Floating" "pi"
   "exp" "log" "sqrt" "**" "logBase" "sin" "cos" "tan" "asin" "acos" "atan" "sinh" "cosh"
   "tanh" "asinh" "acosh" "atanh" "RealFrac" "properFraction" "truncate" "ceiling" "floor"
   "RealFloat" "floatRadix" "floatDigits" "floatRange" "decodeFloat" "encodeFloat"
   "exponent" "significand" "scaleFloat" "isNan" "isInfinite" "isDenormalized"
   "isNegativeZero" "isIEEE" "atan2" "gcd" "lcm" "^^" "fromIntegral" "realtoFrac")
   #'(lambda (a b) (> (length a) (length b))))
  "Defined classes in Haskell.")
  
(defconst my/haskell-prelude-functions
  (sort
   (list ; "&&" "||"
         "not" "otherwise" "maybe" "either" "fst" "snd" "curry" "uncurry" "pred"
	 "round" "subtract" "odd" "mapM" "mapM_" "sequence" "sequence_" "=<<" "id" "const"
	 "flip" "until" "asTypeOf" "error" "undefined" "$!" "seq" "map" "++" "filter"
	 "head" "last" "tail" "init" "null" "length" "!!" "reverse" "fold" "fold1" "foldr"
	 "foldr1" "and" "or" "any" "all" "sum" "product" "concat" "concatMap" "maximum"
	 "minimum" "scanl" "scanl1" "scanr" "scanr1" "iterate" "repeat" "replicate"
	 "cycle" "take" "drop" "splitAt" "takeWhile" "dropWhile" "span" "break" "elem"
	 "notElem" "lookup" "zip" "zip3" "zipWith" "zipWith3" "unzip" "unzip3" "lines"
	 "words" "unlines" "unwords" "shows" "showChar" "showString" "showParen" "reads"
	 "readParen" "lex" "putChar" "putStr" "putStrLn" "print" "getChar" "getLine"
	 "getContents" "intract" "FilePath" "readFile" "writeFile" "appendFile" "readIO"
	 "readLn" "IOException" "ioError" "userError" "catch")
   #'(lambda (a b) (> (length a) (length b))))
  "Defined functions in GHC Prelude.")
  
(defconst my/haskell-ghc-modules
  (sort 
   (list 
   "Control.Applicative" "Control.Arrow" "Control.Category" "Control.Concurrent"
   "Control.Concurrent.MVar" "Control.Concurrent.QSem" "Control.Concurrent.QSemN"
   "Control.Concurrent.STM" "Control.Concurrent.STM.TArray" "Control.Concurrent.STM.TChan"
   "Control.Concurrent.STM.TMVar" "Control.Concurrent.STM.TVar"
   "Control.Concurrent.SampleVar" "Control.Exception" "Control.Exception.Base"
   "Control.Monad" "Control.Monad.Cont" "Control.Monad.Cont.Class" "Control.Monad.Error"
   "Control.Monad.Error.Class" "Control.Monad.Fix" "Control.Monad.Identity"
   "Control.Monad.Instances" "Control.Monad.List" "Control.Monad.RWS"
   "Control.Monad.RWS.Class" "Control.Monad.RWS.Lazy" "Control.Monad.RWS.Strict"
   "Control.Monad.Reader" "Control.Monad.Reader.Class" "Control.Monad.ST"
   "Control.Monad.ST.Lazy" "Control.Monad.ST.Strict" "Control.Monad.STM"
   "Control.Monad.State" "Control.Monad.State.Class" "Control.Monad.State.Lazy"
   "Control.Monad.State.Strict" "Control.Monad.Trans" "Control.Monad.Writer"
   "Control.Monad.Writer.Class" "Control.Monad.Writer.Lazy" "Control.Monad.Writer.Strict"
   "Control.OldException" "Control.Parallel" "Control.Parallel.Strategies" 
   "Data.Array" "Data.Array.Diff" "Data.Array.IArray" "Data.Array.IO"
   "Data.Array.IO.Internals" "Data.Array.MArray" "Data.Array.Paralell"
   "Data.Array.Paralell.Arr" "Data.Array.Paralell.Base" "Data.Array.Paralell.Lifted"
   "Data.Array.Paralell.PArray" "Data.Array.Paralell.Prelude"
   "Data.Array.Paralell.Prelude.Double" "Data.Array.Paralell.Int"
   "Data.Array.Paralell.Word8" "Data.Array.Paralell.Stream" "Data.Array.Paralell.Unlifted"
   "Data.Array.Paralell.Unlifted.Distributed" "Data.Array.Paralell.Unlifted.Paralell"
   "Data.Array.Paralell.Unlifted.Sqeuential" "Data.Array.ST" "Data.Array.Storable"
   "Data.Array.Unboxed" "Data.Bits" "Data.Bool" "Data.ByteString" "Data.ByteString.Char8"
   "Data.ByteString.Fusion" "Data.ByteString.Internal" "Data.ByteString.Lazy"
   "Data.ByteString.Lazy.Char8" "Data.ByteString.Lazy.Fusion"
   "Data.ByteString.Lazy.Internal" "Data.ByteString.Unsafe" "Data.Char" "Data.Complex"
   "Data.Data" "Data.Dynamic" "Data.Either" "Data.Eq" "Data.Fixed" "Data.Foldable"
   "Data.Function" "Data.Generics" "Data.Generics.Aliases" "Data.Generics.Basics"
   "Data.Generics.Instances" "Data.Generics.Schemes" "Data.Generics.Text"
   "Data.Generics.Twins" "Data.Graph" "Data.HashTable" "Data.IORef" "Data.Int"
   "Data.IntMap" "Data.IntSet" "Data.Ix" "Data.List" "Data.Map" "Data.Maybe" "Data.Monoid"
   "Data.Ord" "Data.Ratio" "Data.STRef" "Data.STRef.Lazy" "Data.STRef.Strict"
   "Data.Sequence" "Data.Set" "Data.String" "Data.Time" "Data.Time.Calendar"
   "Data.Time.Calendar.Easter" "Data.Time.Calendar.Julian" "Data.Time.Calendar.MonthDay"
   "Data.Time.Calendar.OrdinalDate" "Data.Time.Calendar.WeekDate" "Data.Time.Clock"
   "Data.Time.Clock.POSIX" "Data.Time.Clock.TAI" "Data.Time.Format" "Data.Time.LocalTime"
   "Data.Traversable" "Data.Tree" "Data.Tuple" "Data.Typeable" "Data.Unique"
   "Data.Version" "Data.Word" "Debug.Trace" 
   "Distribution.Compat.ReadP" "Distribution.Compiler" "Distribution.InstalledPackageInfo"
   "Distribution.License" "Distribution.Make" "Distribution.ModuleName"
   "Distribution.Package" "Distribution.PackageDescription"
   "Distribution.PackageDescription.Check" "Distribution.PackageDescription.Configuration"
   "Distribution.PackageDescription.Parse" "Distribution.ParseUtils" "Distribution.ReadE"
   "Distribution.Simple" "Distribution.Simple.Build" "Distribution.Simple.Build.Macros"
   "Distribution.Simple.Build.PathsModule" "Distribution.Simple.BuildPaths"
   "Distribution.Simple.Command" "Distribution.Simple.Compiler"
   "Distribution.Simple.Configure" "Distribution.Simple.GHC" "Distribution.Simple.Haddock"
   "Distribution.Simple.Hugs" "Distribution.Simple.Install"
   "Distribution.Simple.InstallDirs" "Distribution.Simple.JHC"
   "Distribution.Simple.LocalBuildInfo" "Distribution.Simple.NHC"
   "Distribution.Simple.PackageIndex" "Distribution.Simple.PreProcess"
   "Distribution.Simple.PreProcess.Unlit" "Distribution.Simple.Program"
   "Distribution.Simple.Register" "Distribution.Simple.Setup"
   "Distribution.Simple.SrcDist" "Distribution.Simple.UserHooks"
   "Distribution.Simple.Utils" "Distribution.System" "Distribution.Text"
   "Distribution.Verbosity" "Distribution.Version"
   "Foreign" "Foreign.C" "Foreign.C.Error" "Foreign.C.String" "Foreign.C.Types"
   "Foreign.Concurrent" "Foreign.ForeignPtr" "Foreign.Marshal" "Foreign.Marshal.Alloc"
   "Foreign.Marshal.Array" "Foreign.Marshal.Error" "Foreign.Marshal.Pool"
   "Foreign.Marshal.Utils" "Foreign.Ptr" "Foreign.StablePtr" "Foreign.Storable"
   "GHC.Arr" "GHC.Bool" "GHC.Conc" "GHC.ConsoleHandler" "GHC.Desugar" "GHC.Environment"
   "GHC.Err" "GHC.Exts" "GHC.Generics" "GHC.Handle" "GHC.Ordering" "GHC.PArr" "GHC.Prim"
   "GHC.PrimopWrappers" "GHC.Tuple" "GHC.Types" "GHC.Unicode" "GHC.Unit"
   "Language.Haskell.Extension" "Language.Haskell.Lexer" "Language.Haskell.ParseMonad"
   "Language.Haskell.ParseUtils" "Language.Haskell.Parser" "Language.Haskell.Pretty"
   "Language.Haskell.Syntax" "Language.Haskell.TH" "Language.Haskell.TH.Lib"
   "Language.Haskell.TH.Ppr" "Language.Haskell.TH.PprLib" "Language.Haskell.TH.Quote"
   "Language.Haskell.TH.Syntax" 
   "Network" "Network.BSD" "Network.Socket" "Network.URI" "Numeric"
   "Prelude"
   "System.CPUTime" "System.Cmd" "System.Console.Editline" "System.Console.Readline"
   "System.Console.GetOpt" "System.Directory" "System.Environment" "System.Exit"
   "System.FilePath" "System.FilePath.Posix" "System.FilePath.Windows" "System.IO"
   "System.IO.Error" "System.IO.Unsafe" "System.Info" "System.Locale" "System.Mem"
   "System.Mem.StableName" "System.Mem.Weak" "System.Posix" "System.Posix.Directory"
   "System.Posix.DynamicLinker" "System.Posix.DynamicLinker.Module"
   "System.Posix.DynamicLinker.Prim" "System.Posix.Env" "System.Posix.Error"
   "System.Posix.Files" "System.Posix.IO" "System.Posix.Process"
   "System.Posix.Process.Internals" "System.Posix.Resource" "System.Posix.Semaphore"
   "System.Posix.SharedMem" "System.Posix.Signals" "System.Posix.Signals.Exts"
   "System.Posix.Temp" "System.Posix.Terminal" "System.Posix.Time" "System.Posix.Types"
   "System.Posix.Unistd" "System.Posix.User" "System.Process" "System.Random"
   "System.Time" "System.Timeout" 
   "Test.HUnit" "Test.HUnit.Base" "Test.HUnit.Lang" "Test.HUnit.Terminal"
   "Test.HUnit.Text" "Test.QuickCheck" "Test.QuickCheck.Batch" "Test.QuickCheck.Poly"
   "Test.QuickCheck.Utils" "Text.Html" "Text.Html.BlockTable"
   "Text.ParserCombinators.Parsec" "Text.ParserCombinators.Parsec.Char"
   "Text.ParserCombinators.Parsec.Combinator" "Text.ParserCombinators.Parsec.Error"
   "Text.ParserCombinators.Parsec.Expr" "Text.ParserCombinators.Parsec.Language"
   "Text.ParserCombinators.Parsec.Perm" "Text.ParserCombinators.Parsec.Pos"
   "Text.ParserCombinators.Parsec.Prim" "Text.ParserCombinators.Parsec.Token"
   "Text.ParserCombinators.ReadP" "Text.ParserCombinators.ReadPrec" "Text.PrettyPrint"
   "Text.PrettyPrint.HughesPJ" "Text.Printf" "Text.Read" "Text.Read.Lex" "Text.Regex.Base"
   "Text.Regex.Base.Context" "Text.Regex.Base.Impl" "Text.Regex.Base.RegexLike"
   "Text.Regex.Posix" "Text.Regex.Posix.ByteString" "Text.Regex.Posix.String"
   "Text.Regex.Posix.Wrap" "Text.Show" "Text.Show.Functions" "Text.XHtml"
   "Text.XHtml.Debug" "Text.XHtml.Frameset" "Text.XHtml.Strict" "Text.XHtml.Table"
   "Text.XHtml.Transitional" "Trace.Hpc.Mix" "Trace.Hpc.Reflect" "Trace.Hpc.Tix"
   "Trace.Hpc.Util" 
   "Unsafe.Coerce") #'(lambda (a b) (> (length a) (length b))))
  "GHC modules.")
  
;; see also the latest GHC manual 
;; http://www.haskell.org/ghc/docs/latest/html/users_guide/pragmas.html
(defconst my/haskell-ghc-pragmas
  (sort 
   (list "LANGUAGE" "OPTIONS_GHC" "INCLUDE" "WARNING" "DEPRECATED" "INLINE" "NOINLINE"
   "LINE" "RULES" "SPECIALIZE" "UNPACK" "SOURCE")
   #'(lambda (a b) (> (length a) (length b))))
  "GHC pragmas.")
  
;; see also the latest GHC manual 
;; http://www.haskell.org/ghc/docs/latest/html/users_guide/flag-reference.html#id2631364
(defvar my/haskell-ghc-options
  (list "OverlappingInstances" "IncoherentInstances" "UndecidableInstances" "Arrows"
	"ForeignFunctionInterface" "Generics" "ImplicitParams" "ImplicitPrelude"
	"MonomorphismRestriction" "MonoPatBinds" "RelaxedPolyRec" "ExtendedDefaultRules"
	"OverloadedStrings" "GADTs" "TypeFamilies" "ScopedTypeVariables" "TemplateHaskell"
	"QuasiQuotes" "BangPatterns" "CPP" "PatternGuards" "ViewPatterns" "UnicodeSyntax"
	"MagicHash" "NewQualifiedOperators" "PolymorphicComponents" "Rank2Types"
	"RankNTypes" "ImpredicativeTypes" "ExistentialQuantification" "KindSignatures"
	"EmptyDataDecls" "ParallelListComp" "TransformListComp" "UnliftedFFITypes"
	"LiberalTypeSynonyms" "TypeOperators" "RecursiveDo" "PArr" "RecordWildCards"
	"NamedFieldPuns" "DisambiguateRecordFields" "UnboxedTuples" "StandaloneDeriving"
	"DeriveDataTypeable" "GeneralizedNewtypeDeriving" "TypeSynonymInstances"
	"FlexibleContexts" "FlexibleInstances" "ConstrainedClassMethods"
	"MultiParamTypeClasses" "FunctionnalDependencies" "PackageImports"))
(defvar my/haskell-ghc-no-options
      (mapcar '(lambda (n) (concat "No" n)) my/haskell-ghc-options))
(defvar my/haskell-ghc-language-options
  (sort (append nil my/haskell-ghc-options my/haskell-ghc-no-options)
	#'(lambda (a b) (> (length a) (length b))))
  "GHC Language options.")
  
(defvar my/ac-source-haskell
  '((candidates 
     . (lambda () 
	 (all-completions ac-target 
			  (append nil 
				  my/haskell-defined-types
				  my/haskell-defined-classes
				  my/haskell-reserved-keywords
				  my/haskell-prelude-functions
				  my/haskell-ghc-modules
				  my/haskell-ghc-pragmas
				  my/haskell-ghc-language-options
				  '("-fglasgow-exts")
				  )))))
  "Sources for Haskell keywords.")
  
(add-hook 'haskell-mode-hook
	  '(lambda () (auto-complete-mode 1)
	     (make-local-variable 'ac-sources)
	     (setq ac-sources '(ac-source-yasnippet
				ac-source-abbrev
				ac-source-words-in-buffer
				my/ac-source-haskell))
	     nil))

Well, the above settings are completely dirty, but work fine.

_ 今週末(2009-02-21(Sat),22(Sun)の予定)

このブログの予定表(一番下)にも書いてあるのですが、今週末はおもにプログラミングの日とします(予定)。

2009-02-21 Ruby勉強会 in Matsue.rb#1

松江で Ruby の勉強会があるそうです。でも、松江は遠いので行きません。さいわい、Skype Chat を用意してくださるようなので、それに参加します。現在 1.9.1 で用いられているパーサの改良を行うことを考えています。

Ruby 1.9.1 のパーサは GNU bison を用いて作られています。が、ご存知のように Ruby の文法は、プログラミング言語の意味で「曖昧 (ambiguous)」です。曖昧な文法は、パーサジェネレータである bison の得意分野ではありません(書けないわけではありませんが、制約がつきます)。

曖昧な文法のためのパーサとして「parser combinator」を用いる、という別の方法があります。parser combinator の欠点は、スピードが遅いということですが、その後の研究によりその欠点が改善されつつあります。

• Graham Hutton and Erik Meijer, "FUNCTIONAL PEARLS -- Monadic parseing in Haskell", Journal of Functional Programming, Cambridge University Press, vol. 8, no.4, p.437--444, Jul, 1998.
• Pieter Koopman and Rinus Plasmeijer, "Efficient combinator parsers", In Implementation of Functional Languages, Springer LNCS vol.1995, p.122--138, 1999.
• Richard A. Frost and Rahmatullah Hafiz, "A new top-down parsing algorithm to accomodate ambiguity and left recursion in polynomial time", ACM SIGPLAN Notices, Vol. 41, Issue 5, p. 46--54, May, 2006.
• (他にもいくらでもあるけど、省略)

ということで、「C 言語で書く parser combinator library」を作ろう、という計画をたててみました。parser combinator は、関数型言語で書けば難しいことはないのですが、手続き型言語で書こうとするとさまざまな困難が予想されます。言語には対象物との相性とか向き不向きがあるのです。名古屋で STDIN に言い換えたところで、大事なところが抜けているのです。

このように、C 言語で、ってところが多少無理があるのですが、野心的にも実際に実験を行った方がいます。Parser combinators in C (Draft paper), Nov. 22, 2000. 著者の Koen はお友達だし、ぼくはぼくなりに考えがあるので、これをもう少し進めてみます。

ここからもう一歩進んだ計画は、別の方法 - Packrat parsing - でパーサを書くというものです。これも、曖昧な文法のために parser combinator として実現します。Packratの利点は、字句解析を行う必要がないことです。欠点は、Packrat parser は曖昧な文法を扱うことができないということです。Parser combinator にするなら、この制約を外すことができますが、代わりに linear-time という性質は失われます。

• Bryan Ford, "Packrat parsing: a practical linear-time algorithm with backtracking", MIT Doctoral thesis, Sep, 2002.
• Robert Grimm, "Better extensibility through modular syntax", Conf. Programming Language Design and Implemenntation, Proc. 2006 ACM SIGPLAN, p. 38--51, 2006.
• Alessandro Warth, James R. Douglass and Todd Millstein, "Packrat parsers can support left recursion", ACM/SIGPLAN Workshop Partial Evaluation and Semantics-Based Program Manipulation, Proc. 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p. 103--110, 2008.
• Roberto Ierusalimschy, "A text pattern-matching tool based on Parsing Expression Grammer", be accepted Software; Practice and Experience, (preprint 2008).
• (他にもいくらでもあるけど、省略)

この二つの計画とは独立して、もう一つ計画を持っています。一般に GLR にしろ、 PEG にしろ、「ある文法規則に新しい文法規則を追加したときに矛盾が生じたりしないだろうか」という心配があります。bison を使うと、 "shift/shiftreduce/reduce conflict" や、"shift/reduce conflict" というメッセージがでることがありますが、それです。この問題を、文法規則を静的に解析して発見しようという取り組みがあります。

• Sylvain Schmitz, "Modular syntax demands verification", Laboratoire I3S, Université de Nice - Sophia Antipolis, Rapport de rechereche ISRN I3S/RR-2006-32-FR, Oct. 2006.
• Sylvain Schmitz, "Conservative ambiguity detection in context-free grammers", Proc. 34-th International Colloquium, ICALP, Springer LNCS vol. 4596, p. 692--703, Jul. 2007.
• Sylvain Schmitz, "An experimental ambiguity detection tool", Elecronic Notes in Theoretical Computer Science, vol. 203, issue 2, p.69 -- 84 , Apr. 2008.
• (他にもいくらでもあるけど、省略)

とりあえず、読んだ論文のうちいくつかを紹介してみましたが、実装するとなると、半日ではとても終わらないでしょう。私は、文法解析の専門家でもなければ、職業的プログラマでもありません。興味に向いた何かをすることになると思います。そのために、手ごろな題材を手持ちのポケットから３つ選んでみました。土曜日は、これのどれかをほげります。

2009-02-22 Haskell 勉強会 実践編

Whitespace のインタプリタをいじるらしい。寒かったり、雨だったりしたら行かない。すまんね。予報だと晴れて温かくなるらしいので、それを期待したい。

題材は素朴にパターンマッチで実装されているので、Error monad 使うなり、VM を StateT monad (IO の上に乗せる)なり、パーサに Parsec や Alex & Happy もしくは Frisby などを使えばよいのではないか。あるいは、コンパイラつくったり、Whitespace で Whitespace のインタプリタを書いたり、AOBench などしたらよいと思う。

両日とも、PC の前にいるときはデスクトップを ustream 配信する予定であります。Emacs が全画面を占めるという退屈な画面が延々と流れるだけだと思うけど、見たい人は見ればいいと思うよ。on/off のアナウンスは twitter で。絶望も勇気も好きにすれば。

_ Whitespace インタプリタをふつうに Haskell で書く

今日は１時間遅れて Haskell 勉強会 実践篇 に参加しました。

私：Tutorial とソースコードのセマンティクスが違うのではないか

すみません、ソースコードも Tutorial も正しいです。悪かったのは私の VirtualMachine だった。バグを全部取り、元祖の Examples が全て動くようになりました。これでいい、はず。ソースコード。中途半端感漂いまくりだ。もっと縮まるはず。悔しい。

元のコードは Haskell 98 だったので、こちらの実装は Alex と Happy を使うことにした。これで、パーサはさっと書きあがる。私の書いたコードの特徴を挙げるとしたら、以下の通り:

• スタックやヒープには Data.Map を用いた (無限長を楽に書き、高速に動かすため)
• それらの内部状態はステートモナドを使った
• 入出力を伴うので IO モナドのモナド変換子も使った

エラー処理をさぼってるので、パーサの時点ではじかれると悲しいことになる。これはすぐに直せるんだけど、仮想マシンのバグを取るのに予想外に手こずってしまったので、やらず。バグというか、Whitespace の仕様をちゃんと理解していないというか、その両方。

それから、ステートモナドについて、こういうアホな間違いをたくさんしていた。これはやりがちなので今後気をつける。自動的に発見するツールがいるかもしれない：

modifyMoge :: StateMonad ()
modifyMoge 
  = do s <- get
       modify (\t -> t { memberOfT = foo s , anotherMember = bar t })

型は通ってしまうので、 flymake は警告を出さないが、再帰的にメンバを更新することはめったにないのである。最後の bar t が本来は bar s になっていなければならなかった。

他のバグは、ジャンプの飛んでいくところが一つずれているだとか、計算の前と後ろが逆だったりとか、そういうしょうもないものばかり。だが、それが積み重なると、バグの修正に一日もかかってしまうという。今回はテストをサボって Debug.Trace (trace) を使いまくってしまった。今は反省している。