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

きくらげ観察日記

好きなことを、適当に。

Needleman-Wunsch法により配列の大域アラインメントを求める

アラインメントとは、2つの配列s, tに欠損記号「-」を挿入して、出来る限り2つの一致度が高くなるように並べたものです。 例えば、2つの文字列"ABCD"と"ACDE"があったとき、これは1つめの文字列から'B'を削除して末尾に'E'を挿入たものだと考えるのが自然で…

OCamlのFunctorという概念を知らずに自分で再発明していた話

最近わけあってOCamlの勉強をしているのですが、OCamlは多相的な関数を定義する方法として、Functorというものを持っています。 (* 要素の型と、その比較方法を定義するモジュール *) module type Cmp = sig type elt val le : elt -> elt -> bool (* <= *) …

Gaucheのwriteのバグ(?)を発見した

全角スペースはwriteでは||で囲われずに普通に表示されるのに、readでは半角スペースと同一の扱いでスキップされます。 gosh> (with-output-to-string (^() (write '| |))) ; 全角スペース " " gosh> (call-with-input-string "| |" read) ; ||で囲わないとr…

CGIの仕様

とある理由からGaucheでCGIとかいう謎なことをしなければならなくなったので、ここにメモしておきます。 メソッドは環境変数REQUEST_METHODに保存される。 GETパラメータは環境変数QUERY_STRING、POSTのボディは標準入力。ただし、GET/POSTパラメータはGauch…

Gaucheで文字列のシーケンシャルアクセス

Gaucheでそこそこサイズの大きい文字列へのシーケンシャルアクセスをしたい場合の注意点です。例として、以下のURLにある『吾輩は猫である』の文書中に、何回「猫」という文字が出てくるかを調べてみましょう。http://www.aozora.gr.jp/cards/000148/card789…

Gaucheでロード時定数を作る

Gaucheには元々ロード時定数という機能はありませんが、マクロを使ってうまいこと頑張ると作ることができます。 ;; ロード時定数を保存するためのモジュール (define-module *constant-table*) ;; モジュール module の中で expr を評価し、 *constant-table…

Basic認証の方法を理解する

Basic認証は数あるHTTPの認証方法の中でも最も簡単なものです。認証方法は、ユーザー名とパスワードをコロンで繋いだものをbase64でエンコードし、Authorizationヘッダの値に"Basic (先ほど作った文字列)"をセットするだけです。アホみたいに簡単なので、不…

Gaucheでクラスのフィールド名を変数に束縛する。

HaskellでいうNamedFieldPunsのようなものです。 クラスのインスタンスと、スロット名のリストを渡すことによって、スロット名と同名の変数にスロットの値を束縛するマクロを書きました。使用例は記事の下の方にあります。 ;; macro let-slots (((slot-name …

Schemeと各括弧

多くのScheme処理系では、角括弧[]が通常の括弧()と同一視されます。 この角括弧の使いどころについてまとめてみました。 角括弧は使うな まず始めに結論から書くと、今後書くSchemeのコードでは、角括弧は使用しない方が良いでしょう。というのも、R7RS*1に…

Gaucheでソースコードのあるパスを取得

きちんと ./configure && make && make install するようなプログラムでもない限り、ソースコードを適当にどこかから引っ張ってきて、そこから $ gosh ./main.scm するだけでとりあえず動くようにできたほうが楽な場合はよくあります。 しかし、Gaucheでそれ…

Gaucheで#<eof>を返す

ジェネレーターを自作する場合なんかに#<eof>を返したくなる場合がありますが、以外とググッても方法が出てきません。R6RSの(eof-object)を使えば簡単に生成できます。 ;; 1からnまでの数を返すgeneratorを返す (define (gen n) (define i 0) (^() (if (<= n i) (</eof>…

Schemeにおける「多値」という概念について

inkar-us-i.hatenablog.comこの記事で少しだけ多値について紹介しましたが、この頃はまだよく存在意義がわかっていませんでした。 そもそも多値とは? 大雑把に説明すると、valuesとかhoge&fuga関数を呼んだ時に値が複数返ってくるアレです。 (values 3 2 1)…

Gaucheで値の比較

値の比較に使用する関数は通常eq?, eqv?, equal?の3種類あるのですが、それらの使い分けが曖昧だったのでまとめてみました。 eq? (eq? x y) はxとyが全く同じオブジェクトであるか(=メモリ上の同じ位置にあるか)どうかを判定します。Pythonのisに近いやつで…

Gaucheでデバッグ

Gauche Users’ Reference: Top上のサイトを見る限り、printfデバッグ的なことをするためには#?= #?,の2つの構文が使えるようです。とりあえず#?=の使用例。 gosh> (define (foo x) (+ x 1)) foo gosh> #?=(foo 3) #?="(standard input)":21:(foo 3) #?- 4 4 …

Gaucheでreturn文

return文のようなものは比較的簡単に作れますが、念の為覚え書き。値を返したい位置の継続を受け取って、returnするかわりにその継続に戻り値を渡します。 (use gauche.collection) ;; xsとysのすべての要素が等しければ#t, そうでなければ#f (define (vecto…

Gaucheに継続を「実装」する

http://inkar-us-i.hatenablog.com/entry/2016/09/01/200000inkar-us-i.hatenablog.com上の記事でしっかりしたモナドが作れたので、これを使って継続を実装します。 (define (cont-return x) (^(cont) (cont x))) (define (cont-bind x f) (^(cont) (x (^(xv…

Gaucheでモナド その3

http://inkar-us-i.hatenablog.com/entry/2016/08/27/200000inkar-us-i.hatenablog.com上の記事で作ったモナドはグローバルなスタックに現在のモナドを積むというものでしたので、mlet*の終了と同時に現在使用しているモナドに関する情報が消滅してしまい、…

Gaucheでモナド その2

inkar-us-i.hatenablog.comこのときはGauche歴半日くらいだったんで中置演算子とか定義してて微妙な感じの構文だったので、もう少しLispらしいモナドを書いてみました。 (define *monad-stack* '()) (define (push-monad! monad) (set! *monad-stack* (cons …

CPSとSSA

SSA(Static Single Assignment form, 静的単一代入)とは、一つの変数についての代入文がプログラム中で一度しか現れないような書き方のことを指します。 Scalaでいうと、すべての変数がvalになっているようなものですね。プログラムをこの形式に変換すること…

CPS変換についての覚え書き

CPS(継続渡しスタイル)とは、関数自体に「その後の処理」を引数として渡してしまうような書き方です。例: ;; 点(x . y)のノルムを求める (define (norm x y) (sqrt (+ (expt x 2) (expt y 2)))) (norm 1 1) ; => 1.414... ;; normのcps版 (define (norm/cps …

Ook!はSchemeである

Ook!のソースも、括弧で括ればただのS式ですよね。 ;; ook.scm (define *mem-size* 10000) (define *mem* (make-vector *mem-size* 0)) (define *ptr* 0) (define (inc-ptr!) (inc! *ptr*)) (define (dec-ptr!) (dec! *ptr*)) (define (inc-mem!) (inc! (~ *…

Gaucheのコメントいろいろ

なんか今更な気もしますが……。 行コメント セミコロン(;)から行末まではコメントとみなされます。セミコロンの数にも作法があるみたいです。 ;;; モジュール自体の説明とか、大きなコードブロックの説明 ;;; ;;; このモジュールはフィボナッチ数を生成するジ…

dynamic-wind

R5RSではdynamic-windという面白い関数が定義されています。 (dynamic-wind before thunk after) dynamic-windはまずbeforeを呼び出し、その次にthunkを、最後にafterを呼び出します。試しに以下のようなプログラムを実行してみましょう。 (define *outer-co…

Gaucheの複素数

gosh> 1+3i 1.0+3.0i gosh> i *** ERROR: unbound variable: i gosh> 2i *** ERROR: unbound variable: |2i| この書き方キモくないですか?複素数なんて特定の用途にしか使わないし、別に複素数リテラルとか用意しなくても gosh> (complex 3 5) 3.0+5.0i み…

Gaucheで手続き以外のオブジェクトも呼び出し可能にする

object-applyというメソッドを定義すると、手続き以外の任意のデータ型をあたかも関数であるかのように呼び出すことができます。 ;; (数 数)を(* 数 数)にする (define-method object-apply ((x <number>) (y <number>)) (* x y)) (define x 5) (3 x) ; => 15 以前説明したパ</number></number>…

Gaucheでパラメータを定義する

Gaucheには、グローバル変数の代わりに使用できるパラメータというオブジェクトが存在します。 パラメータの作成 (define x (make-parameter 3)) (x) ; => 3 (x 100) ; xの値を100に設定 (x) ; => 100 典型的な使い方としては、特定の関数が使用するデフォル…

Gaucheで優先度付きキュー

Gaucheの練習。実は何気に優先度付きキューの実装は初めてだったので、ツリーを配列で管理したほうが楽ということを知らずに若干手こずりました。 (define-class <priority-queue> () ((queue-vector :init-keyword :queue-vector :accessor queue-vector) (size :init-keywo</priority-queue>…

Gaucheでリスト内包表記

srfi-42には、リスト内包表記に関するマクロが定義されています。 (use srfi-42) ;; Haskellでいう ;; [i * 2 | i <- [0, 1, 2, 3, 4]] (list-ec (: i '(0 1 2 3 4)) (* i 2)) ; => (0 2 4 6 8) ;; iの値の範囲の指定もできる (list-ec (: i 0 5) (* i 2)) ;…

Gaucheで構造体を定義する

クラスほど大したことをしなくても良い場合、define-record-typeというマクロを使うことでより簡単な構造体を定義することができます。 (define-record-type point #t #t x y) (define p (make-point 3 4)) (point? p) ; => #t (point-x p) ; => 3 (point-y …

Gaucheで関数の実行時間を測定する

gauche.timeのtime-this関数を使うと、指定した関数の実行にどれくらい時間がかかるのかを測定することができます。 (time-this 実行回数 実行する関数) 例として、クラスを使った場合と、ベクタを適当にラップした型に対してアクセスするのとで、どの程度実…

Gaucheで多値を受け取る

複数の値を返す場合、それらの値をリストやペアにしてもよいのですが、通常、Schemeでは多値というものを利用します。 gosh> (min&max 2 4 3 1 5) 1 5 このmin&maxは、与えられた引数のうち最小値と最大値を返す多値関数です。他にも、商と余りを返すquotien…

Gaucheでデータ型の簡単な表現を定義する

例として、以下のようなクラスを用意します。 (define-class <person> () ((name :init-keyword :name) (age :init-keyword :age) (pref :init-keyword :pref))) このようなクラスのインスタンスを作成してみます。 (define taro (make <person> :name "Taro" :age 20 :pref </person></person>…

Gaucheでパーセプトロンを作った

Gaucheの練習。 パーセプトロンは簡単に作れる割に何となく学習してくれた感があって面白いです。 ;; perceptron.scm (use gauche.collection) ;; xがしきい値を超えているかを判定する関数 (define (sig x) (if (<= x 0) 0 1)) ;; 最終的な結果を出力するた…

named let

Gauche(に限らずほぼすべてのLISP)では、letは次のようなシンタックスシュガーとなっています。 (let ((hoge hoge-value) (fuga fuga-value)) (some-function hoge fuga)) ;; ↓展開後 ((lambda (hoge fuga) (some-function hoge fuga)) hoge-value fuga-valu…

Gaucheにおけるモナド的パターン

Maybeモナド的なパターンはand-let*を使うことで処理することができます。 (define (maybe-add maybe-a maybe-b) (and-let* ((a maybe-a) (b maybe-b)) (+ a b))) (maybe-add 3 2) ; => 5 (maybe-add #f 5) ; => #f (maybe-add 0 #f) ; => #f (maybe-add #f …

Gaucheでn-queen問題

Gaucheの練習。 任意のnに対してn-queen問題を総当りで解きます。 ;; 横x, 縦yマス目の位置のクイーンを(x . y)で表す (define (x queen) (car queen)) (define (y queen) (cdr queen)) (define (queen-at x y) (cons x y)) ;; queenがqueensのうち、1つでも…

Gaucheでパターンマッチ

util.matchモジュールを使えば、GaucheでもHaskellのようなパターンマッチを行うことができます。 リテラルに対するパターンマッチ リテラルに対するパターンは、そのリテラルを直接書けばOKです。 (use util.match) (define (fact n) (match n (0 1) (n (* …

ジェネリック関数を定義する

Gaucheでは、アドホックに多相を実現する手段としてジェネリック関数が用意されています。 ;; 足し算 (define (add x y) (+ x y)) (add 3 2) ; => 5 ;; ベクターも足し算したくなった (define (vector-add xs ys) (vector-map + xs ys)) (vector-add #(1 2 3…

Gaucheでクラスの作成

どうやらGaucheにもクラスは存在するようで、継承やアクセサの設定など、基本的なクラスに関する操作は行うことができます。 クラスの定義 (define-class <animal> ; クラス名 () ; 親クラスのリスト ()) ; スロット一覧 (define-class <person> (<animal>) ((name) (age))) インスタ</animal></person></animal>…

Gaucheでハノイの塔

Gaucheの練習。n個のハノイの塔の解き方を表示するプログラムです。 各板の大きさは数値として表され、数値が大きい方が大きい板となっています。 また、見やすさのため表示する際はリストの逆順(右のほうが塔の上側)となっています。 (use gauche.array) ;;…

継続でモナド

Haskellの>>=は実質継続渡しみたいなものなので、継続をうまいこと使えばSchemeにもモナドが実装できるはず(?)とりあえずMaybeモナドを実装してみました。 (define (empty-stack) '()) (define (empty-stack? stack) (null? stack)) (define-syntax push! …

Scheme始めました

某友人の影響でLispに目覚めてしまったので、とりあえずGaucheの勉強を始めることにしました。 (とは言っても授業でコンパイラ作ったりCPU作ったりしてて結構忙しいので、Gauche自体の勉強はかなりゆっくりになると思いますが)なぜ数あるLisp方言やScheme方…