2018-02-11

アマゾンで江添亮の詳説C++17が予約可能になった

江添亮の詳説C++17 | 江添 亮 |本 | 通販 | Amazon

2017年に発行された最新のC++17の新機能をあますところなく解説した私の本、江添亮の詳説C++17がアマゾンで予約可能になったようだ。

本の内容はすでにGitHubで公開している。ライセンスはGPLv3だ。プログラミングの参考書は自由なライセンスで提供されるべきである。

https://github.com/EzoeRyou/cpp17book

次は入門書とTips集を書きたい。

2018-02-09

新しいプログラミング言語を学ぶということ

去年の暮から一ヶ月ほど、Haskellを学んでいる。目的は色々あるが、まったく新しいプログラミング言語を学ぶ経験をもう一度するのが最大の目的だ。

C++17の新機能を余すところなく解説した「江添亮の詳説C++17」は3月に出版される。C++20にはまだ間がある。C++の入門書を書く絶好の機会だ。入門書というのは毎月腐るほど出版されているが、良書は少ない。結局、参考書の中で最も売れ行きが容易に予想可能なのは、最も読み手がいるであろう入門者向けの本であり、入門書の出版がいたずらに増え、粗製濫造されているとみえる。入門書は上級者は読まないので適切な批判もされにくいのでこのような惨状になっているのだろう。

私の入門書はそのような悪書にしたくない。しかし、私はすでにC++の初心者ではないし、C++の初心者がつまづく点がわからない。というより、ここしばらくまったく新しいプログラミング言語を学んだことはない。C++以外にもPython、JavaScript、bashなどを必要に迫られて書き散らすこともあるが、相当古いJavaScript以外は真剣に学んだことがない。

これはよくない。入門書を書く前に、少し時間を割いてでも、全く新しいプログラミング言語に入門すべきだ。そのための言語としてはHaskellがふさわしい。と、こう考えた。

なぜHaskellなのか。HaskellはC++とは全く違った言語だからだ。例えばJavaScriptは表面的にはC++とかなり似た文法を持っているので、全く新しいプログラミング言語を学ぶ目的には使えない。PythonやRubyは文法的には少し違うが、すでに触ったことがあり、それほど苦労した覚えがないのでやはりだめだ。Scalaは汚らわしいJavaの実行環境を私の神聖なメインPCにインストールしたくないために不適だ。

Haskellを学ぶには、Learn you a Haskell for great goodという本が良いらしいので、早速買い求めて読み始めた。この本はとても軽くて読みやすい本だ。そしてユーモアが多い。真面目な参考書に個々までのユーモアは必要なのかと疑問に思うぐらいに多いのだが、しかし全くの初心者が読む本には、これぐらいのユーモアが必要なのではないかと思う。

というのも、だ。私自身、久しぶりに経験して驚いているのだが、全く新しいことを学ぶのは途方もなく疲れる上に非効率的な作業だからだ。不思議なもので、それほど難しいはずはない内容なのに、なぜかなかなか頭に入らない。一日に本を読む時間は何時間もあるが、短期的にいくら時間をかけても内容が頭に入ってこない。一晩寝るなどして時間を開けないとわずか数ページの内容も読み進めることができない。文字を読むことはできるにしても、その内容が理解できず、また残らないとしたら意味がない。

そういう賽の河原のような不毛な作業を続けるには、ユーモアがとても効果的だということがわかる。ただでさえ退屈な作業なのに、ユーモア欠落症患者によって書かれた文章まで読まされるのでは続くものも続かない。

私が書く入門書にはユーモアが必要だということがわかる。

プログラミング言語を学ぶには、プログラミングの実行環境が手元にあったほうがよい。しかしHaskellの実行環境はあまりすぐれているとは言い難い。Haskell PlatformはDebian系ならばapt一発で入るのでまだいいのだが、クールなキッズは皆使うというStackは、私の手元ではまともに動いた試しがない。

そもそもだ。CabalもStackもてんでなっていない。パッケージマネージャと名乗るのもおこがましい。だいたい管理できていない。パッケージを追加することはできるが削除できないのだから。削除するにはどうするか? すべてのパッケージを削除して最初からインストールをやり直す。富豪にもほどがある。Stackもだめだ。結局管理できていない。管理できないからどうするか? とりあえずプロジェクトごとに特定のディレクトリ下に全部環境を構築しよう。富豪にもほどがある。

そういうわけで、Haskellの実行環境を整えるだけで1日を浪費した。C++の入門書では環境構築についてそれなりにページを割かなければならないと痛感した。具体的にはWindowsとMacはC++の学習に不適切なOSなのでGNU/Linuxを推奨したい。主要なディストロならC++の実行環境はデフォルトで入っている。

さて、そうこうしているうちに一ヶ月たち、流石にHaskellである程度のコードは書けるようになってきた。まだモナドについて完全に理解していないのだが、理解できるのも時間の問題だ。なんだ、Haskellも言うほど難しくはないではないか。

しかし、プログラミング言語の学習に当たってはこの時期が一番つらい。プログラミング言語の学習過程では、序盤はさっぱりわからず、中盤はすべてを理解したつもりになり、終盤でやはりわからない状況になる。

プログラミング言語の学習の中盤でつまづくのは、言語の以外な落とし穴だ。例えば私の場合は以下のような例で躓いた。

モナドを学び始めたので、確認がてら、以下のようなコードを書いた。

getContents >>= 複雑な式>>= putStr

しかしこれでは見づらいので、複雑な式を関数に分けることにした。複雑な式の中身は特に重要ではないので、ここでは単にpureとする。

-- こうすればカリー化によって引数を書く必要がないぞ。Haskellは完全に理解した。
f = pure
getContents >>= f >>= putStr

その後、fはそのままにしたまま別の処理を試したくなった。

f = pure
getContents >>= 別の式 >>= putStr

するとエラーになった。意味がわからない。

Haskellではf = pureと書くとfは多相にならず、型を決定しなければならないが、型を推論するための文脈がないのでエラーになるというのが原因だ。解決方法としては、fの型を明示的に書く、引数を書く、GHC拡張を使うなどの方法がある。

しかし、これは割と初心者が引っかかりやすい落とし穴ではないか。例えば以下のコードがなぜエラーになるか、初心者がわかるのだろうか。

f = pure
main = do
    print ( f 0 == Just 0 )
    print ( f 0 == [0] )

どうでもいいことだが、C++を長年やっていた人間として、f = pureとしたあとにf 0 == [0]と書くと、fはpureになり文脈上リストなのでf 0は[0]になるというのは割と驚きがあるし、リストという割と特別扱いされているような昨日でさえ、単なるライブラリ実装であり、(:)はデータコンストラクターにすぎないというのも驚きがある。

早くモナドを完全に理解したい。

2018-02-05

Haskellで書いてみたらC++の10倍遅かった

エレガントな解法、エレファントな解法 〜モンテカルロ法を添えて〜

コインを100回投げたうちに、表もしくは裏が連続して10回でる確率をモンテカルロ法で計算する。

なにはともかくC++で実装してみた。

template < typename Random >
bool coin_toss( const unsigned int try_count, const unsigned int length, Random & r )
{
    unsigned int count{} ;
    int prev{} ;

    std::uniform_int_distribution<> d( 0, 1 ) ;

    for ( unsigned int i = 0 ; i != try_count ; ++i )
    {
        int result = d(r) ;
        if ( result == prev )
        {
            ++count ;
            if ( count == length )
                return true ;
        }
        else
        {
            prev = result ;
            count = 1 ;
        }
    }

    return false ;
}

template < typename Random >
double monte_carlo( unsigned int try_count, Random & r )
{
    unsigned int count{} ;
    for ( unsigned int i = 0 ; i != try_count ; ++i )
    {
        if ( coin_toss( 100, 10, r ) )
            ++count ;
    }

    return double(count) / double(try_count) ;
}

int main()
{
    std::array<unsigned int, sizeof(std::mt19937)/sizeof(unsigned int)> c ; ;
    std::generate( std::begin(c), std::end(c), std::random_device{} ) ;
    std::seed_seq s( std::begin(c), std::end(c) ) ;
    std::mt19937 engine(s) ;

    for ( unsigned int i = 100 ; i != 1000000 ; i *= 10 )
    {
        auto r = engine ;
        std::cout << i << "\t : " << monte_carlo( i, r ) * 100.0 << "%\n" ;
    } 
}

C++11から高度な乱数ライブラリが使えるようになったのだが、現在、実行時に適切に初期化する方法に面倒なボイラープレートコードが必要だ。実行時に乱数で初期化してくれる機能が現在提案されている。

ところで、最近Haskellを学んでいるので、このコードをHaskellでも書いてみようと思った。

まずは乱数だ。コインの表裏はBoolで表現するとして、Haskellらしく無限の乱数リストを生成しよう。

coin_seq :: (RandomGen g) => g -> [Bool]
coin_seq gen = randoms gen

あとはこれをtake 100して一回分の試行とする。1000回試行したければ、drop 100したのを再帰的にtake 100すればよい。しかし、もっといい方法がある。要素数100の[Bool]が入ったリスト、つまり[[Bool]]を無限に作ればいい。そのリストをtake 1000すれば1000回の試行分になる。

split_n :: Int -> [a] -> [[a]]
split_n n seq = take n seq : split_n n (drop n seq)

さて、seq_n = take 100 $ split_n 100 (coin_seq gen)のようなリストseq_n :: [[Bool]]は作れた。あとは[Bool]に連続した要素がn個あるかどうかを調べるcoin_toss nと、それをリストのすべての要素に対して行うmonte_carloを書けばいいだけだ。

coin_tossが結果をBoolで返すとすると、とりあえずseq_nにcoin_tossをmapしてTrueだけfilterして、その結果のリストの要素数を数えれば、成功した試行数がわかる。あとは試行数で割って確率を求めればいいだけだ。

monte_carlo :: Int -> [Bool] -> Double
monte_carlo try_count seq = ((fromIntegral n) / (fromIntegral try_count)) * 100.0
    where
        seq_n = take try_count (split_n 100 seq)
        n = length . filter id $ map (coin_toss 10) seq_n

coin_toss len seqはInt -> [Bool] -> Boolな関数で、seqの中にlen個の連続したTrueもしくはFalseがあるかどうかを数えればよい。

いろいろ考えたが、まずgroup seqして連続した同じ要素を分割して[[Bool]]を作り、それぞれの[Bool]の要素数をいれたリスト[Int]をmapし、len以上の要素だけをfilterして、結果のリストに要素があればTrueを返す計算をすればいいのではないか。つまり、

has_contiguous_elems :: (Eq a) => Int -> [a] -> Bool 
has_contiguous_elems len seq = not $ null $ filter (>= len) $ map length (group seq)

coin_toss :: Int -> [Bool] -> Bool
coint_toss _ [] = 0
coin_toss len seq = has_contiguous_elems len seq

となる。全体的にはこうだ。

import System.Random
import Data.List

coin_seq :: (RandomGen g) => g -> [Bool]
coin_seq gen = randoms gen

split_n :: Int -> [a] -> [[a]]
split_n n seq = take n seq : split_n n (drop n seq)

has_contiguous_elems :: (Eq a) => Int -> [a] -> Bool 
has_contiguous_elems len seq = not $ null $ filter (>= len) $ map length (group seq)

coin_toss :: Int -> [Bool] -> Bool
coint_toss _ [] = 0
coin_toss len seq = has_contiguous_elems len seq

monte_carlo :: Int -> [Bool] -> Double
monte_carlo try_count seq = ((fromIntegral n) / (fromIntegral try_count)) * 100.0
    where
        seq_n = take try_count (split_n 100 seq)
        n = length . filter id $ map (coin_toss 10) seq_n

main = do
    gen <- getStdGen
    let s = coin_seq gen
        in mapM (\n -> putStrLn ((show n) ++ "\t : " ++ (show (monte_carlo n s)) ++ "%") )
                [100, 1000, 10000, 100000] 

このコードは動いた。ただし、最適化オプションを使っても、C++の10倍遅かった。

やはりlen個の連続した要素が存在するかどうかを調べるhas_contiguous_elemsが遅いのではないかと思い、これを再帰で実装することにした。

has_contiguous_elems' :: (Eq a) => Int -> [a] -> Bool 
has_contiguous_elems' _ [] = False
has_contiguous_elems' len (x:xs) =
    if count >= len
        then True
        else has_contiguous_elems' len $ dropWhile (== x) xs
    where count =  1 + (length $ takeWhile (== x) xs)

この実装に差し替えたところ、実行速度はC++の9倍遅かった。

すると、他の部分もリストからリストを生成するという記述をやめて、再帰で実装すればもう少し早くなるのだろうか。

そして思うのは、同様のリストからリストを清々するような処理は、所詮リストのメモリーサイズがキャッシュに収まる程度なので、C++で書くとHaskellより早いのではないかとも思ったが、まだ試していない。

2018-02-04

年収1200万円と2億の資産でできる贅沢はパトロネージュ

以下のはてな匿名ダイアリーの記事が注目を集めている。

贅沢な生活って何が楽しいの?(追記しました

独身34歳男、年収900万+配当収入300万くらい。

贅沢の良さがわからない。

家は相続で貰ったので家賃無し。金融資産は相続したものと合わせて2億を超えた。

生活費は月に12万くらい。配当込みで年間800万以上金が増えていく。

別に金を使うのが嫌いなわけではない。ただ、使う気がおきない。

この増田は1200万円の年収と2億の資産を保有している。増田が過去に行った贅沢は以下の通り。

  • 飛行機のファーストクラス(100万円)
  • ホテルのスイートルーム(100万円)
  • オーダーメイドのスーツ(50万円)
  • 懐石料理(20万円)
  • ステーキ(10万円)

これらの贅沢がありきたりでつまらないのは当然だ。なぜならば、これらの贅沢には、何も1200万円の年収と2億円の資産は必要ないからだ。ただ100万円を貯金して一度に使えばできる程度の贅沢だ。100万円を1年ぐらいかけて貯金するのであれば、34歳男の平均年収である400万円でも可能だ。

せっかく贅沢をするのであれば、年収1200万円と2億円の資産をもって初めて可能になる贅沢をするべきだ。では増田の境遇ではじめて可能になる贅沢とは何か。多額の借金と長期的な支出だ。そして、究極的にはぱとろネージュと呼ばれる行為、すなわち食客を抱えることだ。

多額の借金

増田のような境遇にない我々凡人は、それほど多額の借金ができない。大抵の凡人が生涯に負うことのできる多額の借金は、奨学金と住宅ローンぐらいなものだろう。しかも学費や住宅といった目的が限定されている。

しかし増田は違う。1200万円の年収と2億円の資産を担保に、1億や2億の借金ができるだろう。借金ができる環境はとても贅沢だ。借金で得た金を使って利息を上回る利益を出すことができれば借金をした以上の価値を生む。例えば増田は自分の興味がある事業を立ち上げることができる。ただし、これには利息を上回る利益を出すことができずに資産を失うリスクはある。

長期的な支出

増田が例に挙げている贅沢は、短期的な一度きりの支出ですむものだ。100万円を払ってファーストクラスに乗ったりスイートルームに泊まったりするのはいかにも贅沢に思えるが、一回払うだけでその後は何の支出もいらない。

しかし増田は違う。増田は月に50万円ぐらいの支出を長期的に続けることができる。長期的に支出を行えるのは、我々凡人には不可能な贅沢だ。では、長期的な支出が必要な贅沢とは何か。

答えは人だ。増田は長期的に人をフルタイムで雇うことができる。増田は秘書を雇い日常の雑事をすべて押し付けることもできる。増田の時間は貴重である。増田がファーストクラスやスイートルームや懐石料理を楽しむとして、その予約作業という雑事は、わざわざ贅沢な増田の手をわずらわす作業ではない。秘書にやらせればよい。

そして、古来より最高の贅沢とされる人への支出がある。パトロネージュ、すなわち食客を抱えることだ。

増田にはより発展してほしい芸術や学問はないだろうか。もっと具体的に書こう。自分の気にいる漫画や小説を読みたい。自分の気にいるゲームで遊びたい。ある自由なソフトウェアに自分の望みの機能を追加したい。ある病気を根絶する研究が進んでほしい。ある技術がもっと発展してほしい。しかし、増田は芸術や学問を極めることはできない。増田に絵や詩人の才能はなく、プログラミングはできず、医学博士や工学博士として研究に身を捧げる人生も送りたくはないとする。しかし、世の中には芸術や学問に身を捧げたいと願う天才はいる。増田はそのような天才を食客として衣食住の不便をなくし、芸術や学問を追求させることができる。

増田が増田を書くことができるのは、コンピューターが発展したからだ。ところで現代のコンピューターの発展はチャールズ・バベッジの研究に負うところが大きい。もしチャールズ・バベッジがコンピューターの研究に打ち込まなければ、コンピューターの発展は数十年は遅れていただろう。チャールズ・バベッジは裕福な家の出身ではあったが、コンピューターの研究のためにパトロンが必要だった。

この話の教訓としては、自分が楽しむためにカネを使えないのであれば、他人が楽しむためにカネを使ってみてはどうか。その結果として芸術や学問が発展するのであればこれ幸い。

2018-02-02

江添ボドゲ会@2月11日

だいたい毎月行っている自宅ボドゲ会を2月11日に開催します。

江添ボドゲ会@2月11日 - connpass

2018-01-28

CoinCheckとNemの騒動から暗号通貨について思うこと

何から語ろうか。まずCoinCheckにしよう。CoinCheckという暗号通貨の取引所が、NEMを大量に盗まれたという事件だ。私の法と技術の理解では、盗むというのは物理的な物が伴うので映画泥棒という言葉が法的に正しくないのと同様に違うのではないかと思うんだが、まあそこは置いておこう。ここでは単に悪意としておく。

これについて、自分のNEMが悪意されたのでCoinCheckに金を返せと叫んでいる人間のほとんどは、そもそも筋が悪い。もし、Bitcoinが花開いた暗号通貨が技術的に正しく運用されていたならば、そんなことは起こりようがなかったのだ。つまり、しっかり自分の手元の信頼できる環境でフルノードを実行し、物理的なコンピューターの前には武装した警備員を配備するべきだったのだ。自分でフルノードの実行もせずに、秘密鍵すらCoinCheckに知らせ、やれ盗まれたのなくなったのというのは、紙に印刷してある資料を電子媒体で送れといったら、紙をスキャンした画像をPDFやEXCELに貼り付けて送ってくるバカにも等しい愚かな行為だ。非科学的なアメリカ人は神によって通貨の価値を信じているが、我々科学の信奉者は計算力に裏打ちされた通貨を信じる。計算力の強いやつは正しい。それが暗号通貨の基本的な理念ではなかったのか。

世間では秘密分散共有によるマルチシグネチャーがどうのとか、ホットウォレットがどうのと言っているが、正直本質ではない。秘密鍵を分散させようと、エアギャップさせようと、守りが弱ければ、銃で武装した数人によって脅迫、拷問された末に情報を吐き出すのがオチだ。

さて、今回の事件の記者会見において、NEMのロールバックという面白い概念が提唱された。ロールバック、取引をなかったことにするという救済措置、これについて考えてみよう。

そもそもBitcoinから始まった、あまり正確ではないが俗にブロックチェーンと呼ばれる暗号通貨は、取引の上に取引を重ねる仕組みになっている。

例えば、アリス, ボブ, チャーリーによる取引が、アリス→ボブ→チャーリーの順番で行われた場合、取引チャーリーの取引はボブの取引が成立した上に成り立っており、ボブの取引はアリスの取引が成立した上に成り立っている。

すると、アリスの取引をロールバックするには、ボブとチャーリーの取引もロールバックしなければならないことになる。

もう少し読者が実感できる例で考えてみよう。今週、読者は給料日だったのでまとまったカネを持っている。いまからオーガニック・スシを食べようと出かけたところだ。スシ・レストランに向かう途中の自販機で、財布の中に残っていた小銭で代用ジュースを一本買った。そこに急に、日本自治区政府からのエージェントがやってきて、君に告げる。「君、実は先週、JPYの大量盗難が発生した。ついては被害者救済のために、先週に遡ってJPYの取引をすべてロールバックしたい。全員の同意が必要だ。君が今買った代用ジュースの代金は戻ってくるが、君の給与振込はなかったことになる。被害者救済のため、模範的な一般市民である君はロールバックに同意してくれるだろうね? いや、カネはなくなるわけじゃない。一週間前の状態に戻るだけなんだ。あとで必要な取引は各人で復旧してもらいたい」

読者は同意するだろうか。

しかし、全員が同意するのであれば、アリスの取引だけをなかったことにして、ボブとチャーリーの取引は存在したことにできないだろうか。もちろんできる。それはハードフォーク(通貨の分裂)と呼ばれている。

しかし、我々は計算力によって通貨を信用していたのだ。アリスの取引を無効にすると、その取引に連なるボブとチャーリーの取引は計算では信用できなくなる。しかし、皆がアリスの取引を無効にすることに同意するならば、計算力を持つ皆が信用しているので正しい。自分だけアリスの取引は発生したと主張することは可能だが、過半数がその主張を拒否するのであれば、もはやその価値はなくなる。すると、世の中にはアリスの取引が存在した通貨と、存在しなかった通貨が生まれることになる。どちらを信じるのも自由だ。両方信じてもよい。こうして通貨は分裂する。

わかりやすい例で考えてみよう。日本自治区政府のエージェントは君にこう告げる。「いまから先週発生したJPYの大量盗難の取引を取り消す作業をする。君の財布の中身、銀行口座の金額、その他あらゆるカネとその記録を出し給え。我々がJPYの盗難だけがなかったように書き換えて君に返す。今のカネの状態はすべて破棄される。我々の書き換えは信頼できる。模範的市民の同志、同意してくれたまえ」

読者は同意するだろうか。

今回、このどちらの方法もNEM財団は取らなかった。仮に取ったとしても、マイナー達の同意を取り付けることはできないだろう。

かわりにNEM財団がやったのは、悪意を持った転送先のアドレスに、盗難を意味するモザイクを付与することだ。これはNEMの機能で、詳しくは調べていないが、ここで重要なのことは、アドレスにタグ付けができるということだ。NEM財団が今回悪意を持って取引されたNEMを含むアドレスにすべて盗難タグ付けをしていくことで、そのアドレスとの取引を利用者に拒否するよう促す。これにより、悪意ある者の持っているNEMは私情でかちを失うという目論見だ。なるほど、窃盗アドレスだと知った時点ですでに善意の第三者ではなくなるから、法的にも効果的だ。

しかし、果たしてそううまくいくだろうか。今回の犯人が次にやるべきことは、NEMを小額づつ、適当なアドレスに片っ端から送りつけることだ。大多数のアドレスが窃盗タグで汚染されてしまうと、もはや窃盗タグは意味を為さなくなる。第一、そのタグ付けは計算力に裏打ちされているのだろうか。権威がつけたタグを盲信しているだけではないのだろうか。そして、権威は果たして信用できるのだろうか。するとNEM自体の価値も、果たして信用できるのだろうか。

ただし、この考え方は面白い。我々は権威と計算力のハイブリッドの信用通貨を作り出してもいいのではないだろうか。

通貨の歴史を考える。貴金属のようなもともと価値のあるものが取引されていたのが、貴金属を直接取引するのは非効率的なので、貴金属と交換できる引換券で取引するようになった。しかし、実際に存在する貴金属以上の借金が市場に出回り、この仕組みは崩壊した。今の国家に裏打ちされた通貨は、貴金属と直接交換を保証されていない。

世の中には、存在自体が価値を持つ権威が存在する。国家もそうだが、宗教開祖とかアイドルとか秒速で億ぐらい稼ぐ人とかだ。そういう信者を何十万、何百万と持つ権威が、Bitcoinのような既存の暗号通貨をhard forkして独自の暗号通貨を始めるのはどうだろうか。何十万、何百万の妄信的な信者が価値を認めるのであれば、その暗号通貨には実際に価値が出るだろう。するとマイナーも一枚岩ではなくなるので、誰も過半数の計算力を持つことができずに、マイナーは単なるトランザクション処理係に成り下がる。何か問題が起きれば、権威がイスラム教で言うところのファトワー(見解)を出して訂正するのだ。

と考えてみると、VALUは案外いい線をいっていたのではないかとも思えてしまう。もちろん私は信用しないが。

こうして考えてみると、計算力と権威のハイブリット信用通貨は、国家から通貨発行権を奪還する試みであるとも言える。面白い世の中になってきたが、私としてはもっと現実的な価値を提供してほしい。例えばチューリング完全な計算を提供するとか、実際ストレージとして使えるとか、契約への同意が行われたことの記録ができるとかのブロックチェーンネットワークがほしい。

2018-01-20

物理的に近くの相手とファイル共有する方法

以下のようなTweetを読んだ。

インターネットが普及してからもうかれこれ20年以上もたつが、未だにこの問題が解決できていないのは嘆かわしいことだ。なのでこの問題を解決してみよう。

ただし、今回の問題は、大量に人が集まるため無線通信が難しい状況で、物理的に近い場所にいる相手とのファイル共有だ。

ファイルの転送自体は、前後にインターネット回線を確保してから行ってもいい場合は、どこかに暗号化したファイルを公開しておき、現場では復号鍵を配布すればいいだろう。

しかし、その場で直ちにファイルを転送したい場合はどうするのか。この場合、物理媒体による受け渡しは客が大勢来た場合にスケールせずに非現実的だ。

お互いBluetoothによる通信ができる状況であれば、Bluetoothによるファイル転送が使える。スマフォ端末やタブレット端末ならば、Bluetoothはほぼ確実にあるだろう。問題は、相手がBluetoothによるファイル転送に慣れていない場合、Bluetoothによるファイル転送の方法を説明する必要がある。これには相手の技術レベルにもよるが時間がかかるだろう。これもスケールしない。

もし転送したいファイルが2953バイト以下であれば、QRコードが使える。QRコードはディスプレイに映してもよいし、紙に印刷してもよい。圧倒的にスケールする。ただし、相手の端末にはカメラとQRコードリーダーが必要だ。ほとんどのスマフォとタブレット端末ならQRコードには対応しているだろう。しかし、PDFファイルはまず間違いなく2953バイトではすまないだろう。

やはり一番信頼できるのは有線LANだ。複数の客をさばくためにスイッチングハブを用意する。スマフォやタブレット端末にはEthernetポートがついていないことが多いが、USBポートが一つぐらいはあるだろうから、USBによるEthernetアダプターと各種USB変換ケーブルを用意しておけばよい。相手にIPアドレスを設定させる手間を省くためにDHCPサーバーも用意するとよい。家庭用のどんな格安ルーターでもDHCPサーバー機能はついているので難しくはない。

肝心のファイルを転送する方法であるが、FTP, SMB, HTTPなどが使える。SMBならば家庭用ルーターの機能として提供されていることも多い。しかし、相手への説明のコストを考えると、おそらくHTTPを使うのが一番楽だろう。ただし、URLが"http://192.168.0.100/file.pdf"などではやや相手にとってわかりにくいかもしれない。これを解決するには方法が2つある。ひとつはmDNSを使う方法で、IPアドレスのかわりに、hostname.localと書くことができる。ただし、これは相手の端末がmDNSに対応していなければならない。普通は対応しているはずだ。もう一つは、大抵のルーターについている静的DNSレコードなどと呼ばれている機能を使い、特定のIPアドレスに対してそのルーターのLAN側だけで通用するドメイン名をつけてしまうことだ。これなら相手の端末が万一mDNSに対応していない場合でも使える。

HTTPサーバーを用意する方法としては、転送したいファイルを置いたディレクトリで"python3 -m http.server"を実行するのが最も簡単だろうと思われる。

ただしこの方法は準備する機材がやや多い。ルーター、スイッチングハブ、LANケーブル、USB-Ethernetアダプター、各種USB変換ケーブル、HTTPサーバーを実行するコンピューター、知識を持った人間が必要だ。最後の知識を持った人間が一番用意しにくい。本来ならば、この2018年には全員がコンピューターリテラシーを持ち、この程度のことはできてしかるべきなのだが、スマフォが人をバカにしてしまった。

しかし、手のひらに乗るコンピューターでリアルタイム3DCGが描画でき、メモリ容量の単位がGBで数えられ、GB単位のストレージが数百円もせずに買えるこの2018年だというのに、なぜ身近の人間と物理的にファイルを転送するのにこんなに苦労しなければならないのだろう。

2018-01-19

3月に出版される「江添亮の詳説C++17」が予約できるようになった

3月に発売されるC++17の新機能をすべて解説した参考書、「江添亮の詳説C++17」が予約できるようになった。例えばアマゾンでは以下から予約できる。

江添亮の詳説C++17 | 江添 亮 |本 | 通販 | Amazon

「江添亮の詳説C++17」は、私の名前を冠するエゴの強い書名になっている。これは、次にC++によるプログラミング入門書を出したいために、名前をブランド化する試みだ。これがうまくいくかどうかはわからないが、

江添亮の詳説C++17は、GPLv3でライセンスされる。本のソースコードはGitHubで公開されている。まだもう少しは修正が聞くので、PRを投げてコントリビュートするなら今がチャンスだ。

https://github.com/EzoeRyou/cpp17book

GPLv3なので、本の組版に使ったtexのソースコードも公開されている。わたしはtexに詳しくはないが、できればビルドするためのドキュメントやMakefileなどを整備していきたい。

ちなみに、前回のC++11/14の参考書は、CC-BY-SAでライセンスされている。

https://github.com/EzoeRyou/cpp-book

すでに書いたように、次はC++によるプログラミングの入門書を書く。そのために色々と準備をしている。まず初心者の気持ちを再び味わうために、Haskellに入門した。Haskellは私の知っているプログラミング言語とはだいぶ違う言語であり、最初の数日はとても苦労した。なにより、環境構築が難しいということがわかった。次に書く入門書は、まず環境構築を丁寧に説明しなければならない。環境構築は慣れたものであれば何も意識しないが、何も知らない者にとっては意外と難しいものだということを身をもって学んだ。

C++の入門書はすでに多く書かれているが、いずれも古びてしまい、最新のC++からかけ離れてしまっている。

プログラミングの入門書を書く準備は整ったのだが、もう少しだけ寄り道をして、ブール代数を本格的に学ぼうと思っている。いままで表面的に浅くしか学んでいなかったが、この機会に深く学んでおきたい。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2018-01-17

今流行りの投機実行脆弱性の影響を一切受けないDOOM実装が公開される

https://github.com/xoreaxeaxeax/movfuscator/tree/master/validation/doom

このDOOMは条件分岐を一切使用していない。したがって今流行りの投機実行の脆弱性であるMeltdownやSpectreによる脆弱性は存在しない。

ちなみに、現代の性能のコンピューターで、1フレームの描画に7時間ほどかかるので、このDOOMで遊ぶには若干の忍耐力を要求される。しかし、脆弱性の完全な排除のためには若干のパフォーマンスの低下はやむを得ないところだろう。

このDOOM実装はオリジナルのDOOMのCコードに若干の変更を施して、M/o/Vfuscatorでコンパイルしたものだ。

https://github.com/xoreaxeaxeax/movfuscator

M/o/Vfuscatorとは、IntelのMMUがチューリング完全であることを利用したmov命令のみを使うC言語コンパイラーだ。

2018-01-14

第4回 ドワンゴからの挑戦状予選に参加してみた

第4回 ドワンゴからの挑戦状

第4回、ドワンゴからの挑戦状の予選が開催されたので参加してみた。

A - ニコニコ文字列判定

まずA問題。数字のみが使われた4文字の文字列sが入力として渡される。数字x, yが存在して、sがxyxyのとき"Yes"を、そうでなければ"No"を出力する。

入力は必ず4文字で、数字のみなので、変な文字列が渡される心配をしなくてもよい。

#include <iostream>

int main()
{
    std::string s ;
    std::cin >> s ;

    if ( s[0] == s[2] && s[1] == s[3] )
        std::cout << "Yes" ;
    else
        std::cout << "No" ;
}

A問題は毎回とても簡単な傾向にある。私は最初の提出が、問題文をさっと見ただけでコードを書いてしまったので、"YES", "NO"を出力するようにしてしまい、間違えた。

B - 2525文字列分解

文字'2'と'5'からなる文字列sが入力として与えられる。その文字列を"25"の1回以上の繰り返しからなる2525文字列に分割する。文字を分割するときには、文字の相対的な順序を変えてはならない。分割できる最小数はいくつか。

この問題はとても簡単に解決できる。

文字列sから"25"を取り除く操作を繰り返して、空文字列になるまでの操作回数を数えた結果が答えだ。つまり何回s/25//gできるかを数えればよい。もし、文字列に対してs/25//gを適用しても文字列が変わらなかった場合、その文字列は2525文字列に分解できないので、-1を出力する。

文字列から"25"を取り除いた結果の文字列は、もしまだ2525文字列が存在するのであれば、必ず”25"が出現する。なので文字列が空になるまで繰り返しs/25//gすればよい。

実際のところ、この問題はbashとsedで解くことができる。sedのみで解くことはできるだろうか。どうやらsedは入力文字列を工夫すればチューリング完全であり、sedでチューリングマシンやテトリスを実装したと主張するWebサイトがあるが、詳しく読んでいないので真偽はわからない。

http://www.catonmat.net/blog/proof-that-sed-is-turing-complete/

さてコードに落としていこう。処理は簡単だ。入力の文字列にs/25//gを何回適用できるか数えるだけだ。ただし、空文字列ではないのに適用できなくなった場合、2525文字列に分割できないので-1となる。

このような問題を解くときは、すでに問題を解き終えたと仮定すると書きやすい。

まず、この問題を解く関数solveがすでに存在すると仮定する。この関数solveは文字列をstd::string &型で与えると出力すべき数値をint型で返してくれるとする。引数に渡した文字列は書き換えられるものとする。すると、もうすでに我々は問題を解き終えたわけなので、入力を受け取って関数solveに渡して出力するだけのコードを書けばよいことになる。

#include <iostream>
#include <string>

int main()
{
    std::string s ;
    std::cin >> s ;

    std::cout << solve( s ) ;
}

これで入出力の部分は書いた。あとは関数solveを実装するだけだ。

このような問題を解くときは、すでに問題を解き終えたと仮定すると書きやすい。

まず、文字列に対してs/25//gを行う関数remove_nicoがすでに存在すると仮定する。この関数remove_nicoはstd::string &型の引数を取り、s/25//gする。もしひとつ以上の"25"を置換したのであればtrueを、そうでなければfalseを返す。すると、我々はすでにs/25//gを実装し終えたわけなので、あとはこの関数remove_nicoを何回文字列に適用できるか数えればよいだけだ。ただし、空文字列ではないのにfalseを返した場合は-1だ。

int solve( std::string & s )
{
    int count = 0 ;
    while ( s.size() != 0 )
    {
        bool removed = remove_nico( s ) ;
        if ( removed ) // 適用した
            ++count ;
        else // 適用できなかったので2525文字列ではない
            return -1 ;
    }
    return count ;
}

さて、残りは関数remove_nicoさえ実装すればよい。実装方法としては、単に文字列を先頭から自分自身にコピーしていき、"25"はコピーをスキップすればよい。

bool remove_nico( std::string & s )
{
    auto dest = std::begin(s) ;
    auto src = dest ;
    auto end = std::end(s) ;

    // 文字を自分自身にコピーする
    while ( src != end )
    {
        // 文字列"25"ならばコピーしないことで除去
        if ( *src == '2' && *std::next(src) == '5' )
        {
            std::advance( src, 2 ) ;
        }
        else
        { // コピー
            *dest = *src ;
            ++dest ;
            ++src ;
        }
    }

    // 一度も"25"を除去していなければfalseを返す
    if ( dest == end )
        return false ;

    // 除去した"25"の数だけ文字列のサイズを減らす
    auto shrink = std::distance( dest, end ) ;
    s.resize( s.size() - shrink ) ;

    return true ;
}

しかしこういう処理を自前で書くのは面倒だ。s/25//gをしたいのであれば正規表現ライブラリを使えばいいのではないか。そう思う読者もいるだろう。実際、正規表現ライブラリはC++11で追加されている。問題は、この手の問題に正規表現ライブラリを使うというのは鶏を割くのに牛刀を用いるほど過剰であり、遅いということだ。そもそも正規表現ライブラリは柔軟なパターンマッチができるもので正規表現文字列からパターンマッチのためのデータ構造を構築する。そして、std::regex_replaceによる置換はin-placeでは行われない。今回の置換は削除なので、in-placeに処理できるが、汎用的なライブラリであるstd::regexにそれを望むことはできない。

それでも書くとなると、以下のようになる。

bool remove_nico( std::string & s )
{
    std::regex re("25") ;
    std::string out ;
    // s/25//g
    auto end = std::regex_replace( std::back_inserter(out), std::begin(s), std::end(s), re, "" ) ;
    // 置換しなかった
    if ( s.size() == out.size() )
        return false ;

    s = out ;
    return true ;
}

ちなみに、手書きの"25"削除をatcoderに提出すると実行時間は最大のテストケースで5msぐらいだが、regex_replaceを使う実装を提出すると50msぐらいかかる。実に10倍も遅い。remove_nicoを手動でインライン展開して、reとoutをループの外に出して使いまわす付け焼き刃の最適化も試してみたが、実行時間は変わらなかった。その程度の最適化はコンパイラーがやっているらしい。

とはいえ、10倍遅くても制限時間内だからいいといえばいい。B問題程度はさっさと解くためにこうしてもよいが、それならもっと簡単な言語を使ってもよいということだ。

C問題以降は私には解けないのでもっと強い人の解説を参考にしてもらいたい。

ドワンゴ広告

ドワンゴからの挑戦状本選は2月3日。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2018-01-08

fair use権利を侵害するYouTubeのContent IDと戦うために著作権侵害するゲーム批評家の話

Game Critic Uses Brilliant Workaround For YouTube's Copyright Bullshit

Jim SterlingはYouTubeに動画を投稿するゲーム批評家である。動画によるゲーム批評を行うためには、ゲームの動画を引用する必要がある。しかし、ゲームの動画をYouTubeで引用すると困った問題に巻き込まれる。Content IDだ。

YouTubeではContent IDという仕組みが設けられている。これは、ある動画が著作権者の事前に登録した動画にマッチする場合、その動画に対して著作権者が著作権を主張し、取り下げたり、あるいは広告を出して収入を著作権者に回したりする仕組みだ。

しかし、批評のための引用は各国の法律で「著作権の例外」にあたり、著作権が及ばないと定められている。例えば日本では著作権法の第32条、アメリカ合衆国ではfair use、イギリスではfair dealingにより、著作権の例外であり著作権が及ばないと法的に定められている。ゲームの批評のために必要な範囲の引用には著作権が及ばない。著作権が及ばない以上、当然屈辱的なContent IDマッチによる取り下げや広告収入の横取りは、本来ならば著作権を不当に主張している人間による著作権侵害である。

しかし、Googleは人間が問題に対処しないことで悪名高い企業であり、不当なContent IDマッチの取り下げ要求にはまともに人間が対応しないためにどうしようもない。

さて、Jim Sterlingは収入をPatreon経由で得ており、YouTubeの広告には依存していない。そのため、YouTubeには広告を表示しない設定にしているのだが、ひとたびContent IDにマッチしてしまうと否応なく広告が有効にされてしまうという問題を抱えている。

そんなJim Sterlingが、最近自衛のために行っている行動は、Content IDの仕組みを逆手にとったものだ。上の動画では、任天堂の最近のゲームには新規性がなく過去の成功体験を引きずって使いまわしているだけだという旨の批評を行っている。しかし、動画にはなぜか、何の脈絡もなくMetal Gear Solid V, Grand Theft Auto V, Beyond: Two Soulsといったゲーム動画が使われている。これはなぜか。

Jim Sterlingは過去の自分の動画の中でContent IDにマッチした、既知のContent IDマッチ動画を意図的に使うことによって、動画に複数の大企業のContent IDマッチした著作権主張者を作り出している。複数の著作権主張者が同じ動画に著作権主張をした結果、どの著作権者の主張も認められず、結果として動画には収益横取り広告がつかなくなる。

しかし、その利用方法は正統な批評のための引用ではなく、結果的の著作権侵害ではある。32条、fair use, fair dealingといった著作権の例外の権利を保証させるために、あえて著作権侵害を起こす必要があるとは皮肉なものだ。しかしJim Sterlingによれば、結果的にこれが効果的な方法なのだという。

著作権は誤った考えであり私の生きているうちに世界的に破棄されるだろう。

2018-01-02

Clangをブラウザー上で実行してC++をWebAssemblyにコンパイルして実行するデモ

Clang In Browser

タイトル通り。WebAssemblyにコンパイルされたClangをブラウザー上で実行してC++をWebAssemblyにコンパイルしてブラウザー上で実行するデモ

この有名なトークが現実的になってしまう。核戦争によって滅んだ人類がブラウザーを共通プラットフォームとしてブラウザー上でOSを動かす話。

The Birth & Death of JavaScript

2017-12-26

Haskellのエラーメッセージについて

Haskellの実装であるGHCのエラーメッセージがわかりにくい。

例えば以下のコードがあるとしよう。

f p as@(x:xs) =
    if p x 
    then f p xs
    else as

main = return ()

この関数fはdropWhileと名付けてもいい関数だ。この関数の型は( t -> Bool ) -> [t] -> [t]だ。

ところで、この関数をうっかり書き間違えてしまい、then f p xsとすべきところを、第一引数のpredicateを渡し忘れ、then f xsとしてしまった場合を考えよう。

f p as@(x:xs) =
    if p x
    then f xs
    else as

main = return ()

このコードをGHC 8.0.2でコンパイルすると以下のようなエラーメッセージが表示される。


[1 of 1] Compiling Main             ( prog.hs, prog.o )

prog.hs:1:1: error:
    • Couldn't match type ‘t -> Bool’ with ‘[t]’
      Expected type: [t] -> [t]
        Actual type: (t -> Bool) -> [t] -> [t]
    • Relevant bindings include f :: [t] -> [t] (bound at prog.hs:2:1)

このエラーから読み取れる情報は、(t -> Bool)型は[t]型にマッチできないということだ。f p xsとすべきところをf xsとしてしまったのだから当然の話だ。pは(t -> Bool)でxsは[t]だ。

だが、このエラーメッセージからはどこの箇所が悪かったのか全然わからない。

しかし、このコードをGHC 7.10.3でコンパイルすると、以下のようなとてもわかり易いエラーメッセージが表示される。

prog.hs:3:10:
    Couldn't match expected type ‘[t]’ with actual type ‘[t] -> [t]’
    Relevant bindings include
      xs :: [t] (bound at prog.hs:1:11)
      x :: t (bound at prog.hs:1:9)
      as :: [t] (bound at prog.hs:1:5)
      p :: t -> Bool (bound at prog.hs:1:3)
      f :: (t -> Bool) -> [t] -> [t] (bound at prog.hs:1:1)
    Probable cause: ‘f’ is applied to too few arguments
    In the expression: f xs
    In the expression: if p x then f xs else as

prog.hs:3:12:
    Couldn't match expected type ‘t -> Bool’ with actual type ‘[t]’
    Relevant bindings include
      xs :: [t] (bound at prog.hs:1:11)
      x :: t (bound at prog.hs:1:9)
      as :: [t] (bound at prog.hs:1:5)
      p :: t -> Bool (bound at prog.hs:1:3)
      f :: (t -> Bool) -> [t] -> [t] (bound at prog.hs:1:1)
    In the first argument of ‘f’, namely ‘xs’
    In the expression: f xs

問題は3行目の10文字目と12文字目にあることがわかり、関連するbindingが一覧表示され、問題のある式とその式を含む式まで表示してくれる。これならわかりやすい。バージョンアップしてわかりにくくなるとはどういうことだ。

GHC 8.2.1ではエラーメッセージが改良されたそうだ。果たして直っているだろうか。

https://wandbox.org/permlink/leQ7uQaoN1eqBPLS

prog.hs:1:1: error:
    • Couldn't match type ‘t -> Bool’ with ‘[t]’
      Expected type: [t] -> [t]
        Actual type: (t -> Bool) -> [t] -> [t]
    • Relevant bindings include f :: [t] -> [t] (bound at prog.hs:1:1)
  |
1 | f p as@(x:xs) =
  | ^^^^^^^^^^^^^^^...

なるほど、Clangのプリティなエラーメッセージを真似ようという意思は感じられる。しかしその箇所は関数を宣言している箇所だ。関数の引数が間違っている箇所を指定してくれなければ意味がない。なぜGHC 7でできていたことがGHC 8でできなくなっているのだ。

Wandboxで最新のHEADも試したが、この問題はまだ解決していなかった。

さて、fの型を明示的に書くとエラーメッセージが変わるらしい。早速試してみよう。

f :: (t -> Bool) -> [t] -> [t]
f p as@(x:xs) =
    if p x
    then f xs
    else as

main = return ()

これをGHC 8.0.2でコンパイルすると以下のようなメッセージが表示される。

https://wandbox.org/permlink/307bjIWpMGZ3jJhO

prog.hs:4:10: error:
    • Couldn't match expected type ‘[t]’
                  with actual type ‘[t0] -> [t0]’
    • Probable cause: ‘f’ is applied to too few arguments
      In the expression: f xs
      In the expression: if p x then f xs else as
      In an equation for ‘f’: f p as@(x : xs) = if p x then f xs else as
    • Relevant bindings include
        xs :: [t] (bound at prog.hs:2:11)
        x :: t (bound at prog.hs:2:9)
        as :: [t] (bound at prog.hs:2:5)
        p :: t -> Bool (bound at prog.hs:2:3)
        f :: (t -> Bool) -> [t] -> [t] (bound at prog.hs:2:1)

prog.hs:4:12: error:
    • Couldn't match expected type ‘t0 -> Bool’ with actual type ‘[t]’
    • In the first argument of ‘f’, namely ‘xs’
      In the expression: f xs
      In the expression: if p x then f xs else as
    • Relevant bindings include
        xs :: [t] (bound at prog.hs:2:11)
        x :: t (bound at prog.hs:2:9)
        as :: [t] (bound at prog.hs:2:5)
        p :: t -> Bool (bound at prog.hs:2:3)
        f :: (t -> Bool) -> [t] -> [t] (bound at prog.hs:2:1)

ようやくGHC 7に戻ってきた。GHCはfの型を正しく推定できているのに、なぜ型tを明示的に書かなければ親切なエラーメッセージを出してくれないのだ。不親切にもほどがある。

さて、ではエラーメッセージが親切になったというGHC 8.2.1ではどうか。

https://wandbox.org/permlink/8j00LitIvUUuzDTM

prog.hs:4:10: error:
    • Couldn't match expected type ‘[t]’
                  with actual type ‘[t0] -> [t0]’
    • Probable cause: ‘f’ is applied to too few arguments
      In the expression: f xs
      In the expression: if p x then f xs else as
      In an equation for ‘f’: f p as@(x : xs) = if p x then f xs else as
    • Relevant bindings include
        xs :: [t] (bound at prog.hs:2:11)
        x :: t (bound at prog.hs:2:9)
        as :: [t] (bound at prog.hs:2:5)
        p :: t -> Bool (bound at prog.hs:2:3)
        f :: (t -> Bool) -> [t] -> [t] (bound at prog.hs:2:1)
  |
4 |     then f xs
  |          ^^^^

prog.hs:4:12: error:
    • Couldn't match expected type ‘t0 -> Bool’ with actual type ‘[t]’
    • In the first argument of ‘f’, namely ‘xs’
      In the expression: f xs
      In the expression: if p x then f xs else as
    • Relevant bindings include
        xs :: [t] (bound at prog.hs:2:11)
        x :: t (bound at prog.hs:2:9)
        as :: [t] (bound at prog.hs:2:5)
        p :: t -> Bool (bound at prog.hs:2:3)
        f :: (t -> Bool) -> [t] -> [t] (bound at prog.hs:2:1)
  |
4 |     then f xs
  |            ^^

なるほど、わかりやすくなっている。できればこれを型を明示せずともやってもらいたいものだ。

この記事はめるぽんさんの運営するWandboxという大変便利な本物のWebサイトを活用して書いた。今年もめるぽんさんに野菜をスポンサーしにいかなければならない。

Haskellでwordsを実装してみた

Haskellを学び始めたが、いまだにまともなコードを書くことができないでいる。理由は簡単で、まだ標準入出力が扱えないからだ。

標準入出力はUNIXでは極めて根本的な機能だ。標準入出力が扱えるようになればだいたいの処理はできると考えてよい。というのも、UNIXではパイプによって標準入出力の入力元と出力先を変えることができるからだ。パイプを使えば、ファイル操作やネットワーク操作をコードで表現する方法を知らなかったとしても、操作ができるようになる。

ところが、Haskellでは標準入出力を扱えるようになるまでが遠い。別に書けないわけではない。今でもHaskellでHello,Worldぐらい書けるし、特定の処理がしたいのであれば似たような入出力処理をするコードをどこからか探してきて改変することで目的のコードを作り出すことはできる。そういう意味では、現時点でもHaskellである程度のコードは書けるだろう。しかし、それでは言語を真に理解したことにはならない。言語の仕様を理解し、他人の書いたコードの改変ではなく、自分でコードを無から書けてこそ、自由自在のプログラミングが可能になる。

しかし、関数型言語であるHaskellでは入出力などという副作用を伴う処理には特別な配慮が必要らしく、いまだに標準入出力にたどり着いていない。

しかし、今までに学んだHaskellの知識を使って自力で何かを実装してみたいので、今回はwordsを実装することにした。

wordsは文字列を空白文字を区切り文字として分割した文字列のリストを返す。

> words "aaa bbb ccc"
["aaa","bbb","ccc"]

処理自体は簡単なはずなのだが、これをHaskellの流儀でやるのは割とだるい。アルゴリズム自体はすぐに思い浮かんだのだが、実際にコードを書くと、様々な問題に悩まされた。

takeWord s = takeWhile (not . isSpace) $ dropWhitespace s
dropWhitespace s = dropWhile isSpace s

words' [] = []
words' s =
    let
        word = takeWord s
        rest = drop (length word) $ dropWhitespace s
    in
        word:(words' rest) 

アルゴリズムとしては、文字列の先頭から連続する空白文字をdropし、空白文字が現れるまでtakeし、今回の処理した文字列分dropし、再帰する。

これで使った関数も実装してみた。

takeWhile' _ [] = []
takeWhile' f (x:xs) =
    if f x
    then x: takeWhile' f xs
    else []

dropWhile' _ [] = []
dropWhile' f p@(x:xs) =
    if f x
    then dropWhile' f xs
    else p

drop' _ [] = []
drop' n x | n <= 0 =  x
drop' n (_:xs) = drop' (n-1) xs

length' [] = 0
length' (x:xs) = 1 + length' xs

not' True = False
not' False = True

ちなみに、模範解答はghc/libraries/base/data/OldList.hsにある。

words s                 =  case dropWhile {-partain:Char.-}isSpace s of
                                "" -> []
                                s' -> w : words s''
                                      where (w, s'') =
                                             break {-partain:Char.-}isSpace s'

なるほどbreakは面白い仕組みだ。文字列の切り出しと文字列の先頭のdropを同時にやれるのでコードがきれいになる。早速実装してみよう。

break' _ [] = ( [],[] )
break' f p@(x:xs) =
    if f x
    then ( [], p )
    else let ( a, b ) = break' f xs
         in ( x:a, b )

模範解答。

break                   :: (a -> Bool) -> [a] -> ([a],[a])
#if defined(USE_REPORT_PRELUDE)
break p                 =  span (not . p)
#else
-- HBC version (stolen)
break _ xs@[]           =  (xs, xs)
break p xs@(x:xs')
           | p x        =  ([],xs)
           | otherwise  =  let (ys,zs) = break p xs' in (x:ys,zs)
#endif

USE_REPORT_PRELUDEは、Haskellの仕様書であるHaskell Reportの定義どおりの実装だ。Haskell Reportの定義は効率ではなく正しさだけを目的としている。通常はUSE_REPORT_PRELUDEではない方が使われる。

ところで、"break _ xs@[] = (xs,xs)"は、"break _ [] = ([],[])"と書くのと変わりがないと思うのだが、何か違いがあるのだろうか。

さて、ここまで何の問題もなく実装できているように見えるが、実際は些細な間違いで何時間も悩んでいる。

最初に書いたwords'は以下のような間違った結果を返した。

> words' "aaa bbb  ccc"
["aaa", "bbb", "b", "ccc", "cc"]

これはなぜかと言うと、処理した文字列を切り取る処理が以下のようになっていて、空白文字分を考慮していなかったからだ。

rest = drop (length word) s

しかし問題の原因を特定するのには苦労した。標準入出力が使えないので、最も原始的なprintfデバッグすらまだ使えないためだ。traceというものはあるが、問題はtraceの評価も実際に評価したときにしか行われず、現時点でHaskellのコードを評価する方法として、GHCiに食わせて表示させるということぐらいしか知らないため、traceの出力と本来の出力がごちゃまぜになって極めてわかりにくい。

もう一つハマった落とし穴は、dropWhileを実装していたときだ。以下のように間違ったコードを書いてしまった。

dropWhile' _ [] = []
dropWhile' f p@(x:xs) =
    if f x
    then dropWhile' xs
    else p

間違っている場所がわかるだろうか。私はわからない。GHCのエラーメッセージは型が違うということは知らせてくれるが、具体的にどこのコードが期待している型が違うのかということは教えてくれない。GHCが指し示す問題のある行は、"dropWhile' f p@(x:xs) ="だ。しかし、問題は"then dropWhile' xs"にあるのだ。エラーメッセージは、dropWhile'の型は(t -> Bool) -> [t] -> [t]だが、[t] -> [t]として使おうとしてエラーになっていることを教えてくれる。そこまで分かっているのならば、[t] -> [t]としてdropWhile'を使おうとしている箇所を教えてくれたっていいだろう。技術的にできるはずなのに、なぜか教えてくれない。

Haskellの実装であるGHCのエラーメッセージはあまりにも不親切すぎる。

2017-12-23

中古PC市場

ここ数年、私のメインのコンピューターは常に中古品だ。これにはいくつか理由がある。

中古品は製造元が購入に当たって同意を要求するかもしれない不自由な契約に同意しなくてもいい。契約は同意して初めて効力を持つ。私はメインで使う私の思想の延長線上にあるコンピューターが、不自由な契約で制限されることを好まない。

中古品は妥協ができる。私が新品のコンピューターを買うときは、妥協が出来ない。コンピューターに25万円だすのと30万円だすのとでは、私の中では誤差程度の違いしかない。しかし、中古品であれば妥協ができる。5万円の捨て値で買うコンピューターであれば、極端にこだわっても違いがないのだ。

中古品を探すのは面白い。中古品は市場にあるもので妥協しなければならないが、その特製は新品よりはるかにばらつきが大きい。

中古PC市場をみていると、私の考える価値と、古物商の考える価値がだいぶ食い違っていることがわかる。

どうやら、世の中のコンピューターにはMicrosoftの不自由で不便なWindowsというOSがプレインストールされていなければ売れないと考えているらしい。なので、古物商は、もしWindowsがインストールされていない、あるいはMSの屈辱的なライセンスキーが欠けているコンピューターを入手したときは、これにWindowwsをわざわざ入れて販売する。これにより約立たずなWindowsのライセンス料の分だけ中古PCの値段が上がる。残念なことだ。

また、PCが発売された時期が中古品の価格に大きく影響するらしい。例えば2年前に発売されたまことにゴミクズのような救いようのない性能の中古PCを高い価格をつけているのに、4年前のそれより遥かに性能が良い中古PCは、より古いという理由で価格が安かったりする。もちろん、古いということはそれだけ経年劣化している可能性もあることには注意しなければならない。

中古PC市場でよく目立つのはリース品だ。企業向けにリースされて返却された後の同一型番のコンピューターが大量に古物商に出回っている。元リース品は中古市場への供給が多いので価格が安めになりがちだ。

さて、私は中古PCを選ぶのに何を目安にしているのか。

まず何はともかくメモリ容量だ。この2017年にメモリはどんなに妥協しても最低でも8GBなければならず、16GBはほしい。

CPUにAtomを選んではならない。ただし、求めるものがとても小さくバッテリー時間であり、その他はどうでも良いのであれば、Atomでもよいだろう。

GPUにnvVIDIAを選んではならない。nVIDIAは不自由なソフトウェアを蔓延させることを目的とした企業だ。

ただ、次のメインPCは中古品ではなくて新品を買うかもしれない。というのも、最近Intelの悪意あるバックドアであるIntel MEを無効化する方法が見つかったため、Intel MEを無効化して出荷する自由志向のPCを販売するところが現れ始めたからだ。

2017-12-20

Haskellへの巡礼

C++の入門書を書くという目的のため、C++を一旦離れてHaskellを学ぶことにしてはや三日目。初日は環境構築で潰れ、二日目はリストを学ぶだけで終わった。

Haskellのリストは、単に順序のある値の集合だけではなく、[1..10]のように規則的な数列を作り出す機能も持っている。またList comprehensionsといって、リストからリストを生成する機能もある。

二日目はリスト処理を学ぶだけでだいぶ疲れた。何も難しいことをしている実感はないのだが、全く馴染みのない新しい概念を学ぶということはかくもつらく苦しいものだとは、久しく忘れていた。馴染みのない新しいことを学ぶのはつかれるということは覚えておかなければならない。

そして三日目はtupleを学んだ。

List comprehensionsはなかなか興味深い機能で、本質的にループであり、imperative languageでループを書いて実装する計算のうちの一部はList comprehensionsで実装できるようだ。

しかし、一部でしかない。そこがつらい。私にとってプログラミングとは、標準入出力と入力で得たものを処理して出力することなので、なにはともかくも標準入出力を扱いたいのだが、Haskellで標準入出力を自在に扱うためには覚えることがまだ色々とあるらしく、まだ手を出すことができないでいる。

四日目。型と型クラスを学び、関数とパターンマッチについて学んでいる。Haskellについて少しわかってきた。

しかし、List Comprehensionsでパターンマッチに失敗した要素は単に無視されるのがとても気に食わない。

xs = [ [1,2], [], [3,4] ]
 [a + b | [a,b] <- xs ]
[3,7]

Haskell 2010 Reportにも書いてあるので受け入れるしかないが。

3.11 p2: and if a match fails then that element of the list is simply skipped over.

まだHaskellの全体像をつかめていないのでHaskell 2010 Reportを本格的に読んでいないが、パターンマッチは3.17で規定されている。まだ知らない知識が多すぎて読めない。

7日目。Higher Order Functionsについて学んでいる。もうHaskellはだいぶ理解できてきた。試しにPandocのコードを読んでみたが、部分的に意味がわかるようになっていた。これならば後は全部学ぶだけだ。

さて、Imperativeな言語であるC++が専門の私がHaskellに思うこととしては、やはり速度だ。

まず最適化だが、sumのようなリストの合計値を計算するコードがあったとして、

accumulate [] = error "empty list."
accumulate [a] = a
accumulate (h:t) = h + accumulate t

このコードは毎回リストが空であるかどうかのパターンマッチが入るので非効率的であるが、リストが空でなければ、その後リストが空になることはないので、賢いコンパイラーならば、空のリストのパターンマッチを最初の一回だけにするように変換できるはずだ。

accumulate [] = error "empty list"

accumulate x = accumulate' x
    where   accumulate' [a] = a
            accumulate' (h:t) = h + accumulate' t

これをcall-pattern optimizationと呼び、Haskellではデフォルト無効で、-fspec-constrもしくは-O2で有効になる。デフォルトで有効になっているべき最も初歩的な最適化のように思える。

Haskellはとても賢いコンパイラーがimperativeな操作を行うように最適化を行えば早くなるだろうが、現状ではそうではない。例えばhaskell.orgのクイックソートの例はひどい。

https://wiki.haskell.org/Introduction#Quicksort_in_Haskell

このHaskellのクイックソートのコードは簡潔でアルゴリズムを学ぶのに最適だが、とても遅い。それに反論するために以下のページがある。

Introduction/Direct Translation - HaskellWiki

曰く、Haskellのナイーブなクイックソート例は遅いので、世の中にはHaskellの拘束なクイックソート例と称するものがいくつも出回っているが、どれもコンパイルできない。

そこで、HaskellでCのクイックソートと同等のコードが示してあるが、Cのコードより長く、Cのコードより読みにくく、そして依然としてCのコードより2倍は遅い。

もはや喜劇もいいところだ。

8日目。再びlistとlist comprehensionsについて考えている。Haskellのリストは、C++でいえば、配列であり、for文であり、std::iotaでもある。遅延評価されて適切に最適化されるのであれば速度も問題ないだろうが、しかしクイックソートの例はひどい。

pattern guardsの存在を知ったので、すべてのパターンマッチはcase式で書けるというHaskell 2010 Reportの記述が確認できた。

Haskell 2010 Reportは少しづつ読み始めているが、至るところで何の言及もなく使われているotherwiseキーワードがないのが気になった。GHCIでotherwise = 0と書いてみると何の問題もなく実行される。試しに:t otherwiseしてみると、どうやらotherwiseとは引数を取らずBoolを返す関数のようだ。なるほど・・・いや、それはもしかして・・・やはり単なるotherwise = Trueか。

9日目。ちょっと学ぶ速度が落ちてしまったがのんびりと入門書を読み続けている。ところで、たまたまPCを再起動したときに、ブート直後のGHCIの初回起動が信じられないほど遅いことに気がついた。プロンプトが表示されるまでに5秒はかかる。次回以降の起動は一瞬だ。一体なぜなのか。大規模なファイルシステムへのアクセスをしていてファイルシステムへのキャッシュの有無なのだろうか。そのコンピューターはM.2 SATA SSDを使っていたが、この仮設を確かめるために、よりストレージ性能の高いM.2 NVMe SSDを搭載した別のコンピューターをリブートしてGHCIを起動してみた。やはり初回起動はプロンプト表示までに2秒ぐらいかかる。

だいたい、言語の習得自体に問題がなくなってくると、こういう些細なところが気になってくる。

2017-12-19

nVidia、GeForceのデータセンターでの利用を禁止する

NVIDIAが規約変更によりGeForceのデータセンター利用を制限。大学などの研究活動にも大ブレーキ - WirelessWire News(ワイヤレスワイヤーニュース)

また清水亮がポエムを書いている。困るんだよね、名前の同じ人間にそういうことをされると私まで詩人だと思われてしまう。

nVidiaは確かに邪悪で不自由で存在自体が人道上の罪にあたる極悪企業であり、かのLinuxカーネルの最高開発者であるブリリアント・アッスホールの称号も名高いリーナス・トーバルズにも中指を突き立てられてFから始まるとてもここで書くことができないほどの醜悪極まりない侮辱の四文字言葉で罵られたほどの救いようのない時勢の読めない烏合の衆ではあるが、まさか自らの飯の種であるデータセンターへの利用を禁止するほどの寓話に出てくる金の卵を生む鶏を割くほどの阿呆ではないだろう。どれどれ、この私が直々にソースとやらを検証しことの真偽を確かめてやろう・・・マジじゃねぇか清水亮!

問題となっているのは、nVidiaの物理的な製品であるGeForceとTitanではなく、この製品を利用するためのドライバーのEULA、"License For Customer Use of NVIDIA GeForce Software"だ。

日本国版は以下のようになっている。

2.ライセンスの付与

2.1 付与に関する権利と制限。NVIDIA は本ライセンスをもって、お客様が所有する NVIDIA GeForce または Titan ブランドのハードウェア製品と共に使用するために本ソフトウェアをインストールし、使用する非独占、譲渡不可能のライセンスをお客様に付与します。ただし、以下の制約があります。

2.1.3 制限

データセンターへの導入の禁止。データセンターへの導入の目的では、本ソフトウェアのライセンスは付与されていません。ただし、データセンターにおけるブロックチェーン処理を行うことは許されます。

翻訳ミスかもしれぬので、アメリカ合衆国版も確認すると、以下のようになっている。

http://www.nvidia.com/content/DriverDownload-March2009/licence.php?lang=us&type=GeForce

2. GRANT OF LICENSE

2.1 Rights and Limitations of Grant. NVIDIA hereby grants Customer a non-exclusive, non-transferable license to install and use the SOFTWARE for use with NVIDIA GeForce or Titan branded hardware products owned by Customer, subject to the following:

2.1.3 Limitations.

No Datacenter Deployment. The SOFTWARE is not licensed for datacenter deployment, except that blockchain processing in a datacenter is permitted.

なんと、アメリカ語でも同一の内容で、翻訳のミスではない。この他の部分も念のために読んでみたが、この制約を上書きするような記述は見つけられなかった。

このライセンスはnVidiaのGeForceとTitan用のドライバーをダウンロードするときに同意を求められるもので、ライセンス本文中にもGeForceとTitanと書いてある。このドライバーがなければGeForceとTitanは実質的に使用不可能だ。そのドライバーがデータセンターにデプロイできないとあっては、シリコン製の電力効率の悪い暖房器具をデータセンターに配置するようなもので、何の意味もなくなる。

ブロックチェーンの処理のためであればデータセンターにデプロイできるというのは、その手の計算はAMDのGPUのほうが得意で市場を取っているためだろう。ようするにnVidiaという企業は一度市場シェアを獲得すれば足元を見てあぐらをかいて殿様商売をする邪悪で不自由な企業ということだ。はやく適切な自由市場による淘汰を受けてほしい。

RMSは自由なソフトウェアの定義としてまず第一に、自由ゼロ、「プログラムをいかなる目的においても望みどおりに実行する自由」を掲げた。これが一番最初にあるのは、最も重要だからだ。例えば現実の不自由ソフトウェアは、非エンタープライズ目的に限るとか、1台の物理的なコンピューターに限るとか、自社の提供する物理的なコンピューターに限るとか、様々な不平等で屈辱的で消費者の権利を不当に制限する契約を要求している。そのような不自由ソフトウェアの脅威を受け入れておきながら、今回のnVidiaの契約の妥当性に疑問を示す人間は論理的な思考ができない人間である。

2017-12-12

C++の入門書を書くためにHaskellを学ぶことにした

C++17の参考書、江添亮の詳説C++17はすでに書き上げて、来年の出版を待つばかりになっている。

https://github.com/EzoeRyou/cpp17book

次に書く本はC++の入門書にしようと思っているが、入門書を書く前に、少し時間をかけてHaskellを学ぼうと思っている。

なぜHaskellを学ぶのか。Pandocのためだ。

Pandoc

私の本は、Markdownで書いてPandocで各種フォーマットに変換している。アスキードワンゴでは、Pandocを使ってlatexに変換した上で、手作業で出力されたlatexを編集して組版している。つまり、私の参考書の執筆はPandocに支えられていると言ってよい。

さて、アスキードワンゴ編集部(ドワンゴ)は私が本を出版契約している出版社であり、かつ私が雇用契約している会社でもある。アスキードワンゴの編集者は私の編集者であり同僚でもある。そういったサザエさんの家系図なみに複雑な理由で私はアスキードワンゴの編集者の負担を減らすことにインセンティブがある。編集者はPandocに不満点があり、改良したいと思ってはいるが、Haskellなので手が出せずにいる。話を聞く限り、不満点の解消は、Pandocのコードが理解できれば、それほど難しい変更でもなさそうだ。問題は、PandocはHaskellで書かれているということだ。

Haskellというのは私が今までやってきたプログラミング言語とはだいぶパラダイムの異なる言語で、私はC++に関してはだいぶ理解したが、Haskellという点ではもはやプログラミング未経験者に近い。

さて、早速定評のあるHaskellの入門書、Learn Haskell for Great Goodも買い込み、届くのを待っている間はオンライン版を読みながらHaskellを学ぶとしよう。

Chapters - Learn You a Haskell for Great Good!

プログラミング言語を学ぶには、まずプログラミング言語の実行環境を用意することが重要だ。どうやら、Haskellの実行環境はHaskell Platformとやらで揃うらしい。UbuntuでHaskell Platformをいれるには、

sudo apt install haskell-platform

すればよい。

しかし、どうやらHaskell Platformはもうイケてないらしい。最近のクールなキッズは全員Stackとやらを用いるそうだ。

stackを使うには、シェルスクリプトを落として実行するか、あるいはapt install haskell-stackして、stack upgradeすればいいらしい。さっそくstack upgradeしたが、延々とライブラリのビルドを始めた。小一時間書けてビルドが終わった後に、stack ghciを実行したが、どうやらstack setupしていなかったのでまずghciのビルド済みバイナリのダウンロードが走り、たまたまWiFi経由でダウンロード速度が遅かったので、これまた時間がかかった。

なるほど、環境構築だけで一日が終わってしまった。やったこととしてはコマンドを数行叩くだけなのだが、GHC, Haskell Platform, StackといったHaskellの実行環境の歴史などを学ぶのにだいぶ時間を要した。

この経験から私は、環境構築の解説は丁寧に行うべきだという教訓を得た。C++の入門書の執筆に参考になる経験が、まだHaskellを一行も書かないうちから得られた。

さて、Haskellを学び始めるか。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

江添ボドゲ会@12月17日

毎月恒例の江添自宅ボドゲ会を以下のとおりに開催します。

江添ボドゲ会@12月17日 - connpass

2017-12-11

来年出版予定の「江添亮の詳説C++17」の組版に使うTEXを公開

来年出版する予定のC++17の新機能を解説した参考書、書名は現在、「江添亮の詳説C++17」を予定している本の組版に使うTEXを公開した。

https://github.com/EzoeRyou/cpp17book

この参考書は今年2017年に9ヶ月ほどかけて書いていた本で、C++17に追加された新機能のほぼすべてを解説している。

この参考書は、アスキードワンゴから出版される予定だ。アスキードワンゴでは本の組版にTEXを使っている。

私は自由なライセンスの価値を信じるものであり、本も自由になるべきだと信じている。私の書いた本は自由なライセンスにできるとして、組版に使ったTEXも公開したい。TEXは明らかにソースコードに当たるものであり、ソースコードが公開できなければGPLv3ではライセンスできないのでCC-BY-SAなどを使わなければならない。私が執筆したC++11/14コア言語は、こういった理由でCC-BY-SAだった。

さて、今回の本では、TEXも公開できることになった。すでにmarkdownで書かれた本のソースコードは公開しているので、まだ出版前だがTEXも公開してしまうことになった。これで、今回の本「江添亮の詳説C++17」は自由なライセンスであるGPLv3でライセンスすることができる。

商業出版で使われる本のTEXを公開してどういう効果があるのか、私には予測できない。いい効果があると今後にもつながるのでうれしい。

アスキードワンゴの編集者が作成したTEXを眺めた感想としては、自動化が難しそうだと感じる。今回公開したTEXは私がmarkdownで書いて、pandocでTEXに変換し、それを編集者が手で編集することで作成されている。著者としては編集者の労力を減らすために自動化できるところは自動化したいのだが、編集済みのTEXをみると、結局、編集者が人力ですべてをチェックしなければならないことに変わりはない。

そして、PandocはHaskellで書かれているので、PandocをハックするためにはHaskellを学ばねばならない。Haskellを学ぶのは大変だ。

そういう話をしていたら、同僚のHaskell大好き人間からアスキードワンゴはHaskell本を出しているではないかとツッコミが入った。

Haskellによる関数プログラミングの思考法 - アスキードワンゴ

学ばねばならぬのか。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2017-12-06

C++標準化委員会の文書: P0790R0-P0799R0

P0790R0: library-operator-spaceship

operator <=>が標準ライブラリに与える影響について。

operator <=>によって生成される比較演算子は、ソースコードの書き換えと同等の効果を及ぼすのであって、実際の比較演算子ではないため、アドレスを取ることができない。これにより、opeartor <=>アドレスを取るユーザーコードは動かなくなる。これは互換性の問題となるが、そもそも比較演算子のアドレスを取るユーザーコードはまれだ。というのも、比較演算子はメンバー関数とフリー関数のいずれかで実装されるので、ユーザーコードでアドレスを取るにはどちらで実装されているか知らなければならない。また、一部の標準ライブラリは、a @ bのような式が妥当だとのみ規定されていて、operator @がどのように実装されているかを規定していない。その場合、ユーザーコードでアドレスを取った場合、そもそも未定義となる。なので、互換性の問題はまれにしか起こらないはずだ。

文書は、標準ライブラリで比較可能な型のうち、operator <=>に対応すべきではない型、変換関数を捨ててopeartor <=>に切り替えるべき型、既存の比較演算子に加えてoperator <=>を追加したほうがよい型、operator <=>を追加したほうがよい他の型をラップしている型、現在比較を提供していないがoperator <=>に対応したほうがよい型、operatgor <=>を追加したほうがよいCの型を列挙している。

valarrayというだいぶ忘れ去られた型も考慮している。

よく調べたものだ。

[PDF] P0791R0: Concepts are Adjectives, not Nouns

コンセプトCを使うtemplate < C X >を、template < C typename X >に変える提案。

template < C X >の意味はわからない。Xは型なのだろうか。値なのだろうか。CがコンセプトならばXは型だが、Cがintへのtypedef名ならば、Xは値だ。この問題は、内側のスコープの宣言で名前が隠れるともっとややこしくなる。


template < typename T > concept C = true ;

// Xは型
template < C X > struct S ;

namespace ns {

using C = int ;

// Xは値
template < C X > struct S ;
}

字面は同じtemplate < C X >なのに意味が変わってしまう。

この問題は、本来形容詞であるコンセプトを名詞として使っているから生じるのであって、形容詞的な文法にすればいい。すなわち、文法を以下のように変更する。

template < CopyConstructible typename T > struct S ;

この変更により、複数のコンセプトを簡単な文法で指定することも可能になる。

template < CopyConstructible LessThanCompareble tyepname T > struct S ;

なるほど、趣旨はわかるが文法が冗長になる。

P0792R0: function_ref: a non-owning reference to a Callable

Callableを所有しないラッパーfunction_refの追加。std::functionと違いメモリ確保をせず例外も投げない。

[PDF] P0793R0: SG5: Transactional Memory (TM) Meeting Minutes 2017/06/19-2017/10/09

Transactional Memoryの会議の議事録。

[PDF] P0794R0: SG14: Low Latency Meeting Minutes 2017/08/09-2017/10/11/

Low Latency会議の議事録。

[PDF] P0795R0: From Vulkan with love: a plea to reconsider the Module Keyword to be contextual

Vulkanより愛をこめて。

モジュールTSではmoduleというキーワードの追加を提案しているが、moduleという識別子はすでに多くの既存のソースコードで使われている。特にKhronos Groupの低級グラフィックAPIのVulkanでもmoduleを識別子として使っている。moduleは文脈依存キーワードにすべき。

[PDF] P0796R0: Supporting Heterogeneous & Distributed Computing Through Affinity

NUMAが当然となった現代では、メモリーアフィニティの重要性はいよいよ増すばかりだ。複数のスレッドによる並列処理を行ったとしても、そのメモリーが特定のひとつのスレッドだけで効率的にアクセスできるようになっている場合、並列処理はスケールしない。このようなメモリーとスレッドの関係をアフィニティと呼ぶ。

そこで、C++は標準でシステムのリソーストポロジーをクエリーし、メモリー領域の相対的なアフィニティをクエリー子、実行とメモリ領域を制限するようなアフィニティの設定機能を持つべきだ。

そんなの標準化できるのだろうか。

[PDF] P0797R0: Exception Handling in Parallel STL Algorithms

並列アルゴリズムを中断する方法の提案。

シーケンシャルアルゴリズムは例外を投げることによって中断できた。並列アルゴリズムも提案段階ではexception_ptrを複数もつexception_listを例外として投げることで中断できる予定だったが、この設計には色々と問題があったので廃止された。

この提案では、例外を格納するdisappointment_buffer<disappointment_type>を追加し、これを実行ポリシーオブジェクトで並列アルゴリズムに渡すことで例外リストを受け取る設計を提案している。

P0798R0: p0798r0: Monadic operations for std::optional

optionalにモナド操作として、and_then, or_else, mapを追加する提案。

画像から猫を抽出してより可愛くするコードを考える。

image get_cute_cat (const image& img) {
    return add_rainbow(
             make_smaller(
               make_eyes_sparkle(
                 add_bow_tie(
                   crop_to_cat(img))));
}

しかし、画像に猫が含まれていなかったらどうなるのだ。画像に蝶ネクタイを付加すべき場所が存在しなかったら、 猫が後ろを向いているので目を輝かすことができなかったら。それらの条件では、画像を返すことができない。

例外を使うというのも手だが、プログラムが画像を大量に処理するもので、画像に猫が含まれないことは例外的ではない場合、例外をコントロールフローに使うのはよろしくない。

そこでoptionalだ。

std::optional<image> get_cute_cat (const image& img) {
    auto cropped = crop_to_cat(img);
    if (!cropped) {
      return std::nullopt;
    }

    auto with_tie = add_bow_tie(*cropped);
    if (!with_tie) {
      return std::nullopt;
    }

    auto with_sparkles = make_eyes_sparkle(*with_tie);
    if (!with_sparkles) {
      return std::nullopt;
    }

    return add_rainbow(make_smaller(*with_sparkles));
}

しかし、こんなボイラープレートコードを書きたくない。

そこで、optionalのメンバーにmap, and_then, or_elseを追加すると、以下のように書ける。

std::optional<image> get_cute_cat (const image& img) {
    return crop_to_cat(img)
           .and_then(add_bow_tie)
           .and_then(make_eyes_sparkle)
           .map(make_smaller)
           .map(add_rainbow);
}

趣旨はわかるが現実の問題を解決するC++のコードが、そんなにきれいに引数をひとつ受け取ってひとつ返すような簡単なコードになるわけがなく、したがってこれを使おうとするとラムダ式で囲んだボイラープレートを書かねばならず、机上の空論に見える。

[PDF] P0799R0: Programming vulnerabilities for C++ (part of WG23 N0746)

C++標準規格の文面に脆弱性に対する忠告の文面を入れようという提案

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2017-12-02

仮想通貨と税金についての国税庁の見解についての所感

http://www.nta.go.jp/shiraberu/zeiho-kaishaku/joho-zeikaishaku/shotoku/shinkoku/171127/01.pdf

国税庁が仮想通貨と税金について見解を出しているが、これの一部が私の直感とだいぶ異なる。

1から9までの例について、具体的な暗号通貨であるBitcoin, Ethereum, Bitcoin Cashと日本円を出して考える。その価値は特に実態とは関係がない。

1. 暗号通貨Bitcoinを1万円分買って、後に暗号通貨Bitcoinを2万円で売った。所得=収入-支出=2万円-1万円=1万円となり、1万円の所得が発生する。

わかる。

2. 暗号通貨Bitcoinを1万円分買って、後に暗号通貨Bitcoin全額を支払って2万円の商品を買った。2万円分の収入が発生した扱いになり、所得=収入-支出=2万円-1万円=1万円となり、1万円の所得が発生する。

わかる。

3. 暗号通貨Bitcoinを1万円分買って、後に暗号通貨Bitcoin全額を支払って暗号通貨Etheriumを2万円分買った。2万円の収入が発生した扱いになり、所得=収入-支出=2万円-1万円=1万円となり、1万円の所得が発生する。

理解に苦しむ。暗号通貨から暗号通貨のやり取りには日本円が一切関与していない。

有名画家から絵をもらったとして、その有名画家の絵は市場で1万円の取引実態があるので、1万円の所得が発生したというようなものだ。まだ現金が一切関与していないのに絵を入手しただけで所得になるのはおかしい。

4. これを真面目に計算するのはだるいので具体例を出すのが面倒だが、まあ理解できる

5. 暗号通貨Bitcoinを1万円分買った。後に暗号通貨Bitcoinがforkして、暗号通貨Bitcoin Cashができた。その結果、BitcoinとBitcoin Cashを両方持つことになった。所有するBitcoinの価値は1万円と変わらず、Bitcoin Cashの価値は1千円となった。この場合、1千円の収入が発生した扱いになり、支出は0円で、1千円の所得が発生する。

うーむ・・・結果的に利益が発生したわけではあるが、やはり現金が一切関与していないのに所得となるのはおかしい。

世界に2枚しかない有名画家の絵の1枚を所有しているとして、もう1枚が焼けてなくなったので、自分の持っている絵の価値が1万円分上がった。したがって1万円の所得が発生したというようなものだ。まだ現金が一切関与していないのに所得になるのはおかしい。

6. Bitcoinが雑所得以外に分類される場合について。

わかる。

7. Bitcoinが雑所得とみなされる場合の損失は雑所得のなかだけで通算。

わかる。

8. 暗号通貨にはFXのような投機としての特別措置はない。

実態はもはやFXに近い気がするが、本来の意図した状況ではない気がする。

9. 2万円分の暗号通貨Bitcoinをマイニングするためにコンピューターと電気代で1万円をかけた。収入が2万円、支出が1万円。所得=収入-支出=1万円の所得が発生する。

やはり具体的な現金との関与が一切ないのに所得扱いになるのは解せない。

Bitcoinは実態としては絵に近い。例えば私が有名画家で、私の書いた絵には必ず1万円を支払って購入したい人が列をなして並んでいるとして、私が直ちに売らない絵を描いた場合、私は絵を生み出したのでその場で売らなかったとしても1万円の所得が発生することになるというのと同じ奇妙さがある。

2017-11-28

C++標準化委員会の文書: P0780R0-P0789R0

P0780R0: Pack expansion in lambda init-capture

lambda式のinit-captureにpack expansionを認める提案。ムーブができるようになる。

template < typename ... Types  >
void f( Types ... args )
{
    auto lambda = [ args = std::move(args)... ] { return g( args...) ; }
}

P0781R0: A Modern C++ Signature for Main

mainのシグネチャーを近代化する提案。

int main( const 何らかのコンテナー型<何らかの文字列型> args ) ;

にしたい。この提案では、std::initializer_list<std::string_view>を推奨している。

たしかに、そろそろmainも近代化されるべきだ。

P0782R0: A Case for Simplifying/Improving Natural Syntax Concepts

コンセプトを引数に取る関数テンプレートの文法を使った関数の依存名の解決は、コンセプトで示されているものしかできないようにしようという提案。

現在のコンセプトは、制約テンプレートの使用者に対するチェックだけで、制約テンプレート内のチェックはない。

例えば、現状のコンセプトは以下のコードが通る。

template < typename T >
concept has_f = requires( T x ) { x.f() ; }

void call_f( has_f & x )
{
    // コンセプトに書いてある
    x.f() ;
    // OK、ただしコンセプトに書いてない
    x.g() ;
}

struct X
{
    void f() ;
    void g() ;
}

int main()
{
    X x ;
    call_f( x ) ;
}

コンセプトによるチェックがないと、以下のようなコードが通ってしまう。

template < typename T >
concept has_const_f = requires( T x ) { const_cast<const T &>(x).f() ; }

void call_f( has_const_f & x )
{
    x.f() ;
}

struct X
{
    void f() ;
    void f() const ;
} ;

int main()
{
    X x ;
    // 非const版のvoid X::f()が呼ばれる
    f( x ) ;
}

コンセプトは制約テンプレートを制限しないので、このような挙動になってしまう。

文書では、初心者にコンセプトを使いやすいようにし混乱を防ぐために、ドラフト入りするときに削られたtarse notationによる関数制約テンプレートを復活させ、その依存名の解決はコンセプトに合致するものしか行わないようにしようという提案をしている。

tarse notationを使わないものと使うもので挙動が違うのはますます混乱の元ではないか。

P0783R0: P0783: Continuations without overcomplicating the future

現在、futureに継続を追加するための議論が行われているが、結局executorなしでは継続が実行される媒体が決定的ではなく意味がない。Facebookはfollyライブラリで継続とexecutorを持つfutureを実装して、社内で使った経験から、この件について意見している。

P0784R0: Standard containers and constexpr

vectorやunordered_mapのような可変サイズのコンテナーは実行時プログラミングに便利だ。ということは、コンパイル時計算にも便利なはずだ。

constexpr版のvectorやstringが提案されているが、vectorをそのままconstexr化することはできないのか。

vectorのconstexpr化を妨げる処理は3つ。

  1. デストラクター
  2. メモリ確保
  3. in-place new

デストラクターはconstexpr化できないが、この制約は取っ払うことができる。EDG, MSVC, GCC, Clangの開発者は皆同意している。

メモリ確保はコンパイラーがコンパイル時のメモリ確保を特別に処理することでconstexpr化できる。しかし、コンパイル時メモリ確保は、未定義の挙動を完全に検出できなければならないので、アドレスには追加のメタデータを付与しなければならない。これによりポインターのvoid *への変換はできなくなる。

問題は、いまのoperator newの宣言が以下のようになっていることだ。

void * operator new( std::size_t ) ;

ただし、new, deleteを使っているのならばコンパイラーが特別に対応することもできる。あるいは標準アロケーターで対処する。

in-place newをすべてconstexpr化することは無理だが、vectorで使う一部の用例はconstexpr化できる。

さて、コンパイル時計算で確保したメモリを開放しない場合どうなるのか。一番簡単な方法は未開放を禁止するということだ。しかし、コンパイル時処理の結果を実行時に渡したいときもあるだろう。すると開放されなかったコンパイル時メモリ確保はstaticストレージとして残すという手もある。

夢が広がる話だ。あらゆる計算はコンパイル時計算になりうる。

P0785R0: P0785R0: Runtime-sized arrays and a C++ wrapper

実行時サイズ配列復活論。CのVLAのサブセットとC++のラッパークラスの提案。

ようするにスタックから実行時に指定したサイズのメモリを確保したいということだ。

かつてC++14に入りそうだったdynarryは、スタックから確保できない場合、動的確保にフォールバックするという設計で、確実にスタックから確保されてほしい利用者にとって当てにできない設計であった。その後、厳格にスタックからしか確保しないフォールバックのないbs_arrayなども提案されたりしていた。

C++規格では、スタックとヒープという存在を避けてきた。代わりに、オブジェクトは寿命期間を持つストレージで区別されてきた。殆どのコンパイラーはスタックとヒープを使っていて、その使い分けは自然なものだ。しかし、世の中には組み込みとかカーネルなどの極端な環境があり、スタックメモリーのサイズが極端に小さい環境もあるかもしれない。そういう環境ではメモリはヒープに確保し、スタックではヒープメモリへのアドレスを格納するだけという実装もあり得る。結局、C++規格としてはスタックの利用を強制することはできない。

[PDF] P0786R0: ValuedOrError and ValueOrNone types

エラー処理を暗号的ではなくなるが冗長な記述になるライブラリの提案。

提案されているライブラリの一部を使うと、以下のように書ける。

// 同じ
x.has_value() ;
value_or_error::has_value(x) ;

// 同じ
(o) ? f(*o) : nullopt ;
value_or_error::transform(o, f) ;

// 同じ
(!e) ? e.error() : err
value_or_error::error_or(e, err)

// 同じ
(e) ? false : e.error() == err ;
value_or_error::check_error(e, err) ;

暗号的なコードではなくなるが、冗長な記述になるし、意味がわかりやすいかというとそれも疑問だ。

[PDF] P0787R0: Proclaimed Ownership Declarations

モジュールからproclaimed-ownership-declarationを削除する提案。

[PDF] P0788R0: Standard Library Specification in a Concepts and Contracts World

「プログラムの挙動に合わせて仕様を変えるのは、その逆より簡単だ」 Alan Perlis

「8.5×11インチの紙1枚に収まらない仕様は理解不可能だ」 Mark Ardis

「specというのは仕様(specification)の略か? 憶測(speculation)の略なんじゃないか?」 詠み人知らず

標準ライブラリはどのようにconceptに対応すべきかという方針の提案。

Requires: は現状維持。代わりに新しい要素を追加する。

Requires: を段階的に廃止し、新しい要素で置き換える。

新しい要素として、Constraitns:, Diagnostics:, Expects:, Ensures:を追加する。

[PDF] P0789R0: Range Adaptors and Utilities

Rangeアダプターの提案。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2017-11-22

C++標準化委員会の文書: P0770R0-P0779R0

P0770R0:A Proposal to Specify Behavior in Case of Exception Allocation Failure

例外オブジェクトのストレージは未規定の方法で確保されると規格にある。動的確保する実装の場合、確保に失敗した場合に対処する方法がない。

そこで、例外処理が失敗した場合に絶対に失敗せずに投げられる何らかの例外型を追加する提案。bad_allocを再利用するのがよいとしている。

[PDF] P0771R0: std::function move operations should be noexcept

std::functionのムーブ処理をnoexceptにする提案。すでにanyやshared_ptrはnoexceptなのでstd::functionをnoexceptにしない理由はない。

[PDF] P0772R0: Execution-Agent Local Storage

スレッドより軽い実行媒体がTLSを使うとスレッドのTLSが使われてしまう。ExecutorにTLSを要求するAPIを用意して、ExecutorがTLSを提供するか拒否するかして、スレッドより下の軽い実行媒体にもTLSを提供しようという提案。

P0773R0: Towards meaningful fancy pointers

ポインター風に振る舞うクラス型fancy pointerについての考察。ポインターにメタ情報を付加したり、アドレスにnear/far/segmentといった概念があったりする場合に必要。

[PDF] P0774R0: Module Declaration Location

module宣言の文法を変える提案。相変わらず文法が安定しない。

[PDF] P0775R0: Module Partitions

一つのソースファイルに複数のモジュールを書くことができるようにする提案。

P0776R0: Rebase the Parallelism TS onto the C++17 Standard

Parallerism TSはC++14の文面に合わせて書かれていたので、C++17の文面に合わせて書き直す提案。

[PDF] P0777R0: Treating Unnecessary decay

標準ライブラリでdecayを使っているがremove_cvrefですむ場所でremove_cvrefを使うよう書き換える提案。

[PDF] P0778R0: Module Names

モジュールが未だにこんな問題を抱えてるとは、C++20に入るのはおぼつかないのではないだろうか。

モジュールでimport foo ;と書くと、「これはモジュール名fooをimportしろ」という意味だ。ではモジュール名fooに対応するモジュールが定義されているソースファイルは何だろうか。規格は何も定めていない。

ヘッダーファイルでは、ヘッダー名は実装が実ファイルへのマッピングをするヘッダーか、直接物理のファイル名を意味している。ヘッダーを実装しているC++コンパイラーは存在せず、既存のすべてのコンパイラーはヘッダー名をファイル名として解釈し、所定のincludeディレクトリー群からヘッダー名のファイル名を探し出す。

モジュールの実装では、モジュール名、モジュールソースファイル、モジュールバイナリファイルが存在するはずだ。モジュールバイナリファイルは規格の規定するところではないが、モジュールソースファイルを処理した結果の何らかのファイルだ。モジュールの目的がコンパイルの高速化にあるので、当然このような実装になるはずだ。

すると、モジュール名fooをimportしたとき、C++コンパイラーはモジュール名fooに相当するモジュールバイナリファイルを探し出して使う。もしモジュールバイナリファイルがない場合、モジュールソースファイルを探してモジュールバイナリファイルを生成する。要するに今のビルドシステムがやっている依存関係の解決をC++コンパイラーが内部で直接やるようになる。ここでもやはり、モジュール名とモジュールソースファイルのマッピングが必要になる。

このモジュール名とファイル名のマッピングは、現状のままでは実装ごとに異なることになり、ポータビリティのかけらも存在しない使いづらいものになる。

モジュール機能を提供している他のプログラミング言語の例を列挙して比較してみるが、そもそも多くのプログラミング言語は単一の実行環境、単一の実装といったC++とは異なる状況にあるので参考にできないものも多い。

この文書では、モジュール名の文法を識別子から文字列リテラルにしてファイル名とマッピングするルールを追加するように提案している。

[PDF] P0779R0: Proposing operator try() (with added native C++ macro functions!)

なかなか野心的な提案。

expected<T,E>を返す関数が内部でexpected<U,E>を返す関数を呼び、エラーを返した場合はそのエラーを含むoptionalを伝播して返す処理を考える。

template < typename T >
using expected = std::expected<T, std::error_code > ;

expected<int> get_int() noexcept ;

expected<float> get_float() noexcept
{
    auto r = get_int() ;

    // 結果がエラーならば伝播する
    if ( !r )
        return unexpected( r.error() ) ;

    // floatがintを完全に表現できなければエラーを返す
    auto f = float( *r ) ;

    if ( int(f) != *r )
        return unexpected( std::errc::result_out_of_range ) ;
    else
        return f ;
}

このとき、エラーを伝播させるのがとてもだるい。いちいちエラーかどうか調べてエラーならエラーを返す処理を書かなければならない。

このボイラープレートコードを回避するためにCプリプロセッサーマクロを書くのも醜悪だ。

このコードは、コルーチン提案をまねてoperator tryをオーバーロードできるようにすれば解決できる。

template <class T, class E>
constexpr auto operator try(std::expected<T, E> v) noexcept
{
    struct tryer
    {
        std::expected<T,E> v ;

        constexpr bool try_return_immediately() const noexcept { return !v.has_value() ; }
        constexpr bool try_return_value() { return std::move(v).error() ; }
        constexpr try_value() { return std::move(v).value() ; }
    } ;
    return tryer{ std::move(v) } ;
}

これさえあれば、

auto r = get_int() ;
if ( ! r )
    return unexpected( r.error() ) ;
auto i = int(*r) ;

は、以下のように書ける。

int i = try get_int() ;

しかし、operator tryも冗長なコードを大量に書かなければならない。そもそもコルーチン提案自体が冗長なコードを多数書かなければならない。この問題は、ネイティブ言語マクロを導入すれば解決できる。

結局問題は、関数の呼び出し元の文脈でreturnしたいので、Cぷりプロセッサーに変わるネイティブなマクロがあれば、この問題は解決できるし、コルーチンが常用な問題も解決できるし、range-based forも実装できるし、割とあらゆるものがマクロで実装できることになる。

興味深いのはその提案している文法で、文字#を使っている。#はCプリプロセッサーにかけたあとのC++のソースファイルに残らない文字で、既存の実装はプリプロセス後に文字#があるとエラーを吐く。なので安全に機能拡張に使うことができる。

夢が広がる話だ。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2017-11-21

江添ボドゲ会 11月26日

以下の通り11月26日に自宅でボードゲーム会を開催します。

江添ボドゲ会@11月26日 - connpass

2017-11-20

C++標準化委員会の文書: P0735P0-P0769R0

P0735R0: P0735R0: Interaction of memory_order_consume with release sequences

memory_order_consumeがARMのとても弱いメモリーモデルでは実用的にならないのでなんとかしたいという文書。

P0737R0: P0737r0 : Execution Context of Execution Agents

現在のExecutor提案では実行媒体とかexecutorとか実行リソースについては考慮しているが、具体的なexecution contextについて考慮していない。とりあえず最低限の具体例を定める提案。

P0750R0: p0750r0: Consume

memory_order_consumeは未だにどのC++コンパイラーも実装していない。これは、C++のソースコードレベルでの依存と、ハードウェアでの依存に違いがあるためと、この業界でconsumeという用語の意味が一貫していないためだ。consumeを実装可能にするために色々と提案している文書。

P0752R0: std::vector Destruction Order

vectorの要素の破棄順序を自然にする提案。今まで規格でvectorの要素の破棄順序を規定していなかったので、実装ごとに差異があった。C++では破棄は構築の逆順に行われることが自然なので、vectorも配列やstd::arrayと同じく、末尾の要素から破棄される。

[PDF] P0753R1: Manipulators for C++ Synchronized Buffered Ostream

P0763R0のtypoを修正した。内容は同期バッファーでフラッシュをするかどうかを設定するマニピュレーターの提案

P0756R0: Lambda syntax should be more liberal in what it accepts

lambda-captureの制限緩和の提案。

現在、lambda-captureとして[&x, =]は誤りだ。正しくは[=, &x]。デフォルトキャプチャーの前に個別のキャプチャーを書くことはできない。

現在、lambda-captureとして[=, x]は誤りだ。正しくは[=]。デフォルトキャプチャーと同じ意味の個別のキャプチャーを書くことはできない。

しかし、これの意味は完全に曖昧製無く明らかであるし、初心者がハマる落とし穴であるので、制限緩和すべきであるという提案。

正しい。

P0757R0: regex_iterator should be iterable

filesystemのdirectory_iteratorはrangeとしても使える。

regex_iteratorもrangeとして振る舞うべきだという提案。

確かに、デフォルトコンストラクターが終端イテレーターになるタイプのイテレーターであれば、rangeにもなる。

[PDF] P0761R1: Executors Design Document

実行媒体を表現するExecutorについて。

[PDF] P0762R0: Concerns about expected<T, E> from the Boost.Outcome peer review

Boostのuncheckedの作者からexpectedに物申す文書。どうも些細な違いに思える。

P0766R1: Fixing small-ish functionality gaps in constraints

lambda式でrequires-clauseを使えるようにする提案。

P0767R0: P0767R0: Expunge POD

PODをdeprecated扱いにする提案。これまで規格でPOD型としていた部分はトリビアル型とし、初期化の文脈で「非POD型のグローバルオブジェクト」としていたところは「ユーザー提供コンストラクターで初期化されるグローバルオブジェクト」と書き直す。is_pod traitsはdeprecated扱いになりAnnex Dに移動する。

[PDF] P0768R0: Library Support for the Spaceship (Comparison) Operaton

operator <=>の標準ライブラリによる対応について。

operator <=>はこの前の会議で入ることがほぼ決定した等価比較と大小比較をいっぺんにできる演算子だ。

a == bのとき、a <=> bは0を返す。a < bのとき、a <=> bは<0を返す。a > bのときa <=> bは>0を返す。

また、戻り値は単なる整数型ではなく特別なクラス型で、大小比較できる場合はstd::strong_order, std::weak_order, std::partial_order、等価比較しかできない場合はstd::strong_equality, std::weak_equalityを返す。これらの型は派生関係でis-a関係を表現しているので、例えばstd::strong_orderはstd::weak_orderとしても使えるが逆はない。

大小比較が常にできてa == bのとき、常にf(a) == f(b)が成り立つのがstrong oder、成り立たないのがweak order

例えば文字列のcase insensitiveな比較は等しいと判断されても大文字小文字の違いがあるのでweak_order。

比較ができない値が存在する場合、partial order。

例えばIEEE-754の浮動小数点数はNaN, +0, -0があるのでpartial order。

この文書ではstd::strong_orderなどの標準ライブラリについて細かく定めている。ヘッダーファイルは<cmp>

[PDF] P0769R0: Add shift to <algorithm>

algorithmにshift_leftとshift_rightを追加する提案。

moveとmove_backwardと違い、同じレンジ内で操作する。rotateとは違う。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

glibcのpowがslowpowを呼んで遅い件について

Slow power computation by 64-bit glibc

x86-64 GNU/Linux環境でのglibcのpowは1.0に近い値を渡すと、768bitのソフトウェア実装された浮動小数点数計算を行い高精度な値を得ようとする。slowpowと命名されているこの実行パスは名前通りとても遅い。

glibcはとても基本的なライブラリなので、例えばRubyとかRustのようなプログラミング言語もこの問題に引っかかる。

手元で試したところ、GCC 7.2, glibc 2.26では、-Oと-ffastmathを指定するとpowにslowpowが呼ばれず高速に計算されるようだ。

これでもだいぶ高速化されたのだとか。

Improving math performance in glibc - RHD Blog

2017-11-13

C++標準化委員会の文書: P0650R1-P0722R1

[PDF] P0650R1: C++ Monadic interface

C++でモナドをやるためのライブラリの提案。どうもライブラリでやると煩雑になる気がするのだが。

[PDF] P0655R0: visit<R>: Explicit Return Type for visit

戻り値の型Rを明示的に指定できるvisit<R>の提案。

[PDF] P0657R1: Deprecate Certain Declarations in the Global Namespace

C言語における標準ヘッダーファイル<name.h>はC++では<cname>になった。C++形式のヘッダーファイルをincludeすると、std名前空間スコープに名前が宣言される。同時に、グローバル名前空間に名前が宣言されるかもしれない。

この提案は、C++形式のヘッダーファイルをincludeすると、グローバル名前空間に名前が宣言されることをdeprecated扱いする提案だ。なので、文面は「グローバル名前空間に名前が宣言されるかもしれない」から、「deprecated扱いではあるが、グローバル名前空間に名前が宣言されるかもしれない」になる。

P0658R1: Proposal for adding alias declarations to concepts

conceptのrequires式の本体にエイリアス宣言を書けるようにする提案。

template < typename T>
concept bool SomeReq = requires {
    typename value_type_t<T> ;
    requires Constructible<T, value_type_t<T> > ;
} ;

が、

template < typename T>
concept bool SomeReq = requires {
    using value_type = value_type_t<T> ;
    requires Constructible<T, value_type > ;
} ;

になる。conceptでネストされた型名記述に誤解を生みそうな気がする。conceptはすでにドラフト入りしているのだが、果たして普通のC++プログラマーが書けるようになるのだろうか。

P0670R1: Static reflection of functions

関数呼び出し式から呼び出される関数を得たり引数の型をそれぞれ得たりできるわりと軽めのリフレクション機能の提案。

void func(int);
void func(std::string);
using func_call_m = reflexpr(func(123));
using func_m = get_callable_t<func_call_m>; // reflects void func(int)
using param0_m = get_element_t<0, get_parameters_t<func_m>>;
cout << get_name_v<get_type_t<param0_m>> << '\n'; // prints "int"

[PDF] P0684R1: C++ Stability, Velocity, and Deployment Plans

C++標準化委員会が新機能を追加する際に下位互換性を破壊する変更を伴う時、ユーザーが既存のコードを変更する際に行われる行動を想定した上で、どのようにすべきかという提案。

C++の新しい規格を受容する時は以下のようなステップで行われる。

  1. 新しい規格をサポートした新しいコンパイラーにアップグレードする
  2. 新しいコンパイラーの古い規格モードでの既存のコードをコンパイルすると互換性の問題になる箇所について警告を受ける
  3. 警告を確認してコードを修正する
  4. 新しい規格モードを有効にする

これに従い、下位互換性を破壊する言語機能は容易に警告を出せるかどうかについて注意を払うべきである。

P0692R0: Access Checking on Specializations

知らなかった。

クラスのprivateなメンバーは当然クラス外部からアクセスできないわけだが、既存のほとんどのコンパイラーはテンプレートの明示的特殊化でアクセス指定を無視する。また、GCCとMSVCは部分的特殊化でもアクセス指定を無視する。


class A {
template < typename T >
class impl { } ;
} ;

template < typename T >
struct traits { } 

// 明示的特殊化
// 規格上はエラー
// GCC, Clang, ICC, MSVCは通す
template < >
struct traits< A::impl > { } ;

// 部分的特殊化
// 規格上はエラー
// GCC, MSVCは通す
// Clang, ICCはエラー
template < typename T >
struct traits< A::impl > { } ;

これを踏まえると、現状のC++実装がこの場合にアクセス指定を無視するよう実装していて、またこの仕様ではないとprivateメンバーの型に対する特殊化が出来ないことも考えると、規格を変更してこの制限を取り払ったほうがよいので、明示的特殊化と部分的特殊化ではアクセス指定の制限を緩和をする提案。

P0701R1: p0701r1: Back to the std2::future Part II

名前がよい。

内容はfutureに対する機能追加に対する提案。

[PDF] P0707R2: Metaclasses: Generative C++

現在提案されている静的リフレクションライブラリが入ったという前提でその静的リフレクション機能を使って実装できるmetaclassライブラリの提案。

constexpr {       // コンパイル時実行
    for ( auto m : $T.variables() ) // T型のメンバー変数それぞれに対し
        if ( m.name() == "foo" )  // "foo"という名前のメンバーがあれば
            -> { int bar ; }  // int型の"bar"という名前のメンバーを注入する。

}

割と衝撃的なコードだ。

P0722R1: Efficient sized delete for variable sized classes

sized deallocate functionにクラスへのポインターを取るオーバーロードを追加する提案。

クラスオブジェクトの近隣のストレージ領域を活用した動的にオブジェクトサイズを変えるクラスを実装する時、sizeを効率的に指定するために使える。


void operator delete ( X *, std::destroying_delete_t, その他の引数 ) ;

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

今回C++ドラフトに入った機能

Trip report: Fall ISO C++ standards meeting (Albuquerque) | Sutter’s Mill

Herb Sutterが今回の標準化委員会の会議でドラフト入りした機能についていち早く速報を出している。具体的な文書などはリンク先で確認してもらうとして、概要だけ説明する。

range-based forに初期化子が書けるようになった。

for ( auto result = f() ; auto && value : result ) ;

<bit>にbit_castingが追加された。

short from = 42 ;
auto to = bit_cast<std::uint16_t>(from) ;

operator <=>が追加された。

operator <=>は2つのオペランドの大小比較と等号比較を一度にできる演算子だ。この演算子を定義しておけば、残りの比較演算子はコンパイラーが自動的に生成してくれる。型システムによってstrong order, weak order, partial orderのいずれに対応しているかも切り替えられる。

atomic<shared_ptr<T>>が追加された。shared_ptrをアトミックに操作できる。

remove_cvref traitsが追加された。CV修飾子とリファレンスを消したいが、配列から要素型、関数から関数へのポインター型への変換は行いたくない場合に、decayの代わりに使える。

[[nodiscard]]が一部の標準ライブラリで使われることになった。

同期バッファー付きのostreamラッパーライブラリ、osyncstreamが追加。

// 複数のスレッドから同時に実行されうる関数
void f()
{
    std::osyncstream out( std::cout ) ;
    out << "hello, world!\n" ; 
}

スレッドセーフなostreamラッパーとして使うことができる。

<alogorithm>と<utility>の一部をconstexpr対応。

<comlex>をconstexpr対応。

atomic<floating_point_type>

stringとstring_viewにstart_with/end_withの追加。

また、現在策定中のconstexpr対応のnew, vector, stringは、後数回の会議でドラフト入りできる見込みだというぐらい本格的に議論されているようだ。本気で入れる様子が伺える。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

国家政府用のbitcoin破壊工作ガイド

How to Destroy Bitcoin with 51% (pocket guide for governments)

あなた、政府系の人ですか? bitcoin危険だと思いますか? いやいや滅相もない他にやるべきことがたくさんありますよ。まあでも、ちょっとここではbitcoinが疎ましいと思ってくださいよ。そうそう、あなたは中国だとします。

どうやって止めるのですか? みんな暗号通貨はセキュアで無敵だって言うじゃないですか。ちゃんとコントロールしたいあなた達政府系の人にとってはだいぶおつらいですよね。

Bitcoinを止めるのは実際難しくて、個人を何人か逮捕してサーバーを停止させたぐらいじゃ止まりません。Silk RoadやE-GoldやLiberty Reserveとは違うんですよ。そして参加者はだいたい権力を嫌ってます。

暗号通貨では停止させるべき中央サーバーってものがないんですね。ユーザーはみんな、フルノードをセキュリティ目的で実行してますから(理想的な世界ならばそうなのですが、現実ではだいたいのユーザーは有名所のクラウド提供されたWebウォレットを使ってるようですね)

でも、マイナーとかバリデーターとかウィットネスとか呼ばれているルールに従って選ばれた調停者ってのがいます。Bitcoinではマイナーはハッシュ(計算コストが高く安い電気が必要)の発見に精を出しています。そしてほとんどのマイナーはあなたの国にいるんですね。

画像:中国が世界の71%のマイナーを持つ。
https://cdn-images-1.medium.com/max/1600/1*RyaqdlQMBhrdxDlpnCh7eQ.png

マイナーを止めるってのはバカげた話です。Bitcoinはその維持にマイナーを必要となんかしていません。マイナーはセキュリティのために必要なのです。なので、あなたがた政府系の人がマイナーを差し止めたら、難易度調整が入って他の国のマイナー達がネットワークをセキュアにし続けるってわけです。

Bitcoinを殺すなら、ガツンと凶悪な51%攻撃ってやつをやってやりましょう。

ステップ1、bitcoinを買い集める

大手の交換所すべてに、アカウントを作成しましょう。取引所ひとつにつき10から40アカウントぐらい。さて100箇所ぐらいの交換所にそれぞれ40個のアカウントを作りましたね。上出来です。まず景気づけに1億ドル分ぐらいのBitcoinを買いましょう。あなた、政府系の人ですよね? 国家の安全のためにはそれぐらい捻出できますよね?

これを書いている時点でBitcoinの市場総量というのは950億ドルぐらいなので、0.1%ぐらいの量になります。わりかし悪くないレバレッジですね。

交換所にある通貨をすべてあなたの所有するウォレットに送金しましょう。個々が一番難しいところで、暗号通貨のウォレットのユーザーエクスペリエンスは最悪で、誤操作で結構な金を失う可能性があります(ジョークON)

ステップ2,51%のマイナーを見つけましょう

https://www.buybitcoinworldwide.com/mining/china/によれば、世界のマイナーの71%は中国にいます。彼らは地下に隠れていますが、まあでも、そこはあなた中国政府。あなたは人民のスマフォにスパイウェアの導入を義務付けたり、https://thenextweb.com/asia/2017/07/25/chinas-forcing-its-citizens-to-install-a-terrifying-big-brother-app-on-their-phones-or-go-to-jail/しているわけですから、捜索はそう難しくはないでしょう。

ヒント:彼らは盗電してます。調べましょう。

たとえばこれはオルドスの例ですね(北京からそう遠くないですよ)

https://qz.com/1055126/photos-china-has-one-of-worlds-largest-bitcoin-mines/

ステップ3、秘密作戦

さて、秘密警察組織に作戦実行のデイXまでにできるだけ多くのマイナーを捜索するよう命じましょう。

これは法執行機関さんのやることですので、あなたの国のお巡りさんは説得に当たってマイナーの頭に銃を突きつけてもよいでしょう。このお願い方法はマイナーが知らんふりを決め込んでいるのを説得させるのにとても効果的です。

国家政府が物事を成し遂げるってのはこういうことですね。しかも、あなたは中国なのですから、こういう活動をするにあたってリベラルを装う必要すらないのですよ。

ステップ4、倍々ゲーム

マイナー達に以下の操作を行わせましょう。あなたのウォレットの単一のブロックから4000トランザクション(1つあたり25000ドル)ほど掘らせて全体に行き渡らせます。この4000トランザクションはステップ1で作ったアカウント群に送金を戻すことに使います。

通常、取引の成立には6ブロック重ねる(承認)ことが必要です。

さて、世界のネットワークは今や、あなたのブロックの上にブロックを重ねています。その間に、あなたのほったブロックの上に自分でブロックを重ねましょう。

つまり、ブロックNに対してみんなにブロックN+1を送ります。するとみんなBlockN+2とBlockN+3を掘るのに勤しむわけです。あなたはかわりに、別ブランチのブロックN+1BとブロックN+2Bを掘りましょう。

あなたは51%を持っているのですから、たぶんみんなよりは速く掘れるでしょう。よそのマイナー達があなたのブロックに対して6ブロック承認を終えたら、あなたは持っているBitcoinを全部他の何かに交換しましょう。LitecoinだとかRippleだとかEthereumとか、まあ何でもいいです。普通に交換できるはずです。そしたら、あなたは交換したaltcoinをあなたのウォレットに送ります。

BTCをすべてaltcoinに変えて、altcoinを引き出した後に、あなたの4000トランザクションを無効化するもう一つの秘密のブランチを公開します。

これはリオーガニゼーションというやつです。これでネットワークはあなたのチェインを本流として受け入れ、オーファン化した他のトランザクションのことは忘れなければなりません。

ステップ5、暗号通貨市場の価値が暴落するのを眺めましょう

さて、これによって1億ドルの価値があるBitcoin(交換所はもう持っていない)が、1億ドルの価値があるaltcoin(あなたが持っている)に変わったわけです。おめでとうございます。あなたは2億ドル分の暗号通貨を手に入れました。その市場価値は暴落するでしょうが、目的は市場価値の暴落にあるのだから問題ないでしょう。

この攻撃をもう一発行ってもいいのですが、その必要はないでしょう。この規模の攻撃が一度起こっただけでも、暗号通貨に対する信頼に大打撃となり、数年は市場が暴落するでしょう。

よその国家にはどうしようもできません。Bitcoin自体にはまともな法規制や慣習が存在しないのですから。なので秘密に攻撃してもいいし、公に攻撃しても構いません。

再考

この記事は筆者の現状に対する不満を述べたものであるが、筆者はBitcoinに反対するものではない。筆者は我々が現在陥っている愚行について憤っているのだ。

我々はもう一度原点に立ち返ってパラノイアになるべきであり、我々の脅威モデルを適切に設定すべきなのだ。お前が今やっているのは何だ? スマートコントラクト? ブロックチェインによる個人認証? クソコインとクソコインを分散取引? ICO? そういうことは検閲耐性というブロックチェインにおける唯一の重要な事に比べれば完全に無価値なものだ。検閲耐性以外の余りのクソはお前の5ドルのサーバーでも1000倍は効率的にやってくれる。

お前が検閲耐性などいらないのであれば、わざわざビットコインなど使わないでもっと効率的にやれ。

この攻撃はEthereumに対してはより簡単だ(ステップ1,Ethereum創始者のVitalikを捕まえろ)。他の暗号通貨に対しては51%攻撃というのはヘリコプター一台分の金を使ってASICを投下するだけでよい。なのでやるのであれば、Bitcoinに対して攻撃して他の暗号通貨がドミノ効果で信用を失っていくさまを眺めるがよい。

追記:読者が中国ではなく、中国にジェイムズ・ボンド級のスパイを放って51%のマイナーをハイジャック出来ない場合、Bitcoinに対して51%攻撃をしかけるのはもっと難しい。なので中国を説得してやってもらうしかない。

ちなみに、この51%攻撃(Double Spending)は全体の51%のハッシュレートを持っていれば確実に成功するが、51%より少ないハッシュレートしか持たない場合でも、確率的に成功する。この攻撃は一度成功させるだけで信頼に大打撃を与えられるので、全体の20%程度のハッシュレートしか持たず、確率的に数%しか成功しない場合でも、中国共産党が本気で暗号通貨を潰しにかかった場合、割と実現可能性の高い攻撃ではある。

Analysis of hashrate-based double-spending

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0