Let's start Scheme

2016-04-20

言語レベル

(年に一回くらいこの手のことを書いてる気がしないでもないなぁ)

ある言語を話すことができるという理由で与えられるチャンスはそんなに多くないが、話せないから逃すチャンスというのは多々ある。これは英語に限ったことではなく、例えばここオランダでは募集要項にネイティブもしくはそれに準ずるオランダ語が話せること、ということが明確に書かれていることがある。逆に言うと、英語が話せればいいという職も多数ある。これが日本だと日本語は大前提になるのでExpatの多い国の特徴とも言えるのだろう。自分自身がどれくらい話せるのかとかを客観的に見たことがあまりないので、多少いろいろな角度からどの言語がどれくらいできるのか分析してみたくなった。

分析するにはある程度の基準がいる。とりあえず大きく5つのレベルに分けることにした。ただし、中間を表すために総数を20段階とし、5段階で区切るというようにする。例えば、日常会話はレベル5だが、ビジネスレベル(レベル10)に達していないが日常会話以上というのはレベル6から9の間といった具合である。以下はレベル:
  • レベル0:その言語を全く話せない
  • レベル5:日常会話レベル、かなり大変だがその言語で生活できる
  • レベル10:ビジネスレベル、職場でコミュニケーションができる
  • レベル15:高等教育レベル、日本なら高校卒業時の国語
  • レベル20:専門家レベル、この言語に関する知識で飯が食える
レベルの付け方に異論はあるかもしれないが、日本語だとTPOに関する場合分けが多いのである程度専門的な教育を受けていないとTPOにあった言葉遣い、例えば敬語等、ができないとしている。また、ビジネスレベルが低めなのは、少なくともオランダでは、仕事で使うツールとしての言語ではコミュニケーションができることが、当然だが、重要視され文法等の細かいことは必要以上に重要視されないというところからきている(もちろん文書などを書く際は別だが)。

さて、上記のレベルに自分の言語を当てはめてみる。何かしらのテストを受けて計測したというわけではないので、感覚的にという単なる目安である。
  • 日本語:レベル15(多分もう少し低いが、敬語とか忘れたし、日本の高校卒業してるということで)
  • 英語:レベル13 - 14(多少色眼鏡付きな気もするけど)
  • オランダ語:レベル4 - 6(一応生きていけるが辛い。仕事では使えない)
こんな感じだろう。言語の能力を語る上で語彙数も重要になる。ここによると、日本語の語彙は大学生レベルで4万5千~5万語らしい。一応大学出ているのでそれくらいとしておこう(正確に測るの怖い)。英語の語彙は数年前に測った時に1万2千~1万5千だったのでそうしておく(新聞を辞書なしで読めるレベル)。ちなみに、オランダに来た時点では5000程度だったので、そこから見ると随分増えたともいえる。オランダ語の語彙は知らない。2000ないかも。

全体の習熟度とすればこんな感じなんだろうけど、個別にみると意外と面白いことが分かる。例えばくしゃみをした人にかける言葉として英語では「Bless you」、オランダ語では「Gezondheid」がある。オランダに長く住んでいるので誰かがくしゃみをすると、たとえくしゃみをした人がオランダ語を話せなくても、「Gezondheid」というようになった。同様なものに「Alstublieft」もしくは「Alsjeblieft」がある。もう少し込み入った例だと、「Kan ik pinnen?」ある。これは「Can I use debit?」のオランダ語バージョンと思ってもらえばいいのだが、アメリカに行ったときとか、店員さんがオランダ語喋れない場合でもこれが勝手に出てくる(アメリカで出た際は流石に、「Kan ik,,, can I use credit card?」になったが)。特定のシチュエーションに於いてはアウトプットが最も多いものが勝手に口をついてくるみたいである。

言語の習熟度があがると、言語間の壁のようなものが薄くなる気がする。最近は日本語のやたらいっぱい母音を喋らないといけないというのが面倒に感じるのだが、これが時として悪い方向に働く。例えば日本人と話しているのに、ふっと英語になるとか。これが起きるときは大体分かってて、
  1. グループ内に日本人以外がいる
  2. カタカナ語を英語の発音で喋ってしまう
この二つが主な原因である。1は非常に簡単で、通訳してると出力方面がごちゃごちゃするという単なる混乱。2は、個人的には面白いと思っているのだが、英語の発音で自分の中のコンテキストが切り替わるというもの(これを回避するために日本語喋ってるときは頑なにカタカナ語で喋るのだが)。どうも、英語方面へのスイッチは緩いらしい。英語→日本語にシフトしたことはないのでそういうことだと思っている。母語が日英両方だった場合には起きないんだろうか?不思議である。

とりとめなく終わり。

2016-04-19

Inter-operable hidden binding

The subject might sound weird, but I couldn't find any better name. So please bare with it.

Problem

Suppose you have a situation that 2 macros need to refer the same implicitly bound variable. For example, consider define-generic and define-method; the declaration of generic function is done by define-generic, and adding definition to it is done by define-method. Now, you want to write it as simple as possible, so you've decided to use implicitly bound hashtable.
;; naive definition of define-generic (doesn't work)
(define-syntax define-generic-naive
  (syntax-rules ()
    ((_ name)
     (begin 
       (define implicit (make-eq-hashtable))
       (define (name . args)
          ;; lookup and execute
          )))))

(define-syntax define-method-naive
  (syntax-rules ()
    ((_ name formals body ...)
     (begin
       (define (real-proc . formals) body ...)
       (define dummy
         ;; oops, implicit can't be referred here!
         (hashtable-set! implicit 'name real-proc))))))
Now, your task is make this happen somewhat.

Passing explicitly

Taking this path isn't really what I want, but it's the only way to do it on R7RS.
(define-syntax define-generic-explicit
  (syntax-rules ()
    ((_ name table)
     (begin 
       (define table (make-eq-hashtable))
       (define (name . args)
          ;; lookup and execute
          )))))

(define-syntax define-method-naive
  (syntax-rules ()
    ((_ name table formals body ...)
     (begin
       (define (real-proc . formals) body ...)
       (define dummy
         (hashtable-set! table 'name real-proc))))))
The problem with this implementation is that you need to know the name of the shared bindings. It might be good for debugging or breaking, but you probably don't want to care about something only used internally.

Macro generating macro

If 2 macros cannot refer the variable defined in one of the macro, then make it in the one macro like this:
(define-syntax define-generic/defmethod
  (syntax-rules ()
    ((_ name method-name)
     (begin
       (define shared (make-eq-hashtable))
       (define (name . args) 
         ;; lookup and execute
         )
       (define-syntax method-name
         (syntax-rules ()
           ((_ name shared formals body (... ...))
            (begin
              (define (real-proc . formals) body (... ...))
              (define dummy 
                (hashtable-set! shared 'name real-proc))))))))))
It's probably better than explicitly passing, but it's rather ugly. The method definition should be more generic. In this implementation, the method definition belongs to specific generic function definition.

Identifier macro

If you are using R6RS, then syntax-case can handle non list macro (not sure how it should be called, but I say identifier macro). So if the name of generic function itself can be evaluated to implicit definition name, then we can share the binding by referring the name.
(define-syntax define-generic
  (syntax-rules ()
    ((_ name shared)
     (begin
       (define shared (make-eq-hashtable))
       (define (real-proc . args)
         ;; lookup
         )
       (define-syntax name
         (lambda (x)
           (syntax-case x ()
             ((_ args (... ...)) #'(real-proc args (... ...)))
             (k (identifier? #'k) #'shared))))))))

(define-syntax define-method
  (syntax-rules ()
    ((_ name formals body ...)
     (begin
       (define (real . formals) body ...)
       ;; method name should generic function name;
       ;; thus, it's an identifier macro to return
       ;; implicit table name.
       (define dummy (hashtable-set! name 'name real))))))
Better, at least for me. If I see it with half eye closed, then it looks like fake LISP-2.

Pitfalls I've got

I first thought that maybe I can use datum->syntax to create the same name; however, this wasn't a good idea. It is okay to if both generic function declaration and method definitions are in the same library; otherwise, you'd get a problem. Suppose you have a library (a) contains only define-generic and other library (b) contains define-method. Now, which template identifier you should use to generate the same name of the implicit binding? You need to use the identifier define-generic in the library (a), and it's impossible to use it in library (b). (This is the reason why I needed to write the version 2, macro generating macro.)

Conclusion

I don't have any intention to say, macro is the best, or something like that, but if something beyond procedure (in this case, emulating LISP-2, kind of), then it is rather necessary feature.

2016-04-15

Generic record copy

I've found a tweet that says R7RS define-record-type doesn't create copier (or copy constructor) by default. Well, I can imagine why it doesn't if I think of C++'s copy constructor (which I think very confusing and causing unexpected behaviour). And it's also context dependent what exactly copy means.

Now, if I just say like this, then it's not so fun. So let's write kind of generic copy procedure. Before that, here our definition of copy is deep copy. So it creates a new object without having the same object inside. So more like cloning.

Preparation

If it's generic, then it should work also builtin types. Generally, Scheme chose to have distinct procedures per types and what we want is one generic procedure. The very simple strategy would be dispatching. It might be convenient if users can specify how copy works per types. So the interface of copy procedure would look like this:
(define *copier-table* '())

(define (generic-copy obj)
  (cond ((assoc obj *copier-table* (lambda (x p) (p x))) =>
         (lambda (s) ((cdr s) obj)))
        ;; shallow copy, sort of
        (else obj)))

(define (register-copier! pred copier)
  (set! *copier-table* (cons (cons pred copier) *copier-table*)))
To register built-in types, we can do like this:
(register-copier! pair? list-copy)
(register-copier! vector? vector-copy)
(register-copier! string? string-copy)
(register-copier! bytevector? bytevector-copy)
Now, we have generic copy procedure for built-in types.

NB: list-copy and vector-copy doesn't consider the elements of copying object. If you want to follow the definition of copy here, you need to create own copy procedure.

Syntax

You know how define-record-type works, right? It needs to be fed name of constructors, predicate procedures. So doing the same for copy procedure. Let's call our brand new record definition syntax define-record-type/copy. It would look like this:
(define-record-type/copy pare (kons a d) pare? pare-copy
   (a kar)
   (d kdr))
The extra argument pare-copy is the procedure automatically generated by the macro.

Implementation strategy

Now, how can we implement it? The strategy I chose (and probably this is the only way to do it portably) is that:
  • Collect field value and order it by constructor tag
  • Create object by passing above value with specified constructor
  • Set field values of fields which are not listed on constructor
So my implementation is like this:
(define-syntax define-record-copier
  (syntax-rules ()
    ((define-record-copier "emit" name (ctr f ...) (acc ...) ((a m) ...))
     ;; now we have all information
     (define (name obj)
       (let ((c (ctr (acc obj) ...)))
         ;; mutate if mutators are defined, then we use it.
         ;; to make it simple, we do for all mutator. so some
         ;; of them are just useless.
         ;; FIXME this is not efficient.
         (m c (a obj)) ...
         c)))
    ((_ "mutator" name ctr accessor mutator ())
     (define-record-copier "emit" name ctr accessor mutator))
    ((_ "mutator" name ctr accessor (mutator* ...) ((f a) rest ...))
     (define-record-copier "mutator" name ctr accessor
       (mutator* ...) (rest ...)))
    ((_ "mutator" name ctr accessor (mutator* ...) ((f a m) rest ...))
     (define-record-copier "mutator" name ctr accessor
       (mutator* ... (a m)) (rest ...)))
    ((_ "collect" name ctr (acc ...) () (def* ...))
     (define-record-copier "mutator" name ctr (acc ...) ()(def* ...)))
    ((_ "collect" name ctr (acc ...) (field field* ...) (def* ...))
     (begin
       ;; this part is not R7RS portable since 'foo' doesn't have to be
       ;; renamed (right?). so some of implementation may raise an error
       ;; of redefinition (e.g. Foment)
       ;; however we can't use letrec-syntax because it creates a scope.
       ;; sucks...
       (define-syntax foo
         (syntax-rules (field)
           ((_ ?n ?c
               ((field ac . ignore) rest (... ...))
               (next (... ...))
               (src  (... ...)))
            (define-record-copier "collect" ?n ?c (acc ... ac)
              (next (... ...)) (src (... ...))))
           ((_ ?n ?c (_ rest (... ...)) (next (... ...)) (src (... ...)))
            (foo ?n ?c (rest (... ...)) (next (... ...)) (src (... ...))))))
       (foo name ctr (def* ...) (field* ...) (def* ...))))
    ((_ name ctr (ctr-field* ...) (field-def* ...))
     (define-record-copier "collect" name ctr
       () ;; accessor
       (ctr-field* ...)
       (field-def* ...)))))

(define-syntax define-record-type/copy
  (syntax-rules ()
    ((_ name (ctr field* ...) pred copier field-def* ...)
     (begin
       (define-record-type name (ctr field* ...) pred
         field-def* ...)
       (define-record-copier copier (ctr field* ...)
         (field* ...) (field-def* ...))))))
I usually use letrec-syntax to detect free identifier (well, it should be bound identifier but I don't think there's no way to do it in range of R7RS). But needed to use define-syntax (see comment).

Then you can use it like this:
(define-record-type/copy pare (kons a d) pare? pare-copy
   (a kar)
   (d kdr)
   (s pare-src pare-src-set!))

(register-copier! pare? pare-copy)
(let ((p (kons 'a 'b)))
  (pare-src-set! p '(src))
  (let ((c (generic-copy p)))
    (print (kar c))
    (print (kdr c))
    (print (pare-src c))))
(Write your own print procedure :P). The implementation is not efficient since we call mutator procedure no matter what. To make it efficient, you need to get mutators of which are not listed on constructor tags.

The whole scripts are here:

Conclusion

Use R6RS or SRFI-99.

2016-04-11

肉体改造部 第十四週

先週は何故か忘れた。

計量結果:

  • 体重: 70.9kg (-0.3kg)
  • 体脂肪率: 22.4% (+0.3%)
  • 筋肉率:43.2% (±0.0%)
最近胃袋が小くなったのか、一回に食べる量が減ったのだが、食べる回数(間食)が増えている気がする。Courseraのコースを取ったので(言い訳)筋トレをさぼりがちになっているというのもよろしくない。

2016-04-08

mod-exptの高速化

タイトルは大分嘘です。

Linux上での暗号ライブラリテストが以上に遅かった。他のOSでは問題ないのだが、Linuxだけ10倍以上遅い。何が遅いのかなぁと調べてみると、鍵対の生成が1024ビット程度でも3秒くらいかかっているというものだった。これはおかしいなぁと思っておもむろに鍵対生成をプロファイラにかけてみるとmod-exptが遅い。120回程度呼ばれて1500ms消費という感じであった。

この手続き自体は確かに重いものなのだが、どうもおかしい。以前(多分0.5.x辺り)ではそんなに時間がかかった記憶がない。つまりその辺から今までで入れた変更でLinuxのみが遅くなった可能性がある。記憶を辿ってみると確かにBignumの演算に手を入れた記憶があったので、とりあえずソースを覗いてみる。っが、特に不審な部分も見当たらない。Linux固有の何かを使ったものはないという意味でではあるが。

疑問を疑問のままにしておくのは今一気持ちが悪いので、Valgrindについてるcallgrindを使ってCレベルのプロファイルを取る。すると、mod-exptの処理自体は高速に終わっているという結果が取れた。っで、コールグラフのその下を見ると、スタック領域の割り出しの処理が異常に重たい。そういえば、Bignumの計算でスタックが溢れる不具合を直した際にそんな処理入れたなぁと思い、ダミーの値を返すようにしてSchemeのプロファイルを取る。3秒が30msになった。お前か・・・

具体的にはスタックベースを取得するのが異常に遅いっぽかった。そもそもスタックベースなど一回取得してしまえば変更されることはないはずなので毎回値を律儀に取得しにいくこともないよなぁと思いスレッドローカルな静的領域に格納するように変更。これだけで100倍の高速化に成功した。(実際は100倍の低速化が行われているので、元に戻っただけだが・・・)

ここからは(も?)与太話。
スタックベースの取得にはBoehmGCのGC_get_stack_baseを使っているのだが、LinuxとCygwinで100倍以上の差が付くのはなぜだろうと思いちょっと実装を覗いてみた。Linux(x86_64)では以下の処理を行う:
  1. pthread_getattr_npの呼び出し
  2. pthread_attr_getstackの呼び出し
  3. pthread_attr_destroyの呼び出し
それぞれの関数の呼び出しがどれくらい重いかはよく知らないが、1万回以上の呼び出しがあったのでそれなりにはかかるだろう。(Bignumの処理は大抵再帰なので再帰的にスタック領域の確認をするのだ。)

っで、Cygwinの実装を見てみた。
    GC_API int GC_CALL GC_get_stack_base(struct GC_stack_base *sb)
    {
      void * _tlsbase;

      __asm__ ("movl %%fs:4, %0"
               : "=r" (_tlsbase));
      sb -> mem_base = _tlsbase;
      return GC_SUCCESS;
    }
以上!そら速いわ。。。1万回呼び出されても誤差の範囲に収まるだろうなぁというのは想像に難くない。

特に何もなく、callgrindが便利だったというだけの話だったりはする。他のプロファイラと違いランタイムにリンクさせる必要ないというのはとてもありがたい。その分処理は劇的に遅くなるけど、的が絞れているならこれほど便利なものはないなぁと思ったのでした。

2016-04-01

プロセスとI/O

サーバーが正常に立ち上がったかどうかを確認するのに起動ログを見るか、実際にアクセスして動かないことを確認するしかないというのがだるくなった。なので、ファイルを監視しつつ失敗のキーワードがあれば通知するものを作ったのだが、どうもプロセスをデタッチすると何も出力されないことに気付いた。Sagittarius 0.7.2までは子プロセスの標準入出力は常にパイプが割り当てられるのだが、親プロセスが終了するとパイプから出力を読み取るプロセスがなくなるので何も出力されないという話だった。これでは不便だなぁと思い、えいや!っと出力先を制御できるようにしてみた。

こんな感じで使う。
(import (rnrs) (sagittarius process))
(let ((proc (make-process "foo" '("process")))
      (outfile "pout"))
  (process-call proc :output outfile))
これで、プロセスの標準出力はpoutというファイルになる。出力先を標準出力にしたいときは:stdoutを使う。もちろん、入力(:inputキーワード引数)とエラー出力(:errorキーワード引数)もサポートしている。便利手続きのcreate-processもこれを考慮するように変更したいが、まだしてない(こっちはパイプでも問題ないようにしか使ってないとも言う)。今のところ出力先ファイルは上書きででしか開けないが、必要があれば追記できるようにするかもしれない。

これ変更したのはいいけど、実際に通知を行うのにコンソールに垂れ流すと見落とすということで、notify-sendコマンド使ってデスクトップに通知するようにしたら、パイプ使ってても問題ないなくなった。変更自体は有用だと思うけど、最優先で変更したのはいいが必要なくなった子になってしまった。