Porting to BB10

A lot of Scheme implementations are ported to mobile device such as Gambit (iPhone), Mosh(Android), Gauche(iPhone, developing state though). Well, I'm feeling like it's time for me to ride the wave! Unfortunately, I have no developing environment neither iPhone nor Android but Blackberry. So I've so far decided to do with BB10 environment.

First of all, I needed to build Sagittarius on BB10 environment. This wasn't so difficult actually, I just needed to provide proper CMake tool chain configuration and some patches for Boehm GC (which only makes compiler satisfied currently though).

After that, I was trying to use Sagittarius as a library so that the application only needs to do eval and outputs the result. However this wasn't easy for me to handle standard I/Os. On BB10 environment, as far as I know, it is impossible to redirect keyboard input and standard output to GUI panels. So I thought I needed to create custom port to handle these things but I was too lazy to do it. So I've decided to use remote REPL which is already in library.

The basic idea I'm trying to do is really simple. Put all Sagittarius component into bar (Blackbarry ARchive, I guess) file and run the remote REPL as a child process. So what I need to implement is only send user input and receive the result. Then I'm facing a problem that for some reason sash is not executable. So I wrapped with shell which add permission of execution then run it. Now I've got core dump.

What am I missing?

Why I think macro is necessary for programming language!

DRUNKEN ARTICLE CAUTION: the article might not make any sense!

Macro, that is the last resort for all programmers. Macro, it's a sweet temptation. Macro...

Well, if you are familiar with macros and doing job with Java (or any other languages don't have macro), you must be really frustrated like me. I was thinking why I've got so irritated without macros and got a conclusion.

I assume all programmers want to write clean, fast and maintainable code without any inconsistency. Suppose you are a Java programmer and need to write really similar code multiple times and all of the classes are not the same region. In this case, I would create an abstract class or utility class to put all common process in. However I think it's ugly because the abstract class is not the behaviour of the derived class and utility class is not object oriented. Then what is the cleanest and consist way to resolve it? Copy&Paste? I have yet no solution.

If I'm using C++ then I could use template for that situation. It allow me to write common process without creating super class and inject dependency. If I can use Lisp for this situation, this is, I think, the best situation to use macro to avoid code duplication or writing ugly code.

What makes macro so powerful? Well, after writing this I felt I'm so stupid to write such obvious question. If you have written any code, then you must know how powerful modifying source code before it's compiled is. You can feel you became a god or so (not really). So far, I only know the language which allows you to do such free things is only Lisp. It has macro, read macro, reflection, aspect oriented and so on. (Well, even though I listed some other stuff but I'll focus on only macro.) Which other language can make own *syntax* within its language specification?

I know it has also some crappy things like it doesn't allow me to do much things within the specification (Scheme), not so portable between implementations (CL, Scheme) and all. And I think each language needed to decide not to have all *nice to have* features. So everything is trade off but if that's so, I would rather go more comfortable one and to me comfortable means freedom. More precisely, the language which can extend itself if I needed.

Yes, as I expect there is no conclusion nor sense in this article. Don't write something in drunk.

引数の上限

引数の上限を超えるとどうなるだろうと以下の記事を読んで気になった。

Chibi schemeの多値は単に多値オブジェクトで、call-with-values等で明示的に受け取らないと悲しいことになる。もっともChibi schemeのような実装にも、多値の長さに制限がないというメリットがある。nmoshは多値の長さ(= 事実上手続き引数の個数制限)が100程度に制限されている。現状のSchemeではこの制限をクエリする良い方法が無い。

引数個数制限はご無体な気もするが、Cの呼び出し規約のように関数呼び出しをスタック経由で行う規約は基本的にヒープサイズ制限よりもスタック長制限が先に来る。常識的に考えて固定arityの引数が100を越えることは無いので、可変arityの手続きの呼び出し規約をスタック渡しとオブジェクト渡しに分けるのは効果的かもしれない。
[scheme][nmosh] Unspecifiedの数とarity - .mjtの日記復帰計画

まぁスタックサイズに限界はあるわけだし、SEGVのが普通かなぁと思いつつ、以下のスクリプトを用意。

(import (rnrs) (only (srfi :1) iota))

(define-syntax apply-100000-values
  (lambda (x)
    (syntax-case x ()
      ((k)
       (with-syntax (((v ...) (datum->syntax #'k (iota 100000))))
         #'(list v ...))))))

(apply-100000-values)
(display 'ok) (newline)

以下はGauche用

(define-macro (apply-100000-values)
  `(list ,@(iota 100000)))
(apply-100000-values)
(apply-100000-values)
(print 'ok)

でっ、結果。(Chezはiotaを自前実装した。Chibiは低レベルマクロの使い方が分からないので割愛。)

Chez - ok
Gauche - SEGV
Mosh - ok
Sagittarius - 返ってこない(マクロの展開が終わらなかった)
Ypsilon - ok

意外だなぁと思ったのはMoshで、以前valuesに10000以上の個数をapplyするとSEGVるというバグを報告している経験からこけるものだと思っていた。(スタックを壊してる可能性があるので、他の操作をしたら予期しない場所でこける可能性はあるが。)

Chez及びYpsilonはどうして動いているのかは分からない。

Why does this call/cc go into infinite loop?

I've found interesting call/cc stuff in Chaton's Gauche room (this)

The code is this one;

(let ((x 0) (cc '())) 
  (set! x (+ x (call/cc (lambda (c) (set! cc c) (c 1)))))
  (if (< x 4) (cc 2) x))

As far as I investigate, Chez, Chicken, Mosh, Sagittarius and Ypsilon went infinite loop. Chibi and Gauche returned 5. Well I'm not a guy from continuation world so I can't say which is correct. However if the call/cc is located to left hand side, then it won't be infinite loop.

;; This returns 5
(let ((x 0) (cc '())) 
  (set! x (+ (call/cc (lambda (c) (set! cc c) (c 1))) x))
  (if (< x 4) (cc 2) x))

It seems the order of evaluation so I can probably get the answer.

I don't know about other implementations but Sagittarius so following guess is based on its call/cc implementation.

On Sagittarius, continuation is stack and it contains return address. So call/cc captures arguments and return address. Following is the image;

#first one
before call/cc
 +----------+
 |   cont   |
 +----------+ <- captured
 |   pc(+)  |
 +----------+
 |    x=1   | *1
 +----------+
 | pc(set!) |
 +----------+

#second one
before call/cc           after call/cc
 +----------+             +----------+
 |   cont   |             |    x     |   
 +----------+ <- captured +----------+
 |   pc(+)  |             |   c(1)   |
 +----------+             +----------+
 | pc(set!) |             |   pc(+)  |
 +----------+             +----------+
                          | pc(set!) |
                          +----------+

NOTE: pc is return address, cont is call/cc's argument. 
      Stack is growing upwards.

Well it's already obvious but I will describe just in case.The point is *1. The first one, the x is not a box means it's mere value (in this case 1). Then call/cc will capture the stack with the value. So the second call of (cc 2) will always be addition of 1 and 2. Thus it will never be greater than 4. On the other hand, the second case, stack doesn't have x yet so that VM will always compute what is inside of the box (x). Then (cc 2) will always compute the value of x and 2.

I think implementations caused infinite loop are using the similar method to implement call/cc as Sagittarius and Chibi and Gauche use something different. And again, I'm not the those guys from continuation world, so can't say which is correct or not but as my understanding both can be correct and this case is sort of edge case of call/cc.

Bignumの速度改善(調査編)

SBCLがGMPを使うようになったらしく、こんなツイートをもらった。

これで @tk_riple さんの第二次VS SBCL Bignum戦争開幕？
— llibra (@l_libra) July 5, 2013

期待されているなぁ・・・相手GMPだけど・・・

期待されると応えようともがく性分なので、とりあえず現状でどれくらいGMPと差があるのか適当にテストしてみることにした。GMPと言えばMoshが使っているのでここと比較。なぜか？機械語吐き出すSBCLと戦う前に同じバイトコードなScheme処理系のMoshを倒さないとオーバーヘッドの部分で確実に負けることが確定しているから。

テストコードは以下(ここのPython用のをSchemeに移植)：

(import (rnrs) (time))

(define (factorial n stop)
  (let loop ((n n) (o 1))
    (if (> n stop)
        (loop (- n 1) (* o n))
        o)))

(define (choose n k)
  (/ (factorial n k) (factorial (- n k) 0)))

(time (choose 50000 50))
#|
;; Mosh用timeライブラリ
;; time.scm
(library (time) (export time) (import (mosh)))
|#

以下が結果。

% time sash test.scm

;;  (choose 50000 50)
;;  6.536399841308594 real    11.13800 user    1.669000 sys
sash test.scm  11.17s user 1.76s system 194% cpu 6.661 total

% time mosh --loadpath=. test.scm

;;1.4351999759674072 real 1.264 user 0.172 sys
mosh --loadpath=. test.scm  1.28s user 0.20s system 99% cpu 1.482 total

まぁ、分かってはいたのだがここまで差があるのか・・・
SagittariusはBoehmGCがGC用スレッドを持ってるからRealとUser時間が倍違うのか？とりあえずReal時間だけ気にすることにする。

このベンチだと単純に乗算だけなんだけど、とりあえずそこからか・・・先は長そうである・・・

Loop macro for Scheme

The inspiration came from this article's comment: 10.times - Island Life

I'm not a CL user but I sometimes think CL's loop macro is really convenient if I want to write something really small. (I don't think I want to write big stuff with it. It's too complicated to me.) So why don't I write something looks like it?

Here is that something. It doesn't cover whole loop macro but some.

#!r6rs
(import (except (rnrs) for-each map) (only (srfi :1) iota for-each map))

(define-syntax %loop
  (syntax-rules (:for :in :do :repeat :collect)
    ((_ (vars ...) (body ...) op :for var :in l rest ...)
     (%loop ((var l) vars ...) (body ...) op rest ...))
    ((_ (vars ...) (body ...) op :repeat n rest ...)
     (%loop ((tmp (iota n)) vars ...) (body ...) op rest ...))
    ((_ (vars ...) (body ...) op :do expr rest ...)
     (%loop (vars ...) (expr body ...) for-each rest ...))
    ((_ (vars ...) (body ...) op :collect expr rest ...)
     (%loop (vars ...) (expr body ...) map rest ...))
    ;; last
    ;; do trivial case first
    ((_ () (body ...) op)
     ;; infinite loop
     (do () (#f) body ...))
    ((_ ((var init) ...) (body ...) op)
     (op (lambda (var ...) body ...) init ...))))

(define-syntax loop
  (syntax-rules ()
    ((_ clause ...)
     (%loop () () #f clause ...))))

#|
(loop :for i :in '(1 2 3 10) 
      :for j :in '(4 5 6)
      :do (begin (display i) (display j) (newline)))

(loop :repeat 10 :do (begin (display 'ok) (newline)))

(display
 (loop :for i :in '(1 2 3 10) 
       :for j :in '(4 5 6)
       :collect (+ i j))) (newline)
;; (loop :do (begin (display 'ok) (newline)))
|#

I'm not sure if this is useful or not and I don't want to go deep inside of the crucial loop macro specification either, though :-)

NOTE: I've tested above code Racket (plt-r6rs), Mosh, Ypsilon and Sagittarius but Ypsilon raises an exception when the given list length are not the same.