lisppa.htm

来自「Delphi脚本控件」· HTM 代码 · 共 1,141 行 · 第 1/3 页

  <font color="blue"><b>ElseIf</b></font> X = Root(Key) <font color="blue"><b>Then</b></font>
    <font color="blue"><b>Return</b></font> Root
  <font color="blue"><b>ElseIf</b></font> X < Root(Key) <font color="blue"><b>Then</b></font>
    <font color="blue"><b>Return</b></font> Search(Root(Left), X)
  <font color="blue"><b>Else</b></font>
    <font color="blue"><b>Return</b></font> Search(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>Function</b></font>

<font color="blue"><b>Sub</b></font> DeleteNode(Root, X)
  <font color="blue"><b>Dim</b></font>  P, R
  
  R = Search(Root, X)

  <font color="blue"><b>If</b></font> R = <font color="blue"><b>NULL</b></font> <font color="blue"><b>Then</b></font>
    <font color="blue"><b>Exit</b></font> <font color="blue"><b>Sub</b></font>
  <font color="blue"><b>ElseIf</b></font> (R(Left) = <font color="blue"><b>NULL</b></font>) <font color="blue"><b>And</b></font> (R(Right) = <font color="blue"><b>NULL</b></font>) <font color="blue"><b>Then</b></font>
    <font color="blue"><b>Reduced</b></font> R = <font color="blue"><b>NULL</b></font>
  <font color="blue"><b>ElseIf</b></font> R(Left) = <font color="blue"><b>NULL</b></font> <font color="blue"><b>Then</b></font>
    <font color="blue"><b>Reduced</b></font> R = R(Right)
  <font color="blue"><b>ElseIF</b></font> R(Right) = <font color="blue"><b>NULL</b></font> <font color="blue"><b>Then</b></font>
    <font color="blue"><b>Reduced</b></font> R = R[Left]
  <font color="blue"><b>Else</b></font>
    P = <font color="blue"><b>AddressOf</b></font> R(Left)
    <font color="blue"><b>Do</b></font> <font color="blue"><b>Until</b></font> P(Right) = <font color="blue"><b>NULL</b></font>
      P = <font color="blue"><b>AddressOf</b></font> P(Right)
    <font color="blue"><b>Loop</b></font>
    R(Key) = P(Key)
    <font color="blue"><b>Reduced</b></font> P = P(Left)
  <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>Sub</b></font> InOrder(Root)
  <font color="blue"><b>If</b></font> Root <> <font color="blue"><b>NULL</b></font> <font color="blue"><b>Then</b></font>
    InOrder(Root(Left))
    <font color="blue"><b>println</b></font> Root(Key)
    InOrder(Root(Right))
  <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>Dim</b></font> Tree, X

AddNode(<font color="blue"><b>AddressOf</b></font> Tree, 10)
AddNode(<font color="blue"><b>AddressOf</b></font> Tree, 5)
AddNode(<font color="blue"><b>AddressOf</b></font> Tree, 15)
AddNode(<font color="blue"><b>AddressOf</b></font> Tree, 3)
AddNode(<font color="blue"><b>AddressOf</b></font> Tree, 8)
AddNode(<font color="blue"><b>AddressOf</b></font> Tree, 13)
AddNode(<font color="blue"><b>AddressOf</b></font> Tree, 18)
<font color="blue"><b>println</b></font> Tree
PreOrder(Tree)

X = Search(Tree, 5)
<font color="blue"><b>println</b></font> X

DeleteNode(<font color="blue"><b>AddressOf</b></font> Tree, 10)
<font color="blue"><b>println</b></font> Tree
</pre>
</blockquote>


You can see, the representation of algorithmes is very concise. Note, we prefer 


<blockquote>
<pre>
    <font color="blue"><b>Reduced</b></font> R = <font color="blue"><b>NULL</b></font>
</pre>
</blockquote>

instead of

<blockquote>
<pre>
    <font color="blue"><b>Delete</b></font> R
</pre>
</blockquote>

to avoid explicit use of a deallocation operator.


<a name ="Stacks and queues">
<h3>
Stacks and Queues
</h3>

Empty linked stack is represented by unassigned variable Stack:

<blockquote>
<pre>
    <font color="blue"><b>Dim</b></font> Stack
</pre>
</blockquote>

To push new item anItem into the stack, we use

<blockquote>
<pre>
    Stack = [anItem, Stack]
</pre>
</blockquote>


The top item of the stack is available as Stack(0).


<p>
We can delete the top item with the statement


<blockquote>
<pre>
    <font color="blue"><b>Reduced</b></font> Stack = Stack(1)
</pre>
</blockquote>


The linked queue can be represented by 2 variables Head and Tail. We add new items at the tail of the 
queue with the statement sequence:


<blockquote>
<pre>
<font color="blue"><b>If</b></font> Head = <font color="blue"><b>NULL</b></font> <font color="blue"><b>Then</b></font>
  Tail = [anItem, <font color="blue"><b>NULL</b></font>]
  Head = Tail
<font color="blue"><b>Else</b></font>
  Tail(1) = [anItem, <font color="blue"><b>NULL</b></font>]
  Tail = Tail(1)
<font color="blue"><b>End</b></font> <font color="blue"><b>If</b></font>
</pre>
</blockquote>

The first item of the queue is available as Head(0), Tail(0) returns the last item. The statement

<blockquote>
<pre>
   <font color="blue"><b>Reduced</b></font> Head = Head(1)
</pre>
</blockquote>

allows to delete items at the head of the queue.



<a name ="Two Way Linked Lists">
<h3>
Two Way Linked Lists
</h3>


The most easy way to introduce the two way linked lists is to extend the polymorphic array with the 
Owner property. The Owner property returns reference on array which contains given array.

<p>
To insert new item before the position specified by the P alias, we can use function:


<blockquote>
<pre>
<font color="blue"><b>Function</b></font> Insert(Value, P)
  <font color="blue"><b>Dim</b></font> result = [Value, P]
  <font color="blue"><b>If</b></font> P <> <font color="blue"><b>null</b></font> <font color="blue"><b>Then</b></font>
    P.Owner = result
  <font color="blue"><b>End</b></font> <font color="blue"><b>If</b></font>
  P = result
  <font color="blue"><b>return</b></font> P
<font color="blue"><b>End</b></font> <font color="blue"><b>Function</b></font>
</pre>
</blockquote>


The Add function, which allows to add new item after the position specified by the P alias, can be
expressed via Insert function:


<blockquote>
<pre>
<font color="blue"><b>Function</b></font> Add(Value, P)
  <font color="blue"><b>Dim</b></font> result
  <font color="blue"><b>If</b></font> P = <font color="blue"><b>null</b></font> <font color="blue"><b>Then</b></font>
    result = Insert(Value, P)
  <font color="blue"><b>Else</b></font>
    result = Insert(Value, <font color="blue"><b>AddressOf</b></font> P(1))
    result.Owner = P
  <font color="blue"><b>End</b></font> <font color="blue"><b>If</b></font>
  <font color="blue"><b>return</b></font> result
<font color="blue"><b>End</b></font> <font color="blue"><b>Function</b></font>
</pre>
</blockquote>


The Find function returns alias of item which contains the Key value or <b>null</b> if such item is 
absent:

<blockquote>
<pre>
<font color="blue"><b>Function</b></font> Find(Key, P)
  <font color="blue"><b>Dim</b></font> result = <font color="blue"><b>AddressOf</b></font> P
  <font color="blue"><b>Do</b></font> <font color="blue"><b>While</b></font> result <> <font color="blue"><b>null</b></font>
    <font color="blue"><b>If</b></font> result(0) = Key <font color="blue"><b>Then</b></font>
      <font color="blue"><b>Return</b></font> result
    <font color="blue"><b>End</b></font> <font color="blue"><b>If</b></font>
    result = <font color="blue"><b>AddressOf</b></font> result(1)
  <font color="blue"><b>Loop</b></font>
  <font color="blue"><b>Return</b></font> <font color="blue"><b>null</b></font>
<font color="blue"><b>End</b></font> <font color="blue"><b>Function</b></font>
</pre>
</blockquote>


We can remove an item at the position given by the Value parameter with the Remove function:

<blockquote>
<pre>
<font color="blue"><b>Function</b></font> Remove(Value, L)
  <font color="blue"><b>Dim</b></font> temp, result
  result = <font color="blue"><b>AddressOf</b></font> Find(Value, L)
  <font color="blue"><b>If</b></font> result <> <font color="blue"><b>null</b></font> <font color="blue"><b>Then</b></font>
    temp = result.Owner
    <font color="blue"><b>Reduced</b></font> result = result(1)
    <font color="blue"><b>If</b></font> result <> <font color="blue"><b>null</b></font> <font color="blue"><b>Then</b></font>
      result.Owner = temp
    <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>If</b></font>
<font color="blue"><b>End</b></font> <font color="blue"><b>Function</b></font>
</pre>
</blockquote>


The BackwardOrder function allows to print list items in the backward order:


<blockquote>
<pre>
<font color="blue"><b>Sub</b></font> BackwardOrder(A)
  <font color="blue"><b>Dim</b></font> P
  <font color="blue"><b>If</b></font> A = <font color="blue"><b>null</b></font> <font color="blue"><b>Then</b></font>
    <font color="blue"><b>println</b></font> A
  <font color="blue"><b>Else</b></font>
    P = A
    <font color="blue"><b>Do</b></font> <font color="blue"><b>While</b></font> P(1) <> <font color="blue"><b>null</b></font> ' Find last item
      P = P(1)
    <font color="blue"><b>Loop</b></font>
    <font color="blue"><b>Do</b></font> <font color="blue"><b>While</b></font> P <> <font color="blue"><b>null</b></font>
      <font color="blue"><b>Println</b></font> P(0)
      P = P.Owner
    <font color="blue"><b>Loop</b></font>
  <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>
</pre>
</blockquote>

<a name ="More Detailed Description of the LISPPA Concepts">
<h3>
More Detailed Description of the LISPPA Concepts
</h3>


As was stated above, the LISPPA technology use the following concepts:

<ul>
<li><b>Polymorphic arrays</b>. At present time, a lot programming languages use it.
<li><b>Array constructors</b>. Nothing new, again. The constructors allow to
create new arrays by means of enumeration of the array elements.
<li><b>Reduced assignment statements</b>. The semantics of the statement can be expressed via already known 
concepts: assignment statement and delete operator. Let's consider it in detail.
<p>
The reduced assignment 

<blockquote>
<pre>
<font color="blue"><b>reduced</b></font> A = E
</pre>
</blockquote>

means

<blockquote>
<pre>
<font color="blue"><b>Dim</b></font> temp = E
E = <font color="blue"><b>NULL</b></font>
<font color="blue"><b>delete</b></font> A
A = temp
</pre>
</blockquote>


if A is an array and E is an element of A. Otherwise it means:

<blockquote>
<pre>
<font color="blue"><b>delete</b></font> A
A = E
</pre>
</blockquote>

<li><b>Aliases and terminals</b>. paxBasic uses statement

<blockquote>
<pre>
P = <font color="blue"><b>AddressOf</b></font> A
</pre>
</blockquote>

to assign P as alias of A. Another paxScript languages use different synax rules. So, paxPascal uses 
statement 

<blockquote>
<pre>
P := @ A; 
</pre>
</blockquote>

paxC and paxJavaScript use 

<blockquote>
<pre>
P = & A; 
</pre>
</blockquote>

Alias P of A variable substitutes the A variable in expressions. Most often aliases are used to operate 
with array elements. For example: 

<blockquote>
<pre>
<font color="blue"><b>Function</b></font> CopyTerm(A)
  <font color="blue"><b>Dim</b></font> I, AI, Result
  Result = PaxArray(A.Length)
  <font color="blue"><b>For</b></font> I=0 <font color="blue"><b>To</b></font> A.Length - 1 
    AI = <font color="blue"><b>AddressOf</b></font> A(I)
    <font color="blue"><b>If</b></font> IsCompound(AI) <font color="blue"><b>Then</b></font>
      Result(I) = CopyTerm(AI)
    <font color="blue"><b>Else</b></font>
      Result(I) = AI
    <font color="blue"><b>End</b></font> <font color="blue"><b>If</b></font>
  <font color="blue"><b>Next</b></font>
  <font color="blue"><b>Return</b></font> Result
<font color="blue"><b>End</b></font> <font color="blue"><b>Function</b></font>
</pre>
</blockquote>

The very important feature of aliases is the transitivity. 


<blockquote>
<pre>
<font color="blue"><b>Dim</b></font> A, P, Q
A = 100
P = <font color="blue"><b>AddressOf</b></font> A
Q = <font color="blue"><b>AddressOf</b></font> P
MsgBox Q
</pre>
</blockquote>


It produces 100. In this case we are speaking that P and Q have common <i>terminal</i> A.
Operator TerminalOf returns terminal of variable. All non-aliases are fixed points of TerminalOf
operator. So, the TerminalOf(A) is A in the example above.


<p>
New assignment of alias to P variable discards old value of P. Therefore you can think about statement 

<blockquote>
<pre>
P = <font color="blue"><b>AddressOf</b></font> L
</pre>
</blockquote>

as 2 statements

<blockquote>
<pre>
<font color="blue"><b>delete P</b></font>
P = <font color="blue"><b>AddressOf</b></font> L
</pre>
</blockquote>