[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)
      )
  )