In Lisp, should lists be replaced with trees?

http://www.hxa.name/notes/note-hxa7241-20110515T0907Z.html

by bawatski • 15 years ago

47 40 15 years ago

riffraff• 15 years ago

not directly lisp related, but the team working on Fortress has some interesting work on using "conc lists" (pairs, and trees as a combination of pairs) as a basic unit of work for parallel processing[1], the analysis quite naturally considers its relation with lisp ad cons lists in other languages.

[1] http://labs.oracle.com/projects/plrg/Publications/ICFPAugust...

p4bl0• 15 years ago

Also, Guy Steele is one of the two inventor of Scheme. So it may not be directly lisp related, but it definitely is indirectly lisp related ;-).

jerf• 15 years ago

I think that's directly related. The answer to the question "Why should we replace our lists?" is that you can avoid known failure cases with lists at a relatively small price in complexity and memory in the worst case, and sometimes get big gains. Singly-linked lists are not suitable for a concurrent world and functional programming really needs to stop putting lists on a pedestal and writing them into their very syntax. There's actually other problems they cause, too, but the concurrent problem is a real killer, because you can not just program your way around it, you need a fundamentally different data structure.

vukk• 15 years ago

http://vimeo.com/6624203 Conc lists as video. Titled Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful (Guy Steele)

mahmud• 15 years ago

He seems to have heard of Lua but that didn't stop him from raising the question.

Next article: "Should airplanes be fitted with big rotor on top to allow for vertical take off and hovering? .. like helicopters?"

daleharvey• 15 years ago

not that jets need a big rotor on top to do vertical takeoff and hovering

http://en.wikipedia.org/wiki/Harrier_Jump_Jet :)

alexg0• 15 years ago

The rotor on top has been done. http://en.wikipedia.org/wiki/V-22_Osprey

Turing_Machine2• 15 years ago

"Branchs/trees are a superset of pairs/lists"

No, they aren't. A tree is acyclic by definition. Cons cells allow circular structures.

Turing_Machine2• 15 years ago

To take a familiar example, the Web is not a tree. While you might argue that each page has unique children (outlinks), there is no unique parent -- a page can have an arbitrarily large number of incoming links, and the page can link back to those pages in turn, producing cyclic structures of immense complexity.

For some interesting discussion on the limits of tree structures with respect to urban planning see A City is Not a Tree by Christopher Alexander (who is also the inspiration for the Design Patterns movement in software engineering). http://www.rudi.net/node/317

Deestan• 15 years ago

All good, just a nitpick: You don't need a unique parent to have a tree. You don't even need directed edges. :)

The purest definition of a tree graph is "a graph with no cycles".

chalst• 15 years ago

And this is useful: you can represent the transitions of a state machine in this way, for instance.

omaranto• 15 years ago

The structures described are called trees in the post, but are actually just sets of named objects, which can be used to describe cyclic structures in the same way conses can.

Confusion• 15 years ago

The structure he calls a 'tree' allows cycles and is a generalization of a list. Whether he uses the correct word isn't really interesting: it doesn't detract anything from the post.

cswetenham• 15 years ago

A better reason to replace lists with trees might be for parallel execution. I enjoyed this talk by Guy Steele on replacing lists with trees in Fortress: http://vimeo.com/6624203

fexl6• 15 years ago

It's easy to implement both lists and name-value associations in terms of pairs, so I'm not sure why they need to be built in.

In Fexl (http://fexl.com/code), the only built in concept is the function, and all data is structured out of functions. I won't go into all the details here, but concepts like pair, list, key-value assoc, branch, and everything else are readily expressed as pure functions. So-called "circular" structures are created with the Y combinator, so they really are not circular in memory, only in concept.

jefffoster2• 15 years ago

There's an interesting write up about the idea of "everything is a function" in Haskell at http://conal.net/blog/posts/everything-is-a-function-in-hask....

What's your rationale vbehind everything being a function?

fexl6• 15 years ago

The seed was planted back in 1989 when I read a paper by Jørgen Steensgaard-Madsen in Communications of the ACM titled "Typed Representation of Objects by Functions" (CACM, January 1989, Volume 11 Number 1). I found it brilliant and I never could shake the idea after that.

Even something as lowly as a bit (Boolean value true or false) can be represented as a function. In Fexl, the functions for T and F are expressed as:

  \T = (\T\F T)
  \F = (\T\F F)

In short, the T function returns its first argument, and the F function returns its second argument. So you can do things like this:

  eq x 4 (print "Yes, it's 4") (print "No, it's not 4")

You don't even need an "if" function. Or, if you like the way "if" looks, you can define it as the identity function:

  \if = (\x x)

Then you can say:

   if (eq x 4) (print "Yes, it's 4") (print "No, it's not 4")

You can also define "lists" as functions. There are two cases, "null" and "cons":

  \null = (           \null\cons null)
  \cons = (\head\tail \null\cons cons head tail)

Now if you have a list called "groceries", you can do this:

  groceries
    (print "You don't need anything at the moment")
    \head\tail
      print "You need "; print head;
      print "and possibly some other things."

If you aren't comfortable "calling" a list object as a function, you can define the more familiar "observer" functions:

  \empty = (\list list T \_\_ F)
  \head = (\list list undef \head\_ head)
  \tail = (\list list undef \_\tail tail)

Then you could say:

  if (empty groceries)
    (print "You don't need anything at the moment")
    (print "You need "; print (head groceries);
      print " and possibly some other things.")

If you want an ordered pair, here you go:

  \pair = (\x\y \pair pair x y)

Now you can say:

  \the_pair = (pair 2.6 3.8)
  ...

  the_pair \x\y
    print "left is ";  print x;
    print "right is "; print y;

So, to sum it all up, I am just irresistibly attracted to the utter profundity of this concept. I like how the components of a piece of data simply "present themselves" to the handler function(s) applied to it. Also, you can name your data constructors anything you like -- there are no ultimately predefined names for anything, except any primitive combinators built into the C code, but even these can be shadowed or hidden. So if you want to use "item" and "end" instead of "cons" and "null", you can. (I do.) And if you want to use "first" and "rest" instead of "head" and "tail", you can.

If you like, you can download the code at http://fexl.com/code . One of these days I should put a sandboxed demo interpreter up on the site.

randallsquared• 15 years ago

Although I keep hearing “everything is a function” (and 3 is a nullary or constant function), I don’t hear people say “everything is a list”, and 3 is really the singleton list [3].

Well, in musings around Arc, pg did mention defining everything as a list, including 3 as [[] [] []], I believe. So, it's not that no one says it. :)

jefffoster2• 15 years ago

Will Thimbleby (http://will.thimbleby.net/misc-an-experimental-language/) also explored similar ideas.

agentultra2• 15 years ago

You can just build your tree data structure and develop operators to work with them in Lisp. There's nothing that restricts you to using lists.

So what's the point of "replacing" them (even if such a thing were possible without "replacing" Lisp)?

jasonwatkinspdx2• 15 years ago

Cons cells give you binary trees. It is possible to encode any arbitrary tree as a binary tree. However, this does not mean that the expression of algorithms over such left child right sibling encoded trees is identical to one over trees with some higher branching factor. So the cons/binary situation will at the least require some additional layers of abstraction to simulate various traversal patterns of the n way tree on the encoding binary tree.

There also physical/efficiency concerns. There's a reason databases use highly branching trees.

agentultra2• 15 years ago

And you can create the abstractions necessary to work with such a data structure and add them straight to the regular grammar of the language.

Lisp also has all of the other low-level primitives we're used to when working closer to the machine. Structs, indexed arrays, hashes, etc. If efficiency is a concern, just pick an implementation that compiles to machine code. SBCL is pretty good for this depending on your target platform.

Replacing conses seems like a waste of time.

skewsymmetry• 15 years ago

Lists are trees.

ericmoritz• 15 years ago

Wait, I thought trees are lists.

sesqu2• 15 years ago

No, trees are multidimensional lists. Lists are one-dimensional lists, which are degenerate trees and a simple primitive for the more general (always a loaded term) structure.

frobozz• 15 years ago

Wouldn't that make it a new language called Trep?

ohyes• 15 years ago

A list structure is already a 'dictionary tree', except it has lousy performance in access. (only really visible on large data sets).

* (second (assoc 5 '((1 2) (3 4) (5 6))))

> 6

The lousy performance doesn't matter, most of the time, because you have other data-structures for data, and your compiler generally is only interested in sequential access (constructing a parse tree out of it). The lisp code already being a tree makes parsing fairly simple...

So, I guess my point is that I don't see the point of this?

The only reason to really upgrade to a dictionary would be if you wanted to have non-sequential access to the contents of of your large-scale code-data-structure... generally the lists aren't large enough to merit it. You can do all of the dictionary operations on a list, and they are 'fast enough'. ----

I feel like the rationale here is created by conflating the idea of a cons and a list. I think generally, a list already accomplishes what the author sets out to accomplish.

They are a single step higher level than conses, and give you a hierarchical structure with the possibility for named associations. I don't really see how using something more complicated and memory intensive to build this basic data structure qualifies as an improvement...

fexl6• 15 years ago

> The lousy performance doesn't matter, most of the time, because you have other data-structures for data, and your compiler generally is only interested in sequential access ...

Exactly. Much of the time you don't care. The rest of the time, you can still use assoc-lists, except you create a branching structure on the keys such that no key in the list is a prefix of any other. The first entry of a node contains the value "at" that node, and the tail of the node is a list of branches, where each branch is a pair consisting of a string key and a child node.

The "get" and "put" functions in this structure are very simple recursive functions, and you can maintain very large dictionaries ("maps") this way. The get and put operations are essentially O(1), constant time, if you ignore the sheer length of the keys (which are usually reasonably short anyway). I've done tests where I insert hundreds of thousands of pseudo-random keys and values, and read them back, all very quickly and reliably. The code splits the keys into branching structures automatically. It's also a purely functional structure, so you can keep old versions of the maps.

The value at each node can be anything you like, not just a string, though to detect the absence of a value you need to use a "Maybe" type. In Fexl you can define constructors:

  \absent  = (       \absent\present absent)
  \present = (\value \absent\present present value)

So then the default value of a newly created branch is always absent, but a "put" operation replaces it with (present value). When you delete a key, it automatically detects if the node is empty (i.e. its value is absent and it has no branches) and then eliminates the node from its parent.

You also detect singleton nodes, which have an absent value and only one branch. In that case you can concatenate the key of that branch with the parent key upstairs, eliminating the extra branch.

abc_lisper• 15 years ago

Exactly. Rose by any name smells just as good.

pmb• 15 years ago

Lisp is already made of trees. A Lisp program is a pre-order traversal of the abstract syntax tree of a yacc'ed program in another programming language. This fact is WHY Lisp is powerful. By eliminating yaccing you can create new syntax on the fly without having to recompile your compiler.

hxa72412• 15 years ago

A few people have asked, what is the point? since trees and associative access can just be implemented with lists.

It is the same basic point as having 'let' or 'case' etc. (which can all just be implemented with 'lambda' and 'if' etc.) -- it is just a bit higher-level to program with.

With something that makes programming a little easier (maybe), probably the question ought really be, why shouldn't we have it?

fexl6• 15 years ago

I think the answer is we should have it, but it's just a library.

hxa72412• 15 years ago

OK. Then I suppose the question is: why should it be library not built-in?

The main thing not addressed in the article is: what are the language implementation implications? What are the pros and cons there?

dkarl• 15 years ago

By "replacing" lists with trees, am I supposed to understand that working with trees will be natural and easy, and lists will feel like second-class citizens? I thought we were beyond thinking like that. Building languages around a favorite data structure was never the right thing to do; it was always tunnel vision and bad design. Different data structures have different features and different performance characteristics. There's no reason for a language designer to pick a favorite data structure and force anyone who has to use a different one to deal with warts and second-class library and language support.

sambeau• 15 years ago

This is either a reinvention of ASTs or it's Graph Reduction.

http://en.wikipedia.org/wiki/Abstract_syntax_tree http://en.wikipedia.org/wiki/Graph_reduction

jasonwatkinspdx2• 15 years ago

You provided two things that the original post is a reinvention of. Which is it? Why not read the article enough to decide which it is a reinvention of, then present your thinking in your comment?

ScottBurson• 15 years ago

I wouldn't say lists should be replaced with trees, but adding a rich set of tree-based data structures to Lisp improves it substantially, in my view. To see what I mean, have a look at my FSet functional collections package, which does exactly that:

  http://common-lisp.net/project/fset/

Unlike what the OP is suggesting, FSet doesn't expose the internal structure of its trees. Instead it wraps them in a rich set-theoretic interface.

In Lisp, should lists be replaced with trees?

Related Stories