scheme GP

「やりたいこと」

高速なschemeで遺伝的プログラミング(GP)を実行させる。

「そのために必要なこと」

~~schemeで遺伝的プログラムが可能か調査する。~~

　　　http://www.geneticprogramming.com/Tutorial/　＞できそう

~~線形論理（？）に従ったschemeを実装する。~~ ＞外してそう

　　　~~Lively Linear Lispを翻訳してデータ構造の策定の参考になるかならないか判断する。~~　＞外してる

GC不要なLispが遺伝的プログラミングを高速に実行するために有用か調査する。

着手　　Automatic Memory Management in newLISPを翻訳してのGC不要なメモリ管理が使えるか判断する。

仕様書を書く。

着手　　外部使用を書く
　　　　　　とりあえずは、GPに必要な関数のみに限定する。
　　　　　　データ構造とアルゴリズムを考える。

2006-07-23

Abstract

scheme

線形論理は、ガーベジ・コレクションの問題の1つの解決策として提案されており、より多くの関数型言語内の効率的な「update-in-place」能力を提供しています。
線形論理はアクセスのしやすさを持ちます。そしてその結果、コピーは明示的な分配されたメモリの並列処理に、より適切な機械的メタファーを提供します。
しかし、線形論理における分割の不足は、それ自身の著しい非能率を導入するかもしれません。

私たちは非線形の論理に関する恒常的要因の中を走るLinear Lispと呼ばれる線形論理の効率的な実現を示します。
このLinear LispはRPLACXに操作を許して、非線形のLispと同じくらい安全にストレージを管理しますが、ガベージコレクターを必要としません。
割り当てを提示するが、共有を提示しないので、それは関数型言語と命令的な言語の間の中間層を占めます。
Linear Lisp マシンは連結/グラフリダクションマシンのコピーとガーベージコレクション問題なしで連結/グラフリダクションマシンと同じ能力の多くを提供します。

2006-07-23

Introduction

scheme

借り手も貸し手もない;
ローンはたびたびローンそれ自体と友人の両方を失うから… [Shakespeare, Hamlet, I. iii 75]

共有がコピーの代わりになるので、データ構造の共有は効率的である場合があります。しかし、それは誰がそれらの管理に責任を負うかに関して曖昧さを作成します。
この曖昧さは静的に[Barth77][Bloss89][Chase87][Hederman88][Inoue88][Jones89][Ruggieri88]を削除するのが難しい。また、私たちは、静止の共有分析(純粋な関数型言語用のさえ)がそうかもしれない[Baker90]を示しました、MLタイプ推論と同じくらい困難な、それは指数関数的な[Mairson90]であると知られています。
[脚注2]私たちはここに次のことを示します。共有に関連しているあいまいさを無くす必要があるというよりむしろ、共有の偶発的(副次的)利点を活用するシステムであり、共有が効率を提供することができるのを示します。

線形理論は、陽に共有、もしくはコピーされるべきでないオブジェクトに対処する方法としてジラード[Girard87]によって発明されました。
Wadler[Wadler91]は、単一性参照を備えたデータ構造の使用がガーベジ・コレクションの問題を回避し、かつO(1)配列最新版に備えるためにカウントする方法を提案しました。
Wakeling[Wakeling91]は線形論理をインプリメントし、コピー要求がそのインプリメントでは困難であり、非常に遅いことを知りました。
私たちのLinear Lisp マシンは、単一参照がカウントデータ構造であるWakelingのマシンより効率的にインプリメントし、従来の連結/グラフリダクションマシンのインプリメントより「競争力があります。」

2006-07-23

A Linear Lisp Machine

scheme

このセクションの中で、私たちは、全てのconsセルがちょうど1の参照カウントを持っているLisp Machine のオートマトン理論モデル(それはデータ構造がすべて木であることを暗示する)を導入します――なぜなら、それらは共有またはサイクルを持っていません。例えば、私たちの線形のリスプでは、NREVERSEはREVERSEに同形です。

私たちの機械は、consセルにアトムかポインターのいずれかを固定することができる有限状態コントロールおよびnポインターレジスタから成ります。
アトムはNILかシンボルのいずれかです。
レジスタの1つ(fr)は、「free list」レジスタとして区別されて、NILの無限のリストを示すために初期化されます。
別のレジスタ(sp)は「スタックポインタ」レジスタとして指定されます。

マシンは以下のアトム操作のどれかを実行することができます:

r1<->r2;		/* swap r1,r2. */
r1<->CAR(r2);		/* r1,r2 distinct; precondition(not ATOM(r2)) */
r1<->CDR(r2);		/* r1,r2 distinct; precondition(not ATOM(r2)) */
NULL(r1);		/* predicate for r1=NIL */
ATOM(r1);		/* predicate for r1=NIL or symbolp(r1) */
EQ(r1,r2);		/* defined only for atomic r1,r2; see [Baker93ER] */
r1:='foo;		/* precondition(ATOM(r1) and ATOM('foo)) constant 'foo */
r1:=r2;			/* precondition(ATOM(r1) and ATOM(r2)) */

CONS(r1,r2):		/* r1,r2 distinct; r2<-CONS(r1,r2) and set r1=NIL */
{r1<->CAR(fr); r2<->fr; fr<->CDR(r2);};

PUSH(r1,r2):		/* r1,r2 distinct; Push r1 onto r2 and set r1=NIL */
CONS(r1,r2);

POP(r1,r2):		/* r1,r2 distinct; Pop CAR(r2) into r1 if r1=NIL */
if NULL(r1) and not ATOM(r2)
   then {fr<->CDR(r2); r2<->fr; r1<->CAR(fr);}
   else die;

はたして、この文献を掘り下げる価値はあるのだろうか…

Linear Lispで言っているのは単一のセルをふたつ以上のポインタが決して
指さないように評価機を構成する話ですね。プログラム自身がどう
表現されているかはとは別の話ですね。

shiroさまのご指摘で掘り下げる意味がないことが判明。ありがとございます。

主にアルゴリズムの実験日誌

Lively Linear Lispを翻訳してみる

ToDo

Abstract

Introduction

A Linear Lisp Machine