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

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

Reverse a string (with xchars)

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

Contents

  Reverse a string (with xchars) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-19 09:00 +0000
    Re: Reverse a string (with xchars) mentificium@gmail.com - 2016-02-20 23:44 -0800
    Re: Reverse a string (with xchars) Chris Curl <ccurl609@gmail.com> - 2016-02-21 10:18 -0800
      Re: Reverse a string (with xchars) Chris Curl <ccurl609@gmail.com> - 2016-02-21 10:24 -0800
        Re: Reverse a string (with xchars) Chris Curl <ccurl609@gmail.com> - 2016-02-21 10:35 -0800
          Re: Reverse a string (with xchars) Paul Rubin <no.email@nospam.invalid> - 2016-02-21 12:07 -0800
            Re: Reverse a string (with xchars) Chris Curl <ccurl609@gmail.com> - 2016-02-21 12:40 -0800
              Re: Reverse a string (with xchars) Paul Rubin <no.email@nospam.invalid> - 2016-02-21 12:50 -0800
              Re: Reverse a string (with xchars) Paul Rubin <no.email@nospam.invalid> - 2016-02-21 12:56 -0800
                Re: Reverse a string (with xchars) Chris Curl <ccurl609@gmail.com> - 2016-02-21 14:43 -0800
                  Re: Reverse a string (with xchars) Paul Rubin <no.email@nospam.invalid> - 2016-02-21 14:59 -0800
                    Re: Reverse a string (with xchars) Chris Curl <ccurl609@gmail.com> - 2016-02-21 16:55 -0800
                Re: Reverse a string (with xchars) Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-22 09:37 +0000

#45615 — Reverse a string (with xchars)

The Rosettacode task posted recently was actually
<http://www.rosettacode.org/wiki/Reverse_words_in_a_string>, but there
is also <http://www.rosettacode.org/wiki/Reverse_a_string>, which
reverses the string character-by-character.  There are Forth-94
solutions given there, but with 8-bit or 16-bit characters, these
cannot handle Unicode.

The task is interesting because it is one of the few cases where we
actually need to do something special when dealing with UTF-8, i.e.,
where we actually need words from the xchars wordset for dealing with
UTF-8 (in most other cases, the Forth-94 words are sufficient).

Here's my solution:

\ Has an environmental dependency on 1 chars=1.

\ The xchars wordset offers several ways to skin this cat; I use one,
\ but a different one may be better.

: xreverse {: c-addr u -- c-addr2 u :}
    u allocate throw u + c-addr swap over u + >r begin ( from to r:end)
	over r@ u< while
	    over r@ over - x-size dup >r - 2dup r@ cmove
	    swap r> + swap repeat
    r> drop nip u ;

\ Test case
s" ώщыē" xreverse type

The task description says: "For extra credit, preserve Unicode
combining characters."  Combining characters consist of several code
points; e.g., "ü" is a precomposed character and has one code point,
but could also be encoded in a decomposed way as a "u" followed by the
combining diacritic character U+308 "diaresis".  Because the current
version reverses the code points, it does not work correctly for
decomposed characters.

What is missing from xchars for the extra credit is a way to recognize
combining characters.

While I am at it: a word for validating and normalizing UTF-8 input
would also be a good idea (or split these tasks into several words?).

- 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 2015: http://www.rigwit.co.uk/EuroForth2015/

[toc] | [next] | [standalone]

#45651

On Friday, February 19, 2016 at 1:29:40 AM UTC-8, Anton Ertl wrote:
> The Rosettacode task posted recently was actually
> <http://www.rosettacode.org/wiki/Reverse_words_in_a_string>, but there
> is also <http://www.rosettacode.org/wiki/Reverse_a_string>, which
> reverses the string character-by-character.  There are Forth-94
> solutions given there, but with 8-bit or 16-bit characters, these
> cannot handle Unicode.
> 
> The task is interesting because it is one of the few cases where we
> actually need to do something special when dealing with UTF-8, i.e.,
> where we actually need words from the xchars wordset for dealing with
> UTF-8 (in most other cases, the Forth-94 words are sufficient).
> 
> Here's my solution:
> 
> \ Has an environmental dependency on 1 chars=1.
> 
> \ The xchars wordset offers several ways to skin this cat; I use one,
> \ but a different one may be better.
> 
> : xreverse {: c-addr u -- c-addr2 u :}
>     u allocate throw u + c-addr swap over u + >r begin ( from to r:end)
> 	over r@ u< while
> 	    over r@ over - x-size dup >r - 2dup r@ cmove
> 	    swap r> + swap repeat
>     r> drop nip u ;
> 
> \ Test case
> s" ώщыē" xreverse type
> 
> The task description says: "For extra credit, preserve Unicode
> combining characters."  Combining characters consist of several code
> points; e.g., "ü" is a precomposed character and has one code point,
> but could also be encoded in a decomposed way as a "u" followed by the
> combining diacritic character U+308 "diaresis".  Because the current
> version reverses the code points, it does not work correctly for
> decomposed characters.
> 
> What is missing from xchars for the extra credit is a way to recognize
> combining characters.
> 
> While I am at it: a word for validating and normalizing UTF-8 input
> would also be a good idea (or split these tasks into several words?).
> 
> - 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 2015: http://www.rigwit.co.uk/EuroForth2015/

I did not know that Forth could handle UTF-8 and Unicode. 

I am trying to translate 

http://www.nlg-wiki.org/systems/Mind.Forth into 

http://ai.neocities.org/perlmind.txt (Perl artificial intelligence) 

as an AI that shall use Unicode to think in 
English, German and Russian but the Unicode 
is very difficult for me to get a grip on. 

I am setting up a MindBoot sequence with 
English at timepoints 0 to 651 (up to 999);
Russian at timepoints 1001 to 1577 (up to 1999); and 
German at timepoints 2001 to 3215 (and beyond). 

I appreciate the above post about Forth Unicode. 

- arthur 
-- 
http://ai.neocities.org/P6AI_FAQ.html 
http://ai.neocities.org/P6AI_man.html 
http://ai.neocities.org/AiSteps.html 
http://ai.neocities.org/PMPJ.html

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

#45654

On Friday, February 19, 2016 at 4:29:40 AM UTC-5, Anton Ertl wrote:
\ reverse a string in place
: str.reverse ( addr -- )
	count over + 1-			( start end )
	begin
		2dup >			( start end bool )
		if 2drop exit then	( start end )
		over c@ over c@		( start end start-ch end-ch )
		3 pick c!		( start end start-ch )
		over c!			( start end )
		1- swap 1+ swap		( new-start new-end )
	again
	;

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

#45655

I know that doesn't address the question ... all it does is reverse a 
counted string in place. i'll start the wheels in the back of my head 
turning on the other thing.

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

#45657

I guess I'm having a hard time understanding what the difficulty is.

Since each unicode UTF-16 character is 2 bytes instead of 1, why wouldn't something 
like this work?

\ reverse a UTF-16 string in place
: str.reverse.UTF-16 ( addr -- )
	count over + 2 -		( start end )
	begin
		2dup >			( start end bool )
		if 2drop exit then	( start end )
		over 16@ over 16@	( start end start-ch end-ch )
		3 pick 16!		( start end start-ch )
		over 16!		( start end )
		2- swap 2+ swap		( new-start new-end )
	again
	;

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

#45658

Chris Curl <ccurl609@gmail.com> writes:
> Since each unicode UTF-16 character is 2 bytes instead of 1, why
> wouldn't something like this work?

UTF-16 is a variable length encoding, like UTF-8.  Remember there are
more than a million Unicode code points.  So you can't always specify
one with 2 bytes.  Plus as Anton says, there is the issue of composing
characters:

  https://en.wikipedia.org/wiki/Unicode_normalization

That means certain characters with diacritics have multiple encodings
some of which use more than one code point, and you have to handle
reversing them.

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

#45659

fine. no problem. but i don't have time to code it up right now.

the idea is to pull each char from the source string on an auxiliary stack, 
starting at the beginning, parsing each char for code points. 

each "char" on the aux stack would have the number of bytes needed, followed 
by the actual bytes. 'A' would be (65 00 02 <-- TOS). a coded char would look 
like this: (30 03 65 00 04) or whatever.

that results in a stack with the last char on the top and the first char on 
the bottom.

then you pull the "chars" off the aux stack and build the string front to back.

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

#45660

Chris Curl <ccurl609@gmail.com> writes:
> the idea is to pull each char from the source string on an auxiliary stack, 
> starting at the beginning, parsing each char for code points. 

Yes.  For the word-reversing example, Anton posted some nice code using
the data stack and RECURSE.  

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

#45661

Chris Curl <ccurl609@gmail.com> writes:
> each "char" on the aux stack would have the number of bytes needed,
> followed by the actual bytes. 'A' would be (65 00 02 <-- TOS). a coded
> char would look like this: (30 03 65 00 04) or whatever.

Actually you don't need that overhead.  You can just build up an array
in forward order, but reverse the encoded bytes for each character.  So
if the encoding is (30 03 64 00) then you'd write (00 64 03 30).  After
doing this with all the chars, you'd scan the array backwards, parsing
the encodings from the reversed stream.  In fact you can do this in
place, with no auxiliary storage other than a few bytes to read a single
encoding and reverse it.

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

#45664

On Sunday, February 21, 2016 at 3:56:08 PM UTC-5, Paul Rubin wrote:
> Chris Curl <ccurl...com> writes:
> > each "char" on the aux stack would have the number of bytes needed,
> > followed by the actual bytes. 'A' would be (65 00 02 <-- TOS). a coded
> > char would look like this: (30 03 65 00 04) or whatever.
> 
> Actually you don't need that overhead.  You can just build up an array
> in forward order, but reverse the encoded bytes for each character.  So
> if the encoding is (30 03 64 00) then you'd write (00 64 03 30).  After
> doing this with all the chars, you'd scan the array backwards, parsing
> the encodings from the reversed stream.  In fact you can do this in
> place, with no auxiliary storage other than a few bytes to read a single
> encoding and reverse it.

The thing is ... a character may have more than one modifier, so for 
chars that have >1, don't you need a way to keep the char and its 
modifiers in the proper order? Perhaps what you are saying does that,
I may just not be seeing it yet.

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

#45665

Chris Curl <ccurl609@gmail.com> writes:
> The thing is ... a character may have more than one modifier, so for 
> chars that have >1, don't you need a way to keep the char and its 
> modifiers in the proper order? Perhaps what you are saying does that,
> I may just not be seeing it yet.

I don't think there can be unlimited numbers of modifiers, in fact
I thought there was at most 1.  It doesn't matter, you can do all
the reversals in place.  Algorithm:

  let p = start of buffer
  Until you reach the end of the buffer:
    scan forward from p til you reach the end of the end of
      the char including any modifiers
    let q = current position
    reverse the bytes in the range from p to q
    let p = q
  ( p now points to the end of the buffer )
  reverse bytes from start of buffer to p

So you've done the whole thing in place with no auxiliary buffers,
just a few temp variables for the loops and swaps.

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

#45666

On Sunday, February 21, 2016 at 5:59:33 PM UTC-5, Paul Rubin wrote:
> I don't think there can be unlimited numbers of modifiers, in fact
> I thought there was at most 1.
yeah, the spec says there can be more than one modifier.

> It doesn't matter, you can do all
> the reversals in place.  Algorithm:
> 
>   let p = start of buffer
>   Until you reach the end of the buffer:
>     scan forward from p til you reach the end of the end of
>       the char including any modifiers
>     let q = current position
>     reverse the bytes in the range from p to q
>     let p = q
>   ( p now points to the end of the buffer )
>   reverse bytes from start of buffer to p
> 
> So you've done the whole thing in place with no auxiliary buffers,
> just a few temp variables for the loops and swaps.
that works ... :)

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

#45669

Paul Rubin <no.email@nospam.invalid> writes:

>Chris Curl <ccurl609@gmail.com> writes:
>> each "char" on the aux stack would have the number of bytes needed,
>> followed by the actual bytes. 'A' would be (65 00 02 <-- TOS). a coded
>> char would look like this: (30 03 65 00 04) or whatever.

>Actually you don't need that overhead.  You can just build up an array
>in forward order, but reverse the encoded bytes for each character.  So
>if the encoding is (30 03 64 00) then you'd write (00 64 03 30).  After
>doing this with all the chars, you'd scan the array backwards, parsing
>the encodings from the reversed stream.  In fact you can do this in
>place, with no auxiliary storage other than a few bytes to read a single
>encoding and reverse it.

Very nice!
-- 
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] | [standalone]

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

csiph-web