The Forth Dimension.
Heater.
Posts: 21,230
I recently got my knuckles rapped on the forum for criticizing the Forth language and/or it's implementations without having actually tried it. At least not in a few decades. I have to admit my knuckle wrapping was deserved. Given my respect for my peers here and the fact that they are right I decided to have a little look at Forth. Given that I have been tweaking with my FFT again recently I decided to kick off with trying to get some parts of that working in Forth, it seems like a good learning exercise as the FFT contains a good mix of typical arithmetic/logical ops, bit tweaking, conditionals, loops etc found in typical MCU programming.
So here is my first step into the Forth Dimension (cue the Twilight Zone music). Its a routine to reverse the low order bits of an integer.
"Ah", you say, "Why have you written it out in so many short lines?" Well, this looks like such low level stuff to me a feel better writing out like you would ops in assembler, one by one.
Any comments welcome. Will this actually run on all the Propeller Forths we have?
Next up I need to figure out how to use arrays in Forth any suggestions?
So here is my first step into the Forth Dimension (cue the Twilight Zone music). Its a routine to reverse the low order bits of an integer.
\ Reverse L low order bits of integer I
: bitreverse ( L I -- RI )
swap
dup
$aaaaaaaa and
1 rshift
swap
$55555555 and
1 lshift
or
dup
$cccccccc and
2 rshift
swap
$33333333 and
2 lshift
or
dup
$f0f0f0f0 and
4 rshift
swap
$0f0f0f0f and
4 lshift
or
dup
$ff00ff00 and
8 rshift
swap
$00ff00ff and
8 lshift
or
dup
16 rshift
swap
16 lshift
or
swap
negate
32 +
rshift
;
.( Bit reversal) cr
130 dup .( Initial = ) . cr
8 bitreverse dup .( Reversed = ) . cr
8 bitreverse dup .( And again = ) . cr
bye
"Ah", you say, "There is a PASM instruction to do that in the Propeller". Quite so but that would not be Forth would it. As far as I can tell there is no bit reverse operator in any standard Forth , especially not in the gforth I have been playing with on my PC. I have no Propellers here to try out a Propeller Forth."Ah", you say, "Why have you written it out in so many short lines?" Well, this looks like such low level stuff to me a feel better writing out like you would ops in assembler, one by one.
Any comments welcome. Will this actually run on all the Propeller Forths we have?
Next up I need to figure out how to use arrays in Forth any suggestions?
Comments
\ converted to propforth \ fl ( -- ) buffer the input and route to a free cog fl decimal \ Reverse L low order bits of integer I : bitreverse \ ( L I -- RI ) swap dup hAAAAAAAA and d1 rshift swap h55555555 and d1 lshift or dup hCCCCCCCC and d2 rshift swap h33333333 and d2 lshift or dup hF0F0F0F0 and d4 rshift swap h0F0F0F0F and d4 lshift or dup hFF00FF00 and d8 rshift swap h00FF00FF and d8 lshift or dup d16 rshift swap d16 lshift or swap negate d32 + rshift ; \ test ( -- ) : test c" Bit reversal" .cstr cr d130 dup c" Initial = " .cstr . cr d8 bitreverse dup c" Reversed = " .cstr . cr d8 bitreverse dup c" And again = " .cstr . cr drop ; testor do it this way\ propforth version \ fl ( -- ) buffer the input and route to a free cog fl \ Reverse L low order bits of integer I \ ( L I -- RI ) : bitreverse \ rev ( n1 n2 -- n3 ) n3 is n1 with the lower 32-n2 bits reversed and the upper bite cleared rev \ <------ I assume it uses the spin function only forthisly ; decimal \ test ( -- ) : test c" Bit reversal" .cstr cr d130 dup c" Initial = " .cstr . cr d8 d32 swap - bitreverse dup c" Reversed = " .cstr . cr d8 d32 swap - bitreverse dup c" And again = " .cstr . cr drop ; testDuane J
That's not very encouraging as I though I had used the simplest most common Forth possible.
What's with all the "h0F0F0F0F" and "d8" stuff? Doesn't that lead to conflicts between numbers and words?
I take it "rev" is a special Prop word.
The b, lowercase, forces it to be binary.
The d, lowercase, forces it to be decimal.
The h, lowercase, forces it to be hexadecimal, and the rest must be uppercase.
Actually any alpha character in arbitrary number bases must be upper case, there is just no defining character for them. ( Unless you define one.)
I find it good practice, for me anyway, to make numbers unambiguous.
[/QUOTE]I take it "rev" is a special Prop word.[/QUOTE]
I assume so, at least in PropForth, since the hardware has it. There's really no need for the reverse command which would be slower.
Actually you could have the word if you need it I hope that's right %^)
Others are much better at the fine details than me.
Duane J
Propforth supports arbitrary number base, we prefix with lower case d, h, b for decimal, hex and binary (I didn't know we had binary, please verify),
and ALSO we can prefix with lowercase z to use radix 64.
[The choice of d, h, and b are my fault; I convinced Sal these are more intuitive to new users than %, $, # and whatever, as those are never consistent across languages. Sorry for the inconvenience]
RADIX 64 is handy for text encoding long strings of assembler. SO it actually WOULD be forth to optimize your routine in assembler, and propforth has an easy way to to this. Although I've not done it, Sal, Caskaz, Brian and Nick are the ones to ask. AND Nick is the Fast Hartley guy, it not cheating to cheat of of him. Anything is fine as long as we get an FFT that passes the heater test.
There are other cool things with assembler in propforth but I have not mastered them and therefore have not documented them yet. But, if you get to the point you want to use it, we can focus on that part of the docs for you. But first you should "get it working in forth" before you "get it fast with assembler", as this is the recommended development path.
For debugging my code I have added my own extensions: One of the most useful set of words are the .sx family of stack display words.
Extremely useful for decoding complicated stack manipulations. the .s words non-destructivly display the stack.
Once it works just remove them.
Cool huh!!
Duane
Duane J
I'm really not into optimizing this with some weird Forth assembler. The idea here is for me to learn some Forth. I already have a PASM version of the FFT all be it called from Spin. In C the propgcc compiler compiles it into COG code that runs nearly as fast. Anyway someone has already done that optimization in a Forth version of fft_bench. Sorry I forget who now. If anyone want's to point out that my Forth is crappy and can be optimized that would be great.
The fact that I have kicked off with FFT code is not of any consequence. It's just an exercise for this beginner and could have been anything. However we do have the FFT in a bunch of languages now so at the end of the exercise I can look back at them all and see which one I feel most comfortable with.
What is the "heater test"?
Next up I want to tackle the integer square root function. For that I really have the urge to use local variables. Do the various Propeller Forths support local variables as in {a b c} ?
Thanks.
Does Prop Forth accept decimal numbers without the d ?
if so I'm quite willing to change all the hex literals to decimal as it wold make the code more portable.
I just like to formally set the number type so I don't make mistakes.
Technically, the internal number system is usually 32 bit binary, sometimes 16 bit or 8bit.
The base is really meant as a convention for human input and output.
It doesn't cost any time to formally set the number to decimal, hex, or anything else as they are converted to binary at compile time anyway,(when words are entered into the dictionary).
Note, once the word is entered the base can be changed at will and there will be no effect on the entered word.
You can still sprinkle numbers of different basses by changing the base before the number is entered.
This can be done 2 ways:
1. use the hex , or decimal , or binary word.
2. or formally store the radix in the base variable.
These general words are in all forths I know about.
Duane J
At some point I also plan on adding a COGX2 word, which will allow me to execute Prop-specific instructions such as REV. pfth already has a COGX1 word that allows it to execute the Prop's hubops.
Arrays can be implemented in Forth using CREATE and DOES>. "Starting Forth" contains the following example of an array definition:
: ARRAY ( #rows #cols -- ) CREATE DUP , * ALLOT DOES> ( member: row col -- addr ) ROT OVER @ * + + CELL+ ;A 4x5 array can then be create by typing "4 5 array x". The array element of x at (2, 3) can then be read by typing "2 3 x c@". The magic is performed by the DOES> word. Basically, the words between CREATE and DOES> will create the variable "x", store the number of columns in the first cell and allocate 2*3 = 6 bytes for the array. The words between DOES> and ; will be executed whenever x is accessed. It computes the appropriate offset for the specified row and col, and adds it to the address of the first cell of x.Check out "Starting Forth" and "A Beginners Guide to Forth" for more information on what DOES> does.
BTW, why can't you just add a REV word to the kernel as Tachyon does:
[B][COLOR=#000000][FONT=Ubuntu Mono] [FONT=courier new] ' REV ( n1 bits -- n2 ) Reverse LSBs of n1 and zero-extend[/FONT][/FONT][/COLOR][FONT=courier new] [COLOR=#FFFFFF][B]_REV[/B][/COLOR][COLOR=#000000] rev tos+1,tos[/COLOR] [COLOR=#000000] jmp #DROP[/COLOR] [/FONT][/B]What Duane said with this addition:
Propforth buffers an incoming datastream for example via the word by running a separate interpreter in another cog. This means your development cog (cog6) is free to continue doing work while the text is being interpreted (some steps of the compilation and dictionary insert do take noticeable effort and therefore time).
Each cog can have a different base, which we can set on the fly. This is very powerful and useful, but we found it gets to be a pain in the brain to manage this manually, and so it is easier to explicitly state the base in the code. It actually makes things MUCH clearer and cleaner, although it is different from what we've grown accustomed to struggling with. Please give explicit base declaration for number literals a change, although once you see its usefulness you may be forever tainted and not tolerant of its absence in other environments.
Also, don't worry about portability, it not like C where its a big deal. These are mostly small programs that you or we are personally intimate with, and well written code is a snap to port or return to. (If your code is NOT easy to understand when you come back to it, it is a sign of weak programming technique. This goes away after a short while).
Propforth is tailored to the prop architecture, Tachyon is tailored for speed and minimal size, and pfth is tailed for ANSII compatibility.
I can't believe I'm having such a rough start over such a simple thing. Is there one way to specify hexadecimal literals that works in all Propeller Forths? Or should I switch bases with "hexadecimal" and "decimal" as and when required? Or should I just do everything in decimal ?
Braino, I am exactly going to worry about portability.
As I said whatever I do has to work under gforth as that will be my playground when I don't have any Propellers around. There is nothing in the FFT that requires any specific Propeller features. It's only calculating a lot of stuff after all. At least not until you want to get into speeding it up. Besides there may be other Forths on other MCUs I want to play on. It has to work on as many Propeller Forths as possible. I totally agree. Especially as the FFT itself, in this case, is hard enough to understand when spelled out in the most simple way. That's also why I don't want any non-standard, non-portable constructs in there. Anything specific to a Forth implementation is an extra little complication to have to remember.
I have been flicking back and forth between Brodie's book of which I have fond memories from the 1980's and the gforth tutorials which seems to be lacking in some areas. I consider the fft_bench to be a complete project, it's not exactly trivial, it works, it has know results, it just needs doing in Forth. That is my chosen exercise and it has many interesting little sub-exercises.
Please, please, does any Prop Forth support local variables?
Actually I guess according to my portability criteria if even one Prop Forth does not support local variables then I won't use them.
BTW, Doug and Peter, you haven't answered Heater's question about implementing arrays. How do you implement arrays in PropForth and Tachyon?
I also would appreciate the lowest common denominator way to set use arrays and look up tables.
Forth doesn't normally handle number base prefix or suffix but it can be added on if the Forth supports a fall-through when a word cannot be found nor converted to a number. Even though I have all the special processing built in there is still a vector called "unum"
unum res 2 ' User number processing routine - executed if number failed and UNUM <> 0
and
unknown byte REG,unum,WFETCH,QDUP,_IF,03,ACALL,_AGAIN,@un01-@chkeol
I have always preferred having a $ sign for hex numbers or alternatively the "h" for a suffix. This has been standard on so many assemblers that I have worked with but I have never liked the 0x prefix that somehow crept into C.
Well, I aim to have them fully implemented but at present I have this:
[/FONT][/COLOR]So 4 LOCAL will grab 4 parameters from the stack and store them in a local variables stack. X1 X2 X3 X4 implicitly fetch those variables with minimal overhead. I do not try to create local results though, I just work the stack as usual but all the headache stuff is taken care of. Eventually the symbol names enclosed in the stack comment will be used instead and so the LOCAL and RELEASE operator will not be required either.
Hmm..I did not understand any of that. None of it looks like "book forth". What is with the pri and pub?
Are you saying that the stuff in comments will start to have meaning to the compiler?!!
Sounds like locals are off the table as I it looks like there is not going to be any common ground here.
As far as arrays are concerned, I think you will have to break the ARRAY definition that I presented earlier into two words. The first word creates the array, and contains the code before DOES>. The second word would be use to get the address of an element in the array, and contains the code after DOES>.
Dave's right on with both these comments.
Any Forth practitioner will frown on local variables and say you need to refactor your words if the stack becomes unmanageable. Any word should keep stack elements down to a small set that can be kept straight in the authors brain.
I think is pfth is the only implementation with the DOES> word which mean it is the only one that can have an ARRAY word that does one thing at compile time and another at implementation time. Others will need an array creation word and an array accessor word.
Factor, a Forth derivative for PCs can use the stack effects documentation, ( x y -- z) for creation of local variables if you want, much like Peter intends for Tachyon.
Chuck Moore, Chuck was clearly insane.
OK, undeterred, local variables are out and we boldly go forth where no man has gone forth before...
As far as I can tell I don't need a DOES> word to get my arrays going. Which is nice as I have no idea what DOES> does.
No way, I want lowest common denominator constructs for this exercise. Factor is not even Forth any more.
I'm kind of thinking it would be an idea to tweak my version of a TINY compiler to emit Forth source code instead of x86 or Propeller instructions and then cast the FFT in TINY and generate Forth from it. Might be quicker than writing Forth by hand:)
PropTiny was the result of my working through Jack Crenshaw's "Let's build a Compiler" articles years ago. I did my versions of Jack's Pascal experiments in C and ended up generating x86 assembler output. I revived it to generate Prop LMM code some years later. It's not at all efficient, no optimization, I was just so amazed that I had managed to build a compiler at all, a task that had fascinated me for a long time before and which I never understood from picking up books on the subject.
I don't even remember what features I put in it now, variables, statements, expressions, conditionals, loops, signed and unsigned bytes words and longs, global and local variables. No arrays, structures or strings. Block structured like Pascal or C. Half way from Jacks TINY language to the bigger KISS.
I keep wanting to revisit it but there is never enough time. I suspect today it is now possible to build PropTiny with propgcc and actually have a C like compiler running on the Prop itself! That idea could spur me into action again. (needs a PASM assembler that runs on the Prop though)
PropTiny is here: http://forums.parallax.com/showthread.php?113228-PropTiny-Jack-Crenshaw-s-TINY-language-for-the-Prop
Turns out my LMM generation is not so hot, I didn't do jumps the proper way.
Ok guys. Define what you mean by portability.
Do you write assembler on one hardware, (x86) and expect it to be directly portable to another hardware (68k)? No
Are you going to write code on the prop, and expect it to be directly portable on an ATEMGA? In ANY language? No.
Are you going to write a BASIC program for the prop, and expect it to be directly portable to another BASIC on the prop? No. There will all ways be at least something different.
IF you write in FORTH, is any one going to require you to run you program on all three current incarnation of forth with no changes. Possibly, but its still kind of silly.
Please look at the ANSII terminal control support for propforth.
http://propforth.googlecode.com/files/ANSI%20Escape%20Sequences20120704-1652.f
This should pretty much run on ANY forth, as I developed it on the PC and ported it to propforth. Some stuff is different, but its the same for the most part. The things that make it different on the prop or the PC are so small that you don't even notice them. The effort is similar to when you notice spell "the" as "teh". You fix it and move on.
So you have to change 1B to h1B. Or change h1B to $1B. How much is that going to kill you? Sheesh!
Ok this numeric litteral thing is tough on your established habits, sorry about that. It is my fault.