In Lisp, should lists be replaced with trees?

Although Fexl does have built-in functions for long int and double float values, it is possible to do without them.

There are a couple of ways to define integers as pure functions. One is unary notation, which is equivalent to the "3" example you cite above. So you'd have these two constructors:

  \zero = (   \zero\succ zero)
  \succ = (\N \zero\succ succ N)

And then the "add" would be:

  \add == (\x\y x y \n succ (add n y))

Or, using the ';' (right-pivot) to avoid nesting on the right (though sometimes that can be too clever by half):

  \add == (\x\y x y \n succ; add n y)

That works fine for some applications. But you can use binary notation as well, defining an integer as a list of bits, with the lowest-order bit first. Then the "add" function becomes:

  \add == (\x\y x y \bx\nx y x \by\ny
     \sum=(add nx ny)
     bx
        (by (cons F (inc sum)) (cons T sum))
        (cons by sum))

Where inc is:

  \inc == (\x x (cons T null) \b\n
     b (cons F (inc n)) (cons T n))

I think I transcribed that right, but I haven't tested it in a while. It's all surprisingly fast -- I was actually doing long division of 100 digit numbers years ago in reasonable time in this notation, including the conversion to decimal notation by repeated division by 10.

One of these days I need to link a big number library into Fexl, but it hasn't been a priority for me. (Actually I need to think seriously about dynamically linked libraries, with linkage control done in Fexl itself. This can be sandboxed for secure applications, of course.)

Oh and here's my old division function, which again I haven't tested in a while, so no warranties expressed or implied:

  #---------------------------------------------------------------------------
  # (nat:div x y) divides x by y.  It yields a pair , where q is the
  # quotient and r is the remainder.
  #
  # The result satisfies the equation x = q*y + r,  0 .
  #---------------------------------------------------------------------------
  \nat:div==(\x\y\:
      x (: null null) \bx\nx
      y (: null null) \by\ny
      by
      (
          # divide by odd - recur on x only
          nat:div nx y \q\r
              \r=(bx nat:2x1 nat:2x r)
              \d=(nat:sub r y)
              int:ge0 d
                  (: (nat:2x1 q) (int:abs d))
                  (: (nat:2x q) r)
      )
      (
          # divide by even - recur on x and y
          nat:div nx ny \q\r
              : q (bx nat:2x1 nat:2x r)
      )
  )

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.

> 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.

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?

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?