Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #35703 > unrolled thread

Packed strings in Forth ... any thoughts, advice, or links to prior art?

Back to article view | Back to comp.lang.forth

Contents

  Packed strings in Forth ... any thoughts, advice, or links to prior art? Michael Barry <barrym95838@yahoo.com> - 2015-01-11 00:42 -0800
    Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? stephen@mpeforth.com (Stephen Pelc) - 2015-01-11 12:03 +0000
    Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-01-11 12:02 +0000
      Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Michael Barry <barrym95838@yahoo.com> - 2015-01-11 11:29 -0800
        Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Bernd Paysan <bernd.paysan@gmx.de> - 2015-01-11 22:24 +0100
          Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-01-12 10:10 +0000
        Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-01-12 10:12 +0000
        Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-01-12 11:17 +0000
          Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Michael Barry <barrym95838@yahoo.com> - 2015-01-12 19:13 -0800
    Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? hughaguilar96@gmail.com - 2015-01-11 14:38 -0800
      Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Michael Barry <barrym95838@yahoo.com> - 2015-01-11 17:09 -0800
        Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? "Elizabeth D. Rather" <erather@forth.com> - 2015-01-11 17:18 -1000
          Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Michael Barry <barrym95838@yahoo.com> - 2015-01-11 19:48 -0800
        Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? hughaguilar96@gmail.com - 2015-01-12 17:59 -0800
          Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Michael Barry <barrym95838@yahoo.com> - 2015-01-12 19:04 -0800
            Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? hughaguilar96@gmail.com - 2015-01-12 19:52 -0800
              Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Michael Barry <barrym95838@yahoo.com> - 2015-01-12 20:28 -0800
                Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? hughaguilar96@gmail.com - 2015-01-13 19:42 -0800
              Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Alexander Skobelev <al.skobelev@gmail.com> - 2015-01-13 08:38 +0300
                Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Alexander Skobelev <al.skobelev@gmail.com> - 2015-01-13 08:43 +0300
                Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? hughaguilar96@gmail.com - 2015-01-13 19:27 -0800
      Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? "Alex McDonald" <blog@rivadpm.com> - 2015-01-12 10:03 +0000
        Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? hughaguilar96@gmail.com - 2015-01-12 18:11 -0800
          Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? "Alex McDonald" <blog@rivadpm.com> - 2015-01-13 09:56 +0000
            Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Bernd Paysan <bernd.paysan@gmx.de> - 2015-01-14 03:07 +0100
              Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-01-14 11:27 +0000
                Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Bernd Paysan <bernd.paysan@gmx.de> - 2015-01-15 18:09 +0100
      Re: Packed strings in Forth ... any thoughts, advice, or links to prior art? Ilya Tarasov <ilya74.tarasov@gmail.com> - 2015-01-15 06:42 -0800

Page 1 of 2  [1] 2  Next page →

#35703 — Packed strings in Forth ... any thoughts, advice, or links to prior art?

Hello, all.

I'm not sure if this is the proper place to ask about this question
 that has been bothering me for several months of my limited spare
 time, but I figure that I might as well pull the trigger ... here
 goes ...

I have a hypothetical machine that doesn't address bytes, only 32-
 bit words.  Chars, cells, addresses, single-precision integers and
 single-precision floats are all 32-bits wide.  In a world where
 UTF-32 was the standard way to encode a character, this would be
 perfect, and is how my default method of handling strings in Forth
 would work.

I don't like the idea of excluding a more efficient way of handling
 UTF-16 and UTF-8 strings by packing two or four chars in each word,
 but there are some questions I have about how much complexity this
 would add to an otherwise very simple and clean design.

My first idea is to have two attribute bits in the highest-order
 end of the count cell at the beginning of the string.  Zeros there
 would indicate that the following string is UTF-32, limiting it
 to a length of about 10^9 chars.  Other two-bit values could
 indicate alternate encodings.  Exactly how the remaining 30 bits
 in the count cell would do this is where I need some help.

I don't have sufficient knowledge of the advanced features of Forth
 to know whether or not it is feasible to have all the words that
 create, move, compare, compile and manipulate strings be able to
 determine the encoding and act appropriately, since frequent
 packing and unpacking would be wasteful.  Are any of you aware
 of any implementations in the field that have already addressed
 this issue?  I could simply write two or three sets of words that
 handle each encoding, but I would prefer to make a single set of
 "smart" words that can figure out what needs to be done on the
 fly.  This might even include an ability for a word like S= to
 compare a packed string with the least-significant bits of the
 chars in an unpacked string.  Another thing that crossed my mind
 would be the ability for the count cell to contain information
 about where (in the first char cell) the string actually began,
 to avoid the necessity of long series of bit-shifts to add or
 remove single chars at the logical beginning of the packed string.
 Am I opening a huge can of worms with regards to being able
 to address a string that doesn't start or end on a cell
 boundary?

I realize that bit-field manipulations would likely be much more
 efficient as primitives, and I have had great fun so far in
 writing primitives, but I would like to avoid as many false
 starts as possible, since I'm hand-assembling everything at this
 point.  I have a lot to learn about the many ways that Forth
 uses strings, and I would appreciate any advice you could give.
 Am I likely biting off more than I can chew?  I won't be deeply
 offended if the consensus winds up being "Yes", just a bit
 disappointed.

Thanks in advance,

Mike

[toc] | [next] | [standalone]

#35710

On Sun, 11 Jan 2015 00:42:35 -0800 (PST), Michael Barry
<barrym95838@yahoo.com> wrote:

>I have a hypothetical machine that doesn't address bytes, only 32-
> bit words.  Chars, cells, addresses, single-precision integers and
> single-precision floats are all 32-bits wide.  In a world where
> UTF-32 was the standard way to encode a character, this would be
> perfect, and is how my default method of handling strings in Forth
> would work.
>
>I don't like the idea of excluding a more efficient way of handling
> UTF-16 and UTF-8 strings by packing two or four chars in each word,
> but there are some questions I have about how much complexity this
> would add to an otherwise very simple and clean design.

The simple solution is to have an area of memory that is only 8 bits
wide rather than 32 bits. In this environment (maybe accessed by the
words C@ and C!) there is no physical memory wasted.

Stephen

-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[toc] | [prev] | [next] | [standalone]

#35711

Michael Barry <barrym95838@yahoo.com> writes:
>I have a hypothetical machine that doesn't address bytes, only 32-
> bit words.  Chars, cells, addresses, single-precision integers and
> single-precision floats are all 32-bits wide.  In a world where
> UTF-32 was the standard way to encode a character, this would be
> perfect, and is how my default method of handling strings in Forth
> would work.
>
>I don't like the idea of excluding a more efficient way of handling
> UTF-16 and UTF-8 strings by packing two or four chars in each word,
> but there are some questions I have about how much complexity this
> would add to an otherwise very simple and clean design.

The main question is: If you want to handle so much string data that
32-bit chars are too inefficient, why do you choose a cell-addressed
machine?  Otherwise using 32-bit chars is the way to go IMO.

If you really want to put more than one char in an address unit, I
think the way to go is to look at what operations you want to do with
the strings, and have special words for doing these operations with
your special string representation.

>My first idea is to have two attribute bits in the highest-order
> end of the count cell at the beginning of the string.  Zeros there
> would indicate that the following string is UTF-32, limiting it
> to a length of about 10^9 chars.  Other two-bit values could
> indicate alternate encodings.  Exactly how the remaining 30 bits
> in the count cell would do this is where I need some help.
>
>I don't have sufficient knowledge of the advanced features of Forth
> to know whether or not it is feasible to have all the words that
> create, move, compare, compile and manipulate strings be able to
> determine the encoding and act appropriately, since frequent
> packing and unpacking would be wasteful.

For normal Forth strings represented by (addr u) even simple address
and length arithmetics like

( addr1 u1 ) swap char+ swap 2 - ( addr2 u2 )

has to work, and that would not work with your representation.  Even
for counted strings, you can convert them to addr u strings with

dup c@ swap char+

and cannot work with your representation, either.

Many people are not satisfied by the string handling provided in the
standard, and have developed string packages.  Some (probably
especially the ones having a string stack) might have an interface
that is abstract enough that it can be used with your representation.
I have not looked closely enough at them to point you to a particular
one.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2014: http://www.euroforth.org/ef14/

[toc] | [prev] | [next] | [standalone]

#35718

On Sunday, January 11, 2015 at 4:19:13 AM UTC-8, Anton Ertl wrote:
> 
> If you really want to put more than one char in an address unit,
> I think the way to go is to look at what operations you want to
> do with the strings, and have special words for doing these
> operations with your special string representation.
> 
I respect your opinion, and will attempt to do just that.

The main reason for packed strings thus far is to reduce the size
 of my dictionary headers.  I think that I will write a FIND that
 packs the search string onto the return stack (or into PAD or ,
 perhaps?), then compares it to the packed name fields in the
 headers before discarding it (or abandoning it), as applicable.
 Do you see any likely problems with any of those three temporary
 destinations?

I know that there are several words that call FIND, but I haven't
 studied them in detail yet.  If I want to add a word to my
 dictionary, I suppose that a PACK32>8 word would come in handy for
 that as well, so I'll write one that can be called by FIND and
 any other word(s) that may find it useful.

Thanks for the help, Stephen and Anton.

Mike

[toc] | [prev] | [next] | [standalone]

#35722

Michael Barry wrote:
> The main reason for packed strings thus far is to reduce the size
>  of my dictionary headers.  I think that I will write a FIND that
>  packs the search string onto the return stack (or into PAD or ,
>  perhaps?), then compares it to the packed name fields in the
>  headers before discarding it (or abandoning it), as applicable.
>  Do you see any likely problems with any of those three temporary
>  destinations?

The only part where a dictionary entry is represented as standard string is 
with the output of NAME>STRING (part of the TRAVERSE-WORDLIST proposal).  
You can probably use a temporary buffer for that output, though it is not 
specified as one.  You probably don't implement TRAVERSE-WORDLIST anyhow.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*

[toc] | [prev] | [next] | [standalone]

#35743

Bernd Paysan <bernd.paysan@gmx.de> writes:
>The only part where a dictionary entry is represented as standard string is 
>with the output of NAME>STRING (part of the TRAVERSE-WORDLIST proposal).  
>You can probably use a temporary buffer for that output, though it is not 
>specified as one.

In the standard it is:

|15.6.2.1909.40 NAME>STRING "name-to-string" TOOLS EXT
|                 ( nt ­ ­ c-addr u )
|
|NAME>STRING returns the name of the word nt in the character string
|c-addr u. The case of the characters in the string is
|implementation-dependent. The buffer containing c-addr u may be
|transient and valid until the next invocation of NAME>STRING. A
|program shall not write into the buffer containing the resulting
|string.
|
|See: 15.6.2.2297 TRAVERSE-WORDLIST.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2014: http://www.euroforth.org/ef14/

[toc] | [prev] | [next] | [standalone]

#35745

Michael Barry <barrym95838@yahoo.com> writes:
>The main reason for packed strings thus far is to reduce the size
> of my dictionary headers.

That saves maybe 30 bytes per dictionary entry (with relatively long
10-character names on average), and if you have 5000 dictionary
entries, it saves a total of 150KB.  That's probably not worth any
special effort at being compact.

OTOH, you also only have very few operations: creating a dictionary
entry, comparing the name while searching, and (if you implement
NAME>STRING) extracting the name as string.  So the effort required
would not be that high, at least if you use an 8-bit encoding for the
characters.  If you want to support, say, Unicode in names, you have
to do the conversion from UTF-32 to UTF-8 (and back, for NAME>STRING),
but then you need that for WRITE-FILE (and READ-FILE) anyway.

>  I think that I will write a FIND that
> packs the search string onto the return stack (or into PAD or ,
> perhaps?), then compares it to the packed name fields in the
> headers before discarding it (or abandoning it), as applicable.
> Do you see any likely problems with any of those three temporary
> destinations?

PAD is reserved for application programmer usage, so don't use that
for system stuff.  The traditional place to put the buffer is HERE,
but that is normally WORD's doing, not FIND's.  I count only two
temporary destications in your description.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2014: http://www.euroforth.org/ef14/

[toc] | [prev] | [next] | [standalone]

#35748

In article <8aeb1d74-e4e7-42f8-9aed-bf120edaaeb1@googlegroups.com>,
Michael Barry  <barrym95838@yahoo.com> wrote:
>On Sunday, January 11, 2015 at 4:19:13 AM UTC-8, Anton Ertl wrote:
>>
>> If you really want to put more than one char in an address unit,
>> I think the way to go is to look at what operations you want to
>> do with the strings, and have special words for doing these
>> operations with your special string representation.
>>
>I respect your opinion, and will attempt to do just that.
>
>The main reason for packed strings thus far is to reduce the size
> of my dictionary headers.  I think that I will write a FIND that

Without further explanation this sounds pretty incredible in this
time and age. I "waste" about 1000 cells (8 Kbyte in ciforth 64 bits.)
in order to treat name strings as uniform compared to user strings.
I get in return: less trouble remembering them, applicability of
all string tools, no special words.
Almost all implementors would sacrifice 10 kbyte (for e.g. a hash
mechanism) for a 20% speed up in dictionary lookup.

>
>Mike

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#35762

On Monday, January 12, 2015 at 3:17:31 AM UTC-8, Albert van der Horst wrote:
> 
> Without further explanation this sounds pretty incredible in
> this time and age. I "waste" about 1000 cells (8 Kbyte in
> ciforth 64 bits.) in order to treat name strings as uniform
> compared to user strings. I get in return: less trouble
> remembering them, applicability of all string tools, no
> special words.
> Almost all implementors would sacrifice 10 kbyte (for e.g.
> a hash mechanism) for a 20% speed up in dictionary lookup.
> 

Well, Albert, you now know someone who is fighting the trend
 of bigger, bigger, bigger.  It irks me to waste space that
 could be used, even at the expense of speed ... it is very
 likely a lingering side-effect of my 8-bit days, when I
 spent way to much time shoe-horning code and data into
 systems with as little as 4 KB of RAM.  My processor is a
 tribute to those days, from which some of my fondest
 memories come.

Take care,

Mike

[toc] | [prev] | [next] | [standalone]

#35723

On Sunday, January 11, 2015 at 1:42:36 AM UTC-7, Michael Barry wrote:
> I have a hypothetical machine that doesn't address bytes, only 32-
>  bit words.  Chars, cells, addresses, single-precision integers and
>  single-precision floats are all 32-bits wide.  

As I recall, you said that you are designing a hypothetical processor that looks like a cross between the 6502 and 6809, but in 32-bit. If you are planning on eventually putting this in an FPGA, then that is not a good design. Forth code is highly factored, so it is imperative that you can call functions quickly, and also keep memory usage of the threaded-code to a minimum. In the MiniForth, the high bit of every xt indicated if it was a colon word or a primitive, so NEXT could do the right thing. Every call required only one cell of memory; this was as compared to the 6502 or 6809 where one byte is needed for the JSR opcode and the next cell (2 bytes) is the address (so the MiniForth used 2/3 the memory). NEXT got parallelized almost every time, so NEXT generally took zero clock cycles to execute --- EXIT took one clock cycle though, so a colon word wasn't entirely free. If you are designing a processor and intend Forth to be the primary language, you should focus on design issues related to Forth such as I've described above. Also, unless you know a hardware-design language and can design the processor yourself, speculating on possible designs is a waste of time --- believe me, any design you come up with will fall apart in the first week of putting it in hardware --- hardware design is not something that you plan out in detail ahead of time, but it is something that has to be figured out as you go (it is done "bottom up" rather than "top down").

I would really recommend that you just find an existing processor and go with it --- there is no market for Forth, so you still won't have your feet planted firmly in reality, but at least you will be in a low orbit around reality.

> I don't have sufficient knowledge of the advanced features of Forth
>  to know whether or not it is feasible to have all the words that
>  create, move, compare, compile and manipulate strings be able to
>  determine the encoding and act appropriately, since frequent
>  packing and unpacking would be wasteful.  

I can't think of any way to do it, except to unpack as needed. The MiniForth only addressed 16-bit words, and didn't address bytes, so this was similar to your contrived processor. I wrote primitives to pack and unpack, and they were pretty fast --- as a rule, primitives were a couple of orders of magnitude faster than equivalent colon words --- unfortunately, writing primitives in MiniForth assembly-language was a couple of orders of magnitude more difficult than writing the equivalent colon words.

One good thing, is that you can compare packed strings for equality without unpacking them --- you have to unpack to compare for greater or less than, though.

[toc] | [prev] | [next] | [standalone]

#35731

Thanks, Bernd.

On Sunday, January 11, 2015 at 2:38:48 PM UTC-8, hughag...@gmail.com wrote:
>
> As I recall, you said that you are designing a hypothetical
> processor that looks like a cross between the 6502 and 6809,
> but in 32-bit. If you are planning on eventually putting this
> in an FPGA, then that is not a good design.
>

You are probably correct, but I neglected to stress that the
 *assembly* language looks like a cross between 6502 and 6809,
 not the *machine* language.  There's enough room in my 32-bit
 opcodes to include a 17-bit signed "inherent" constant, which
 allows most complete instructions to fit into a single word.

>
> Forth code is highly factored, so it is imperative that you can
> call functions quickly, and also keep memory usage of the
> threaded-code to a minimum. In the MiniForth, the high bit of
> every xt indicated if it was a colon word or a primitive, so
> NEXT could do the right thing. Every call required only one
> cell of memory; this was as compared to the 6502 or 6809 where
> one byte is needed for the JSR opcode and the next cell (2
> bytes) is the address (so the MiniForth used 2/3 the memory).
> NEXT got parallelized almost every time, so NEXT generally
> took zero clock cycles to execute --- EXIT took one clock
> cycle though, so a colon word wasn't entirely free.
>

It sounds to me like you are describing an STC model, right?
 I have been looking around a bit, and come to the inescapable
 conclusion that ITC is very inefficient on my design, and
 I'm seriously considering switching over to DTC or STC.
 BTW, I believe that NEXT is always free in STC, on any
 "normal" microprocessor, because the program counter and
 the interpretive pointer are one and the same, right?

Here are a couple of examples:

First, ITC.  Y is IP, X is PSP, A is TOS, U is W, S is RSP:

                 ;   71 ;------------------------------------ EXECUTE
00000040:00000000;   72         NOT_IMM 'EXECUTE'
00000041:07455845;   72
00000042:43555445;   72
                 ;   73 _execute: ; ( xt -- ) Execute Forth word 'xt'
00000043:00000044;   74         PRIMITIVE
00000044:54000000;   75         ldu  #,a        ; Pop new W
00000045:42020000;   76         lda  ,x+        ;   from stack
00000046:5e0a0000;   77         jmp (,u+)       ; Execute from *(W++)
                 ;   78 ;---------------------------------------- lit
00000047:00000040;   79         NOT_IMM 'lit'
00000048:036c6974;   79
                 ;   80 _lit: ; ( -- x ) Push inline literal to stack
                 ;   81 ; This is the primitive compiled by LITERAL
00000049:0000004a;   82         PRIMITIVE
0000004a:52040000;   83         ldb  ,y+        ; b = *(IP++)
                 ;   84 pushb_:
0000004b:a3020000;   85         sta  ,-x        ; Make room on stack
                 ;   86 putb_:
0000004c:40080000;   87         lda  #,b        ; TOS = b
0000004d:5c060053;   88         jmp  donext_
                 ;   89 ;--------------------------------------- EXIT
0000004e:00000047;   90         NOT_IMM 'EXIT'
0000004f:04455849;   90
00000050:54000000;   90
                 ;   91 _exit: ; ( -- ) Exit a colon definition
00000051:00000052;   92         PRIMITIVE
00000052:4a0c0000;   93         ply             ; Pop IP from rstack
                 ;   94 donoop_:
                 ;   95 donext_:
00000053:56040000;   96         ldu  ,y+        ; W = *(IP++)
00000054:5e0a0000;   97         jmp  (,u+)      ; Execute from *(W++)
                 ;   98 ;------------------------------------ DOCOLON
                 ;   99 docolon_: ; ( internal )
                 ;  100 ; Enters a new high-level thread.
00000055:680a0000;  101         pdy  #,u        ; Push IP to rstack,
                 ;  102 ;                           point IP to PFA
00000056:5c060053;  102         jmp  donext_
                 ;  103 ;--------------------------------------------

Next, DTC.

                 ;  154 ;---------------------------------------- lit
00000040:00000000;  155         NOT_IMM 'lit'
00000041:036c6974;  155 
                 ;  156 ; This is the primitive compiled by LITERAL
                 ;  157 _lit: ; (  -- x ) \ Push inline literal
00000042:a3020000;  158         sta  ,-x        ; push
00000043:42040000;  159         lda  ,y+        ;   *(IP++) on pstack
00000044:5e040000;  160         jmp  (,y+)      ; NEXT
                 ;  161 ;------------------------------------ docolon
                 ;  162 docolon_: ; ( R:  -- a ) \ (internal)
00000045:6a0c0000;  163         pdy  ,s+        ; IP <-> rTOS
00000046:5e040000;  164         jmp  (,y+)      ; NEXT
                 ;  165 ;--------------------------------------------

I haven't checked STC out in detail yet, but it looks like I can
 just use single-word JSRs (as long as my dictionary doesn't
 grow larger than 64 KW), and two-word "extended-address" JSRs in
 the unlikely event that it does exceed 64 KW.  DOCOLON is JSR,
 EXIT is RTS, and NEXT is nothing at all in STC, right?

>
> If you are
> designing a processor and intend Forth to be the primary
> language, you should focus on design issues related to Forth
> such as I've described above.
>

Well, maybe not the primary language (I like assembly too darn
 much), but the first "high-level" language to be implemented.

>
> Also, unless you know a hardware- design language and can
> design the processor yourself, speculating on possible
> designs is a waste of time --- believe me, any design you
> come up with will fall apart in the first week of putting it
> in hardware --- hardware design is not something that you
> plan out in detail ahead of time, but it is something that
> has to be figured out as you go (it is done "bottom up"
> rather than "top down").
> 

I'm not sure that I understand your point, but I can agree
 that the odds are stacked heavily against me.  I'm writing
 lots of test-code before I finalize the machine instruction
 set to help me make decisions about what can be added or
 removed to make assembly programming as fun and efficient
 as possible (at least for me).

>
> I would really recommend that you just find an existing
> processor and go with it --- there is no market for Forth,
> so you still won't have your feet planted firmly in reality,
> but at least you will be in a low orbit around reality.
>

To hell with reality, I just want to have fun in my spare
 time, and I'm a nerd, so I do stuff like this instead of
 snowboarding or fishing or whatever the cool kids do.
 
Mike

[toc] | [prev] | [next] | [standalone]

#35734

On 1/11/15 3:09 PM, Michael Barry wrote:
...
> It sounds to me like you are describing an STC model, right?
>   I have been looking around a bit, and come to the inescapable
>   conclusion that ITC is very inefficient on my design, and
>   I'm seriously considering switching over to DTC or STC.
>   BTW, I believe that NEXT is always free in STC, on any
>   "normal" microprocessor, because the program counter and
>   the interpretive pointer are one and the same, right?
...
> I haven't checked STC out in detail yet, but it looks like I can
>   just use single-word JSRs (as long as my dictionary doesn't
>   grow larger than 64 KW), and two-word "extended-address" JSRs in
>   the unlikely event that it does exceed 64 KW.  DOCOLON is JSR,
>   EXIT is RTS, and NEXT is nothing at all in STC, right?
>
>>
>> If you are
>> designing a processor and intend Forth to be the primary
>> language, you should focus on design issues related to Forth
>> such as I've described above.
...

Many years ago we looked at various other models for implementing Forth 
on conventional processors. We were most attracted by STC, but 
discovered that although it was faster for colon definitions, data 
objects got a lot more complicated because they made good use of the I 
register (Interpreter pointer), and we decided it wasn't a good trade. 
When we added compiler optimization to the implementation mix, then of 
course the tradeoff changed dramatically.

>> I would really recommend that you just find an existing
>> processor and go with it --- there is no market for Forth,
>> so you still won't have your feet planted firmly in reality,
>> but at least you will be in a low orbit around reality.
>>
>
> To hell with reality, I just want to have fun in my spare
>   time, and I'm a nerd, so I do stuff like this instead of
>   snowboarding or fishing or whatever the cool kids do.

I trust you have Phil Koopman's book, Stack Computers: the New Wave 
http://users.ece.cmu.edu/~koopman/stack_computers? Not all that new 
anymore, but good on the hardware design issues. Available 
electronically in a variety of formats.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#35735

On Sunday, January 11, 2015 at 7:18:40 PM UTC-8, Elizabeth D. Rather wrote:
> 
> I trust you have Phil Koopman's book, Stack Computers: the New Wave 
> http://users.ece.cmu.edu/~koopman/stack_computers? Not all that new 
> anymore, but good on the hardware design issues. Available 
> electronically in a variety of formats.
> 
I have heard of his work, but never looked at it in detail.  I followed
 your link and downloaded a free copy for my hard-drive.  Thank you.

Mike

[toc] | [prev] | [next] | [standalone]

#35757

On Sunday, January 11, 2015 at 6:09:57 PM UTC-7, Michael Barry wrote:
> On Sunday, January 11, 2015 at 2:38:48 PM UTC-8, hughag...@gmail.com wrote:
> > Forth code is highly factored, so it is imperative that you can
> > call functions quickly, and also keep memory usage of the
> > threaded-code to a minimum. In the MiniForth, the high bit of
> > every xt indicated if it was a colon word or a primitive, so
> > NEXT could do the right thing. Every call required only one
> > cell of memory; this was as compared to the 6502 or 6809 where
> > one byte is needed for the JSR opcode and the next cell (2
> > bytes) is the address (so the MiniForth used 2/3 the memory).
> > NEXT got parallelized almost every time, so NEXT generally
> > took zero clock cycles to execute --- EXIT took one clock
> > cycle though, so a colon word wasn't entirely free.
> >
> 
> It sounds to me like you are describing an STC model, right?
>  I have been looking around a bit, and come to the inescapable
>  conclusion that ITC is very inefficient on my design, and
>  I'm seriously considering switching over to DTC or STC.
>  BTW, I believe that NEXT is always free in STC, on any
>  "normal" microprocessor, because the program counter and
>  the interpretive pointer are one and the same, right?

No, all processors have a JSR opcode (sometimes called CALL), and it takes some number of clock cycles, so it is not free --- the MiniForth is the only processor that I know of that does a call in zero clock cycles --- the MiniForth EXIT (called RTS in most processors) does take one clock cycle, so it is not free (but one clock cycle is not a lot).

Also, all processors that I know of require both a JSR opcode and one cell for the destination operand (on the 6502, that is 1+2=3 bytes total) --- the MiniForth is the only processor that I know of that has only the one cell for the destination operand but no memory used for the opcode (one bit of the address indicates if the address is for a primitive or a colon-word).

This is not STC --- this is DTC in hardware.

> I haven't checked STC out in detail yet, but it looks like I can
>  just use single-word JSRs (as long as my dictionary doesn't
>  grow larger than 64 KW), and two-word "extended-address" JSRs in
>  the unlikely event that it does exceed 64 KW.  DOCOLON is JSR,
>  EXIT is RTS, and NEXT is nothing at all in STC, right?

Nope, not right at all --- totally not getting it.

> > I would really recommend that you just find an existing
> > processor and go with it --- there is no market for Forth,
> > so you still won't have your feet planted firmly in reality,
> > but at least you will be in a low orbit around reality.
> >
> 
> To hell with reality, I just want to have fun in my spare
>  time, and I'm a nerd, so I do stuff like this instead of
>  snowboarding or fishing or whatever the cool kids do.

Why don't you learn how the MiniForth works, before tackling processor-design yourself? You know: stand on the shoulders of those who came before you. The MiniForth is 20-year-old technology (it is called the RACE now, and it has been upgraded to new hardware, but it is still pretty much the same, and it still uses MFX as the development system) --- but although it is from last century, it is beyond what you are conceiving now.

I snowboarded in those days, when I was writing MFX --- I haven't done so in many years though.

[toc] | [prev] | [next] | [standalone]

#35760

On Monday, January 12, 2015 at 5:59:16 PM UTC-8, hughag...@gmail.com wrote:
> 
> No, all processors have a JSR opcode (sometimes called CALL), and it
> takes some number of clock cycles, so it is not free --- the MiniForth
> is the only processor that I know of that does a call in zero clock
> cycles --- the MiniForth EXIT (called RTS in most processors) does take
> one clock cycle, so it is not free (but one clock cycle is not a lot).
> 
> ...
>
> Also, all processors that I know of require both a JSR opcode and one
> cell for the destination operand (on the 6502, that is 1+2=3 bytes
> total) --- the MiniForth is the only processor that I know of that
> has only the one cell for the destination operand but no memory used
> for the opcode (one bit of the address indicates if the address is
> for a primitive or a colon-word).
> 

My processor has a short-form and long-form of every machine
 instruction, including jsr.  The short-form fits in one word,
 and covers addresses and constants that will fit in 17-bits,
 not unlike the ARM.  The long-form uses a "magic value" of
 $10000 in the 17-bit instruction field, which triggers a 32-
 bit operand fetch from the following instruction word.

> 
> This is not STC --- this is DTC in hardware.
> 
> ...
> 
> Nope, not right at all --- totally not getting it.
> 

Okay, perhaps I misunderstood what I thought was a pretty clear
 description of the various models here:

http://www.bradrodriguez.com/papers/moving1.htm

I'll have to study it again, to see where Dr. Brad lost me.  It
 sucks being wrong, but I'm no stranger to it, and I'll try to
 get it right before I waste any more time on an allegedly
 incorrect train of thought.

> 
> Why don't you learn how the MiniForth works, before tackling
> processor-design yourself? You know: stand on the shoulders of
> those who came before you. The MiniForth is 20-year-old
> technology (it is called the RACE now, and it has been upgraded
> to new hardware, but it is still pretty much the same, and it
> still uses MFX as the development system) --- but although it
> is from last century, it is beyond what you are conceiving now.
> 

I love stuff from the last century ... it was one of the most
 eventful on record, and it even produced you and me!

Do you have any links that you could recommend for me?

Thanks,

Mike

[toc] | [prev] | [next] | [standalone]

#35764

On Monday, January 12, 2015 at 8:04:50 PM UTC-7, Michael Barry wrote:
> On Monday, January 12, 2015 at 5:59:16 PM UTC-8, hughag...@gmail.com wrote:
> > 
> > No, all processors have a JSR opcode (sometimes called CALL), and it
> > takes some number of clock cycles, so it is not free --- the MiniForth
> > is the only processor that I know of that does a call in zero clock
> > cycles --- the MiniForth EXIT (called RTS in most processors) does take
> > one clock cycle, so it is not free (but one clock cycle is not a lot).
> > 
> > ...
> >
> > Also, all processors that I know of require both a JSR opcode and one
> > cell for the destination operand (on the 6502, that is 1+2=3 bytes
> > total) --- the MiniForth is the only processor that I know of that
> > has only the one cell for the destination operand but no memory used
> > for the opcode (one bit of the address indicates if the address is
> > for a primitive or a colon-word).
> > 
> 
> My processor has a short-form and long-form of every machine
>  instruction, including jsr.  The short-form fits in one word,
>  and covers addresses and constants that will fit in 17-bits,
>  not unlike the ARM.  The long-form uses a "magic value" of
>  $10000 in the 17-bit instruction field, which triggers a 32-
>  bit operand fetch from the following instruction word.

Actually, your addresses and constants are 16-bit, not 17-bit, as the high-bit is part of the opcode part rather than the data part. Are these 16-bit "addresses" actually relative offsets to the current PC, or are they absolute addresses in low memory (like the 6502's zero-page, except 64K)? I would make branches relative, but I would make JSRs absolute (so you put all of your common Forth words in the low-64K and hence make your threaded code small), and make memory access absolute too (so you put all of your common data in the low-64K too). 

I'm not very familiar with the ARM --- I do know about the BL instruction though, which I think is pretty cool and worth putting in your processor.

> > This is not STC --- this is DTC in hardware.
> > 
> > Nope, not right at all --- totally not getting it.
> 
> Okay, perhaps I misunderstood what I thought was a pretty clear
>  description of the various models here:
> 
> http://www.bradrodriguez.com/papers/moving1.htm
> 
> I'll have to study it again, to see where Dr. Brad lost me.  It
>  sucks being wrong, but I'm no stranger to it, and I'll try to
>  get it right before I waste any more time on an allegedly
>  incorrect train of thought.

haha --- what a funny way to say that you are right. :-)

What I meant, was that the MiniForth was not STC (what you had said), because the MiniForth distinguished between primitives (in code memory) and colon-words (in data memory), as it is Harvard Architecture. I said that the MiniForth is "DTC in hardware" --- this is sort of correct, but not exactly, as there was no DOCOLON, DOCONSTANT, etc. code in front parameter field --- the only kind of words were colon words and primitives, so there was no DOCOLON code, but this was assumed by NEXT. 

Brad Rodriguez' article is good, and I'm sure you understood it completely --- it just doesn't apply to the MiniForth, because the MiniForth was a "Forth engine" whereas Rodriquez' article is about software implementations.

> > Why don't you learn how the MiniForth works, before tackling
> > processor-design yourself? You know: stand on the shoulders of
> > those who came before you. The MiniForth is 20-year-old
> > technology (it is called the RACE now, and it has been upgraded
> > to new hardware, but it is still pretty much the same, and it
> > still uses MFX as the development system) --- but although it
> > is from last century, it is beyond what you are conceiving now.
> > ... 
> Do you have any links that you could recommend for me?

RACE, the processor formerly known as MiniForth, belongs to Testra --- MFX belongs to them too --- I can't provide any of this to you. 
Ask them:  http://www.testra.com/
AFAIK, they give MFX for free to anybody who asks, as MFX is only good for the RACE and can't be used on any competitor's processor. I wrote a simulator for the MiniForth as part of MFX, so you don't have to buy an experimenter board --- this is just a hobby for you, after all, so you don't want to spend any money --- don't expect any support from them though, if they figure out that this is just a hobby for you, as this is not a hobby for them.

The MiniForth cum RACE may be too reality-based for you, as it was designed for use in motion-control boards, not just to be a fun Forth hobby-horse.

[toc] | [prev] | [next] | [standalone]

#35765

On Monday, January 12, 2015 at 7:52:48 PM UTC-8, hughag...@gmail.com wrote:
> 
> Actually, your addresses and constants are 16-bit, not 17-bit, as
> the high-bit is part of the opcode part rather than the data part.
> 

Well they are more than 16-bit and slightly less than 17-bit.
 -65536 ($10000) is the only magic value, so every other 17-bit
 number in [-65535 .. 65535] is a valid short address or value,
 depending on the addressing mode.  I have reserved negative
 absolute addresses for "system space", whatever that eventually
 becomes, so the positive absolute addresses are available to
 the casual programmer.

> 
> Are these 16-bit "addresses" actually relative offsets to the
> current PC, or are they absolute addresses in low memory (like
> the 6502's zero-page, except 64K)? I would make branches
> relative, but I would make JSRs absolute (so you put all of
> your common Forth words in the low-64K and hence make your
> threaded code small), and make memory access absolute too
> (so you put all of your common data in the low-64K too). 
> 

Every operand, short or long, is added to a hardware register
 by the operand adder.  If the register is Z, and the operand
 is an address, then you have the equivalent of absolute
 addressing (zero page in short-form, absolute in long form).
 If the register is N (the name I chose for the instruction
 pointer ... Nstruction pointer, get it??) then you have the
 equivalent of PC-relative.  If the register is S, then you
 have system stack-relative, and so on.

I didn't stop at addresses for this mechanism:  it also works
 for the 6xxx equivalent of immediate data.  I don't need a
 special op-code for the 6xxx version of INX, because I can
 do the same (and much more) with a simple load instruction:

        ldx  #1,x       ; x++
        ldx  #-6000,x   ; x -= 6000
        ldy  #14,x      ; y = x + 14
        adx  #432,x     ; x += x + 432

... well, the last one isn't a load instruction, but I was
 proud of thinking it up anyway ...

> ...
> I'm not very familiar with the ARM --- I do know about the
> BL instruction though, which I think is pretty cool and
> worth putting in your processor.
> 

I should admit that I don't know much about ARM either ...
 I have a little bit of opcode space left, and I'll take a
 look at BL to see if it tickles my fancy enough to include.

> ...
> haha --- what a funny way to say that you are right. :-)
> 

That, my friend, is what some of us call the elusive skill
 of "tact".  I'm certainly no master, but I consider
 myself to be an interested student of the subject.  Care
 to join me?

> ...
> The MiniForth cum RACE may be too reality-based for you,
> as it was designed for use in motion-control boards, not
> just to be a fun Forth hobby-horse.
> 

Sounds cool.  I'll make an effort to learn more about it.

Thanks,

Mike

[toc] | [prev] | [next] | [standalone]

#35803

On Monday, January 12, 2015 at 9:28:26 PM UTC-7, Michael Barry wrote:
> On Monday, January 12, 2015 at 7:52:48 PM UTC-8, hughag...@gmail.com wrote:
> > 
> > Actually, your addresses and constants are 16-bit, not 17-bit, as
> > the high-bit is part of the opcode part rather than the data part.
> > 
> 
> Well they are more than 16-bit and slightly less than 17-bit.
>  -65536 ($10000) is the only magic value, so every other 17-bit
>  number in [-65535 .. 65535] is a valid short address or value,
>  depending on the addressing mode.  I have reserved negative
>  absolute addresses for "system space", whatever that eventually
>  becomes, so the positive absolute addresses are available to
>  the casual programmer.
> 
> > 
> > Are these 16-bit "addresses" actually relative offsets to the
> > current PC, or are they absolute addresses in low memory (like
> > the 6502's zero-page, except 64K)? I would make branches
> > relative, but I would make JSRs absolute (so you put all of
> > your common Forth words in the low-64K and hence make your
> > threaded code small), and make memory access absolute too
> > (so you put all of your common data in the low-64K too). 
> > 
> 
> Every operand, short or long, is added to a hardware register
>  by the operand adder.  If the register is Z, and the operand
>  is an address, then you have the equivalent of absolute
>  addressing (zero page in short-form, absolute in long form).
>  If the register is N (the name I chose for the instruction
>  pointer ... Nstruction pointer, get it??) then you have the
>  equivalent of PC-relative.  If the register is S, then you
>  have system stack-relative, and so on.
> 
> I didn't stop at addresses for this mechanism:  it also works
>  for the 6xxx equivalent of immediate data.  I don't need a
>  special op-code for the 6xxx version of INX, because I can
>  do the same (and much more) with a simple load instruction:
> 
>         ldx  #1,x       ; x++
>         ldx  #-6000,x   ; x -= 6000
>         ldy  #14,x      ; y = x + 14
>         adx  #432,x     ; x += x + 432
> 
> ... well, the last one isn't a load instruction, but I was
>  proud of thinking it up anyway ...

That looks like a pretty good design.

I'm currently writing in AVR assembly-language, and it has some weaknesses. The branches are relative, which is good because branch destinations are usually close, but the short form of CALL (RCALL) is also relative, which is bad because there is not reason to believe that any sub-function is going to be close --- it would be better if they were absolute, so all the common sub-functions (the Forth primitives) could be put in one place and get a short CALL from everywhere in the program.

> > ...
> > haha --- what a funny way to say that you are right. :-)
> > 
> 
> That, my friend, is what some of us call the elusive skill
>  of "tact".  I'm certainly no master, but I consider
>  myself to be an interested student of the subject.  Care
>  to join me?

I think that being tactful would be a good idea, so people would like me better --- I also think that growing fur would be a good idea, so I can be warm in the winter without wearing a coat --- neither is likely to happen.

> > The MiniForth cum RACE may be too reality-based for you,
> > as it was designed for use in motion-control boards, not
> > just to be a fun Forth hobby-horse.
> 
> Sounds cool.  I'll make an effort to learn more about it.

When I visited recently, I asked if they had an experimenter's board for hobbyists, and I was told 'no' --- Tom Hart said: "Hobbyists aren't a good market to target because they require too much support, and they don't have any money."

So, don't expect to be welcomed with open arms --- showing up with a suitcase full of cash will get their attention though.

[toc] | [prev] | [next] | [standalone]

#35768

hughaguilar96@gmail.com writes:
[...]
> RACE, the processor formerly known as MiniForth, belongs to Testra ---
> MFX belongs to them too --- I can't provide any of this to you.  Ask
> them: http://www.testra.com/
[...]

When I (from pure curiosity) tried to go to this site it asked for login
and password. It's very strange. Aren't they publicly available anymore
or they just filter some IPs?

[toc] | [prev] | [next] | [standalone]

#35769

Alexander Skobelev <al.skobelev@gmail.com> writes:

> hughaguilar96@gmail.com writes:
> [...]
>> RACE, the processor formerly known as MiniForth, belongs to Testra ---
>> MFX belongs to them too --- I can't provide any of this to you.  Ask
>> them: http://www.testra.com/
> [...]
>
> When I (from pure curiosity) tried to go to this site it asked for login
> and password. It's very strange. Aren't they publicly available anymore
> or they just filter some IPs?

Oops, sorry, this seems to be Safari problem – all opens fine from Firefox.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.forth

csiph-web