2 ms·
In the area of programming languages and compilers, we usually have trees without parent links, with substructure sharing, which are DAGs. We call them trees be
by kazinator 3y ago
In the area of programming languages and compilers, we usually have trees without parent links, with substructure sharing, which are DAGs. We call them trees because most of the code operating on them thinks they are.
E.g. the Lisp expression (+ a (* b b)), informally called a syntax tree, is actually a DAG. Both apparent instances of the b symbol are actually graph edges leading to the same symbol object. Moreover, nothing points to its parent; that would be horrible.
Other kinds of trees don't always have parent pointers. For instance search trees like red-black can be implemented with parent pointers, or without; e.g. with functional recursion.
- IshKebab 3y ago> E.g. the Lisp expression (+ a (* b b)), informally called a syntax tree, is actually a DAG That is a syntax tree. Syntactically it is a tree. The fact that you have a later step that recognises that the `b` identifiers refer to the same object and turn it into a DAG doesn't mean it isn't a tree initially.
- kazinator 3y agoMost of the time when the word "tree" is used in this context, it is in reference to that DAG, not the printed version. E.g. see the tree and tree-structure glossary entries in ANSI CL. https://www.lispworks.com/documentation/lw61/CLHS/Body/26_glo_t.htm https://www.lispworks.com/documentation/lw61/CLHS/Body/26_gl...