Linear Lisp -- Introduction

Introduction

導入

Neither a borrower nor a lender be;
For loan oft loses both itself and friend ... [Shakespeare, Hamlet, I. iii 75]

借り手も貸し手もない;
ローンはたびたびそれ自体と友人の両方を失うから…

The sharing of data structures can be efficient, because sharing can substitute for copying, but it creates ambiguity as to who is responsible for their management.

データ構造の共有は効率的であることができます、なぜならば共有はコピーの変わりにすることが可能だからです、しかしそれは誰がそれらを管理することに対して責任があるのかのあいまいさを引き起こします。

This ambiguity is difficult to statically remove [Barth77] [Bloss89] [Chase87] [Hederman88] [Inoue88] [Jones89] [Ruggieri88], and we have shown [Baker90] that static sharing analysis--even for pure functional languages--may be as hard as ML type inference, which is known to be exponential [Mairson90].

***** footnote(注釈) *****

We have conjectured that sharing analysis [Baker90] utilizing ML type inference will elicit its exponential behavior.
私達は共有の解析を利用するMLの型推論が指数関数的な振る舞いを引き出すと推測しました。

**************************

このあいまいさは静的に取り除くのが困難で私達は静的な共有の解析(純粋な関数型言語でさえ[MLの型推論と同じくらい困難で、それは指数関数的であると知られています])を示しました。

We show here that a system which takes advantage of incidental, rather than necessary, sharing can provide efficiency without the ambiguity normally associated with sharing.

私達は偶発的であるよりむしろ必要な長所を持つシステムをここに示します、共有は通常共有と関係があるあいまいさなしで効率を提供することができます。

Linear logic was invented by Girard [Girard87] as a way to deal with objects which should not be blithely shared or copied.

線型論理は軽率に共有やコピーされてはならない物を扱うための方法としてGirardによって考案されました。

Wadler [Wadler91] has proposed the use of data structures with unity reference counts in order to avoid the problems of garbage collection and provide for O(1) array update.

WadlerはガベージコレクションとO(1)配列更新の問題を避けるために唯一の参照カウントデータ構造の使用を提案しました。

Wakeling [Wakeling91] has implemented linear logic and found that it is extremely slow, due to its requirement for laborious copying.

Wakelingは線型論理を実装しそれが非常に遅く、それが面倒なコピーを必要とすることに起因することを見出しました。

Our Linear Lisp Machine implements unity reference count data structures more efficiently than Wakeling's machine, and should be "competitive" with traditional implementations of combinator/graph reduction machines.

私達のLinear LispマシンはWakelingのマシンより効率良く唯一の参照カウントデータ構造を実装し、従来のコンビネータ/グラフリダクションマシンの実装に「優位性」があります。


>> Lively Linear Lisp
>> Abstract
>> Introduction
>> A Linear Lisp Machine
>> A Linear Lisp Machine with FREE, COPY, EQUAL and Assignment
>> Dataflow-like Producer/Consumer EVAL
>> Reconstituting Trees from Fresh Frozen Concentrate
>> Linear Lisp EVAL
>> Implications for Real Multiprocessors
>> Conclusions and Previous Work