FORTH and the Rosetta Code Challenge

The other day I came across this Rosetta Code challenge and thought that seems simple enough for me to have a go at... using RobsForth! Perhaps, I misunderstood what the challenge was really about? As far as I understood it, most languages don't have (COBOL does) an IF conditional that can be fed two truth tests and will output:

1. Both tests are True
2. The first test is True 
3. The second test is True
4. Neither test is True

The challenge was to reformulate the typical solution using nested IF's  given below into a function called IF2 which can be used instead of the nested IF's anywhere in your code.

There were lots of languages on display, quite a few of them esoteric one-off's like RobsForth, as well as the usual suspects like C++, Java and Python. I was surprised how complex some of the solutions were. Some submitters provided their function without a test suite, but we all know how easy it is to introduce a logic error, even on the simplest code.

Rosetta Code's introduction assured me that Lisp and Forth automatically support language extension, so I figured this shouldn't be a problem 😆 and away I went. My first effort was too complex, but eventually I pared everything down and ended up with:

# cond1 cond2 -- int
: if2
	IF IF 3 exit THEN 2 exit THEN
	IF 1 exit THEN
	0
;

a Forth word that eschews the ELSE clause.  Forth, of course, is a stack based language and while RobsForth does have global variables, it doesn't have local variables and so everything you see below relies on the stack to store state.

"""
	if2 
	Rosetta Code challenge 
	https://rosettacode.org/wiki/Extend_your_language

if (condition1isTrue) {
     if (condition2isTrue)
        bothConditionsAreTrue();
     else
        firstConditionIsTrue();
  }
  else if (condition2isTrue)
     secondConditionIsTrue();
  else
     noConditionIsTrue();

if2 (condition1isTrue) (condition2isTrue)
     bothConditionsAreTrue();
  else1
     firstConditionIsTrue();
  else2
     secondConditionIsTrue();
  else
     noConditionIsTrue();
"""

• Anything between """ and """ is a multi-line comment
• # is a single line comment

# ----------------- if2 Definition ------------------------

# cond1 cond2 -- int
: if2
	IF IF 3 exit THEN 2 exit THEN
	IF 1 exit THEN
	0
;

# ----------------- if2 Test ------------------------------

# int -- stdout
: branch
	dup
	3 = IF drop |+ ' is divisible by 2 & 3 ' +| exit THEN
	dup
	2 = IF drop |+ ' is divisible by 3 ' +| exit THEN
	dup
	1 = IF drop |+ ' is divisible by 2 ' +| exit THEN
	drop
	|+ ' is not divisible by 2 or 3 ' +|
;

The above word, called branch, demonstrates much of what RobsForth is about:

• IF consumes a truth value, where 0 is false and anything else is true.  The truth value is supplied by the stack.
• Words between |+ & +| are prepended to the words queue and executed immediately, before returning to continue executing the compiled word.
• Words between ' & ' are printed to std out.  Inside a compiled word they must be surrounded by |+ & +| otherwise ' & '  would consume the words queue AFTER this compiled word.
• exit jumps out of a compiled word.  It turns a sequence of IF statements into a Case statement, rather than the deep nesting of IF ELSE's that would otherwise be required e.g.
  IF ELSE
  IF ELSE
  IF ELSE
  THEN
  THEN
  THEN

# --
14 0 BEGIN
   dup dup dup dup dup . space . 
   3 / swap 3 / int - 0 = pob
   2 / swap 2 / int - 0 = pob
   top top if2 branch /n
next WHILE drop drop

RobsForth doesn't have to compile words before using them. Code can just be a script as above. The only native conditional words in RobsForth are:

• IF ELSE THEN where IF is really Jump==0 while ELSE is Jump and THEN is a jump marker for IF or ELSE.
  
• BEGIN WHILE where WHILE is really Jump!=0 and BEGIN is its jump marker.

RobsForth uses a deque rather than a stack and pob and top are moving items from the top of the deque to the bottom and vice versa. Consequently, RobsForth has four easily accessible local variable slots rather than a typical Forth's two.  RobsForth does not implement complicated stack manipulators like pick, roll, rot, nip, tuck, etc, etc... just:

• dup, swap, over, drop at the top of the deque.
  
• dob, sop, oob, bop, pob, top, beep on the bottom of the deque. beep is equivalent to peek, but there is no peek in Forth, because Forth words automatically consume the stack when they are invoked and may leave items on the stack when they exit. This implied use of the stack for local variables removes the need to explicitly set and get local variables. The stack is an interesting structure:
• Variables on it are transient globals whose lifespan is determined by their depth on the stack. In most languages local variables must be explicitly passed by value to another function. In Forth, variable creation, passing and destruction is implied.
• The state of the program can be inferred by looking at the stack because it contains all local variables. RobsForth also stores true global variables on it's heap which live for the duration of the script, but whenever possible, I try to avoid using heap variables.
• Because RobsForth has no local variables, refactoring is straight forward.  Simply extract a sequence of words from a word and call them a new word. The key to refactoring is to have word names that accurately describe what that word is doing. If this is done then RobsForth becomes a domain specific language and understanding code means comprehending the major words in the task's context.

# ----------------- if2 Results ----------------------------

<!-- Forth --> @test.fr
0 is divisible by 2 & 3
1 is not divisible by 2 or 3
2 is divisible by 2
3 is divisible by 3
4 is divisible by 2
5 is not divisible by 2 or 3
6 is divisible by 2 & 3
7 is not divisible by 2 or 3
8 is divisible by 2
9 is divisible by 3
10 is divisible by 2
11 is not divisible by 2 or 3
12 is divisible by 2 & 3
13 is not divisible by 2 or 3
<!-- Forth --> 

I hope this gives you an idea of what RobsForth looks like. It's just a stream of white space separated tokens, which I have formatted, so that they are easy to look at.

A key objective with RobsForth is to keep software development simple. Below are three acronyms the industry uses in an attempt to keep software simple.

• KISS: Keep it simple stupid (”Write the code in the simplest way you can think of. Refactor constantly.”)
• YAGNI: You ain’t gonna need it (”Don’t write the code if you don’t need it now”)
• DRY: Don’t repeat yourself (”Do not copy-paste”)
  

Chuck Moore, the inventor of Forth, was a firm believer in KISS and YAGNI (DRY was probably so obvious to him, that he never bothered to mention it!) and I think the following acronym too.

• MS: Minimise syntax (”Avoid languages with excessive syntax”)
• Since using RobsForth, I no longer like languages which expect syntax. They're too busy which makes it harder to concentrate on the problem at hand.  White space syntax languages are the worst, which is ironic, since RobsForth is implemented using Python!
  

Go FORTH and build your own language!

FORTH is a wonderfully simple and compact programming language. Take a look at Rosetta Code Language Comparison.  Nearly every column on their table for FORTH is either... N/A, None or No!  I laughed at the column about the language being standardised (ANSI, ISO/IEC 15145:1997). Nothing could be further from the truth. At the beginning, a vanilla FORTH doesn't even have variables! You make them yourself by coding the word var (or whatever you think a variable should be called) using

 : var create 1 allot ; which is a compile time word 

every time the word var is invoked at run-time, create looks at the next word in the word list, let's call it counter for this example, assigns it a dictionary key, saves the current heap slot along with the instruction to push the heap slot to the data stack as a dictionary value and finally, advances to a new slot on the heap. So next time you call the word counter (not var. It's done what it needed to do), FORTH looks up the dictionary, and pushes it's heap slot to the data stack. Now you can retrieve the contents of the heap slot, using the built-in word @ or write a new value to the heap slot using the built-in word !

You're probably lost already, but this isn't a lesson in how to use FORTH. I cut my teeth on FORTH written in Python and highly recommend it. Instead I want to posit my pearl of FORTH. Somebody said somewhere that the pearl of Forth is it's create does> word pair, which in brief, let's you pair a compile time action (create) with a run time action (does>). This word pairing let's a user create their own language on top of FORTH. In the past people have created Object Oriented FORTHS and even BASIC. However, this is just syntactic sugar. I've discovered quite early in my FORTH journey that it's better to stay as close to the machine (Python virtual machine in my case) as you can.

No... for me the pearl of FORTH is that anybody can write their own FORTH and consequently there are hundreds of them out there. Few of them follow the FORTH standard. 

The reason you can write your own FORTH is due to it's very simple compile / interpret loop. FORTH doesn't have a compiler in the standard sense. Instead it has compiling words like var above. In FORTH there is no syntax, just a stream of white space separated tokens called words which are consumed in a single pass. The compile / interpret loop works as follows:

1.    We begin in interpret mode. If the word presented is a : we enter compile mode.  Otherwise consume the word and execute it immediately.

2.    If we are in compile mode, consume each word, compile it, but don't execute it.  Instead once ; is reached, store the compiled pcode in the dictionary for future execution, when the word we have just made (var above) is called again.

3.    Go back to 1.

A number of implications flow from this simple pcode compiler:

because the the words themselves act as switches to turn the compiler on and off, compiled words can be redefined further down the word list. Word (function) redefinition is the way a FORTH program deals with a function needing to do slightly different things based on it's context (function overloading in C++).

anybody can change how a FORTH compiler behaves by creating new built-in words that interact directly with the compile / interpret loop in a similar way as : and ; do.

a compiled word is a list of built-in words and perhaps other compiled words. At run-time those words call each other in sequence. My FORTH, like a lot of them, uses the concept of indirect threaded code where the compiled words are a list of function calls in a Python list stored in a dictionary. To execute each underlying Python function the FORTH word (key) calls the dictionary, which then calls the Python built-in function's memory address (value) which it looked up and stored during the compile process. In direct threaded code each function would call the next, similar to a linked list. The advantage of indirect threading, is that the built-in function doesn't need to know anything about calling or being called and so:

Compiled words can be defined that contain words that haven't been defined yet, as long as all words have been defined by execution time. 

Recursion is possible. 

All of FORTH's built-in tokens including the compiler control tokens : and ; can be renamed by storing them as constants. 

the words list is consumed as it is compiled / interpreted. This makes it easy to add new words to the words list at run-time, just create a word that reads in a new file and adds it's contents to the top of the words list. This lessens the need for namespaces as words are only introduced when needed rather than being present when the program loads.

you can increase the performance of your code by treating the word list as your string storage, something you would never do in a compiled language. This works particularly well when you want to print out large swaths of HTML which, just like FORTH, has no syntax. I put it all in my FORTH file (which is actually a collection of database records) and use the FORTH interpreter to print it directly to standard output (std out), bypassing the stack and heap. Want to store the string on the data stack instead (SQL queries come to mind for that)? Same approach as for std out except the word is different that puts it on the stack.

being able to poke around in the compiler gives you a very good understanding of how your FORTH works and the result is that you work to it's strengths and avoid it's weaknesses. The strengths I have noticed so far:

• the code base is very malleable (the refactoring everybody talks about) and it is easy to change things so that you can re-use code e.g. printing a table is commonplace so I have standard table printing code where I redefine what can happen before, in and after a table cell. Now it's easy to print out HTML, tab delimited format, CSV or whatever.
•  no types. If you want a type you have to explicitly cast it. Using HTML its all strings, so most of the time I don't want to be fooling around with types anyway. The only ones I've implemented so far are str and int. The other day I wanted a currency type. I found the appropriate Javascript and dropped my number between it. A quick and dirty solution that I wouldn't want to use for a table with hundreds of values, but formatting variables by surrounding them with FORTH string constants is standard practice for me.
• avoid local variables because they make it difficult to refactor. A web app is a collection of independent pages, so the chances of global variables standing on each other is reduced. I have a number of predefined global variables which I use over and over. Then I came across the concept of shadowing. A FORTH variable is really an array of one (1 allot).

          var counter

1 allot

You now have a variable with two slots.  To refer to the first slot you simply call it by its name:

counter

counter 1 +

gets you the second slot.

This shadowing concept means you can store a backup of your variable in the same variable name. 

The Weaknesses 

• being able to have local variables would be nice occasionally 😀. Stack twiddling is not useful work. My solution has been to turn the stack into a deque and to use the bottom of the stack to store one or two local variables. Many FORTHS use the top of the control stack to store a local variable. I haven't tried that, preferring the deque concept instead because you don't have to monitor it so closely. If I'm iterating through a table there's going to be a lot of values on the stack, so there's no chance the bottom value will be accessed from above. I've added a bottom peek instruction which works well, but would be a disaster at the top, since FORTH words almost without exception pop from and push to the stack.
• it's very easy to write inscrutable code. To address this, I indent my code following the typical conventions e.g. nested if statements. Plastering the code with comments is standard practice in other languages. Instead I try to use words that make sense when being read from left to right. Done right you end up with statements that intuitively make sense e.g. empty counter ! means put a '' into the counter variable and store it on the heap. Traditional FORTHS have a lot of one and two character words like @ ! . , : ; etc. I've tried to avoid those except for the most common ones that everyone knows. If I'm reimplementing a Python function I use the same name that Python has. I don't eschew comments completely. A longer explanation of what the code does is placed in the first record, although I've found the need for commenting is not that critical because the unit name and database record name combination gives you plenty of clues as to what the code is doing. Despite these things, it is not easy to read FORTH code. You have to be in the "zone" which requires time. C code is much easier to understand when you first see it.

A FORTH written in C would remain a toy without many many man hours, but that's not what I'm doing here. I'm using FORTH as a way to simplify Python down to doing one thing... emitting scripts to std out or to file. Creating those scripts is faster than doing them directly in Python, because FORTH doesn't do any syntax checking (Python's tab/space syntax checking drives me mad!) and FORTH never crashes. It just emits the Python error and remains in it's REPL (Read Evaluate Print Loop). The scripts are typically SQL, HTML, CSS and Javascript, but I could  target any tool that is scriptable. LaTEX and Python are likely to be targets in future.

 

Safe Python Eval

Many of us want to use a safe simple scripting language to extend our Internet applications and I have seen many discussions on the Internet on how to implement Python so that it's eval function can't be exploited. The problem is, nobody can be sure that they've covered every scenario, because Python has become complex over time, with multiple ways to achieve the same objective.

My scenario is a typical one. I have a web based database application hosted on a remote server. Now I want it's users to access it's database to produce ad hoc reports, without compromising the database or anything else! I could do the typical thing of providing a screen where users can submit Select queries, but SQL by itself isn't enough to get a report that is useful except in the most simple scenarios. To begin with you can only work with one query result at a time. Reports frequently require multiple query results to be combined. Tables of course can be joined using SQL, but the result usually has lots of redundant data fields that must be omitted. A declarative language like SQL just can't do it alone. It needs to be combined with a procedural language. After all, that's how my web application works. The procedural capability of Python is combined with SQL to produce web pages that make sense to users.

After surveying the scripting languages out there, Python came in at number one, BUT, it has an eval function that can access the file system or carry out other security exploits. Vanilla Python isn't a sensible choice as an extension scripting language.

I have looked at FORTH in the past, ATLAST and Ficl were front runners, but they are traditional FORTHs with weak string manipulating capability. Strong string capability is what I need, because my database queries return as nested Python string lists. I came up with that format years ago before JSON became popular, using Python eval to parse the database query, returning a table that Python can iterate over using it's index functions.

Then I came across FORTH written in Python, a toy project for educational purposes. I realised it wasn't going to be fast, because FORTH is an interpreted language written in an interpreted language! What it did have going for it was very strong string capability and the ability to cherry pick the Python functions required, leaving everything else behind. Suddenly, eval wasn't a problem as I could overlay it with some checks to make sure eval could only eval a list. FORTH is a simple typeless stack based language with the entire environment comprising two stacks and a heap (Python lists), a dictionary (Python dictionary) and a heap pointer (Python integer). FORTH has no syntax! The language is just a stream of white space delimited tokens called words. Traditional FORTH has no error checking and crashes are common place. But having Python underneath FORTH  makes it uncrashable. Sure your FORTH code will frequently bomb, but the FORTH REPL (Read Evaluate Print Loop) just displays the Python error and awaits your next command.

I made some alterations to the Python code to get a FORTH that isn't quite FORTH anymore (as the saying goes 'when you've seen one FORTH - you've seen one FORTH')! Everything became a string, both the stack and the heap able to handle strings or lists of any size in addition to numbers. Actually Python is cleverer than that. Lists can store variables of any type, so my database lists stay as lists (under the hood, they're probably C arrays) which are passed by reference rather than value. Numbers stay as numbers and dates as dates unless they are cast explicitly, something I've brought over from Python. But apart from that the toy project has stayed largely untouched. All it can do is step, branch, loop, create variables, read variables and print to the console. But at just over 300 lines of Python, it's Turing complete and this is all you need to create a report. Already I have written a complex report utilising two tables that cannot be joined, the report output is styled HTML.

Perhaps the most interesting thing I've done is to create a persistant library of Forth definitions. The way I've done that is to store the FORTH environment after loading forth.py (the REPL) and forth.fr (the persistant library) as Python command line arguments. The working code FORTH file is then called manually in the REPL. Each time it is called the FORTH environment is restored to the finish of forth.fr. This means you can call the working code file over and over without having to restart the REPL.

But there's still a problem!  FORTH over Python might be safe, but a user could write a function that never returns. Endless loops are easy to create inadvertently in procedural languages. Code needs to be added to Isectd that checks how long a worker has been busy for. If it has been busy for longer than 20 seconds and has no clients attached then Isectd sends a kill command to the process which will automatically restart after it has been killed.

The working FORTH code is included in PocketClassmaker install file from the downloads area of my website.