自作のLisp処理系に並列構文を導入した話

# 概要
Easy-ISLispに並列計算を導入しようとしています。まずはインタプリタにおいて並列構文を追加し、マルチスレッドにより動作、並列計算について一定の成果を得ましたので、後日のために記録に残します。


# スレッドセーフ
C言語ライブラリのPthreadを用いました。eval、applyといった主要部分をスレッドセーフにする必要があります。スタック、局所環境をスレッドごとに持たせる必要があります。また、セルへのアクセスは競合を防止する必要があります。

# 並列構文
pletという構文を採用しました。Common-Lispの並列ライブラリにあったアイディアを拝借しました。次の例はpletを使ってフィボナッチ数を計算するコードです。

```lisp
;;; test paralell

(defun fib (n)
    (plet ((a (fib1 (- n 1)))
           (b (fib1 (- n 2)))) (+ a b)))

(defun fib1 (n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (t (+ (fib1 (- n 1)) (fib1 (- n 2))))))

```

# データ構造
局所環境は連想リストで実装されています。これは従来epという変数にその先頭アドレスを保持していました。このepをスレッドごとに管理するために配列としました。

ep[0] メインスレッド
ep[1] サブスレッド１
ep[2] サブスレッド２
ep[3] サブスレッド３


同様にスタックポインタであるspも配列としました。またスタックも多次元配列としました。

stck[STCKSIZE][PARASIZE]

push、popは次のようになっています。

```c
/* for stack to store ep(environment) */
int push(int pt, int th)
{
    if (sp[th] >= STACKSIZE)
	error(STACK_OVERF, "push", NIL);

    stack[sp[th]++][th] = pt;
    return (T);
}

int pop(int th)
{
    if (sp[th] <= 0)
	error(STACK_UNDERF, "pop", NIL);
    return (stack[--sp[th]][th]);
}

```

eval、applyなど主要な関数にはスレッド番号を表す引数を追加しました。スレッドでの起動時にその番号（１~4）を与えることによりスレッドセーフを実現しています。

# 競合回避
自由リストからセルを取り出してくるときにスレッド間の競合が生じる可能性があります。mutexで競合を回避しています。freshcellという関数がセル供給を担当しています。コンカレントGCにも対応するために状況に応じて動作を切り替えています。


```c
int freshcell(void)
{
    int res;

    if (!concurrent_flag) {
	pthread_mutex_lock(&mutex);
	res = hp;
	hp = GET_CDR(hp);
	SET_CDR(res, 0);
	pthread_mutex_unlock(&mutex);
	fc--;
	if (fc <= 50 && !handling_resource_err) {
	    handling_resource_err = true;
	    error(RESOURCE_ERR, "M&S freshcell", NIL);
	}
    } else if (concurrent_stop_flag) {
	/* while remarking stop the world */
	pthread_mutex_lock(&mutex);
	while (concurrent_stop_flag) {
	    pthread_mutex_unlock(&mutex);
	    pthread_mutex_lock(&mutex);
	}
	pthread_mutex_unlock(&mutex);
	res = hp;
	hp = GET_CDR(hp);
	SET_CDR(res, 0);
	fc--;

    } else if (concurrent_sweep_flag && rc > 50) {
	/* while concurrent-sweeping set flag USE */
	res = hp;
	//pthread_mutex_lock(&mutex);
	hp = GET_CDR(hp);
	//pthread_mutex_unlock(&mutex); 
	SET_CDR(res, 0);
	rc--;
    } else if (concurrent_flag && rc > 50) {
	res = hp;
	hp = GET_CDR(hp);
	SET_CDR(res, 0);
	rc--;
	remark[remark_pt++] = res;
    } else {
	pthread_join(concurrent_thread, NULL);
	res = hp;
	hp = GET_CDR(hp);
	SET_CDR(res, 0);
	fc--;
    }

    return (res);
}

```

setqのように破壊的代入をする場合にも競合防止が必要ですが、今のところ未対応です。

# 実装
スレッドセーフにするのはなかなか困難なことでした。evalを頂点にして配下にある関数を漏れなくスレッド単位で切り分ける必要がありました。ChatGPTに相談しながらなんとかスレッドセーフになりpletが機能するようになりました。pletのコードは下記のとおりです。

```c
struct para {
    int in;
    int num;
    int out;
};


void *plet(void *arg);
void *plet(void *arg)
{

    struct para *pd = (struct para *) arg;

    parallel_flag = 1;
    pd->out = eval(pd->in, pd->num);
    parallel_flag = 0;
    return NULL;
}

int f_plet(int arglist)
{
    int arg1, arg2, temp, i ,res;

    arg1 = car(arglist);
    arg2 = cdr(arglist);
	if (length(arglist) == 0)
	error(WRONG_ARGS, "plet", arglist);
	if (length(arg1) > PARASIZE)
	error(WRONG_ARGS, "plet", arg1); 
    if (!listp(arg1))
	error(IMPROPER_ARGS, "plet", arg1);
    temp = arg1;
    while (!nullp(temp)) {
	int temparg1;

	temparg1 = car(car(temp));
	if (improper_list_p(car(temp)))
	    error(IMPROPER_ARGS, "plet", car(temp));
	if (length(car(temp)) != 2)
	    error(IMPROPER_ARGS, "plet", car(temp));
	if (!symbolp(temparg1))
	    error(NOT_SYM, "plet", temparg1);
	if (temparg1 == T || temparg1 == NIL
	    || temparg1 == make_sym("*PI*")
	    || temparg1 == make_sym("*MOST-POSITIVE-FLOAT*")
	    || temparg1 == make_sym("*MOST-NEGATIVE-FLOAT*"))
	    error(WRONG_ARGS, "plet", arg1);
	if (STRING_REF(temparg1, 0) == ':'
	    || STRING_REF(temparg1, 0) == '&')
	    error(WRONG_ARGS, "plet", arg1);

	temp = cdr(temp);
    }


    pthread_t t[PARASIZE];
    struct para d[PARASIZE];

	temp = arg1;
	i = 0;
	while (!nullp(temp)){
    d[i].in = cadr(car(temp));
    d[i].num = i+1;
    ep[i+1] = ep[i];
    pthread_create(&t[i], NULL, plet, &d[i]);
	temp = cdr(temp);
	i++;
	}

	temp = arg1;
	i = 0;
	while (!nullp(temp)){
    pthread_join(t[i], NULL);
    temp = cdr(temp);
	i++;
	}
	temp = arg1;
	i = 0;
	while (!nullp(temp)){
    add_lex_env(car(car(temp)), d[i].out, 0);
	temp = cdr(temp);
	i++;
	}
	while (arg2 != NIL) {
	shelter_push(arg2, 0);
	res = eval(car(arg2), 0);
	shelter_pop(0);
	arg2 = cdr(arg2);
    }
    return (res);
}

```

# 計測
２５のフィボナッチ数程度ならインタプリタでも並列計算できるようになりました。並列処理をすれば実行時間は短縮されるばずです。以下はWindows　WSL Ubuntuでの計測です。

```
Easy-ISLisp Ver3.14
> (load "./tests/para.lsp")
T
> (time (fib 25))
Elapsed Time(second)=1.017071
<undef>
> (time (fib1 25))
Elapsed Time(second)=1.492650
<undef>
> 

```

並列処理の方が逐次に比較しておおよそ2/3程度の実行時間となっています。並列処理の効果がでてきます。他にラズパイ４００でも同様な結果でした。しかし、デスクトップLinuxMINTで実行したところ、並列の方が2倍ほご時間がかかっていました。スレッドに分けるためのオーバーヘッドが大きいようです。


# 将来展望
ver4に向けて並列処理部分を充実させます。具体的には下記のことを予定しています。

### コンパイラでの並列実行コードの生成

### コンカレントGCとの共存

### pmapcarのようなmap型関数の並列化