Showing posts with label programming. Show all posts
Showing posts with label programming. Show all posts

2020-04-16

Error handling in Erlang

Last time, I wrote about how to write a hello world HTTP server by using Erlang, Cowboy and Rebar3.

Walkthrough of hello world HTTP server with Erlang, Cowboy, and Rebar3

Today, I'm going to write about the error handling in Erlang.

The error handling in Erlang is easy if we can ignore the error. That is, we don't expect the error. In the event of unlikely failure, we immediately abandon any computation we were doing and start over. The OTP and other famous frameworks were written by following Erlang culture of error handling so it will handle it well. If, on the ohter hand, the errors are expected to happen, so we have to explicitly deal with it. Erlang is suddenly reared its ugly head.

How a function notify it's caller the failure? In other languages, like Haskell, there is a Maybe type which may or may not contains the value. Erlang is not staticaly strong typed language so the Erlang version of the Maybe is tagged tuple. We return ok or {ok, State} upon success and we return any other value otherwise. It may be {error, Reason}, empty list [], or simply an atom like error, false, undefined whatever.

The user of such functions must match the returned value with ok tagged tuple,

do_something( State ) ->
    {ok, State_1} = f( State ),
    do_normal_things.

If the function f return anything other than {ok, any()}, match failed and throw an exception of error:{badmatch, V}. So hopefully, the higher framework catch these exceptions and restart the process.

But what if the caller want to deal with the error? We have to use the patter match for the conditional execution. It can be done by case expression or function.

case expression:

do_something( State ) ->
    case f( State ) of
        { ok, State_1 } -> do_normal_things ;
        { error, Reason } -> do_error_handling
    end.

function :

do_something( State ) ->
    do_something_1( f( State ) ) .

do_something_1( { ok, State } ) -> do_normal_things ;
do_something_1( {error, Reason} ) -> do_error_handling .

Whichever you use, it became quite verbose and boilar-plate.

Erlang has exception like many other langauges. But I feel some oddities on Erlang's exception and that is the concept of class.

The Erlang has three class of exception: error, exit, and throw. These are thrown by calling function error/1,2, exit/1, and throw/1 respectively.

If you don't care about exception, you need to do nothing. But if you care, that is, you want to run some code on the condition of exception, things get verbose.

Let's suppose that previous function f/1 return { ok, State } on success, but throw some exceptions otherwise and you want to deal with it because you expect it to happen. You can use try expression or catch expression

try expression is strightforward, if you ignore the awkward Erlang grammer that is.

try Exprs
    catch Class1:Pattern1 -> Body1 ;
    catch Class2:Pattern2 -> Body2
end

The class is either error, exit, or throw, pattern may vary. If you were to catch the exception thrown by error class's badmatch(1 = 2), it looks like this.

try 1 = 2
    catch error:{ badmatch, V } -> its_bad_man
end

Now, how to do_normal_thing and do_error_handling depending on the presense of exception? try expression can have of section and it will be evaluated only on no exception in Exprs.

try f( State ) of
    { ok, State_1 } -> do_normal_thing ;
catch
    throw:something_went_bad -> do_error_handling
end

Now how to deal with the situation where the error will be reported in either by value or exception? Use try expression's of section to pattern match the error value.

try f( State ) of
    { ok, State_1 } -> do_normal_thing ;
    { error, Reason } -> do_error_handling
catch
    throw:something_went_bad -> do_error_handling
end

There is another way to deal with the exception. The catch expression.

catch Exprs

catch expression evaluate Exprs and return its value on no exception. In case of exception, the value will be either

For exceptions of class error, that is, run-time errors, {'EXIT',{Reason,Stack}} is returned.

For exceptions of class exit, that is, the code called exit(Term), {'EXIT',Term} is returned.

For exceptions of class throw, that is the code called throw(Term), Term is returned.

Erlang -- Expressions

If it's by throw({error, Reason}), the code will be clean.

case catch Exprs of
    { ok, Value } -> do_normal_thing ;
    { error, Reason } -> do_error_handling
end

But if it's error class, the code is too ulgy to read.

case catch 1 = 2 of
    { 'EXIT', { {badmatch, _} }, _ } -> do_error_handling
end

Perhaps, error and exit class were not meant to be handled by catch expression, but some library use these even for the predictable situations. like list_to_integer, binary_to_integer. My guess is to keep the backward compatibility.

Putting it all togather, it's very verbose to handle errors in Erlang.

Let's quickly borrow a code from the hello world HTTP server I explained in the previous article. Walkthrough of hello world HTTP server with Erlang, Cowboy, and Rebar3

Instead of returning the hello world, we're going to return the sum of two query parameter a, b.

$ curl "http://localhost:8080/?a=1&b=2"
3
$ curl "http://localhost:8080/?a=1&b=-100"
-99

All we need to do is modify the cowboy_handler. The simplest code that assume no error will be like this.

init( Req, State ) ->
    P = cowboy_req:parse_qs(Req),
    { _, A } = lists:keyfind(<<"a">>, 1, P ),
    { _, B } = lists:keyfind(<<"b">>, 1, P ),
    Sum = integer_to_binary( binary_to_integer(A) + binary_to_integer(B) ),
    Req_1 = cowboy_req:reply( 200,
        #{<<"content-type">> => <<"text/plain">>},
        Sum, Req ),
    {ok, Req_1, State ).

Well, it's not bad. But I want to deal the the error.

Suppose, the users forget the query parameters.


$ curl "http://localhost:8080/"
$ curl "http://localhost:8080/?a=1"
$ curl "http://localhost:8080/?b=1"

If this happend, our code failed the pattern match because lists:keyfind returns false.


{ _, A } = false,

In such cases, I want to reply with the helpful error messages like this.


$ curl "http://localhost:8080/"
Error: missing query parameter a, b.
$ curl "http://localhost:8080/?a=1"
Error: missing query parameter b.
$ curl "http://localhost:8080/?b=1"
Error: missing query parameter a.

We can do condional branching with either case expression or function pattern match.

Another type of error is although the query paramters are present, it has a string that cannot be parsed as an integer.


$ curl "http://localhost:8080/?a=abc&b=123"

I would like to reply with helpful error messages in this case too.

After consdering the various code, I come up with this code. It's too verbose and ugly but I think alternatives are worse.

init( Req, State ) ->
    P = cowboy_req:parse_qs(Req),
    A = lists:keyfind( <<"a">>, 1, P ),
    B = lists:keyfind( <<"b">, 1, P ),
    { Http_status_code, Answer } = process( A, B ),

    Req_1 = cowboy_req:reply( Http_status_code,
        #{&lt;&lt;"content-type"&gt;&gt; =&gt; &lt;&lt;"text/plain"&gt;&gt;},
        Answer, Req ),
    { ok, Req_1, State }.

process/2 is set of function that ultimately returns { integer(), iodata() }. Here is the verbose code.

%% for missing query parameters.
process( false, false )     -> { 400, <<"Error: missing query parameter a, b.\n">> } ;
process( false, _ )         -> { 400, <<"Error: missing query parameter a.\n">> } ;
process( _, false )         -> { 400, <<"Error: missing query parameter b.\n">> } ;
%% for invalid query parameters
process( badarg, bardarg)   -> { 400, <<"Error: invalid query parameter a, b.\n">> } ;
process( badarg, _ )        -> { 400, <<"Error: invalid query parameter a.\n">> } ;
process( _, bardarg)        -> { 400, <<"Error: invalid query parameter b.\n">> } ;
% lists:keyfind succeeded.
process( { _, A }, { _, B } ) ->
    process(
        try binary_to_integer( A ) catch error:badarg -> badarg end,
        try binary_to_integer( B ) catch error:badarg -> badarg end
    ) ;
% no invalid query parameter. return the result.
process( A, B ) ->
    { 200, { integer_to_binary( A + B ), <<"\n">> } } .

The -spec attribute for this process/2 is abomination.

-spec process(
    { bitstring(), bitstring() } | false | badarg | integer(),
    { bitstring(), bitstring() } | false | badarg | integer()
)  -> { integer(), iodata() }.

Well, at least, I understand the error handling of Erlang.

2020-04-13

Erlang, Cowboy, Rebar3によるHello World HTTPサーバーのチュートリアル

本記事では、Erlang, Cowboy, Rebar3によるHello worldを出力するHTTPサーバーの実装方法を解説する。

目的は、このプログラムを実行中に、以下のような挙動になることだ。

$ curl "htttp://localhost:8080/"
hello,world

ErlangもCowboyもRebar3も、情報が極めて少ない。しかも公式ドキュメントすら間違っている。公式ドキュメントすら間違っているのには理由があり、実際の実装とドキュメントに差がでているのだ。Erlangは変化の少ない言語ではあるが、それでもOTP17からmapが追加されたりと言語的に少し変わっているし、mapの追加により、cowboyも以前ならproplistsを使っていた部分でmapを使うようになり、しかも2.0でAPIかなり破壊的な変更が入り、2.5からはモジュールの構成も少し変わってしまった。Rebar3は本当にひどい。名前が示すように、すでに破壊的な変更を2回経ている。そして技術的負債の塊だ。

この記事で解説する程度の知識を得るのに私は公式ドキュメントと何ヶ月も格闘するはめになった。公式ドキュメントですらこうなのだから、非公式なドキュメントは本当に参考にならない。ここに書いてあることは2020年の時点では正しいが、来年はわからない。

準備

Erlang実装とRebar3が必要だ。CowboyについてはRebar3がダウンロードしてくれるので考えなくてよい。

Debian系のディストロでErlangをインストールする。

$ apt install erlang

GNU/Linuxでrebar3をインストールする最も信頼できる方法は、自前でビルドすることだろう。

$ git clone https://github.com/erlang/rebar3.git
$ cd rebar3
$ ./bootstrap

これで"rebar3"というファイルができるので、このファイルをPATHの通ったディレクトリにコピーするかシンボリックリンクをはればよい。

ln -s rebar3 /usr/local/bin

これで準備が完了した。

プロジェクト作成

まずrebar3を使ってプロジェクトを作成する。名前を"hello_server"としよう。

$ rebar3 new release hello_server
$ cd hello_server

このコマンドで"hello_server"というディレクトリが作成される。その中にはテンプレート生成されたファイルがいくつかある。重要なものだけ説明する。

"hello_server/rebar.config"は設定ファイルで、cowboyの依存を追加するために編集する。

"hello_server/apps"ディレクトリにはアプリケーションが配置される。rebar3のreleaseプロジェクトはumbrella projectと呼ばれていて、複数のアプリケーションを持つことができる。

"hello_server/apps/hello_server"はrebar3がテンプレートから生成したアプリケーションだ。このディレクトリ内には"src"ディレクトリがあり、3つのファイルが作成されている。"hello_server_app.erl", "hello_server_sup.erl", "hello_server.app.src"だ。

"hello_server_app.erl"はapplication behaviourを実装するソースファイルだ。

"hello_server_sup.erl"はsupervisor behaviourを実装する。今回は編集しない。

"hello_server.app.src"はapplication resource fileを生成するためのソースファイルだ。Erlang VMをどのように実行するかということを設定するためのファイルだ。rebar3はこのファイルから実際のapplication resource fileを生成する。このファイルも編集する。

Cowboyを依存に追加

Cowboyを依存に追加してrebar3にダウンロードしてもらう。そのために"hello_server/rebar.config"を編集する。

$ vim rebar.config

最初の数行は以下のようになっている。

[erl_opts, [debug_info]}.
{deps, []}.

[relx, [{release, {hello_server, "0.1.0"},
...

今回編集するのは2行目、つまり"{deps,[]}."という部分だ。このlistのなかに依存を記述していく。記述のフォーマットは様々だが、すべて"{ package_name, ...}"という形のtupleになっている。このチュートリアルではパッケージをhex.pmからダウンロードしてくるので、フォーマットは"{ package_name, "version number"}"になる。本チュートリアルを執筆時点で、最新の安定版のcowboyのバージョンは2.7.0だ。


{deps, [
    {cowboy, "2.7.0"}
]}.

rebar3は依存ライブラリが必要になった時に自動的にダウンロードするが、今回は正しく記述できていることを確認するために明示的にダウンロードしてみよう。

$ rebar3 upgrade

次に、アプリケーションリソースファイルを編集して、cowboyを先にスタートさせるようにする。今実装しているアプリケーションはcowboyを使っているので、cowboyを先にスタートさせておかなければならない。その設定方法として、"hello_server.app.src"を編集する。

$ vim apps/hello_server/src/hello_server.app.src

このファイルの中身を抜粋すると以下のようになっている。


{application, hello_server,
  [...
  {applications
    [kernel,
     stdlib
    ]},
  ...
  ]}.

applicationsのtagged tupleの中のlistに"cowboy"を追加する。

{application, hello_server,
  [...
  {applications
    [kernel,
     stdlib,    % カンマを忘れないこと
     cowboy     % この行を追加
    ]},
  ...
  ]}.

これはErlangのlistなのでカンマを忘れないようにすること。

HTTPサーバーの始動

容易が全て整ったので、HTTPサーバーを開始する。まず"apps/hello_server/src/hello_server_app.erl"を編集する。

vim apps/hello_server/src/hello_server_app.erl

このソースコードはrebar3によって生成されたapplication behaviourを実装するためのモジュールだ。start/2を変更して、HTTPサーバーを開始する。

start(_StartType, _StartArgs) ->
    hello_server_sup:start_link().

HTTPサーバーを開始してコネクションをlistenするには、まずcowboy用語でルートと呼ばれているものを設定する。これは特定のリモートホストやパスをcowboy_handlerに関連付けるための設定だ。ルートを設定するにはcowboy_router:compile/1を使う。この関数は引数としてcowoy_router:routes()型を取る。型は"[{Host, Pathlist}]"となっている。PathList型を展開すると、"[{Host, [{Path, Handler, InitialState}]}"となる。

start(_StartType, _StartArgs) ->
    Dispatch = cowboy_router:compile([
        { Host, [{Path, Handler, InitialState}]}
    ]),
    hello_server_sup:start_link().

ホストとして'_'を指定すると、任意のホストからのコネクションを受けつける。ホストを制限したい場合、例えばlocalhostからの接続しか受け付けたくない場合は、<<"localhost">>を指定する。

今回の場合、Pathは<<"/">>だ。今回は"http://localhost/aa/bb/cc"のようなPathは受け付けないのでこれでいい。

Handlerにはhello_handlerというatomを指定する。これは後でcowboy_handler behaviourを実装するモジュールとして実装する。

特に状態は持たないので、InitialStateは空のlistを使う。

すべてまとめると、以下のようなコードになる。

start(_StartType, _StartArgs) ->
    Dispatch = cowboy_router:compile([
        { <<"localhost">>, [{<<"/">>, hello_handler, [] }]
    ]),
    hello_server_sup:start_link().

ルートが準備できたので、HTTPリスナーを開始する。ここでは素のHTTPを使うので、cowboy:start_cear/3を使う。引数はstart_claer( Name, TransportOpts, ProtocolOpts )だ。

NameはこのHTTPリスナーを識別するための名前で、ErlangのTermであればなんでもよい。通常はatomが使われる。ここでは"hello_listener"を使う。

TransportOptsには様々なオプションがあるが、このチュートリアルではlistenするポートを指定するだけだ。今回はHTTPサーバーのポートはは通常80だが、今回は8080を使うので、"{{port, 8080}}"となる。

ProtocolOptsでは先程設定したrouteを指定する。ProtocolOptsの型はmapで、envというキーがあり、値はdispatch型だ。ここに先程束縛したDispatch変数を指定する。

成功した場合、start_clear/2は{ok, pid}を返す。okのtagged tupleに束縛することで失敗時のことはapplication behaviourにまかせよう。

start(_StartType, _StartArgs) ->
    Dispatch = cowboy_router:compile([
        { <<"localhost">>, [{<<"/">>, hello_handler, []}] }
    ]),
    {ok, _} = cowboy:start_clear(
        ello_listener,
        [{port, 8080}],
        #{env => #{dispatch => Dispatch}}
    ),
    hello_server_sup:start_link().

接続の処理

HTTP listenerの用意が出来たので、やってきた接続要求を処理していく。そのためにはさきほどのhello_handlerを実装しなければならない。これはcowboy_handler behaviourとして実装する。まず新しいソースファイルを作成する。

$ vim apps/hello_server/src/hello_handler.erl

まず基本的なところを埋めていこう。

-module(hello_handler).
-behaviour(cowboy_handler).
-export([init/2]).

init( Req, State ) ->
    {ok, Req, State}.

Reqはリクエストとレスポンスを保持している。Stateは好きに使える状態だが今回は使わないので空のlistとする。

やるべきことは、HTTPステータスコードとして200を返し、ヘッダーのcontent-typeとしてはtext/plainを指定し、コンテンツは"hello,world"とするだけだ。これにはcowboy_req:reply/4を使う。引数の型は"reply(Status, Headers, Body, Req)"だ。

StatusはHTTPステータスコードで型はnon_reg_integer()もしくはbinary()だ。今回は200を指定する。

HeaderはHTTP headerをmap()で指定する。今回は"content-type"を"text/plain"にする。

Bodyには<<"hello,world">>を指定する。

Reqは現在のReqオブジェクトだ。

replyは新しいReqオブジェクトを返す。これ以降Reqオブジェクトを使う際には、この新しいReqオブジェクトを使わなければならない。

init/2のコードは以下のようになる。

init( Req, State ) ->
    Req_1 = cowboy_req:reply(
        200,
        #{<<"content-type">> => <<"text/plain">>},
        <<"hello,world">>,
        Req
    ),
    {ok, Req, State}.

プログラムの実行

$ rebar shell

確認しよう。

$ curl "http://localhost:8080/"
hello,world

次はErlangのエラー処理について書こうと思う。Erlangのエラー処理はその場で処理を中断して無視していい場合は簡単だが、エラーに明示的な対処が必要だととたんに面倒になる。

2019-10-03

また初心者にプログラミングを教える機会があった

プログラミングでわからないところがあるので教えてほしいと以下のようなことを聞かれた。

こういうJavaScriptの関数がある。

// valuesは配列
// elementはvaluesの要素型の値
// 配列valuesに値elementと等しい要素があるならばそのインデックスを返す。
// それ以外の場合、-1を返す
function find_index( values, element )
{
    for ( let i = 0 ; i !== values.length ; ++i )
    {
        if ( values[i] === element )
            return i ;
    }
    return -1 ;
}

質問は、「なぜreturn -1にelseはいらないのか」というものであった。

似たような問題に、昔遭遇した気がするが、別人だ。

まずここにelseを書くべき文法はJavaScriptに存在しない。if文で何らかの条件を切り分ける必要もない。なぜならば、return -1が評価されるとき、すでにforループを抜けているわけで、その場合要素が見つからなかったということだ。逆に、要素が見つかったのであれば、すでに上のreturn iが評価されているので、すでに処理は関数の呼び出し元に戻っており、return -1は評価されることがない。

ただ、このような机上の説明を繰り返しても理解ができない様子であったので、さらにデバッガーでステップ実行してみせるなどして説明した。

この問題は、逐次実行という概念と、逐次実行がfor文やif文やreturn文によって変わるということ、そしてプログラミングにおける関数の理解が必要だ。しかし、筆者はこのような概念の理解に苦労した覚えはないし、周りの職業プログラマーに聞いても、やはり苦労した覚えはないという。

しかし不思議だ。質問者は数学の素養があり、数学における関数なら理解しているはずだ。聞けば再帰も理解しているという。それならと以下のように再帰で書いてみた。


function find_index( values, element )
{
    function solve( i )
    {
        if ( i === values.length )
            return -1 ;

        if ( values[i] === element )
            return i ;

        return solve( i + 1 ) ;
    }
    return solve(0) ;
}

これを何の説明もせずに見せたところ、「これはとても良くわかる。なんでみんなこう書いてくれないのか」とのことであった。質問者はJavaScriptの初歩の初歩しか学んでおらず、このようなコードは見たことがないはずだ。しかしわかりやすいと言う。再帰は正しく理解できていることが確認できた。

質問者にはHaskellのような純粋関数型の言語のほうが向いているのかもしれない。

2018-07-31

GCCのgit移行が難航中

GCCはgitへの移行を計画しているが、GCCの既存のsubversionレポジトリをgitレポジトリに変換する作業が難航している。

GCCの移行作業を検証しているのは他ならぬEric S. Raymond(ESR)だ。

ESRお手製の変換ツール、reposurgeonはsubversionからgitへの変換ができる。

Resource page for reposurgeon 3.44

しかしGCCは30年もの歴史を持ち、そのsubversionレポジトリも複雑だ。

ESRはGCCのためにreposurgeonのバグを潰し、勢い変換しようと試みたが、意外な障害に出くわした。メモリ不足だ。

GCC's Conversion To Git Is Being Held Up By RAM, a.k.a. Crazy DDR4 Prices - Phoronix

ESRの所有する64GBのメモリを詰んだマシンではメモリ不足で処理できない。そしてDDR4メモリの値段は高騰している。GCCのビルドサーバーに128GBのメモリを詰んだものがあるからそれを使わせてくれとか、reposurgeonをPythonからGoに移植すればメモリ消費量は減らせる可能性があるが移植は困難を極めるとか、ESRに投げ銭してメモリを買わせようなどと議論をしていたのが7月はじめ。

さて、今はメモリ以外の問題に出くわしている。

GCC's Conversion To Git Is Still Turning Out To Be A Massive Headache - Phoronix

どうもGCCの膨大で複雑な歴史を正しくgitで表現する方法について議論の余地がある他、変換結果が壊れることもある。問題を解決したいが、変換自体がとても遅いため、デバッグが困難だという。

https://gcc.gnu.org/ml/gcc/2018-07/msg00322.html

トンネル出口の明かりが見えたと思ったら対抗列車が突っ込んできやがった。

もう変換はほぼほぼ終わりだと思っていたのに。俺はtrunkとブランチすべてがクリーンに変換されるのを確認したのに。捨ててもいいことに同意した失敗ブランチただ一つを除いては。

後残っているのはexecute-permission propagationとかmid-branch deleteをどうするかという問題だけで、前者はすでに解決済みだし、後者も解決に取り掛かっている。最終的には年末には、たぶん8月とか9月には、完了できるはずだったのに。

そしたらこのザマよ。俺の最新の変換がtrunkで間違った結果を出しやがった。これは実際ヤバイ問題で、GCCレポジトリがあまりにも巨大すぎるので調査するのに時間がかかりすぎる。SVNダンプファイルをreposurgeonで読み込むだけで4.5時間かかるし、フル変換に9時間はかかる。レポジトリは俺が最適化を考えるのと同じぐらい早く増大しているぜ。

しかも悪いことに、クリーンな変換ができるコミットまで戻っても失敗する。たぶん俺がへんてこなブランチコピーの対処を実装した結果こうなってるんだと思う。

パーティーに遅れてやってきた奴のために説明してやると、Subversionのダンプファイルの処理シーケンスの解釈は単純で検証も楽だ。ブランチコピー操作を除いてはな。ブランチコピーが他の操作に及ぼす影響だけはマジで闇が深い。

Subversionのコードが何をすべきかっていう正しいセマンティクスは存在するわけだが、古のSubversion開発者が理解していたことは、今や失われている。ダンプフォーマットはまともにドキュメント化されていない。今の不完全なドキュメントが存在する理由は、他でもない俺が解析したからだ。でも俺のドキュメントも疑問だらけだし、その疑問にはSubversion開発者も回答できないできる。

なのでレポジトリを変換する際にブランチコピーに関連した謎の挙動に出くわすのはよくあることだ。普通、おれは問題のコミットをbisectして、

  1. ダンプを問題が再現する最小のセグメントに切り取る
  2. content blobsをsource commitを識別できるunique small cookiesに置換する処理を行って結果が正しいことを検証
  3. topological reduceしブランチコピーもプロパティ変更でもない無価値なコミットを除去し、結果が正しいことを検証
  4. 手動で不必要なブランチをreposurgeonで削除

いつもなら、俺は今頃、問題を再現できる割と小さめのレポジトリ(今までで200コミットを超えたことはない)を作ってる。デバッグレベルを上げて変換を観察し、何が起こっているのかを観察する。そして問題を修正し、問題を再現する最小例は新たなテストケースになるって寸法だ。

これによって、ダンプファイル解析を着実に改善していき、Subversionのコードがやっていることをより忠実にエミュレートしていく。簡単な仕事ではないが、エッジケースを埋めていくほど楽になる。今まではこれでうまくいってきた。

GCCレポジトリのサイズでは、この戦略がうまくいかない。軽く計算するだけで、bisect一回で最短でも18日かかる。現実的には一ヶ月近くかかるだろう。

つまり、現状ではゲームオーバーで負けたってことだ。GCCレポジトリはでかすぎる上に変すぎる。

この問題を現実的に解決するには、俺のツールはすっげー速くなる必要がある。だいたい桁違いに早くないといかん。

ハードウェア性能を上げるのは無理だ。シングルプロセスを1.3GHz以上にあげたコンピューターはこの世に存在しないし、問題は並列化できない。

ソフトウェアの変更でうまく行く可能性はある。俺はreposurgeonをPythonからGoに移植するということについて考えている。repocutterで実験してみたところ、{Python版の40倍高速化した。reposurgeonではそんなに高速化するとは思えないが、問題を現実的に解決できるぐらいには高速化できるだろうと踏んでいる。40倍の半分だったとしても、9時間のテストランが13分になるわけだから。

この計画の問題点は、GOに移植するのは困難を極めるってことだ。めっちゃむずい。どのくらい時間がかかるかわからんが数カ月単位でかかる。

GCCはどのくらい辛抱強く待つのか決める必要があるな。現状だと、今のソースツリーの状態をそのままgitにしていちからはじめるほうがマシかもしれん。歴史は記録だけに留めるとして。

2018-05-29

世の中にはプログラミングを理解できない人間が存在する

現在、C++によるプログラミングの入門書を書いているので、初心者のプログラミングの学習過程にとても興味がある。私自身も初心者の気持ちを取り戻すためにHaskellを学んでみた。最初の数日は頭が痛くなるほど難しかったが、そこを過ぎてみれば後は楽になってしまった。結局、初心者の気持ちはあまりわからなかった。結局、プログラミングの基礎はすでに学んでしまっているので、

先日、FizzBuzzがわからないから教えてくれという知人がいたので、これは初心者の気持ちを知るいい機会と話を聞いてみたところ、想像を絶する世界が見えてきた。

まずこれが動かないと悩んでいたコードだ。


for ( int i = 0 ; i <= 100 ; i++ )
{
}
else if ( i % 15 == 0 )
{
    Debug.log("FizzBuzz") ;
}
else if ( i % 3 == 0 )
{
    Debug.log("Fizz") ;
}
else if ( i % 5 == 0 )
{
    Debug.log("Buzz") ;
}
else
{
    Debug.log(i) ;
}

一見するとそれらしいソースコードのようにみえるが、そもそも文法が間違っている。文法が間違っている箇所を指差しても納得しない。for文の文法を説明しようとするが聞く耳を持たない。「これが間違っているなら参考にしている教科書も間違っている」との一点張りで誤りが存在していることを頑なに認めない。参考にしているらしいスライド資料にのっているコード例と比較させても間違いの箇所を判断できない。for文の文法の説明をもう一度試みるがやはり聞く耳を持たない。

そしてソースコードの見た目を適当に書き換えてなんとか問題を「修正」しようと試みる。私はいつシェイクスピアの名作が出来上がるだろうかと考えながらその様子を見守っていた。

ややあって、奇跡的にソースコードが適切な形に「修正」された。しかし出力は期待通りにならない。当然だ。なぜならこれはUnityで、使っているのはデバッグログ用の機能であって、重複は省かれるからだ。出力は、1, 2, "Fizz"というメッセージが何件, 4, "Buzz"というメッセージが何件, 7, 8...と続く

そもそも基礎的なプログラミングの知識が十分ではないのだから、Unityはやめてもっと罠の少ないCLI環境でプログラミングの基礎を学ぶべきだと諭しても、「Unityは私がやりたいことを実現できる環境であり私のモチベ維持のために重要であるからUnityでやる」といって改めようとしない。

これは一体どうすればいいのだろう。こういう人間は教育不可能だ。この人物の経歴を見るに、どうもそれらしく見えるモックアップをでっち上げてきたアート系の人間のようだ。本人は今の時代は科学とアートは同じものでありアートを融合することでユーザービリティを考慮したUIが云々などと、まるでピタゴラス派のようなことを言う。世界は人間にとって美しい数字とか法則で定義されるべきであり、定義が観測結果に従わないとしても定義は正しいと主張したのがピタゴラス派だ。アートに引きこもっているならそれでいいのだが、それは科学ではない。コンパイラーのソースコードの解釈はこの自然界には珍しいことに冪等性を持っているのだから、見た目をでっち上げるのではなくて本質を理解すべきなのだ。たとえその本質が自分の美学に合わなかったとしてもだ。私は本棚にあったアラン・ソーカルの著書、知の欺瞞を手に取らせてみたが、あまり興味は示さなかったようだ。

こういう人間によって書かれたソースコードは一見もっともらしく見えるが、文法違反の間違ったコードとなる。どこかからか発見してきたコードをコピペしてツギハギしてそれらしい見た目のソースコードをでっち上げる。人間相手であれば、いかにも主題について理解したかのようにもっともらしくでっち上げた小論文を書いて読ませれば筆者は主題を理解していると読者を騙すことは可能だが、ことコンパイラーが相手では文法違反のソースコードを騙すことなどできない。

思うに、先天的に、あるいは幼少期の教育の結果、プログラミングに向かない学習方法に最適化されてしまった人間がいるのではないだろうか。物事の本質を完全に理解するにはコストがかかる。しかし、不完全な理解だがそれらしいものをでっち上げるにはコストがかからない。そして、人間には、それらしくでっち上げられた偽物と、本質を理解した上で作られた本物を判別するのが難しい。一方コンピューターは違う。コンパイラーはソースコードがいかに本物のソースコードらしい見た目をしていようとも、文法違反のソースコードを判別できる。コストを書けずに結果を出すためにそれらしくでっち上げる学習方法に最適化されてしまった人間は、コンパイラーに対して、それらしくでっち上げられたソースコードを食わせてコンパイラーが騙されてくれることを期待する。しかしコンピューターは騙されない。そもそも騙しようがない。コンパイラーは定義済みの規則に則って判断するだけで騙すという概念すらないのだから。

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-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-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

2017-05-10

Rustのパッケージマネージャーでパッケージ名nulを作ったら全Windowsユーザーのパッケージマネージャーが壊れた話

How I Broke Rust's Package Manager for All Windows Users - sasheldon.com

非Windowsユーザーが何気なくRustでnulという名前のパッケージを作って公開した。すると、全Windowsユーザーのパッケージマネージャーが壊れた。

理由は、nulという名前はWindowsでは予約語だからだ。Win32サブシステム経由で、どのディレクトリであれ、nulというファイル名を使おうとすると、それはGNU/Linuxでいう/dev/nullと同じような扱いになる。nulに拡張子がついていても同じだ。

RustはWindowsサポートも重視しているので、これに対処してWindowsの予約語を禁止する変更がなされた。

Reserve windows crate names. by withoutboats · Pull Request #695 · rust-lang/crates.io

これはWindowsがクソだが、他のOSでもファイルシステムには様々な技術的な柵がある。例えばMac OSのファイルシステムはUnicode正規化が特殊でクソだし、POSIXの多くのコマンドは-をSTDINやSTDOUTとして特別扱いする。また、bashは/dev/tcp/host/portというファイル名でhost:portに対するTCP接続を行う。

2017-01-05

GoogleがGoによるPython実装、Grumpyを発表

Googleが既存の社内のPythonコードをGoで実行するためのPython実装を公開している。

Google Open Source Blog: Grumpy: Go running Python!

google/grumpy: Grumpy is a Python to Go source code transcompiler and runtime.

Googleの発表によれば、YouTubeのフロントエンドサーバーとYouTube APIはほとんどPythonで書かれているという。現在、YouTubeのフロントエンドはCPython 2.7で実行されているが、CPythonの制約により効率化には限界があるのだという。

GrumpyはPython 2.7のコードをGoのコードに変換するツールgrumpcの実装だ。grumpcはPythonで実装されていて、astモジュールでPythonをパースして、Goコードを吐く。Python 2.7系なのは、Google社内の既存のコードを実行するためだ。また、execやevalのようなインタープリター実装ならではの極めて動的な一部の機能は実装されていない。

Pythonの標準ライブラリのほとんどは、Pythonによって実装されているため、そのままGoコードに変換されてそのまま動く。

GrumpyにはGlobal Interpreter Lockが存在しない。リファレンスカウントのかわりにGoのGCにオブジェクトの生存管理を任せている。この設計のため、C extension moduleは使えない。この設計により、GrumpyはCPython実装よりスケールすると主張している。

Grumpyはインタープリターではない。Grumpyによって生成されたGoのコードは通常通りGoによってコンパイルされる。これにより開発やデプロイの柔軟性は下がるが、ネイティブコードへのコンパイルと静的解析により、より効率のよいコードを吐くことができるようになる。また、Grumpyで実行されるPythonコードは、Goのモジュールをimportして使うことができる。

興味深いツールだ。

2016-10-09

高専プロコンの問題がクソすぎるのでプログラミングを放り出して人力に走るのは最適解であり協賛企業はプログラミングを軽視する企業として唾棄されるべき

第27回高等専門学校プログラミングコンテストが不評を買っている。プログラミングコンテストと名前が付いているのにもかかわらず、本選の上位入賞者は、人力で問題を説いたという。特にコンピューターを持ち込んですらいないチームまでいたという噂まで流れている始末。

なぜそんな残念な結果になるのか、高専生のアルゴリズム力が低いからこうなったのだろうか。この謎を改名すべく、筆者は課題を確認した。

http://www.procon.gr.jp/uploads/procon27/1_Apply27.pdf

課題を要約すると、以下の通りだ。

問題

「一枚の木の板(中密度繊維板)を切り出して、50個以下のピース(凹多面体を含む多角形)に分割する。このピースを枠内で組み合わせて板にせよ。正しい位置のピースの数が得点となる」

制限時間は10分から20分。

その他:コンピューター類を持ち込んでよい。ただし競技ブースに電源はない。外部との通信は認めない。

まるでプログラミングするなと言っているような課題だ。要するに、問題は多角形のパズルを解くものであるが、それは問題の最も簡単な部分である。

ピースは物理的に与えられるので、プログラミングで処理するためには、これを何らかの方法でデータとして表現しなければならない。ピースが十分に薄ければスキャナーが使えるかもしれないが、会場に電源はない。したがってスキャナーのような大電力の装置を稼働させるには、大容量バッテリーか発電機を持ち込む必要がある。

なるべく電力を消費しない方法としては、無地単色の布などを背景に、距離を固定したカメラでピースを一つづつ撮影する必要がある。しかし、制限時間は最大でも20分、ピースは最大50個。撮影装置を一台用意した場合、何のトラブルも起こらずに撮影しても10分から20分の制限時間を超過してしまうだろう。

すると、ピースをすべて並べて一度に撮影して、複雑な画像処理をする必要があるが、カメラの角度がピースに対して正面ではない、レンズの歪み、ピースの加工精度など、様々な要因がピースをデータで表現して処理する際の面倒事となる。

外部との通信が禁じられているので、たとえば画像処理に外部のクラウドサーバーのインスタンスを立ち上げるといったこともできない。

それ以外でも、極めて短い制限時間はやはり問題だ。機器のわずかなトラブルにより、10分、20分程度の時間は容易に失われる。

さて、ここに人間という計算機がある。人間は高精度なカメラ、マイク、スピーカー、多関節脚、マニピュレーターを取り付けられた計算機である。人間は完全に自律移動できる。人間は極めて正確なピースの移動操作ができる。人間のパターン認識能力は極めて高く、完全な乱数列に対して存在しないパターンを見出してしまうほどである。この人間を訓練すれば、パズルを高速に解くことができる。人間はコンデンサの破裂、接触不良、宇宙線によるソフトメモリエラーを起こしたりしない。人間のバッテリー容量はとても高く、外部から燃料を一切供給せずとも長時間稼働できる。

したがって、この問題を解くのに人間を使うのは当然の最適解である。ちなみに、同点の場合、勝敗はサイコロを振って決定される。実際に優勝者はサイコロを振って決定されたそうなので、この戦略は適切であったことが実証されている。

明らかに、この問題と制約(電源なし、制限時間10分、外部通信禁止)はプログラミングコンテストにふさわしくない。この内容でプログラミングをさせたいのであれば、競技ではなく、課題公開から半年から1年ほど問題を解けるシステムを開発させたうえで皆で集まって成果報告会を開くべきである。競技には競技として適切な課題がある。この課題は競技に向かない。

高専プロコンの上位入賞者が人力解答者で占められたのは今年が初めてではない。高専プロコンの課題作成者は競技プログラミングを理解していないとしか言いようがない。この課題は、少し考えただけでも、純粋なプログラミング以外の部分が困難である。課題作成者は自分で課題を解いてみたのだろうか。

そして、この高専プロコンを協賛した企業は覚えておくべきだ。これらの企業は、プログラミングコンテストと銘打ちながら純粋なプログラミング力を競う競技のための課題を作成できず、至極自然で適切な戦略として人力解答者が上位を占めるという失態をしでかしたイベントの恥ずべき協賛者である。これらの協賛企業のプログラミングの認識と熱意と尊敬は、こんなイベントを協賛したレベルである。

全国高等専門学校プログラミングコンテスト - 協賛企業 - 第27回大会

協賛企業

プログラミングコンテストは情報関連企業のみなさまの多大なご協力により運営されています。

これらの企業はプログラミングコンテストの目的や高専教育に対して理解を示して下さっています。皆さんも就職対象として検討されてはいかがでしょうか。

上に引用した内容によれば、これらの協賛企業は、プログラミングコンテストに不向きで人間が最適解である見当違いの課題を設定するこのような謎のイベントの目的に理解を示しているようだ。イベントの実際の内容から考えるに、これらの協賛企業はプログラミングに理解は示しておらず、人間が頑張って単調作業をすることが最適解となることに理解を示しているのだろう。プログラマーの地位と尊厳を重要視する人間はこの事実を踏まえて、就職対象として検討するべきである。

なお、信じられないことに、高専プロコンのWebサイトはこの2016年にもかかわらずTABLEレイアウトを使っていた。繰り返す。TABLEレイアウトを使っていた。お後がよろしくなさすぎる。

2016-09-09

なぜターミナルにBを表示するのは#に比べて遅いのか

java - Why is printing "B" dramatically slower than printing "#"? - Stack Overflow

Stack Overflowに、ターミナルに、'B'を多数出力するコードは、'#'を多数出力するコードに比べて、桁違いに遅いが、なぜかという質問が上がっている。

不思議なことに、ideone.comで試すと速度に違いはないらしい。

その理由は、ターミナルがword-wrap(単語ごとの行折り返し)を行っているので、#を表示する際にはword-wrapは行う必要がないが、Bを出力した場合、後続の文字が単語を区切る文字かどうかを判定するための処理が入り遅くなるというものだった。

よくぞ答えを当てたものだ。

2016-07-17

作業が早いプログラマーと遅いプログラマーの差の比は4:1

An empirical study of working speed differences between software engineers for various kinds of task

プログラマーの作業速度には差がある。作業速度が早いことだけをもって優秀なプログラマーとは限らない。そのソフトウェアの保守性が悪いかもしれないからだ。しかし、やはり作業速度の早いプログラマーは優秀と見られがちだ。特に、転職界隈では、優秀なプログラマーは、その作業速度の速さを形容して、「ニンジャ」とか「10倍プログラマー」などというタイトルで喧伝されている。さて実際には、プログラマーの作業速度は、全体としてどの程度違うのか。

プログラマーの作業速度が早いものと遅いものの比は、従来、28:1であると言われてきた。この数字には根拠となる研究がある。1967年にGrantとSackmanが公開した論文[1]で、実験をした結果、28:1であると結論しているからだ。

[1]: "E. Eugene Grant and Harold Sackman. An exploratory investigation of programmer performance under on-line and off-line conditions. IEEE Trans. on Human Factors in Electronics, 8(1):33–48, March 1967."

問題は、その実験内容というのが、たった12人の経験豊富なプログラマーの被験者に2つの問題を解かせただけなのだ。

たったの12人の結果など、真の結果からかけ離れている可能性も大いにある。しかし、この論文はあまり批判されることがなく、28:1という数字のみが独り歩きしてしまい、今日の10倍プログラマーなどという都市伝説を生み出している。

この論文は、十分なサンプル数を集めてみたところ、28:1という比を否定した。

そもそも、プログラミングには様々な種類の作業がある。この論文では、プログラミングを以下の作業に分類した。

  • 保守(既存のコードの理解と変更と拡張)
  • 理解(例、特定の質問に応えるなど)
  • テスト/デバッグ(テストとデバッグ)
  • レビュー(誤りがないかの確認)
  • プログラミング(設計、実装、テスト、デバッグ)
  • 設計
  • コーディング(実装)

分類の判断に迷う場合は、プログラミングか保守に分類した。また、純粋なコーディング単体のみの作業はまれなので、分類上はプログラミングになっている。

結果としては、作業の種類によって、作業速度のばらつきには差が見られた。テスト/デバッグやプログラミングでは差が大きかったが、保守や理解では差が小さかった。レビュー作業の時間は差がとても小さかった。

結論として、プログラマーの作業速度の差は、4:1を超えることはめったにない。バラつきの大きい作業においても、大抵は2:1から3:1であった。

体感では、こういう短期間の実験では、乱数が相当に左右するのではないだろうかと思う。運悪くtypoをして何時間も悩むことがよくあるために。

2016-05-05

MITがSICPを教えなくなった理由

Programming by poking: why MIT stopped teaching SICP | posterior science

このNYC Lisp meetupの動画で、Gerry Sussmanに対する質問として、SussmanとAbelsonの古典、The Structure and Interpretation of Computer Programs(SICP)に基づく、伝説的な6.001講義をなぜMITはやめたのかと聞かれている。

Sussmanの回答としては、SussmanとHal Abelsonは1980年代から延々と教え続けるに嫌気が差し、1997年に、学部長の事務所に行って、「俺らはやめる。後どうするからは勝手に考えろ」と宣言した。より重要なこととしては、SICPのカリキュラムは、今日のエンジニアリングに求められるエンジニアを育てることができないからである。1980年代と1990年代には、エンジニアは複雑なシステムを組むのに、単純で十分に理解されている部品を組み合わせた。SICPの目的は、そのようなシステムを理解するための抽象的な言語を提供することだ。

今日では、状況が変わっている。今のエンジニアは、自分が完全に理解していない複雑なハードウェアのためのコードを日常的に書いている(そして、大抵の場合、企業秘密により完全に理解するのは不可能である)。ソフトウェアでも状況は同じだ。プログラミング環境は、多大な機能を提供する巨大なライブラリ群の集合として存在している。Sussmanの今日の生徒は、その時間の大半を、ライブラリのマニュアルを読み、どのように組み合わせれば目的が達成できるのかを把握することに費やしている。Sussman曰く、今日のプログラミングは、「より科学に近い。ライブラリを持ち寄って、つっつき回すのだ。プログラムを書くには、突っつき回して、どのように動作するかを観察する。そして、「目的を達成するために改造できるか」と考えるのだ」。SICPの「合成による解析」という物の見方である、小さな、単純な部品を組み合わせて大きなシステムを作るということは、もはや今日の状況にそぐわなくなった。今や、我々のプログラミングはつっつき回すことで行われている。

なぜPythonを選んだかということについて、Sussmanは、"late binding"に決定したと冗談を飛ばした。Pythonには大量のライブラリがあり、教育者の様々な実習に使いやすい(たとえば、ロボットを制御するソフトウェアを書くなど)

Sussmanは、SICPカリキュラムは現在のカリキュラムより洗練されていると考えているものの、正しいカリキュラムのあり方についてはまだ答えが出ていないという。

たしかに、今のプログラマーは、ハードウェアの仕様書を元にを直接操作するコードは書かないし、OSを実装していないし、コンパイラーも実装していないし、古典的なアルゴリズムやデータ構造さえ自分の手で書く必要がなくなっている。ライブラリが発達してその必要がなくなったためでもあり、また個々の機能があまりにも高度になりすぎて、到底一個の人間の手に負える作業量ではなくなったということもある。

不自由なハードウェア、ソフトウェアが蔓延してその詳細がわからなくなり、また自由なソフトウェアであっても、その内容が複雑になりすぎ、一つ一つ完全に理解するには時間が足りなすぎる。

何にせよ、平均的なプログラマーが実現できる機能は昔よりはるかに複雑になっていることは確かだ。

2016-05-02

コンピューター科学のアカデミック業界の残念な現状

mhoye on Twitter: "Extremely angry with the state of academic CS research right now. (1/n)"

MozillaでFirefoxのエンジニアリングコミュニティマネージャーであるMike Hoyeが、コンピューター科学におけるアカデミック研究の残念な現状に激怒している。

コンピューター科学のアカデミック研究の現状に激怒している。

MozillaがBugzillaを始めとした多数の情報を公開した結果として、多くの研究論文が書かれている。

我々はそのような研究には注目している。論文はじっくり読んでいるし、研究結果にしたがって今後の方向性も決めている。

しかし、我々は常に変化する世界に生きている。そのため、我々はデータをもとに結果を再検証して、仮定が正しいことを確認する。

ここで我々が行いたいことは、我々はある意思決定をある論文Xの結果をもとに行いたいのだが、その結果は最新のデータでも妥当であろうか? と言えることだ。

まともな世界では、そのような検証は以下の3ステップで行えるはずだ。

  • 論文著者のバージョン管理システムのレポジトリをクローン
  • 論文著者のプログラムを最新のデータに対して適用
  • 新しく生成されたグラフを見る

データはまだ仮説を支持するものであるか? 素晴らしい。この方向で進めよう。結果が変わった? 何故なのか考えてみよう。いずれにせよ。全員が満足する結果となる。

しかし、これは実現しない。なぜならば、コンピューター科学の研究者はコードもデータも公開しないからだ。奴らはLatexで整形したWordドキュメントをペイウォールに阻まれたPDFとして公開する。

奴らときたら、科学の原則である、「妥当性」とか「再現性」とか、中でも最も基本的な原則、「現実に即しているか」などは、クソ喰らえの姿勢だ。

人間が知識や学習結果を共有しないことの時代遅れがいかに時代遅れであるかを見てみようか。

ギリシア火薬の製法は失われた。ダマスカス鋼の製法は失われた。アンティキティラ島の機械は紀元前200年に失われ、同等の精度を持つ時計を再び作るには1500年代まで待たねばならなかった。

いいか。よく聞け。お前の未公開のコードと、お前の未検証のデータと、お前のペイウォールに阻まれた博士論文は、この輝かしい因習の一部であるのだぞ。

お前の目的とやらが、学士を得て卒業することなら、まあいいだろうよ。大抵の人間が望むことだ。だが、院にまで来てやることか?

お前の業績により世界をよりよい方向にインクリメントするためには、世界はお前の業績を読めなければならないのだぞ。

俺は結果の報告書など読みたくない。そんなのは、ワインを注文しているのに、赤っぽい色の液体について報じた新聞記事の切り抜きをFAXしてよこされるのと同じだ。

検証可能なデータと動くコードなしには、お前のコンピューター科学の博士論文の命題とやらは命題ではない。それは単に命題が存在するかもしれないという未検証の主張に過ぎない。

まとめると、俺は大変に失望している。もっと言うべきことはあるが、俺はこれから長年の研究とツールを再現するためのコードを書かねばならないのだ。

2016-04-20

curl | bashをサーバーサイドで判定する方法

Detecting the use of "curl | bash" server side | Application Security

ソフトウェアをインストールするとき、シェルスクリプトを実行するのはよくあることだ。しかし、そのシェルスクリプトが他人のリモートサーバーでホストされていた場合、curl | bashするのは危険だ。まともなユーザーは、curl | bashする前に、まず中身を確認して、悪意がないことを確かめるものだ。

しかしもし、サーバー側がwgetやcurlといったツールとブラウザーを判定して、それぞれ別のコードを返した場合どうか。ユーザーが見るのは囮のシェルスクリプトだ。

しかし、それではcurlやwgetを利用してシェルスクリプトをダウンロードするユーザーは騙せない。しかしもし、curlとcurl | bashを判定することができたらどうか。実は、できるのだ。

curlとcurl | bashを判定する方法は、bashの処理にある。bashはコードを順次実行していく。コードの実行中はパイプからの読み出しが滞る。ネットワークとパイプのバッファーが全て埋まってしまえば、サーバーからのデータのダウンロードは中断する。したがって、コードの冒頭にsleepを置いて、バッファーを埋めるために無害で表示されないnull文字を送りつける。ダウンロードが途中で中断すれば、curlはパイプを経由してbashに出力しているのだと判断できる。

curl | bashを判定するサーバーを判定する方法

では、ユーザーはどうやってcurl | bashを判定するサーバーを判定すればいいのだろうか。判定が上に述べたような簡単なディレイで行われているならば、そういうディレイを発生させてやればよい。

curl https://example.com/setup.bash | (sleep 3; cat)

しかし、curl | bashを判定する方法はその他にもあるし、ディレイを複数使って判定することもできるので、確実に判定はできない。信頼できないデータはまずローカルのファイルに落として、中身を検証してから、ローカルのファイルをbashで実行すべきだ。

2016-04-12

Brian Kernighanがプログラミング言語Goの組版に使ったのはなんとtroff

Ramakrishnan Muthukrishnan - Brian Kernighan on the typesetting of "The Go Programming Language" book

L&RのKでありAWKのKでもあるBrian KernighanとAlan Donovanの執筆したThe Go Programming Language(邦訳は丸善からプログラミング言語Goとして6月15日に出版される予定)の組版には、Troff(具体的にはgroff)が使われたそうだ。同本の組版に感心した人間が、Brian Kernighanに組版について以下のようなメールを送った。

親愛なるKernighan教授へ

プログラミング言語Goの本のとても組版が美しい。個人的な感想では、LaTexでクマれたものより美しいように思われる。

同本の執筆手順と本の組版について詳しい説明を願いたい。著作権の項目に使ったツールについては書かれているが。

謝意

Ramakrishnanより

その結果、Kernighanから以下のような返事が返ってきたという。

Ramakrishnanへ

組版について褒めていただきありがたい。組版の大半は単にtroff(実際にはgroff)と-msマクロパッケージで行われた。Latexも少し試したが、私もAlanもその出力をさらに編集する気になれなかったし、Latexを使って組版するのは不可能だと思っている。Troffは私のよく知る昔ながらのツールで、汚く例外的な挙動も多いが、文字を組みたい場所に置いてくれることは確かだ。

入力はXMLで、見出し、パラグラフ、索引、プログラムコード辺、簡単な表などを25個ぐらいのタグで表現している。Goのプログラムでこれを変換した。素早く画面上で見るためと、もし機会があればe-book版のためにHTMLにするのと、印刷のためにtroffにする。XMLを使うのは執筆時にすこし面倒だったが、エラーチェックが便利だった。

細かい修正のために多数のgoプログラムとスクリプトを書いた。例えばすべてのページが同じ高さになるようにtroffの出力を書き換えるとか。生成されたpostscriptにも印刷所の印をいれるために手を入れている。

フォントはAlanの選択だ。適切なフォントを見つけて適切なサイズと見た目にするのにかなり労力を使った。いくつかのアジア圏の文字はうまく扱うのが難しかった。troffは全角Unicode文字を適切に扱えないので、テキストを書きかえてごまかした部分がいくつかある。

図はぜんぶAlanの仕事だった。Googleのドローイングプログラムを使った。pic[画像?、ソフトウェアの名称?]を少し試してみたが、便利ではなかったし、HTMLで扱うためには面倒だった。上付き文字以上の組版が必要な数式は使わなかったし、表は簡素なものだった。eqnとtblぐらいあれば足りるが、HTMLでは扱っていない。

もう少しドキュメントを整備してツールも公開すべきなのだろうが、ほとんどの読者は君のように過程に興味はない。もうひとつの問題として、始めた当初は綺麗で筋の通った設計だったのに、結果として過程は炎上したし、やたら複雑なmakefileを書く必要に迫られた。

メールをありがとう

Brian

ちなみに、GNUのtroff互換実装であるgroffは、ここ10年ほどメンテナーがいなくて保守されていない。

ドワンゴ広告

アスキードワンゴ編集部はlatexを使っているそうだ。ちなみに、日本の殆どの出版社はInDesignで組版をしている。それも、編集者はInDesignを直接触らない。InDesignを触るのは印刷所の人間だ。ある編集者などは、「自分はコンピューターを触らない」と誇らしげに言うそうだ。そういう人は、紙に直接赤鉛筆などで組版の指示をして印刷所に投げる。

私からすると、GUIの組版ツールを使うのは同じ作業を何度も繰り返さなければならず極めて効率が悪いと思うのだが、印刷業界は不思議なものだ。

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

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

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

2015-12-16

Grub2の認証でバックスペースを28回押すとレスキューコンソールに入れる脆弱性が発見された

Back to 28: Grub2 Authentication Bypass 0-Day

Grub2のバージョン1.98(2009年12月)から、2.02(2015年12月)までにおいて、脆弱性が発見された。

脆弱性はGrub2の認証機能を使っていた場合に、ユーザー名を入力すべきところで、バックスペースを28回入力すると、レスキューコンソールに入れてしまうものだ。これにより、コンピューターに物理アクセスを得ている人間が、Grub2の強力なレスキューコンソール機能を使うことができる。

脆弱性の原因も詳しく書かれていて興味深い。grub2のコードでは、'\b'が入力されるたびに、unsigned型の変数をデクリメントする。この時、アンダーフローをチェックしていない。その変数は配列の添字に渡されて、ゼロが書き込まれる。

結果として、関数のreturn addressを0x0にすることができ、関数の終了時に戻って実行されるアドレス0x0になる。

通常のユーザースペースのプログラムやカーネルの場合、便利な保護機能が何重にもあるので、ここで終わりになるはずだが、grub2はブートローダーなので、そのような便利な保護機能はない。特殊な実行環境の結果、self-modifying codeを含むループに突入し、最終的に、grub_rescue_run()の先頭アドレスに飛ぶことで、レスキューコンソールに至る。

とても面白い。

2015-06-21

x86のmov命令はチューリング完全

世の中には様々なチューリング完全なシステムがある。

本の虫: うっかりチューリング完全になっちゃったもの

x86のMMUはチューリング完全である。

BGP(Border Gateway Protocol)はチューリング完全である。

http://vanbever.eu/pdfs/vanbever_turing_icnp_2013.pdf

さて、x86の命令セットは極めて複雑で冗長であることが知られている。なんと、mov命令はチューリング完全であるそうだ。

http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

もちろん、mov命令でメモリ上に任意のコードを書いて実行させればチューリング完全になるが、論文ではそのようなコード生成や自己書き換えによるイカサマは行っていない。また、アドレスモードもたいていのRISCにあるようなものしか使っていないという。

x86のmov命令だけを使った後、無条件jumpで先頭に戻るループを実行することで、チューリング完全になるそうだ。

レジスターに入っている2つのアドレスA, Bが正しいかどうかは、アドレスAにある値をストアして、その後にアドレスBに別の値をストアして、そしてアドレスAの値をみると、AとBが等しいかどうかがわかる。レジスターRiの値にアドレスA入っていて、レジスターRjの値にアドレスBが入っている場合、レジスターRiとレジスターRjが等しいかどうかは、以下のようにしてわかる。

mov [Ri], 0
mov [Rj], 1
mov Rk , [Ri]

このコードはアドレスの指し示すメモリ内容を破壊するが、このアドレスはシンボル用に確保しているものなので問題はない。

比較の結果を0か1で得ることによって、Rkを使って2要素が入ったテーブルを参照することによって、2つのアドレスから選択をすることができる。レジスターNにアドレスNが入っていて、レジスターRi, Rjに選択される2つのアドレスが入っていて、Rkに比較の結果が0か1で入っている場合、以下のようにしてRi, Rjのどちらかのアドレスを選択してRlに入れることができる。

mov [N], Ri
mov [N+1], Rj
mov Rl , [N + Rk ]

この論文を元にした、MOV命令のみを使うコードを生成するコンパイラー、xoreaxeaxeax/movfuscatorがGitHubで公開されている。これはBrainfuckコンパイラーだが、BFBASICを併用することで、BASICからBrainfuckに変換できるので、BASICからmov命令(と末尾の銭湯に戻る無条件jump)のみのコードを生成するとしている。

なお、将来的にはCコンパイラーを実装するとしている。