Skip to content
29 October 32010 / Robin Wellner

Programming language: Lith

This one has been fermenting in my head for a while. It was based on thinking about Lua and BrainFuck, about minimalism and how far you can push it. The name, Lith, is a portmanteau of Lisp and Forth, because it looks more like either of those than Lua or BF.

Imagine a programming language with only two datatypes.

Why two? Well, you’d need a compound datatype at the very least, because otherwise you could represent nothing more than the datatypes that are built in. And since we’re being minimalistic, we wouldn’t have many. Let’s say a list, because they are conceptually simple to grasp. Excellent! We can now represent any tree that doesn’t have information attached other than what child nodes it has. In fact, you can represent any kind of data with it, although it won’t be pretty or easy to work with. (To see why that is, first agree with me that any kind of information can be represented by binary. Next, we use [] for a 0 and [[]] for a 1 (the reverse would work as well), and put all the 1s and 0s in a big list. Great, you just proved that any kind of data can be represented by simply nested lists only!)

So let’s add another datatype: true, or T. Now we can write [ T T T ], which is not the same as [ [] [] [] ].

That’s basically all there is to Lith. Of course, it only becomes interesting if we give some meaning to different formations and organisations of T and []. So an empty list is false, everything else evaluates to true. [ T ] means 1, [ T T ] means 2, etc. With a bit of imagination you can implement strings and more complex objects as well in a logical fashion.

The next step is, you put those abstractions in the language, or rather, in the parser. If you write 34, it understands you really mean [ T T T T T ... T T T T T ]. A smart interpreter/compiler would still use 34 under the hood, rather than a long list of trues, but conceptually, the Ts would still be there. You could ask for the head of 34 and get T. If you’d ask for the tail of 34, you’d get 33, etc.

Now, every expression evaluated is pushed to the stack, which is basically another list. Arguments and return values for functions make use of the same stack.

So what is implemented currently? Only a simple tree parser, which accepts only [ ] and T (plus whitespace and various separator characters). Will I ever implement more? Dunno. Experience says it could go either way.
(Update: I have.)

Now here’s something I haven’t figured out yet: how to do functions, using only abstractions from lists and true. So, dear readers, do you have an idea? How would you implement functions as a tree? Please share and enlighten me!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: