Persistent data structure: Difference between revisions

Content deleted Content added
m Scala: fix capitalization
Citation bot (talk | contribs)
Add: publisher, date. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox3 | #UCB_webform_linked 1521/2306
Line 2:
{{Distinguish|Persistent storage}}
 
In [[computing]], a '''persistent data structure''' or '''not ephemeral data structure''' is a [[data structure]] that always preserves the previous version of itself when it is modified. Such data structures are effectively [[Immutable object|immutable]], as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjans' 1986 article.<ref name="Driscoll">{{Cite book |vauthors=Driscoll JR, Sarnak N, Sleator DD, Tarjan RE |date=1986 |title=Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 |year=1986 |chapter=Making data structures persistent |isbn=978-0-89791-193-1 |doi=10.1145/12130.12142 |journal=Proceeding STOC '86. Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing |pages=109–121|citeseerx=10.1.1.133.4630 |s2cid=364871 }}</ref>
 
A data structure is '''partially persistent''' if all versions can be accessed but only the newest version can be modified. The data structure is '''fully persistent''' if every version can be both accessed and modified. If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called '''confluently persistent'''. Structures that are not persistent are called ''ephemeral''.<ref name="kaplan2">{{Cite journal|author=Kaplan, Haim|year=2001|title=Persistent data structures|url=http://www.math.tau.ac.il/~haimk/papers/persistent-survey.ps|journal=Handbook on Data Structures and Applications}}</ref>
Line 177:
 
=== Prolog ===
Prolog terms are naturally immutable and therefore data structures are typically persistent data structures. Their performance depends on sharing and garbage collection offered by the Prolog system.<ref>{{Citation|title= The Implementation of Prolog - Patrice Boizumault|date=1993|isbn=9780691637709|url=https://press.princeton.edu/books/hardcover/9780691637709/the-implementation-of-prolog|last1=Djamboulian|first1=Ara M.|last2=Boizumault|first2=Patrice|publisher=Princeton University Press }}</ref> Extensions to non-ground Prolog terms are not always feasible because of search space explosion. Delayed goals might mitigate the problem.
 
Some Prolog systems nevertheless do provide destructive operations like setarg/3, which might come in different flavors, with/without copying and with/without backtracking of the state change. There are cases where setarg/3 is used to the good of providing a new declarative layer, like a constraint solver.<ref>{{Citation|title=The Use of Mercury for the Implementation of a Finite Domain Solver - Henk Vandecasteele, Bart Demoen, Joachim Van Der Auwera|date=1999|url=https://lirias.kuleuven.be/retrieve/440562}}</ref>