Forth Times One

Back in "Why Forth? - Part 1", I made a semi-joking parenthetical statement about the Forth I was developing for the Flexible System Architecture: "(should I call it "North", as in "Not Forth"?)." Since then, I have reviewed some of the articles on www.ultratechnology.com, particularly the discussions by, and interviews with Charles Moore, the inventor of the Forth language. To me, Mr. Moore just seems so far ahead of everybody else that he's the one consistently working on 'Not-Forth'.

Therefore, much of this essay will be a dissection of the transcript of a talk he gave in April 1999 about the evolution of his language over the previous fifteen years, entitled "1x Forth", and how I see his ideas applying, or in some cases not applying, to my work on North for the FSA. Sort of like one of Bill Simmons' "Retro Diaries," only not necessarily following the chronological order of the event.


If there's an underlying theme to the lecture, it is that of simplicity.

The goal was very simple: to minimize the complexity of the hardware software combination ... I'm never bored by simplicity. Show me a simpler way to do anything that I'm doing. I will jump on it ... Forth doesn't need to be complicated. Classic Forth started out simple, it gradually accreted layers of complexity.

In Forth, simplicity equals factoring.

You factor. You factor, you factor, you factor and you throw away everything that isn't being used, that isn't justified.

Moore uses the term "factor" like most programmers use "refactor." If there's a general definition for refactoring, it is: "altering internal structure without changing external behavior." Refactoring means cleaning up the code - squeezing out the junk, the extraneous, the duplications. You don't change how it works, but you do clarify the logic and control flow; make it more simple and readable. In Moore's usage, "factoring" pretty much means writing clean code in the first place, but the idea's basically the same.

... that is in my mind one of the keystones of Forth, you factor and you factor and you factor until most of your definitions are one or two lines long.

Hmmmm. Definitions one or two lines long. That certainly is different than some of the Forth examples I've seen. One cannot argue with the simplicity implied here, but I wonder if there's not a slight speed penalty to be paid. If a definition is accomplishing a lot of processing yet only two lines long, it must mean the def is made up of 'powerful' words. I mean, if somebody writes a 12 line definition and then refactors it down to a half dozen words, that's a half dozen new definitions to be looked up when it runs. Once its compiled, it will still be very fast, but still, that's six extra strands in the threaded code, isn't it?

One slight doubt I have about following Moore's advice too slavishly is that - and this is not a criticism - I don't know what real world applications he has written. I know at the time of this talk he had been working on a series of hardware implementations for Forth, as well as Forth-driven CAD systems for laying out the chips. An impressive body of work, but had his 'Not-Forth' gotten too fine-tuned to one specific application area? The same doubt could apply to Forth in general, actually ...

I think perhaps Forth programmers play too many games with the tool they have because there's no applications.

I read once that General Electric had written their whole system for building locomotives in Forth. Things like ordering, inventory, the manufacturing steps, the whole template, in Forth. While I could waste a paragraph expressing my opinion of the quality of GE products like light bulbs and extension cords, I assume their locomotives ran pretty well. More to the point, the software I read about would have been a huge real world application, one of the earliest examples of CAM (Computer Aided Manufacturing).

Maybe I'm buying trouble anyway, The FSA is a Control Architecture meant primarily for embedding on silicon. It's not really intended for large, database intensive systems. OTOH, if I see a possible speed problem related to factoring into shorter definitions, then that is a concern for an embedded core. This harkens back to the discussion about 'abstraction' back in "Controlling Complexity". If a 12 line definition consisting of some stack operations and a loop or two is shrunk down to a few Forth tokens, those tokens, if named sensibly, no doubt will be more readable and do a better job of explaining what is going on. There's still that speed hit, however. Comments explain things too, and don't add any calls to the code. Tradeoffs again. Anyone who claims programming isn't as much art as science simply hasn't done enough of it.


What is Forth?

Forth is highly factored code. I don't know anything else to say except that Forth is definitions. If you have a lot of small definitions you are writing Forth. In order to write a lot of small definitions you have to have a stack. Stacks are not popular. Its strange to me that they are not. There is a just lot of pressure from vested interests that don't like stacks, they like registers. Stacks are not a solve all problems concept but they are very very useful, especially for information hiding and you have to have two of them.

The good news here is that the standard FSA sequencer has two counters. Two counters, two stacks. So far so good. I've mentioned before that I use a call stack rather than a return stack and I do wonder if that will bite me sometime as I go forward in my language developments.

What is a definition? Well classically a definition was colon something, and words, and end of definition somewhere.
  : some ~~~~~~ ;
I always tried to explain this in the sense of this is an abbreviation, ... you give it a name and you can use it more conveniently. But it's not exactly an abbreviation because it can have a parameter perhaps or two. And that is a problem with programmers, perhaps a problem with all programmers; too many input parameters to a routine. Look at some 'C' programs and it gets ludicrous. Everything in the program is passed through the calling sequence and that is dumb.

A Forth word should not have more than one or two arguments. This stack which people have so much trouble manipulating should never be more than three or four deep.


Now that is something I can totally agree with. More on short stacks is coming up, but here Moore starts talking about his COLOR FORTH invention:

Our current incarnation of our word (:) is to make it red. That way you don't even use colon ... The red word is being defined,
  some ~~~~~~
the definition is green and it might have a semicolon in the definition which means return but it does not mean end of definition. It can have more than one return, and you can have more than one entry point in here if you want ...


Two things: Having different colors in the source code to tell what state the program is in is probably a very good idea, but I've been a text based programmer for a long time and I've got to write a lot of text Forth before I'll feel comfortable with trying yet a newer paradigm. Color Forth also takes a specialized editor, which would be a problem for me. The other thing is the multiple returns and entry points. Later on he talks more about multiple semicolons:

In fact in all my latest Forths semicolon kind of meant either return or jump depending on the context and it's optimized in the compiler to do that.

It took me several re-readings to get my head around this. I was totally lost until I finally realized he's using them as the equivalent of a 'continue;' statement in C. In other words, there's a test of some kind before the semicolon. Fine. But did he also mean to say "more than one entry point"? Sounds like spaghetti code to me. I know I defended multiple entry points when I wrote about subroutines and functions in "Deciding to Get Loopy", but that was in machine language, where I said "you [may be] more interested in efficiency than style." Also, you can see exactly where you're jumping into; see exactly what the next series of instructions will do. Jumping into the middle of more highly abstracted code, even code as close to the machine as Forth, I dunno about that ...

But as to stack parameters, the stacks should be shallow ... The words that manipulate that stack are DUP, DROP and OVER period. There's no ..., well SWAP is very convenient and you want it, but it isn't a machine instruction. But no PICK no ROLL, none of the complex operators to let you index down into the stack. This is the only part of the stack, these first two elements, that you have any business worrying about ... The others are on the stack because you put them there and you are going to use them later after the stack falls back to their position. They are not there because your using them now. You don't want too many of those things on the stack because you are going to forget what they are.

Again, I agree. Oddly enough in this case, because when I first started creating a Forth interpre/piler for my architecture, I was most excited about implementing all the various flavors of stack ops. They seemed like they'd be both fun to write and give a quick payoff ("Whoo hoo, look what I'm making the stack do!"). Now I'm glad I didn't get that far. First of all because now that I'm adding new machine instructions to the C language FSA simulator (and yes, refactoring as I go along), I'm getting more than my fill of futzy, detailed low level programming. Secondly because I see his point. Somewhere in another discussion he says something about the stack not being an array. In other words, if you want to perform array operations, create an array somewhere and operate on it there. Keep the stack reserved for quick on / quick off parameters.

So people who draw stack diagrams or pictures of things on the stack should immediately realize that they are doing something wrong. Even the little parameter pictures that are so popular. I used to appreciate this back in the days when I let my stacks get too complicated, but no more. We don't need this kind of information.

Charles! You'd been writing Forth for thirty years. Allow us neophytes at least a cheat sheet or two!

Of course on a chip those [first two elements] are the two inputs to the ALU so those are what are relevant to the hardware.

Excellent point. I'm experimenting with having some local logical testing available at each sequencer to hold down accessing the ALU, but much of the time the top two items on the stack are going to be cycled through an ALU: Plus, Minus, Or, Xor, whatever.


Getting Loopy with Forth

So the stack operations that I use are very limited. Likewise the conditionals. In Classic Forth we used  IF ELSE THEN,  And I have eliminated ELSE ... I will have IF with a semicolon and then I will exit the definition at that point or continue.
  IF ~~~ ; THEN
I have the two way branch but using the new feature of a semicolon which does not end a definition. Likewise with loops, there were a lot of loop constructs. The ones I originally used were taken out of existing languages. I guess that is the way things evolve.
  DO LOOP was from FORTRAN,
  FOR NEXT was from BASIC,
  BEGIN UNTIL was from ALGOL.
What one do we pick for Forth? This (DO LOOP) has two loop control parameters and it is just too complicated. This (FOR NEXT) has one loop control parameter and is good with a hardware implementation and is simple enough to have a hardware implementation. And this one (BEGIN) has variable number of parameters...


By the time of this lecture, Moore has dropped all of them, opting instead for "tail recursion". Putting an example in text-style Forth, you have:

  : newdef ~~~ IF ~~~ newdef ; THEN ~~~ ;

I mentioned before that recursion is a useful, clever looping construct so long as long as you 'loop in place' rather than rebuilding stack frame after stack frame after stack frame. Charles loops in place, of course. I definitely believe this is generally the best, most modern way to loop. Yet I think it will be worthwhile to keep a more direct, low level looping system available as well. In "Deciding to Get Loopy", I write about TTL & BTL (Top-Tested Loop & Bottom-Tested Loop) as basic machine language primitives. I want to keep those.

As North elements (remember, it will be 'North', not 'Forth'), I'm not sure yet what form TTL & BTL will take. Will they be colon-defs or lower-level primitives? Will they need a specialized delimiter or will a semicolon do? If they do need delimiters, forget BEGIN-UNTIL or any other wordy things, I'll steal the { curly braces } from C.

There is another aspect to TTL & BTL ... maybe. The Forth I've developed so far has two types of definitions. For example, in "Hashing it Out" I show the 17 memory words taken up by the entry for the plus sign. There are 7 memory words of the standard definition header, followed by 10 hand coded machine language instructions that actually operate the parameter stack and ALU to add two numbers. The other type of definition is a compiled one, as shown in "Why Forth1? - Part 1", where the standard header is followed by a "thread list" of calls (including two to '+').

What I would like TTL & BTL to do is to build the first type of definition, the one with direct active code, when they are themselves part of a Forth definition. Even the old FORTH-79 standard that I've been cribbing from has the "defining word"  DOES>  which lets you put a run-time action within a colon-definition, but that action is still defined with other Forth words. That is tricky enough, but I'd like to be able to use TTL or BTL to create definitions out of actual machine code. Although perhaps this is trying to go "A Bridge Too Far."

I loop back to the beginning of the current definition. And that is the only construct that I have at the moment and it seems to be adequate and convenient. It has a couple of side effects. One is that it requires a recursive version of Forth. This word must refer to the current definition and not some previous definition ... the net result is that it is simpler. It would of course not be convenient to nest loops but nested loops are a very dicey concept anyway. You may as well have nested definitions. We've talked over the last fifteen years about such things. Should you have conditional execution of a word or should you have something like IF THEN? Here is an example where I think it pays well in clarity, the only loop you have to repeat the current word ... It's a very simple look back optimization that actually saves a very important resource, the return stack.

This is too far out even for me. How do you NOT allow for nested loops? Multidimensional arrays, various mathematical algorithms, etcetera, depend on looping within a loop. I wish I'd been at this talk, I could have asked questions... Actually, I don't see why you can't have nested looping with a tail-recursive Forth. Perhaps Moore gave up something useful when he dropped the 'hard' semicolon? It's no doubt an advance to have ';' be context sensitive, but maybe using ';;' as an explicit end to a definition will still be handy for text based Forth (or maybe C's { curly braces }?). I'll have to experiment...

You shouldn't nest too deeply. It makes programs impossible to follow. You can have spaghetti code with calls just as you can with GOTOs. You have got to keep it simple.

This at least I can understand. And get behind. Moore mentions one chip he designed (the i21) where "the return stack is only 17 deep. People who are used to nesting indefinitely might get into trouble here." Once more, it's all about simplification. I'm not necessarily in favor of enforcing a physical limit on stack depth, but if a call chain gets so long as to get confusing, it is time to refactor the code.

Towards the end, Moore talks about some of his Forth-specific chip designs.

Machine Forth is what I like to call using the Forth primitives built into the computer instead of interpreted versions of those or defining macros that do those. One of those is IF. Classically IF drops the thing that's on the stack and this was inconvenient to do on i21 so IF leaves its argument on the stack and very often you are obliged to write constructs like IF DROP. But not always. It seems that about as often as it is inconvenient to have IF to leave an argument on the stack it is convenient to have that to happen. It avoids using a DUP IF or a ?DUP. So with this convention the need for ?DUP has gone away. And ?DUP is a nasty word because it leaves a variable number of things on the stack and that is not a wise thing to do.

I could not find '?DUP' by searching the Internet; perhaps the search engines` syntaxes got in the way. Be that as it may, I wonder if I should plan to offer two IFs, say 'if+' and 'if-' to provide both stack effects?

... in order to optimize data transfer it is very useful to have an incremented fetch operator. One of the problems I suppose on any computer ... is addresses ... It takes an extra memory cycle to load the address and then you can do the fetch against the address which takes another memory cycle. So the manipulation of address is expensive and you want to do it as little as possible. Fetch-plus (@+) helps with that. You put an address in the address register, which is called A, and it stays there a while. And if you execute this operator (@+) A gets incremented and you can fetch a sequence of things in order. Likewise you can store a sequence of things.

These operators are not in classic Forth ... They lead to a completely different style of programming. In the case of the DO LOOP the efficient thing to do was actually put the address as your loop control parameter and then refer to it as I and do an I fetch (I @) inside the loop. And the DO LOOP is working with the addresses. If you don't do that, if you have the fetch-plus (@+) operator you don't need the DO LOOP, you don't need the I, you use the fetch-plus (@+) inside of the loop to fetch the thing that's different each time. It is different but equivalent. You can map one to the other.


I think I'm OK here. My North-Forth operates out of a four-pack of sequencers, meaning eight counters are available. When running Forth, three of those get pretty active use, but one of the other five should be handy for temporary use equivalent to his 'A' register. The FSA also currently has a block move instruction available for data transfer, although it has made the sequencer logic much more complex to simulate and I'm thinking of dropping it. Once again, we'll see...

A brings up another issue. A acts very much like a local variable, a place where you can store something for a while and then retrieve it later in addition to acting as an address register. The reason that it acts as an address register, the reason I have it as an address is literally to provide a mechanism for this (@+). It is more convenient for the address to be on the stack from the programmer's standpoint, but if you are going to access repetitively you have to put it in a place where you can increment it.

He also has an 'R' register for MOVE operator. Besides '@+' against 'A', he can do a store-R against 'R'.

But such registers raises the question of local variables. There is a lot of discussion about local variables. That is another aspect of your application where you can save 100% of the code. I remain adamant that local variables are not only useless, they are harmful. If you are writing code that needs them you are writing, non-optimal code? Don't use local variables. Don't come up with new syntaxs for describing them and new schemes for implementing them. You can make local variables very efficient especially if you have local registers to store them in, but don't. It's bad. It's wrong.

This has a curious resonance with the MIT online course I mentioned I had audited, where they introduce the concept of "local state": "... we must be concerned with how a computational object can change and yet maintain its identity. This will force us to abandon our old substitution model of computation in favor of a more mechanistic but less theoretically tractable environment model of computation. The difficulties of dealing with objects, change, and identity are a fundamental consequence of the need to grapple with time in our computational models. These difficulties become even greater when we allow the possibility of concurrent execution of programs."Structure ... Chapter 3 Intro.

OK, that's a lot of information taken out of context. Basically it means their chapter three is going to explain how having variables (saving local state) can really complicate the low level flow of a programming language. They spent chapters one and two using purely "functional programming" to compute all kinds of non-trivial math functions and algorithms without having to assign one single variable! There surely were variables like the typical x & y of algebra, but they were used as 'substitution' parameters to procedures that instantly consumed them. There was no use of statements like

  z = x + y

where 'x + y' are assigned to some memory slot named 'z'. Yet the very first simplistic program introduced in chapter three - updating a bank balance - amazingly ends up requiring more underlying language support than did solving any dense, high degree polynomial encountered in the earlier chapters, simply because working with a bank balance does require saving a value that can change over time.

The messiness increases another step when concurrency is thrown in, for example two people with a joint account, one making a withdrawal and the other a deposit at different ATMs at about the same time. Then both checking the balance. This turns out to be a hard, real-world problem. Tracking the time order of assignments becomes a necessary part of the underlying architecture. Since the FSA is meant to support parallel processing, any 'perfect language' running on it must deal with this level of complexity too. Anyway, I'm guessing that all this relates to Moore's dislike of local variables.

Once more, I do have to ask myself how broad a class of problems he had been working on at the time of the talk. Maybe the code for super efficient CAD systems is fundamentally mappable to functional programming, and that's why he doesn't much have to concern himself much with state variables? By the way, he does allow for 'system' variables, it's the 'application' variables that get him going...

It is necessary to have variables. Color Forth has got a whole slew of system variables for something ... Variables are essential. [Yet] I don't see any use for a small number of variables and I don't see any use for variables which are accessed instantaneously.

So variables are an interesting, possibly treacherous monkey in the wrench works (as opposed to monkey wrench in the works) that I will have to watch out for as North development proceeds.

Here's another possible disconnect between his work and the FSA:

The world has changed in the last twenty years in ways that maybe are obvious but I think no one would have anticipated. When I first started in this business in fifty seven computers were used for calculating, computing. ... I don't know the statistics but I would guess that most computers don't compute, they move bytes around. ... But for today's applications, implementing protocols or displaying text, arithmetic is not necessary. A computer should not be optimized for arithmetic and mine are not.

Well, mine is. GenAPro stands for General Application Processing, which means the FSA will do math, move bytes, and twiddle bits. For embedded service, it simply has to do all three.


Heading North

So ... much to consider. Chuck is like the "Wizard of Stacks." I'm reminded that compilers use stacks as they parse high level languages into machine code. Is Forth the magic bullet for bypassing a major step of language complexity? I believe it may be.

And what about the interaction with underlying hardware? In "Why Forth? - Part 1", I jokingly wrote: "I'd accuse him of stealing my ideas but he sort of got there first. Of course, I designed the machine first and am now tossing a language at it, while he went the other direction." I'd say my current goal is to optimize the FSA for North as much as possible without sacrificing its general purpose nature. I mentioned above about experimenting with having some local testing at each sequencer. This came about when I started first coding a Forth interpreter. Suddenly the ALU was getting a lot more action than it ever had when I was writing demo math routines. Since I intend the ALU to be available as a resource to a multiple number of nearby sequencers (can you say, "bottleneck?"), it wasn't so good to have the Forth kernel starting to hog it. So I moved simple equality testing to individual sequencers (and in doing so lost a bunch of control bits to use as status bits, but there you go).

Remember Moore's 'fetch-plus' '@+' operator? I could conceivably leapfrog him by having counters built into the top two stack slots. However, this would mean adding a special 'stack sequencer' to the architecture in addition to the 'standard sequencer' and I don't think I want to do that. Not every programmer will want to use a 4-pack to run North, some will stick to pure machine language. It's that general purpose thing again. OTOH, I have uncommitted fields still available in the instruction set (indeed, fields already reserved for specialty operations) that I could dedicate to stack stuff.

Back to the ALU for a minute. Just as sequencers can be dropped in to a hardware design wherever desired, the standard ALU is meant to be dropped in as a super fast 'peripheral', and even though there are multiple buses (data bus, test bus ... more!) I will still have to provide ways to resolve the inevitable contention issues. I even added an extra clock phase, 'wait', to the original trigger - crunch - settle, because even after the logic in the sequencers, ALUs, and everything else has settled, if any entity is trying to send or receive any kind of data, it will sometimes have to wait for traffic to clear.

Although I won't really want to, I may have to bite the bullet and come up with something besides the standard sequencer to semaphore all this information around. Whatever form it ends up taking, one of its prime jobs will be to enforce the security hierarchy described in the previous blog.

It is becoming obvious to me that North will have some major differences from standard Forth (you know, if there were a standard Forth). New North definitions will be necessary to support the FSA's unusual instructions and augmented hardware. New architecture, new "_orth".

At this point, one big difference is the kernel being in a second sequencer, offset from the definitions. In real Forth, you are always 'inside' Forth. Here is a typical Forth outermost loop, albeit with nonstandard Forth commenting:

: QUIT BEGIN
                // clear the return stack
                // fetch a line of input using QUERY
                // execute the input using EXECUTE
                // ." ok" CR
     0 UNTIL ;  // loop forever

All of my kernel code should be inside there somewhere. I say "should be" for two reasons. First, Forth was created to be a portable, self contained operating system with everything you need to use defined as a word in its dictionary. You live and write code within that dictionary (yes, I promised you'd never see the terms 'word' & 'dictionary' again in this blog, but when I'm basing an article on a talk by the inventor of the language you've gotta give me some room to breathe!).

Second, I'm on record as praising the self referential, metacompiling languages like Forth & Lisp as being superior to even my beloved C. Problem is ... I'm a control freak. For me, there's something more clear about having the kernel off to the side, manipulating the collection of 'passive' definitions from a slight distance. Some part of me won't consider my 'perfect' language to be perfect by my own standards until it reaches this self referential peak, and yet that final consummation will be just that: final. I'm afraid that project will stay near the bottom of my in basket for a long time. Alas and alack, there's no time for it all!

One thing that won't be sacrificed is keeping all program entities remaining "first class". In a programming language, something is considered first class if it can be

  constructed at runtime
  assigned to a variable
  passed as a parameter
  returned from a subroutine

These comprise a sort of defacto definition of a powerful language. For example, C doesn't meet the 'constructed at runtime' standard. There have been C programs around for years that write other C programs, but the originating program and its output have to be compiled separately. That's a clunky mechanism compared to a language that can write more of itself from within itself and run it immediately. Of course Forth doesn't have functions per se, but definitions communicate with each other by way of the parameter stack so it amounts to the same thing.

This next is a little off the subject of language development, but I'll fit it in quickly because it is an architectural issue. Besides bus control, another issue I've been grappling with recently is that of "interrupts". An interrupt can be as innocent as a keystroke or mouse click, or as important as a core meltdown alarm at a nuclear reactor. Either way, they are something a user will want a program to respond to in reasonable time. A 'quiet' way to handle such input is by "polling" - a program loop checks each possible event source and responds if it stumbles over one. An interrupt on the other hand, is like a slap in the face: "Stop what you're doing and answer me right now!," as I described its effect at the bottom of "Controlling Complexity".

Both methods ultimately accomplish the same thing, but the difference is that with polling, the program is looking for the event on purpose, while the interrupt comes as a surprise. So the program has to save the state of what it's in the middle of - any stacks and/or variables that handling the interrupt might overwrite - and reload them later to pick up where it left off. Long story short: I've decided I won't put interrupt handling logic within individual sequencers. This is what multiprocessing and the idea of dropping in sequencers is supposed to be all about. If a design needs to deal with interrupts, have one or more dedicated sequencers intercept them first. Obviously, there still has to be a rapid forwarding of the event to its ultimate destination, but at least this interception method gives things a chance to be handled more gracefully, and without complicating the logic of every single seq in the system.

What else ... while reading postings on comp.lang.forth, I found that I wasn't the first one to come up with the idea of searching through the dictionary by way of some sort of hash code. I'm so, so surprised I didn't do it first. I didn't read far enough to see if anybody else is ordering the definitions by hash code and then doing a binary 'divide and conquer' search to find the target def, but they probably are.

One result of this approach is that my kernel must handle numbers differently. In traditional Forth, if a search through all the linked-listed definitions doesn't come up with a match, the input is considered to be a number. That is a long long path to take merely to decide that something's a number. Better I think to have the kernel recognize digits (and '+' & '-' & '.') right off the bat. For hexadecimal input, the 'numerals' A through F must also be dealt with. Original Forth also let you work in number bases from binary through base 36 (10 digits plus the 26 capital letters). Who in the world does actual computing with base 36? Or base 35, or base 21 or ... ? North for the FSA will be practical.

Threaded code by way of a call stack runs very fast, but admittedly isn't quite as fast as if the definitions involved in a compiled entity were all lined up end to end and fell through into one another. That's what I was trying to get at with my "Bridge Too Far" reference while discussing loops above. If certain entities can be written into memory directly as machine code, they can then run without having calls interspersed among the instructions.

In my mind, I think of this as "laying down tracks," which makes it sound like recording music. In a way, maybe it is at that. This is another reason I like having the kernel separate from the definitions, which are always in flux (new ones being added, some being dropped, all of them being reordered by hash code from time to time). Some things - jump tables come to mind - seem to fit better in the more stable sequencer where the kernel resides.

Things laid down in memory somewhere South of the kernel wouldn't necessarily have names, just pointers to them. They'd be "anonymous functions" like many functional languages have, and like some scripting languages have begun to implement. The big drawback here would be the need to add a "garbage collector" to North. Garbage collection is a form of automatic memory management. Periodically, a routine runs that looks for pointers that aren't addressing an entity that's being used anymore, and gives the space it takes up back to the memory "heap". It is a lot like defragmenting a disk drive.

The problem is that this doesn't fit well with embedded programming, where you kind of want the programmer to take direct responsibility for what he or she is doing with the memory resources. You wouldn't want a mission critical process to be delayed by some garbage collector routine that suddenly decides to take over at the exact wrong time.

I know all too well that it is not easy to stay on top of memory management. I once completely filled up the disk drive of a server for five workstations due to a "memory leak". My first large C program was a personal project, an ecological simulation called "Whales and Plankton." I would stay late tweaking the genetics of the whales so they would evolve and get better at eating plankton, then go home after setting things up to run overnight. One time I wrote a loop that kept allocating memory for newborn whales but not freeing the memory of those whales that had passed on to that great ocean in the sky. When the other engineers came in the next morning, their programs wouldn't run - there was no room for them. I wasn't in too much trouble, I think the system administrator blamed himself for not having set up limits to the memory any individual program could claim in the first place. Still, it was embarrassing, and I made sure to avoid springing any more leaks after that.

Revisiting this issue here in August 2011, I have clarified my thinking somewhat on what I mean by "laying down tracks." I am proposing the following format for a condensed case statement similar to the example in "Deciding to Get Loopy":

: case-1 :: ' nope ' thar ' that ' this defal ; 30000 ; 99 4 4 case ;;

This is a colon definition for creating a case statement that will have the definition name 'case-1'. The double colon tells the compiler to expect a reserved word (in this case, 'case') at the end of the definition, which ultimately closes with the ';;'. This double semicolon to end colon defs is what I proposed above, leaving single semis available to act as "return or jump" as prescribed by Doctor Moore.

Working to the right from the reserved 'case', the first '4' tells how many switches (including a default in this example) there will be in the final case statement. Then come three specific switching values. Note the lack of a single semicolon between '4' and '99' so that '4' will fall through to '99'. OTOH, '99' will break past '30000' due to the explicit ';'. '30000' also breaks past 'defal', which is another reserved word optionally used to point to a default case if none of the specific numeric values are input to 'case-1' when it runs.

Finally the 'ticked' names are pointers to the parameter fields of the (hopefully already written!) definitions of the routines that are to be run for each different input value. By the time 'case' has reached these last four stack parameters, it has already laid down the "bundle of tested jumps" described in "Deciding to Get Loopy" and merely has to place the pointers in their proper slots. If everything works as planned, when

somevar case-1

is invoked, 'case-1' will consume 'somevar' off of the parameter stack, and then replace itself on the call stack with one or more (more, if somevar is a case that falls through) pointers to the definition(s) to handle the somevar input value. I BELIEVE this double colon approach has to be faster and more compact than trying to kludge up an equivalent case statement in a more traditional Forth-like way. Maybe though, if I write a lot more regular Forth, I'll end up proving myself wrong.

One final issue to touch on before I start winding this down ... In "Type Casting", I proposed a namespace format,

.namespace.forthword

as something that might replace the "vocabularies" of traditional Forth. It is perhaps a workable idea I'll follow up on, but it screws up the syntax so I'm rethinking something along the lines of

.. .namespace.forthword

where the '..' will be a North definition to trigger the handling of the namespace format. This is still not perfect, as I'll expand on soon, but at least it will prevent something like:

.abc.def

that in the original formulation would be confused with a token for a hex fraction (with an extra 'hexadecimal point' in the middle of it yet).

This is yet another example of the always challenging "English Versus the Machine" interaction. Getting from human language to machine language never seems to be as straightforward as one would like. Most every higher level language starts out with a simple syntax - the way the elements of source code 'read' to the programmer - and most every HLL ends up with an annoying exception or two to that underlying elegance. The strings I wrote about a few blogs ago tend to be one of the worst offenders, by the way.

Pure Forth avoids these complications better than any other serious HLL I've come across, probably because its stack based paradigm is already so close to the machine. And yet I've already messed this up by having the kernel directly handle numbers. My excuse is better efficiency, but still. My namespace proposal is even uglier: '.. .namespace.forthword' isn't even in the proper order. It should at least be '.namespace.forthword ..'! But '.namespace.forthword' is a compound token, which is not something that can easily be placed on the stack without a little help first. Maybe I'll just drop it altogether.

What to drop, what to add, what to think of next. I believe this will be my last blog for awhile. I've definitely gotten way ahead of myself; my ideas running far beyond their realization. I look at the work I've set out in these essays, and it is a bit daunting, both alarmingly and delightfully complex. I've even been speculating on what the FSA would look like if expanded beyond 16 bits ... stop me before I design again!


Can Computing Be Made More Simple?

Well, we've kind of lost sight of Chuck, haven't we? Yet that's on purpose - I wanted him to have (most of) the last words. The theme of this essay started out to be simplicity and that's the theme we'll end with.

The goal was very simple: to minimize the complexity of the hardware software combination. As far as I can see no-one else is doing that. Some lip service perhaps, but no-one is trying to minimize the complexity of anything and that is a great concern to me.

We are building a culture which can not survive as trivial an incident as Y2K. Once we lose the billion dollar fabrication plants and once we lose the thousand man programming teams how do we rebuild them? Would be bother to rebuild them? Are computers worth enough to demand the social investment that we put into them. It could be a lot simpler. If it were a lot simpler I would have a lot more confidence that the technology would endure into the indefinite future.

This talk was in 1999, and the "Year 2000 Problem" was making everybody very edgy. We did survive it, and with so little disruption that most people immediately seemed to think, "Oh, that was nothing." 'Most people' don't know how much frantic effort went into updating millions of lines of software in the late 90's just so Y2K would turn out to be a speed bump rather than a drive off a cliff. People might have had a more realistic appreciation in the long run if there actually had been a few minor disasters.

Simplify the problem you've got or rather don't complexify it. I've done it myself, it's fun to do. You have a boring problem and hiding behind it is a much more interesting problem. So you code the more interesting problem and the one you've got is a subset of it and it falls out trivial. But of course you wrote ten times as much code as you needed to solve the problem that you actually had.

Ten times code means ten times cost; the cost of writing it, the cost of documenting it, it the cost of storing it in memory, the cost of storing it on disk, the cost of compiling it, the cost of loading it, everything you do will be ten times as expensive as it needed to be. Actually worse than that because complexity increases exponentially ... 10x Maintenance ... Ten times the bugs!

My contention is that every application that I have seen that I didn't code has ten times as much code in it as it needs. And I see Forth programmers writing applications with ten times as much code as is necessary.

I have found that teaching someone Forth does not mean that he is going to be a good Forth programmer. There is something more than the formalism and syntax of Forth that has got to be embedded in your brain before you're going to be effective at what you do.

It's a rule of thumb in the coding world that some programmers are ten times more productive than the average. And nobody can really say why. Yet it is a fact - some people just 'get it.' Where does your humble author rate himself on this scale of 1 to 10? I give myself the geometric mean: 3.16. I'm good, but I'm slow. Anyway, Moore finds himself frustrated by his inability to find a way to train better programmers:

I wish I knew what to tell you that would lead you to write good Forth. I can demonstrate. I have demonstrated in the past, ad nauseam, applications where I can reduce the amount of code by 90% percent and in some cases 99%. It can be done, but in a case by case basis. The general principle still eludes me.

I suspect the general principles are in fact buried throughout this very talk. We merely have to dig it out and internalize it. I've got to internalize it. I suspect a key is one of the words he keeps repeating:

So how do you avoid falling into this trap? How do you write one times programs? ... You factor. You factor, you factor, you factor and you throw away everything that isn't being used, that isn't justified ... Small applications, application isn't the right word. Small bits of code to do a particular thing and are not generalized to do anything else.

I've written very little Forth myself. At this point I'm still in the implementation stage. More accurately, the pre-implementation stage, considering the current upgrade process I'm going through with the FSA instruction set and simulator. Yet I am truly trying to internalize the lesson of simplicity as my efforts round the final turn.

There seems to be a propensity to make things complicated. People love to make them complicated ... I think there is perhaps an optimal level of complexity that the brain is designed to handle.

It is not possible to have a practical language running on a powerful system without both the software and the hardware being pretty complex. At least, once the kinks are worked out of the hardware much of its complication becomes invisible to the programmer. Still, the underlying logical layout - the architecture - has to be understood to make the best use of it.

As for the software, a certain level of complexity, ranging from basic syntax to high level abstractions, is unavoidable. All the more reason to simplify as much as possible wherever possible.




Note:

I have reordered some linking within this blog. Where "Next," below, used to link to Silicon Brain, That article and its sibling Silicon Brain, Part Deux, have been moved to the "Naive Speculations" section on Intro page. The reason for this note is that although the AI essays have almost nothing to do with computer languages, the linked article does have some discussion of FSA programming about halfway down under the title: "Build a Silicon Brain in Your Garage."





         Introduction to "The Perfect Language"    —   Table of Contents
         Secure Thoughts    —   Previous
         Compiling On    —   Next
         Glossary




Started: July 4, 2011