Framework for self-referential data structures: ConsList and ConsTree
By Athina Kyriazi
University of Patras
By Athina Kyriazi
University of Patras
[Abstract: Is it possible to operate in Self-Referential Expressions? For which of those is it worth making framework? ConsList and ConsTree are two self referential types that are being introduced in this community post. It includes new function definitions (ex. constructors) and properly modified functions from the List and the Tree Framework in order to be able to operate on these types.]
Initialization
Initialization
Introduction
Introduction
Is it possible to operate on Self-Referential Expressions?
Is it possible to operate on Self-Referential Expressions?
Issues
Issues
Can expressions like x={x,x} be interpreted from the computer and what result are we anticipating from it?
The result that we receive is the following:
The result that we receive is the following:
In[]:=
x={x,x}
Out[]=
Hold[{x,x}]
and now is the point that we ask ourselves: Why?
Basically what we did is: we created an infinite search loop which goal was to define the symbol x
Basically what we did is: we created an infinite search loop which goal was to define the symbol x
LOOP DISCRIPTION
x={x,x} -> Initialize symbol x with expression {x,x} ->Evaluate@ {x,x} : List of elements that kernel needs to evaluate -> Evaluate[x] -> Searching for the value of x -> x={x,x}
x={x,x} -> Initialize symbol x with expression {x,x} ->Evaluate@ {x,x} : List of elements that kernel needs to evaluate -> Evaluate[x] -> Searching for the value of x -> x={x,x}
The kernel detects this loop and applies Hold to the {x,x} expression in order to prevent infinite evaluation
Hold solution
Hold solution
If we were to apply Hold on top of the expression, we would prevent its evaluation from the kernel. This way, we can execute the code:
In[]:=
x=Hold[{x,x}]
Out[]=
Hold[{x,x}]
Answer
Answer
Yes, with proper handling. Helpful tools: Hold, HoldFirst, HoldRest, HoldForm, HoldPattern, HoldAll
Are there any MEANINGFUL Self-Referential Expressions?
Are there any MEANINGFUL Self-Referential Expressions?
Examples
Examples
cons:=cons[cons]cons:=cons[x,cons]
Answer
Answer
By assuming: meaningful <=> can be applied to solve a problems
1. First approach: extending existing Data Structures that exist in the Wolfram Language, which already have the “meaningful” attribute
2. Second approach: introduce a new Data Structure and reasoning its existence with an application
In this project, the first approach is being followed. Although, some ideas of other self referential data structures are being displayed in the examples above, none of them reasons its existence, so they can’t be properly introduced.
1. First approach: extending existing Data Structures that exist in the Wolfram Language, which already have the “meaningful” attribute
2. Second approach: introduce a new Data Structure and reasoning its existence with an application
In this project, the first approach is being followed. Although, some ideas of other self referential data structures are being displayed in the examples above, none of them reasons its existence, so they can’t be properly introduced.
List and ConsList
List and ConsList
ConsList Definition
ConsList Definition
In order to create an infinite list, I need to store each time the element that is placed in a specific position and a reference to the next ConsList object.
-Expression form of the ConsList object:
ConsList[ ID, next ]
-Expression form of multiple ConsList objects (infinite list, one-sided infinite “chain” of ConsList objects):
ConsList[ ID1, ConsList[ ID2, ConsList[ ID3, ...]]]
-Expression form of the ConsList object:
ConsList[ ID, next ]
-Expression form of multiple ConsList objects (infinite list, one-sided infinite “chain” of ConsList objects):
ConsList[ ID1, ConsList[ ID2, ConsList[ ID3, ...]]]
1st attempt: infiniteOnes is a function that defines a cons symbol in its body with arguments 1 and infiniteOnes (not successful)
Calling infiniteOnes -> Evaluate[cons[1, infiniteOnes]] -> Evaluate[1] and Evaluate[infiniteOnes] -> Calling infiniteOnes
As a result we have an “infinite” infiniteOnes recursion which results cons to be a self referential data structure
Calling infiniteOnes -> Evaluate[cons[1, infiniteOnes]] -> Evaluate[1] and Evaluate[infiniteOnes] -> Calling infiniteOnes
As a result we have an “infinite” infiniteOnes recursion which results cons to be a self referential data structure
In[]:=
infiniteOnes:=ConsList[1,infiniteOnes]
not successful
In[]:=
infiniteOnes
Out[]=
Hold[ConsList[1,infiniteOnes]]
prevent loop with HoldRest : ConsList doesn’t evaluate its arguments except from the first one ( 1 can’t be further evaluated because its an atom, in case of 1+1 as first argument: {{1+1},2})
In[]:=
SetAttributes[ConsList,HoldRest]
successful
In[]:=
infiniteOnes
Out[]=
ConsList[1,infiniteOnes]
Controllable ConsList expansion - New function definitions
Controllable ConsList expansion - New function definitions
controllable ConsList expansion: (the following function ended up being introduced in the final framework)
Basic code features:
-applying evaluation on top of Hold overcomes the Hold attribute and lets the kernel evaluate the expression. In the following code, Evaluation is allowed until a certain extend which is specified by the variable n.
-n variable countdown
-while n!=1 Evaluation of the second argument is forced
-if n==1 ConsList element is return without influencing the default HoldRest attribute
Basic code features:
-applying evaluation on top of Hold overcomes the Hold attribute and lets the kernel evaluate the expression. In the following code, Evaluation is allowed until a certain extend which is specified by the variable n.
-n variable countdown
-while n!=1 Evaluation of the second argument is forced
-if n==1 ConsList element is return without influencing the default HoldRest attribute
In[]:=
ExpandConsList[ConsList[ID_,next_],n_]:=ConsList[ID,Evaluate[ExpandConsList[next,n-1]]]ExpandConsList[ConsList[ID_,next_],1]:=ConsList[ID,next]
In[]:=
ExpandConsList[infiniteOnes,5]
In[]:=
ExpandConsList[infiniteOnes,100]
In order to visualize the self reference between the ConsList objects we can use the following code (this is implemented by the function DisplayConsList which is included in the code of the project)
In[]:=
ExpandConsList[infiniteOnes,10]//ExpressionTree
Out[]=
Connection between ConsList and List - Existing List Framework extension
Connection between ConsList and List - Existing List Framework extension
controllable ConsList expansion and conversion into a list:
Basic code features:
-!calling a function with “next” as argument! (implicit Hold overcome)
Although “next” isn’t evaluated in the ConsList[ID, next] expression, nothing prevents it from being evaluated when being an argument in another function
-Prepend method: known programming logic when working with recursion and list initialization ( takes care of the list order
Basic code features:
-!calling a function with “next” as argument! (implicit Hold overcome)
Although “next” isn’t evaluated in the ConsList[ID, next] expression, nothing prevents it from being evaluated when being an argument in another function
-Prepend method: known programming logic when working with recursion and list initialization ( takes care of the list order
toList[ConsList[ID_,next_],n_]:=Prepend[toList[next,n-1],ID]/;n>1toList[ConsList[ID_,next_],n_]:={ID}/;n==1toList[ConsList[ID_,next_],n_]:={}/;n<=0
In[]:=
toList[infiniteOnes,10]
Out[]=
{1,1,1,1,1,1,1,1,1,1}
The above function can be translated into a list-framework function. Therefore the above function isn’t used in the actual project. (Purpose: logic reasoning why extending existing list framework)
Tree and ConsTree
Tree and ConsTree
ConsTree Definition
ConsTree Definition
In order to create an infinite tree, I need to store the node’s ID and a reference to the a list of the next ConsTree objects which can be referred to as leaves.
-Expression form of the ConsTree object:
ConsTree[ID, nextChildren] nextChildren: list of ConsTree elements
-Expression form of multiple ConsTree objects (infinite list, one-sided infinite “chain” of ConsList objects):
ConsTree[ID1.1, {ConsTree[ID2.1, {...}],ConsTree[ID2.2, {...}], ...}]
ConsTree type follows the way that Tree elements are defined in order to be compatible, with small alterations, with the built-in Tree functions (For detailed explanation on the HoldRest attribute: List and ConsList / ConsList Definition)
-Expression form of the ConsTree object:
ConsTree[ID, nextChildren] nextChildren: list of ConsTree elements
-Expression form of multiple ConsTree objects (infinite list, one-sided infinite “chain” of ConsList objects):
ConsTree[ID1.1, {ConsTree[ID2.1, {...}],ConsTree[ID2.2, {...}], ...}]
ConsTree type follows the way that Tree elements are defined in order to be compatible, with small alterations, with the built-in Tree functions (For detailed explanation on the HoldRest attribute: List and ConsList / ConsList Definition)
In[]:=
SetAttributes[ConsTree,HoldRest]
In[]:=
myTree=ConsTree[0,{ConsTree[1,{ConsTree[2,next],ConsTree[2,next]}],ConsTree[1,{ConsTree[2,next1],ConsTree[2,next]}],ConsTree[1,{ConsTree[2,next],ConsTree[2,next]}]}]
In order to create an infinite Tree, a pattern is needed (a rule which determines the next leaves based on the value of the source node). Therefore, f returns a list and applies a certain rule to each node.
In[]:=
NestConsTree[f_,initialID_]:=ConsTree[initialID,NestConsTree[f,#]&/@f[initialID]]
In[]:=
quickTree=NestConsTree[{2*#,3*#,4*#}&,1]
Out[]=
ConsTree[1,(NestConsTree[{2#1,3#1,4#1}&,#1]&)/@({2#1,3#1,4#1}&)[1]]
Connection between ConsTree and Tree - Extend the existing Tree Framework
Connection between ConsTree and Tree - Extend the existing Tree Framework
Basic Idea of the ConsTree code mapping the extended built-in functions into each one of the leaves that source from each node
In order to find the connection of ConsTree and Tree, a function which replaces the head ConsTree with Tree so that the Tree form can be displayed as output + implicit evaluation of hold element (explained in more detail in a similar example : List and ConsList / Controllable ConsList expansion - New function definitions)
Because the project has as ConsTree constructor only the NestConsTree function
Because the project has as ConsTree constructor only the NestConsTree function
In[]:=
ConsTree/:RootTree[ConsTree[ID_,nextChildren_],n_]:=Tree[ID,RootTree[#,n-1]&/@nextChildren]ConsTree/:RootTree[ConsTree[ID_,nextChildren_],0]:=ID
In[]:=
myTree=ConsTree[0,{ConsTree[1,{ConsTree[2,next],ConsTree[2,next]}],ConsTree[1,{ConsTree[2,next1],ConsTree[2,next]}],ConsTree[1,{ConsTree[2,next],ConsTree[2,next]}]}]
In[]:=
quickTree=NestConsTree[{f[#],g[#],h[#]}&,1]
Out[]=
ConsTree[1,(NestConsTree[{f[#1],g[#1],h[#1]}&,#1]&)/@({f[#1],g[#1],h[#1]}&)[1]]
In[]:=
RootTree[quickTree,3]
Out[]=
In[]:=
RootTree[myTree,2]
Out[]=
ConsList
ConsList
Construction
Construction
The following functions are used for the construction of ConsList objects:
InfiniteSteps
InfiniteSteps
creates a ConsList object with all the positive powers of 2
creates a ConsList object with all the negative powers of 2
creates a ConsList object with all negative numbers
InputSequence
InputSequence
arbitrary sequence:seq[n]=seq[n-1]^2+seq[n-5]
Quick Access (ConsListRange, InfiniteSames)
Quick Access (ConsListRange, InfiniteSames)
1. Function Repository Reference: ConsListRange
2. Function Repository Reference: InfiniteSames
Manipulation
Manipulation
The following functions are used for the manipulation of ConsList objects:
Combination of the extended List-Framework
Combination of the extended List-Framework
New functions
New functions
ExpandConsList, DisplayConsList, ConsListMapThread, NestConsList
Application Examples
Application Examples
Primes
Primes
Fibonacci Sequence
Fibonacci Sequence
2D infinity
2D infinity
In this example, a ConsList object element is created which has as ID another ConsList object. As a result, one could imagine the final structure having 2 infinite “degrees of freedom”
Defining the variables that determine the expansion extend
Show 2 independent expansions with the help:
1.the symbol f acting as a function with one argument and NestConsList function which creates the internal ConsList elements
2.the external ConsList elements are created by ConsListRange[1,1] (basic nats ConsList)
1.the symbol f acting as a function with one argument and NestConsList function which creates the internal ConsList elements
2.the external ConsList elements are created by ConsListRange[1,1] (basic nats ConsList)
Display internal ConsList expression
replace f with #^2 squaring each element in order to define the next one in the internal ConsList
ConsTree
ConsTree
Construction
Construction
The following function is used for the construction of ConsTree objects:
ConsNestTree
ConsNestTree
creates an infinite tree by applying the specified (1st argument) rule to each node, start node: 0
Manipulation
Manipulation
The following functions are used for the manipulation of ConsTree objects:
Combination of the extended Tree-Framework
Combination of the extended Tree-Framework
Application Example
Application Example
Letter Combinations
Letter Combinations
Conclusion
Conclusion
List problems - What ConsList offers?
List problems - What ConsList offers?
1. Smaller code size (shorter and more compact expressions)
because one expression includes multiple lists
because one expression includes multiple lists
2. Infinite attribute ( Memory limitations )
Why self-reference instead of Iteration?
Why self-reference instead of Iteration?
1. Functional programming approach
2. Smaller code size (shorter expressions)
Possible model extensions
Possible model extensions
The following parts of code are not included in the code of the project. These are just suggestion and different ways of approaching the consList type (utilize the flexibility of the model, don’t just stick with the above models)
Keywords
Keywords
◼
infinite list
◼
infinite tree
◼
Hold / Evaluate
◼
Self reference / Recursion
Acknowledgment
Acknowledgment
This project wouldn’t be possible without the help of my mentors Christopher Wolfram and Bradley Klee. Sotiris Michos contributed as well. Special thanks also to Dr. Stephen Wolfram for assigning me this project. The other great part of this experience was having lots of peers to work with and a fun team for project meetings.
References
References