LISPPA Technology

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.

Representation of Lists
List Processing
Working with Binary Trees
Stacks and Queues
Two Way Linked Lists
More Detailed Description of the LISPPA Concepts
LISPPA and Symbolic Computation
LISPPA and COM Technology
Demos
Conclusions
References

Representation of Lists

In terms of polymorphic arrays one can formulate the following recursive definition of the linked list:

NULL is a list.
If L is a list, the one-dimensional array A with two elements A(0) and A(1) = L is a list too.

A(0) contains a value of the list item.

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:

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

paxBasic provides more easy solution to implement the same operation by the variant array constructor:

Dim L = [100, [200, [300, NULL]]]

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.

List Processing

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:

L = [50, L]

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:

Dim temp = Array(2)
temp(0) = 50
temp(1) = L
L = temp

L and temp variables are references. You assign references, not actual arrays in the third and fourth statements.

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:

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

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.

Let's assume we want to insert 150 between 100 and 200. The following statement sequence allows us to do it:

P = AddressOf L(1)
P = AddressOf P(1)   'insert before 200
P = [150, P]

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.

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

L = L(1)

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 statement

reduced L = L(1)

allows us to assign L(1) to L without the memory leak. This statement has the following semantics:

Dim temp = L(1)
L(1) = NULL
delete L
L = temp

We can see, the reduced assignment statement is processed effectively.

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:

P = AddressOf L 
Do Until P(1) = NULL
  P = AddressOf P(1) 
Loop
reduced P = P(1)

The operation of removing items at the middle of the L list has the same unified form and concise notation:

P = AddressOf L
P = AddressOf P(1)
reduced P = P(1)

Finally, let's consider how to remove all items from the L list:

Do Until L = NULL
  Reduced L = L(1)
Loop

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.

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

Dim L = [100, [200, [300, NULL]]]
L[1][1][1] = AddressOf L

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.

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:

TerminalOf P = AddressOf W

Here is the LISPPA solution of the cycled list problem:

Dim L = [100, [200, [300, NULL]]]
P = AddressOf L
Do Until P = NULL 
 P = AddressOf P(1)
Loop
TerminalOf P = AddressOf L

The following statement sequence will print list items:

P = AddressOf L
I = 0
Do
  println P[0]
  P = AddressOf P[1]
  I += 1
Loop Until I = 15

It is necessary to note, the using of aliases can be considerably eliminated. Often we can use ordinary references instead of aliases.

For example, I can insert new item anItem into L list after the first item of L by means of

L[1] := [anItem, L[1]];

Furthermore, I might use the statement sequence

P := L[1];
P[1] := [anItem, P[1]];

to insert new item after the second item of L list.

However, I prefer to use aliases as they keep the structure of the statement of insertion:

P := [anItem, P];

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.

Working with Binary Trees

In terms of polymorphic arrays one can formulate the following recursive definition of the binary tree:

NULL is a binary tree
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.

A(0) contains a key of a node.

Lets's consider a simple program in paxBasic:

Dim 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

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

    Reduced R = NULL

instead of

    Delete R

to avoid explicit use of a deallocation operator.

Stacks and Queues

Empty linked stack is represented by unassigned variable Stack:

    Dim Stack

To push new item anItem into the stack, we use

    Stack = [anItem, Stack]

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

We can delete the top item with the statement

    Reduced Stack = Stack(1)

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:

If Head = NULL Then
  Tail = [anItem, NULL]
  Head = Tail
Else
  Tail(1) = [anItem, NULL]
  Tail = Tail(1)
End If

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

   Reduced Head = Head(1)

allows to delete items at the head of the queue.

Two Way Linked Lists

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.

To insert new item before the position specified by the P alias, we can use 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 Add function, which allows to add new item after the position specified by the P alias, can be expressed via Insert function:

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

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

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

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

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

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

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

More Detailed Description of the LISPPA Concepts

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

Polymorphic arrays. At present time, a lot programming languages use it.
Array constructors. Nothing new, again. The constructors allow to create new arrays by means of enumeration of the array elements.
Reduced assignment statements. The semantics of the statement can be expressed via already known concepts: assignment statement and delete operator. Let's consider it in detail.
The reduced assignment
```
reduced A = E
```
means
```
Dim temp = E
E = NULL
delete A
A = temp
```
if A is an array and E is an element of A. Otherwise it means:
```
delete A
A = E
```
Aliases and terminals. paxBasic uses statement
```
P = AddressOf A
```
to assign P as alias of A. Another paxScript languages use different synax rules. So, paxPascal uses statement
```
P := @ A; 
```
paxC and paxJavaScript use
```
P = & A; 
```
Alias P of A variable substitutes the A variable in expressions. Most often aliases are used to operate with array elements. For example:
```
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
```
The very important feature of aliases is the transitivity.
```
Dim A, P, Q
A = 100
P = AddressOf A
Q = AddressOf P
MsgBox Q
```
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.
New assignment of alias to P variable discards old value of P. Therefore you can think about statement
```
P = AddressOf L
```
as 2 statements
```
delete P
P = 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 sequence
```
Dim A, P
A = 100
P = AddressOf A
MsgBox A
MsgBox P
delete P
MsgBox A
MsgBox P
```
produces
```
100
100
100
NULL
```
To destroy A by means of P, you have to use TerminalOf operator:
```
Dim A, P
A = 100
P = AddressOf A
MsgBox A
MsgBox P
delete TerminalOf P
MsgBox A
MsgBox P
```
These statements produce
```
100
100
NULL
NULL
```
Let's note there are only 2 places where you might use the TerminalOf operator.
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:
```
[Reduced][TerminalOf] Expr1 = [AddressOf [TerminalOf]] Expr2
```
The reduced modifier is used to avoid a memory leak. It has been considered above.
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:
```
Dim 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
```
It produces
```
300
300
300
500
```
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 example
```
Dim 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
```
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 statement
```
TerminalOf Q2 = AddressOf TerminalOf Q1
```
changes parameters, not source terms.

LISPPA and Symbolic Computation

The use of LISPPA considerably simplify the programming of symbolic computation in the imperative languages. Indeed, how one can characterize a language which is well-suited for the symbolic computations? Such language should provide a simple way for representation of terms and flexible control structures allowing to process terms. LISPPA-extension of such imperative languages as Pascal or Basic can ensure both conditions: array constructors provide a suitable way for the term representation, aliases allows to process terms effectively.

Let's consider an example written in paxBasic. This is the most general unifier algorithm, the heart of the theorem proving and logic 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 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.

LISPPA and COM Technology

A possibility to represent and to process complex data structures in LISPPA on the base of Variant data types can important for the COM technology. There are a few data types which are admissible in COM: selected scalar data types and variants. Let's suppose both the server and client of Automation supports LISPPA (as was stated above, LISPPA can be implemented as a simple extension of Variant type concept). For example, our server can contain an expert system and we pass set of facts to the expert system as a parameter. The set of facts can be easily represented as a variant array which contains terms as elements. Server will send to client a value represented as a term as well.

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.

Demos

You can try these demos with the paxScript IDE. (See Download section at www.paxscript.com).

Conclusions

LISPPA technology is based on 4 main concepts:
1. Polymorphic arrays.
2. Array constructors.
3. Reduced assignments.
4. Aliases or delegates of variable. Terminals.
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).
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.
LISPPA technology considerably simplify the processing of dynamic data structures in comparison with the technology based on the use of pointers. For example, the structure of statement which expresses operation of the insertion of item into the list
```
P = [NewItem, P]
```
and structure of statement which expresses operation of the removing item from the list
```
reduced P = P(1)
```
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.
Well known variant types can be easy extended to provide LISPPA. paxScript scripting engine implements LISPPA on the base of an extension of the Variant type. In particular, the alias type is a Variant sub-type. So LISPPA can be implemented in all programming systems which support the variant types.
LISPPA considerably extends the applicability of imperative programming languages in the symbolic computations and AI applications.
LISPPA can be important for the COM technology (representation and processing of data in Variants).
Java views pointers as something that are too much trouble to deal with, and therefore doesn't expose them to the programmer. .NET paradigm relaxes this strict limitation but does not allow the use of pointers in "normal" code. Therefore LISPPA technology can be important for both directions. (Variant types are absent in Java and .NET Frameworks however the support of LISPPA can be easily implemented).
Implementation LISPPA in paxJavaScript can be used as a background of possible development of ECMA standard of the JavaScript language.
The Variant types provide the most easy way of the LISPPA implementation. However, this is not a necessary condition. We might introduce new data types such as pa-integer (polymorphic array of integers), pa-double (polymorphic array of doubles) etc to privide the strict data typing in the processing of dynamic data structures and to increase the performance. More general, if T is a data type, we can consider pa-T, the polymorphic array of elements of T type.
LISPPA has theoretical value as it allows to concisely describe well-known data structures and algorithmes on the base of the concept of the polymorphic array. For example, linked lists, trees and graphs can be considered as partial cases of polymorphic array.

References

For the first time the use polymorphic arrays for the processing of dynamic data structures has been presented in the articles:

Baranovsky A.I. (1998) The Universal Programming Language VIRT. Kibernetika i sistemny analiz, ISSN 0023-1274, N5, Kiev, p. 130-150.
Baranovsky A.I. (1999) Using the VIRT Language for the Symbolic Computations, Artificial Intelligence, ISSN 1561-5359, N1, Donetsk, p. 59-69.
Baranovsky A.I. (1999) Using the VIRT Language for the Mechanical Theorem Proving. Kibernetika i sistemny analiz, ISSN 0023-1274, N6, p. 87-99 Kiev.