lisppa.htm
来自「Delphi脚本控件」· HTM 代码 · 共 1,141 行 · 第 1/3 页
HTM
1,141 行
<html>
<head>
<link rel=stylesheet type="text/css" href="styles.css">
</head>
<body>
<font face="Arial, Helvetica">
<h2>
LISPPA Technology
</h2>
<hr>
<p>
LISPPA (List Processing based on the Polymorphic Arrays) technology is a way to process dynamic
data structures (lists, trees and more) without using pointers. LISPPA uses polymorphic arrays as
a base of the data representation.
<p>
What is the polymorphic array? The elements of a polymorphic array can be of any type allowed in the
given programming language, besides the array elements can hold another arrays.
<p>
A very important example of polymorphic arrays is <i>variant arrays</i> in such languages as Visual Basic,
Object Pascal (Delphi) and other. The current implementation of LISPPA is based on an extension of the Variant
type. All languages of the <a href="http://www.paxscript.com">paxScript scripting engine</a>: paxPascal,
paxBasic, paxC, paxJavaScript support LISPPA.
<h3>
Contents
</h3>
<ul>
<li><a href="#Representation of Lists">Representation of Lists</a>
<li><a href="#List Processing">List Processing</a>
<li><a href="#Working with Binary Trees">Working with Binary Trees</a>
<li><a href="#Stacks and queues">Stacks and Queues</a>
<li><a href="#Two Way Linked Lists">Two Way Linked Lists</a>
<li><a href="#More Detailed Description of the LISPPA Concepts">More Detailed Description of the LISPPA Concepts</a>
<li><a href="#LISPPA and Symbolic Computation">LISPPA and Symbolic Computation</a>
<li><a href="#LISPPA and COM Technology">LISPPA and COM Technology</a>
<li><a href="#Demos">Demos</a>
<ul>
<li><a href="#paxBasic">paxBasic</a>
<li><a href="#paxC">paxC</a>
<li><a href="#paxJavaScript">paxJavaScript</a>
<li><a href="#paxPascal">paxPascal</a>
</ul>
<li><a href="#Conclusions">Conclusions</a>
<li><a href="#References">References</a>
</ul>
<a name="Representation of Lists">
<h3>
Representation of Lists
</h3>
In terms of polymorphic arrays one can formulate the following recursive definition of the linked list:
<ol>
<li> NULL is a list.
<li> If L is a list, the one-dimensional array A with two elements A(0) and A(1) = L is a list too.
</ol>
A(0) contains a value of the list item.
<p>
How we might create a list by means of the variant arrays? Let's assume we want to create list
(100, 200, 300). We can implement it in Basic by the following statements:
<blockquote>
<pre>
<font color="blue"><b>Dim</b></font> L, A1(1), A2(1), A3(1)
A3(0) = 300
A2(0) = 200
A2(1) = A3
A1(0) = 100
A1(1) = A2
L = A1
</pre>
</blockquote>
paxBasic provides more easy solution to implement the same operation by the variant array constructor:
<blockquote>
<pre>
<font color="blue"><b>Dim</b></font> L = [100, [200, [300, <font color="blue"><b>NULL</b></font>]]]
</pre>
</blockquote>
This possibility to create arrays by the variant array constructor is the first important extension of
the variant data type. We will see, the variant array constructors is widely used in the LISPPA.
<a name="List Processing">
<h3>
List Processing
</h3>
Now let's consider the problem of insertion of new item 50 at the head of list L. The variant array
constructor concept suggests a solution:
<blockquote>
<pre>
L = [50, L]
</pre>
</blockquote>
Let's note that this operation is processed effectively and without memory leak as L variable
is a reference. To see it, consider semantics of the statement above:
<blockquote>
<pre>
<font color="blue"><b>Dim</b></font> temp = Array(2)
temp(0) = 50
temp(1) = L
L = temp
</pre>
</blockquote>
L and temp variables are references. You assign references, not actual arrays in the third and
fourth statements.
<p>
To insert new item 400 at the tail of the L list, we have to introduce the concept of delegate of
variable. It will be the second extension of the variant type concept.
<p>
Delegate P of variable V substitutes the variable V in the program. In another words, we can think about
P as an alias of V. Therefore we will use both names "delegate of variable" and "alias" to denote the
same concept. This concept will be detail discussed below. For now, let's note that using aliases
gives us a way to effectively solve the problem of insertion new item at the tail of list L. Indeed:
<blockquote>
<pre>
P = <font color="blue"><b>AddressOf</b></font> L 'Create alias of L
<font color="blue"><b>Do</b></font> <font color="blue"><b>Until</b></font> P = <font color="blue"><b>NULL</b></font> 'Find tail of L
P = <font color="blue"><b>AddressOf</b></font> P(1)
<font color="blue"><b>Loop</b></font>
P = [400, P] 'Add new item at the tail of L
</pre>
</blockquote>
At this point we have L list (50, 100, 200, 300, 400). Is there a way to insert a new item, for
example 150, at the middle of L? We can guess, the using aliases allows us to solve this problem as well
with the same success.
<p>
Let's assume we want to insert 150 between 100 and 200. The following statement sequence allows us to do it:
<blockquote>
<pre>
P = <font color="blue"><b>AddressOf</b></font> L(1)
P = <font color="blue"><b>AddressOf</b></font> P(1) 'insert before 200
P = [150, P]
</pre>
</blockquote>
Note, 3 operations of insertion (at the head, at the middle, at the tail) are implemented by
uniform way. A single statement is enough to insert new item in all cases.
<p>
Now let's consider the problem of removing items from the list. At first, let's consider the removing at the
head of list L.
<p>
The first possible solution
<blockquote>
<pre>
L = L(1)
</pre>
</blockquote>
is not quite correct because it will produce a memory leak. The LISPPA extends the ordinary assignment
statement with the <b>reduced</b> modifier. The reduced assignment statement
<blockquote>
<pre>
<font color="blue"><b>reduced</b></font> L = L(1)
</pre>
</blockquote>
allows us to assign L(1) to L without the memory leak. This statement has the following semantics:
<blockquote>
<pre>
<font color="blue"><b>Dim</b></font> temp = L(1)
L(1) = <font color="blue"><b>NULL</b></font>
<font color="blue"><b>delete</b></font> L
L = temp
</pre>
</blockquote>
We can see, the reduced assignment statement is processed effectively.
<p>
Let's consider the removing items at the tail of the L list. We can use aliases to find
last item of L, then we delete it:
<blockquote>
<pre>
P = <font color="blue"><b>AddressOf</b></font> L
<font color="blue"><b>Do</b></font> <font color="blue"><b>Until</b></font> P(1) = <font color="blue"><b>NULL</b></font>
P = <font color="blue"><b>AddressOf</b></font> P(1)
<font color="blue"><b>Loop</b></font>
<font color="blue"><b>reduced</b></font> P = P(1)
</pre>
</blockquote>
The operation of removing items at the middle of the L list has the same unified form and concise notation:
<blockquote>
<pre>
P = <font color="blue"><b>AddressOf</b></font> L
P = <font color="blue"><b>AddressOf</b></font> P(1)
<font color="blue"><b>reduced</b></font> P = P(1)
</pre>
</blockquote>
Finally, let's consider how to remove all items from the L list:
<blockquote>
<pre>
<font color="blue"><b>Do</b></font> <font color="blue"><b>Until</b></font> L = <font color="blue"><b>NULL</b></font>
<font color="blue"><b>Reduced</b></font> L = L(1)
<font color="blue"><b>Loop</b></font>
</pre>
</blockquote>
Ok. At this point we have considered LISPPA concepts (polymorphic arrays, array constructors, reduced
assignments and aliases) which provide a way to process the linked lists. We have to introduce one more
(the last) concept to ensure the full applicability of the LISPPA for the representation and processing of
dynamic data structures.
<p>
Let's consider a problem of representation of cycled list (100, 200, 300). We have to find a possibility to
join the head and tail of the list. The first solution
<blockquote>
<pre>
<font color="blue"><b>Dim</b></font> L = [100, [200, [300, <font color="blue"><b>NULL</b></font>]]]
L[1][1][1] = <font color="blue"><b>AddressOf</b></font> L
</pre>
</blockquote>
is trivial one, but it is not suitable for a "long" list. We have to find a way to do the same for arbitrary
lists.
<p>
At first, let's note, if P is an alias of V variable, the new assignment of alias of another variable W
will discard the old value of P. Therefore, if we want to make V as alias of W by means of P, we should use
the TerminalOf operator:
<blockquote>
<pre>
<font color="blue"><b>TerminalOf</b></font> P = <font color="blue"><b>AddressOf</b></font> W
</pre>
</blockquote>
Here is the LISPPA solution of the cycled list problem:
<blockquote>
<pre>
<font color="blue"><b>Dim</b></font> L = [100, [200, [300, <font color="blue"><b>NULL</b></font>]]]
P = <font color="blue"><b>AddressOf</b></font> L
<font color="blue"><b>Do</b></font> <font color="blue"><b>Until</b></font> P = <font color="blue"><b>NULL</b></font>
P = <font color="blue"><b>AddressOf</b></font> P(1)
<font color="blue"><b>Loop</b></font>
<font color="blue"><b>TerminalOf</b></font> P = <font color="blue"><b>AddressOf</b></font> L
</pre>
</blockquote>
The following statement sequence will print list items:
<blockquote>
<pre>
P = <font color="blue"><b>AddressOf</b></font> L
I = 0
<font color="blue"><b>Do</b></font>
<font color="blue"><b>println</b></font> P[0]
P = <font color="blue"><b>AddressOf</b></font> P[1]
I += 1
<font color="blue"><b>Loop</b></font> <font color="blue"><b>Until</b></font> I = 15
</pre>
</blockquote>
<font size ="2">
It is necessary to note, the using of aliases can be considerably eliminated. Often we can use ordinary
references instead of aliases.
<p>
For example, I can insert new item anItem into L list after the first item of L by means of
<blockquote>
<pre>
L[1] := [anItem, L[1]];
</blockquote>
</pre>
Furthermore, I might use the statement sequence
<blockquote>
<pre>
P := L[1];
P[1] := [anItem, P[1]];
</blockquote>
</pre>
to insert new item after the second item of L list.
<p>
However, I prefer to use aliases as they keep the structure of the statement of insertion:
<blockquote>
<pre>
P := [anItem, P];
</blockquote>
</pre>
which is uniform one, i.e. <b>it does not depend from the position of insertion</b>
(at the top, at the middle, at the tail of list). You are moving alias, not changing structure of the
statement.
</font>
<a name ="Working with Binary Trees">
<h3>
Working with Binary Trees
</h3>
In terms of polymorphic arrays one can formulate the following recursive definition of the binary tree:
<ol>
<li>NULL is a binary tree
<li>If L and R are binary trees, the one-dimensional array A with 3 elements A(0), A(1) = L and
A(2) = R is a binary tree too.
</ol>
A(0) contains a key of a node.
<p>
Lets's consider a simple program in paxBasic:
<blockquote>
<pre>
<font color="blue"><b>Dim</b></font> Key = 0, Left = 1, Right = 2
<font color="blue"><b>Sub</b></font> AddNode(Root, X)
<font color="blue"><b>If</b></font> Root = <font color="blue"><b>NULL</b></font> <font color="blue"><b>Then</b></font>
Root = [X, <font color="blue"><b>NULL</b></font>, <font color="blue"><b>NULL</b></font>]
<font color="blue"><b>ElseIf</b></font> X < Root(Key) <font color="blue"><b>Then</b></font>
AddNode(<font color="blue"><b>AddressOf</b></font> Root(Left), X)
<font color="blue"><b>ElseIf</b></font> X > Root(Key) <font color="blue"><b>Then</b></font>
AddNode(<font color="blue"><b>AddressOf</b></font> Root(Right), X)
<font color="blue"><b>End</b></font> <font color="blue"><b>If</b></font>
<font color="blue"><b>End</b></font> <font color="blue"><b>Sub</b></font>
<font color="blue"><b>Function</b></font> Search(Root, X)
<font color="blue"><b>If</b></font> Root = <font color="blue"><b>NULL</b></font> <font color="blue"><b>Then</b></font>
<font color="blue"><b>Return</b></font> <font color="blue"><b>NULL</b></font>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?