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

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

string-stack.4th

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

Contents

  string-stack.4th hughaguilar96@gmail.com - 2016-03-03 21:42 -0800
    Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-03 21:54 -0800
    Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-04 18:01 -0800
      Re: string-stack.4th Mark Wills <markwills1970@gmail.com> - 2016-03-05 02:52 -0800
        Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-05 15:17 -0800
          Re: string-stack.4th foxaudioresearch@gmail.com - 2016-03-06 08:50 -0800
            Re: string-stack.4th foxaudioresearch@gmail.com - 2016-03-06 10:54 -0800
              Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-06 14:08 -0800
                Re: string-stack.4th "HAA" <someone@microsoft.com> - 2016-03-07 10:30 +1100
                  Re: string-stack.4th foxaudioresearch@gmail.com - 2016-03-06 16:45 -0800
                    Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-06 19:09 -0800
                      Re: string-stack.4th Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-03-07 12:27 +0000
                        Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-07 22:44 -0800
                          Re: string-stack.4th JennyB <jennybrien@googlemail.com> - 2016-03-11 03:47 -0800
                        Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-09 22:27 -0800
                          Re: string-stack.4th Coos Haak <chforth@hccnet.nl> - 2016-03-10 11:05 +0100
                            Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-10 09:28 -0800
                              Re: string-stack.4th Coos Haak <chforth@hccnet.nl> - 2016-03-11 00:10 +0100
                                Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-10 22:42 -0800
                                  Re: string-stack.4th Coos Haak <chforth@hccnet.nl> - 2016-03-11 12:29 +0100
                                    Re: string-stack.4th JennyB <jennybrien@googlemail.com> - 2016-03-12 01:33 -0800
                                      Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-12 16:56 -0800
                            Re: string-stack.4th "WJ" <w_a_x_man@yahoo.com> - 2016-04-22 09:55 +0000
                            Re: string-stack.4th "WJ" <w_a_x_man@yahoo.com> - 2016-04-22 10:00 +0000
                          Re: string-stack.4th "WJ" <w_a_x_man@yahoo.com> - 2016-03-11 06:24 +0000
                        Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-21 23:26 -0700
                      Re: string-stack.4th franck.bensusan@gmail.com - 2016-03-10 10:42 -0800
                        Re: string-stack.4th hughaguilar96@gmail.com - 2016-03-10 23:00 -0800
                          Re: string-stack.4th hughaguilar96@gmail.com - 2016-04-10 20:23 -0700
                            Re: string-stack.4th stephen@mpeforth.com (Stephen Pelc) - 2016-04-11 09:45 +0000
                              Re: string-stack.4th hughaguilar96@gmail.com - 2016-04-11 20:00 -0700
                            Re: string-stack.4th Mark Wills <markwills1970@gmail.com> - 2016-04-11 03:16 -0700
                              Re: string-stack.4th Mark Wills <markwills1970@gmail.com> - 2016-04-11 03:47 -0700
                              Re: string-stack.4th Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-04-11 05:50 -0500
                                Re: string-stack.4th Raimond Dragomir <raimond.dragomir@gmail.com> - 2016-04-11 04:21 -0700
                                  Re: string-stack.4th Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-04-11 06:36 -0500
                                  Re: string-stack.4th hughaguilar96@gmail.com - 2016-04-11 20:34 -0700
                                Re: string-stack.4th hughaguilar96@gmail.com - 2016-04-11 20:20 -0700
                            Re: string-stack.4th hughaguilar96@gmail.com - 2016-06-03 05:53 -0700
                Re: string-stack.4th Mark Wills <markwills1970@gmail.com> - 2016-03-08 11:29 -0800

Page 1 of 2  [1] 2  Next page →

#45815 — string-stack.4th

On Saturday, November 17, 2012 at 10:24:26 AM UTC-7, Elizabeth D. Rather wrote:
> On 11/17/12 2:56 AM, Alex McDonald wrote:
> > On Nov 17, 12:18 pm, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> ...
> >> I have multiple stacks, with each stack associated to a particular
> >> data-type --- well, at least to a particular data-type size, as the
> >> double-wide stack will be for both double-precision integers and
> >> adr,len strings which are different data types but which both fit
> >> nicely on the double-wide stack. The point of doing this is to reduce
> >> the amount of stack-juggling that is done --- stack-juggling is a big
> >> part of why ANS-Forth is widely considered to be unreadable --- it is
> >> a major mess to have double-wide data intermingled with single-wide
> >> data on the parameter stack. I will also support local variables of
> >> course, but they won't be needed as a crutch to avoid stack-juggling
> >> as is often true in ANS-Forth --- with the multiple stacks, Forth
> >> purists who dislike locals will be able to write code without locals,
> >> while yet avoiding all of that ugly stack-juggling that typically
> >> plagues ANS-Forth.
> >
> > : foo s" abcd" over 1 ." the character " type ."  is the first
> > character of " type ;
> > : hugh ??? ;
> >
> > Fill in the ??? please without introducing stack to stack moves.
> >
> 
> The addr-len parameters for a string are not an example of "double-wide" 
> data, they are a pair of single-cell items each of which has a meaning 
> and potential use independent of the fact that together they describe a 
> string.
> 
> For example:
> 
> S" Here is some text" PAD SWAP MOVE
> 
> ...uses them individually but in a relevant way, as does Alex's example.
> 
> Double-length integers are less likely to need their components treated 
> individually, but even there it's awfully nice to be able to convert a 
> double that you know (because of application knowledge) to a single by 
> doing a DROP.
> 
> Cheers,
> Elizabeth

I have written another file for the novice-package. This provides a stack of strings. My goal here was to get ANS-Forth up to the level of QBASIC in regard to text handling. I remember reading an article comparing Forth to QBASIC written in the early 1990s. The author said that Forth is a better language because it has features such as meta-compilation that allow the language to be extended, but that QBASIC was far superior in out-of-the-box capability, especially in regard to strings. Forth has always been like this --- a lot of potential, but little or no capability --- more thunder than lightning.

Using string-stack.4th, for example, we can do things like this:

: hugh ( -- )
    s" abcd" >$  
    ." the character: " dup$  1 left$ .$
    ."  is the first character of: " .$ ;

I do have stack-to-stack moves (the >$ above), despite the challenge to write the code without. I don't really understand why this is a problem. S" is the standard way to generate constant strings (note that the novice-package provides an S" that works in interpretive mode, and there can be more than one of them, all of which is an enhancement to ANS-Forth).

The strings are held on the heap. The code is efficient however, in that it minimizes the number of ALLOC and DEALLOC calls. In the above function, for example, the DUP$ does not allocate a new heap element.

I can provide string-stack.4th to anybody who wants it. It will also be in the next novice-package release, which is coming soon.

[toc] | [next] | [standalone]

#45816

On Thursday, March 3, 2016 at 10:42:53 PM UTC-7, hughag...@gmail.com wrote:
> On Saturday, November 17, 2012 at 10:24:26 AM UTC-7, Elizabeth D. Rather wrote:
> > On 11/17/12 2:56 AM, Alex McDonald wrote:
> > > On Nov 17, 12:18 pm, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> > ...
> > >> I have multiple stacks, with each stack associated to a particular
> > >> data-type --- well, at least to a particular data-type size, as the
> > >> double-wide stack will be for both double-precision integers and
> > >> adr,len strings which are different data types but which both fit
> > >> nicely on the double-wide stack. The point of doing this is to reduce
> > >> the amount of stack-juggling that is done --- stack-juggling is a big
> > >> part of why ANS-Forth is widely considered to be unreadable --- it is
> > >> a major mess to have double-wide data intermingled with single-wide
> > >> data on the parameter stack. I will also support local variables of
> > >> course, but they won't be needed as a crutch to avoid stack-juggling
> > >> as is often true in ANS-Forth --- with the multiple stacks, Forth
> > >> purists who dislike locals will be able to write code without locals,
> > >> while yet avoiding all of that ugly stack-juggling that typically
> > >> plagues ANS-Forth.
> > >
> > > : foo s" abcd" over 1 ." the character " type ."  is the first
> > > character of " type ;
> > > : hugh ??? ;
> > >
> > > Fill in the ??? please without introducing stack to stack moves.
> > >
> > 
> > The addr-len parameters for a string are not an example of "double-wide" 
> > data, they are a pair of single-cell items each of which has a meaning 
> > and potential use independent of the fact that together they describe a 
> > string.
> > 
> > For example:
> > 
> > S" Here is some text" PAD SWAP MOVE
> > 
> > ...uses them individually but in a relevant way, as does Alex's example.
> > 
> > Double-length integers are less likely to need their components treated 
> > individually, but even there it's awfully nice to be able to convert a 
> > double that you know (because of application knowledge) to a single by 
> > doing a DROP.
> > 
> > Cheers,
> > Elizabeth
> 
> I have written another file for the novice-package. This provides a stack of strings. My goal here was to get ANS-Forth up to the level of QBASIC in regard to text handling. I remember reading an article comparing Forth to QBASIC written in the early 1990s. The author said that Forth is a better language because it has features such as meta-compilation that allow the language to be extended, but that QBASIC was far superior in out-of-the-box capability, especially in regard to strings. Forth has always been like this --- a lot of potential, but little or no capability --- more thunder than lightning.
> 
> Using string-stack.4th, for example, we can do things like this:
> 
> : hugh ( -- )
>     s" abcd" >$  
>     ." the character: " dup$  1 left$ .$
>     ."  is the first character of: " .$ ;
> 
> I do have stack-to-stack moves (the >$ above), despite the challenge to write the code without. I don't really understand why this is a problem. S" is the standard way to generate constant strings (note that the novice-package provides an S" that works in interpretive mode, and there can be more than one of them, all of which is an enhancement to ANS-Forth).
> 
> The strings are held on the heap. The code is efficient however, in that it minimizes the number of ALLOC and DEALLOC calls. In the above function, for example, the DUP$ does not allocate a new heap element.
> 
> I can provide string-stack.4th to anybody who wants it. It will also be in the next novice-package release, which is coming soon.

Here is another fun quote:

On Thursday, November 15, 2012 at 5:36:18 PM UTC-7, Stephen Pelc wrote:
> For practical applications, all Forth standards to date have been
> inadequate for commercial level string handling.

Both of these quotes come from this thread:
https://groups.google.com/forum/#!topic/comp.lang.forth/IAyf4wHMTig%5B151-175%5D

Note that my string-stack.4th is written entirely in ANS-Forth, as is all of the novice-package. Stephen Pelc's quote is yet another example of the committee members telling the Forth community that what they want to do is impossible --- the committee members seem to be obsessed by the desire to restrict what can be done with Forth.

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

#45847

On Thursday, March 3, 2016 at 10:42:53 PM UTC-7, hughag...@gmail.com wrote:
> On Saturday, November 17, 2012 at 10:24:26 AM UTC-7, Elizabeth D. Rather wrote:
> > The addr-len parameters for a string are not an example of "double-wide" 
> > data, they are a pair of single-cell items each of which has a meaning 
> > and potential use independent of the fact that together they describe a 
> > string.
> > 
> > For example:
> > 
> > S" Here is some text" PAD SWAP MOVE
> > 
> > ...uses them individually but in a relevant way, as does Alex's example.

My string-stack.4th could easily be rewritten to use UTF-8 or UTF-16 or any other character-coding system. I mention this because Ching mentioned the subject of Chinese text to me, which made me think about UTF-8.

The advantage of abstracting away the concept of a string, is that the internal definition of a string can be changed while the API remains the same. I could write a version of string-stack.4th that worked with UTF-8 and most of the programs using string-stack.4th would continue to work unchanged using either version. The only problems that would arise are when the strings on the string-stack are transferred over to the data-stack as an adr/cnt pair by $> --- but this should not be a problem because $> is only used when strings have to be stored in data-structures --- if the string is going to be stored in a data-structure and later put back on the string-stack, the adr/cnt will be fine, but the adr/cnt is only a problem when the programmer accesses the string assuming carnal knowledge about the string (assuming that it is ascii).

I'll make a note in the documentation explaining this issue --- tell the users that if they use $> to obtain an adr/cnt pair then they should not do anything with the adr/cnt pair except store it somewhere and eventually use >$ to put it back on the string-stack --- they should not access the string's chars manually because doing so involves a lot of assumptions about the string that aren't necessarily true.

Another problem with UTF-8 (or UTF-16 or any other UTF format) is that UCASE$ and LCASE$ are quite difficult to write, as there is no simple way to distinguish uppercase from lowercase in the myriad languages supported (some languages don't even have uppercase and lowercase; I don't think Chinese does). This is another issue I will have to mention in the documentation --- if people want their programs to work with UTF-8 or any encoding other than ascii, they have to avoid UCASE$ and LCASE$ as well as all of the case-insensitive comparison functions.

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

#45851

On Saturday, 5 March 2016 02:01:30 UTC, hughag...@gmail.com  wrote:
> On Thursday, March 3, 2016 at 10:42:53 PM UTC-7, hughag...@gmail.com wrote:
> > On Saturday, November 17, 2012 at 10:24:26 AM UTC-7, Elizabeth D. Rather wrote:
> > > The addr-len parameters for a string are not an example of "double-wide" 
> > > data, they are a pair of single-cell items each of which has a meaning 
> > > and potential use independent of the fact that together they describe a 
> > > string.
> > > 
> > > For example:
> > > 
> > > S" Here is some text" PAD SWAP MOVE
> > > 
> > > ...uses them individually but in a relevant way, as does Alex's example.
> 
> My string-stack.4th could easily be rewritten to use UTF-8 or UTF-16 or any other character-coding system. I mention this because Ching mentioned the subject of Chinese text to me, which made me think about UTF-8.
> 
> The advantage of abstracting away the concept of a string, is that the internal definition of a string can be changed while the API remains the same. I could write a version of string-stack.4th that worked with UTF-8 and most of the programs using string-stack.4th would continue to work unchanged using either version. The only problems that would arise are when the strings on the string-stack are transferred over to the data-stack as an adr/cnt pair by $> --- but this should not be a problem because $> is only used when strings have to be stored in data-structures --- if the string is going to be stored in a data-structure and later put back on the string-stack, the adr/cnt will be fine, but the adr/cnt is only a problem when the programmer accesses the string assuming carnal knowledge about the string (assuming that it is ascii).
> 
> I'll make a note in the documentation explaining this issue --- tell the users that if they use $> to obtain an adr/cnt pair then they should not do anything with the adr/cnt pair except store it somewhere and eventually use >$ to put it back on the string-stack --- they should not access the string's chars manually because doing so involves a lot of assumptions about the string that aren't necessarily true.
> 
> Another problem with UTF-8 (or UTF-16 or any other UTF format) is that UCASE$ and LCASE$ are quite difficult to write, as there is no simple way to distinguish uppercase from lowercase in the myriad languages supported (some languages don't even have uppercase and lowercase; I don't think Chinese does). This is another issue I will have to mention in the documentation --- if people want their programs to work with UTF-8 or any encoding other than ascii, they have to avoid UCASE$ and LCASE$ as well as all of the case-insensitive comparison functions.

Good job. Pleased to see someone else working with string stacks.

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

#45863

On Saturday, March 5, 2016 at 3:52:48 AM UTC-7, Mark Wills wrote:
> Good job. Pleased to see someone else working with string stacks.

For the record, I was inspired to write string-stack.4th by Mark Wills (this is mentioned in my documentation). He has Turbo Forth code and an ANS-Forth implementation as well. My internal workings are different, but the general idea of a stack for strings came from him. To a large extent my API is the same as his, but there are some differences --- the API is largely derived from QBASIC with MID$ and +$ etc..

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

#45896

On Saturday, March 5, 2016 at 6:17:20 PM UTC-5, hughag...@gmail.com wrote:
> On Saturday, March 5, 2016 at 3:52:48 AM UTC-7, Mark Wills wrote:
> > Good job. Pleased to see someone else working with string stacks.
> 
> For the record, I was inspired to write string-stack.4th by Mark Wills (this is mentioned in my documentation). He has Turbo Forth code and an ANS-Forth implementation as well. My internal workings are different, but the general idea of a stack for strings came from him. To a large extent my API is the same as his, but there are some differences --- the API is largely derived from QBASIC with MID$ and +$ etc..

And for the record, I wrote these kind of concepts in the 1980s for Ti-Forth for the the TI-99 as a recovering BASIC programmer and submitted an article to Dr. Dobbs but it was declined.  I re-wrote the code for HS/Forth in the 1990s for use in real world applications.  In the 2000s somewhere I shared that code with Mark after I saw his cool work on the TI-99. (hard to forget your first machine)  Mark re-wrote string stack code based on these concepts for Turbo Forth putting them back into the TI-99.  That's kind of amusing. :-)


BF

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

#45899

On Sunday, March 6, 2016 at 11:50:23 AM UTC-5, foxaudio...@gmail.com wrote:
> On Saturday, March 5, 2016 at 6:17:20 PM UTC-5, hughag...@gmail.com wrote:
> > On Saturday, March 5, 2016 at 3:52:48 AM UTC-7, Mark Wills wrote:
> > > Good job. Pleased to see someone else working with string stacks.
> > 
> > For the record, I was inspired to write string-stack.4th by Mark Wills (this is mentioned in my documentation). He has Turbo Forth code and an ANS-Forth implementation as well. My internal workings are different, but the general idea of a stack for strings came from him. To a large extent my API is the same as his, but there are some differences --- the API is largely derived from QBASIC with MID$ and +$ etc..
> 
> And for the record, I wrote these kind of concepts in the 1980s for Ti-Forth for the the TI-99 as a recovering BASIC programmer and submitted an article to Dr. Dobbs but it was declined.  I re-wrote the code for HS/Forth in the 1990s for use in real world applications.  In the 2000s somewhere I shared that code with Mark after I saw his cool work on the TI-99. (hard to forget your first machine)  Mark re-wrote string stack code based on these concepts for Turbo Forth putting them back into the TI-99.  That's kind of amusing. :-)
> 
> 
> BF

I stripped my old string stack code down to what I feel is truly useful and also adapted it closer to current Forth thinking on the use of stack strings.
It's not totally compatible with that line of thinking but this code makes my old HS/Forth hobby system better able to compile other peoples code today and still gives me my crutch. :-)
This version also compiles on Win32Forth. I think is pretty standard code.

\ strings.HSF slightly new approach to my old string system

\ Wil Baden's toolbelt
: c+!      ( n addr -- )          dup>r  c@ +  r> c! ;
: append-char  ( char string -- ) dup>r  count dup 1+ r> c! + c! ;
: +place   ( addr1 n addr2 -- )   2dup 2>r  count +  swap move 2r> c+! ;
: place    ( addr1 n addr2 -- )   2dup 2>r  1+  swap  move  2r> c! ;

HEX
\ build a string stack/array to hold input strings
100 constant ss-width
ss-width 1- constant max$len

: stack-base  here ss-width + ;

variable $depth

DECIMAL
: LEN      ( $1 -- length)     c@ ;
: ITEMS    ( -- n)             $depth @  ;
: new:     ( -- )              1 $depth +! ;
: drop$    ( -- )   -          -1 $depth +! ;
: ]stk$    ( ndx -- addr)      ss-width * stack-base + ;
: TOP$     ( -- addr)          $depth @ ]stk$ ;
: collapse ( -- )              $depth off ;
: >new:top$ ( addr len -- top$) new: top$ dup >r place r> ;
: move$    ( $1 $2 -- )        >r COUNT R> PLACE ;
: push$    ( $ -- )            new: top$ move$ ;

\ used primitives to build counted string functions
: left$    ( $addr #char --  top len  ) >r count drop r>  >new:top$ ;
: right$   ( $addr1 n  -- $addr2)  >r count r> over min /string >new:top$ ;
: +$       ( $1 $2 --  top$ )  SWAP push$ count TOP$ +PLACE TOP$ ;
: mid$     ( adr$ start len  --  top$)  new: top$  2>r + 1+  2r> place top$   ;
: pos$     ( adr$ char -- position ) >r count 2dup r> scan  drop nip swap - ;

: compare$ ( $1 $2 -- -n:0:n ) count rot count compare ;
 : =$       ( $1 $2 -- flag ) compare$ 0= ;
 : +char    (  $ char -- $)   over append-char ;

: :=""     ( caddr -- )        0 swap c! ;
: :="      ( $addr -- <text> ) [CHAR] " word swap move$ ;

\ these 2 words provide cheap automatic garbage collection
: $.       ( $ -- ) count type collapse ;
: $!       ( $1 $2 -- ) move$ collapse ;

: split    ( str len char -- str1 len1 str2 len2 ) 
           >r 2dup r> scan 2swap 2 pick - ;

: snip     ( str len  -- ) 1- swap 1+ swap ;
: separate ( str len char -- str1 len1 str2 len2 ) split 2swap snip 2swap ;

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

#45902

On Sunday, March 6, 2016 at 11:54:30 AM UTC-7, foxaudio...@gmail.com wrote:
> On Sunday, March 6, 2016 at 11:50:23 AM UTC-5, foxaudio...@gmail.com wrote:
> > On Saturday, March 5, 2016 at 6:17:20 PM UTC-5, hughag...@gmail.com wrote:
> > > On Saturday, March 5, 2016 at 3:52:48 AM UTC-7, Mark Wills wrote:
> > > > Good job. Pleased to see someone else working with string stacks.
> > > 
> > > For the record, I was inspired to write string-stack.4th by Mark Wills (this is mentioned in my documentation). He has Turbo Forth code and an ANS-Forth implementation as well. My internal workings are different, but the general idea of a stack for strings came from him. To a large extent my API is the same as his, but there are some differences --- the API is largely derived from QBASIC with MID$ and +$ etc..
> > 
> > And for the record, I wrote these kind of concepts in the 1980s for Ti-Forth for the the TI-99 as a recovering BASIC programmer and submitted an article to Dr. Dobbs but it was declined.  I re-wrote the code for HS/Forth in the 1990s for use in real world applications.  In the 2000s somewhere I shared that code with Mark after I saw his cool work on the TI-99. (hard to forget your first machine)  Mark re-wrote string stack code based on these concepts for Turbo Forth putting them back into the TI-99.  That's kind of amusing. :-)

When Mark discussed this topic with me, he recommended that I hold the strings in the heap. This is what I did. My string-stack is only 2 cells wide (the adr/cnt pair). My strings are not limited to 255 chars as yours are.

My own innovation was to work out a method in which I minimize the calls to ALLOC and DEALLOC on the assumption that these are the speed-killers. I mentioned in my first post that DUP$ does not call ALLOC but all it does is make a copy of the adr/cnt of the string that it is duplicating. The LEFT$ just modifies this adr/cnt (adjusts the cnt). The .$ just types out the string and drops the adr/cnt from the string-stack. The next .$ also types out the string but it has to DEALLOC the string before it drops the adr/cnt from the string-stack.

Most likely, my code is going to be faster than yours. You don't list DUP$ in your code, but if you did then it would call MOVE$ which copies the string --- copying a string is also a speed-killer that I avoid.

Anyway, I'm not saying that I invented the concept of the string-stack. I got the idea from Mark Wills. He apparently got the idea from you. The idea may have been independently invented several times (Forth has a stack for cells so a stack for strings is an obvious next step).

All I'm saying is that my string-stack.4th is the most efficient.

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

#45904

hughaguilar96@gmail.com wrote:
> ...
> Anyway, I'm not saying that I invented the concept of the string-stack. I got the idea
> from Mark Wills. He apparently got the idea from you. The idea may have been
> independently invented several times (Forth has a stack for cells so a stack for
> strings is an obvious next step).

The idea for a string stack has been around a long time e.g. "Stacking Strings
in Forth" J.Cassady, BYTE 2/1981.

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

#45907

On Sunday, March 6, 2016 at 6:32:49 PM UTC-5, HAA wrote:
> hughaguilar96@gmail.com wrote:
> > ...
> > Anyway, I'm not saying that I invented the concept of the string-stack. I got the idea
> > from Mark Wills. He apparently got the idea from you. The idea may have been
> > independently invented several times (Forth has a stack for cells so a stack for
> > strings is an obvious next step).
> 
> The idea for a string stack has been around a long time e.g. "Stacking Strings
> in Forth" J.Cassady, BYTE 2/1981.

I am pretty certain there was a an article in Forth Dimensions some time in the mid '80s that got me thinking in that fashion.

My goal was to be able to write string expressions without worrying about intermediate results and then quickly collapsing the string stack after getting the result. So the string words leave an address behind for the next function to consume. That's the only thing remotely innovative.

It works ok. I would be very interested in seeing how it compares in speed to using Allocate et al...  

Hugh can you run some tests when you have some time?

I implemented Allocate for my own amusement and it seems much more complicated that simply grabbing some free space quickly and then setting a variable to 0 when you are finished.

However the efficiency of cutting up stack strings is very impressive.  Beats copying or allocating every time I should think.

BF

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

#45910

On Sunday, March 6, 2016 at 5:45:39 PM UTC-7, foxaudio...@gmail.com wrote:
> It works ok. I would be very interested in seeing how it compares in speed to using Allocate et al...  
> 
> Hugh can you run some tests when you have some time?

I would like to get a program that does a lot of string-handling --- perhaps a port of an old QBASIC program --- and use that as a demonstration of my string-stack.4th. A program like this might also make for a good benchmark. Any suggestions would be appreciated.

> I implemented Allocate for my own amusement and it seems much more complicated that simply grabbing some free space quickly and then setting a variable to 0 when you are finished.

Allocate varies a lot in speed from one Forth system to another. This also depends upon the OS underneath. For the most part, allocate is pretty slow. It is necessary to use the heap though, if you are going to support strings of any size --- I think this is important, as that old 255 char limit is something that we want to put in the past and forget about.

> However the efficiency of cutting up stack strings is very impressive.  Beats copying or allocating every time I should think.

I have two kinds of strings on the string-stack, which are "unique" and "derivative." A unique string is one that is on the heap. A derivative string is one that is inside of a unique string. A derivative string is indicated by having a negative cnt value. I have these kinds of words:

1.) JUGGLERS --- These include SWAP$ etc. and they just move items around on the string-stack.

2.) DUPLICATORS --- These include DUP$ etc. and they make a derivative item.

3.) CONSUMERS --- These include .$ etc. and they consume an item. If the item is a derivative it is just dropped. If the item is a unique, then FIX-DERIVATIVES is called first (this searches the string-stack for derivatives that are inside of this unique and changes them into uniques) and then it is dropped.

4.) MUTATORS --- These include UCASE$ etc. and they modify an item. If the item is a derivative it gets changed into a unique first, and if the item is a unique then FIX-DERIVATIVES gets called first, then the item is modified.

Because the DUPLICATORS put the derivative on top of the string-stack, you generally have derivatives above their uniques on the string-stack. This is good because a CONSUMER or MUTATOR of a derivative is faster than of a unique. For the most part, we can avoid doing ALLOC and DEALLOC because we are working with derivatives. This plan gets messed up when SWAP$ or ROT$ etc. are used and we end up with a unique above its derivatives on the string-stack --- then when we do a CONSUMER or MUTATOR of the unique we end up having to call FIX-DERIVATIVES which is the speed-killer --- this should be pretty rare in most programs however, because SWAP$ and ROT$ etc. tend to be pretty rare.

You asked above for a speed benchmark. This is somewhat difficult because it depends upon what a typical program is like (how much SWAP$ and ROT$ etc. are used). Since we don't actually have any programs at this time, it is somewhat early to say anything about what a typical program would be like.

BTW: My ultimate goal with all of this is to write a program that can translate Esperanto into English or Spanish or whatever. I thought of this way back in 1984 when I was learning Esperanto. It is too difficult for a program to translate directly from Spanish to English or vice-versa because those language are difficult to figure out (this was true 30 years ago and is still true). By making the human write in Esperanto however, most of the work can be dumped on the human. Translating from Esperanto to English or Spanish should be possible. All the Esperanto words have a suffix that tells you exactly what part of speech they are. In string-stack.4th I have functions for working with prefixes and suffixes that I provided specifically for taking apart Esperanto words. The idea is that the front-end of the program builds a lexical tree for the Esperanto sentence. There would be a back-end of the program specific to each output language that converts the lexical tree into English, Spanish, etc..

BTW: It was Marcos Cruz who got me thinking about Esperanto --- I haven't given any thought to that subject in almost 30 years --- at one time though, I did know a little about the subject.

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

#45916

hughaguilar96@gmail.com writes:

>On Sunday, March 6, 2016 at 5:45:39 PM UTC-7, foxaudio...@gmail.com wrote:
>> It works ok. I would be very interested in seeing how it compares in spee=
>d to using Allocate et al... =20
>>=20
>> Hugh can you run some tests when you have some time?

>I would like to get a program that does a lot of string-handling --- perhap=
>s a port of an old QBASIC program --- and use that as a demonstration of my=
> string-stack.4th. A program like this might also make for a good benchmark=
>. Any suggestions would be appreciated.

>> I implemented Allocate for my own amusement and it seems much more compli=
>cated that simply grabbing some free space quickly and then setting a varia=
>ble to 0 when you are finished.

>Allocate varies a lot in speed from one Forth system to another. This also =
>depends upon the OS underneath. For the most part, allocate is pretty slow.=
> It is necessary to use the heap though, if you are going to support string=
>s of any size --- I think this is important, as that old 255 char limit is =
>something that we want to put in the past and forget about.

>> However the efficiency of cutting up stack strings is very impressive.  B=
>eats copying or allocating every time I should think.

>I have two kinds of strings on the string-stack, which are "unique" and "de=
>rivative." A unique string is one that is on the heap. A derivative string =
>is one that is inside of a unique string. A derivative string is indicated =
>by having a negative cnt value. I have these kinds of words:

That is a neat trick, and I like the following analysis, which could be
a basis for a good practical package.

>1.) JUGGLERS --- These include SWAP$ etc. and they just move items around o=
>n the string-stack.

>2.) DUPLICATORS --- These include DUP$ etc. and they make a derivative item=
>.

>3.) CONSUMERS --- These include .$ etc. and they consume an item. If the it=
>em is a derivative it is just dropped. If the item is a unique, then FIX-DE=
>RIVATIVES is called first (this searches the string-stack for derivatives t=
>hat are inside of this unique and changes them into uniques) and then it is=
> dropped.

>4.) MUTATORS --- These include UCASE$ etc. and they modify an item. If the =
>item is a derivative it gets changed into a unique first, and if the item i=
>s a unique then FIX-DERIVATIVES gets called first, then the item is modifie=
>d.

>Because the DUPLICATORS put the derivative on top of the string-stack, you =
>generally have derivatives above their uniques on the string-stack. This is=
> good because a CONSUMER or MUTATOR of a derivative is faster than of a uni=
>que. For the most part, we can avoid doing ALLOC and DEALLOC because we are=
> working with derivatives. This plan gets messed up when SWAP$ or ROT$ etc.=
> are used and we end up with a unique above its derivatives on the string-s=
>tack --- then when we do a CONSUMER or MUTATOR of the unique we end up havi=
>ng to call FIX-DERIVATIVES which is the speed-killer --- this should be pre=
>tty rare in most programs however, because SWAP$ and ROT$ etc. tend to be p=
>retty rare.

I would like to extend the analysis by the following.
If you swap derived strings there is no problem. Only if you juggle
a derived string under a unique string there may be problems. In both
SWAP$ and ROT$ that can only be the case if the new string on top is
unique. It suffices to replace the one (swap) or two (rot) strings
by uniques if they are derived.

>You asked above for a speed benchmark. This is somewhat difficult because i=
>t depends upon what a typical program is like (how much SWAP$ and ROT$ etc.=
> are used). Since we don't actually have any programs at this time, it is s=
>omewhat early to say anything about what a typical program would be like.

The allocate contained in ciforth would be suitable, as it uses the first
free space available. You can just copy it from lina's forth.lab, or mail
me for a more heavily commented version.

>BTW: My ultimate goal with all of this is to write a program that can trans=
>late Esperanto into English or Spanish or whatever. I thought of this way b=
>ack in 1984 when I was learning Esperanto. It is too difficult for a progra=
>m to translate directly from Spanish to English or vice-versa because those=
> language are difficult to figure out (this was true 30 years ago and is st=
>ill true). By making the human write in Esperanto however, most of the work=
> can be dumped on the human. Translating from Esperanto to English or Spani=
>sh should be possible. All the Esperanto words have a suffix that tells you=
> exactly what part of speech they are. In string-stack.4th I have functions=
> for working with prefixes and suffixes that I provided specifically for ta=
>king apart Esperanto words. The idea is that the front-end of the program b=
>uilds a lexical tree for the Esperanto sentence. There would be a back-end =
>of the program specific to each output language that converts the lexical t=
>ree into English, Spanish, etc..

That is interesting. A collegue of mine Toon Witkam had this idea of translating
into Esperanto to disambiguate natural language. It turned into a project
for the EU and earned him a doctorate, later he became professor.
The EU didn't really like it too much, at the time it was slow (80's),
but mostly they didn't want too clear language in their treatises.
That was a multi-manyear project. I don't see you pull off a similar project
without a team.

>BTW: It was Marcos Cruz who got me thinking about Esperanto --- I haven't g=
>iven any thought to that subject in almost 30 years --- at one time though,=
> I did know a little about the subject.

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]

#45936

On Monday, March 7, 2016 at 5:27:32 AM UTC-7, Albert van der Horst wrote:
> I would like to extend the analysis by the following.
> If you swap derived strings there is no problem. Only if you juggle
> a derived string under a unique string there may be problems. In both
> SWAP$ and ROT$ that can only be the case if the new string on top is
> unique. It suffices to replace the one (swap) or two (rot) strings
> by uniques if they are derived.

Well, that is a possibility. You are saying to have the juggler (SWAP$ ROT$ etc.) fix the problem. By comparison, I am leaving the problem until it really has to be fixed by a consumer or mutator.

I think that you are not considering what happens with a function such as +$ that takes two parameters rather than one. In this case, having a unique above a derivative is not a problem anyway --- +$ handles all four permutations efficiently.

Note that +$ is in my EXCEPTIONS group that don't fit in the other categories. Note also that I have a comment in my source-code mentioning that +$ was one of the most complicated functions I've ever written as a Forth programmer --- efficiency has its price!

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

#45977

On Tuesday, 8 March 2016 06:45:01 UTC, hughag...@gmail.com  wrote:
> On Monday, March 7, 2016 at 5:27:32 AM UTC-7, Albert van der Horst wrote:
> > I would like to extend the analysis by the following.
> > If you swap derived strings there is no problem. Only if you juggle
> > a derived string under a unique string there may be problems. In both
> > SWAP$ and ROT$ that can only be the case if the new string on top is
> > unique. It suffices to replace the one (swap) or two (rot) strings
> > by uniques if they are derived.
> 
> Well, that is a possibility. You are saying to have the juggler (SWAP$ ROT$ etc.) fix the problem. By comparison, I am leaving the problem until it really has to be fixed by a consumer or mutator.
> 
> I think that you are not considering what happens with a function such as +$ that takes two parameters rather than one. In this case, having a unique above a derivative is not a problem anyway --- +$ handles all four permutations efficiently.
> 
> Note that +$ is in my EXCEPTIONS group that don't fit in the other categories. Note also that I have a comment in my source-code mentioning that +$ was one of the most complicated functions I've ever written as a Forth programmer --- efficiency has its price!

Let's see how this might be done without a heap:

String space grows linearly, like dictionary space.
Unique strings are written once and once only into string space, and a reference pushed on the string stack. 
String-handling words make no distinction between unique and derived arguments.
They consume the string stack but do not reduce string space. 

String space is only reclaimed when the string stack empty. At that point it is up to the program to ensure that any unique string that is still required has already been copied elsewhere. A mechanism for named string spaces looks possible, similar to MARKER or Anton's Regions.

That would work, except that for the most papt, a unique string /is/ unique; you want it once and once only. It's fairly easy to check if the string you are about to consume is in fact the last string in string space and remove it if it is:

   S" FOO" $" BAR"  2SWAP $push $push $. $.   
    - easy To leave nothing in string space 

    S" FOO" $" BAR"  $push $push $swap $. $.
    - not so easy.  

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

#45953

On Monday, March 7, 2016 at 5:27:32 AM UTC-7, Albert van der Horst wrote:
> hughaguilar96@gmail.com writes:
> >BTW: My ultimate goal with all of this is to write a program that can trans=
> >late Esperanto into English or Spanish or whatever. I thought of this way b=
> >ack in 1984 when I was learning Esperanto. It is too difficult for a progra=
> >m to translate directly from Spanish to English or vice-versa because those=
> > language are difficult to figure out (this was true 30 years ago and is st=
> >ill true). By making the human write in Esperanto however, most of the work=
> > can be dumped on the human. Translating from Esperanto to English or Spani=
> >sh should be possible. All the Esperanto words have a suffix that tells you=
> > exactly what part of speech they are. In string-stack.4th I have functions=
> > for working with prefixes and suffixes that I provided specifically for ta=
> >king apart Esperanto words. The idea is that the front-end of the program b=
> >uilds a lexical tree for the Esperanto sentence. There would be a back-end =
> >of the program specific to each output language that converts the lexical t=
> >ree into English, Spanish, etc..
> 
> That is interesting. A collegue of mine Toon Witkam had this idea of translating
> into Esperanto to disambiguate natural language. It turned into a project
> for the EU and earned him a doctorate, later he became professor.
> The EU didn't really like it too much, at the time it was slow (80's),
> but mostly they didn't want too clear language in their treatises.
> That was a multi-manyear project. I don't see you pull off a similar project
> without a team.

I agree that I need a team --- I think that one dozen beautiful women would be adequate --- I'll do the programming!

In the meantime, I upgraded the capability of string-stack.4th a bit. I can do this now:

s" foo:=bar" >$  ok
s" :=" >$ infix$ . -1  ok
extract$  ok
.$ bar ok
.$ foo ok

INFIX$ returns a flag indicating if it found the pattern in the string. The dot gave me -1 (TRUE) so I then used EXTRACT$ to remove the infix and return the prefix and suffix that were surrounding the infix. So, I parsed a little bit of Pascal code there (in Pascal, := is an assignment). I think my string-stack.4th could be used for lexical analysis just as well as Lex is used in the C world.

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

#45954

Op Wed, 9 Mar 2016 22:27:58 -0800 (PST) schreef hughaguilar96@gmail.com:

> On Monday, March 7, 2016 at 5:27:32 AM UTC-7, Albert van der Horst wrote:
>> hughaguilar96@gmail.com writes:
>>>BTW: My ultimate goal with all of this is to write a program that can trans=
>>>late Esperanto into English or Spanish or whatever. I thought of this way b=
>>>ack in 1984 when I was learning Esperanto. It is too difficult for a progra=
>>>m to translate directly from Spanish to English or vice-versa because those=
>>> language are difficult to figure out (this was true 30 years ago and is st=
>>>ill true). By making the human write in Esperanto however, most of the work=
>>> can be dumped on the human. Translating from Esperanto to English or Spani=
>>>sh should be possible. All the Esperanto words have a suffix that tells you=
>>> exactly what part of speech they are. In string-stack.4th I have functions=
>>> for working with prefixes and suffixes that I provided specifically for ta=
>>>king apart Esperanto words. The idea is that the front-end of the program b=
>>>uilds a lexical tree for the Esperanto sentence. There would be a back-end =
>>>of the program specific to each output language that converts the lexical t=
>>>ree into English, Spanish, etc..
>> 
>> That is interesting. A collegue of mine Toon Witkam had this idea of translating
>> into Esperanto to disambiguate natural language. It turned into a project
>> for the EU and earned him a doctorate, later he became professor.
>> The EU didn't really like it too much, at the time it was slow (80's),
>> but mostly they didn't want too clear language in their treatises.
>> That was a multi-manyear project. I don't see you pull off a similar project
>> without a team.
> 
> I agree that I need a team --- I think that one dozen beautiful women would be adequate --- I'll do the programming!
> 
> In the meantime, I upgraded the capability of string-stack.4th a bit. I can do this now:
> 
> s" foo:=bar" >$  ok
> s" :=" >$ infix$ . -1  ok
> extract$  ok
> .$ bar ok
> .$ foo ok
> 
> INFIX$ returns a flag indicating if it found the pattern in the string. The dot gave me -1 (TRUE) so I then used EXTRACT$ to remove the infix and return the prefix and suffix that were surrounding the infix. So, I parsed a little bit of Pascal code there (in Pascal, := is an assignment). I think my string-stack.4th could be used for lexical analysis just as well as Lex is used in the C world.

Using strings on a heap, not a stack:

want split-text  ok
"foo:=bar"  ok
":="  ok
split-text  ok
type foo ok
type bar ok

groet, Coos

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

#45962

On Thursday, March 10, 2016 at 3:05:28 AM UTC-7, Coos Haak wrote:
> Op Wed, 9 Mar 2016 22:27:58 -0800 (PST) schreef hughaguilar96@gmail.com:
> 
> > On Monday, March 7, 2016 at 5:27:32 AM UTC-7, Albert van der Horst wrote:
> >> hughaguilar96@gmail.com writes:
> >>>BTW: My ultimate goal with all of this is to write a program that can trans=
> >>>late Esperanto into English or Spanish or whatever. I thought of this way b=
> >>>ack in 1984 when I was learning Esperanto. It is too difficult for a progra=
> >>>m to translate directly from Spanish to English or vice-versa because those=
> >>> language are difficult to figure out (this was true 30 years ago and is st=
> >>>ill true). By making the human write in Esperanto however, most of the work=
> >>> can be dumped on the human. Translating from Esperanto to English or Spani=
> >>>sh should be possible. All the Esperanto words have a suffix that tells you=
> >>> exactly what part of speech they are. In string-stack.4th I have functions=
> >>> for working with prefixes and suffixes that I provided specifically for ta=
> >>>king apart Esperanto words. The idea is that the front-end of the program b=
> >>>uilds a lexical tree for the Esperanto sentence. There would be a back-end =
> >>>of the program specific to each output language that converts the lexical t=
> >>>ree into English, Spanish, etc..
> >> 
> >> That is interesting. A collegue of mine Toon Witkam had this idea of translating
> >> into Esperanto to disambiguate natural language. It turned into a project
> >> for the EU and earned him a doctorate, later he became professor.
> >> The EU didn't really like it too much, at the time it was slow (80's),
> >> but mostly they didn't want too clear language in their treatises.
> >> That was a multi-manyear project. I don't see you pull off a similar project
> >> without a team.
> > 
> > I agree that I need a team --- I think that one dozen beautiful women would be adequate --- I'll do the programming!
> > 
> > In the meantime, I upgraded the capability of string-stack.4th a bit. I can do this now:
> > 
> > s" foo:=bar" >$  ok
> > s" :=" >$ infix$ . -1  ok
> > extract$  ok
> > .$ bar ok
> > .$ foo ok
> > 
> > INFIX$ returns a flag indicating if it found the pattern in the string. The dot gave me -1 (TRUE) so I then used EXTRACT$ to remove the infix and return the prefix and suffix that were surrounding the infix. So, I parsed a little bit of Pascal code there (in Pascal, := is an assignment). I think my string-stack.4th could be used for lexical analysis just as well as Lex is used in the C world.
> 
> Using strings on a heap, not a stack:
> 
> want split-text  ok
> "foo:=bar"  ok
> ":="  ok
> split-text  ok
> type foo ok
> type bar ok
> 
> groet, Coos

Where is this SPLIT-TEXT defined? Some code-library?

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

#45967

Op Thu, 10 Mar 2016 09:28:02 -0800 (PST) schreef hughaguilar96@gmail.com:

<snip>
> Where is this SPLIT-TEXT defined? Some code-library?

Straight high level, standard code:

: SPLIT-TEXT    ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 c-addr1 u4 )
        >r >r 2dup r> r@ search
        if      r> over >r /string 2swap r> -
        else    2drop "" 2swap rdrop
        then
    ;

Where "" could be defined as : "" 0 0 ;
You might use 2SWAP afterwards if the the second part must be on top.
I use this to generate html from my glossary files.

groet Coos

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

#45971

On Thursday, March 10, 2016 at 4:10:41 PM UTC-7, Coos Haak wrote:
> Op Thu, 10 Mar 2016 09:28:02 -0800 (PST) schreef hughaguilar96@gmail.com:
> 
> <snip>
> > Where is this SPLIT-TEXT defined? Some code-library?
> 
> Straight high level, standard code:
> 
> : SPLIT-TEXT    ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 c-addr1 u4 )
>         >r >r 2dup r> r@ search
>         if      r> over >r /string 2swap r> -
>         else    2drop "" 2swap rdrop
>         then
>     ;
> 
> Where "" could be defined as : "" 0 0 ;

The problem I notice immediately is that c-addr3 points to inside of a memory-block on the heap --- if you use FREE on this, it will fail --- how do you keep track of which strings can be given to FREE and which can not?

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

#45975

Op Thu, 10 Mar 2016 22:42:09 -0800 (PST) schreef hughaguilar96@gmail.com:

> On Thursday, March 10, 2016 at 4:10:41 PM UTC-7, Coos Haak wrote:
>> Op Thu, 10 Mar 2016 09:28:02 -0800 (PST) schreef hughaguilar96@gmail.com:
>> 
>> <snip>
>>> Where is this SPLIT-TEXT defined? Some code-library?
>> 
>> Straight high level, standard code:
>> 
>>: SPLIT-TEXT    ( c-addr1 u1 c-addr2 u2 -- c-addr3 u3 c-addr1 u4 )
>>         >r >r 2dup r> r@ search
>>         if      r> over >r /string 2swap r> -
>>         else    2drop "" 2swap rdrop
>>         then
>>     ;
>> 
>> Where "" could be defined as : "" 0 0 ;
> 
> The problem I notice immediately is that c-addr3 points to inside of a memory-block on the heap --- if you use FREE on this, it will fail --- how do you keep track of which strings can be given to FREE and which can not?

No problem, I can type the string or concatenate two strings.

do-debug  ok
( ) "foo:=bar" ":=" split-text  ok
( "bar" "foo" ) ":=" strcat  ok
( "bar" "foo:=" ) 2swap  ok
( "foo:=" "bar" ) strcat  ok
( "foo:=bar" ) type foo:=bar ok
The strings live in a circular heap.
strcat ensures (by strdup) that the first string is placed at the end
of the string pointer so it can add the second to its end.
This also works for strings outside the heap e.g. in colon definitions.
It speaks for itself that the length of the strings is on the
stack, not between the strings like the old counted strings.

groet Coos

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web