No primitive data types: Intuitions about how data is represented in Fencore

The original inspiration for Fencore came from the lambda calculus, combinatory logic, and functional programming. Fencore isn't based on any of these, exactly, and you don't have to understand them before you can understand Fencore, but it is in many ways similar to these systems. In this post, I'll use some concepts from these systems to give you some intuitions about how data is represented in Fenfire. (The reason Fenfire does not actually use these systems is that data structures formulated in them are not very extensible. I'll explain this further in a furture blog post.)

In combinatory logic, everything is described by terms, which are either constants or the application of one term (representing a one-argument function) to another term (representing the function's argument). For example, to represent the natural numbers, you could use two constants: zero and succ (the successor function, taking a natural number n and returning n+1). Application of a function to an argument is usually written (f a). Then, you have,

    0 = zero
    1 = (succ zero)
    2 = (succ (succ zero))

etc. A function F(a,b) with two arguments is represented as a one-argument function f such that (f a) is a function which takes b and returns F(a,b); so F(a,b) = ((f a) b). This is abbreviated as (f a b). So you could represent lists using nil and cons: the empty list is nil, and the list [a]+rest is (cons a rest).

Pure functional programming languages, like Haskell, use this technique for representing data structures, such as lists and trees, but not for natural numbers and characters.

If your programs represent data like this, it becomes much easier to use logic to prove things about these programs; you don't need to introduce special rules for every sort of data you want to represent. (For comparison, look at the formal semantics some researchers have created for languages like Java, if you want to see how much it takes to make your head explore.) As a simple example, you can define addition and multiplication in your language itself

    (add ?x zero)      = ?x
    (add ?x (succ ?y)) = (succ (add ?x ?y))
    (mul ?x zero)      = zero
    (mul ?x (succ ?y)) = (add ?x (mul ?x ?y))

and then prove

    (mul ?x (add ?y ?z)) = (add (mul ?x ?y) (mul ?x ?z))

In fact, using Haskell, you could in theory do that for datastructures like lists -- on paper. If you take a university course about functional programming, be prepared to do that for some examples about as complicated as the one above. The language and compiler don't include tools that would make this sort of thing useful in the real world, though. I'm told that internally, Haskell compilers make use of this sort of reasoning a lot, but it's not exposed at the user level.

So in Fencore, all data is by default stored in a way similar to this (the difference is that it's RDF triples rather than function applications); when that's too slow, you devise some other way to store it, and use the built-in logic that it does the right thing.

For example, when representing numbers in binary, you would first represent binary numbers as terms -- for example, add the constants zeroBit and oneBit, and define a binary number to be a cons/nil list bits. Second, you would tell the computer how the inefficient representation (succ/zero) is defined in terms of the efficient operation (list of bits). Third, you would do some implementation magic to cause the bit lists to be represented as actual blocks of memory, and to cause operations that are primitive in the underlying system (add and mul, say) to be implemented using these primitives.

(The above description ignores the fact that a machine word is limited size and that add wraps around. It would be this simple only if the underlying system supported arbitrarily large natural numbers already. If you wanted to map to int32, you'd first have to state explicitly that this only works for numbers smaller than 2^31.)

So why not just have numbers in the language definition from the beginning on? The most important reason is to keep the language and logic simple; if binary numbers look like they're terms, like everything else, you don't need special rules for them in the logic. Another important reason is to allow the user to add their own "native data types."

A not quite so important reason is that in my humble opinion, having this basic paradigm to unify everything and then breaking that paradigm for a couple of primitive data types is butt-ugly. I can understand doing it for pragmatic reasons, like in Java, but if your underlying paradigm allows you to avoid primitives and still be efficient, like in Fencore, then I see no point in having them.