サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
掃除・片付け
rainyday.blog.ss-blog.jp
一昨年に出版されたImplementing Programing Languages <http://www.digitalgrammars.com/ipl-book/> という本(以下IPL)を読んでいました。 この本は名前の通りインタプリタ/コンパイラの実装についての本ですが、とてもいい本です。何がまずいいかというと、薄い(そして安い)。207ページしかありません。コンパイラ作りたいとなったらドラゴンだのタイガーだのと格闘しなければならないという先入観がありますのでこの薄さは画期的です。 内容の深さという意味では他の本に譲る点はあるのでしょうが、一通りのことが実践できるようになるまでを要領よく解説していて、かつ最初は読み飛ばしてもいい理論部分にもわざわざ印をつけてくれているので、おそらくコンパイラ作成志望者にとっての最短コースを示してくれる本だと思います。 飛ばし読みの成果としてJVM
OCaml で Tcl インタプリタのサブセットを作ってみた。Tcl の文法は [1] のようなものだが、すべてを実装しているわけではない。コードは全115行で以下のとおり。 module StringMap = Map.Make(String) exception Unknown_command type interp = { result : string; g : string StringMap.t; } type state = { openBraces : int; argv : string list; buf : string; nest : bool; } let string_of_char c = String.make 1 c let invoke interp argv = let argv = List.rev argv in match argv with |
今回は手近なところで Tcl を使って Wiki 記法のパーサを作ってみようと思う。 これは以前 Tcl で Wiki 記法を採用したソフトウェアを作成したけどあまり美しくないやりかたでゴリゴリ書いていたのでプログラム的に触りにくいものになってしまった反省というのもある。 Tcl でパーサを作成するのためのライブラリはいくつかあるが、今回は Yeti/Ylex を使う。 http://www.fpx.de/fp/Software/Yeti/ Wiki 記法の文法は以下のとおりとする。 -記事は空行区切りで並べられたブロック要素群である。 -「*」で始まるブロックは見出しである。レベル6見出しまで対応 -「-」で始まるブロックは順序なしリストである。 -「+」で始まるブロックは順序ありリストである。 -それ以外のブロックは段落である。 まずは字句解析器を作る。Ylex では 1. yeti:
PHP に array_reduce という関数が用意されていたので喜び勇んで使ってみたんだけど実に興味深い仕様だったのでここに記しておきたい。 array_reduce は関数型言語でいう reduce か fold に相当する関数だ。例を挙げると、 <?php function conc($acc, $x) { return $acc . $x; } echo array_reduce(array("a", "b", "c"), "conc"); ?> この結果は abc となる。 別にコールバック関数名を文字列で与えるのが気持ち悪いとかいう話ではない。 次に、array_reduce は第3引数に初期値を与えることができて、それを与えるとコールバック関数が最初に呼ばれるときの第1引数になる(fold になる)。 ではこれはどうなるだろうか。 <?php function conc($
このところマイコンを使った電子工作に興味を持ち始めました。電子工作をやっているといっても理科の知識は中学生未満だし半田付けもできるだけ避けたいという軟派な感じのものですが。 マイコンとしては主にPICという電子工作によく使われている廉価なものを使っていて、アセンブラかCで書いたプログラムをマイコンのフラッシュメモリに書き込むのですが、ちょっとした実験のために使い捨てプログラムが必要になることがあります。しかしそうしたプログラムをいちいちアセンブラやCで書いてライターで書き込むのは面倒くさい。多少の制約(時間的な精度とか)は受け入れても超高級言語が使いたい、と思うことがあります。 そこで Gainer mini [http://gainer-mini.jp/] というデバイスを買いました。これはPCとUSBケーブルで接続され、電子回路上の電圧の制御や読み取りがPC上のプログラミング言語から行
よく Scheme や Lisp の本で Scheme/Lisp を使って Scheme/Lisp 処理系を書くというのがあって大層簡潔に書いてあったりするのですが、これは要するに S 式リーダ機能がビルトインで存在するというのが有利に働いているので、他の言語でも S 式を簡単に読めれば同じくらいにはできそうです。 そこで OCaml の sexplib [1] を使ってみたかったこともあって、それを使ってなんちゃって Scheme を書いてみました。 なお sexplib は「産業界における関数型言語の事例」でよく引き合いに出されている Jane Street Capital で開発された OCaml 向けの S 式ライブラリです。 #use "topfind";; #require "sexplib";; #require "extlib";; open ExtList;; open
Java を勉強していてエキゾチックだと感じるのはやはりチェック例外だ。このチェック例外という仕組みは、便利か邪魔か、ということはひとまず置くとしてやはり非常に興味深いものだと思う。そんな Java のチェック例外を自分なりに理解しやすいように整理・言い換えをしてみた。(これも前回と同様にかなり雑な内容だと思いますがとりあえずあきらめて記事にしてしまいます) まずメソッドの throws 節に書かれる例外クラスを戻り値の型と比べてみよう。戻り値の型は実際に return される型と不整合があるとコンパイルエラーになる。同様に throws 節の例外クラスと実際にメソッドから投げられうる例外との間に不整合があるとコンパイルエラーになる。 いずれもメソッドのクライアントに対する契約の一部をなしているから、宣言された型より小さい型を実際に返す/投げる分には構わないが逆は不可である。例えば Obj
Ruby 1.9 で標準装備になったという tap メソッド [1] [2] というのがかなりかっこいい。この場合の tap って多分電源タップの意味だろうか。メソッドチェーンの流れを切るまいとする Ruby 的な発想なんだろうと思う。 というわけで Scala でもやってみた。仕組み自体はおなじみのもの。Scala でも特に問題無い様に思われる。 scala> class Tap[T](obj: T) { | def tap(block: T => Unit): T = { block(obj); obj } | } defined class Tap scala> implicit def any2tap[T](obj: T): Tap[T] = new Tap(obj) any2tap: [T](T)Tap[T] scala> val l = List(2, 1, 4, 5, 3)
Higher-Order Lua [1] のサイトを作る上で一部に Text::Hatena [2] を使用しているのだけど Text::Hatena はドキュメント上はルールの拡張や改変をサポートしていなくて細かいことをやろうとしたら HTML 直打ちをしないといけないところが都合が悪い。 Text::Hatena は内部的には Parse::RecDescent [3] を使っているのだが、このパーサには Extend メソッドと Replace メソッドが定義されていて、既に作られているルールを後から変更することが可能である。 たとえば最初に次のような文法があったとする。 use Parse::RecDescent; $grammar = q( expression : atom "+" expression { $return = $item[1] + $item[3]; } ex
最近プログラミング的なことが何もできてなくて書けることが無いので scalac のちょっと興味深いコンパイラオプションの話を2点お届けします。 * -Xprint:<phase> Scala コンパイラは入力プログラムを構文解析後、構文木に対するさまざまな変換フェイズの後に JVM バイトコードに辿り着くようです。 -Xprint オプションを使うとその各フェイズで Scala プログラムがどんな姿をしているかを見ることができます。 ためしに以下のようなプログラムを用意しましょう。 object For { def main(args: Array[String]) = { for (i <- 1 to 10) { println(i) } } } コンパイルのフェイズにどんなものがあるかは scalac -Xshow-phases で見ることが出来ます。おそらく上から下に進むのでしょうね
情報隠蔽とパターンマッチを巡って考えたことなど。 OCaml にはシグニチャという仕組みがあってオブジェクト指向言語でいうところのインターフェイスのようなものとして使われる。 例として次のようなスタックの実装を考えてみる。 module StackImpl = struct type 'a t = 'a list let empty = [] let push x s = x::s let pop (x::xs) = (x, xs) end モジュール StackImpl は単純にリストとしてスタックを定義している。 # let s = StackImpl.empty;; val s : 'a list = [] # let s = StackImpl.push 'a' s;; val s : char list = ['a'] # let s = StackImpl.push 'b' s
{ case 1 => "One" case 2 => "Two" case _ => "Many" }:Int=>String
Prolog で簡単なスタック言語を作ってみた。組み込み関数は以下の通り。 - dup: スタックの先頭を複製してスタックに積む - swap: スタックの最初の2つを入れ替える - pop: スタックの最初の要素を取り除く - add: スタックの最初の2つを取り除いてそれらを合計したものを積む - if: スタックの先頭の真偽値に応じて2つ目ないし3つ目の関数を実行 - cons: スタックの最初の要素を2つ目の要素(リスト)にconsする - emptyp: スタックの最初の要素を取り除き、それが空リストだったらtrue、それ以外だったらfalseをスタックに置く - car: スタックの先頭要素(リスト)を取り除き、そのcarを積む - cdr: スタックの先頭要素(リスト)を取り除き、そのcdrを積む - app: スタックの先頭要素(関数)を適用する - papp: スタックの
EOPL の続き。また進路を変更して今度は第5章のオブジェクト指向言語の実装をやることにした。ここでは4通りの実装を紹介しているのだけどまずは 5.4.1 A Simple Implementation から。 この実装ではオブジェクトを part というデータ型のリストとして表現する。 (define-datatype part part? (a-part (class-name symbol?) (fields vector?))) 一つの part はクラス名とフィールドの配列を持っている。継承されたクラスをインスタンス化した場合、例えば c1 を継承した c2 をインスタンス化した場合は part のリストの car が c2 の part で、c2 に固有ないしはオーバーライドしたフィールドが入り、リストの cadr には c1 のフィールドが入る。 メソッドを呼び出す場合はこの
本質的でない記述に嫌悪感を感じるセンスがあれば、同じキーが何度も現れていることを「めんどくさい」と感じるはずだ。そして、こんなふうに書けないだろうかと一度は思うはずだ。 data = %h{ ['name', 'age', 'email'], ['Foo', 20, 'foo@mail.com'], ['Bar', 21, 'bar@mail.net], ['Baz', 22, 'baz@mail.org'], } 「怠慢はプログラマの美徳」というけれど - kwatchの日記 Ruby はこんな書き方できるのか、面白いなー、と思ったらそうではなくて架空の文法みたいですね。 というわけで Scala ではどうするかと思って考えてみました。 元の例はハッシュを構造体的に使って、それを表組み形式で書けるコンストラクタを作るということですが、静的言語ではあまりそういうことをしないので問題を直接に
Ruby のブロックつき open のように勝手に後始末をしてくれる open メソッドを Scala で実装することを考えて見ます。これを素直に書けばこうなります。 import java.io.FileOutputStream object DisposableFile1 { def openOut(path: String)(block: FileOutputStream => Unit) { val out = new FileOutputStream(path) try { block(out) } finally { out.close() // Console.println("closed") } } } これはこのようにして使えます。 scala> import DisposableFile1._ import DisposableFile1._ scala> openO
結構前にブックマークして後でちゃんと読もうと思ってた「Regular Expression Matching Can Be Simple And Fast」という記事 [1] があるのだけど、それを参考にして OCaml で正規表現エンジンを作ってみました。 type state = | Char of char * state ref | Split of state ref * state ref | Match type frag = {nfa: state; danglings: state ref list} let post_of_regex regex = let rec expr = parser | [< c = conc; t = expr_tail >] -> c ^ t and expr_tail = parser | [< ''|'; c = conc; t =
「Scala で diff を書いてみた」[1] という記事に触発されて [2] の論文や [3] の解説を読んで diff のアルゴリズムを勉強して自分なりに Scala で実装してみました。 これは [2] で "An O((M+N)D) Greedy Algorithm" と呼ばれているほうの実装で、論文の後半では改良についても書いてあるけどそちらは読んでいません。 私なりに工夫をした部分は全体的に副作用を排除した所とエディットグラフの格子点をオブジェクトとして表現した点です。 元論文の擬似コードで "a number of simple optimizations are employed" とされている部分は可読性の観点から取り入れませんでした。ただ元論文が「D回の編集で到達する(対角線 k 毎の)最遠点の集合」を配列で管理しているのを Set で管理するようにしたのは本当はよろ
昔論理学の授業で習ったタブロー法を Scheme と SLLGEN で実装してみました。 * 速習タブロー法 タブロー法とは論理式が充足可能か矛盾しているかを確かめるアルゴリズムの一つです。 充足可能というのはその論理式が真になるような場合がありうるかということです。例えば P&Q は P が 真で Q も真であれば真になるので充足可能です。一方で P&~P は P が真であっても偽であっても真になりえないので矛盾しています。 タブロー法は 1. 与えられた論理式が全て充足可能であると仮定する 2. 論理式を展開規則によって原子式まで分解して行く。例えば「A&B=真」という仮定からは「A=真」「B=真」という2つの仮定が生じます。 3. 分解していく過程でなんらかの原子式Pについて「P=真」と「P=偽」の両方が現れたら矛盾。最後まで矛盾しなかったら充足可能。 という手順を踏んでいきます。展
IE でウェブサイトを開いてそのスクリーンショットを撮るスクリプトを書いてみた。 Param([String]$url, [String]$filename, [String]$format="png") if (!$url -or !$filename) { return } $ie = new-object -com InternetExplorer.Application # URL を開く $ie.Navigate($url) # ページをロードし終わるまで待つ while ($ie.Busy) {sleep -milliseconds 10} # バー関連はすべて消して IE を可視化 $ie.StatusBar = $false $ie.ToolBar = $false $ie.MenuBar = $false $ie.AddressBar = $false $ie.Visib
前回のプログラムの問題点 前回 [1] の sock_try2.php は同じ期間に1つの接続しか受け入れない設計でした。 クライアントから以下のように実行してみるとそれが分かります。 % set f [socket localhost 9999] sock1544 % set g [socket localhost 9999] sock1532 % puts $f f; flush $f % puts $g g; flush $g % puts $f f; flush $f % puts $g g; flush $g % puts $f f; flush $f % puts $g g; flush $g % close $f % close $g これを実行するとサーバ側は以下のようになります。 php sock_try2.php f f f g g g クライアントからは2つの接続から
GNU GLOBAL [1] というツールを使ってみた。 昔からあるようだし、いまさら便利がっているほうが恥ずかしいのかもしれないけどこれは素晴らしい。 何をしてくれるかというと、C や C++ なんかのソースを総ざらいして関数やマクロなどがどこで使用されているかという情報をハイパーテキスト化してくれる。他人のソースを読むときとか、自分のソースをリファクタリングしたりするときにかなり重宝しそう。例えばある関数を改変したいときにどこでその関数が使われているかという影響範囲がすぐに一覧で分かる。それに出力が HTML なのでかなり直感的にブラウズできる。他人の書いたソースをつらつらと眺めるのに便利な感じだ。 使い方はインストールして、ソースツリーの置かれたディレクトリで gtags htags -sa と打つ。これで HTML というディレクトリができるので ./HTML/index.html
Camomile について調べたメモ。 普通の文字列型 (string) と Camomile 内部のユニコード文字列型との間の変換を行うエンコーダ/デコーダを作る。内部エンコーディングとして UTF-8 を使う場合は以下のようにする。UTF8 以外にも UText, XString, UTF16, UCS4 が選べるようだ。 KURO-BOX% ocaml bigarray.cma camomile.cma Objective Caml version 3.10.0 # module U = CamomileLibrary.Default.Camomile.CharEncoding.Make(CamomileLibrary.UTF8);; module U : sig type text = CamomileLibrary.UTF8.t val decode : CamomileLibr
私はこれまではまだ Tcl8.4 をメインにしていて 8.5 の機能をあまり触っていないことに気がついたので新機能を試してみることにしたい。 まずは新規追加になった apply コマンド。これは端的に言うと Tcl で関数型プログラミングへの道を開くものだ。 プログラミング言語のデザインでは「なんでも○○」という原則を作ることで仕様を簡潔にするということがしばしば行われている。○○に入るのは「オブジェクト」だったり「S式」だったりするかもしれない。Tcl ではそこに「文字列」が入る。Tcl という言語におけるファーストクラスは文字列のみであり(EIAS: Everything Is A String)、Tcl の魅力と奇怪さの多くはここから来ている。 さて、 Tcl ではプロシージャ(=関数)は通常の変数とは別の名前空間を持ち、また通常の変数への代入はできない。 例えば Lua や OCa
「プログラミング言語の基礎概念」(五十嵐2011)をAgdaでやっていた途中だが、 ここで "Types and Programming Language" (Pierce 2002) の第8章 "Typed Arithmetic Expressions" をAgdaでやることにする。 open import Relation.Binary.PropositionalEquality using (_≡_; refl) open import Data.Product using (_×_; proj₁; proj₂; ∃; ∃-syntax) renaming (_,_ to ⟨_,_⟩) open import Data.Sum using (_⊎_; inj₁; inj₂) infix 10 succ_ infix 10 pred_ infix 9 iszero_ infix 8 i
Scala に名前付き引数ってないのかなと思って調べてみたら、プリミティブとしてはなかったけど組み立てることはできたので紹介。まずは名前付き引数を実現するのに必要な道具立てから。 1. Scala は可変長引数が扱える 引数の型の後に * を付けると可変長引数が取れます。 scala> def sum(nums: Int*) = { nums.foldLeft(0) { (sum, n) => sum + n } } sum: (Int*)Int scala> sum(1, 2, 3) unnamed0: Int = 6 scala> sum(1, 2, 3, 4, 5) unnamed1: Int = 15 2. Scala にもファットコンマがある これはついさっきまで知りませんでしたが、タプルを作るのにコンマだけでなく「->」が使えます。 scala> ("Smith", 25) u
抽象データ型とリテラルというのがそもそも相容れないのかもしれないが Camomile の文字列型にはリテラルがない。ソースを書いた時点で固定的な情報をランタイムに計算するのはちょっと癪なのでいろいろ考えてみたのだけど、結局文字列型としては UTF8.t を、リテラルとしては通常の OCaml の文字列リテラルを使って abstraction barrier を破って UTF8.t と認識させるのが一番簡単であろうという結論に達した。 ただしこれだとソースファイルも UTF-8 で書かないといけないという問題がある。これを解決するために Java でいう native2ascii のような簡単なツールを作った。 (* wchar2latin.ml *) open CamomileLibrary.Default.Camomile;; open CamomileLibrary.Default.C
Camomile についてさらに調べる。 Camomile のユニコード文字列型には何種類かあるけれども文字型は UChar という1つしかない。 特定のエンコーディングで書かれたテキストファイルから読み込むには以下のようにする。hyoji.txt は Shift_JIS で「表示」の2文字だけが書かれたファイルとする。 # let inc = open_in "hyoji.txt";; val inc : in_channel = <abstr> # let sjis = CamomileLibrary.Default.Camomile.CharEncoding.of_name "SHIFT_JIS";; val sjis : CamomileLibrary.Default.Camomile.CharEncoding.t = <abstr> # let inc' = new Camomi
そろそろ Camlp4 3.10 を調べていこうかと思った。 * Camlp4 で何もしない OCaml ソースを構文木にしてさらに OCaml コードに戻すだけのコマンドラインは以下のようになる。 camlp4 -parser OCaml -printer OCaml tryme.ml これは以下と同じ camlp4 Camlp4OCamlParser.cmo Camlp4OCamlPrinter.cmo tryme.ml 以前の Camlp4 では出力でコードに戻す場合と構文木のままダンプしてコンパイラに渡す場合でプリンタを変えなければいけなかったけど 3.10 では -printer Auto とすると適宜に選んでくれる。 camlp4 -parser OCaml -printer Auto tryme.ml # この場合コードを出力 ocamlc -pp 'camlp4 -pars
次のページ
このページを最初にブックマークしてみませんか?
『Rainy Day Codings:So-net blog』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く