Composable continuation (1)

After 2 weeks of fighting, I've finished implementing composable continuation. This is my memo of how I understand composable continuation and what I've done to implement it.

How it works

If I google it, I can find a lot of (maybe not so many) articles and/or papers regarding composable continuation. All those papers are, of course, very abstracted, means it wasn't intuitive for me. (I'm not good at those symbols, unfortunately.) So, let me illustrate a bit more concretely.

CAVEAT: This is how I understand and how it works on Sagittarius.

First, Sagittarius is a VM machine using stack as its call frames. The same model as previous article. When call/cc is called, then the call frames are move to the heap with the same structure. It'd be like this:

~ before call/cc ~
 [ call frame 0] <-- VM's cont register
 [ call frame 1]
 [ call frame 2]
  :
 [ call frame n]
 
~ after call/cc ~
 [ call frame 0] -> [ call frame 1] -> [ call frame 2] -..> [ call frame n]

This only means, stack call frames became heap call frames. When the captured continuation is invoked, then it'd simply replaces the VM's current cont frame to captured one.

[ call frame 0] -> [ call frame 1] -> [ call frame 2] -..> [ call frame n]
~~~~~~~~~~~~~~~
VM's cont register

When the heap call frame is returned, then the call frame will be poped. Then the saved arguments will be pushed into the bottom of the stack, like this:

[ call frame 0] -> [ call frame 1] -> [ call frame 2] -..> [ call frame n]
~~~~~~~~~~~~~~~
This is poped

[ arg n ] <- stack pointer
 :
[ arg 1 ]
[ arg 0 ] <- frame pointer = bottom of stack
~~~~~~~~~~
These arguments are form [ call frame 1 ]

In this way, the local argument reference doesn't require special handling, but just refering the same relative location. (i.e. LREF 0 always refers *fp, LREF 1 is *(fp + 1).)

Now, we have composable continuation. A composable continuation captures the call frames up until the specified prompt. So, conceptionally, the captured call frames are like this:

~ before call/comp ~
  [ call frame 0 ]
  [ call frame 1 ]
  [   prompt 0   ] <- capture until here
  [ call frame 2 ]
   :
  [ call frame n ]
 
~ captured continuation ~
[ call frame 0 ] -> [ call frame 1 ] -> [ prompt 0 ]

And when the captured continuation is invoked, then call frames will be like this.

~ before invocation ~
  [ call frame a ]
  [ call frame b ]
      :
  [ call frame z ]

captured continuation: [ call frame 0] -> [ call frame 1] -> [ prompt 0 ]

~ after invocation ~
  [ call frame 0 ]
  [ call frame 1 ]
  [   prompt 0   ]
  [ call frame a ]
  [ call frame b ]
      :
  [ call frame z ]

So, the captured continuation will be stack up on top of the current call frames. This means, it returns to the same location from the invocation. For example, this shows 1,3,2,3, instead of 1,3,

(call-with-continuation-prompt
 (lambda ()
   (call-with-composable-continuation
    (lambda (k)
      (display "1,")
      (k 1)
      (display "2")))
   (display "3,")))

If you replace call-with-composable-continuation with call/cc, then it shows 1,3,.

Closest prompt

When it comes with abort-current-continuation, composable continuations are not that much intuitive. See the script below:

;; invoking captured k means calling the thunk passed as an argument
(let ((k (call-with-continuation-prompt ;; (1)
          (lambda ()
            ((call-with-composable-continuation
              (lambda (k) (lambda () k))))))))
  (call-with-continuation-prompt ;; (2)
   (lambda ()
     (+ 99 (k (lambda () (abort-current-continuation 
                          (default-continuation-prompt-tag)
                          8)))))
   (default-continuation-prompt-tag)
   values))

Initially, I thought this would be like this cont frame transition.

prompt/handler notation, #f means no handler

~ capture ~ 
[ cont frame 0 ]
[  prompt/#f   ] <- default prompt tag + #f

~ invocation ~
[  cont frame 0 ]
[   prompt/#f   ]
[  cont frame 1 ] <- (+ 99 ...)
[ prompt/values ] <- default prompt tag + values

So, my mind said this should throw an error. But it ends up returning 8. Why?

The prompet inserted by the continuation invocation should come after the one inserted by the call-with-continuation-prompt (2). If I only see the call frame stack, the prompt/#f is the closest, but because it's composable continuation, the stacked up prompt must be after.

;; prompt order
~ my intuition ~
[ prompt/#f ] -> [ prompt/values ]

~ how it should be ~
[ prompt/values ] -> [ prompt/#f ]

This means, I need to manage the prompt insertion order separately as well.

It's getting longer than I though, so to be continnued.

Continuation prompt

Since long time ago, I was thinking if Sagittarius can have some nice async/await equivalent things. I'm using Java/Kotlin at my work, occasionally TypeScript, they, execpt Java, have nice async/await thing. So, I asked my new shiny friends, Copilot or ChatGPT, if it's possible to implement it with continuation. And the answer was yes, also it'd be cleaner if I use delimited continuation.

Now, I remember that SRFI-226 defines delimited continuation. And I vaguely remember one of the discussions saying it can be implemented with continuation prommpt and composable continuation. I've been avoiding to touching the continuation, but it seems it's time for me to have some courage.

With my shallow understanding, composable continuation requires continuation prompt, so I decided to implement continuation prompt first. A continuation prompt can be implemented as a boundary frame. Currently, Sagittarius's call frame is implementented like this:

[  cont 0  ] <-- top
[  cont 1  ]
[  cont 2  ]
[ boundary ] <-- when C calling Scheme procedure
[  cont 3  ]
  :
[  cont n  ] <-- bottom

Now, I should be able to implement prompt as an extra frame like this:

[  cont 0  ] <-- top
[  cont 1  ]
[  cont 2  ]
[  prompt  ] <-- prompt frame
[  cont 3  ]
  :
[  cont n  ] <-- bottom

There's a very good reason why I should do this. Sagittarius' compiler optimises let with very advanced (I want to believe) way. It takes frame size into account. This means, I can't add extra field into the call frame structure. Because of this reason, I can't annotate the call frame with prompt tag by adding an extra struct member. The boundary frame is already using one of the members to hold a mark. In other words, I can use one member to hold prompt information.

Now, inserting prompt seems easy job, then next step, abort-current-continuation. It seems this is required to implement delimited continuation. Reading the document doen't really click what it does. So checked the behaviour with Racket. Started with the very simple example below.

(call-with-continuation-prompt
  (lambda ()
    (abort-current-continuation (default-continuation-prompt-tag) 1)
    (display 'not-reached) (newline))
  (default-continuation-prompt-tag)
  values)
;; -> 1

My easily get hallucinated brain understood that abort-current-continuation aborts the current continuation up to the specified prompt tag and invokes the abort-handler... this is what the document says... If I draw a diagram then it looks like this

[  cont 0  ] <-- abort/cc
[  cont 1  ]
[  cont 2  ]
[  prompt  ] <-- target   == after  ==>  ;; the rest of the call frame
[  cont 3  ]					         [  cont 3  ]
  :								           :
[  cont n  ]           			         [  cont n  ]

Okay, it looks easy enough to do it.

(Until I fell into a lots of pitfalls...)

Memo: Socket selector on Windows

Sagittarius has (net socket) library which defines socket selector. A socket selector takes arbitary number of sockets and waits until one or more of the given sockets are readable. The concept was there quit a long time, however it wasn't really working on Windows unfortunately. Now, I put some effort to make it work as I expected.

The requirement of the socket selector is below:

• Interruptible
• No limits of the number of sockets
• Timeout on socket level and procedure call itself

Windows has nice functions to archive it. Only I couldn't find anything similar to my solution, so it might worth to share.

The below piece of code shows essence of the actual implementation. It doesn't handle timeout for the sake of simplicity. What it does is the following;

• Associstes the given sockets to the given event
• Waits the event
• Once an event is received, then associates the sockets to other event, this time an event per socket
• Check if the socket is readable (passing 0 timeout value)
• If it's readable, add to the list

It doesn't do much, the only important part is checking by batch due to the limitation of WSA_MAXIMUM_WAIT_EVENTS.

#include <winsock2.h>
#include <windows.h>

typedef struct socket_list_rec
{
  SOCKET socket;
  struct socket_list_rec *next;        /* NULL = term */
} socket_list_t;

socket_list_t * selector_wait(int n, SOCKET *sockets, WSAEVENT event)
{
  socket_list_t *list = NULL;
  for (int i = 0; i < n; i++) {
    WSAEventSelect(sockets[i], event, FD_READ | FD_OOB);
  }
  int r = WSAWaitForMultipleEvents(1, event, FALSE, INFINITE, FALSE);
  if (r == WSA_WAIT_FAILED) {
    return NULL;
  }
  if (r == WSA_WAIT_EVENT_0) {
    WSAResetEvent(event);
    for (int i = 0; i < n; i++) {
      WSAEventSelect(sockets[i], NULL, 0);
    }
    int rem = (n % WSA_MAXIMUM_WAIT_EVENTS) > 0 ? 1 : 0;
    int batch = (n / WSA_MAXIMUM_WAIT_EVENTS) + rem;
    int size = min(n, WSA_MAXIMUM_WAIT_EVENTS);
    WSAEVENT events[WSA_MAXIMUM_WAIT_EVENTS];
    for (int i = 0; i < size; i++) {
      events[i] = WSACreateEvent();
    }
    for (int i = 0; i < batch; i++) {
      int count = 0;
      int offset = i * WSA_MAXIMUM_WAIT_EVENTS;
      for (int j = 0; j < size; j++) {
        int m = offset + j;
        if (m < n) {
          WSAEventSelect(sockets[m], events[j], FD_READ | FD_OOB);
          count++;
        } else {
          break;
        }
      }
      int r = WSAWaitForMultipleEvents(count, events, FALSE, 0, FALSE);
      if (r != WSA_WAIT_FAILED && r != WSA_WAIT_TIMEOUT) {
        WSANETWORKEVENTS ne;
        for (int j = 0; j < count; j++) {
          if (WSAEnumNetworkEvents(sockets[offset + j], events[j], &ne) == 0) {
            if ((ne.lNetworkEvents & (FD_READ | FD_OOB)) != 0) {
              socket_list_t *n = (socket_list_t *)malloc(sizeof(socket_list_t));
              n->socket = sockets[offset + j];
              n->next = list;
              list = n;
            }
          }
        }
      }
    }
    for (int i = 0; i < n; i++) WSAEventSelect(sockets[i], NULL, 0);
    for (int i = 0; i < size; i++) WSACloseEvent(events[i]);
  }
  return list;
}

The above code creates events per call, this might be too expensive and wasteful. The actual code pre-allocates the event array during the initialisation.

cond-expand enchancement

When I'm writing a library or tools, I usually write them working on the current release version of Sagittarius, unless R6RS portable one. However, I often want to use the development branch version of the features as well, especially with the new procedures.

Since R7RS, cond-expand has the library clause, which checks if the library specified in the clause exists or not. If you are handling multiple implementations, this feature is useful, for example, if one of the implementations doesn't support SRFI-1, then you can write a compatible layer easily. However, if there's a new procedure and/or macro added in a new version of Sagittarius, this library clause doesn't work as I want. To resolve this dilemma, I've added the new version clause to cond-expand.

The version clause can be used to cooperate among Sagittarius versions. The below example shows how to split the process between 0.9.12 and earlier.

(import (rnrs)
        (sagittarius) ;; for cond-expand
        (sagittarius crypto keys))

(cond-expand
 ((and cond-expand.version (version (>= "0.9.12")))
  ;; secp160r1 is supported since 0.9.12
  (generate-key-pair *key:ecdsa*
                     :ec-parameter *ec-parameter:secp160r1*))
 (else
  ;; default ECDSA key pair for earlier version
  (generate-key-pair *key:ecdsa*)))

The cond-expand.version is required to make it work on Sagittarius version earlier than 0.9.12.

I personally think this feature should be incorporated into R7RS but I'm too lazy to write a SRFI.

OAS stub

ここ数ヶ月Kotlinを書いていたのだが、なんとなく形になったしちょっと紹介記事を書こうかなぁと。

Swagger/OpenAPI Specificationは多分誰でも知っているだろう。Microserviceな流れになっていた前職で10を超えるバックエンドサービスに接続する必要があったのだが、毎回stubを書くのは馬鹿らしいと思い提供されているAPI定義(たいていSwaggerかOAS)を読み込んだらリクエストの検査からレスポンスの生成をやってくれないかなぁと思って作ったものの焼き増しがOAS stubになる。実際にこのアプリはかなり便利で、恐ろしく時間の短縮が可能だった^*1ので多分OSSにしても需要があるんじゃないかなぁと。

基本的な使用方法は今のところ二つ、Spring Bootアプリとしてスタンドアローンにするか、テスト用フレームワークとして使うか。

スタンドアローンアプリ

スタンドアローンなアプリを作るにはまず以下の依存関係をpom.xmlに入れる。ちなみにSpring Bootは3.1.xが必須。2.x.x系では動かないので注意。

<dependency>
    <groupId>io.github.ktakashi.oas.stub.spring</groupId>
    <artifactId>oas-stub-spring-boot-starter-web</artifactId>
    <version>1.2.0</version>
</dependency>

一応BOMもあるのでそっちがいいならBOMをio.github.ktakashi.oas.stub:oas-stub-bom:1.2.0をdependencyManagementに入れると良い。この依存を入れるとAutoConfigurationが勝手に動くので、後は普通にSpring Bootアプリケーションを書くだけ。こんな感じ。

package com.example;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

@SpringBootApplication
public class ExampleApplication {
    public static void main(String[] args) {
        SpringApplication.run(ExampleApplication.class, args);
    }
}

これでドキュメントに書いてあるエンドポイントが有効になる。アノテーションを明示的につけるようにした方がいいかなぁとも思ったけど、あまりメリットがない気がしたのでこの形。

一応、ブートストラップ時にクラスパスから読み取って設定するということも可能。これはそのうちドキュメントに書く。

テストフレームワーク

BDDを使って結合テスト的なテストをビルド時にやるのはとても効率が良いので是非やるべき^*2、ということで結合テスト用のフレームワーク的なものもある。まずは以下の依存をpom.xmlに入れる。

<dependency>
    <groupId>io.github.ktakashi.oas.stub.spring</groupId>
    <artifactId>oas-stub-spring-boot-starter-test</artifactId>
    <version>1.2.0</version>
    <scope>test</test>
</dependency>

っで、Spring Bootテストに以下のアノテーションとサービスを追加する。

package com.example;

import io.github.ktakashi.oas.test.OasStubTestService;
import io.github.ktakashi.oas.test.server.AutoConfigureOasStubServer;
import org.springframework.boot.test.context.SpringBootTest;

@SpringBootTest
@AutoConfigureOasStubServer
public class ExampleApplicationTest {
    @Autowired
    private OasStubTestService oasStubTestService; 
}

OasStubTestServiceはテスト用の便利サービスでAPIを増やしたり呼び出し回数を検査したりできる。機能的にはまだ足りないかなぁと思っているが、適宜追加する方向にしている。

これでどういうことができるのかというのは多分例を見た方が早いと思うので、そっちを参照してもらう感じで。Cucumber使ったBBDだからそんなに癖とかないだろう、きっと。

WireMock？

WireMockはよくお世話になったんだけど、モック書くのが結構面倒だったり細かくやるとWireMock自体を知らないといけなかったりで、ちょっと面倒があったりする。例えば、レスポンスは署名が付いてくるとかだと静的なファイルだけでは無理なんだけど、これを解決するのに結構面倒だった。っで、この辺をプラグイン^*3で解決してしまおうというのもこのアプリの特徴で、Groovyが書ければかなり柔軟に色々できたりする。

まとめ

OASファイルをアップロードすればそのままスタブができるというアプリの紹介。

今のところ自分が入りそうな機能しか入っていないので、使ってもらってフィードバックがあるととても嬉しい。

---

[1]: それまではスタブ一個追加するのに一週間とかかかってたのが、5分で済むようになった。

[2]: BDDいいよ、ビジネスアプリならユニットテストよりまずこっちを入れるべき。

[3]: まぁ、このプラグイン機構はセキュリティとか一切考慮していないので、このアプリを本番環境に置くのは全くお勧めしてない。

転職して一ヶ月で異動、または履歴書に前職の経歴を書く功罪

転職して一ヶ月で異動になった話。ちょっと個人的にツボったので後で振り返るように書いておく。

2023年9月から銀行Iで働くことになった。前職である銀行Rではオランダで最も使われているペイメントスキームの一つであるiDealのメンテナンス及びメジャーバージョンアップに多大に貢献した。当然ではあるが、履歴書にそのことを載せていた。ちなみに、銀行Iはオランダ最大手の銀行かつ銀行Rの競合他社であるが、iDealのメジャーバージョンアップ(以降iDeal 2.0)において銀行Rの後塵を配していた。自慢になるが、銀行RがiDeal 2.0において他の追随を許さない勢いで成功を収めたのは、僕の功績が大きい*1。ちなみに銀行Iに転職する前の面接では一応そのことを仄めかしていたが、大きくは取り上げなかった。個人的にiDeal 2.0に関わりたくなかったし*2。

転職直後の月曜日に別のチームのマネージャからなぜか「coffee catch up」というタイトルのミーティングが飛んでくる。そして、その直後のマネージャから同様の招待がその前日にスケージュールされる。ぶっちゃけ、なんだこれ状態に陥る。よくわからんなぁと思いつつ、マネージャからの話を聞くと、

• iDeal 2.0を仕切っているマネージャからであること
• 要は引き抜きを行いたいということ

という話であった。いや、まだ開発環境のセットアップすら終わってませんが。銀行Rを辞める直前くらいに元同僚と、銀行IはiDeal 2.0で悲惨な結果を残したからうっかりすると引き抜かれるんじゃね？みたいな笑い話をしていたのだが、これが冗談でなくった瞬間であった。

っで、当日のミーティング。基本的には顔合わせみたいな意味合いだと言われて臨んだのだが、そもそも別のチームのマネージャと顔合わせを自分のマネージャより前にするとか今までやったことないよなぁ、と思いつつ話を聞く。要点は、まぁ上記にプラスしてEPIのチームが結成されるがどう？みたいな話。iDeal 2.0には難色を示しつつ、EPIは興味あると答える。実際興味あるし。この時すでに、半々くらいでiDeal 2.0を手伝ってほしいみたいなことを言われる。いや、まだ開発環境すら…

一週間後、部長みたいな地位の人と顔合わせさせられる。この時点で異動ケテーイ。ぶっちゃけ笑うしかないスピード感。この時に、どうやら7、8月に既に取り合いが発生していたという話を聞く。どうも、僕の履歴書をiDeal 2.0やらEPIやらのマネージャが見たらしい。そして、銀行Rでの立役者ならこっちでも同じことやってほしいみたいな話になったとかなんとか。

その後、マネージャとフィードバック面接をした際に、前職の経歴が履歴書に載せてなかったらという無理ゲーな不満を言われるなどされる。いや、それなかったら多分歯牙にもかかってないと思うの。ちなみに、チームメンバーの一人はこの決定に大激怒で、これが続くなら辞めるとまで言っている。色々秘密裏に行われた感じはあるから、わからんでもない。

*1: なんだけど、当時のマネージャは全くそれを認めずあまつさえ、僕いなくてもいいんじゃね？という扱いをしてくれた。これが決め手となり転職を決意。ぶっちゃけ、どんなけ功績立てても評価(主に給料アップとか)されないならいる意味ないしね。

*2: 24/7かつ稼働率99.5%が義務付けられていたので、結構夜中の電話とかくらうのですよ。

英語の勉強のお供に？

同僚のスクリーンセーバが英単語とその意味を表示するやつなのをみて、こういうのあると便利かなぁと思い始めたのでなんとなく似た感じのものを作ってみた。まぁそこまで似ているというほどでもないのだが、起動するとコンソールに単語の意味と例文をなんちゃってカード形式で表示するというもの。ちなみに単語はUrban Dictionaryの非公式APIを使って取得していたりするので、このスクリプトがある日突然使えなくなっても泣かないようにしないといけない。

Gistに載せたのはコピペしたものなので、色がついてたり太字になってたり下線がついてたりするのが見えないのが残念。実際にどのように見えるのかは実行すればわかるということで。

別段特筆すべきこともないのだが、これを書くために使ったライブラリ達(当然だが全部Sagittariusに付属している)

• (net http-client): モダン(なつもり)な非同期HTTPライブラリ
• (text json jmespath): JMESPathライブラリ
• (rfc uri-template): RFC 6570準拠なURIテンプレートライブラリ
• (sagittarius combinators): コンビネーターライブラリ
• (util concurrent): 並列処理ライブラリ

処理のために書いた小道具とかもライブラリにするといいのかもと思いつつ(非同期http-getとか、コンソールの色付けとか)あまりいいアイデアもないのでとりあえず放置。