C# でランク N 多相

C#Sprache というパーサーコンビネーターがあるのだが、最近そいつを継続渡しスタイル(continuation passing style; CPS)にしてやろうと、Haskell のパーサーコンビネータattoparsec を参考にいじっていた。

そこでこういう型があった。

newtype Parser i a = Parser {
      runParser :: forall r.
                   State i -> Pos -> More
                -> Failure i (State i)   r
                -> Success i (State i) a r
                -> IResult i r
    }

この型単品では C# への翻訳で困らないのだが、次のような関数があると困ったことになる。

plus :: Parser i a -> Parser i a -> Parser i a

そこで StackOverflow で質問してなるほどなーと思ったのでまとめてみる。

newtype は実質型の別名なので(明示的な相互変換が要るが)、plus 型は次のように理解できるわけだ。

plus :: (forall r.
            State i -> Pos -> More
         -> Failure i (State i)   r
         -> Success i (State i) a r
         -> IResult i r)
     -> (forall r.
            State i -> Pos -> More
         -> Failure i (State i)   r
         -> Success i (State i) a r
         -> IResult i r)
     -> (forall r.
            State i -> Pos -> More
         -> Failure i (State i)   r
         -> Success i (State i) a r
         -> IResult i r)

ややこしいので今回の話題に本質的でない部分を省くと、次のようになる。(意味のあるものではなくなっているが。)

f :: (forall r. r -> r)
  -> ()

この型は C# でいうところの void F<R>(Func<R, R> f) なのではないかと思うかもしれないが次のような場合に問題がある。

static void Main(string[] args)
{
    F(Id);
}

T Id<T>(T t) { return t; }

void F<T>(Func<T, T> f) { // This is not sound!
    System.Console.WriteLine("{0}", f(1));
    System.Console.WriteLine("{0}", f("one"));
}

F<T>(Func<T, T>) を使うところで推論できないとエラーが出、じゃあと T の型を指定しようとすると int にしても string にしても問題があるわけだ。

f の型は F を適用するところでは一意に決めず多相のままにしておきたいわけだ。こういうのをランク 2 多相という。(上述の F はランク 1 多相。)

で、C# はそんな多相をサポートしてないしなんとか回避策がないものかと考えてパッっと出てこなかったんで StackOverflow に聞いてみたら次のような回答が得られた。

using System;

interface IGenericSameTypeFunction
{
    T Apply<T>(T input);
}

public class SimpleIdentityFunction : IGenericSameTypeFunction
{
    public T Apply<T>(T input) => input;
}

class Test
{    
    static void F(IGenericSameTypeFunction function)
    {
        Console.WriteLine(function.Apply(1));
        Console.WriteLine(function.Apply("one"));
    }

    static void Main()
    {
        F(new SimpleIdentityFunction());
    }
}

なるほどなぁ。部分型多相を使うことでランク N 多相を実現するのだな。

“meaningless REX prefix used” “use of REX.w is meaningless”

コマンドプロンプトPowerShell でプログラムを実行したときに次のようなエラーが出て困っていた。

[0x7FFE822C2B00] ANOMALY : meaningless REX prefix used
[0x7FFE85B3DDA0] ANOMALY : use of REX.w is meaningless (default operand size is 64)

REX プレフィックスとは何ぞや。

ロングモードでは、64ビット化するにあたり、16ビット時代から存在した1バイトのinc/dec命令であるinc reg16/dec reg16命令(op 0x40〜0x4f)を廃止してこの位置にプリフィックスを再定義した。結果として、4ビット分のビットフィールドが確保された。 http://www.wdic.org/w/SCI/REX%E3%83%97%E3%83%AA%E3%83%95%E3%82%A3%E3%83%83%E3%82%AF%E3%82%B9

なんか CPU 的に意味のないフラグが立ってるっぽいけど、一体なんでなのやら。

stack が ghc-pkg 辺りの出力をパースをしてるらしく、この出力のせいでエラーになってずっと困ってた。

とりあえずググってみたけど、判然とした原因はいまいちなく、ディスプレードライバーが原因やらウイルス対策ソフトが原因やらという感じだったので、試しに導入していたウイルスセキュリティを無効にして Windows Defender を有効にしてみた。

そうしたらメッセージが出なくなった。原理はよく分かってないけど、一事例として。

関係と代数的データ型との相互変換についての妄想 その3

思い付き その2

class QueryUser ? where
    queryUser :: (?) => Key -> MonadDB User

instance QueryUser ? where
    -- queryUser :: (HasFriends ?) => Key -> MonadDB User
    query =instance QueryUser ? where
    -- queryUser :: (HasName ?) => Key -> MonadDB User
    query = …

userFriends :: (HasFriends ?) => User -> [User]
userName :: (HasName ?) => User -> [User]

ふむー?userFriendsuserName を使った項は、まぁ (HasFriends ?, HasName ?) になりそうな気はするな。HasFriends ?? に入る型と対応する値が要る気がする。

そもそもそれぞれでインスタンス実装できるのか?

ConstraintKinds?

“When matching, GHC takes no account of the context of the instance declaration (context1 etc).” ってあるしムリっぽい。 https://downloads.haskell.org/~ghc/7.0.1/docs/html/users_guide/type-class-extensions.html#instance-overlap

GHC 8.0 だとその記述なくなってるな。 https://downloads.haskell.org/~ghc/8.0.2/docs/html/users_guide/glasgow_exts.html#overlapping-instances

とはいえムリっぽいのは変わりなさそうなんで、次は普通にモナドの方針で行ってみるか。

関係と代数的データ型との相互変換についての妄想 その2

思い付き その1

型レベルのリストをクエリー函数に与えてやる。(DataKinds が有効)

data Attr = Id | Name | Friends
data User = User { id :: Int, name :: String, friends :: [User] }
query :: Proxy '[??] -> Key -> MonadDB User
userFriends :: Proxy '[Friends] -> User -> [User]

リストだとダメだなーって気付いた。勝手に型の和が取られるわけじゃないからね。

それはそれとして、分からないところが2点。

1つは上記のコードで query の型の ?? って書いているところをどう書けばよいか。やりたいことは「?? の部分に入るのは 'Attr カインドの任意の型」ということを示したい。

しばらく寝かせて思い付いたけど KindSignatures を有効にして下記でいけるっぽい。

data ProxyAttr (t :: [Attr]) = ProxyAttr

もう1つは、下記のをうまいこと推論してくれないのなんでだ。stack --resolver lts-8.12 exec -- ghci -fprint-explicit-kinds -XDataKinds にて。

後から気付いた ProxyAttr を使うとエラーにならなかった。

ghci> :m + Data.Proxy
ghci> data Attr = Id | Name | Friends
ghci> data User = User { id :: Int, name :: String, friends :: [User] } deriving (Show)
ghci> :{
ghci| userFriends :: Proxy '[Friends] -> User -> [User]
ghci| userFriends _ _ = [User 1 "Ada" []]
ghci| :}
ghci> bob = User 2 "Bob" []
ghci> let p = Proxy in userFriends p bob

<interactive>:9:30: error:
    • Couldn't match type*’ with ‘[Attr]’
      Expected type: Proxy [Attr] ((':) Attr 'Friends ('[] Attr))
        Actual type: Proxy * ((':) Attr 'Friends ('[] Attr))
    • In the first argument of ‘userFriends’, namely ‘p’
      In the expression: userFriends p bob
      In the expression: let p = Proxy in userFriends p bob

Proxy に型注釈してやると大丈夫。

ghci> let p = Proxy :: Proxy '[Friends] in userFriends p bob
[User {id = 1, name = "Ada", friends = []}]

どっちにしろリストの戦略は破綻してるのでボツ。

制約の方に情報を乗せないとあかん気がしている。

関係と代数的データ型との相互変換についての妄想 その1

OR マッパーみたいな、関係*1とデータ型との相互変換が機械的にできたら嬉しいなという話。

シンプルなのは簡単だしすでにできる。例えば次のような関係がある場合*2

var user base relation {
  id integer,
  name string,
}
key { id };

var friends base relation {
  user1 integer,
  user2 integer
};

これを単に次のようなデータ型に変換するのはいくらかのライブラリーで実現できる。

data User = User { id: Int, name: String }

data Friends = Friends { user1: Int, user2: Int }

しかし、実際のところ欲しい型というのは次の通りでこれは機械的にできるのはなさそう。(ちゃんとは調べてないのであったら教えてほしい。)

data User = User { id: Int, name: String, friends: [User] }

よくあるクラスベースのオブジェクト指向言語なら Friends ゲッターの中でクエリー発行すればいいんだけど、同じことを Haskell ですると IO まみれになるしできれば純粋な函数にしたいよなー。

public class User {
  public readonly int id;
  public readonly string name;
  readonly IList<User> friends;
  public IList<User> Friends {
    get {
      if (friends == null) friends = …;
      return friends;
    }
  }
  public User query(int id) { … }
}

妄想としては、そのフィールドが使われてるかの情報を型に乗っけることで、DB からの取得時にどれを取ってくればいいか分からないかなーと。

do
  user <- queryUser 1 -- 何らかの queryUser :: Int -> MonadDB User みたいな函数があるとして
  return $ friends user

friends 函数の型を GetFriends user => user -> [User] みたいにしてやることで型推論によって queryUser 函数の型クラス制約にも GetFriends が付いて実装を変えられないかなぁと。

うーんでも型クラスのありなしでは実装は変えられないかー。なんとか型に情報乗せないとダメかな。

続きはまた後日。

*1:ここでいう関係は関係代数の用語としての関係です。

*2:Tutorial D の記法に従ってますが、パーサーにかけたことがないのでまちがってるかもしれない。

技術書典2にサークル参加します 「Haskell Yesod 本」

4月9日日曜日にアキバ・スクエアにて開催される技術書オンリー同人誌即売会技術書典2」にサークル「趣味はデバッグ……」として参加します。

冬コミで頒布した『遠回りして学ぶ Yesod 入門』の誤字脱字等を修正して組版を改善したものを持っていきます。

新作はちょっと間に合うか……

内容

内容は、下記となります。

  • ビルドツール Stack
  • 効率のよい文字列の扱い
  • Haskell の言語拡張
  • コンパイル時計算 Template Haskell
  • Web Application Interface とは
  • 簡単な Yesod の解説
  • ロガー用 Middleware を作る

詳しい内容は見本誌で確認ください。

ロガー用 Middleware の章は @syocy さんに書いていただきました。

紙面版仕様

  • 表紙フルカラー
  • 本文モノクロ
  • B5 判
  • 76ページ(表紙込み)

電子版

BOOTH にて販売中です。誤字脱字等修正済みです。

紙面版購入者は対面電書にて誤字脱字等修正版をダウンロードできます。

価格

価格は下記の通りとなります。

  • 現地販売(現金・クレジットカード)
    • 紙面+電子版
      • 1000円
    • 電子版
      • 800円
      • ダウンロード URI を渡します
  • オンライン販売
    • 電子版
      • 1000円

クレジットカード決済は、Square 社が対応しているものに限ります。

スペース

スペースは「う-04」です。

techbookfest.org

よろしくお願いします!

Yesod で1ページに複数個フォームがある場合は identifyForm を使う

resolver lts-5.4 で確認。

問題

1ページに複数個フォームがある場合、runFormPost はそれぞれのフォームの区別をしてくれません。どういうことかというと、例えば下記のような2つのフォームを利用するとします。

data AFormData = AFormData Text
aForm :: Html -> MForm Handler (FormResult AFormData, Widget)
aForm = renderDivs $ AFormData <$> areq textField "A Text" Nothing

data BFormData = BFormData Text
bForm :: Html -> MForm Handler (FormResult BFormData, Widget)
bForm = renderDivs $ BFormData <$> areq textField "B Text" Nothing

この2つのフォームを1つのページに配置し、ブラウザーでアクセスしどちらか一方のフォームに “Hello” とでも入力し送信します。すると runFormPost aFormrunFormPost bForm も返り値の FormResult Xxx 型の部分が FormSuccess xxx となり、xxx の部分はそれぞれ AFormData "Hello"BFormData "Hello" となります。

これは困ります。

解決

identifyForm を使います。

identifyForm
  :: Monad m
  => Text -- ^ Form identification string.
  -> (Html -> MForm m (FormResult a, WidgetT (HandlerSite m) IO ()))
  -> (Html -> MForm m (FormResult a, WidgetT (HandlerSite m) IO ()))

第1引数にユニークな文字列を指定してください。

aForm = identifyForm "a-form" $ renderDivs $ AFormData <$> areq textField "A Text" Nothing

これで、対応するフォームに入力されたときだけ runFormPostFormSuccess を返すようになります。

参考

Issue yesod-web/yesod #649