newLisp -- Implementing ORO memory management

Implementing ORO memory management

OROメモリ管理の実装

The following pseudo code illustrates the algorithm implemented in newLISP in the context of LISP expression evaluation. Only two functions and one data structure are necessary to implement ORO memory management:

次の擬似コードはLISPの式評価のnewLISPで実装されたアルゴリズムを示します：

function pushResultStack(evalationResult)

function popResultStack() ; implies deleting

array resultStack[] ; preallocated stack area

The first two functions pushResultStack and popResultStack push or pop a LISP object handle on or off a stack. pushResultStack increases the value resultStackIndex while popResultStack decreases it. In newLISP every object is contained in a LISP cell structure. The object handle of that structure is simply the memory pointer to the cell structure. The cell itself may contain pointer addresses to other memory objects like string buffers or other LISP cells linked to the original object. Small objects like numbers are stored directly. In this paper function popResultStack() also implies that the popped object gets deleted.

最初の２つの関数pushResultStackとpopResultStackは、LISPオブジェクトハンドルをスタックの上にまたは外すプッシュまたはポップをします。
pushResultStackはresultStackIndexの値をインクリメントします、と同時にpopResultStackはその値をデクリメントします。
newLISPでは各オブジェクトはLISPセル構造を含みます。
その構造のオブジェクトハンドルは単純にセル構造へのメモリポインタです。
セルそれ自身は文字列バッファのようなメモリオブジェクトやオリジナルオブジェクトへ接続された他のLISPセルへのポインタアドレスを含むでしょう。
小さな数のようなオブジェクトは直接格納されます。
この論文では関数popResultStack()でもまたポップされたオブジェクトが削除されることを意味します。

The two resultStack management functions described are called by newLISP's evaluateExpression function:

２つのresultStack管理関数の記述はnewLISPのevaluateExpression関数と呼ばれます：

function evaluateExpression(expr)
{
resultStackIndexSave = resultStackIndex

if typeOf(expr) is BOOLEAN or NUMBER or STRING
return(expr)

if typeOf(expr) is SYMBOL
return(symbolContents(expr))

if typeOf(expr) is QUOTE
return(quoteContents(expr))

if typeOf(expr) is LIST
{
func = evaluateExpression(firstOf(expr))
args = rest(expr)
if typeOf(func) is BUILTIN_FUNCTION
result = evaluateFunc(func, args)
else if typeOf(func) = LAMBDA_FUNCTION
result = evaluateLambda(func, args)
}
}

while (resultStackIndex > resultStackIndexSave)
deleteList(popResultStack())

pushResultStack(result)

return(result)
}

The function evaluateExpression introduces the two variables resultStackIndexSave and resultStackIndex and a few other functions:

関数evaluateExpressionは２つの変数resultStackIndexSaveとresultStackIndexそして他の少しの関数を導入します：

* resultStackIndex is an index pointing to the top element in the resultStack. The deeper the level of evaluation the higher the value of resultStackIndex.

resultStackIndexはresultStackの一番上の要素を指しているインデックスです。
評価のより深いレベルはresultStackIndexの値がより高いです。

* resultStackIndexSave serves as a temporary storage for the value of resultStackIndex upon entry of the evaluateExpression(func, args) function. Before exit the resultStack is popped to the saved level of resultStackIndex. Popping the resultStack implies deleting the memory objects pointed to by entries in the resultStack.

resultStackIndexSaveはevaluateExpression(func, args)関数の登録でresultStackIndexの値のための一時的なストレージとして機能します。

* resultStack[] is a preallocated stack area for saving pointers to LISP cells and indexed by resultStackIndex.

resultStack[]は事前割振りされたLISPセルへのポインタを保存すうるためのスタック領域でresultStackIndexによってインデックスされます。

* symbolContents(expr) and quoteContents(expr) extract contents from symbols or quote-envelope cells.

symoblContents(expr)とquoteContents(expr)はシンボルやquote-envelopeセルから内容を引き出します。

* typeOf(expr) extracts the type of an expression, which is either a BOOLEAN constant like nil or true or a NUMBER or STRING, or is a variable SYMBOL holding some contents, or a QUOTE serving as an envelope to some other LIST expression expr.

typeoOf(expr)は式の型を引き出します、それはnilやtrueのようなBOOLEAN定数やNUMBERやSTRING、いくつかの内容を持っているSYMBOL変数、あるいはいくつか他のLIST式exprを包むような役割のQUOTEです。

* evaluateFunc(func, args) is the application of a built-in function to its arguments. The built-in function is the evaluated first member of a list in expr and the arguments are the rest of the list in expr. The function func is extracted calling evaluateExpression(first(expr)) recursively. For example if the expression (expr is (foo x y)) than foo is a built-in function and x and y are the function arguments or parameters.

evaluateFunc(func, args)は組み込み関数のその引数への適応です。
組み込み関数はexprのリストの評価された最初のメンバーです、そして引数はexprのリストの残りです。
関数funcは再帰的にevaluateExpression(first(expr))を呼び出すことで引き出されます。
例えばもし式が(expr is (foo x y))ならばfooは組み込み関数です、そしてxとyは関数の引数やパラメータです。

* evaluateLambda(func, args) works simlar to evaluateFunc(func, args), applying a user-defined function first(expr) to its arguments in rest(expr). In case of a user-defined function we have two types of arguments in rest(expr), a list of local parameters followed by one or more body expressions evaluated in sequence.

evaluateLambda(func, args)はevaluateFunc(func, args)と似た働きをします、ユーザー定義の関数first(expr)をその引数rest(expr)で適応します。
ユーザー定義の関数の場合、私たちは２つのタイプのrest(expr)の引数を持ちます、ローカルパラメータのリストは１つ以上の順に評価された塊の式に従います。

Both, evaluateFunc(func, args) and evaluateLambda(func, args) will return a newly created LISP cell object, which may be any type of the above mentioned expressions. The result values from these functions will always be newly created LISP cell objects destined to be destroyed on the next higher evaluation level, after the current evaluateExpression(expr) function excution returned.

evaluateFunc(func, args)とevaluateLambda(func, args)は両方、新しい生成されたLISPセルオブジェクトを返すでしょう、それは上で述べた式のどの型でもある可能があります。
これらの関数の結果の値はいつでも現在のevaluateExpression(expr)関数の実行から帰ったあとにより次の高い評価のレベルで削除されることを運命付けられた新しく生成されたLISPセルオブジェクトです。

Both functions will recursively call evaluateExpression(expr) to
evaluate their arguments. As recursion deepens it increases the
recursion level of the function.

両方の関数はそれらの引数を評価するためにevaluateExpression(expr)を再帰的に呼ぶでしょう。
再帰が深まるにつれて関数の再帰レベルが増加します。

Before evaluateExpression(func, args) returns it will pop the resultStack deleting the result values from deeper level of evaluation and returned by one of the two functions, either evaluateFunc or evaluateLambda.

evaluateExpression(func, args)が返る前にそれは評価のより深いレベルからの結果の値を削除してevaluateFuncかevaluateLambdaの二つの関数の一つによって返されたresultStackをポップするでしょう。

Any result expression is destined to be destroyed later but its deletion is delayed at a lower level of evaluation. This permits results to be used or copied by calling functions.

どんな結果の式も後に削除される運命にありますが、その削除は評価の低いレベルで遅延されます。
これは結果が呼び出している関数によって使用またはコピーされることを許します。

The following example shows the evaluation of a small user-defined LISP function sum-of-squares and the creation and deletion of associated memory objects:

次の例は小さいユーザー定義のLISP関数sum-of-squaresとメモリオブジェクトに関連付けられた生成と削除の評価を示します：

(define (sum-of-squares x y)
(+ (* x x) (* y y)))

(sum-of-squares 3 4) => 25

sum-of-squares is a user-define lambda-function calling to built-in functions + and *.

sum-of-squaresは組込み関数+と*を呼び出すユーザー定義lambda-functionです。

The following trace shows the relevant steps when defining the sum-of-squares function and when executing it with the arguments 3 and 4.

次のトレースはsum-of-squares関数を定義する時とそれを引数3と4で実行する時の関連したステップを示します。

> (define (sum-of-squares x y) (+ (* x x) (* y y)))

level 0: evaluateExpression( (define (sum-of-squares x y)
(+ (* x x) (* y y))) )
level 1: evaluateFunc( define <6598> )
level 1: return( (lambda (x y) (+ (* x x) (* y y))) )

→ (lambda (x y) (+ (* x x) (* y y)))

> (sum-of-squares 3 4)
level 0: evaluateExpression( (sum-of-squares 3 4) )
level 1: evaluateLambda( (lambda (x y) (+ (* x x) (* y y))), (3 4) )
level 1: evaluateExpression( (+ (* x x) (* y y)) )
level 2: evaluateFunc( +, ((* x x) (* y y)) )
level 2: evaluateExpression( (* x x) )
level 3: evaluateFunc( *, (x x) )
level 3: pushResultStack( 9 )
level 3: return( 9 )
level 2: evaluateExpression( (* y y) )
level 3: evaluateFunc( *, (y y) )
level 3: pushResultStack( 16 )
level 3: return( 16 )
level 2: popResultStack() ->16
level 2: popResultStack() ->9
level 2: pushResultStack( 25 )
level 2: return( 25 )
level 1: return( 25 )

→ 25

The actual C-language implementation is optimized in some places to avoid pushing the resultStack and avoid calling evaluateExpression(expr). Only the most relevant steps are shown. The function evaluateLambda(func, args) does not need to call evaluateLambda(func, args) to evaluate its arguments 3 and 4 becuase they are constants, but evaluateLambda(func, args) will call evaluateExpression(expr) twice to evaluate the two body expressions (+ (* x x) and (+ (* x x). Lines preceded by the prompt > show the command-line entry.

実際のC言語の実装は一部でresultStackをプッシュすることを避け、evaluateExpression(expr)を呼ぶことを避けることで最適化されます。
最も関連したステップだけが示されます。
関数evaluateLambda(func, args)はそれらは定数なのでそれを引数3と4で評価するためにevaluateLambda(func, args)を呼ぶことを必要としません、しかしevaluateLambda(func, args)は2つの式(+ (* x x))と(+ (* x x))を評価するためにevaluateExpression(expr)を2回呼ぶでしょう。

evaluateLambda(func, args) also saves the environment for the variable symbols x and y, copies parameters into local variables and restores the old environment upon exit. These actions too involve creation and deletion of memory objects. Details are omitted, becuase they are similar to to methods in other dynamic languages.

evaluateLambda(func, args)もまた変数のシンボルxとyのために環境を保存します、パラメータを局所変数へコピーして出口で古い環境を復元します。
これら作用はメモリオブジェクトの生成と削除を必要とします。
詳細は省略されます、それらは他の動的言語での方法に似ているので。


>> Automatic Memory Management in newLISP
>> Traditional automatic memory management (Garbage Collection)
>> One reference only, (ORO) memory management
>> Performance considerations with value-passing
>> Memory and datatypes in newLISP
>> Implementing ORO memory management