Journal InTime

_ Feature #6242: Ruby should support lists

RubyはLISPなのでリストをサポートするべきだというチケットを登録。

• <URL:https://bugs.ruby-lang.org/issues/6242>

チケットに添付したパッチでは、Listというクラスを導入して、NilClassとConsをListのサブクラスにしている。

最初、%S(1 2 3)のような形でS式をサポートしようかと思ったけど、このネタ自体を思い付いたのが今日であまり時間もなかったので、 S[1, 2, 3]のような形でお茶を濁してしまった。

ちゃんとしたS式の代りにcons演算子を追加してみた。 Haskellではconsは:、MLやScalaでは::のようだが、Rubyだとどちらも使えないので苦肉の策で:::を使うことにした。 ポイントは右結合であるということで、

1 ::: 2 ::: 3 ::: nil

は、

1 ::: (2 ::: (3 ::: nil))

という意味になる。

もう一つのポイントは、右側のオペランドがレシーバに、左側のオペランドが引数になるということ（たしかScalaがそうしていたと思う）。 つまり、上の式は、

(nil.:::(3)).:::(2).:::(1)

という意味になる。 左側をレシーバにすると、Objectに:::メソッドを追加しないといけなくなるし、ユーザ定義のリストクラスを作った時に:::を使えない。

後でfoldl/foldrを追加して、foldl/foldrを使って+, flatten/concat, map, flat_map/concat_map, filter, length/size, sum, reverseなどのメソッドを定義してみたが、Ruby（というかCだけど）で関数プログラミングができてなかなか楽しかった。

_ git-credential-gnomekeyring

gitをhttpで使う時に気になるのがパスワードの管理で、以前はcurlの設定ファイルである.netrcに生パスワードを書くか、環境変数GIT_ASKPASSでコマンドを指定して何とかするしかなかった。 git 1.7.9でcredential helperという仕組みが導入されていて、比較的簡単にパスワード管理方法を拡張できるようなので、Gnome Keyringに保存するcredential helperを書いてみた。

• git-credential-gnomekeyring

すでに誰かが書いてそうな気もするけど、まあいいや。

追記:

やっぱりあったorz

• git-credential-keyring

しかし、keyringという名前は一般的すぎる気が。

さらに追記:

↑のは古いAPIのようで、↓のforkだとgit 1.7.9のAPIに対応しているみたい。だけど試してないので動くかどうかは知らない。

• <URL:https://github.com/pah/git-credential-keyring>

_ 千手院の枝垂れ桜

ちょっと仕事をさぼってバイクで千住院の枝垂れ桜を見に行ってきた。会社からは5分ほど。 桜を眺めながら抹茶をいただいてきた。

寺までの坂道にはソメイヨシノも植えられていて、桜ごしに松江城を望むことができた。

_ Rubyで遅延評価 - delay, force, lazy

正格評価の言語で明示的に遅延評価を行う方法として、Schemeのdelay/forceがある。 Rubyで実装するとこんな感じ。

class Promise
  NULL = Object.new

  def initialize(&block)
    @value = NULL
    @block = block
  end

  def self.delay(&block)
    new(&block)
  end

  def force
    if @value == NULL
      @value = @block.call
    else
      @value
    end
  end
end

count = 0
x = Promise.delay { count += 1; 1 + 2 }
p x.force #=> 3
p x.force #=> 3
p count #=> 1

メモ化してくれるので、delayされた式は何回forceしても一度しか実行されないのがポイント。

しかし、この実装には問題があって、末尾呼び出しの最適化を有効にしても以下のコードがstack overflowになってしまう。

def loop
  Promise.delay { loop.force }
end
loop.force

この例だとエラーになっても害がないと思われるかもしれないが、遅延評価の言語で末尾再帰になるような関数をdelay/forceで書こうとすると、上記のようにPromise.delay { (...).force }という形が出て来るのでちと困る。

そこで、SchemeのSRFI-45でlazyという機能が導入されており、(delay (force ...))の代りに(lazy ...)とすることで解決できる。

Rubyでの実装は以下。

class Promise
  Box = Struct.new(:type, :value)

  def initialize(type, value)
    @box = Box.new(type, value)
  end

  private_class_method :new

  def self.lazy(&block)
    new(:lazy, block)
  end

  def self.eager(value)
    new(:eager, value)
  end

  def self.delay
    lazy {
      eager(yield)
    }
  end

  def force
    content = box
    case content.type
    when :eager
      content.value
    when :lazy
      promise = content.value.call
      content = box
      if content.type != :eager
        content.type = promise.box.type
        content.value = promise.box.value
        promise.box = content
      end
      force
    else
      raise ScriptError, "should not reach here"
    end
  end

  protected

  attr_accessor :box
end

$c = 0
def loop
  $c += 1
  Promise.lazy { loop }
end
at_exit { p $c }
loop.force

末尾呼び出しの最適化を有効にして実行すると、ちゃんと無限ループになる。 Ctrl+Cで止めると以下のように実行回数が表示される。

$  ruby-trunk -e 'RubyVM::InstructionSequence.compile_option = \
  {:tailcall_optimization => true, :trace_instruction => false}' \
  -e 'load(ARGV[0])' t.rb
^C133411
t.rb:34:in `force': Interrupt
	from -e:3:in `load'
	from -e:3:in `<main>'

_ こいのぼり

妻と長男がバレーの練習試合で出かけている間に娘二人を連れて近所の川にこいのぼりを見に行ってきた。 毎年たくさんのこいのぼりが上げられているのだが写真はその一部(半分くらい?)。 たくさんの子ども連れで賑わっていた。

我が家にはこいのぼりがないので毎年ここで済ませている。

_ Majestouch NINJA Tenkeyless 茶軸・テンキーレス・US ASCII

最近肩こりがひどく、ZENBOOKのキーボードで一日中入力するのはかなりしんどいので、FILCOのFKBN87M／EFB2というキーボードを買った。

色々考えたが、結局オーソドックスなテンキーレスのメカニカルキーボードでUS配列のものを選んだ。

タイプ感はかなりよく、軽いタッチで小気味よく入力ができる。刻印がキートップの上部ではなく前面にあるので剥がれてこないのが気が効いているし、見た目もすっきりしている。 ダイヤテックオンラインで購入したら赤・黒・白のキートップが付いてきたのでEscを赤に変えてみた。キートップを外す器具まで付属しているので、交換作業もスムーズである。

と、いいことづくめのようだが、一つ難点があって、やはりタイプ音が大きいということである。あまりタイプ音がしないように軽く打っているつもりなのだが、いつの間にか原君がイヤホンをしていたくらい。 もう少しで発売される赤軸のモデルにしておいたらもうちょっと静かだったかもしれない。 まわりの人はみんなパンタグラフとかなので罪悪感を感じるし、 そのうちこんなことを言われないかひやひやしている。

他のみんなもメカニカルキーボードにしないかなあ。

_ iiyama 23インチワイド液晶ディスプレイ PLXB2374HDS-B1

iiyama 23インチワイド液晶ディスプレイ IPSパネル LEDバックライト 昇降・ピボット機能搭載 HDMIケーブル同梱モデル マーベルブラック PLXB2374HDS-B1

キーボードとあわせてディスプレイを購入した。 24インチのVAパネルのモデルと迷ったが、IPSの方が目が疲れなさそうな気がしてこちらにした。 正直ディスプレイの違いはよくわからないのだが、IPSの23インチディスプレイがこの値段で買えるのは素晴らしい。

このモデルはスタンドの高さを調節できるので肩こりにも良さそうだ。 スタンドの作りも割としっかりしている。

モニタを回転できる機能もあるけど、さすがにちょっと縦長すぎるので滅多に使う機会はなさそう。

_ Brouwerの不動点定理と直観主義論理

Conceptual Mathematicsと並行して記号論理入門を読んでいるのだが、たまたまConceptual Mathematicsの方でBrouwerの不動点定理を取り上げた章を読んでいる時に、記号論理入門の方でBrouwerの名前が出て来て面白かった。

記号論理入門によると、Brouwerは「数学において排中律を無制限に用いるのは正当でない」と主張したそうで、古典論理から排中律を除いた論理体系を直観主義論理と呼ぶそうなのだが、Conceptual MathematicsのSession 10の§4の演習では背理法を使う必要があって、このケースでは排中律(を前提とする背理法)を使ってよいのかなと疑問に思った。

ところが、改めて前の§を読み返すと、p.125に以下のような記述があった。

We need to use another principle of logic, that not (not A) implies A, to reach `every f has a fixed point.' Brouwer himself seriously questioned this rule of logic; and we will later see that there are examples of useful categories in whose `internal' logic this rule does not hold.

[Conceptual Mathematicsより引用]

日本語に翻訳すると、以下のような意味だと思う。

「すべてのfは不動点をもつ」を導くためには、論理のもう一つの原理である「not (not A) ならば A」を使う必要があります。Brouwer自身はこの論理規則に対して深刻な疑問を呈していました。後に見るように、いくつかの有用な圏の例においては、その「内部の」論理ではこの規則が成り立ちません。

読み流していたけど、Brouwerの直観主義を踏まえて敢えてこういう構成になっているんだな、とちょっと感動した。 ちなみに「not (not A) ならば A」（¬¬A→A）は、排中律「A or not A」（A∨¬A）と同値である（記号論理入門 p.57）。

追記: 後で読み返したらここはBrouwerの証明をなぞっているだけで、別にこの本独自の構成というわけではないようだ。独自なのは、§5で二つの公理を導入することで、位相空間と連続写像の詳細を説明せずに、Brouwerの定理を一般化した定理［topological spaceだけでなくsmooth space（ってなんじゃらほい）などにおいても成り立つ］を導いているところのようだが、消化しきれていないので後でもう一度読む。

_ real-time deque

Purely Functional Data Structuresのreal-time dequeをRubyで実装してみた。 dequeは両端から要素を追加したり削除できるキューで、real-time dequeは両端への追加・削除が最悪でもO(1)というもので、以下のような使い方ができる。

>> deque = Immutable::Deque.empty.push(1).push(2).push(3)
=> #<Immutable::Deque:0x20f21b18 @front=Stream[?, ...], @front_len=1, @front_schedule=Stream[...], @rear=Stream[?, ...], @rear_len=2, @rear_schedule=Stream[...], @c=3>
>> deque.to_a
=> [1, 2, 3]
>> deque.first
=> 1
>> deque.shift.to_a
=> [2, 3]
>> deque.last
=> 3
>> deque.pop.to_a
=> [1, 2]

短命データなら例えば双方向リストを使って簡単に実装できると思うが、永続データだと後でリンクを付け変えることができないので結構複雑になる。このreal-time dequeでは、2本のリストを使って前半と後半に要素を分けて管理し、一回の操作がO(1)に収まるように一方のリストから他方に逐次的に要素を移している。

当初、queueの実装をFigure 5.3どおりに以下のように実装していたが、@c == 2*1の時に(1..5).inject(Immutable::Deque.empty, :&cons).to_aのようなコードでエラーになってしまった。

def queue(f, f_len, f_schedule, r, r_len, r_schedule)
  # ...
  elsif r_len > @c * f_len + 1
    i = (f_len + r_len) / 2
    j = (f_len + r_len) - i
    f2 = rotate_drop(f, j, r)
    r2 = r.take(j)
    self.class.new(f2, i, f2, r2, j, r2)
  else
    self.class.new(f, f_len, f_schedule, r, r_len, r_schedule)
  end
end

どうも

i = (f_len + r_len) / 2
j = (f_len + r_len) - i

の部分を

j = (f_len + r_len) / 2
i = (f_len + r_len) - j

のようにiとjを入れ替えないと上手く行かないようだ。 この部分はリア側の要素をフロント側に移す処理をしていて、elsifの前にはフロント側の要素をリア側に移すコードがあるのだが、それと対称的なコードにするには上記のようにiとjを入れ替えないといけない気がする。

また、Figure 5.3のコードはrotateDropの引数の順番も間違っているような気がするのだが、MLのコードなのでよくわからない。