llizard teaser
The other day I saw this page about the Cat programming language. It’s a stack-based (or “concatenative” if you wish) language, like Forth, Factor and Joy.
As it happens, I have been writing stack-based toy interpreters for years. I don’t think I ever released any of these languages; after all, these implementations are just toys. With the current resurgence of interest (well, relatively speaking :-) in stack-based programming, I just might publish an interpreter or two, though.
The working title for my toy language has been llizard. (I should probably change this name, to avoid confusion with the ASCII artist of the same name.)
Anyway, llizard differs in a few ways from “regular” (if there is such a thing) stack-based languages. (Note: The following probably only makes sense if you’re already familiar with a language like Forth or Joy.)
For starters, rather than one stack, it uses a stack of stacks internally. Objects are pushed onto the topmost stack. So we start out with [[]], and after doing e.g. “1 2 3″, we have [[1, 2, 3]]. Since for most actions only the topmost stack is used, this works as expected:
> 1 2 + println 3
However, llizard also supports lists/stacks as a data type, and this is where the nested stack representation comes in.
> [ 4 5 6 ] println [ 4 5 6 ] # compare: print [4, 5, 6] > [ 3 4 ] length println 2 # compare: print len([3, 4])
The [ and ] words are not special syntax; they are builtins that work like other words, but happen to manipulate the stack of stacks. [ pushes a new, empty stack onto the stack-of-stacks. ] pops the topmost stack, and pushes it onto the previous stack. For example:
# start: [[]] > 3 # stack-of-stacks: [[3]] > [ # stack-of-stacks: [[3], []] > 4 # stack-of-stacks: [[3], [4]] > 5 # stack-of-stacks: [[3], [4, 5]] > ] # stack-of-stacks: [[3, [4, 5]]] # contains a number and a list.
This way, I can implement lists without having to use special syntax. (One of the design goals of llizard is to do as much with regular words as possible.) It also allows me to manipulate an “open” list however I want, and then “close” it when it has the desired contents.
Similarly, ( and ) are used to create “code blocks” or “anonymous words” or “lambda-words”:
> 3 > ( 1 + ) exec > println 4
( 1 + ) creates a code block that, when executed, pushes the number 1 and calls +. Again, this is done without special syntax; ( and ) are separate words, and must be surrounded by whitespace when appropriate; (1 +) won’t work, because llizard sees this as the words “(1″) and “+)”.
Defining new words, variables, etc, does not require special syntax either. All you need to define a new word, for example, is a code block, and a name (provided as a string or a symbol):
> "inc" ( 1 + ) defword > 4 inc 5
By contrast, Forth, Joy, Factor and Cat all require some sort of “lookahead” and/or “special words”. The example above would look like this in Cat:
define inc { 1 + }
…which arguably looks nicer, but it cannot be done without looking ahead, or making this a special form in the parser. In other words, Cat does not execute “define”, “inc”, “{“, etc, in that order… the whole definition is a form that must be read and executed as a whole.
llizard has some more funky stuff, like mu-words that are like lambda-words but dynamically scoped. Aside from that, it has “functional” words much like Joy and Cat: map, apply, etc. And modules. (To be fair, the “..” word that is used to look up names in modules, *does* use a lookahead, although there is a word module-lookup that doesn’t… but using “..” is nicer. More about this later. Maybe.)
Right now, the llizard interpreter isn’t available yet, but chances are it will be soon… several versions have been written in Python, the latest one was done in OCaml. A possible newer version could be done in Python or Scheme or something. Dynamic languages allow for easy definition of many stack-transforming words, something which is harder in OCaml. (I’ll probably write a separate post about this later, with Python examples.)
Maybe once I have a distribution up for download, 99 Bottles of Beer will accept my code sample as well… They haven’t so far.