WIP to find crashing problem generating eturtle.exe
[hf86v099.git] / hforth.htm
1 <HTML>\r
2 <HEAD>\r
3 <TITLE>hForth - A Small, Portable ANS Forth</TITLE>\r
4 </HEAD>\r
5 <BODY>\r
6 \r
7 <P><I>Originally published in</I>Forth Dimensions XVIII/2, 30</P>\r
8 \r
9 <H1>hForth - A Small, Portable ANS Forth</H1>\r
10 \r
11 Wonyong Koh, Ph.D.</BR>\r
12 Taejon, Korea</BR>\r
13 wykoh@pado.krict.re.kr</BR>\r
14 \r
15 <H2>Background history</H2> \r
16 \r
17 <P>I started a personal project two and half years ago, which was in my\r
18 mind for quite a long time: Widespread Forth in Korea. Postfix is natural\r
19 to Korean people since a verb comes after an object in Korean language.\r
20 Also Forth does not restrict a programmer to use only alphanumeric\r
21 characters. A Korean Forth programmer can easily express his idea in\r
22 comfortable Korean words rather than to be forced to think in English. As\r
23 one might expect, there was an effort for Korean Forth. Dr. Chong-Hong\r
24 Pyun and Mr. Jin-Mook Park built a Korean version of fig-Forth for Apple\r
25 II computer in mid-eighties. Long-time FD readers may remember Dr. Pyun's\r
26 letter in <I>Forth Dimensions</I> X/6, 8. Unfortunately, Korean computer\r
27 community swiftly moved to IBM PC while Dr. Pyun wrote articles about\r
28 their work in popular programming and science magazines. It became\r
29 somewhat obsolete before being known widely. Despite of this and other\r
30 efforts Forth has been virtually unknown to most Koreans. Two and half\r
31 years ago I decided to restart it and looked for a vehicle for the\r
32 purpose. I found that there was no small ANS Forth system for IBM PC. I\r
33 decided to build one. In the course of ANSifying eForth I have replaced\r
34 every line of eForth source and felt that it deserved its own name. I\r
35 knew that there were Forth systems named as bForth, cForth, eForth,\r
36 gForth, iForth, Jforth and KForth. I picked <I>h</I> since it seemed not\r
37 yet used by anyone and also <I>Han</I> means Korean in Korean\r
38 language.</P>\r
39 \r
40 <H2>ROM model came first</H2>\r
41 \r
42 <P>eForth, which was written by Mr. Bill Muench and Dr. C. H. Ting in\r
43 1990, seemed to be a good place to start. I studied eForth source and Dr.\r
44 Ting's article in <I>Forth Dimensions</I> XIII/1, 15 and set the\r
45 following goals:</P>\r
46 \r
47 <UL>\r
48 <LI>small machine dependent kernel and portable high level code</LI>\r
49 <LI>strict compliance to ANS Forth</LI>\r
50 <LI>extensive error handling through CATCH/THROW mechanism</LI>\r
51 <LI>separated code and name space</LI>\r
52 <LI>use of wordlists</LI>\r
53 <LI>explicit consideration for separated RAM/ROM address space</LI>\r
54 <LI>simple vectored input/output</LI>\r
55 <LI>direct threaded code</LI>\r
56 <LI>easy upgrade path to optimize for specific CPU</LI>\r
57 </UL>\r
58 \r
59 <P>Most of them are adapted from eForth. I emphasize extensive error\r
60 handling since some of well-known Forth systems cannot manage as simple a\r
61 situation as divide-by-zero. In hForth almost all ambiguous conditions\r
62 specified in the ANS Forth document issue <CODE>THROW</CODE> and are\r
63 captured by <CODE>CATCH</CODE> either by user-defined word or by hForth\r
64 system.</P>\r
65 \r
66 <P>hForth ROM model is especially designed for a minimal development\r
67 system for embedded applications which uses non-volatile RAM or ROM\r
68 emulator in place of ROM. The content of ROM address space can be changed\r
69 during development phase and is copied later to real ROM for production\r
70 system. hForth ROM model checks whether or not ROM address space is\r
71 alterable when it starts. New definitions go into ROM address space if it\r
72 is alterable. Otherwise they go into RAM address space.</P>\r
73 \r
74 <PRE>\r
75   Alterable ROM address space       Unalterable ROM address space\r
76 ===============================    ===============================\r
77                                     name space of new definitions\r
78                                    -------------------------------\r
79 \r
80        RAM address space                  RAM address space\r
81 \r
82 -------------------------------    -------------------------------\r
83                                        data space / code space \r
84           data space                     of new definitions\r
85 ===============================    ===============================\r
86  name space of old definitions      name space of old definitions\r
87 -------------------------------    -------------------------------\r
88  name space of new definitions\r
89 -------------------------------\r
90 \r
91        ROM address space                  ROM address space\r
92 \r
93 -------------------------------    -------------------------------\r
94    data space / code space \r
95      of new definitions                      data space\r
96 -------------------------------    -------------------------------\r
97  code space of old definitions      code space of old definitions\r
98 ===============================    ===============================\r
99 </PRE>\r
100 \r
101 <P>Data space can be allocated either in ROM address space for tables of\r
102 constants or in RAM address space for arrays of variables.\r
103 <CODE>ROM</CODE> and <CODE>RAM</CODE>, recommended in the Appendix of the\r
104 Standard document, are used to switch data space between RAM and ROM\r
105 address space. Name space may be excluded in final system if an\r
106 application does not require Forth text interpreter. 8086 hForth ROM\r
107 model occupies little more than 6 KB of code space for all Core word set\r
108 words and requires at least 1 KB of RAM address space for stacks and\r
109 system variables.</P>\r
110 \r
111 <P>The assembly source is arranged so that more implementation-dependent\r
112 words come earlier. System-dependent words come first, CPU-dependent\r
113 words come after, then come all the other high level words. Colon\r
114 definitions of all high level words are given as comments in the assembly\r
115 source. One needs to redefine only system-dependent words to port hForth\r
116 ROM model to a 8086 single board computer from current one for MS-DOS\r
117 machine without changing any CPU-dependent words. Standard words come\r
118 after essential non-Standard words in each system-dependent,\r
119 CPU-dependent, and portable part. All Standard Core word set words are\r
120 included to make hForth an ANS Forth system. High level Standard words in\r
121 the last part of the assembly source are not used for the implementation\r
122 of hForth and can be omitted to make a minimal system. Current 8086\r
123 hForth ROM model for MS-DOS has 59 kernel words: 13 system-dependent\r
124 words, 21 CPU-dependent non-Standard words and 25 CPU-dependent Standard\r
125 words. System-dependent words include input/output words and other words\r
126 for file input through keyboard redirection of MS-DOS. For five of kernel\r
127 words, including <CODE>(search-wordlist)</CODE> and <CODE>ALIGNED</CODE>,\r
128 CPU-dependent definitions are used instead of high level definitions for\r
129 faster execution.</P>\r
130 \r
131 <P>System initialization and input/output operations are performed\r
132 through following execution vectors: <CODE>'boot</CODE>,\r
133 <CODE>'init-i/o</CODE>, <CODE>'ekey?</CODE>, <CODE>'ekey</CODE>,\r
134 <CODE>'emit?</CODE>, <CODE>'emit</CODE>, and <CODE>'prompt</CODE>.\r
135 Appropriate actions can be taken by redirecting these execution vectors.\r
136 <CODE>'init-i/o</CODE> is executed in <CODE>THROW</CODE> and when the\r
137 system starts while <CODE>'boot</CODE> is executed only once when the\r
138 system starts. One has better chance not to loose control by restoring\r
139 i/o vectors through <CODE>'init-i/o</CODE> whenever an exception\r
140 condition occurs. For example, serial communication link may not be\r
141 broken by an accidental change of communication parameters.\r
142 <CODE>'boot</CODE> may be redirected to an appropriate application word\r
143 instead of default word in a finished application. Traditional\r
144 'ok&lt;end-of-line&gt;' prompt (which is actually not) may be replaced by\r
145 redirecting <CODE>'prompt</CODE>.</P>\r
146 \r
147 <P>Control structure matching is rigorously checked for different control\r
148 flow stack items. Control-flow stack is implemented on data stack.\r
149 Control-flow stack item is represented by two data stack items as\r
150 below</P>\r
151 \r
152 <PRE>\r
153 Control-flow stack item     Representation (parameter and type)\r
154 -----------------------    -------------------------------------\r
155      <I>dest</I>                    control-flow destination      0\r
156      <I>orig</I>                    control-flow origin           1\r
157      <I>of-sys</I>                  OF origin                     2\r
158      <I>case-sys</I>                x (any value)                 3\r
159      <I>do-sys</I>                  ?DO origin           DO destination\r
160      <I>colon-sys</I>               xt of current definition     -1\r
161 </PRE>\r
162 \r
163 <P>hForth can detect the nonsense clause "<CODE>BEGIN IF AGAIN\r
164 THEN</CODE>" easily. <CODE>CS-ROLL</CODE> and <CODE>CS-PICK</CODE> can be\r
165 applied to the list of <I>dest</I>s and <I>orig</I>s only. This can be\r
166 verified by checking whether the ORed type is 1. I can not think of a\r
167 control-structure-mismatch that current hForth cannot catch.</P>\r
168 \r
169 <P>Number of words grows substantially as a Forth system is extended.\r
170 Dictionary search can be time-consuming unless hashing or other means are\r
171 employed. Currently hForth uses no special search mechanism, however,\r
172 maintains reasonable compilation speed by keeping shallow search depth in\r
173 addition to using optimized <CODE>(search-wordlist)</CODE>. Initially two\r
174 wordlists are in the search order stack: <CODE>FORTH-WORDLIST</CODE> and\r
175 <CODE>NONSTANDARD-WORDLIST</CODE>. <CODE>FORTH-WORDLIST</CODE> contains\r
176 all the Standard words and <CODE>NONSTANDARD-WORDLIST</CODE> contains all\r
177 the other words. Upon extending hForth, optional Standard words will go\r
178 in <CODE>FORTH-WORDLIST</CODE> and lower-level non-Standard words to\r
179 implement them will be kept in separate wordlists which are usually not\r
180 in the search order stack. Only a small number of non-Standard words to\r
181 be used by a user will be added in <CODE>NONSTANDARD-WORDLIST</CODE>.</P>\r
182 \r
183 <H2>RAM and EXE models follow</H2>\r
184 \r
185 <P>hForth package consists of three models: ROM, RAM and EXE model.\r
186 hForth RAM model is for RAM only system where name, code and data spaces\r
187 are all combined. hForth EXE model is for a system in which code space is\r
188 completely separated from data space and execution token (xt) may not be\r
189 a valid address in data space. 8086 hForth EXE model uses two 64 KB full\r
190 memory segments: one for code space and the other for name and data\r
191 spaces. EXE model might be extended for an embedded system where name\r
192 space resides in host computer and code and data space are in target\r
193 computer. Few kernel words are added to ROM model to derive RAM and EXE\r
194 models and only several high level words such as <CODE>HERE</CODE> and\r
195 <CODE>CREATE</CODE> are redefined.</P>\r
196 \r
197 <P>ROM and RAM models are probably too slow for many practical\r
198 applications as original eForth. However, 8086 hForth EXE model is more\r
199 competitive. High-level colon definitions of all frequently used words\r
200 are replaced with 8086 assembly code definitions in hForth EXE model.\r
201 Comparison with other 8086 Forth systems can be found in Mr. Borasky's\r
202 article "Forth in the HP100LX" <I>Forth Dimensions</I> XVII/4, 6.</P>\r
203 \r
204 <P>hForth models are highly extensible. Optional word set words as well\r
205 as an assembler can be added on top of basic hForth system. Complete\r
206 Tools, Search Order, Search Order Ext word set words and other optional\r
207 Standard words are defined in <I>OPTIONAL.F</I> included in 8086 hForth\r
208 package. 8086 Forth assembler is provided in <I>ASM8086.F</I>. Many of\r
209 Core Ext word set words are provided in <I>OPTIONAL.F</I> and all the\r
210 other Core Ext words except obsolescent ones and <CODE>[COMPILE]</CODE>\r
211 (for which <CODE>POSTPONE</CODE> should be used) are provided in\r
212 <I>COREEXT.F</I>. Complete Double and Double Ext word set words are\r
213 provided in <I>DOUBLE.F</I>. High level definitions in these files should\r
214 work in hForth for other CPUs. These files are loaded into 8086 hForth\r
215 for MS-DOS machines through keyboard redirection function of MS-DOS.\r
216 Complete Block, Block Ext, File and File Ext word set words are provided\r
217 in <I>MSDOS.F</I> using MS-DOS file handle functions. Other utilities are\r
218 also included in 8086 hForth package. <I>LOG.F</I> is to capture screen\r
219 output to an MS-DOS text file, which is edited to make Forth text source.\r
220 <I>DOSEXEC.F</I> is to call MS-DOS executables within hForth system. A\r
221 user can call familiar text editor, edit Forth text source, exit the\r
222 editor, load the source and debug without leaving hForth environment.\r
223 This process can be repeated without saturating address spaces if a\r
224 <CODE>MARKER</CODE> word is defined in the beginning of the Forth text\r
225 source and called before reload the source.</P>\r
226 \r
227 <H2>Multitasker</H2>\r
228 \r
229 <P>I had a chance to look at Mr. Muench's eForth 2.4.2. The multitasker\r
230 is the most elegant one among those that I have seen. It does task\r
231 switching through only two high-level words. I immediately adapted it to\r
232 hForth. Mr. Muench's multitasker is now included in P21Forth for MuP21\r
233 processor.</P>\r
234 \r
235 <P>In Forth multitasker each task has its own context: data stack, return\r
236 stack and its own variables (traditionally called user variables). The\r
237 contexts must be stored and restored properly when tasks are suspended\r
238 and resumed. In Mr. Muench's multitasker <CODE>PAUSE</CODE> saves current\r
239 task's context and <CODE>wake</CODE> restores next task's context.\r
240 <CODE>PAUSE</CODE> saves return stack pointer on data stack and data\r
241 stack pointer into a user variable <CODE>stackTop</CODE>, then jumps to\r
242 next task's <CODE>status</CODE> which is held in current task's user\r
243 variable <CODE>follower.</CODE> It is defined as:</P>\r
244 \r
245 <PRE><CODE>    : PAUSE   rp@ sp@ stackTop !  follower @ &gt;R ; COMPILE-ONLY\r
246 </CODE></PRE>\r
247 \r
248 <P>Advanced Forth users already know that '<CODE>&gt;R EXIT</CODE>'\r
249 causes high level jump for traditional Forth virtual machine. Each task's\r
250 user variable <CODE>status</CODE> holds <CODE>wake</CODE> and immediately\r
251 followed by user variable <CODE>follower</CODE>. Initially hForth has\r
252 only one task <CODE>SystemTask</CODE>. Its user variable\r
253 <CODE>status</CODE> and <CODE>follower</CODE> hold:</P>\r
254 \r
255 <PRE>\r
256 SystemTask's   status                follower\r
257               +------+ +-----------------------------------------+\r
258               | wake | | absolute address of SystemTask's status |\r
259               +------+ +-----------------------------------------+\r
260 </PRE>\r
261 \r
262 <P>If <CODE>FooTask</CODE> is added, <CODE>status</CODE> and\r
263 <CODE>follwer</CODE> of the two tasks now hold:</P>\r
264 \r
265 <PRE>\r
266 SystemTask's   status                follower\r
267               +------+ +-----------------------------------------+\r
268               | wake | | absolute address of FooTask's status    |\r
269               +------+ +-----------------------------------------+\r
270 \r
271    FooTask's   status                follower\r
272               +------+ +-----------------------------------------+\r
273               | wake | | absolute address of SystemTask's status |\r
274               +------+ +-----------------------------------------+\r
275 </PRE>\r
276 \r
277 <P>Effectively current task's <CODE>PAUSE</CODE> jumps to next task's\r
278 <CODE>wake</CODE>. At this point user variables and stacks are not\r
279 switched yet. <CODE>wake</CODE> assigns the return stack item (the next\r
280 address of <CODE>status</CODE>, i.e. the address of\r
281 <CODE>follower</CODE>) into global variable <CODE>userP</CODE>, which is\r
282 used to calculate absolute address of user variables.  All user variables\r
283 cluster in front of <CODE>follower</CODE>. Now user variables are\r
284 switched. Then <CODE>wake</CODE> restores data stack pointer stored in\r
285 user variable <CODE>stackTop</CODE> (now data stack is switched) and\r
286 restores return stack pointer saved on top of data stack (now return\r
287 stack is switched). <CODE>wake</CODE> is defined as:</P>\r
288 \r
289 <PRE><CODE>    : wake   R&gt; userP !  stackTop @ sp!  rp! ; COMPILE-ONLY\r
290 </CODE></PRE>\r
291 \r
292 <P>What is clever here is that one item on return stack, left by\r
293 <CODE>PAUSE</CODE> and consumed by <CODE>wake</CODE>, is used to transfer\r
294 control as well as information for context switching. This multitasker is\r
295 highly portable. Not a line of multitasker code was touched when hForth\r
296 8086 RAM model was moved to Z80 processor. This is also verified by Neal\r
297 Crook when porting hForth to ARM processor. I believe that it should be\r
298 possible to port this multitasker to subroutine-threaded or native-code\r
299 Forth by redefining them in machine codes.</P>\r
300 \r
301 <P>I used this multitasker to update graphics screen and make cursor\r
302 blink in <I>HIOMULTI.F</I>. Console output is redirected to graphics\r
303 screen to display Korean and English characters for VGA and Hercules\r
304 Graphics Adapters. <CODE>EMIT</CODE> fills characters into a buffer and a\r
305 background task displays them on graphics screen when hForth is waiting\r
306 for keyboard input. Scrolling text on graphics screen is as fast as on\r
307 text screen. I also used the multitasker for serial communication in\r
308 <I>SIO.F</I>. Main routine fetches characters from input buffer and\r
309 stores characters in output buffer while background task does actual\r
310 hardware control.</P>\r
311 \r
312 <H2>Jump table interpreter</H2>\r
313 \r
314 <P>I applied all the best ideas and tricks I know to hForth. Most of them\r
315 came from other people while I added a few of my own. I believe that some\r
316 of them are worth to mention.</P>\r
317 \r
318 <P>hForth text interpreter uses vector table to determine what to do with\r
319 a parsed strings after search it in the Forth dictionary. Dictionary\r
320 search results the string and 0 (for an unknown word); xt and -1 (for\r
321 non-immediate word); or xt and 1 (for immediate word) on data stack.\r
322 hForth text interpreter chooses next action by the following code:</P>\r
323 \r
324 <PRE><CODE>    1+ 2* STATE @ 1+ + CELLS 'doWord + @ EXECUTE\r
325 </CODE></PRE>\r
326 \r
327 <P><CODE>'doWord</CODE> table consists of six vectors.</P>\r
328 \r
329 <PRE>\r
330                                compilation state   interpretation state\r
331                                (STATE returns -1)   (STATE returns 0)\r
332                                ------------------  --------------------\r
333 non-immediate word (TOS = -1)     optiCOMPILE,         EXECUTE\r
334 unknown word       (TOS =  0)      doubleAlso,        doubleAlso\r
335 immediate word     (TOS =  1)       EXECUTE            EXECUTE\r
336 \r
337 TOS = top-of-stack\r
338 </PRE>\r
339 \r
340 <P>The behavior of the hForth text interpreter can be interactively\r
341 changed by replacing these vectors. For example, one can make hForth\r
342 interpreter accept only single-cell numbers by replacing\r
343 <CODE>doubleAlso,</CODE> and <CODE>doubleAlso</CODE> with\r
344 <CODE>singleOnly,</CODE> and <CODE>singleOnly</CODE> respectively.\r
345 <CODE>optiCOMPILE,</CODE> does the same thing as Standard word\r
346 <CODE>COMPILE,</CODE> except that it removes one level of\r
347 <CODE>EXIT</CODE> if possible. <CODE>optiCOMPILE, </CODE> does not\r
348 compile null definition <CODE>CHARS</CODE> into the current definition.\r
349 Also it compiles <CODE>2*</CODE> instead of <CODE>CELLS</CODE> if\r
350 <CODE>CELLS</CODE> is defined as "<CODE>: CELLS 2* ;</CODE>".</P>\r
351 \r
352 <H2>Special compilation action for default compilation semantics</H2>\r
353 \r
354 <P>Compiling words created by <CODE>CONSTANT</CODE>,\r
355 <CODE>VARIABLE</CODE>, and <CODE>CREATE</CODE> as literal values can\r
356 increase execution speed, especially for native-code Forth compilers. A\r
357 solution is implemented in hForth EXE model to provide special\r
358 compilation action for default compilation semantics. Words created by\r
359 <CODE>CONSTANT</CODE>, <CODE>VARIABLE</CODE>, and <CODE>CREATE</CODE>\r
360 have a special mark and xt for special compilation action. hForth\r
361 compiler executes the xt if it sees the mark. (<CODE>POSTPONE</CODE> must\r
362 find this special compilation action also and compile it.) A new data\r
363 structure with special compilation action can be built by\r
364 <CODE>CREATE</CODE> and only two non-Standard words:\r
365 implementation-dependent <CODE>doCompiles&gt;</CODE> and\r
366 implementation-independent <CODE>compiles&gt;</CODE>.\r
367 <CODE>doCompiles&gt;</CODE> verifies whether the last definition is ready\r
368 for special compilation action and takes an xt on data stack and assign\r
369 it as special compilation action of the last definition.\r
370 <CODE>compiles&gt;</CODE> is defined as:</P>\r
371 \r
372 <PRE><CODE>    : compiles&gt;  ( xt -- )\r
373         POSTPONE LITERAL POSTPONE doCompiles&gt; ; IMMEDIATE\r
374 </CODE></PRE>\r
375 \r
376 <P>For example, <CODE>2CONSTANT</CODE> can be defined as:</P>\r
377 \r
378 <PRE><CODE>    :NONAME   EXECUTE POSTPONE 2LITERAL ;\r
379     : 2CONSTANT\r
380         CREATE SWAP , , compiles&gt; DOES&gt; DUP @ SWAP CELL+ @ ;\r
381 </CODE></PRE>\r
382 \r
383 </CODE><P>It is the user's responsibility to match special compilation\r
384 action with the default compilation semantics. I believe that this\r
385 solution is general enough to be applied to other Forth systems.</P>\r
386 \r
387 <H2>Turtle Graphics</H2>\r
388 \r
389 I implemented LOGO's Turtle Graphics in hForth. The turtle moves on VGA\r
390 or Hercules graphics screen and follows postfix Forth command '<CODE>100\r
391 FORWARD</CODE>' instead of prefix LOGO command '<CODE>FORWARD\r
392 100</CODE>'. No floating-point math is used at all. Integers are used\r
393 represent angles in degree rather than in radian and look-up table is\r
394 used to evaluate trigonometric functions. Only a few words are defined in\r
395 machine code for line drawing and trigonometric function evaluation. The\r
396 turtle moves swiftly on a 286 machine. The Forth source and MS-DOS\r
397 executables, <I>TURTLE.F</I>, <I>ETURTLE.EXE</I> (using English commands)\r
398 and <I>HTURTLE.EXE </I>(using Korean commands), are included.</P>\r
399 \r
400 <H2>Summary</H2>\r
401 \r
402 <P>hForth is a small ANS Forth system based on eForth. It is especially\r
403 designed for small embedded system. The basic ROM and RAM models are\r
404 designed for portability, however, can be easily optimized for a specific\r
405 CPU to build a competitive system as shown in 8086 EXE model. hForth\r
406 packages for 8086 and Z80 can be found at \r
407 <A HREF="http://www.taygeta.com/forthcomp.html">\r
408 http://www.taygeta.com/forthcomp.html</A> or \r
409 <A HREF="ftp://ftp.taygeta.com/pub/Forth/Reviewed/">\r
410 ftp://ftp.taygeta.com/pub/Forth/Reviewed/</A>. hForth is also ported to\r
411 H8 processor by Mr. Bernie Mentink and to ARM processor by Neal Crook.\r
412 I hope that hForth will be useful to many people.</P>\r
413 \r
414 </BODY>\r
415 </HTML>\r