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.
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.
A very important example of polymorphic arrays is variant arrays 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 paxScript scripting engine: paxPascal, paxBasic, paxC, paxJavaScript support LISPPA.
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:
paxBasic provides more easy solution to implement the same operation by the variant array constructor:Dim L, A1(1), A2(1), A3(1) A3(0) = 300 A2(0) = 200 A2(1) = A3 A1(0) = 100 A1(1) = A2 L = A1
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.Dim L = [100, [200, [300, NULL]]]
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:L = [50, L]
L and temp variables are references. You assign references, not actual arrays in the third and fourth statements.Dim temp = Array(2) temp(0) = 50 temp(1) = L L = temp
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.
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:
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 = AddressOf L 'Create alias of L Do Until P = NULL 'Find tail of L P = AddressOf P(1) Loop P = [400, P] 'Add new item at the tail of L
Let's assume we want to insert 150 between 100 and 200. The following statement sequence allows us to do it:
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 = AddressOf L(1) P = AddressOf P(1) 'insert before 200 P = [150, 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.
The first possible solution
is not quite correct because it will produce a memory leak. The LISPPA extends the ordinary assignment statement with the reduced modifier. The reduced assignment statementL = L(1)
allows us to assign L(1) to L without the memory leak. This statement has the following semantics:reduced L = L(1)
We can see, the reduced assignment statement is processed effectively.Dim temp = L(1) L(1) = NULL delete L L = temp
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:
The operation of removing items at the middle of the L list has the same unified form and concise notation:P = AddressOf L Do Until P(1) = NULL P = AddressOf P(1) Loop reduced P = P(1)
Finally, let's consider how to remove all items from the L list:P = AddressOf L P = AddressOf P(1) reduced P = P(1)
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.Do Until L = NULL Reduced L = L(1) Loop
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
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.Dim L = [100, [200, [300, NULL]]] L[1][1][1] = AddressOf L
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:
Here is the LISPPA solution of the cycled list problem:TerminalOf P = AddressOf W
The following statement sequence will print list items:Dim L = [100, [200, [300, NULL]]] P = AddressOf L Do Until P = NULL P = AddressOf P(1) Loop TerminalOf P = AddressOf L
It is necessary to note, the using of aliases can be considerably eliminated. Often we can use ordinary references instead of aliases.P = AddressOf L I = 0 Do println P[0] P = AddressOf P[1] I += 1 Loop Until I = 15
For example, I can insert new item anItem into L list after the first item of L by means of
Furthermore, I might use the statement sequenceL[1] := [anItem, L[1]];
to insert new item after the second item of L list.P := L[1]; P[1] := [anItem, P[1]];
However, I prefer to use aliases as they keep the structure of the statement of insertion:
which is uniform one, i.e. it does not depend from the position of insertion (at the top, at the middle, at the tail of list). You are moving alias, not changing structure of the statement.P := [anItem, P];
Lets's consider a simple program in paxBasic:
You can see, the representation of algorithmes is very concise. Note, we preferDim Key = 0, Left = 1, Right = 2 Sub AddNode(Root, X) If Root = NULL Then Root = [X, NULL, NULL] ElseIf X < Root(Key) Then AddNode(AddressOf Root(Left), X) ElseIf X > Root(Key) Then AddNode(AddressOf Root(Right), X) End If End Sub Function Search(Root, X) If Root = NULL Then Return NULL ElseIf X = Root(Key) Then Return Root ElseIf X < Root(Key) Then Return Search(Root(Left), X) Else Return Search(Root(Right), X) End If End Function Sub DeleteNode(Root, X) Dim P, R R = Search(Root, X) If R = NULL Then Exit Sub ElseIf (R(Left) = NULL) And (R(Right) = NULL) Then Reduced R = NULL ElseIf R(Left) = NULL Then Reduced R = R(Right) ElseIF R(Right) = NULL Then Reduced R = R[Left] Else P = AddressOf R(Left) Do Until P(Right) = NULL P = AddressOf P(Right) Loop R(Key) = P(Key) Reduced P = P(Left) End If End Sub Sub InOrder(Root) If Root <> NULL Then InOrder(Root(Left)) println Root(Key) InOrder(Root(Right)) End If End Sub Dim Tree, X AddNode(AddressOf Tree, 10) AddNode(AddressOf Tree, 5) AddNode(AddressOf Tree, 15) AddNode(AddressOf Tree, 3) AddNode(AddressOf Tree, 8) AddNode(AddressOf Tree, 13) AddNode(AddressOf Tree, 18) println Tree PreOrder(Tree) X = Search(Tree, 5) println X DeleteNode(AddressOf Tree, 10) println Tree
instead ofReduced R = NULL
to avoid explicit use of a deallocation operator.Delete R
To push new item anItem into the stack, we useDim Stack
The top item of the stack is available as Stack(0).Stack = [anItem, Stack]
We can delete the top item with the statement
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:Reduced Stack = Stack(1)
The first item of the queue is available as Head(0), Tail(0) returns the last item. The statementIf Head = NULL Then Tail = [anItem, NULL] Head = Tail Else Tail(1) = [anItem, NULL] Tail = Tail(1) End If
allows to delete items at the head of the queue.Reduced Head = Head(1)
To insert new item before the position specified by the P alias, we can use function:
The Add function, which allows to add new item after the position specified by the P alias, can be expressed via Insert function:Function Insert(Value, P) Dim result = [Value, P] If P <> null Then P.Owner = result End If P = result return P End Function
The Find function returns alias of item which contains the Key value or null if such item is absent:Function Add(Value, P) Dim result If P = null Then result = Insert(Value, P) Else result = Insert(Value, AddressOf P(1)) result.Owner = P End If return result End Function
We can remove an item at the position given by the Value parameter with the Remove function:Function Find(Key, P) Dim result = AddressOf P Do While result <> null If result(0) = Key Then Return result End If result = AddressOf result(1) Loop Return null End Function
The BackwardOrder function allows to print list items in the backward order:Function Remove(Value, L) Dim temp, result result = AddressOf Find(Value, L) If result <> null Then temp = result.Owner Reduced result = result(1) If result <> null Then result.Owner = temp End If End If End Function
Sub BackwardOrder(A) Dim P If A = null Then println A Else P = A Do While P(1) <> null ' Find last item P = P(1) Loop Do While P <> null Println P(0) P = P.Owner Loop End If End Sub
The reduced assignment
meansreduced A = E
if A is an array and E is an element of A. Otherwise it means:Dim temp = E E = NULL delete A A = temp
delete A A = E
to assign P as alias of A. Another paxScript languages use different synax rules. So, paxPascal uses statementP = AddressOf A
paxC and paxJavaScript useP := @ A;
Alias P of A variable substitutes the A variable in expressions. Most often aliases are used to operate with array elements. For example:P = & A;
The very important feature of aliases is the transitivity.Function CopyTerm(A) Dim I, AI, Result Result = PaxArray(A.Length) For I=0 To A.Length - 1 AI = AddressOf A(I) If IsCompound(AI) Then Result(I) = CopyTerm(AI) Else Result(I) = AI End If Next Return Result End Function
It produces 100. In this case we are speaking that P and Q have common terminal 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.Dim A, P, Q A = 100 P = AddressOf A Q = AddressOf P MsgBox Q
New assignment of alias to P variable discards old value of P. Therefore you can think about statement
as 2 statementsP = AddressOf L
The first statement is implied, you have no a need to use it explicitly. Note, the delete statement destroys P variable, not terminal of P. So, the statement sequencedelete P P = AddressOf L
producesDim A, P A = 100 P = AddressOf A MsgBox A MsgBox P delete P MsgBox A MsgBox P
To destroy A by means of P, you have to use TerminalOf operator:100 100 100 NULL
These statements produceDim A, P A = 100 P = AddressOf A MsgBox A MsgBox P delete TerminalOf P MsgBox A MsgBox P
Let's note there are only 2 places where you might use the TerminalOf operator.100 100 NULL NULL
The first place is the delete statement. You can delete either P or terminal of P.
The second place is the assignment statement. The assignment statement has the following grammar:
The reduced modifier is used to avoid a memory leak. It has been considered above.[Reduced][TerminalOf] Expr1 = [AddressOf [TerminalOf]] Expr2
The TerminalOf at the left part of the assignment statement should be used only when Expr1 is alias and AddressOf is presented at the right part of the statement. (Because TerminalOf Expr1 = Expr2 produces the same assignment as Expr1 = Expr2 in all another cases). When AddressOf is presented at the right part, the use of TerminalOf in the left part allows you to assign alias of Expr2 to terminal of Expr1. For example:
It producesDim A[10], B, C, P B = 300 C = 500 P = AddressOf A(5) TerminalOf P = AddressOf B MsgBox P MsgBox A[5] P = AddressOf C MsgBox A[5] MsgBox P
The TerminalOf at the left part of the assignment statement should be used only when Expr2 is an alias. In this case, the use of TerminalOf allows you to assign Expr1 as alias of terminal of Expr2. For example300 300 300 500
This example illustrates how the search of most general unifier works (mechanical theorem proving). T1 and T2 represent terms, P1 and P2 are parameters of T1 and T2 accordingly. The last statementDim P1 = "X" Dim P2 = "Y" Dim T1 = ["R", ["F", AddressOf P1]] Dim T2 = ["R", AddressOf P2] Dim Q1 = AddressOf T1[1] Dim Q2 = AddressOf T2[1] TerminalOf Q2 = AddressOf TerminalOf Q1
changes parameters, not source terms.TerminalOf Q2 = AddressOf TerminalOf Q1
Let's consider an example written in paxBasic. This is the most general unifier algorithm, the heart of the theorem proving and logic programming:
The most general unifier algorithm is the "litmus paper" of applicability of a programming language for symbolic computations. While functional languages offer simple solutions, the imperative languages based on using pointers will increase the complexity of the implementation of the algorithm. The example above shows a simple solution in the imperative style of the programming.Function Unify(N As Integer, T1 As Variant, T2 As Variant) As Boolean Dim I As Integer Dim P1, P2 As Variant For I=N to T1.length - 1 P1 = AddressOf T1(I) P2 = AddressOf T2(I) If IsCompound(P1) And IsCompound(P2) Then If Not Unify(0, P1, P2) Then Return false End If ElseIf IsVar(P1) And (Not Inside(P1, P2)) Then TerminalOf P1 = AddressOf TerminalOf P2 ElseIf IsVar(P2) And (Not Inside(P2, P1)) Then TerminalOf P2 = AddressOf TerminalOf P1 ElseIf P1 <> P2 Then Return false End If Next Return true End Function
The LISPPA allows you to transfer complex data structures between server and
client without having to encode/decode the data. It can considerably increase the total speed of data
processing at both sides. LISPPA provides an uniform way for the data representation.
The third concept is optional as it can be expressed via already known concepts.
Aliases and terminals are not new concepts too, I have adjusted their semantics for the processing
of polymorphic arrays.
Demos
You can try these demos with the paxScript IDE. (See Download
section at www.paxscript.com).
Conclusions
The first 2 concepts are not new, they are presented in many programming languages. Just let's remind:
a variable of a polymorphic array type is actually a reference. Hence more than one variable
can refer to the same polymorphic array. The assignment statement executes copying references, not actual
arrays. The copy of A array can be created by the unary plus operator (+ A).
and structure of statement which expresses operation of the removing item from the list
P = [NewItem, P]
are uniform. In another words, they are do not depend from the position of insertion or deleting
(at the top, at the middle, at the tail of list). You are moving alias, not changing structure of the
statement. Both operations are expressed by single statement. You do not use allocation and deallocation of
memory explicitly. The programming of the dynamic data structures becomes more safe and free of bugs.
reduced P = P(1)
References
For the first time the use polymorphic arrays for the processing of dynamic data structures has been
presented in the articles:
Copyright © 1999-2006
VIRT Laboratory. All rights reserved.