Tutorial: Arrays in Forth

[Willsy]

It's fine - I don't think it's nit-picking. Brian's use of the term 'array' is also applicable, since the implementation gives random access to the strings (by walking the list) - so it could be argued that, at least from a users point of view, it's an array. Implementation wise, it's a list.  It's all good !

[Willsy]

Ha! I just noticed I started this thread in 2017!!!!

[GDMike]

2 hours ago, Willsy said:

Ha! I just noticed I started this thread in 2017!!!!

Yup. And I've never seen this!! I picked up on something regarding loading DF80 object code here. This is really cool.

[+TheBF]

5 hours ago, apersson850 said:

What you are doing here isn't a string array, though, but a list containing strings. An array does allow random access of any item inside, without having to traverse the list first.

 

If you want to both have a flexible memory usage and be able to replace a string, the typical approach in a language like Pascal is to use a linked list. Then each data item contains a string as well as a pointer.

For this to be truly flexible, you need to keep track of the string, the pointer to the next string and the number of words allocated to each variable.

In UCSD Pascal, they are created by varnew, a command which allocates any number of words on the heap. To release the memory, you must use vardispose. So this is similar to using the standard functions new and dispose, except that the first pair allows the number of words allocated to be undetermined at compile time.

 

Takes more time to handle, of course, but if memory is at a premium, it may still be worth it. And by handling the pointers, you can delete a string in the list, insert a string and, combining both, replace a string with one of a different length.

Point taken on this being a list not an array.   It was a mental diversion to distract me from my coughing.   

 

Linked lists are very cool and flexible but coding in a tiny environment for specific needs they might be needless complication.

It would be perfectly acceptable to use a computed address for each string in the array for fixed sizes in simple cases if that's all one needed.

 

To atone for my sins I will make a version that is more analogous to the C example with computed addresses of fixed length strings.

 

As I write this I realize that in the traditional Forth systems with BLOCK based disk systems the common way to do this was to allocate some disk blocks to hold the strings and compute block number and offset with the /MOD operator.

This allowed strings "arrays" to be the size of the entire disk system with one definition.  Since the BLOCK system is virtual memory, performance was reasonable and you can add more buffers if you need them.

In fact the error message system used this technique.  Typical of how Chuck Moore removed complexity.

 

(Verbose constant names used to explain the purpose)

   64 CONSTANT MAX_STRING_LENGTH
1024 CONSTANT BYTES_PER_BUFFER

:  RECORD ( n -- addr)    MAX_STRING_LENGTH  *   BYTES_PER_BUFFER  /MOD ( -- addr rem)  BLOCK + ;  

 

But now you have "gone and done it"  @apersson850 as they say the USA.  

Now I have to see what it would take to make arrays that are lists of pointers to strings.

I am betting the code is about 100X more complicated than Chuck's solution in the example above.  

 

Edited January 28, 2022 by TheBF
TYPO

[+Lee Stewart]

What allows true random access to arrays is that the array elements have constant width—easy and efficient with numbers. This permits calculation of an element’s position as well as value replacement. As has already been discussed, creating an array of strings, with each element set at the maximum string length (for the given array), may be easy enough but certainly not efficient. To allow random access to an array of any-length strings, without requiring walking a list, could be accomplished with an array of pointers to (addresses of) strings. This would allow the strings to be scattered about memory and would allow replacement. Of course, when the replacement is a larger string, the replaced string’s memory is lost unless there is also a memory manager for the process (yet more “wasted” space).

 

[Edit: I see I am being a bit redundant: (from @TheBF’s last post: “Now I have to see what it would take to make arrays that are lists of pointers to strings.”)]

 

...lee

[apersson850]

Yes, an array of pointers allow for random access pretty fast. It also makes operations like sorting more efficient, since you don't have to move around data, just the pointers.

Recovering lost memory either has to be done with some kind of garbage collection, which can use an algorithm that can be applied at any time, or by some special management of free space. Like markin it with a character that's illegal in a valid string.

A third possibility is the p-system's mark and release. There you store a memory address before you allocate the data. If you don't need it any longer, you release back to the mark, and then all that memory is free again.

 

I've actually used a four-way linked list in a real project, i.e. not just some programming experiment.

You should also realize that the use of linked lists, albeit adding complexity to the data itself, if well thought out may allow for the data processing to be simplified in such a way that you save memory from having a simpler code. Like recursive processing, which works very well in stack based environments.

Edited January 28, 2022 by apersson850

[+TheBF]

I sat down tonight to look into this a bit more and it's clear why Chuck Moore didn't mandate fancy data structures in the core language.

The simplest array of strings is created with almost nothing and in some ways is handier to use than simple C strings because they are counted not zero terminated.

 

\ simplest string arrays. Calculated addresses. No protection. Bare bones 
CREATE Q$  32 20 * ALLOT

: ]Q$  ( ndx -- addr) 32 * Q$ + ;

In an embedded application this may be all you ever need. 

S" Now we can assign strings" 0 ]Q$ PLACE

 

You can put some "lipstick" on these if you needed to:  

\ fancier: Remember the size and number of strings in the array itself
\ create operators for this kind of array
: STRINGS:  ( len # )
  CREATE  2DUP  ,   ,   *  ALLOT   \ compile time: remember the parameters
  
  DOES> 2 CELLS + ;                \ runtime: skip past the parameters
                                   \ returns the base address of the array

: LEN[]    ( addr -- len) 1 CELLS - @ ;
: MAX[]    ( addr --  n)  2 CELLS - @ ;
: ERASE[]  ( addr -- )  2@ * 0 FILL ;

\ address calculator
: []    ( ndx addr -- addr') TUCK LEN[] * + ;

64 20 STRINGS: X$
S" These are a little more verbose." 0 X$ [] PLACE
S" But they do the job" 1 X$ [] PLACE
S" Note: These strings reside in CPU RAM"      2 X$ [] PLACE
S" But we can use other memory spaces as well" 3 X$ [] PLACE

 

Creating an array of pointers with string addresses will require a way to dynamically create a string in memory and assign the pointer to an integer array.

Forth doesn't have that.  Instead it has the components to make that.  These of course are static strings in this example.

If we wanted fancier we would have to use ANS/ISO  ALLOCATE  FREE RESIZE . 

And if we needed garbage collection we would have to build it or find a library and adapt it for for TI-99.

The cool thing about these pointer based arrays is the strings could be allocated in VDP RAM or SAMS memory or even disk based virtual memory with the pointer arrays in RAM.

 

\ allocate strings on the fly and assign to an array
INCLUDE DSK1.ARRAYS

32 ARRAY Y$   \ normal integer array
: ERASE  ( addr n -- ) 0 FILL ;

0 Y$ 32 CELLS ERASE  \ init pointers to 0

\ compile a string into memory and return it's address
: $"     ( -- addr)  HERE  [CHAR] " PARSE  S,  ;

$" This string can be of any length up to 255 characters"  0 Y$ !
$" Each string must be stored in the Y$ array of pointers"  1 Y$ !
$" Notice that to assign the string we use the integer store operator"  2 Y$ !
$" To read these strings we use the 'fetch' operator '@' to deference the pointer" 3 Y$ !

: WRITE$   ( addr -- ) @  COUNT  CR TYPE ;

: .Y     4 0 DO  I Y$ WRITE$   LOOP ;

That's all I got for now.  Not nearly as fancy as USCD Pascal but then again we are writing in the extensible assembly language for a 2 stack virtual machine. 

So for that level of language it's not too shabby.  

 

 

 

[apersson850]

It's all about what you value most.

Forth is fast and efficient, which makes it effective at runtime, even on low spec hardware.

The advanced data structures available in Pascal makes software development and maintenance easier. The cost is a bit lower performance at runtime. Mainly speedwise, since the UCSD p-system was developed when memories were small and is therefore pretty advanced when it comes to memory management. Something you have already seen, if you read my previous posts about the internal workings of the p-system.

 

When I ramped up my use of the 99/4A, Forth was not yet available. I did a little in BASIC, then quickly moved to Extended BASIC, to get more value from the system.

Tape recorder storage became too limited, so I moved on to expansion box, which I then equipped with everything then available (memory, RS232, disk system and p-code card). From that time, I did all work with the p-system, unless there was a need for it to be useful for people with less equipped machines too.

Thus I learned how to use it well, what was fully doable in Pascal and how to support with assembly, for the things that were too slow. Like sorting a thousand integers in less than half a second.

When Forth became available, and then I used what we called PB Forth (Programbiten Forth), a version developed in Sweden from TI Forth, I found it interesting, but not as well structured for software development as the p-system. I also noticed that execution time was less of an issue compared to development time for me. And Pascal excelled in development support and structure.

 

As a side note, I think PB Forth was the first Forth version for the TI that allowed loading from tape. Thus it was enough with a memory expansion to run it.

 

Nowadays, when I maintain software for more than a decade, software with tens of thousands of code lines, at work, I do appreciate tools that allow easy development and maintenance of the code itself more than utmost execution speed. With today's hardware, the latter is usually good enough anyway.

[atrax27407]

Wycove Forth allowed loading from tape and was the first independently developed FORTH after the release of TI Forth. I still use it from time to time albeit from disk these days.

[+TheBF]

 

7 hours ago, apersson850 said:

It's all about what you value most.

Forth is fast and efficient, which makes it effective at runtime, even on low spec hardware.

The advanced data structures available in Pascal makes software development and maintenance easier. The cost is a bit lower performance at runtime. Mainly speedwise, since the UCSD p-system was developed when memories were small and is therefore pretty advanced when it comes to memory management. Something you have already seen, if you read my previous posts about the internal workings of the p-system.

 

When I ramped up my use of the 99/4A, Forth was not yet available. I did a little in BASIC, then quickly moved to Extended BASIC, to get more value from the system.

Tape recorder storage became too limited, so I moved on to expansion box, which I then equipped with everything then available (memory, RS232, disk system and p-code card). From that time, I did all work with the p-system, unless there was a need for it to be useful for people with less equipped machines too.

Thus I learned how to use it well, what was fully doable in Pascal and how to support with assembly, for the things that were too slow. Like sorting a thousand integers in less than half a second.

When Forth became available, and then I used what we called PB Forth (Programbiten Forth), a version developed in Sweden from TI Forth, I found it interesting, but not as well structured for software development as the p-system. I also noticed that execution time was less of an issue compared to development time for me. And Pascal excelled in development support and structure.

 

As a side note, I think PB Forth was the first Forth version for the TI that allowed loading from tape. Thus it was enough with a memory expansion to run it.

 

Nowadays, when I maintain software for more than a decade, software with tens of thousands of code lines, at work, I do appreciate tools that allow easy development and maintenance of the code itself more than utmost execution speed. With today's hardware, the latter is usually good enough anyway.

Indeed every language has strengths. The P-code system's comprehensive feature set is very impressive on the TI-99. There is really nothing that comes close that I know of.

The time I spent (4 years) maintaining and upgrading a significant Turbo Pascal project was very enjoyable.

I just remembered that back in the 1980s I had a "centerfold" from Byte Magazine of a Pascal program printout laid out on a red satin sheet (a la Playboy magazine) hanging in my locker at work.  

So I was a Pascal fan back in those days.

 

My opinion on Forth is that one should never program in Forth.

It's extensible like LISP so the first order of business is to make the intermediate language that will allow you to build the application. This makes it harder in the beginning and easier (if you do it well) later.

IMHO one should borrow any great feature from other languages that wlll get the job done. But that's just my style. 

 

*QUESTION*

"Like sorting a thousand integers in less than half a second."

 

What sorting algorithm did you use for this? 

I have a quicksort here in Forth  (unoptimized) from Rosetta code that takes 4.4 seconds on a reversed order set and 8 seconds on an empty set with only 2 integers in it which seems to be the worst case.

 

Apologies to @GDMike  for stealing the thread. 

 

I used to be confused but now I am not sure

 

[apersson850]

3 hours ago, TheBF said:

"Like sorting a thousand integers in less than half a second."

 

What sorting algorithm did you use for this? 

I have a quicksort here in Forth  (unoptimized) from Rosetta code that takes 4.4 seconds on a reversed order set and 8 seconds on an empty set with only 2 integers in it which seems to be the worst case.

I used Quicksort too, with insertion sort to finish off the last subsegments. Quicksort itself isn't efficient on short lists.

My algorithm also removes the recursion, for higher efficiency. Half a second is some average for randomly ordered arrays. It's least efficient if the array is already sorted.

Do you want to see it?

 

I can add that I turned on the old machine and ran a test. Generating 1000 random numbers (floating point), converting them to integers and storing them in an array took 90 seconds. In Pascal. Sorting the same array took 0.25 seconds, or so. Varies slightly between attempts.

Sorting an already reverse ordered array took 1.5 seconds.

I tried to run the test on a sorted array too, but it turned out that benchmark program needs some fix to run. Didn't bother edit and recompile now.

Edited January 31, 2022 by apersson850

[+TheBF]

12 minutes ago, apersson850 said:

I used Quicksort too, with bubble sort to finish off the last subsegments. Quicksort itself isn't efficient on short lists.

My algorithm also removes the recursion, for higher efficiency. Half a second is some average for randomly ordered arrays. It's least efficient if the array is already sorted.

Do you want to see it?

I thought you would never ask.

Yes please

[apersson850]

Keeping you waiting, huh? ?

 

This was written in 1983. My knowledge of the innards of the p-system wasn't too good back then. Some things would have been done differently today. But the main algorithm is there. You can use this to sort integers under any language.

Here it is. The sorting subprogram, that is.

Spoiler

         .NARROWPAGE
         .PAGEHEIGHT 72
         .TITLE "QUICKSORT FOR INTEGERS"
         
;Procedure sorting integers in ascending order
;Called from Pascal host by QSORT(A,N);
;Declared as PROCEDURE QSORT(VAR A:VECTOR; N:INTEGER); EXTERNAL;
;Vector should be an array [..] of integer;

;--------------
;Workspace registers for subroutine at START
;
;R0  Array base pointer
;R1  Array end pointer
;R2  L
;R3  R
;R4  I
;R5  J
;R6  KEY
;R7  Temporary
;R8  Temporary
;R9  Subfile stack pointer
;R10 Main stackpointer
;R11 Pascal return address (P-system WS)
;R12 Not used
;R13 Calling program's Workspace Pointer
;R14 Calling program's Program Counter
;R15 Calling program's Status Register
;-----------------

;The actual vector in the Pascal-program could be indexed [1..n]
;This routine assumes only that n indicates the number of elements, not the
;last array index.


         .RELPROC  QSORT,2
LIMIT    .EQU    16              ;Quick- or Insertionsort limit
         
         BLWP @SORTING
         AI   R10,4              ;Simulate pop of two words
         B    *R11               ;Back to Pascal host

SORTING  .WORD  SORTWS           ;Transfer vector for Quicksort
         .WORD  START
         
START    MOV  @14H(R13),R10      ;Get stackpointer from calling program's WP
         LI   R9,ENDOFSTK        ;SUBFILE STACKPOINTER
         MOV  *R10+,R1           ;GET PARAMETER N
         MOV  *R10+,R0           ;GET ARRAY POINTER
         DEC  R1
         SLA  R1,1
         A    R0,R1              ;CALCULATE ARRAY ENDPOINT
         
         MOV  R0,R2              ;L:=1
         MOV  R1,R3              ;R:=N
         MOV  R1,R7
         S    R0,R7
         CI   R7,LIMIT
         JLE  INSERT             ;FIGURE OUT IF QUICKSORT IS NEEDED
         
MAINLOOP MOV  R2,R7
         SRL  R7,1
         MOV  R3,R8
         SRL  R8,1
         A    R8,R7 
         ANDI R7,0FFFEH          ;R7:=INT((L+R)/2)
         MOV  *R7,R8
         MOV  @2(R2),*R7
         MOV  R8,@2(R2)          ;A[(L+R)/2]:=:A[L+1]
         
         C    @2(R2),*R3
         JLT  NOSWAP1
         MOV  @2(R2),R8
         MOV  *R3,@2(R2)
         MOV  R8,*R3             ;A[L+1]:=:A[R]
         
NOSWAP1  C    *R2,*R3
         JLT  NOSWAP2
         MOV  *R2,R8
         MOV  *R3,*R2
         MOV  R8,*R3             ;A[L]:=:A[R]
         
NOSWAP2  C    @2(R2),*R2
         JLT  NOSWAP3
         MOV  @2(R2),R8
         MOV  *R2,@2(R2)
         MOV  R8,*R2             ;A[L+1]:=:A[L]
         
NOSWAP3  MOV  R2,R4
         INCT R4                 ;I:=L+1
         MOV  R3,R5              ;J:=R
         MOV  *R2,R6             ;KEY:=A[L]
         JMP  INCLOOP
         
INNERLOP MOV  *R4,R8             ;LOOP UNWRAPPING
         MOV  *R5,*R4
         MOV  R8,*R5             ;A[I]:=:A[J]
         
INCLOOP  INCT R4                 ;I:=I+1
         C    *R4,R6
         JLT  INCLOOP            ;A[I]<KEY
         
DECLOOP  DECT R5                 ;J:=J-1
         C    *R5,R6
         JGT  DECLOOP            ;A[J]>KEY
         
         C    R4,R5
         JLE  INNERLOP           ;IF I<=J THEN CONTINUE
         
OUT      MOV  *R2,R8
         MOV  *R5,*R2
         MOV  R8,*R5             ;A[L]:=:A[J]
         
DEL1     MOV  R5,R7              ;Quicksort subfiles?
         S    R2,R7              ;R7:=J-L
         MOV  R3,R8
         S    R4,R8
         INCT R8                 ;R8:=R-I+1
         CI   R7,LIMIT
         JH   DEL2
         CI   R8,LIMIT
         JH   DEL2
         
         CI   R9,ENDOFSTK        ;LVL=0?
         JEQ  INSERT             ;No more Quicksorting at all?
         
         MOV  *R9+,R2            ;POP L
         MOV  *R9+,R3            ;POP R
         JMP  MAINLOOP
         
DEL2     C    R7,R8              ;Determine what is small and large subfile
         JL   ELSE2
         
         MOV  R2,@LSFL
         MOV  R5,@LSFR
         DECT @LSFR
         MOV  R4,@SSFL
         MOV  R3,@SSFR
         JMP  DEL3

ELSE2    MOV  R4,@LSFL
         MOV  R3,@LSFR
         MOV  R2,@SSFL
         MOV  R5,@SSFR
         DECT @SSFR

DEL3     CI   R7,LIMIT           ;Is small subfile big enough to be sorted by
         JLE  THEN3              ;Quicksort?
         CI   R8,LIMIT
         JH   ELSE3

THEN3    MOV  @LSFL,R2           ;Don't Quicksort small subfile, only large
         MOV  @LSFR,R3
         JMP  MAINLOOP

ELSE3    DECT R9                 ;Stack large subfile
         MOV  @LSFR,*R9          ;PUSH R
         DECT R9
         MOV  @LSFL,*R9          ;PUSH L
         MOV  @SSFL,R2           ;Sort small subfile
         MOV  @SSFR,R3
         JMP  MAINLOOP

;Insertionsort finishing up

INSERT   MOV  R1,R4
         DECT R4                 ;I:=N-1
         C    R4,R0
         JL   LEAVE              ;Check if any looping at al
         
FORI     C    @2(R4),*R4
         JGT  NEXTI              ;If next is greater than this, it's OK
         
         MOV  *R4,R6             ;KEY:=A[I]
         MOV  R4,R5
         INCT R5                 ;J:=I+1
         
WHILE    MOV  *R5,@-2(R5)        ;A[J-1]:=A[J]
         INCT R5                 ;J:=J+1
         C    R5,R1
         JH   ENDWHILE           ;J>N?
         C    *R5,R6             ;A[J]<KEY?
         JLT  WHILE
ENDWHILE MOV  R6,@-2(R5)         ;A[J-1]:=KEY
NEXTI    DECT R4
         C    R4,R0              ;Check if passed array base point
         JHE  FORI
LEAVE    RTWP                    ;Return to main assembly level
         
         
;--------------
; DATA AREA

SORTWS   .BLOCK  20H,0           ;Workspace for sorting routine
SUBFSTK  .BLOCK  40H,0           ;Internal subfile stack
ENDOFSTK .EQU    SUBFSTK+40H     ;End of that stack

LSFL     .WORD   0               ;Large SubFile Left pointer
LSFR     .WORD   0               ;Large SubFile Right pointer
SSFL     .WORD   0               ;Small SubFile Left pointer
SSFR     .WORD   0               ;Small SubFile Right pointer

         .END

 

 

Edited January 31, 2022 by apersson850

[+TheBF]

Now if I am clever enough to remember how to use my own tools I should be able to:

1. Assembler this program
2. Link the object file into Forth with my linker
3. Fill the array with Forth
4. Run the sort from the Forth command line. 

We shall see. I might have to make some memory location tweaks but in theory I can do this.

 

Thank you. This is very educational for me.

[apersson850]

In the p-system, the system itself uses R8-R15. Of particular interest for this program is R10, the stack pointer, and R11, the return address. You can use R0-R7 on your own. But I needed a little more.

To be able to mess with the other registers I used a BLWP inside this program to my own workspace, and some data moving to get hold of the number of items to sort and their starting address. Note that I also pop the stack by changing the p-system's stack pointer before returning. Otherwise you crash the p-system.

Today I would have just LWPI a new workspace, but back then I didn't know what to LWPI back to get back to the p-system. Now I know. PASCALWS is 8380H.

Since the recursion has been removed, there is an internal stack, which keeps track of where the splits are. Quicksort splits the array into smaller arrays, and then applies itself to these arrays.

 

The .RELPROC directive instructs the p-system that this code file is a relocatable file (even after it was loaded in the first place, name is QSORT and it allocates two words for parameters on the stack.

.WORD is the same as DATA, .BLOCK is BSS.

Edited January 31, 2022 by apersson850

[+TheBF]

Just now, apersson850 said:

In the p-system, the system itself uses R8-R15. Of particular interest for this program is R10, the stack pointer, and R11, the return address. You can use R0-R7 on your own. But I needed a little more.

To be able to mess with the other registers I used a BLWP inside this program to my own workspace, and some data moving to get hold of the number of items to sort and their starting address. Note that I also pop the stack by changing the p-system's stack pointer before returning. Otherwise you crash the p-system.

Today I would have just LWPI a new workspace, but back then I didn't know what to LWPI back to get back to the p-system. Now I know. PASCALWS is 8380H.

Thanks. I was noting the register usage just now.

Most of it is very compatible with what I have.  I can create a workspace and load its registers directly from Forth so setting it up is pretty easy.

This would mean I don't need to reach back to Forth's stack to get the array address and size.

Lots more study at this end.  I will have to adjust for TI-99 assembler with some directive names.

Very nicely commented.

Succinct and helpful.   

 

[apersson850]

The comments refer to the pseudo algorithm, mainly written in Algol syntax, which explained the procedure to follow to me. Many years ago.

[apersson850]

18 hours ago, atrax27407 said:

Wycove Forth allowed loading from tape and was the first independently developed FORTH after the release of TI Forth. I still use it from time to time albeit from disk these days.

I checked some sources. It seems Wycove Forth and PB Forth were both released in 1983. I don't know exactly which date, so I can't tell which was the first one. They both support loading the system from tape. Both will run with Extended BASIC, Mini Memory or Editor assembler.

[+TheBF]

Too many links on the internet. You can waste a lot of life span but this one I liked. 

 

I had looked at the J1 CPU page and GitHub repository but I had never seen this presentation that explains why Mr. Bowman felt the need to make his own FPGA CPU.  It really really really is RISC.  

 

The presentation is short and clear.  It also shows the speed and code-size improvements he got using his own Forth CPU and Forth tool chain versus the Pico- Blaze CPU and GCC running on the same FPGA.  Impressive work.

 

The J1 CPU (forth.org)

[+FarmerPotato]

On 4/4/2022 at 2:57 PM, TheBF said:

Too many links on the internet. You can waste a lot of life span but this one I liked. 

 

I had looked at the J1 CPU page and GitHub repository but I had never seen this presentation that explains why Mr. Bowman felt the need to make his own FPGA CPU.  It really really really is RISC.  

 

The presentation is short and clear.  It also shows the speed and code-size improvements he got using his own Forth CPU and Forth tool chain versus the Pico- Blaze CPU and GCC running on the same FPGA.  Impressive work.

 

The J1 CPU (forth.org)

J1A is the most beautiful thing. 
 

All my laptops and FPGA boards have copies of it with various permutations. I’ve used it to program tests for each thing I’m doing.