突破してみる? / Why don't you get over?

ソフトウェアエンジニアの備忘録 / Memorandum for software engineers

スクリプト言語Butai

スクリプト言語Butai

スクリプト言語を作っている。その名はButai。
インターネットという巨大な文化祭の「舞台」を作りたい。
世界には日本発のオブジェクト指向言語Rubyがある。
Butaiも思い切り影響を受けた。Butaiもやはりオブジェクト指向言語である。
しかも、現実的なRubyと違い「純粋な」オブジェクト指向言語である。
整数すらもオブジェクトに包まれている。
「純粋」とか「一貫性」といったキーワードは、Butaiの設計哲学である。
まだ公開には至っていないし、ローカルでチマチマとやっているのだが、
Butaiでは、いくつかのブレイクスルーがあると思っている。

ケアフルリスト

これは「注意深い」リンクトリストである。
ポインタの使用方法を勘違いするといった、
リストでありがちなで厄介なバグをその場で指摘してくれる。
特に先頭と末尾を待ち構えている番兵エントリを超えないようにチェックする。
それから、リストとエントリの所属を管理するマネージャも新開発だ。
中間管理のマネージャは一見筋が悪そうに見えたのだが意外と問題ない。
リストのO(1)操作をそれほど邪魔しない。
リストとエントリの対応がつくので、
間違ったリストに間違ったリストやエントリをつなぎ合わせるようなバグを指摘できる。

O(n) ガーベージコレクタ

マーク&スイープのガーベージコレクタである。
インスタンスはリストで管理される。
インスタンスは初期リストに登録されている。
インスタンスをマークすると、マーク済みリストにO(1)で移動させる。
インスタンス再帰的にマークし終わると、初期リストの残りをスイープする。
インスタンス数をnとし、マーク数をmとし、スイープ数をlとすると、
O(m + l) = O(n)である。
シンプルなマーク&スイープではO(m + n)であるから、計算量として高速になる。

そう、この教条的な哲学の言語では、計算量で議論をしたい。
逆に言うと、同じ計算量なら、多少のオーバーヘッドがあってもいいとすることもできる。

乞うご期待

手元のバージョンはbutai-0.37.1。まだまだひよこである。

world setを使おう

worldとは?

今回は、Gentoo Linuxのお話です。

worldとはemergeコマンドでインストールされたパッケージを管理する仕組みです。emergeコマンドで直接指定されたパッケージはworldファイル(/var/lib/portage/world)に登録されます。例えばこんな感じです。

# emerge app-misc/hello
  :  snip
# grep hello /var/lib/portage/world
app-misc/hello
#

worldには、依存関係でインストールされたパッケージや、--oneshotオプションを付けてインストールされたものは登録されません。

worldは、--depcleanオプションで削除するパッケージに影響します。worldに登録されたパッケージとそれに依存するものは削除されませんが、それ以外のパッケージは削除されます。

worldの仕組みに則ると、パッケージを簡潔に管理することができるでしょう。

world setを書こう

worldファイルはemergeコマンドが管理するので手で書き換えるようなことは避けたほうがいいかもしれません。幸い、emergeコマンドはworld setという仕組みを持っています。/etc/portage/sets以下に複数のworld setを持つことができます。管理者が手で書き換えてもいいworldファイルを設定ファイルとして複数持つことができるということです。私は、worldファイルのすべてのパッケージをworld setに移してworldファイルは空で運用しています。

world setの記法

atom記法が使えますのでバージョンを固定したり、除外したりすることができます。

world setの使い方のコツ

  • world setの全パッケージのインストール・再インストール
# echo 'app-misc/hello' > /etc/portage/sets/new_set
# emerge --ask @new_set

These are the packages that would be merged, in order:

Calculating dependencies... done!
[ebuild  N     ] app-misc/hello-2.9  USE="nls"

Would you like to merge these packages? [Yes/No]
#
  • world setの全パッケージを削除
# emerge --unmerge @my_set
#
  • 既存のworld setにパッケージを追加したとき
# echo 'app-misc/hello' >> /etc/portage/sets/added_set
# emerge --update --ask @added_set

These are the packages that would be merged, in order:

Calculating dependencies... done!
[ebuild  N     ] app-misc/hello-2.9  USE="nls"

Would you like to merge these packages? [Yes/No]
#

Synchronize with fibers

toppa.hatenablog.com

Instalation of walk and fibers

This time, Let's play with node.js and CoffeeScript.

Install walk and fibers.

$ mkdir walk_fibers
$ cd walk_fibres
$ npm install walk fibers
$

Asynchronus Directory traverse with walk


walk is a library that proceseses files traversing directory tree recursively. It is also asynchronous so you can gain speed.

  • walk.coffee
# node.js modules
Path  = require('path')

# npm modules
Walk  = require('walk')

class Traverse
  constructor: -> @traverse_async('.')

  traverse_async: (root_dir) =>
    list = []

    # *1_1: Start directory traverse.
    walk = Walk.walk(root_dir)

    # *1_2: Callback on file stat-ed.
    walk.on 'file', (root, stat, next) =>
      filename = Path.join(root, stat.name)
      list.push(filename)
      next()

    # *1_3: Callback on walk ended.
    walk.on 'end', =>
      list.sort()

      # *1_4: Do something with list *asyncronously* in the walk callback.
      console.log(list)

new Traverse

How to work on walk

First, the directory traversing starts with *1_1 .
And register a callback that will be called when the file is stated in *1_2 .
Each time stat is called *1_2 , it adds file path to the array.
It is the *1_3 callback that is called when the directory traversing ends.
After it completes the directory traversing, it sorts the array.
And it get list in *1_4 and put it out in callback function.

Here is the execution:

$ coffee walk.coffee
[ 'node_modules/fibers/.npmignore',
  'node_modules/fibers/LICENSE',
  'node_modules/fibers/README.md',
  'node_modules/fibers/bin/.npmignore',
  'node_modules/fibers/bin/darwin-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/darwin-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.6/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.14/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.6/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.14/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.6/fibers.node',
  ...
  'walk.coffee',
  'walk_fibers.coffee' ]
$

Synchronization with fibers

Next, Try also fibers. You can wait for asynchronus directory traversing with it.

  • walk_fibers.coffee
# node.js modules
Path  = require('path')

# npm modules
Walk  = require('walk')
Fiber = require('fibers')

class Traverse
  constructor: ->
    # *2_1: Register @main_procedure as the main thread and run the main thread.
    Fiber(@main_procedure).run()

  main_procedure: () =>
    list = @traverse('.')

    # *2_6: Do something with list *syncronously* in the main procedure.
    console.log(list)

  traverse: (root_dir) =>
    list = []

    # *2_2: Get the main thread for later at *2_4.
    main_thread = Fiber.current

    # Start directory traverse.
    walk = Walk.walk(root_dir)

    # Callback on file stat-ed.
    walk.on 'file', (root, stat, next) =>
      filename = Path.join(root, stat.name)
      list.push(filename)
      next()

    # Callback on walk ended.
    walk.on 'end', =>
      list.sort()

      # *2_4: Resume back the the main thread at *2_5.
      main_thread.run(list)

    # *2_3: Yield the main thread to async walk procedure
    list = Fiber.yield()
    # *2_5: Will be resumed here.
    return list

new Traverse

How to work on fibers

First, register and run main_procedure () as the main thread at *2_1 .
Get the main thread object with *2_2 . It is a preparation to use this object in *2_4 .
Process walks asynchronously with travase().
Control is returned to the main thread during asynchronous processing. Processing of the main thread yields by executing Fiber.yield() with *2_3 . Wait that asynchronous processing ends.
When asynchronous processing is finished, return to the main thread from the walk 'end' function in *2_4 .

After the main thread is synchronized and moves to *2_5 and exits traverse(). It returns to main_procedure() at *2_6 . You will be able to use list to do further processing.

$ coffee walk_fibers.coffee
[ 'node_modules/fibers/.npmignore',
  'node_modules/fibers/LICENSE',
  'node_modules/fibers/README.md',
  'node_modules/fibers/bin/.npmignore',
  'node_modules/fibers/bin/darwin-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/darwin-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.6/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.14/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.6/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.14/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.6/fibers.node',
  ...
  'walk.coffee',
  'walk_fibers.coffee' ]
$

Advantages of fibers

In the latter code, you can further process within the same hierarchy from *2_6 after performing traverse() in main_procedure().
The point is not within the walk 'end' callback, but main procedure continues after asynchronus processing of walk.

fibersを使って同期しよう

toppa.hatenablog.com

walkとfibersのインストール

今回はnode.jsとCoffeeScriptで遊んでみましょう。

walkとfibersをインストールします。

$ mkdir walk_fibers
$ cd walk_fibres
$ npm install walk fibers
$

walkによる非同期ディレクトリ走査

walkは、非同期にディレクトリを再帰走査してファイルを処理するライブラリです。非同期なので速度を稼ぐことができるでしょう。

  • walk.coffee
# node.js modules
Path  = require('path')

# npm modules
Walk  = require('walk')

class Traverse
  constructor: -> @traverse_async('.')

  traverse_async: (root_dir) =>
    list = []

    # *1_1: Start directory traverse.
    walk = Walk.walk(root_dir)

    # *1_2: Callback on file stat-ed.
    walk.on 'file', (root, stat, next) =>
      filename = Path.join(root, stat.name)
      list.push(filename)
      next()

    # *1_3: Callback on walk ended.
    walk.on 'end', =>
      list.sort()

      # *1_4: Do something with list *asyncronously* in the walk callback.
      console.log(list)

new Traverse

walkの動作

まず*1_1ディレクトリの走査が始まります。
そして*1_2でファイルがstatされると呼び出されるコールバックを登録します。
statされるたびに*1_2が呼び出され、配列にファイルパスを追加していきます。
ディレクトリの走査が終了するときに呼び出されるのが*1_3のコールバックです。
ディレクトリの走査が終了したら配列をソートします。
そして*1_4でlistを得てコールバック内で出力します。

実行はこうなります。

$ coffee walk.coffee
[ 'node_modules/fibers/.npmignore',
  'node_modules/fibers/LICENSE',
  'node_modules/fibers/README.md',
  'node_modules/fibers/bin/.npmignore',
  'node_modules/fibers/bin/darwin-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/darwin-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.6/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.14/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.6/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.14/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.6/fibers.node',
  ...
  'walk.coffee',
  'walk_fibers.coffee' ]
$

fibersによる同期化

今度はfibersも使います。ディレクトリ走査の非同期処理を待ち受けることができます。

  • walk_fibers.coffee
# node.js modules
Path  = require('path')

# npm modules
Walk  = require('walk')
Fiber = require('fibers')

class Traverse
  constructor: ->
    # *2_1: Register @main_procedure as the main thread and run the main thread.
    Fiber(@main_procedure).run()

  main_procedure: () =>
    list = @traverse('.')

    # *2_6: Do something with list *syncronously* in the main procedure.
    console.log(list)

  traverse: (root_dir) =>
    list = []

    # *2_2: Get the main thread for later at *2_4.
    main_thread = Fiber.current

    # Start directory traverse.
    walk = Walk.walk(root_dir)

    # Callback on file stat-ed.
    walk.on 'file', (root, stat, next) =>
      filename = Path.join(root, stat.name)
      list.push(filename)
      next()

    # Callback on walk ended.
    walk.on 'end', =>
      list.sort()

      # *2_4: Resume back the the main thread at *2_5.
      main_thread.run(list)

    # *2_3: Yield the main thread to async walk procedure
    list = Fiber.yield()
    # *2_5: Will be resumed here.
    return list

new Traverse

fibersの動作

まず*2_1のところでmain_procedure()をメインスレッドとして登録して走らせます。
*2_2でメインスレッドのオブジェクトを取得します。*2_4でこのオブジェクトを利用するための下準備です。
travase()で非同期的にwalkを処理します。
非同期処理の間にメインスレッドに制御が戻りますが、*2_3でFiber.yield()することでメインスレッドの処理を明け渡し、非同期処理が終了するのを待ちます。
非同期処理が終わると*2_4でwalk終了関数からメインスレッドを復帰させます。

メインスレッドが同期され*2_5に移りtraverse()を抜けると、*2_6でmain_procedure()に戻り、listを使ってその後の処理を行うことができるようになります。

実行はこうなります。

$ coffee walk_fibers.coffee
[ 'node_modules/fibers/.npmignore',
  'node_modules/fibers/LICENSE',
  'node_modules/fibers/README.md',
  'node_modules/fibers/bin/.npmignore',
  'node_modules/fibers/bin/darwin-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/darwin-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/darwin-x64-v8-3.6/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.14/fibers.node',
  'node_modules/fibers/bin/linux-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/linux-x64-v8-3.6/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.11/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.14/fibers.node',
  'node_modules/fibers/bin/win32-ia32-v8-3.6/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.11/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.14/fibers.node',
  'node_modules/fibers/bin/win32-x64-v8-3.6/fibers.node',
  ...
  'walk.coffee',
  'walk_fibers.coffee' ]
$

fibersの利点

main_procedure()でtraverse()を実行した後に*2_6以降の同じ階層内で更に処理を続けられるコードになっています。
walkの非同期処理の後の手続きをwalk終了コールバック内じゃなくて、メイン処理で行えるところが味噌です。

CoffeeScriptでオブジェクト指向

JQueryをつかってHTML5のオーディオAPIで遊んでみよう

<!DOCTYPE html>
<html>
  <head>
    <script src='./jquery-2.1.1.min.js'></script>
    <script src='./player_jquery.js'></script>
  </head>
  <body>
    <audio controls id='player'>
      <source src='./test.mp3'></source>
    </audio>
    <div id='controller'>
      <input id='speed_slider' max='3' min='0.1' step='0.1' type='range' value='1'>
      <input id='speed_ratio' max='3' min='0.1' step='0.1' type='number' value='1'>
    </div>
  </body>
</html>
change_playback_rate = (speed) ->
  $('audio#player')[0].playbackRate = speed # HTML5 Audio API

$(document).ready ->
  $('input#speed_slider').on 'input', (event) ->
    speed = event.target.value
    $('input#speed_ratio').val(speed)
    change_playback_rate(speed)

  $('input#speed_ratio').on 'input', (event) ->
    speed = event.target.value
    $('input#speed_slider').val(speed)
    change_playback_rate(speed)

CoffeeScriptコンパイルはこうなります。

$ coffee -c player_jquery.coffee
$

test.mp3は、適宜用意してください。
player_jquery.htmlをブラウザで見ると、HTML5オーディオプレイヤとスライダと数値ボックスが表示されます。スライダか数値の変更により、オーディオの再生速度が変わります。

$(document).ready()節にイベント処理を実装して全体でコードを短くしてみました。

Read more

Bashで整数の加減乗除はどうやるの? -- Bashの算術展開と算術評価

  • Bashの算術展開
    • 加減乗除
    • インクリメント、デクリメント
  • Bashの算術評価
    • ループ
    • 分岐

Bashの算術展開

Bashでも整数の算術計算ができます。詳しくはman 1 bashのArithmetic ExpansionとArithmetic Evaluationのところを読むといいのですが、少し例を挙げてみたいと思います。

加減乗除

加減乗除と剰余とべき乗の計算ができます。

$ var=10
$ echo $((var + 3))
13
$ echo $((var - 3))
7
$ echo $((var * 3))
30
$ echo $((var / 3))
3
$ echo $((var % 3))
1
$ echo $((var ** 3))
1000
$
Read more

Bashで文字列の置換はどうするの? -- Bashのパラメータ展開

  • Bashのパラメータ展開
    • ${parameter/wildcard/string}, ${parameter//wildcard/string}
    • ${parameter/#wildcard/string}, ${parameter/%wildcard/string}
    • ${parameter#wildcard}, ${parameter##wildcard}
    • ${parameter%wildcard}, ${parameter%%wildcard}
    • まとめ

Bashのパラメータ展開

Bashでワイルドカードを使って文字列を置換したいときありますよね。Gentooだとebuildがシェルスクリプトなので、特に需要があると思います。難読な記法ですが、慣れると結構重宝します。

詳しくはman 1 bashのParameter Expansionを読むといいのですが、例を書いておきます。

${parameter/wildcard/string}, ${parameter//wildcard/string}

/だとwildcardに一致する最初の部分文字列をstringに置換します。
//だとwildcardに一致するすべての部分文字列をstringに置換します。

$ str_to_substitute='/usr/src/linux-3.16.6-gentoo'
$ echo "${str_to_substitute/-/_}"
/usr/src/linux_3.16.6-gentoo
$ echo "${str_to_substitute//-/_}"
/usr/src/linux_3.16.6_gentoo
$

ハイフンをアンダースコアに置換してみました。
Gentooのebuildでは、変数Pがパッケージネームとバージョンをハイフンでつないだ値を持っていますが、
それをアンダースコアに置換するときによく使います。

Read more