2016-12-11

syntax-rulesの仕様を読んで確認した

r7rsのsyntax-rulesのパターンの部分の仕様を読んで確認する。(vectorは省く)

とる形は、以下の4つ(Pはパターンで、[ellipsis]は、0個以上の繰り返し)
1. (P1 ... Pn )
2. (P1 ... Pn . Pn+1)
3. (P1 ... Pk Pe [ellipsis] Pm+1 ... Pn)
4. (P1 ... Pk Pe [ellipsis] Pm+1 ... pn . Px )

つまり、
1.真性リストで[ellipsis]を含まない。
2.非真性リストで[ellipsis]を含まない。
3.真性リストで[ellipsis]を含む。
4.非真性リストで[ellipsis]を含む。
ということか。

1

(define-syntax check-1
  (syntax-rules () ((_ (a b c d e)) (quote (a b c d e)))))


(display (check-1 (1 2 3 4 5)))(newline) ;(1 2 3 4 5)

真性リストで同じ要素数のものだけしかマッチしない。
特になし

2

(define-syntax check-2
  (syntax-rules () ((_ (a b . c))(quote (a b c)))))


(display (check-2 (1 2 )))(newline);(1 2 ())
(display (check-2 (1 2 3 )))(newline);(1 2 (3))
(display (check-2 (1 2 3 4 5)))(newline);(1 2 (3 4 5))
(display (check-2 (1 2 . 3)))(newline);(1 2 3)

非真性、真性どちらでもよく、左から順にマッチさせていき、のこりを最後のcdr部にマッチさせる。
これも、特になし。

3

(define-syntax check-3
  (syntax-rules () ((_ (a b ... c d ))(quote (a b ... c d )))))

(display (check-3 (1 2 3 4 5)))(newline);(1 2 3 4 5)
(display (check-3 (1 2 3)))(newline);(1 2 3)

真性リストで、[ellipsis]の左側と右側をマッチさせて、残りを[ellipsis]の所にマッチさせる。
これも、特になし。

4-1

全部、パターン変数の場合。

(define-syntax check-4a
  (syntax-rules () ((_ (a b ... c . d))(quote (b ...  d  )))))

(display (check-4a (1 2 3  4 5)))(newline);(2 3 4 ())
(display (check-4a (1 2 3 4 . 5)))(newline);(2 3 5)
(display (check-4a (1 2 3)))(newline);(2 ())

処理系によっては、動かなかったり、明らかに間違った結果がでたりした。
saggitarius0.6.11やgauche0.9.5の結果だと、
非真性リストを入れると、末尾cdr同士、それ以外同士でマッチングし、
真性リストを入れると、patternの末尾cdrにnullがマッチして、全部その左側にマッチする。

4-2

定数を入れた場合。

(define-syntax check-4b
  (syntax-rules () ((_ (1 2 ... 3 . d))(quote d ))))

(print (check-4b (1 2 2 2 3 . 4 )));4

真性リストを入力した場合、最後のcdr要素(null)だけが、Pxにマッチするので、
Pnまでうまくマッチできそうなケースでもだめだね。

2016-11-11

ウサギとカメ(循環リスト)

連結リストで循環しているかどうか、どこで循環が始まっているのかを検出する。
正式には、Floyd's cycle-finding algorithmと呼ぶらしい。
証明は省くが、だいたい↓のような手順

循環判定

・セルを2つづつ移動するのをウサギ、1つづつ移動するのをカメとして、1ステップずつシミュレートする。
・ウサギとカメが出会う(同じセルにいる)場合そのリストは循環している。

循環場所の検出

・ウサギを最初のセルにもどし、ウサギのスピードを1にする。
・再度シミュレートして、ウサギとカメが出会ったセルが循環のスタート地点。

コード

hare:ウサギ
tortoise:カメ

is_circle_listは、循環リストなら循環スタートのセルを返し、そうでなければfalseを返す。

var Cell = function(a,b){
    this.car = a;
    this.cdr = b;
}

var is_circle_list = function(ls){
    var hare = ls;
    var tortoise = ls;
    while (true){
        if (hare.cdr == null || hare.cdr.cdr == null){
            return false;
        }
        hare = hare.cdr.cdr;
        tortoise = tortoise.cdr;

        if (hare == tortoise){
            break;
        }
    }
    
    hare = ls;
    while (true){
        if (hare == tortoise){
            break;
        }
        hare = hare.cdr;
        tortoise = tortoise.cdr;
    }
    return hare;
}

2016-11-10

schemeのパラメータオブジェクトの使い方を調べた。

r7rsでは標準。

パラメータオブジェクトは、値を束縛して動的存続期間中にその値を変更できるオブジェクト。
make-parameterで、パラメータオブジェクトを作れる。

(define foo (make-parameter 123))
(foo);123

パラメータオブジェクトに値を渡した時の挙動は処理系依存とされているが、 CHICKEN,picrinなど、値を変更するケースが多い。

(foo);123
(foo 100)
(foo);100

parameterizeを使うと、その中でのパラメータオブジェクトが返す値を変更できる。

(foo);123
(parameterize ((foo 10)) (foo));10
(foo);123

make-parameterに2つ引数(init converter)を渡すと、初期化や値の変更時に converterを通した値がセットされる。

(define boo (make-parameter 123 (lambda (x) (* x x ))))
(boo);15129
(boo 3);9

2016-10-16

python-mechanizeでログインするぞ。

mechanizeは、スクレイピングとか用のweb操作ライブラリ。
標準ではないのでpip等でinstall。

で、ためしにログイン画面をつくってmechanizeでアクセスする。
ログイン画面はこんなかんじ。

index.html

<html>
    <head>
    </head>
    <body>
        <form name="LOGIN" action="/cgi-bin/form_test.py">
            USERNAME <input type="text" name="USERNAME"></input><br>
            PASSWORD <input type="text" name="PASSWORD"></input><br>
            <input type="submit"></input>
        </form>
        <div id="foo"></div>

    </body>
</html>

cgi-bin/form_test.py

#!/usr/bin/env python
import cgi

print "Content-Type: text/html\n\n"

print "<html><body>"

form = cgi.FieldStorage()

name = form["USERNAME"].value
password = form["PASSWORD"].value
if name == "user" and password == "pass":
    print "OK"
else:
    print "ERROR"


print "</body></html>"

ユーザ名がuserで、パスワードがpassだとOK、それ以外だとERRORと出力するようにした。
クライアントは以下

#coding:utf-8
import mechanize
URL = "http://127.0.0.1:8000"

#ブラウザオブジェクトを生成
br = mechanize.Browser()
#robot.txtを無視
br.set_handle_robots(False)

#アクセス
br.open(URL)

#form情報を作る
br.select_form(name="LOGIN")
br["USERNAME"] = "user"
br["PASSWORD"] = "pass"

#submit
ret = br.submit()

#帰ってきたhtmlを見る
print ret.read()

以上。

2016-10-07

schemeのdatum label

datum labelを使うとschemeの循環構造を表記できる。

(define x (list 1 2 3 ))
(set-cdr! (cddr x) x)
;#0=(1 2 3 . #0#)

(define y (list 4 x 6))
(set-cdr! (cddr y) y)
;#0=(4 #1=(1 2 3 . #1#) 6 . #0#)


(define z (quote #0=(1 2 . #0#)))
;#0=(1 2 . #0#)

2016-09-23

openboxにターミナル起動キーバインドを追加しました。

ctrl+alt+tでターミナルエミュレータを起動するようにする。
~/.config/openbox/rc.xmlにキーバインド関係の設定がある。

<keybord>内に以下のような感じで書き加える。
こちらの環境では、lilytermを使っている。

    <keybind key="C-A-t">
        <action name="Execute">
            <command>lilyterm</command>
        </action>
    </keybind>

修飾キーの略語は、
C:Control
A:Alt
S:Shift
W:windows key
のような感じ。

2016-09-21

gentooにtint2をいれました。

openboxのお供にする。

インストール

ランチャー機能がある0.12以上を入れる。

emerge --ask xdotool   
emerge --ask "=x11-misc/tint2-0.12.3"

コンフィグを修正

~/.config/tint2/tint2rcを編集する。
初期状態では、そんざいしないアプリケーションへのリンクとかがあるので、
#Launcharの#launcher_item_app から始まるものをすべてコメントアウトする。

アプリケーションをメニュに加える

.desktopファイルを追加するだけでよい。
例えば、forefox-binだと、
.desktopファイルをapplications下において、

cp /usr/portage/www-client/firefox-bin/files/firefox-bin.desktop /usr/share/applications/

コンフィグファイルに追加する。

launcher_item_app = /usr/share/applications/firefox-bin.desktop

おしまい。
f:id:niyarin-man:20160921171606j:plain