Sequences

[The Beez]

Hi 4tH-ers!

I think this may be a bit controversial, but I've added Factor-like style sequences as well. But there are a few significant differences here:

- Sequences are completely standalone. You don't have to (implicitly or explicitly) import the Factor combinators to make it work;

- Where the goal of the Factor combinators was to use as little Forth primitives as possible and turn to the Factor kernel code as fast as we could, this doesn't hold a single but of Factor code. It's all designed from scratch;

- This is only a tiny implementation. Most words that create new sequences out of others simply aren't there.

But a few remarks are needed as well:

- Factor has GC. This implementation has not. If you allocate a sequence, you WILL have to free it at one point or another;

- This is not a "light" library. It takes a significant amount of code (about 800 words), about as much as a small FP library;

- Frankly, I don't have an idea how useful it will actually be. It may be of use when creating initialized (but writable) data, set processing, etc. I don't see it appearing much in other libraries - unless e.g. set processing libraries. I see it foremost as an application library;

- Of course, this kind of "cooked" fancy datatypes tend to be slower than "raw" arrays

On the functionality side, I don't think there's much wrong with it:

- You can make integer sequences, string sequences and sequences of sequences (up to about eight levels deep). You CAN'T make mixed integer/string/sequences - well, not out of the box;

- You can resize or shrink sequences;

- You can search sequences;

- You can apply high order functions like EACH, MAP, REDUCE;

- You can define ranged sequences (IOTA).

I may implement more specialized function later. First see if it is of any use. Anyway, it you want to play with it - or if you're just curious, code is in SVN.

https://sourceforge.net/p/forth-4th/code/1335/

Yes, I guess, it's out of my system now. ;-)

Hans Bezemer

[Ron K. Jeffries]

Showing my (profound!) ignorance: any chance you might share a few examples of using this feature?

---
Ron K. Jeffries

805-380-5446 mobile

--
You received this message because you are subscribed to the Google Groups "4tH-compiler" group.
To unsubscribe from this group and stop receiving emails from it, send an email to 4th-compiler...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/4th-compiler/4a45e93c-5354-4b92-a964-8db2c23aa45en%40googlegroups.com.

[The Beez]

Hi Ron!

Of course! This is the article I've written for the manual:

Sequences

A sequence is a set of integers, strings or other sequences, which are packed into a dynamic array. Creating sequences is quite easy, e.g.

include lib/sequence.4th

    

{ 1 2 4 8 16 32 64 128 256 }

{ s" Hello" s" world" s” !" }s

Note that sequences are created in dynamic memory - so you will have to free them at one time or another. It also means, that the previous example left two pointers on the stack: one for the string sequence and one for the integer sequence.

You can free integer sequences with ”FREE”, but you'll have to free a string sequence with ”SFREE”. Remember that, because I don't want you to leak memory all over the place! There is another way to create a sequence:

5 iota

Which will create a sequence with the numbers 0 up to 4. If you choose another number it will create a sequence from 0 unto that number. Don't forget that before these numbers are turned into a sequence, they are stored on the stack. If you make your sequences too large you will most likely exceed the stack capacity.

Now we got that all out of the way, what can you do with a sequence? Well, you can perform actions on them. This one will print out all the numbers of the sequence:

{ 9 8 7 6 5 4 3 2 1 0 } dup [: . ;] each cr

free abort" Cannot free sequence"

It is as if every value in this sequence is input to the quotation, which issued to ”EACH”. Hence, that value is printed. We can step up our game and use ”MAP!” - which not only accesses the value, but writes back the result which is left after executing the quotation:

5 iota dup [: dup * ;] map! 

dup [: . ;] each cr

free abort" Cannot free sequence"

Ok, this gets complex, let's break it down:

• ”IOTA” produces a sequence with the numbers 0, 1, 2, 3 and 4;
• Each of this values is offered to the ”DUP *” quotation, which produces the results 0, 1, 4, 9 and 16;
• These values are written back to the sequence, replacing the original numbers;
• Now the sequence is offered to ”EACH” - which prints these numbers;
• And finally, the sequence is freed.

And finally, there is ”REDUCE!”. This word required a value on the stack and applies the quotation to each value and the value on the stack. Hence, this quotation requires two values. This one returns the sum of all the values in the sequence:

5 iota dup 0 [: + ;] reduce!

dup [: . ;] each cr

free abort" Cannot free sequence"

So, the first time the quotation is encountered, there is a zero on the stack and a zero value - which is added and amounts to zero. The second time there is a zero on the stack and a value ”1” - which is added and amounts to ”1”. The third time there is a ”1” on the stack and a value ”2” - which is added and amounts to ”3”. You catch my drift..

If you want to access a specific value, you can. It's not much different from accessing an array, as a matter of fact:

5 iota dup 3 nth ? cr

free abort" Cannot free sequence"

Note ”NTH” doesn't return a value, but an address - if not it would be quite difficult to store a value there. Like ”TH” indexes, ”NTH” indexes start at zero. So in this case the value ”3” would be displayed.

You can also search sequences. If you're looking for exact matches, ”INDEX” is your man:

5 iota 3 over index

stow nth ? cr

free abort" Cannot free sequence"

This one will - of course - return ”3”. If the index returned is bigger of equal to the length of a sequence, the value was not found. If you need something more sophisticated, you might try ”FIND”. This word simply applies a quotation to each value - and the first one that renders true is the winner:

{ 9 8 7 6 5 4 3 2 1 0 } dup [: 5 < ;] find

stow nth ? cr

free abort" Cannot free sequence"

So, this one returns ”4” - which is the first number smaller than ”5”. Now, I know there is one question left to answer: how do I get the length of a sequence? That 's easy:

5 iota dup length . cr

free abort" Cannot free sequence"

That's how you get the length of a sequence. If you're not happy with the length, you can set it according to your wishes. If you increase the length, additional elements are added at the end, if you decrease the length, elements are removed from the end:

{ 9 8 7 6 5 4 3 2 1 0 } 4 set-length

dup length . cr

free abort" Cannot free sequence"

This poor sequence now consists of the elements ”9”, ”8”, ”7” and ”6”. Note that ”SET-LENGTH” actually destroys your sequence and creates a new one - so it returns the address of your new sequence, while the address of your old sequence is invalidated. 

And this is a demo program:

include sequence.4th

[ASSERT]

{ } dup empty? . free . cr             \ empty sequence - and freed

." -----" cr

                                       \ iota sequence squared and shown

5 iota dup dup [: dup * ;] map! [: . ;] each cr

free drop                              \ and freed

assert( depth 0= )

." -----" cr

                                       \ string sequence, shown and freed

{ s" Hello" s"  world" s" !" }s dup

dup [: count type ;] each

2 nth ds.count type cr                 \ return the second element address

sfree drop

assert( depth 0= )

." -----" cr

                                       \ iota sequence reduced

5 iota dup dup 0 [: + ;] reduce! . cr  \ while "sum" does the same thing

sum . cr

free drop

assert( depth 0= )

." -----" cr

                                       \ create a sequence and

{ 9 8 7 6 5 4 3 2 1 0 } dup dup dup [: 5 < ;] find nth ? cr

3 over index nth ? cr                  \ search it both ways

free drop

assert( depth 0= )

." -----" cr

{ 9 8 7 6 5 4 3 2 1 0 } 4 set-length   \ clip a sequence

dup [: . ;] each cr                    \ show the result

free drop

assert( depth 0= )

." -----" cr

: factorial ( n -- seq n! ) iota dup 1 [: 1 + * ;] reduce! ;

9 factorial . cr

free drop

assert( depth 0= )

." -----" cr

                                       \ safely access first and last

{ 2 3 4 } dup ?first ?                 \ elements

dup ?last ?

free drop

{ } dup ?first . cr                    \ this fails and returns false

free drop

assert( depth 0= )

." -----" cr

                                       \ sequence within sequence

: seq.free dup [: free E.LIBERR throw" Cannot free sequence" ;] each free ;

                                       \ can't just FREE this one

{ { 1 2 } { 3 4 } { 5 6 } { 7 8 } } dup

[: [: . ;] each cr ;] each

seq.free drop

assert( depth 0= )

Like I said - if or in what situations it can be useful - I dunno. Note I've once written the LEAF.4TH library for database indexes. Later I found out I didn't need it. But it became invaluable when making the ini-file manager. I never throw away useful code. At one time or another it may prove to be just what one needed.

I hope this answers your question..

Hans Bezemer

[Ron K. Jeffries]

Very helpful.  Thank you!

Ron K Jeffries 

@rokjeffries

To view this discussion on the web visit https://groups.google.com/d/msgid/4th-compiler/e705d828-15da-4a2f-8bfb-8e740835b20dn%40googlegroups.com.