読者です 読者をやめる 読者になる 読者になる

Light Table プラグインチュートリアル

LightTable ClojureScript Clojure

はじめに

Light Table Plugin Tutorialの翻訳になります。
LightTable のプラグインに関する日本語情報が不足しているため、翻訳してみました。
間違い等ありましたら、ご指摘いただけると助かります。

Original article: Light Table Plugin Tutorial by Jakub Arnold

ちなみにオリジナルの記事はLightTableのwikiにもリンクが貼ってあります。

元記事の著者の許可は取得済み↓

翻訳

ソースコードがオープンになってからLight Tableで遊んでいます。(Rubyのプラグインも作りました)

Light Table は 3つのコンセプトを持つ BOT アーキテクチャに基づいて作られています。振る舞い(Behaviors)、オブジェクト(Objects)、そしてタグ(Tags)の3つです。もしあなたがNode.jsや他のイベント駆動プログラミングを経験していれば、そのコンセプトを理解するのは簡単です。

クリックイベントを受け取るボタンを持ち、それがクリックされた際、ユーザにそれを通知することを想像してみてください。

jQuery を使えば、以下のようにシンプルに実装できます。

<input class="my-button" type="submit" value="Do work"/>
$(".my-button").click(function() {
  showProgress("I'm doing some heavy lifting");
});

しかしこのやり方にはちょっと問題があります、とりわけLightTableの視点から。まず、第一に要素に割り当てられた後、コールバックを参照する方法がありません。これは実行時、簡単に変更できないことを意味します。BOTでは、オブジェクト(the button)をトリガー(click)による実際の振る舞いから分離することができます。

ClojureScript による実装を見てみましょう。もしあなたがチュートリアルに沿って進むなら、まずはファイルを作ります。例えば /tmp/tutorial.cljs に。そしてCtrl-Spaceを押し、Add Connectionと入力、そしてLight Table UIを選択します。これは稼働している Light Table インスタンスの中で直接 ClojureScript を評価することを可能にします。その前に、以下の requires をファイルの先頭に追加しましょう。

(ns lt.tutorial
  (:require [lt.object :as object]
            [lt.objs.tabs :as tabs]
            [lt.objs.statusbar :as statusbar]
            [lt.objs.notifos :as notifos]
            [lt.util.js :as util])
  (:require-macros [lt.macros :refer [behavior defui]]))

今後は、カーソル位置にある現在のフォームを Cmd-Enter により評価することができます。

次にdefuiマクロを使ってボタンを定義しましょう。

(defui work-button [this]
  [:input {:type "submit" :value "Do work"}]
  :click #(object/raise this :clicked %))

このコード断片は明白ですね。<input type="submit" value="Do work"/>をクリックイベントのハンドラと共に生成します。#(object/raise this :click %) はただ単に(fn [e] (object/raise this :click e))の簡易表現です。ここでobject/raiseはターゲットとなるオブジェクトに対してクリックイベントを発生させます。名前から想像するかもしれませんが、例外を発生させるわけではありません。

次にワーカーオブジェクトを定義しましょう。

(object/object* ::worker
                :name "A hard worker"
                :behaviors [::work-on-click]
                :init (fn [this] (work-button this)))

これはクリックした際にハードな処理を行うワーカーです。ここで着目する点はinit関数で返される値です。init関数で返された値はオブジェクトがタブに置かれる際に使用されます。今回のケースでは、作成したオブジェクトを持ったボタンが返されています。

残りは振る舞いの設定です。Light Table の素晴らしいライブラリnotifosを利用し、進捗を表す動く四角形を表示します。

(behavior ::work-on-click
          :triggers #{:clicked}
          :reaction (fn [this]
                      (notifos/working "Doing some heavy lifting!")
                      (util/wait 10000 #(statusbar/loader-set 0))))

振る舞いの名前はオブジェクトの:behaviors に記載したのと同じ名前にする必要があります。また、振る舞いは:reaction関数を引数として渡されたオブジェクトと共に呼び出す際の引き金となる:triggersを持っています。今回は振る舞いは、ただ単に作業の進捗を示し、10秒後にそれを隠すだけとなります。

これで、オブジェクトを作成してそれをタブに追加する準備が整いました。

(let [worker (object/create ::worker)]
  (tabs/add! worker)
  (tabs/active! worker))

コンテンツを含んだ新しいタブが出現するでしょう。そこにあるボタンをクリックすると小さいプログレスバーがページ下部に表示され、10秒後に自動的に消えると思います。

ただ、勘の良い人なら既に気づいているかも知れませんがタブを閉じることができません。この原因は、タブを閉じるためのデフォルトとなる振る舞いが存在しないことに付随します。いくつかのタブは閉じる際、ユーザーに保存を促したいかもしれないし、また他のタブは全く違った実装にしたい場合があるのでこのようになっています。 都合が良いことに、閉じる際のアクションは Light Table をリスタートせずに追加することができます。

closeイベントに反応する新しい振る舞いを追加しましょう(docs.cljs から流用)

(behavior ::on-close-destroy
          :triggers #{:close}
          :reaction (fn [this]
                      (when-let [ts (:lt.objs.tabs/tabset @this)]
                        (when (= (count (:objs @ts)) 1)
                          (tabs/rem-tabset ts)))
                      (object/raise this :destroy)))

次にオブジェクトに対し、behaviors リストに追加することによって、この振る舞いの利用を知らせる必要があります。

(object/object* ::worker
                :name "A hard worker"
                :behaviors [::work-on-click ::on-close-destroy]
                :init (fn [this] (work-button this)))

何かを再起動する必要はありません。ただ振る舞いとオブジェクトの定義を評価するだけでタブを閉じることができるでしょう。:) Light Table はなんてダイナミックなんだ!

全体的な結果を見たい人達に対して、ここに gist のリンクと、以下に gif の画像を貼っておきます。:)

screencast

このチュートリアルは LightTable でできることを示したちょっとした紹介でした。ただ、Light Table のシステム全体が如何にダイナミックかってことについて、あなたに考える機会を与えられたのではと思います。


翻訳終わり

ClojureScript でボイド(Boids)なプログラムを書いてみる

ClojureScript Clojure 人工生命

はじめに

ClojureScript の勉強のために自分で書いてみたいコードを探していたところ、以下の記事を発見。

【ボイド】JavaScriptとHTML5で『群れ』をシミュレーションしてみよう【プログラミング】 - あのねノート。

JavaScript → ClojureScript に書き直してみることにしました。

作るもの

ボイド(Boids)という人工生命シュミレーションプログラムを作ります。詳しくは元記事を参考にしてください。

完成品はこんな感じとなります。ソースはこちら

プログラミングの下準備

ClojureScript で作成するにあたり、leiningenlein-cljsbuild を活用します。

  • Leiningen: Clojure(ClojureScriptを含む)のプロジェクトを便利に管理するためのツール。
  • lein-cljsbuild: Leiningen のプラグイン。 これを使うことにより ClojureScript のコンパイルを自動で行える。

現状、ClojureScript で何かを作るならこの二つはデファクトなんで何も考えずに利用しましょう。

プロジェクト作成

lein new cljs-boids

Leiningen の lein コマンドでプロジェクトのひな形を作成します。

project.clj へ記述を追加

(defproject boids "0.1.0-SNAPSHOT"
  :description "Sample program of Boids written by ClojureScript"
  :url "https://github.com/snufkon/clj-boids"
  :license {:name "Eclipse Public License"
            :url "http://www.eclipse.org/legal/epl-v10.html"}
  :source-paths ["src/cljs"]
  :dependencies [[org.clojure/clojure "1.5.1"]
                 [org.clojure/clojurescript "0.0-2069"]]
  :plugins [[lein-cljsbuild "1.0.0"]]
  :cljsbuild {:builds
              [{:source-paths ["src/cljs"]
                :compiler {:output-to "resources/public/js/main.js"
                           :optimizations :advanced}}]})
  • :dependenciesclojurescriptを追加。
  • :pluginslein-cljsbuildを追加。
  • :cljsbuildを追加。
    • source-pathsソースコード(main.cljs)を置くsrc/cljsを指定。
    • compilemain.cljsコンパイルしてできたjsファイルの出力先(output-to)として、resources/public/js/main.jsを追加。
    • compileに最適化オプション(optimizations)として、advancedを指定。

コンパイルオプション

ちょっとだけ補足しておきますが、ボイドのプログラム作成には関係ないので読まなくても良いです。

コンパイルのオプションに:advancedを指定していますが、開発中はデバッグのため

:optimizations :whitespace
:pretty-print true

を指定しています。このオプション指定だとコンパイル後に出力されるmain.jsのコードが読める形で出力されます。 :advancedオプションだと、強力な最適化を行って、コードサイズや実行にかかる時間を少なくしてくれますが、出力されたコードは読めません(頑張れば読めるのかも...)。ちなみに、以下のようなことをしてくれているみたいです。

  • 変数や関数の名前を短いものにリネームする(mungingと呼ばれる)。
  • オブジェクトのネストを平板化する。
  • 未使用のコードを消去する。
  • インライン関数を作成する。
  • JavaScriptランタイムの特性に沿ってパフォーマンスを最適化する。

以下の本より引用。

ClojureScript: Up and Running

ClojureScript: Up and Running

:advancedコンパイルする際、いくつかの前提を元にコードを処理するため、処理対象のソースコードがこの前提に沿っていないと出力されたコードが期待する動作とならない場合もあることを頭に入れておきましょう。開発の途中途中、たまに:advancedコンパイル&実行して動作確認しておくのが良いと思います。プログラム完成後、:advancedコンパイル&実行、動かない...とならないように気をつけましょう(自戒を込めて...)。

index.html の作成

元記事index.htmlをそのまま、resources/public/index.htmlにコピーでおしまい。

main.cljs の作成

コード全体は、こちらで確認してください。気になる部分だけ解説しておきます。

(def boids (array))

(defn make-boids []
  (loop [i 0]
    (when (< i NUM_BOIDS)
      (aset boids i (js-obj "x" (* (js/Math.random) SCREEN_SIZE)
                            "y" (* (js/Math.random) SCREEN_SIZE)
                            "vx" 0
                            "vy" 0))
      (recur (inc i)))))

(make-boids)

boidsarrayjs-objで表現します。はじめ、VectorMapで表現してプログラムを作ったんですが、元のJavaScriptのコードと比較してあまりにも遅かったため書き直しました。(StackOverflowで質問したらarrayを使えと)

arrayのデータへの取得、更新にはaget,asetをそれぞれ利用します。

(aget boids index "x")  ;; boids[index].x
(aset boids index 10)   ;; boids[index] = 10
(set! (.-onload js/window) init)

set!を使い、window.onloadinit関数を設定します。

(js* "debugger;")

js*を利用してJavaScriptのコードを直接埋め込むことができます。完成したプログラムには記載していませんが、デバッグ時に上記のコードを活用していました。

(.time js/console "label name")
;; 計測したい処理を記述
(.timeEnd js/console "label name")

こちらも完成したプログラムに記載していませんが、処理時間を計測するために上記コードを活用していました。

おわりに

ClojureScript でプログラムを書くのに慣れていないので思ったより時間がかかりました。最初にboidsVector&Map で表現して作成するまでは良かったんですが、実行速度に問題があることに気づき、処理時間を計測したり、boidsの表現をarrayに変えたり、完成して:advancedコンパイルしたら動かなかったりなんなりで時間を浪費しました。最終的に完成したコードを見て思ったのは、「JavaScriptで書けばいいんじゃないかと?」、これは自分のClojureScriptのスキルが足りないのが原因な気もします。今回は ClojureScript の勉強だったので良いのですが、この程度のプログラムならそのまま JavaScript で書いたほうが良いのかなと思いました。

Light Table のプラグインを作成してみる

LightTable ClojureScript Clojure

Light Table しばらく触っていない間に0.6.0(最新は0.6.2)になり、オープンソースプラグイン対応となりました。

自分でも試しにプラグインを作成してみたので、簡単に手順を説明しておきます。

作ったもの: Shishio-sayings プラグイン

ユーザーの入力を勝手に志々雄真実(るろうに剣心)の名言に変換するお遊びプラグインです。

ソースコード

仕様

  • ユーザー入力を登録してある志々雄の名言に変換する。
  • 新しい行に移動したら、ランダムで使用する名言を変更する。
  • プラグインはコマンドでON,OFFする。

作成手順

プラグインのひな形を作成

plugins ディレクトリで下記のコマンドを実行しプラグインのひな形を作成します。 (Leiningenのインストールが必要)

lein new lt-plugin shishio-sayings
  • plugins のディレクトリ場所
    • Mac: ~/Library/Application Support/LightTable/plugins
    • Linux: ~/.config/LightTable/plugins/
    • Windows: %APPDATALOCAL%/LightTable/plugins/

作成されるディレクトリ構成は以下のようになります。

shishio-sayings
├── plugin.edn
├── project.clj
├── shishio_sayings.behaviors
└── src
    └── lt
        └── plugins
            └── shishio_sayings.cljs

shishi_sayings.cljs へ記述

shishio-sayings/src/lt/plugins/shishio_sayings.cljsプラグインで使用するコードを記述します。ひな型作成時に出力されたコードは利用しないので一旦全て削除してからコードを書きます。

(ns lt.plugins.shishio-sayings
  (:require [lt.objs.editor :as editor]
            [lt.objs.editor.pool :as pool]
            [lt.objs.command :as cmd]
            [lt.objs.notifos :as notifos]))

lt.plugins.shishio-sayingsで使用するライブラリを定義。

(def sayings ["所詮この世は弱肉強食。強ければ生き弱ければ死ぬ"
              "油断?何のことだ?これは「余裕」というもんだ"
              "まだ夜も更けてねぇのに寝言ほざいてんじゃねーよ"
              "てめえのものさしで語るんじゃねェよ"
              "「君」ぐらいつけろよ。無礼な先輩だな"
              "かかってくるなら、この如何ともしがたい実力の差を、ちったぁ埋めてからかかってこい"
              "おい!なんだ?ホントに死んじまったのか?物足りねぇ!"
              "弱者は強者の糧(かて)となるべき。糧にすらならない弱者は存在する価値すらねえ"
              "生まれがどーのこーのじゃねェ、お前が弱いから悪いんだ"
              "この俺が直々にブッ殺してやる"])

置き換えに使用する志々雄さんの名言を配列(Vector) として用意。 名言は志々雄真実_botからピックアップ。

(def current-saying (atom (rand-nth sayings)))

現在の変換先対象となる名言を保持する変数。

(defn change-to-another-saying []
  (reset! current-saying (rand-nth sayings)))

変換先対象となる名言を変更する関数。

(defn to-shishio-saying [user-say]
  (subs (deref current-saying) 0 (count user-say)))

現在の名言からユーザ入力の文字数と同等の長さの名言を切り出す関数。

(def say (atom false))
(defn on-sayings? [] (deref say))
(defn on-sayings [] (reset! say true))
(defn off-sayings [] (reset! say false))

(cmd/command {:command :toggle-shishio-sayings
              :desc "Shishio sayings: Toggle shishio sayings"
              :exec (fn []
                      (if (on-sayings?)
                        (do
                          (off-sayings)
                          (notifos/set-msg! "Shishio sayings: OFF"))
                        (do
                          (on-sayings)
                          (notifos/set-msg! "Shishio sayings: ON"))))})

名言への変換機能のON,OFFを切り替えるtoggle-shishio-sayingsコマンドを定義。定義したコマンドは、View->Commandsで開くコマンドバーから実行することができます。

(defn shishio-sayings-behind-cursor []
  (when (on-sayings?)
    (let [cm (editor/->cm-ed (pool/last-active))
          cursor (.getCursor cm)
          from #js {:line (.-line cursor) :ch 0}
          user-say (.getRange cm from cursor)
          shishio-say (to-shishio-saying user-say)]
      (if (= (count user-say) 0)
        (change-to-another-saying))
      (when (not= user-say shishio-say)
        (.replaceRange cm shishio-say from cursor)))))

(cmd/command {:command :shishio-sayings-behind-cursor
              :hidden true
              :desc "Shishio sayings: replace user input to shishio sayings"
              :exec shishio-sayings-behind-cursor})

変換機能がONであれば、変換処理を行うshishio-sayings-behind-cursorコマンドを定義。このコマンドは、キー入力があった際に呼び出したいのでコマンドバーから実行するのではなくbehaviorsファイルに設定を記述します。:hidden trueを設定するとコマンドバーにコマンドが表示されなくなります。

shishio_sayings.behaviors へ記述

{:+ {:app [(:lt.objs.plugins/load-js "shishio_sayings_compiled.js" true)]
     :editor [(:lt.objs.editor/on-change :shishio-sayings-behind-cursor)]}}

on-chnageに対応するコマンドとしてshisio-sayings-behaidn-cursorを登録。

コンパイル

shishio_sayings.cljsを保存したタイミングで自動的shishio_sayings.compiled.jsが作成されると思います。

動作確認

一旦、LightTableを終了し、起動し直します。shishio_sayings.compiled.jsがあれば、起動時に勝手にプラグインがロードされ、コマンドバーにshishioと入力すると定義したコマンドが表示されると思います。コマンドバーでShishio sayings: Toggle shishio sayingsを実行するとLightTable下部にshishio sayings: ONと表示されます。この状態で何かファイルを開きキー入力すると志々雄の名言に勝手に変化されます。もう一度、Shishio sayings: Toggle shishio sayingsを実行するとOFFにすることができます。

終わりに

公式ドキュメントも含め、まだプラグイン作成に関する情報はあまり出回ってないみたいです。現状は他の方が作成したプラグインのソースを眺めて学習するのが良いと思います。

LightTableのコマンドバーでPlugins: Show plugin managerを実行するとインストール済み利用できるプラグインの情報が表示されるのでそこから github へ行きソースを眺めるのが良さそうです。

Clojure でのお仕事募集中。

参考資料

SICP 孤読書会 - 2.4 抽象データの多重表現 (2.4.1 〜 2.4.3)

SICP

この節では、プログラムの内部実装が、異なる方法で表現されている可能性があるデータにどう対処するかを勉強する。

そこで必要となる

  • 汎用手続き(generic procedure)
  • 型タグ(type tag)
  • データ主導(data directed) プログラミング

についても述べる。


2.4.1 複素数の表現

汎用演算を使うプログラムとして、複素数の算術演算を実行するシステムの開発を考える。

複素数は2つの表現を持つことができる。

  • 直交座標形式(実部と虚部)
  • 極座標形式(絶対値と偏角)

複素数の加算(減算)では、実部と虚部による直交座標形式を使った考え方が適する

Real-part(z1 + z2) = Real-part(z1) + Real-part(z2)
Imaginary-part(z1 + z2) = Imaginary-part(z1) + Imaginary-part(z2)

複素数の乗算(除算)では、絶対値と偏角による極座標系式での表現を使った考え方が適する

Magnitude(z1・z2) = Magnitude(z1)・Magnitude(z2)
Angle(z1・z2) = Angle(z1)・Angle(z2)

複素数の演算に対して、4つの選択子と2つの構成子

  • 選択子
    • real-part
    • imag-part
    • magnitude
    • angle
  • 構成子
    • make-from-real-imag (実部と虚部で指定した複素数を返す)
    • make-from-mag-ang (絶対値と偏角で指定した複素数を返す)

が実装済みであると仮定すると抽象データを使った複素数の算術演算を実装することができる

(define (add-complex z1 z2)
  (make-from-real-imag (+ (real-part z1) (real-part z2))
                       (+ (imag-part z1) (imag-part z2))))

(define (sub-complex z1 z2)
  (make-from-real-imag (- (real-part z1) (real-part z2))
                       (- (imag-part z1) (imag-part z2))))

(define (mul-complex z1 z2)
  (make-from-mag-ang (* (magnitude z1) (magnitude z2))
                     (+ (angle z1) (angle z2))))

(define (div-complex z1 z2)
  (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
                     (- (angle z1) (angle z2))))

最初に述べたように複素数は、直交座標形式、極座標系式のどちらでも表現することができる

直交座標形式で表現

(define (real-part z) (car z))
(define (imag-part z) (cdr z))
(define (magnitude z)
  (sqrt (+ (square (real-part z)) (square (imag-part z)))))
(define (angle z)
  (atan (imag-part z) (real-part z)))
(define (make-from-real-imag x y) (cons x y))
(define (make-from-mag-ang r a)
  (cons (* r (cos a)) (* r (sin a))))

z は複素数(直交座標形式で表現されている)

極座標形式で表現

(define (real-part z)
  (* (magnitude z) (cos (angle z))))
(define (imag-part z)
  (* (magnitude z) (sin (angle z))))
(define (magnitude z) (car z))
(define (angle z) (cdr z))
(define (make-from-real-imag x y)
  (cons (sqrt (+ (square x) (square y)))
        (atan y x)))
(define (make-from-mag-ang r a) (cons r a))

z は複素数(極座標で表現されている)

先に定義した複素数の算術演算(add-complex, sub-complex, mul-complex, div-complex)は どちらの複素数表現を利用しても問題なく動作する。

2.4.2 タグ付きデータ

複素数の具体的表現(直交座標系式、極座標系式)の決定を伸ばすことができれば、システム設計の柔軟性を最大に保つことができる。
最終的に両方の表現を使うと決定することもできる。

それぞれの複素数型タグ(type tag)をつけることで、両方の表現を1つのシステムに組み込むことが可能となる。

タグつきデータを操作するため、

  • attach-tag: タグ付きデータを作る手続き
  • type-tag: タグを取り出す手続き
  • contents: 実際の内容を取り出す手続き

を定義する

(define (attach-tag type-tag contents)
  (cons type-tag contents))

(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum -- TYPE-TAG" datum)))

(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum -- CONTENTS" datum)))

これらを使い、複素数が直交座標形式、極座標形式のどちらを持つか判定する定義

(define (rectangular? z)
  (eq? (type-tag z) 'rectangular))

(define (polar? z)
  (eq? (type-tag z) 'polar))

を書くことができる。

型タグを使った直交座標表現

(define (real-part-rectangular z) (car z))

(define (imag-part-rectangular z) (cdr z))

(define (magnitude-rectangular z)
  (sqrt (+ (square (real-part-rectangular z))
           (square (imag-part-rectangular z)))))

(define (angle-rectangular z)
  (atan (imag-part-rectangular z)
        (real-part-rectangular z)))

(define (make-from-real-imag-rectangular x y)
  (attach-tag 'rectangular (cons x y)))

(define (make-from-mag-ang-rectangular r a)
  (attach-tag 'rectangular
              (cons (* r (cos a)) (* r (sin a)))))

型タグを使った極座標表現

(define (real-part-polar z)
  (* (magnitude-polar z) (cos (angle-polar z))))

(define (imag-part-polar z)
  (* (magnitude-polar z) (sin (angle-polar z))))

(define (magnitude-polar z) (car z))

(define (angle-polar z) (cdr z))

(define (make-from-real-imag-polar x y)
  (attach-tag 'polar
               (cons (sqrt (+ (square x) (square y)))
                     (atan y x))))

(define (make-from-mag-ang-polar r a)
  (attach-tag 'polar (cons r a)))

2.4.1 で仮定した汎用手続き real-part, imag-part, magnitude, angle は タグを調べ、その型のデータを扱う手続きを呼ぶ手続きとして実装することができる。

(define (real-part z)
  (cond ((rectangular? z)
         (real-part-rectangular (contents z)))
        ((polar? z)
         (real-part-polar (contents z)))
        (else (error "Unknown type -- REAL-PART" z))))

(define (imag-part z)
  (cond ((rectangular? z)
         (imag-part-rectangular (contents z)))
        ((polar? z)
         (imag-part-polar (contents z)))
        (else (error "Unknown type -- IMAG-PART" z))))

(define (magnitude z)
  (cond ((rectangular? z)
         (magnitude-rectangular (contents z)))
        ((polar? z)
         (magnitude-polar (contents z)))
        (else (error "Unknown type -- MAGNITUDE" z))))

(define (angle z)
  (cond ((rectangular? z)
         (angle-rectangular (contents z)))
        ((polar? z)
         (angle-polar (contents z)))
        (else (error "Unknown type -- ANGLE" z))))

汎用演算子が polar 型 の数に演算するときは、タグを剥がし 極座標表現を扱うプログラムに渡す。
逆に汎用演算として複素数を構成するときは、極座標表現を使うプログラムで polar 型のタグを付ける。

データオブジェクトをレベルからレベルへ渡すとき、タグをつけ剥がしすることは重要な組織化戦略となる。
(2.5節で詳しく扱う)


2.4.3 データ主導プログラミングと加法性

データの型を調べ、適切な手続きを呼び出す一般的戦略は型による振り分け(dispatching on type)という。
システム設計で部品化を実現する強力な戦略となる。

2.4.2 節の振分け実装には2つの弱点がある

  • 汎用インターフェース手続き(real-part, imag-part, magnitude, angle) は異なる表現のすべてを知らなければならない
  • それぞれの表現はシステム全体でどの二つの手続きも同じ名前を持たない保証をしなければならない

汎用インターフェースの実装が加法的(additive)ではない。

システム設計を更に部品化する手段が必要。 データ主導プログラミング(data-directed programming)というプログラム技法が役に立つ。

データ主導プログラミングは、一方の軸に演算、他方の軸に型をとった二次元の表を扱っているとみなすことができる。

Polar Rectangular
real-part real-part-polar real-part-rectangular
imag-part imag-part-polar imag-part-rectangular
magnitude magnitude-polar magnitude-rectangular
angle angle-polar angle-rectangular

表の項目は各引数の型に対し、各演算が実装する手続きを表す。

表から演算名と引数の型の組合せを探し、作用させる正しい手続きを見つけ、 それを引数の内容に作用させる単一の手続きとしてインターフェースを実装する。

こうすることにより、新しい表現を追加する際、既存の手続きを変更する必要はなく、表に新しい項目を追加するだけとなる。 汎用インタフェースの実装が加法的となる。


問題 2.73 〜 2.76

SICP/ch2/2-73.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-74.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-75.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-76.txt at master · snufkon/SICP · GitHub

に解答を追加。


SICP 孤読書会のメインページはこちら

計算機プログラムの構造と解釈

計算機プログラムの構造と解釈

SICP 孤読書会 - 2.3 記号データ (2.3.1 〜 2.3.4)

SICP

この節では、データとして任意の記号に対して作業する能力を採用し、言語の表現力を拡大する。


2.3.1 クォート

記号を操作するために、データオブジェクトをクォートする(quote)能力が必要である。

リスト (a b) を作りたい場合、(list a b) で作ることはできない。
(list a b) は a と b をそれぞれ評価し、値のリストを作成してしまう。

(define a 1)
(define b 2)
(list a b) => (1 2)

リストや記号を評価される式としてではなく、データオブジェクトとして扱うことを示すのにクォートを使用する。

(list 'a 'b) => (a b)

(list 'a b) => (a 2)

リストの印字表現を使い、合成オブジェクトを作成するのにクォートを使うことができる

(car '(a b c)) => a

(cdr '(a b c)) => (b c)


問題 2.53 〜 2.55

SICP/ch2/2-53.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-54.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-55.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.3.2 例: 記号微分

記号操作、データ抽象の実例として記号微分を実行する手続きの設計を考える。

記号微分を実行する手続きは

代数式(2ax + b)と変数(x)を引数としてとり、代数式を変数で微分した結果(2a)を返す

手続きとして実装する。

抽象データによる微分プログラム

対象の問題を簡単にするため、2つの引数を持った加算と乗算の演算だけからなる式を扱うこととする。
これらの式は以下の簡約規則を使うことで実行できる

\(\frac{dc}{dx} = 0\)     c は定数か x と異なる変数

\(\frac{dx}{dx} = 1\)

\(\frac{d(u + v)}{dx} = \frac{du}{dx} + \frac{dv}{dx}\)

\(\frac{d(uv)}{dx} = u(\frac{dv}{dx}) + v(\frac{du}{dx})\)


次の選択子、構成子、述語を実装した手続きは既にあると仮定すると

(variable? e)   e は変数か?
(same-variable? v1 v2)   v1 と v2 は同じ変数か?

(sum? e)   e は和か?
(addend e)   e の加数
(augend e)   e の被加数
(make-sum a1 a2)   a1 と a2 の和を構成

(product? e)   e は積か?
(multiplier e)     e の乗数
(multiplicand e)   e の被乗数
(make-product m1 m2)   m1 と m2 の積を構成

記号微分を実行する手続き(deriv)は以下にように記述できる

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))

この deriv は抽象データを使って表されている。
そのため、正当な選択肢と構成子を設計しさえすれば、

代数式の表現をどう選ぶか?

に無関係に微分を行うことができる。

代数式の表現

上記したように代数式の表現は自由に決めることができる。

例えば、通常の代数記法に合わせて ax + b を

(a * x + b)

と表現することができる。

ここでは、Lisp と同様、前置記法で代数式を表現することを考える。 ax + b は

(+ (* a x) b)

と表現することになる。

前置記法での代数式表現に合わせ、 deriv で使われている選択子、構成子、述語のデータ表現は以下のようになる

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum a1 a2) (list '+ a1 a2))

(define (make-product m1 m2) (list '* m1 m2))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s) (cadr s))

(define (augend s) (caddr s))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (multiplier p) (cadr p))

(define (multiplicand p) (caddr p))

deriv 手続きの使用例

(deriv '(+ x 3) 'x)               ; (+ 1 0)

(deriv '(* x y) 'x)               ; (+ (* x 0) (* 1 y))

(deriv '(* (* x y) (+ x 3)) 'x)   ; (+ (* (* x y) (+ 1 0))
                                  ; (* (+ (* x 0) (* 1 y))
                                  ; (+  x 3)))


問題 2.56 〜 2.58

SICP/ch2/2-56.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-57.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-58-a.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-58-b.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.3.2 例: 集合の表現

集合に使われる演算を規定することで「集合」を定義する。

  • 演算
    • element-of-set? : 与えられた要素が集合の構成要素であるか?を判定する述語
    • adjoin-set : 引数としてオブジェクトと集合をとり、元の集合にそのオブジェクトを追加した集合を返す
    • union-set : 2つの集合の和集合
    • intersection-set : 2つの集合の積集合

データ抽象的に、これらの演算を実装する表現は自由に選択することができる。

  • 集合の表現
    • 順序づけられないリストとしての集合
    • 順序づけられたリストとしての集合
    • 二進木としての集合

表現の選択は、そのデータを使用するプログラムの効率に大きく影響する。


問題 2.59 〜2.66

SICP/ch2/2-59.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-60.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-61.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-62.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-63.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-64.png at master · snufkon/SICP · GitHub
SICP/ch2/2-64.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-65.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-66.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.3.3 例: Huffman 符号化木

集合と木を操作するリスト構造、データ抽象の使い方を Huffman 符号化木を例として練習する。


問題 2.67 〜 問題2.72

SICP/ch2/2-67.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-68.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-69.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-70.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-71.png at master · snufkon/SICP · GitHub
SICP/ch2/2-71.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-72.txt at master · snufkon/SICP · GitHub


SICP 孤読書会のメインページはこちら

計算機プログラムの構造と解釈

計算機プログラムの構造と解釈

【旅138日目 2012/10/14】桂浜と土佐闘犬

自転車日本一周 【131〜140日】京都 → 高知

自転車日本一周、138日目。

起床

続きを読む

SICP 孤読書会 - 2.2 階層データ構造と閉包性 (2.2.1 〜 2.2.4)

SICP

この節では、

  • 合成データの閉包性(closure property)の重要さ

について話す。

要素が"対"であるような"対"を作る能力は、リスト構造にとって重要。 この能力を cons の閉包性という。

閉包は階層的(hierarchical)構造を作ることができる。


2.2.1 並びの表現

対を使って並び(sequence)を表現することができる。

例えば、1, 2, 3,4 の並びは

(cons 1
      (cons 2
            (cons 3
                  (cons 4 nil))))

で表現することができる。

nil は 並びの終端を表す。
gauche には nil がないので空リスト '() で終端を表します。

入れ子の cons で作られた対の並びをリスト(list)という。
リストは list という基本手続きで作成することができる。

(list 1 2 3 4)

は上記の cons で作成した 1, 2, 3, 4 の並びと等価。


問題 2.17 〜 2.23

SICP/ch2/2-17.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-18.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-19.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-20.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-21.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-22.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-23.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.2.2 階層構造

リストによる並びの表現は、その要素がまた並びであるような表現に一般化できる。

例えば

(cons (list 1 2) (list 3 4))

要素自身が並びであるような並びは、木(tree)としてみることができる。

再帰は、木構造を扱う自然な道具である。


問題 2.24 〜 2.32

SICP/ch2/2-24.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-24.png at master · snufkon/SICP · GitHub
SICP/ch2/2-25.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-26.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-27.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-28.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-29.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-30.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-31.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-32.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.2.3 公認インタフェースとしての並び

引数として木をとり、奇数である葉の二乗の和を計算する手続きを考える

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares (car tree))
                 (sum-odd-squares (cdr tree))))))

この手続きは内部で

  • 木の葉を数え上げる
  • フィルタを通し、奇数のものを選ぶ
  • 選ばれたものをそれぞれ二乗する
  • 0 の初期値に結果を + を使いアキュムレートする

を行なっている。

しかしながら、実装としては数え上げを手続き全体に撒き散らし、 写像、フィルタ、アキュムレータを使って混ぜあわせている。

信号処理のように

enumerate --> filter --> map --> accumulate

の構造が明白になるようにプログラムを構成できれば、 出来上がったプログラムの明晰性が増大する。

信号処理構造を構成する鍵は、プロセスのある段から次へ流れる「信号」 に集中することである。

並びの演算

プログラムを並びの演算として表すことは、部品化されたプログラム設計を可能とする。
リストとして実装した並びは、処理部品を組み合わせるのを可能にするための公認インタフェースとして役立つ。


問題 2.33 〜 2.43

SICP/ch2/2-33.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-34.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-35.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-36.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-37.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-38.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-39.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-40.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-41.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-42.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-43.scm at master · snufkon/SICP · GitHub

に解答を追加。


2.2.4 例: 図形言語

図形言語を例に、データ抽象と閉包の能力を示す。


問題 2.44 〜 2.52

SICP/ch2/2-44.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-45.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-46.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-47.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-48.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-49.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-50.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-51.scm at master · snufkon/SICP · GitHub
SICP/ch2/2-52.scm at master · snufkon/SICP · GitHub

に解答を追加。

図形の描画には、以下を利用させてもらいました。

図形言語 描画スクリプト – SICP(計算機プログラムの構造と解釈)その59 : Serendip - Webデザイン・プログラミング
図形言語 描画スクリプト(with Canvas and JavaScript) :: SICP(計算機プログラムの構造と解釈)- Serendip


SICP 孤読書会のメインページはこちら

計算機プログラムの構造と解釈

計算機プログラムの構造と解釈