[fexl]

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.

[jefffoster]

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?

[fexl]

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]

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

[fexl]

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 <q,r>, where q is the
  # quotient and r is the remainder.
  #
  # The result satisfies the equation x = q*y + r,  0 <= r < y.
  #
  # NOTE:  If you divide by zero, the function yields the pair <0,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)
      )
  )