Monday, December 5, 2022

Listack, a flat programming language

 I'm working on yet another new programming language.  After the success of Falsish, a False derivative with elements of Fish ><> enabling both global (upper case) and local (lower case) variables, with a stack of stacks enabling local scope, I wanted to make something better.  Or at least easier to read.  (False was made to be an obfuscated esolang.  It wasn't the first, but it did kick off the movement, as it happened at the beginning of the internet era.)  So I started working on something similar, but with a real parser to handle, you know, words, and not just individual symbols.

I worked on that a bit, and it worked well enough, but I wanted something more.  Something different.  Stack based concatenative (Forth-like) languages have been done to death, because they are easy.  Factor looks intriguing, but its on-line documentation is, well, so thorough and detailed as to be unreadable.  And then I ran across a video on Stackless Python.  (Abandoned in favor of PyPy, apparently.)  The language implementation is more or less flat, without using the call stack to handle procedures calls and returns.  It claimed to be easier to use for advanced functions like concurrency.  EVE Online uses it to handle tens of thousands of simultaneous users.

Well, that certainly did sound different.  A challenge!  But how to implement it?  At about the same time, I read something about a stack based pure functional language that took as its arguments the program and the data stack, and returned a new data stack and program for every function call.  While this seemed inefficient, it had potential.  After all, a program is basically a list of past outcomes, future commands, and the current command as "now".

So that's what I am building.  I've done a few technical demonstrations, and gotten them working.  The key, as usual, is to make things simpler.  Always simpler, never more complex.  It's working spectacularly.  Whenever something seems difficult, I take a break, and the correct, simple way eventually comes to me.  I'm still refining, because this method of language implementation has opened up so many broad areas to explore.

Listack (current working name, because it uses lists and stacks) is a flat language.  It operates purely on a loop with a few context variables.  It does not call itself.  It is not, in and of itself, recursive.  It supports recursion, of course.  (While loops are implemented as recursion, for example.)  How does it work?  The past is a stack, with the most recent data on top.  Future commands are a queue, with the next one to be executed at the front.  Moving items from the future queue to the past stack and back is trivial, but the key to how everything works.  Listack is implemented as two deques, one for the past stack and one for the future queue.  The present is a single variable called current.  (There is also a deque of deques to implement local scope by saving versions of the past.)

The only real control flow operator in the language is IF.  All IF does is to delete one of two items, based on a boolean condition (true or false).  If the condition is true, it deletes the second item.  if false, the first.  That's all you need to implement control flow.  Well, that and a bit of meta programming to move elements around.  (I'm using ALL CAPS to show commands.)


In postfix notation, if works like this: 

        condition [do if true] [do if false] :IF

With the flat implementation, I can also implement a prefix version: 
        IF: [condition] [do if true] [do if false]

And infix, which seems easiest to read: 
        condition IF [do if true] [do if false]


With if, we can create while.  The begin gets added so we can implement continue and break in the body of the while.

original postfix: [condition] [body] :WHILE
becomes:  condition [body BEGIN [condition] [body] :WHILE] NOP :IF

prefix:  WHILE: [condition] [body]
becomes:  IF: [condition] [body BEGIN WHILE: [condition] [body]] NOP

infix:  [condition] WHILE [body]
becomes:  condition IF [body BEGIN [condition] WHILE [body]] NOP


And the best part is that I can have all three styles by just implementing the postfix version, then using meta programming to move the arguments around.  I can easily implement most commands with a prefix, infix, and postfix variant.  It's a bit tedious, but not complicated.

Procedures/functions are merely variables whose [contents] can be executed.  Of course, that's technically true of all variables, as the meaning of '5' is to push the number 5 onto the stack.

I could implement a local scope for commands , in addition to data.  I'm still considering that.  It's not like it would be difficult.  I'm just not sure of how or why to use it, and what it should look like.  Since local scope for the data stack is N(), perhaps the command queue should be N{} ?  (N is the number of items to push to the new deque from the old.  When the scope is closed, the remaining items get pushed back onto the old deque.)

I can also make the meta-programming routine available as a function in the language, so the user can create their own control flow commands.  FOR isn't complex at all.  It's just a while with some initialization beforehand and a regular change that gets tacked onto the body.

prefix:  FOR: [init] [condition] [change] [body]
becomes:  init WHILE: [condition] [body change]

You want it to look different?  Customize it!
infix:  FOR [[init] [condition] [change]] DO [body]       (Note: DO is pure syntactic sugar)
becomes:  init [condition] WHILE [body change]

You want a for-like until?
infix:  init DO [body] UNTIL [condition] [change]
becomes:  init body [condition] WHILE [change body]




No comments:

Post a Comment

I reserve the right to remove egregiously profane or abusive comments, spam, and anything else that really annoys me. Feel free to agree or disagree, but let's keep this reasonably civil.