FC2ブログ
--.--
--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

12.08
Tue
ningleつかっててhttpsで通信させたいなーとおもって,
clackのコードとか見てたんですけど、少なくともバックエンドにhunchentootを使ってる時は簡単にできました。

こんな感じです。

clackupするときに、秘密鍵と証明書の設定をすればいいだけです。

ほかの、サーバをバックエンドに使う時とかどうなのかなーとか
おもってたらclackのissueで議論されてました。

HTTPS support via SSL


スポンサーサイト
comment 0 trackback 0
07.25
Sat
もう半年も時間が経ってしまっていたみたいなんですが、
TAPLを読んでた時に作っていた静的型付けで型推論のある関数型言語について書きます。

リポジトリ: https://github.com/moratori/protolang

実装に関してはとても単純です。
構文解析をyaccでやって、Commmon Lispのオブジェクトに変換します。
で、それに対して型推論と静的型検査をしてエラーがなければ、Common Lispのソースコードに変換します。
なのでコンパイルとか実行時の話は全部Common Lisp側の処理系(SBCLを意図)に任せられます。

使い方とかですが
SBCLをインストールしquicklispを入れてください
~/.quicklisp/local-projects とかで
git clone https://github.com/moratori/protolang.git してください.

あとはSBCLのREPLで

(ql:quickload :protolang)
(protolang::main)
してください

そうすると以下のようにつかえるとおもいます

>>> 1+2
3 : Integer

>>> [x] -> x+1
([x] -> +[x,1]) : (Integer -> Integer)

>>> def fact [n] -> if (n == 0) 1 n * fact[n-1]
fact : (Integer -> Integer)

>>> def search[f,n] -> if f[n] n search[f,n+1]
search : ((Integer -> Boolean) -> (Integer -> Integer))

>>> fact[search[[x] -> (x % 23) == 4 , 30]]
30414093201713378043612608166064768844377641568960512000000000000 : Integer


これを元にまともに使える言語を作りたいなーとかおもってるんですけどいつになるかわからないです笑

comment 0 trackback 0
12.22
Mon
配列のハッシュ値ってどうやって求めるんだろうなーって思って研究室の先輩に相談したら

Javaの実装を教えてくれました。



ということで前々回の記事(ハッシュテーブル)の最後では配列をリストに変換してsxhashしていたのですが
(理由などは前々回の記事参照)
これを改善してみます。

hash関数を以下のように書き換えます



で実行してみると(solve-toplevelを呼ぶ)


Evaluation took:
1.878 seconds of real time
1.872118 seconds of total run time (1.804113 user, 0.068005 system)
[ Run times consist of 0.500 seconds GC time, and 1.373 seconds non-GC time. ]
99.68% CPU
102 lambdas converted
4,688,367,618 processor cycles
535,618,928 bytes consed

SEARCHED STATE: 181439
SORTEST: 31

-- PATH --


8 6 7
2 5 4
3 0 1

8 6 7
2 0 4
3 5 1


めっちゃ速くなりました!!
comment 0 trackback 0
12.13
Sat
PLOKAMIはCommon Lispでパケットのキャプチャを行うためのpcapのLispバインドです。
PLOKAMI - Common Lisp PCAP Interface
quicklispで簡単に導入できます。

これで簡単なスニッファをつくってみます。



ethernetとIPのヘッダあわせて34byte分キャプチャしてbufferという配列に格納します。

送信元と宛先IPアドレス合わせて8byte分をbufferからもってきて表示しています

1418446039 - from: 192.168.1.47 to: 8.8.8.8
1418446039 - from: 8.8.8.8 to: 192.168.1.47
1418446040 - from: 192.168.1.47 to: 8.8.8.8
1418446040 - from: 8.8.8.8 to: 192.168.1.47
1418446041 - from: 192.168.1.47 to: 8.8.8.8
1418446041 - from: 8.8.8.8 to: 192.168.1.47

実行にはroot権限ひつようなので注意

comment 0 trackback 0
12.08
Mon
Lispのハッシュテーブル使ってて困ったことがあったので書きます。

まずハッシュテーブルとはキーと値の組みを効率的に扱うためのデータ構造で、
リストの配列とかで実装されていることが多いです。

基本的にハッシュテーブルの参照・追加は定数時間でできます。
(後述するようにハッシュコードが頻繁に衝突しなければ)

配列Arrayとそのサイズをnと考えます。大きいほどハッシュ値の衝突は起こりづらくなるはずです。
まずエントリーを追加する時はキーのハッシュ値を求めます.(これはとなります)
そのハッシュ値をインデックスとして配列Arrayを参照し、そこに値をぶち込みます。
ハッシュ値が衝突していれば既に配列に値が埋まっているのでリストとしてくっつけていきます。
参照を行う時もキーのハッシュ値を求めて配列を参照します。

ここで重要なのがハッシュ値を求める関数が高速であり、なるべく衝突をおこさない値を返すことです。

という事を踏まえてこないだ問題のおきたコードをはります。
ハッシュテーブルの使い方がおかしいのでいつまでたっても終わりません.



なにをしているコードなのかというと8パズルを解くやつです。
構造体で各盤面の状態を定義して幅優先探索で8パズルを解きます。
スロットには盤面を表す大きさ9の配列とかを持っています。

幅優先探索なので重複した状態を探索しないようにするために各状態(構造体)をキーとするハッシュテーブルを使って
記録しているのですが上手く機能してないのでいつまでたっても終わりません。

上のsolveをちょっと変えたのが以下です。



ハッシュテーブルのキーに構造体でなく、盤面を表す配列を指定しています。

このようにしてやるとうまく行きます。sbcl1.2.6の環境で実行してみると


Evaluation took:
2.069 seconds of real time
2.068129 seconds of total run time (1.984124 user, 0.084005 system)
[ Run times consist of 0.504 seconds GC time, and 1.565 seconds non-GC time. ]
99.95% CPU
102 lambdas converted
5,165,940,091 processor cycles
535,698,896 bytes consed

SEARCHED STATE: 181439
SORTEST: 31

-- PATH --

8 6 7
2 5 4
3 0 1

8 6 7
2 0 4
3 5 1

8 0 7
2 6 4
3 5 1

0 8 7
2 6 4
3 5 1

2 8 7
0 6 4
3 5 1

2 8 7
3 6 4
0 5 1

2 8 7
3 6 4
5 0 1

2 8 7
3 6 4
5 1 0

2 8 7
3 6 0
5 1 4

2 8 0
3 6 7
5 1 4

2 0 8
3 6 7
5 1 4

2 6 8
3 0 7
5 1 4

2 6 8
0 3 7
5 1 4

2 6 8
5 3 7
0 1 4

2 6 8
5 3 7
1 0 4

2 6 8
5 3 7
1 4 0

2 6 8
5 3 0
1 4 7

2 6 0
5 3 8
1 4 7

2 0 6
5 3 8
1 4 7

2 3 6
5 0 8
1 4 7

2 3 6
0 5 8
1 4 7

2 3 6
1 5 8
0 4 7

2 3 6
1 5 8
4 0 7

2 3 6
1 5 8
4 7 0

2 3 6
1 5 0
4 7 8

2 3 0
1 5 6
4 7 8

2 0 3
1 5 6
4 7 8

0 2 3
1 5 6
4 7 8

1 2 3
0 5 6
4 7 8

1 2 3
4 5 6
0 7 8

1 2 3
4 5 6
7 0 8

1 2 3
4 5 6
7 8 0


初めのsolveにめちゃくちゃ時間がかかる感じなのは構造体のハッシュ値を出した時に衝突が起こって
それのために時間が掛かっているのではないかと思いました。(リストの線形探索になってしまっているとか開番地法に時間がかかるとか?.処理系の実装がどうなっているのかわからないですが)

なので、sxhashというオブジェクトのハッシュ値を求めてくれるLispの関数を用いて構造体のハッシュ値を求めてたのが以下です。



適当に作った構造体の全てのハッシュ値が一致します。
だから始めの構造体をキーに取るバージョンだと上手くいかないのかと思ったのですが、
これは配列でもこうなります。つまり、



となります。

なので改善したsolveのコードがなぜうまく動いてるのかという話になるのですが、
そもそもハッシュコードを取るのにsxhashは使われていないのかな?とかいろいろ考えていました。

その時にみつけたやつWhy does `sxhash` return a constant for all structs?


Franzの人の回答が貼ってあるっぽいですが、make-hash-tableのhash-functionキーにhash関数を渡してやればいいとか書いて有りますね.処理系依存っぽいですけど。

でSBCLにもあるのか調べてみたらありました。(describe 'make-hash-table)してみると

:HASH-FUNCTION
If NIL (the default), a hash function based on the TEST argument is used,
which then must be one of the standardized hash table test functions, or
one for which a default hash function has been defined using
SB-EXT:DEFINE-HASH-TABLE-TEST. If HASH-FUNCTION is specified, the TEST
argument can be any two argument predicate consistent with it. The
HASH-FUNCTION is expected to return a non-negative fixnum hash code.


ありました。

そうですよね。普通他の言語とかでハッシュテーブル使って任意のオブジェクトをキーにしたいならhashメソッドとか実装されてないとおかしいですもんね。

でこれのラッパーもありました。CL-CUSTOM-HASH-TABLE

これを使って書いてみたのが以下。



実行してみる


Evaluation took:
5.627 seconds of real time
5.620351 seconds of total run time (5.492343 user, 0.128008 system)
[ Run times consist of 0.616 seconds GC time, and 5.005 seconds non-GC time. ]
99.88% CPU
102 lambdas converted
14,043,350,512 processor cycles
841,386,704 bytes consed

SEARCHED STATE: 181439
SORTEST: 31

-- PATH --


8 6 7
2 5 4
3 0 1

8 6 7
2 0 4
3 5 1

〜省略〜


coerceするのが若干ネックになっているのか、遅いですがうまくできました。

配列をキーに取ったときに上手くいったのは謎ですね...







comment 0 trackback 0
back-to-top
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。