Linear Lisp -- Dataflow-like Producer/Consumer EVAL

Dataflow-like Producer/Consumer EVAL

データフローのような生産者/消費者EVAL

Before showing how to make FREE, COPY and EQUAL more efficient, it is instructive to show a natural programming metaphor for Linear Lisp.

FREE, COPY, EQUALをさらに効果的にする作り方を示す前に、はLinear Lispの自然なプログラミングメタファーを示すことは有益です。

The natural metaphor for Linear Lisp is quantum mechanics, in which objects interact, and every interaction with an object--including reading--affects the object.

Linear Lispの自然なメタファーは量子マシンです、オブジェクトは相互に作用しオブジェクトに対するあらゆる相互作用(読み取ることも含む)はオブジェクトに影響を及ぼす。

Linear Lisp calls for the mechanical interpretation of a function as a "black box" which consumes its arguments and produces its result, while returning the black box to its quiescent state.

Linear Lispはその引数を消費し、結果を生み出す「ブラックボックス」としての関数の機械的な解釈を要求します。その静的な状態にブラックボックスを返すまでの間。

Since an argument to a function is consumed, the function can reference it only once, after which the formal parameter binding becomes unbound!

関数に引数が消費されたときから、関数はそれをたった一回だけ参照することができ、その後に形式的なパラメータの束縛は開放される!

In fact, the requirement to return the box to its quiescent state means that every parameter and local variable must be referenced exactly once, since it is a run-time error to return from the function so long as any parameters or local variables still have bindings.

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

I.e., no values can be "left on base at the end of an inning", to provide a baseball analogy.
すなわち、値は野球に例えると「回終了後の残塁」はありません。
This error can usually be checked at compile-time.
このエラーは通常コンパイル時にチェックされます。

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

実際には、その静的な状態にボックスから返ることの要求は、どんなパラメータや局所変数も束縛を受けている限りは関数から返ることはランタイムエラーになるので、あらゆるパラメータと局所変数は厳密に一度だけ参照されなければならないことを意味します。

In order to utilize a value more than once, it must be explicitly copied.

1回以上値を利用するために、それは明示的にコピーされなければなりません。

We relax the "reference-once" requirement in the case of multiple-arm conditionals.

私達は複合条件文の場合に「一回だけの参照」を緩めます。

Since the execution of one arm implies the non-execution of the other arms, the single use of the variable within each arm is sufficient to guarantee that single use is dynamically satisfied.

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

Copying is still required if speculative execution of an arm is performed.
もし推論的な実行が行われるならばコピーはやはり必要です。

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

片方の実行はもう片方の非実行を意味するので、各々での値の単一使用は単一使用が動的に満足されるのを保証するのに十分です。


In fact, the best policy is to reference exactly the same set of variables in all of the arms of the conditional.

実際には、最良の方針は厳密に条件文の全ての変数の同じ集合に参照をつけることです。

The exactly-one-reference policy can be checked syntactically at compile-time in a manner analogous to the "occurs free" predicate of the lambda calculus.

厳密な単一参照の方針は、ある意味ではλ計算の述部「開放が起こる」ことに類似して、コンパイル時に構文的にチェックすることが可能です。

The following technique should make the programming of certain predicates more efficient.

次のテクニックは確かな述語のプログラミングをより効果的にするべきです。

A value passed to a predicate is often subsequently used in the arm of a conditional, yet in many of these cases, the predicate does not depend upon any deep property of the value.

述語を過ぎた値はしばしば条件文で使用された後で、これらの場合の多くでも、述語はどんな深い値の属性にも依存しません。

The cost of copying and then consuming the entire value is therefore wasted.

全ての値のコピーと消費のコストはそれ故に無駄になります。

For such a "shallow" predicate, one might rather program it to return (a list of) two values--the value of the predicate and its reconstituted arguments, which is then bound to new parameters and (re)used in the subsequent computation.

1つは2つの値(のリスト)(新しいパラメータとして束縛され、それに続く計算で[再]使用された時の述語の値とその再構成された引数)を返すよりはむしろ、そのような「浅い」述語のためにプログラムされるかもしれません。

Since the argument to CAR or CDR is completely consumed, how can one gain access to both components?

CARやCDRへの引数が完全に消費されてから、どのように両方の部分へのアクセスを得ることができるのでしょうか?

The natural model for binding in Linear Lisp is that of a destructuring bind, which binds a number of variables "simultaneously", while recycling the backbone of the value-containing list structure.

Linear Lispでの束縛の自然なモデルは分離構造化束縛のそれです、「同時に」たくさんの変数を束縛します、リスト構造を含む値のバックボーンの再利用として。

This destructuring bind eliminates the need for separate CAR and CDR functions.

この分離構造化束縛はCARとCDR関数を分離するために必要なものを取り除きます。

Nested functional composition has the obvious mechanical interpretation, since the intermediate results are utilized by exactly one consumer.

入れ子になった関数構成は明らかな機械的解釈を持ちます、中間結果は厳密に1回消費されることによって利用されるので。

The mechanical metaphor also shows that parallel execution of subexpressions is possible and correct (so long as the primitive CONS itself--the creator of argument lists--evaluates its arguments in parallel), since there is no mechanism whereby the subexpressions can communicate.

機械的メタファーもまた副次式の並行実行が可能で妥当であることを示します(プリミティブなCONSであるならばそれ自身[引数リスト{並行に評価するその引数}の作成者])、副次式は伝達することができるための仕組みがないので。

Thus, collateral argument evaluation [Baker77] can be considered the norm, and on this machine there are no garbage collection problems because every callee is required to "clean up" after itself.

このように、対応する引数の評価はノルムと見なすことが出来ます、そしてこのマシンでそれらは全ての呼ばれる側がそれ自身の後に「後片付け」を必要とするので、ガベージコレクションの問題がありません。

Unfortunately, the hash consing technique described later requires that CONS be (transitively) strict in both of its arguments.

あいにく、ハッシュコンシングテクニックは後でCONSはその項の両方で(推移的に)厳密である必要が述べられます。

As a result, only variable binding itself can be lazy, which isn't nearly lazy enough for most interesting applications of laziness; lazy "futures" [Baker77] cannot be supported.

結果として、変数束縛それ自身だけが遅延することが可能です、ほとんどの遅延の興味深い応用のためにほぼ十分な遅延ではありません。


The analogy with a dataflow machine [Arvind87] is quite close.

データフローマシンの例えは本当に近いです。

Values are tokens which are consumed by a function to produce a new token/value. The implementation of the token metaphor on our Swapping Lisp Machine is straightforward.

値は新しいトークン/値を生産するための関数によって消費されるトークンです。

In addition to programmer-visible values, we also have "holes", which are the bindings of variables when they are "unbound".

プログラマーから見える値に加えて、私達は「ホール」も持ちます、それはそれらが「開放された」ときの変数の束縛です。

Argument passing is accomplished by "swap-in, swap-out" (reminiscent of [Harms91]), and "holes" flow backwards relative to values.

引数渡しは「スワップイン、スワップアウト」([Harms91]を彷彿とさせる)によって完了されます、そして「ホール」は値と相対的に後方へ流れます。

When implemented in this way (see Appendix), EVAL avoids most copying, and should be reasonably efficient even without the hash consing scheme discussed in the next section.

この方法で実装する場合(付録を参照)、EVALはできるだけコピーは避けます、そして次のセクションでハッシュコンシングの仕組の合理的で効果的な議論がされるでしょう。


>> 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