リリカル☆Lisp開発日記

富山に行ってきました。

そこで素敵なお買い物カードを手に入れました。池田市のカードもこれくらい頑張ってほしい。

卒論出した。

あとは発表だけ。

「C言語のsetjmpとlongjmpがあればスレッドは作れる」
という話を聞いたので実際にやってみました。
まずは、完成品の使用例から。

#include <stdio.h>
#include <stdlib.h>
#include "ahothread.h"

void f1(void *args)
{
  int i, j;
  char *str = (char*)args;
  for (i=0; i<3; i++) {
    puts(str);
    for (j=0; j<10000000; j+= 1 + rand()%2);
  }
}

int main(int argc, char **argv)
{
  int t1, t2;
  ahothread_init();
  t1 = ahothread_create(f1, "aho");
  t2 = ahothread_create(f1, "baka");
  ahothread_join(t1);
  ahothread_join(t2);
  return 0;
}

ahoとbakaが交互に出ます。多分。
ループの中でrand()を呼ぶことにより時間稼ぎをしているので、
環境によっては交互じゃない可能性もあります。

次は、スレッドの中身で、もっとも重要な部分。

int ahothread_create(void (*func)(void*), void *args)
{
  int id = search_free_thread();
  thread_table[id].state = ALIVE;
  if (setjmp(thread_table[current_thread].jb) == 0) {
    if (id > current_thread) {
      alloca((id-current_thread) * FRAME_SIZE);
    }
    else {
      assert(0);
    }
    current_thread = id;
    func(args);
  }
  return id;
}

void ahothread_yield()
{
  if (setjmp(thread_table[current_thread].jb) == 0) {
    int next = search_alive_thread();
    current_thread = next;
    longjmp(thread_table[next].jb, 1);
  }
}

ahothread_createは、setjmpで現在の状態を記憶し、
allocaでスタックポインタを適当に押し上げた後に、(別のスレッドとして)目的の関数を呼びます。
ahothread_yieldは、setjmpで現在の状態を記憶し、
適当な(多くの場合、現在とは別の)スレッドを探し、longjmpで制御を移します。
ahothread_yieldを定期的に呼ぶことにより、実行するスレッドが定期的に切り替わります。

最後に、全部のソースを載せておきますが、
かなりやっつけで作ったのでバグが沢山埋もれている可能性があります。

#include <stdlib.h>
#include <setjmp.h>
#include <assert.h>
#include <signal.h>
#include <sys/time.h>

#define MAX_THREAD 32
#define FRAME_SIZE 10240

#define DEAD 0
#define ALIVE 1
#define JOIN 2

struct thread_data {
  jmp_buf jb;
  int state;
  int wait;
};

struct thread_data thread_table[MAX_THREAD];
static int current_thread = 0;
static int num_thread = 1;

static int search_alive_thread()
{
  int i;
  for (i=current_thread+1; i<num_thread; i++) {
    if (thread_table[i].state == ALIVE) {
      return i;
    }
  }
  for (i=0; i<=current_thread; i++) {
    if (thread_table[i].state == ALIVE) {
      return i;
    }
  }
  assert(0);
  return -1;
}

static int search_free_thread()
{
  int i = num_thread++;
  assert(i < MAX_THREAD);
  return i;
}

static int search_join_thread(int id)
{
  int i;
  for (i=0; i<num_thread; i++) {
    if (thread_table[i].state == JOIN &&
        thread_table[i].wait == id) {
      return i;
    }
  }
  return -1;
}

void ahothread_yield()
{
  if (setjmp(thread_table[current_thread].jb) == 0) {
    int next = search_alive_thread();
    current_thread = next;
    longjmp(thread_table[next].jb, 1);
  }
}

void ahothread_join(int id)
{
  if (thread_table[id].state != DEAD) {
    thread_table[current_thread].state = JOIN;
    thread_table[current_thread].wait = id;
    ahothread_yield();
  }
}
void ahothread_exit()
{
  int join;
  if (current_thread == 0) {
    exit(0);
  }
  join = search_join_thread(current_thread);
  if (join != -1) {
    thread_table[join].state = ALIVE;
  }
  thread_table[current_thread].state = DEAD;
  ahothread_yield();
}

int ahothread_create(void (*func)(void*), void *args)
{
  int id = search_free_thread();
  thread_table[id].state = ALIVE;
  if (setjmp(thread_table[current_thread].jb) == 0) {
    if (id > current_thread) {
      alloca((id-current_thread) * FRAME_SIZE);
    }
    else {
      assert(0);
    }
    current_thread = id;
    func(args);
  }
  return id;
}

static void ahothread_handler(int sig)
{
  if (num_thread > 1) {
    ahothread_yield();
  }
}

void ahothread_init()
{
  struct sigaction sa = {
    .sa_handler = ahothread_handler,
    .sa_flags = SA_RESTART
  };
  struct itimerval it = {};
  thread_table[0].state = ALIVE;
  it.it_interval.tv_sec = 0;
  it.it_interval.tv_usec = 100000;
  it.it_value = it.it_interval;
  sigemptyset(&sa.sa_mask);
  sigaction(SIGALRM, &sa, NULL);
  setitimer(ITIMER_REAL, &it, 0);
}

もう2月になってしまった。

卒論の締め切りが迫ってきた。

お久しぶりです。

もうすぐ、このサイトができてから3年になります。

適当に今年の出来事を10個集めてみました。

ポケステでLispが動いた
去年の年末から今年の年始にかけてポケステ向けのLispインタプリタを作りました。

フルマラソン走った
翌日の筋肉痛が凄かったです。タイムが遅かったのが残念。

Mac Book買った
非常に使いやすいです。いい買い物をした。

自転車で琵琶湖一周
大体時速20kmをキープし続けることができました。次走るときはもう少し良い自転車で走りたい。

マンガで分かるLispがたくさん
最近停滞気味ですが、最後まで続けたいと思います。

BiwaSchemeでゲーム作った
Schemeでブラウザ向けのゲームが作れるというのは面白いですね。

院試受かった
院試が近い時期に彦根まで自転車でひこねのよいにゃんこのグッツを買いにいったりしましたが、
試験日やその前日にカツ丼やチキンカツ定食を食べたおかげか無事合格できました。

CLでJavaのアセンブラ/逆アセンブラを作った
CLでプログラムを書くのも大分慣れてきたおかげか、比較的楽に書くことができました。

cl-openglで遊んだ
こいうプログラムを書くのは楽しいですね。

今年1年振り返ってみたけど、ろくなことをやってない
特に書くことがなかったので再帰的なリンクを張っておきます。

メモリたくさん欲しいです(Yet Another Ranha)
を読んで、私もオシオキしてみることにしました。

画像が小さくて良く見えませんが、4人が水泳大会の順位を言っていて、
そのなかで一人だけ嘘をついているのでその人を見つけ出すみたいです。
(順位も求めるみたいですが、誰が嘘をついているか分かれば順位は自明なので、
　順位は表示したりしていません。)

私はranhaさんのように変態紳士では無いので、素直にPrologを使いました。
処理系はSWI-Prolog。

;; 二つの集合が等しいか
set_eq([], []).
set_eq([X|Xs], Y) :- member(X, Y), delete(Y, X, Z), set_eq(Xs, Z).
;; 4人が別々の順位になるか
rank(X,Y,Z,W) :- set_eq([X,Y,Z,W], [1,2,3,4]).
;; それぞれの言い分
ayu(1).
ayu(2).
suzu(1).
suzu(2).
naru(N, S) :- N < S.
kotori(1).
;; オシオキされる人
oshioki(ayu)   :- suzu(S), kotori(K), rank(_,S,N,K), naru(N, S).
oshioki(suzu)  :- ayu(A), kotori(K), rank(A,S,N,K), naru(N, S).
oshioki(naru)  :- ayu(A), suzu(S), kotori(K), rank(A,S,_,K).
oshioki(kotori):- ayu(A), suzu(S), rank(A,S,N,_), naru(N, S).

で、動かしてみたら、誰をオシオキしたらいいのかすぐに分かります。

?- oshioki(X).
X = suzu

SWI-Prologのdeleteの引数が想像と逆ですこしハマりました。
それにしてもあまりきれいじゃないですね。
もう少しうまく書けないものか。

Movable TypeからWordPressに移行しました。

動作が明らかに速くなって快適です。

気がついたらブログを1ヶ月以上放置していた。

なんか色々あった。マンガで分かるLispのトップページに英語訳が付いたり。

ものすごく適当に書いてもそれっぽく動く。cl-opengl凄い。
Common Lispでゲームを作るのは案外簡単な気がしてきた。

背景の写真は滋賀県の某所で撮ったものです。
画面のキャプチャにはCopernicusを使用しました。
ただ、Mac Bookのスペックの問題か、秒間2フレームほどでしか撮影できなかったので、
cl-openglのプログラムの方をゆっくり動かし、撮影した動画をiMovieで早送りしました。