Tali Forth for the 65c02

[scotws]

I had really, really hoped to get this finished before Spring, but the weather has turned warm too early and people are insisting I start doing stuff in the garden instead of sitting in front of the computer. So, I'm presenting an almost-finished ("Alpha") variant of Forth I have been working on: Tali Forth for the 65c02. Tada!

Tali Forth is a Subroutine Threaded Code (STC) implementation specifically for the 65c02, modeled on the ANS Forth standard. I wrote it because I wanted to understand the inner workings of Forth and have a modern version of the language for my Übersquirrel. Its aims are, in rough order of priority:

Simple. The primary aim is to help understand me a complete Forth system byte by byte. This is why the STC format was chosen, and why the dictionary has a bizarre structure (more on that later). This is also the reason the source code is perversely over-commented.

Specific. A lot of other Forths are written with a general structure and then ported. This is for my favorite 8-bit MPU and that MPU only, with its strengths in mind.

Standardized. One problem with FIG Forth is that it is ancient, and learning Forth with it feels like trying to learn English by reading Chaucer. Tali Forth follows the ANS Draft Standard 200x where it can. For example, it uses PARSE-NAME instead of WORD.

Speedy. Tali Forth places speed over size (within reason). Still, the aim is to keep the core stuff and the kernel routines in 8k of ROM.

This is what I managed to code before global warming forced me out of the cellar:

Code: Select all

ELSE THEN IF WORDS DROP 2DROP ! @ >R R> R@ OVER 2OVER DUP ?DUP 2DUP SWAP 2SWAP NIP TUCK ROT DEPTH 1- 1+ FALSE TRUE BRANCH (BRANCH) 0BRANCH (0BRANCH) BEGIN AGAIN ABS DABS + - * / */ */MOD UM* M* UM/MOD UD/MOD SM/REM FM/MOD MOD /MOD M+ AND OR XOR INVERT NEGATE DNEGATE MAX MIN LSHIFT RSHIFT S>D D>S D+ D- <# # #S HOLD SIGN #> U. U.R UD. . .R D. D.R 2 1 0 < = > 0= 0< COUNT >IN TYPE EMIT CHAR TOUPPER KEY BASE HERE PAD UNUSED ERASE FILL CELL+ CELLS CHAR+ CHARS C, C! C@ CMOVE CMOVE> ALIGN ALIGNED ALLOT , ' >BODY >NAME EXECUTE EVALUATE STATE COMPILE, : ; ] [ POSTPONE IMMEDIATE CREATE VARIABLE +! SOURCE DECIMAL HEX BINARY DIGIT>NUMBER NUMBER >NUMBER BL CR SPACE SPACES ." (.") S" (S") .( ( \ /STRING -TRAILING FIND ACCEPT PARSE PARSE-NAME .S SEE DUMP QUIT ABORT LITERAL (LITERAL) BYE

(WORDS returns a few more, but those are just dictionary headers without code). The most important stuff still missing are the loop structures such as DO, LOOP, UNTIL, then DOES>, and some stuff like CONSTANT and MOVE I probably could do in a few hours if I wasn't busy planting radishes. Reference design is gForth, so what works in Tali Forth should produce identical results or have a good reason not to. There is a .ods (for Windows users: .xls) file with more details, though it is not complete. I've followed the Forth tradition of putting the code in the public domain.

I cannot stress enough that this is alpha-level code. When it says "tested" on the spreadsheet, that means I've tried one or two trivial cases and it didn't blow up in my face. There is little error checking, nothing has been optimized, and a lot of stuff was coded at odd times of the day. You'll see the source code is riddled with "TODOs". I hope to be able to work on it some more in the coming months, but I know how that turned out last year, so I'm presenting what I have in the hope it might be interesting to somebody while I'm digging the veggie patch.

There is a binary included in the attached ZIP package called ophis.bin that will run on py65mon at your own risk. Load with

Code: Select all

py65mon --mpu 65C02 -r ophis.bin 

It currenty loads as 16k at C000 because I'm too lazy to change the default input/output address of py65mon from F000.

I'll talk about the dictionary structure in a follow-up here soon. Comments and suggestions are of course most welcome, and thanks to everybody who made this possible here and in other parts of the net!

[scotws]

A note on the dictionary structure, which, er, is slightly different that other Forths: Since the first aim is to keep everything as simple as possible, I wanted the executive tokens (xt) to be an address that points to the the head of the corresponding dictionary entry (in other words, the link). This simplifies things enormously because everything else is just an offset that can be read by instructions with the format (XT),Y (assuming xt is stored on zero page). This is realized by starting every entry with a BRA instruction. Yes, every single entry.

Code: Select all

                        7 6 5 4 3 2 1 0  bit 
                       +---------------+
      (xt) l_xxxx -->  |   BRA ($80)   |  +0 offset from xt (dictionary head)
                       +-            --+
           a_xxxx <--  |               |  +1 
                       +-+-+-+---------+
                       |I|N|C| Length  |  +2 
                       +-+-+-+---------+
                       |               |  +3 
                       +-    Link     -+ 
           l_yyyy <--  |               |  +4 
                       +---------------+
                       |               |  +5 
                       +-  Code End   -+ 
           z_xxxx <--  |               |  +6 
                       +---------------+
                       |               |  +7 
                       +-             -+
                       |     Name      |
                       +-             -+
                       |           ... |
                       +---------------+
           a_xxxx -->  |               | 
                       +-             -+ 
                       |     Data      |
                       +-             -+
           z_xxxx -->  |           ... |
                       +---------------+

This wastes two bytes and up to four cycles per access. The penalty is not quite as bad as I had feared, because we save time with FIND by not having to deal with negative indices. Also, Tali Forth supports basic native compiling for short words (the function of the z_xxxx pointer that references the end of the Data Field where the code is). So DROP is not JSR BRA INX INX RTS in compiled code, but simply INX INX. Still, this is an admittedly curious decision, and I'm not sure I'd choose it if I were following other priorities.

Other notes on the header: I is the bit for Immediate, N for Native Code, and C for Compile Only.

The other design decisions are straightforward in comparison, see the stack.txt and memorymap.txt files in the ZIP archive for details.

[BigDumbDinosaur]

scotws wrote:

...people are insisting I start doing stuff in the garden instead of sitting in front of the computer.

"People are insisting?" Would this "people" happen to be your wife?

I'm not a Forth user, so I certainly am not qualified to comment on your efforts to date. I will applaud you, though, for the effort to build an ANS-compliant (?) version. Implementing any language/operating environment is no mean feat by any yardstick.

Periodically, I get the notion to look at Forth, but being as heavily invested as I am in UNIX/Linux and all that that entails, can't seem to come up with a good reason to leap Forth (<groan>). If I did, I fear that I'd want to scratch-write a 65C816-specific kernel, which for me would be too much like Chaucer trying to learn English by hanging out in a Detroit ghetto: same language but a very alien dialect. Dunno if RPN has anything to do with it...

[BigDumbDinosaur]

scotws wrote:

A note on the dictionary structure, which, er, is slightly different that other Forths...by starting every entry with a BRA instruction...

In a perverse way, your dictionary structure does make sense for use with an eight bit MPU. The BRA instruction is certainly fast enough at three cycles, and the dictionary structure is fully relocatable. You could have used some other structure type (a lexically sorted list with binary search lookup comes to mind), but would have incurred processing expense in one place or another. If it works...use it.

[scotws]

Thank you for the encouragement!

BigDumbDinosaur wrote:

Periodically, I get the notion to look at Forth, but being as heavily invested as I am in UNIX/Linux and all that that entails, can't seem to come up with a good reason to leap Forth (<groan>).

Learning Forth has a high entertainment value if you read stuff by its creator, Chuck Moore. There is a great interview with him in the book Masterminds of Programming (http://www.amazon.com/Masterminds-Progr ... 0596515170) where he calls operating systems a scam by people like Bill Gates, and says a program with a million lines of code means that whoever wrote it hasn't understood the problem. It seems he uses custom CPUs for his current work that are 18 bits wide -- three "bytes" of six bits each. He has since moved on to "Color Forth" where the color indicates the function (http://www.colorforth.com/cf.htmI). He's a, er, colorful character all around.

As for the language itself, the two really fun things are the completely different perspective on how to interact with computers and the mental challenge of working with the stack. I've given up pretending I can read anything but the most trivial Forth code directly, and sit down with a pencil and create stack diagrams. The advantage of that approach is that I've been able to adapt a bunch of stuff (SM/REM, FM/MOD) by back-converting to assembler so it is faster than pure Forth.

[GARTHWILSON]

scotws wrote:

This is realized by starting every entry with a BRA instruction. Yes, every single entry. [...] This wastes two bytes and up to four cycles per access. The penalty is not quite as bad as I had feared, because we save time with FIND by not having to deal with negative indices.

I wouldn't worry too much about the speed of FIND. I started a topic nearly 10 years ago on dictionary hashing for making FIND work faster, at viewtopic.php?f=9&t=555 but then later, 2/3 of the way down the first page, reported finding that I had a lot of things slowing compilation down more than my FIND which had to look through a 500-word, unsorted, unhashed, single list of words:

Garth wrote:

FIND is a primitive, but WORD is a pretty long secondary, as is EXPECT , QUERY , and INTERPRET which hands the found word off to COMPILER which is also a secondary. At least WORD uses primitives SKIP and SCAN for the iterative processes, but EXPECT has a loop in high level that runs once per character received.

But that's not all. Since it's a 4.5" x 6.5" SBC with no mass storage of its own (yet) and I'm using the PC to write, edit, and store the source code, the TIB is being filled from the RS-232 receive buffer, and that's being filled by an interrupt-service routine that services the serial port. All that's being done in high-level too, including the interrupt service. Clearly I never took the compilation speed seriously, and now it's the computer's sorriest (is that a word?) performance area. You can still write a new word a few lines long and compile it and have it running almost instantly, but compiling several pages of source code at a time definitely gives you some time to twiddle your thumbs.

scotws wrote:

Also, Tali Forth supports basic native compiling for short words (the function of the z_xxxx pointer that references the end of the Data Field where the code is). So DROP is not JSR BRA INX INX RTS in compiled code, but simply INX INX. Still, this is an admittedly curious decision, and I'm not sure I'd choose it if I were following other priorities.

For the event that I ever get far enough to write my own STC Forth, I've thought about having something in the header give a number that could be used to tell whether to JSR to the routine or straightline it. It would generally be correlated with the length, but there could be other influences on it too. Then you could set a threshold at compile time which would tell the compiler what the priority of speed versus memory is. Obviously the words like DROP that could be straightlined with three or fewer bytes will never be JSR'ed but your threshold chosen at compile time would determine where to stop straightlining and where to start JSR'ing.

scotws wrote:

Other notes on the header: I is the bit for Immediate, N for Native Code, and C for Compile Only.

Is this something you determined has better application for STC? In the ITC I've been using, internals get compiled by other words which use ?COMP, so there's no compile-only bit. For example, unnest gets compiled by ; which will stop with the error message if it is encountered when the compiler is not on. 0branch is compiled by IF and other words which will stop with the error message if they're encountered when the compiler is not on, and so on.

Quote:

he calls operating systems a scam by people like Bill Gates, and says a program with a million lines of code means that whoever wrote it hasn't understood the problem.

I like that!

Quote:

As for the language itself, the two really fun things are the completely different perspective on how to interact with computers and the mental challenge of working with the stack.

It's just a different way of thinking, which, after the programmer really catches on, seems to work much better.

Quote:

I've given up pretending I can read anything but the most trivial Forth code directly,

I've seen an awful lot of unreadable Forth, but I mostly blame that on the programmer, not the language. Although Forth makes good programmers better, it also makes bad ones worse. Actually, I've seen an awful lot of unreadable code in every language, and the difficulty of making assembly readable is why I did the program-structure macros, which I mostly patterned after Forth ones. It's usually a pain to look at someone else's code, so I try to be nice. In a way, my own code becomes someone else's too after I've been away from it for a while and have to come back to it years later to make a change, so I try to make it as clear as possible.

Quote:

and sit down with a pencil and create stack diagrams. The advantage of that approach is that I've been able to adapt a bunch of stuff (SM/REM, FM/MOD) by back-converting to assembler so it is faster than pure Forth.

The fastest Forth is where it's run on a processor whose machine language is Forth. Then it screams performance. Even the Harris RTX-2000 16-bit Forth processor 25 years ago routinely ran 16 million Forth instructions per second at 12MHz (due to some compiler optimization).

[BitWise]

scotws wrote:

Also, Tali Forth supports basic native compiling for short words (the function of the z_xxxx pointer that references the end of the Data Field where the code is). So DROP is not JSR BRA INX INX RTS in compiled code, but simply INX INX. Still, this is an admittedly curious decision, and I'm not sure I'd choose it if I were following other priorities.

Do native words still operate as standard words? Would something like ' DROP EXECUTE work as expected?

[BigDumbDinosaur]

scotws wrote:

. There is a great interview with [Chuck Moore] in the book Masterminds of Programming (http://www.amazon.com/Masterminds-Progr ... 0596515170) where he calls operating systems a scam by people like Bill Gates, and says a program with a million lines of code means that whoever wrote it hasn't understood the problem.

I don't agree with Moore on the scam angle applying to all operating systems—it wouldn't be accurate to call Linux, which is free for the downloading, a scam. Also, without an operating system of some kind, support for multiple users and concurrent task execution on a single machine would be very difficult to implement. Any such operating system by nature is going to be relatively complicated and is going to have a lot of code. However, it's interesting to note a comment from the Brian Kernighan/Dennis Ritchie book The C Programming language, which was published in 1978, describing the flexibility of K&R C:

• Of the 13,000 lines of [UNIX kernel] code, only about 800 lines at the very lowest level are written in assembler.

Clearly an efficient operating system kernel can be written, even in a compiled language such as C—if it implements what an operating system should implement (e.g., mass storage management) and does not bulk up the kernel with innumerable bells and whistles, as is the case with both Microsoft Windows and the Macintosh OS. In particular, a GUI is what would contribute to millions or tens of millions of lines of code. For example, Windows 95 SR1, which was released 19 years ago, had 11 million lines of C++ code. It was a huge resource hog (as are all Windows versions) and about as stable as an intoxicated three-legged elephant.

There's no question that Bill Gates et al have created a snake oil situation with operating systems. Anyone who builds their information technology around Windows has only subscribed to the notion of vendor lock-in and will be scammed by the need for endless updates and patches. Also, consider the alarmists who are urging everyone to discontinue using Windows XP because Microsoft has officially ended support for it (unofficially, it's still supported if you are willing to pay for support—definitely a scam, if there ever was one). What's the alternative these alarmists are recommending? Why, Windows 8, of course, which is currently the world leader in bloatware and obtuse user interfaces. And when Windows 8 support ends, the cycle will be repeated. That is a scam, without question.

[HansO]

BigDumbDinosaur wrote:

Clearly an efficient operating system kernel can be written, even in a compiled language such as C—if it implements what an operating system should implement (e.g., mass storage management) and does not bulk up the kernel with innumerable bells and whistles, as is the case with both Microsoft Windows and the Macintosh OS.

You can add Linux to this list of massive bloated kernels. It is so by design.
A quote from 2009 by Linus:

The Linux kernel is getting too big too fast, and that's negatively affecting Linux performance. While this might sound like a message from Microsoft's marketing team, it's actually a frank admission that Linus Torvalds made Monday in a roundtable discussion at the LinuxCon event in Portland, Ore.

Asked whether features are being added to the Linux kernel too quickly, and whether this is affecting Linux performance, Torvalds acknowledged that this is indeed a problem. The Linux kernel has also grown to the point where it's no longer streamlined and efficient, Torvalds added.

"The kernel is huge and bloated, and our icache footprint is scary. I mean, there is no question about that. And whenever we add a new feature, it only gets worse," Torvalds said at the event

Have a look at micro kernel systems if you really want a non-bloated kernel operating system. For example MINIX 3 is a free, open-source, operating system designed to be highly reliable, flexible, and secure. It is based on a tiny microkernel running in kernel mode with the rest of the operating system running as a collection of isolated, protected, processes in user mode.

[scotws]

GARTHWILSON wrote:

Then you could set a threshold at compile time which would tell the compiler what the priority of speed versus memory is.

I never thought of providing that flexibility, that's a really cool idea. The plan so far is when everything is written and optimized, I figure out a sane rule which words should be Native Compile and which shouldn't (say, not longer than x bytes and faster by at least y percent) and then give those words a fixed "NC" flag. -- I might not include that in this Forth because of the added complexity, but I've pretty much decided to switch to the 65816 after this machine, and then I hope to be up for a more ambitious take on Forth.

Using a bit for the Compile Only etc flags sort of grew out of the bits used by FIG Forth. It makes for a quick test: Get the Length Byte at xt + offset, mask everything but the bit, and branch if zero. Given the problems I had understanding how POSTPONE works, I was happy for everything that simple .

Quote:

Even the Harris RTX-2000 16-bit Forth processor 25 years ago routinely ran 16 million Forth instructions per second at 12MHz (due to some compiler optimization).

I had actually checked at some point, and it seems that nobody is making those chips anymore, which is a pity. Lots of FPGA designs, but that doesn't feel the same.

It would probably be considered poor form (and a bit of a challenge) to remove the one from Cassini-Huygens ...

[scotws]

BitWise wrote:

Do native words still operate as standard words? Would something like ' DROP EXECUTE work as expected?

It does, because ' (tick) calls PARSE-NAME and then FIND, so it never sees the internals of the word.

But Native Compile is only for compiling anyway, during interpretation, it's always a subroutine jump. The difference is that "normal" compilation adds "JSR f_drop" to the word's definition, and NC inserts "INX INX" instead.

[BigDumbDinosaur]

HansO wrote:

You can add Linux to this list of massive bloated kernels. It is so by design.
A quote from 2009 by Linus...

Actually the Linux kernel started to acquire bloatware characteristics around 2000-2001, which was when commercial influences began to alter the development path. Creeping featurism tends to be a problem with any operating system that sees contributions from many sources. Everyone has their favorite little feature they want added and before you know it, the kernel is as big and unwieldy as the Titanic. The shift from 32 bit to 64 bit code seems to have actually made it worse, suggesting that perhaps the GNU compiler is part of the problem. Also, the Linux kernel API has gotten monstrous, suggesting that a lot of obscure functions were added that probably would have been better left in the C library for use with user-developed code.

Anything I might develop for the POC series in the way of an operating system kernel will be constrained to what will fit in somewhat less than 64KB of RAM (i.e., one bank), so bloat will be somewhat self-limiting. Contrast that with Linux and Windows, which are virtual memory systems that theoretically know no size limitations.

[White Flame]

Since Forth environments are often operating systems, I don't think Chuck's speaking very sensibly there. Forth owns and manages the memory layout, ABI of functions, and abstracts storage devices and console communication via APIs, to say the least. It is a light-weight OS, no doubt, but an OS nonetheless.

[BigDumbDinosaur]

White Flame wrote:

Since Forth environments are often operating systems, I don’t think Chuck’s speaking very sensibly there.  Forth owns and manages the memory layout, ABI of functions, and abstracts storage devices and console communication via APIs, to say the least.  It is a light-weight OS, no doubt, but an OS nonetheless.

You raise a good point.

Any software that can directly interact with computer hardware and enable something useful to be accomplished can be characterized as an “operating system.”  Something as basic as the firmware in my POC unit fits that description.  It drives a console, interacts with memory, has an API jump table, keeps time, and even has rudimentary mass storage capabilities (very rudimentary).  So condemning operating systems en masse doesn’t really make a whole lot of sense to me.

To be sure, there are some horrid operating systems and some great ones, small ones and monstrous ones.  What really should be receiving condemnation is mediocre programming.  It shouldn’t take millions of lines of code to control mass storage and I/O, schedule processes, keep time and manage memory.  UNIX did all that and then some 30 years ago with around 13,000 lines of code, almost all of it in C.  Where did everything go wrong?

[GARTHWILSON]

Many here know far more about operating systems than I; but where is the dividing line between the kernel and the GUI that accompanies it for example? My DOS-based CAD is point-and-click, and obviously graphics, but there's no GUI in the OS itself. There was minor GUI when I was running GEOS under DOS. On my Linux machine, I use audio- and photo-editing software, streaming video, etc. which are amazingly complex yet not part of the OS. The GUI that came with the kernel does have things like thumbnail photo previews, and the mp3 files' icons, not to be outdone, start playing the music if you mouse over them (since it's not very helpful if they all play at once when you're looking at the folder's contents). It does not seem that the OS has any business being as big as modern ones. But where is the line between the kernel and the GUI? is the GUI part of the OS? Do programs that are very graphics-oriented particularly need a GUI that's external to the program? For desktop applications, we enjoy a lot of things that won't come simply; yet I'm not convinced that the way it's done is the way it should be done. Further, it is inexcusable that modern OSs want the amount of RAM and disc space that they do.