On 2022-01-28, Dave Froble <davef@tsoft-inc.com> wrote:
> On 1/28/2022 12:31 PM, John Reagan wrote:
>> 4) As we've discussed the BASIC cross-compiler is still not available due to G2L not being
>> able to totally handle how the BASIC MAP statement is described to GEM. The GEM to
>> LLVM module for common blocks is radically different. Could you write a DIRECTORY
>> replacement in BASIC without using MAP?
>
> Why, yes, I'm rather sure I could. For example, from one of my routines:
>
> RECORD FABBLK !
> RECORD NAMBLK !
> RECORD FIBBLK ! FIB structure
>
> And now I'm waiting for you to say that the Basic RECORD statement has the same
> problems as MAP.
>

How easy is it in DEC Basic to build a tree of (say) 1000 nodes of
a custom data structure in dynamic memory and then walk the tree
either depth-first or breadth-first ?

I've had a quick look at the dynamic storage section of the DEC Basic user
manual, but I don't see how you link a set of nodes together into a tree.
However, as mentioned previously, I don't know DEC Basic and searching
for the word pointer didn't reveal anything appropriate, so I assume
it's another keyword I am not aware of.

In addition, how easy is this to do if the nodes are not all of the
same record type, but have a common tag at the start of each record
to say what kind of record it actually is ? I see you have variant
records in DEC Basic. Do they also work in a dynamic memory based
tree structure ?

Simon.

--
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP
Walking destinations on a map are further away than they appear.

On Friday, January 28, 2022 at 1:57:28 PM UTC-6, Simon Clubley wrote:
>
> How easy is it in DEC Basic to build a tree of (say) 1000 nodes of
> a custom data structure in dynamic memory and then walk the tree
> either depth-first or breadth-first ?
>

The statement that you want is

DIM

create a (I haven't hacked BASIC for a while and didn't log into Eisner to test this so take the concept, not the syntax, as being pure)

RECORD SOME_RECORD
STRING IN_USE=1%
STRING SOME_KEY_VALUE=15%
INTEGER PREV_REC
INTEGER NEXT_REC
STRING WHOLE_LOT_OF_STUFF=255%
! other fields
END RECORD

As you learned in data structures class, you put the subscripts in as you add records.
You have to keep the doubly linked list in order yourself, but if you set IN_USE to CVT%$(255%) or even just "Z" for every empty record you can even sort well.

Oh, you don't like it as a doubly linked list?

RECORD SOME_RECORD
STRING IN_USE=1%
STRING SOME_KEY_VALUE=15%
INTEGER LEFT_NODE
INTEGER RIGHT_NODE
INTEGER PARENT_NODE
STRING WHOLE_LOT_OF_STUFF=255%
! other fields
END RECORD

You can even redimension if need be.

On 1/28/2022 2:57 PM, Simon Clubley wrote:
> How easy is it in DEC Basic to build a tree of (say) 1000 nodes of
> a custom data structure in dynamic memory and then walk the tree
> either depth-first or breadth-first ?
>
> I've had a quick look at the dynamic storage section of the DEC Basic user
> manual, but I don't see how you link a set of nodes together into a tree.
> However, as mentioned previously, I don't know DEC Basic and searching
> for the word pointer didn't reveal anything appropriate, so I assume
> it's another keyword I am not aware of.
>
> In addition, how easy is this to do if the nodes are not all of the
> same record type, but have a common tag at the start of each record
> to say what kind of record it actually is ? I see you have variant
> records in DEC Basic. Do they also work in a dynamic memory based
> tree structure ?

Basic is different than C and Pascal. You do not call a dynamic
allocation function and get back a machine address that you need
to free later.

But you can do a tree by using a dynamic sized array and indexes
into that as "pointers".

And Basic map dynamic is similar to C union.

Example code (maybe not super elegant - either because
it is not the right language for the task or because my Basic
skills are very limited - but it seems to work):

$ typ tree.bas
record treenoderec
long v
long styp
string s = 512
long pnode
long lnode
long rnode
end record

declare integer constant STRING_TYP = 1
declare integer constant INTEGER_TYP = 2
declare integer constant DECIMAL_TYP = 3
$ typ dyn.bas
program dyn

%include "tree.bas"

external sub tree_insert(treenoderec dim(), long, long, long, string)
external sub tree_print(treenoderec dim())
external sub tree_dump(treenoderec dim(), long)

declare long top
declare long capacity
top = 0
capacity = 1
dim treenoderec tree (1 to capacity)
map (u) string sv = 512
map dynamic (u) long iv
map dynamic (u) decimal zv

declare long i, j

for i = 1 to 10
sv = "Nothing"
call tree_insert(tree(), top, rnd * 1000, STRING_TYP, sv)
if top = capacity then
gosub extend_tree_array
end if
next i
iv = 123
call tree_insert(tree(), top, 499, INTEGER_TYP, sv)
zv = 123.45
call tree_insert(tree(), top, 501, DECIMAL_TYP, sv)
call tree_dump(tree(), top)
call tree_print(tree())
exit program

extend_tree_array:
dim treenoderec temp(1 to capacity)
for j = 1 to capacity
temp(j) = tree(j)
next j
capacity = 2 * capacity
dim treenoderec tree (1 to capacity)
for j = 1 to capacity / 2
tree(j) = temp(j)
next j
return

end program
! sub tree_update(treenoderec tree(), long top, long ix)

%include "tree.bas"

if tree(top)::v < tree(ix)::v then
if tree(ix)::lnode = 0 then
tree(ix)::lnode = top
tree(top)::pnode = ix
else
call tree_update(tree(), top, tree(ix)::lnode)
end if
else
if tree(ix)::rnode = 0 then
tree(ix)::rnode = top
tree(top)::pnode = ix
else
call tree_update(tree(), top, tree(ix)::rnode)
end if
end if

end sub
! sub tree_insert(treenoderec tree(), long top, long v, long styp, string s)

%include "tree.bas"

external sub tree_update(treenoderec dim(), long, long)

declare long ix

top = top + 1
tree(top)::v = v
tree(top)::styp = styp
tree(top)::s = s
tree(top)::lnode = 0
tree(top)::rnode = 0
if top = 1 then
tree(top)::pnode = 0
else
call tree_update(tree(), top, 1)
end if

end sub
! sub tree_print_part(treenoderec tree(), long ix)

%include "tree.bas"

map (u) string sv = 512
map dynamic (u) long iv
map dynamic (u) decimal zv

if tree(ix)::lnode > 0 then
call tree_print_part(tree(), tree(ix)::lnode)
end if
sv = tree(ix)::s
if tree(ix)::styp = STRING_TYP then
print tree(ix)::v, trm$(sv)
end if
if tree(ix)::styp = INTEGER_TYP then
print tree(ix)::v, iv
end if
if tree(ix)::styp = DECIMAL_TYP then
print tree(ix)::v, zv
end if
if tree(ix)::rnode > 0 then
call tree_print_part(tree(), tree(ix)::rnode)
end if

end sub
! sub tree_print(treenoderec tree())

%include "tree.bas"

external sub tree_print_part(treenoderec dim(), long)

call tree_print_part(tree(), 1)

end sub
! sub tree_dump(treenoderec tree(), long top)

%include "tree.bas"

declare long i

for i = 1 to top
print
i,tree(i)::v,tree(i)::styp,tree(i)::pnode,tree(i)::lnode,tree(i)::rnode
next i

end sub
$ bas dyn
$ lin dyn
$ run dyn
1 763 1 0 2 3
2 179 1 1 0 5
3 902 1 1 4 0
4 889 1 3 7 0
5 387 1 2 8 6
6 475 1 5 0 9
7 882 1 4 0 0
8 185 1 5 0 10
9 638 1 6 11 0
10 269 1 8 0 0
11 499 2 9 0 12
12 501 3 11 0 0
179 Nothing
185 Nothing
269 Nothing
387 Nothing
475 Nothing
499 123
501 123.44
638 Nothing
763 Nothing
882 Nothing
889 Nothing
902 Nothing

Arne

On 1/28/2022 8:33 PM, Arne Vajhøj wrote:
> On 1/28/2022 2:57 PM, Simon Clubley wrote:
>> How easy is it in DEC Basic to build a tree of (say) 1000 nodes of
>> a custom data structure in dynamic memory and then walk the tree
>> either depth-first or breadth-first ?
>>
>> I've had a quick look at the dynamic storage section of the DEC Basic user
>> manual, but I don't see how you link a set of nodes together into a tree.
>> However, as mentioned previously, I don't know DEC Basic and searching
>> for the word pointer didn't reveal anything appropriate, so I assume
>> it's another keyword I am not aware of.
>>
>> In addition, how easy is this to do if the nodes are not all of the
>> same record type, but have a common tag at the start of each record
>> to say what kind of record it actually is ? I see you have variant
>> records in DEC Basic. Do they also work in a dynamic memory based
>> tree structure ?
>
> Basic is different than C and Pascal. You do not call a dynamic
> allocation function and get back a machine address that you need
> to free later.
>
> But you can do a tree by using a dynamic sized array and indexes
> into that as "pointers".
>
> And Basic map dynamic is similar to C union.
>
> Example code (maybe not super elegant - either because
> it is not the right language for the task or because my Basic
> skills are very limited - but it seems to work):
>
> $ typ tree.bas
> record treenoderec
> long v
> long styp
> string s = 512
> long pnode
> long lnode
> long rnode
> end record
>
> declare integer constant STRING_TYP = 1
> declare integer constant INTEGER_TYP = 2
> declare integer constant DECIMAL_TYP = 3
> $ typ dyn.bas
> program dyn
>
> %include "tree.bas"
>
> external sub tree_insert(treenoderec dim(), long, long, long, string)
> external sub tree_print(treenoderec dim())
> external sub tree_dump(treenoderec dim(), long)
>
> declare long top
> declare long capacity
> top = 0
> capacity = 1
> dim treenoderec tree (1 to capacity)
> map (u) string sv = 512
> map dynamic (u) long iv
> map dynamic (u) decimal zv
>
> declare long i, j
>
> for i = 1 to 10
> sv = "Nothing"
> call tree_insert(tree(), top, rnd * 1000, STRING_TYP, sv)
> if top = capacity then
> gosub extend_tree_array
> end if
> next i
> iv = 123
> call tree_insert(tree(), top, 499, INTEGER_TYP, sv)
> zv = 123.45
> call tree_insert(tree(), top, 501, DECIMAL_TYP, sv)
> call tree_dump(tree(), top)
> call tree_print(tree())
> exit program
>
> extend_tree_array:
> dim treenoderec temp(1 to capacity)
> for j = 1 to capacity
> temp(j) = tree(j)
> next j
> capacity = 2 * capacity
> dim treenoderec tree (1 to capacity)
> for j = 1 to capacity / 2
> tree(j) = temp(j)
> next j
> return
>
> end program
> !
> sub tree_update(treenoderec tree(), long top, long ix)
>
> %include "tree.bas"
>
> if tree(top)::v < tree(ix)::v then
> if tree(ix)::lnode = 0 then
> tree(ix)::lnode = top
> tree(top)::pnode = ix
> else
> call tree_update(tree(), top, tree(ix)::lnode)
> end if
> else
> if tree(ix)::rnode = 0 then
> tree(ix)::rnode = top
> tree(top)::pnode = ix
> else
> call tree_update(tree(), top, tree(ix)::rnode)
> end if
> end if
>
> end sub
> !
> sub tree_insert(treenoderec tree(), long top, long v, long styp, string s)
>
> %include "tree.bas"
>
> external sub tree_update(treenoderec dim(), long, long)
>
> declare long ix
>
> top = top + 1
> tree(top)::v = v
> tree(top)::styp = styp
> tree(top)::s = s
> tree(top)::lnode = 0
> tree(top)::rnode = 0
> if top = 1 then
> tree(top)::pnode = 0
> else
> call tree_update(tree(), top, 1)
> end if
>
> end sub
> !
> sub tree_print_part(treenoderec tree(), long ix)
>
> %include "tree.bas"
>
> map (u) string sv = 512
> map dynamic (u) long iv
> map dynamic (u) decimal zv
>
> if tree(ix)::lnode > 0 then
> call tree_print_part(tree(), tree(ix)::lnode)
> end if
> sv = tree(ix)::s
> if tree(ix)::styp = STRING_TYP then
> print tree(ix)::v, trm$(sv)
> end if
> if tree(ix)::styp = INTEGER_TYP then
> print tree(ix)::v, iv
> end if
> if tree(ix)::styp = DECIMAL_TYP then
> print tree(ix)::v, zv
> end if
> if tree(ix)::rnode > 0 then
> call tree_print_part(tree(), tree(ix)::rnode)
> end if
>
> end sub
> !
> sub tree_print(treenoderec tree())
>
> %include "tree.bas"
>
> external sub tree_print_part(treenoderec dim(), long)
>
> call tree_print_part(tree(), 1)
>
> end sub
> !
> sub tree_dump(treenoderec tree(), long top)
>
> %include "tree.bas"
>
> declare long i
>
> for i = 1 to top
> print i,tree(i)::v,tree(i)::styp,tree(i)::pnode,tree(i)::lnode,tree(i)::rnode
> next i
>
> end sub
> $ bas dyn
> $ lin dyn
> $ run dyn
> 1 763 1 0 2 3
> 2 179 1 1 0 5
> 3 902 1 1 4 0
> 4 889 1 3 7 0
> 5 387 1 2 8 6
> 6 475 1 5 0 9
> 7 882 1 4 0 0
> 8 185 1 5 0 10
> 9 638 1 6 11 0
> 10 269 1 8 0 0
> 11 499 2 9 0 12
> 12 501 3 11 0 0
> 179 Nothing
> 185 Nothing
> 269 Nothing
> 387 Nothing
> 475 Nothing
> 499 123
> 501 123.44
> 638 Nothing
> 763 Nothing
> 882 Nothing
> 889 Nothing
> 902 Nothing
>
> Arne
>

Arne, I have difficulty following your code examples. Is it me, or you?

--
David Froble Tel: 724-529-0450
Dave Froble Enterprises, Inc. E-Mail: davef@tsoft-inc.com
DFE Ultralights, Inc.
170 Grimplin Road
Vanderbilt, PA 15486

On 1/28/2022 2:57 PM, Simon Clubley wrote:
> On 2022-01-28, Dave Froble <davef@tsoft-inc.com> wrote:
>> On 1/28/2022 12:31 PM, John Reagan wrote:
>>> 4) As we've discussed the BASIC cross-compiler is still not available due to G2L not being
>>> able to totally handle how the BASIC MAP statement is described to GEM. The GEM to
>>> LLVM module for common blocks is radically different. Could you write a DIRECTORY
>>> replacement in BASIC without using MAP?
>>
>> Why, yes, I'm rather sure I could. For example, from one of my routines:
>>
>> RECORD FABBLK !
>> RECORD NAMBLK !
>> RECORD FIBBLK ! FIB structure
>>
>> And now I'm waiting for you to say that the Basic RECORD statement has the same
>> problems as MAP.
>>
>
> How easy is it in DEC Basic to build a tree of (say) 1000 nodes of
> a custom data structure in dynamic memory and then walk the tree
> either depth-first or breadth-first ?

Linked lists are rather basic (sic) ..

> I've had a quick look at the dynamic storage section of the DEC Basic user
> manual, but I don't see how you link a set of nodes together into a tree.
> However, as mentioned previously, I don't know DEC Basic and searching
> for the word pointer didn't reveal anything appropriate, so I assume
> it's another keyword I am not aware of.

No, it is because you're attempting to use methods you'd use in C. Different
methods in Basic.

> In addition, how easy is this to do if the nodes are not all of the
> same record type, but have a common tag at the start of each record
> to say what kind of record it actually is ? I see you have variant
> records in DEC Basic. Do they also work in a dynamic memory based
> tree structure ?

Unless you're going to do your own LIB$Get_VM Basic doesn't do dynamic memory in
that manner. You can, but probably should not. I tend to assign adequate
storage for the task at hand.

An example of how I'd approach any such need:

Record NODES
Long ForwardLink
Long BackLink
Word InUse
String N$=64
End Record

DIM NODES List(999)

Might also:

DIM NODES List2(999)
DIM NODES List3(9999)

I'd probably have an integer variable pointing to the start of the list. Would
not have to be consecutive if nodes were being added and deleted. Could have an
integer pointing to beginning of unused nodes. (I avoid using the word POINTER,
though that's what they would be.)

Not going to go much further, other than to say that I've used linked lists,
tree structures, and such many times.

If you really want to get into such, take a look at my RMS_LOCKS.BAS on the VMS
freeware.

--
David Froble Tel: 724-529-0450
Dave Froble Enterprises, Inc. E-Mail: davef@tsoft-inc.com
DFE Ultralights, Inc.
170 Grimplin Road
Vanderbilt, PA 15486

On 2022-01-28 19:57:26 +0000, Simon Clubley said:

> How easy is it in DEC Basic to build a tree of (say) 1000 nodes of a
> custom data structure in dynamic memory and then walk the tree either
> depth-first or breadth-first ?

MAP DYNAMIC and REMAP are the operators you're looking for, for the
approach you're envisioning.

Maybe involving the LIBRTL tree routines.

It's a slog. Lots of glue code. But it's workable.

Pragmatically, more than a few BASIC apps store will dynamic data
structures in key-value or other persistent file storage.

Not that I've met many BASIC apps that have used red-black or other trees.

With SSDs et al, the performance penalty for (misusing?) persistent
storage is much lower.

Without language support for pointers (for the ugly approach) and
without object support (for the cleaner approach), BASIC dynamic memory
data structures get clunky.

Moderate- and larger-sized apps necessarily also become multiple
sub-two-tebibyte storage chunks too, with all the "fun" that entails.

BASIC is a ripe target for 64-bit addressing and for the addition of
object support, as I've commented before.

With that, the binary tree can be implemented within the object
run-time (once, not everywhere), and the developer can (largely) ignore
the tree implementation details.

--
Pure Personal Opinion | HoffmanLabs LLC

On 1/29/2022 12:16 AM, Dave Froble wrote:
> On 1/28/2022 8:33 PM, Arne Vajhøj wrote:
>> On 1/28/2022 2:57 PM, Simon Clubley wrote:
>>> How easy is it in DEC Basic to build a tree of (say) 1000 nodes of
>>> a custom data structure in dynamic memory and then walk the tree
>>> either depth-first or breadth-first ?
>>>
>>> I've had a quick look at the dynamic storage section of the DEC Basic
>>> user
>>> manual, but I don't see how you link a set of nodes together into a
>>> tree.
>>> However, as mentioned previously, I don't know DEC Basic and searching
>>> for the word pointer didn't reveal anything appropriate, so I assume
>>> it's another keyword I am not aware of.
>>>
>>> In addition, how easy is this to do if the nodes are not all of the
>>> same record type, but have a common tag at the start of each record
>>> to say what kind of record it actually is ? I see you have variant
>>> records in DEC Basic. Do they also work in a dynamic memory based
>>> tree structure ?
>>
>> Basic is different than C and Pascal. You do not call a dynamic
>> allocation function and get back a machine address that you need
>> to free later.
>>
>> But you can do a tree by using a dynamic sized array and indexes
>> into that as "pointers".
>>
>> And Basic map dynamic is similar to C union.
>>
>> Example code (maybe not super elegant - either because
>> it is not the right language for the task or because my Basic
>> skills are very limited - but it seems to work):
>>
>> $ typ tree.bas
>> record treenoderec

>> $ typ dyn.bas
>> program dyn
>>
>> %include "tree.bas"

> Arne, I have difficulty following your code examples.  Is it me, or you?

Probably me.

:-)

In this case Simon outlined a problem where Pascal and C are obvious
languages and me with no Basic experience wrote some Basic code - that
is almost ensure an "unsual style". Or to put it another way: I am
(or was) a Fortran programmer and Fortran programmers can program
in Fortran in any language. :-)

Arne

On 1/29/2022 12:16 AM, Dave Froble wrote:
> On 1/28/2022 8:33 PM, Arne Vajhøj wrote:
>> On 1/28/2022 2:57 PM, Simon Clubley wrote:
>>> How easy is it in DEC Basic to build a tree of (say) 1000 nodes of
>>> a custom data structure in dynamic memory and then walk the tree
>>> either depth-first or breadth-first ?
>>>
>>> I've had a quick look at the dynamic storage section of the DEC Basic
>>> user
>>> manual, but I don't see how you link a set of nodes together into a
>>> tree.
>>> However, as mentioned previously, I don't know DEC Basic and searching
>>> for the word pointer didn't reveal anything appropriate, so I assume
>>> it's another keyword I am not aware of.
>>>
>>> In addition, how easy is this to do if the nodes are not all of the
>>> same record type, but have a common tag at the start of each record
>>> to say what kind of record it actually is ? I see you have variant
>>> records in DEC Basic. Do they also work in a dynamic memory based
>>> tree structure ?

>> $ typ tree.bas
>> record treenoderec

>> $ typ dyn.bas
>> program dyn
>>
>> %include "tree.bas"

> I have difficulty following your code examples.

If I were to try to explain the code then I needed 3 things.

1) a tree structure

which I did with an array of records and using element indexes
instead of traditional pointers/addresses.

>> record treenoderec
....
>>    long pnode
>>    long lnode
>>    long rnode
>> end record

>> declare long top
>> declare long capacity

>> dim treenoderec tree (1 to capacity)

>> sub tree_insert(treenoderec tree(), long top, ...)

>> sub tree_print(treenoderec tree())

2) dynamic allocation

which I did with DIM when the trees backing array needed
to be extended.

>> if top = capacity then
>> gosub extend_tree_array
>> end if

>> extend_tree_array:
>> dim treenoderec temp(1 to capacity)
>> for j = 1 to capacity
>> temp(j) = tree(j)
>> next j
>> capacity = 2 * capacity
>> dim treenoderec tree (1 to capacity)
>> for j = 1 to capacity / 2
>> tree(j) = temp(j)
>> next j
>> return

3) support for different types (C union, Pascal case record)

which I did with MAP and MAP DYNAMIC.

>> record treenoderec
....
>> long styp
>> string s = 512
....
>> end record

>> declare integer constant STRING_TYP = 1
>> declare integer constant INTEGER_TYP = 2
>> declare integer constant DECIMAL_TYP = 3

>> map (u) string sv = 512
>> map dynamic (u) long iv
>> map dynamic (u) decimal zv

Arne

On 29/01/2022 3:57 am, Simon Clubley wrote:
> On 2022-01-28, Dave Froble <davef@tsoft-inc.com> wrote:
>> On 1/28/2022 12:31 PM, John Reagan wrote:
>>> 4) As we've discussed the BASIC cross-compiler is still not available due to G2L not being
>>> able to totally handle how the BASIC MAP statement is described to GEM. The GEM to
>>> LLVM module for common blocks is radically different. Could you write a DIRECTORY
>>> replacement in BASIC without using MAP?
>>
>> Why, yes, I'm rather sure I could. For example, from one of my routines:
>>
>> RECORD FABBLK !
>> RECORD NAMBLK !
>> RECORD FIBBLK ! FIB structure
>>
>> And now I'm waiting for you to say that the Basic RECORD statement has the same
>> problems as MAP.
>>
>
> How easy is it in DEC Basic to build a tree of (say) 1000 nodes of
> a custom data structure in dynamic memory and then walk the tree
> either depth-first or breadth-first ?
>
> I've had a quick look at the dynamic storage section of the DEC Basic user
> manual, but I don't see how you link a set of nodes together into a tree.
> However, as mentioned previously, I don't know DEC Basic and searching
> for the word pointer didn't reveal anything appropriate, so I assume
> it's another keyword I am not aware of.
>
> In addition, how easy is this to do if the nodes are not all of the
> same record type, but have a common tag at the start of each record
> to say what kind of record it actually is ? I see you have variant
> records in DEC Basic. Do they also work in a dynamic memory based
> tree structure ?
>
> Simon.
>

I'd employ Lib$ malloc, realloc, and calloc

In article <st4t2h$gh9$2@gioia.aioe.org>, Richard Maher <maher_rjSPAMLESS@hotmail.com> writes:
>On 29/01/2022 3:57 am, Simon Clubley wrote:
>> On 2022-01-28, Dave Froble <davef@tsoft-inc.com> wrote:
>>> On 1/28/2022 12:31 PM, John Reagan wrote:
>>>> 4) As we've discussed the BASIC cross-compiler is still not available due to G2L not being
>>>> able to totally handle how the BASIC MAP statement is described to GEM. The GEM to
>>>> LLVM module for common blocks is radically different. Could you write a DIRECTORY
>>>> replacement in BASIC without using MAP?
>>>
>>> Why, yes, I'm rather sure I could. For example, from one of my routines:
>>>
>>> RECORD FABBLK !
>>> RECORD NAMBLK !
>>> RECORD FIBBLK ! FIB structure
>>>
>>> And now I'm waiting for you to say that the Basic RECORD statement has the same
>>> problems as MAP.
>>>
>>
>> How easy is it in DEC Basic to build a tree of (say) 1000 nodes of
>> a custom data structure in dynamic memory and then walk the tree
>> either depth-first or breadth-first ?
>>
>> I've had a quick look at the dynamic storage section of the DEC Basic user
>> manual, but I don't see how you link a set of nodes together into a tree.
>> However, as mentioned previously, I don't know DEC Basic and searching
>> for the word pointer didn't reveal anything appropriate, so I assume
>> it's another keyword I am not aware of.
>>
>> In addition, how easy is this to do if the nodes are not all of the
>> same record type, but have a common tag at the start of each record
>> to say what kind of record it actually is ? I see you have variant
>> records in DEC Basic. Do they also work in a dynamic memory based
>> tree structure ?
>>
>> Simon.
>>
>
>I'd employ Lib$ malloc, realloc, and calloc

How C senor.

--
VAXman- A Bored Certified VMS Kernel Mode Hacker VAXman(at)TMESIS(dot)ORG

I speak to machines with the voice of humanity.

On 2022-01-28, seasoned_geek <roland@logikalsolutions.com> wrote:
>
> Oh, you don't like it as a doubly linked list?
>
> RECORD SOME_RECORD
> STRING IN_USE=1%
> STRING SOME_KEY_VALUE=15%
> INTEGER LEFT_NODE
> INTEGER RIGHT_NODE
> INTEGER PARENT_NODE
> STRING WHOLE_LOT_OF_STUFF=255%
> ! other fields
> END RECORD
>
> You can even redimension if need be.

If _that's_ how you do a tree in DEC Basic, then yuck, yuck, yuck!!!

For starters, what about when you want to prune the tree and insert
new branches and leaf nodes while you are processing it ?

My question was driven by Arne's comment that he would prefer DEC Basic
over C for userland applications. If you are going to replace C, then
you need a language that can do everything C can, and do it better.

That's certainly true for Pascal, but not true for DEC Basic based
on what I see above. DEC Basic might be suitable for some less complex
programs, but certainly not all of the userland programs.

For example, could you cleanly write a CDU replacement or a TPU
replacement in DEC Basic ? I've never seen the source code for either
of them, but I would expect both of those to use variable sized
tree building and processing because of the parsing they do.

Simon.

--
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP
Walking destinations on a map are further away than they appear.

On 2022-01-29, Arne Vajhøj <arne@vajhoej.dk> wrote:
> On 1/29/2022 12:16 AM, Dave Froble wrote:
>
>> Arne, I have difficulty following your code examples.  Is it me, or you?
>

Well, Arne didn't use line numbers so that may be throwing you. :-)

> Probably me.
>
>:-)
>
> In this case Simon outlined a problem where Pascal and C are obvious
> languages and me with no Basic experience wrote some Basic code - that
> is almost ensure an "unsual style". Or to put it another way: I am
> (or was) a Fortran programmer and Fortran programmers can program
> in Fortran in any language. :-)
>

Thanks for the demo program Arne.

The approach you are forced to use in DEC Basic is way more ugly than
doing it in C or Pascal.

Simon.

--
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP
Walking destinations on a map are further away than they appear.

On 1/30/2022 6:45 PM, Simon Clubley wrote:
> On 2022-01-28, seasoned_geek <roland@logikalsolutions.com> wrote:
>> Oh, you don't like it as a doubly linked list?
>>
>> RECORD SOME_RECORD
>> STRING IN_USE=1%
>> STRING SOME_KEY_VALUE=15%
>> INTEGER LEFT_NODE
>> INTEGER RIGHT_NODE
>> INTEGER PARENT_NODE
>> STRING WHOLE_LOT_OF_STUFF=255%
>> ! other fields
>> END RECORD
>>
>> You can even redimension if need be.
>
> If _that's_ how you do a tree in DEC Basic, then yuck, yuck, yuck!!!
>
> For starters, what about when you want to prune the tree and insert
> new branches and leaf nodes while you are processing it ?
>
> My question was driven by Arne's comment that he would prefer DEC Basic
> over C for userland applications. If you are going to replace C, then
> you need a language that can do everything C can, and do it better.
>
> That's certainly true for Pascal, but not true for DEC Basic based
> on what I see above. DEC Basic might be suitable for some less complex
> programs, but certainly not all of the userland programs.
>
> For example, could you cleanly write a CDU replacement or a TPU
> replacement in DEC Basic ? I've never seen the source code for either
> of them, but I would expect both of those to use variable sized
> tree building and processing because of the parsing they do.

It is actually not that different from the C/Pascal way.

It just use array indexes instead of pointers/addresses.

So 3 integers instead of 3 pointers.

You can do tree's, hash tables's etc. that way.

Just a different way of thinking.

Arne

On 1/30/2022 6:54 PM, Simon Clubley wrote:
> On 2022-01-29, Arne Vajhøj <arne@vajhoej.dk> wrote:
>> In this case Simon outlined a problem where Pascal and C are obvious
>> languages and me with no Basic experience wrote some Basic code - that
>> is almost ensure an "unsual style". Or to put it another way: I am
>> (or was) a Fortran programmer and Fortran programmers can program
>> in Fortran in any language. :-)
>
> Thanks for the demo program Arne.
>
> The approach you are forced to use in DEC Basic is way more ugly than
> doing it in C or Pascal.

Ugly or just unfamiliar?

Arne

On 2022-01-30, Arne Vajhøj <arne@vajhoej.dk> wrote:
>
> It is actually not that different from the C/Pascal way.
>
> It just use array indexes instead of pointers/addresses.
>
> So 3 integers instead of 3 pointers.
>
> You can do tree's, hash tables's etc. that way.
>
> Just a different way of thinking.
>

Except you have to manage those integers yourself unlike the Pascal
or C approach, especially if you want to prune or add nodes while you
are processing the tree. There's also the required copying of the
current data every time you grow the tree.

Simon.

--
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP
Walking destinations on a map are further away than they appear.

On 1/30/2022 7:03 PM, Simon Clubley wrote:
> On 2022-01-30, Arne Vajhøj <arne@vajhoej.dk> wrote:
>>
>> It is actually not that different from the C/Pascal way.
>>
>> It just use array indexes instead of pointers/addresses.
>>
>> So 3 integers instead of 3 pointers.
>>
>> You can do tree's, hash tables's etc. that way.
>>
>> Just a different way of thinking.
>
> Except you have to manage those integers yourself unlike the Pascal
> or C approach, especially if you want to prune or add nodes while you
> are processing the tree.

They get assigned when new nodes are added and they are used to
walk the tree. I don't think C/Pascal pointers would be different
in that regard.

Pascal pointers would be more type safe though.

> There's also the required copying of the
> current data every time you grow the tree.

That is common practice in many languages for dynamic
sized data structures needing linear backing.

Arne

On 2022-01-30, Arne Vajhøj <arne@vajhoej.dk> wrote:
> On 1/30/2022 6:54 PM, Simon Clubley wrote:
>> On 2022-01-29, Arne Vajhøj <arne@vajhoej.dk> wrote:
>>> In this case Simon outlined a problem where Pascal and C are obvious
>>> languages and me with no Basic experience wrote some Basic code - that
>>> is almost ensure an "unsual style". Or to put it another way: I am
>>> (or was) a Fortran programmer and Fortran programmers can program
>>> in Fortran in any language. :-)
>>
>> Thanks for the demo program Arne.
>>
>> The approach you are forced to use in DEC Basic is way more ugly than
>> doing it in C or Pascal.
>
> Ugly or just unfamiliar?
>

Ugly because of all the tree management stuff you have to do for
yourself that you get for free in C or Pascal.

In addition, there's the overhead of copying the tree everytime
you run out of allocated spare space and need to extend it.

Simon.

--
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP
Walking destinations on a map are further away than they appear.

On 2022-01-30, Arne Vajhøj <arne@vajhoej.dk> wrote:
> On 1/30/2022 7:03 PM, Simon Clubley wrote:
>> There's also the required copying of the
>> current data every time you grow the tree.
>
> That is common practice in many languages for dynamic
> sized data structures needing linear backing.
>

But elsewhere you have the choice of whether to use something
like a Vector or if you need to build a tree structure yourself.

Specifying the growth increment of a linear structure is also
a tradeoff but you are not forced to use a linear structure if
you can build real trees and that's a better choice.

Simon.

--
Simon Clubley, clubley@remove_me.eisner.decus.org-Earth.UFP
Walking destinations on a map are further away than they appear.

On 1/30/2022 7:14 PM, Simon Clubley wrote:
> On 2022-01-30, Arne Vajhøj <arne@vajhoej.dk> wrote:
>> On 1/30/2022 7:03 PM, Simon Clubley wrote:
>>> There's also the required copying of the
>>> current data every time you grow the tree.
>>
>> That is common practice in many languages for dynamic
>> sized data structures needing linear backing.
>
> But elsewhere you have the choice of whether to use something
> like a Vector or if you need to build a tree structure yourself.
>
> Specifying the growth increment of a linear structure is also
> a tradeoff but you are not forced to use a linear structure if
> you can build real trees and that's a better choice.

Typical you will have both a linear data structure and trees.

I was not trying to make linear and trees the same.

My point was that the reallocating double size concept
is considered acceptable effective in the industry.

Arne

On 1/30/2022 6:45 PM, Simon Clubley wrote:
> On 2022-01-28, seasoned_geek <roland@logikalsolutions.com> wrote:
>>
>> Oh, you don't like it as a doubly linked list?
>>
>> RECORD SOME_RECORD
>> STRING IN_USE=1%
>> STRING SOME_KEY_VALUE=15%
>> INTEGER LEFT_NODE
>> INTEGER RIGHT_NODE
>> INTEGER PARENT_NODE
>> STRING WHOLE_LOT_OF_STUFF=255%
>> ! other fields
>> END RECORD
>>
>> You can even redimension if need be.
>
> If _that's_ how you do a tree in DEC Basic, then yuck, yuck, yuck!!!

Are you trying to show some bias?

Some people show you some very simple uses of the RECORD statement, and because
they are not fleshed out, you don't see the use. Hey, i do this for
compensation, cough up some money and I'll write any application you want in Basic.

Basically (sic) the RECORD statement is a method of defining structures, and it
can be very flexible. Also understandable. Can you say that about C?

> For starters, what about when you want to prune the tree and insert
> new branches and leaf nodes while you are processing it ?

Can be done. I haven't yet seen any applications where such is needed.
Usually, an application is designed for a specific need, and then Basic can be
used to implement the application.

> My question was driven by Arne's comment that he would prefer DEC Basic
> over C for userland applications. If you are going to replace C, then
> you need a language that can do everything C can, and do it better.

Anything application wise you can do in C, I can duplicate in Basic, and many
times much easier.

Do programmers do their own memory management in Basic? Not if they don't have
to. But it can be done. Why? Because on VMS, playing around with memory is an
OS thing, not a language thing.

> That's certainly true for Pascal, but not true for DEC Basic based
> on what I see above. DEC Basic might be suitable for some less complex
> programs, but certainly not all of the userland programs.

Suitable is a nebulous term. Suitable for whom?

> For example, could you cleanly write a CDU replacement or a TPU
> replacement in DEC Basic ? I've never seen the source code for either
> of them, but I would expect both of those to use variable sized
> tree building and processing because of the parsing they do.

Just why do you think Basic cannot do this?

I will admit that VSI Basic has some issues. All of them are implementation
specific, not language specific. That is a rather important distinction.

--
David Froble Tel: 724-529-0450
Dave Froble Enterprises, Inc. E-Mail: davef@tsoft-inc.com
DFE Ultralights, Inc.
170 Grimplin Road
Vanderbilt, PA 15486

On 1/30/2022 7:09 PM, Simon Clubley wrote:
> On 2022-01-30, Arne Vajhøj <arne@vajhoej.dk> wrote:
>> On 1/30/2022 6:54 PM, Simon Clubley wrote:
>>> On 2022-01-29, Arne Vajhøj <arne@vajhoej.dk> wrote:
>>>> In this case Simon outlined a problem where Pascal and C are obvious
>>>> languages and me with no Basic experience wrote some Basic code - that
>>>> is almost ensure an "unsual style". Or to put it another way: I am
>>>> (or was) a Fortran programmer and Fortran programmers can program
>>>> in Fortran in any language. :-)
>>>
>>> Thanks for the demo program Arne.
>>>
>>> The approach you are forced to use in DEC Basic is way more ugly than
>>> doing it in C or Pascal.
>>
>> Ugly or just unfamiliar?
>
> Ugly because of all the tree management stuff you have to do for
> yourself that you get for free in C or Pascal.

What is all the tree management stuff?

When the node is inserted the code walks down from the top of the tree
find parent for the new node, update either the parents left or right
node "pointer" to point to the new node and both left and right
"pointer" of the new node is set to 0.

That is fundamentally what you will do in C or Pascal as well.

I expect the code in C or Pascal to look reasonable similar.

> In addition, there's the overhead of copying the tree everytime
> you run out of allocated spare space and need to extend it.

There is some source code overhead of having to code that
manual. And I agree that part is ugly.

Runtime there is no guarantee that the copying will actually
be more expensive than all the allocation/deallocation of
a traditional solution.

Arne

On 1/30/2022 7:14 PM, Simon Clubley wrote:
> On 2022-01-30, Arne Vajhøj <arne@vajhoej.dk> wrote:
>> On 1/30/2022 7:03 PM, Simon Clubley wrote:
>>> There's also the required copying of the
>>> current data every time you grow the tree.
>>
>> That is common practice in many languages for dynamic
>> sized data structures needing linear backing.
>>
>
> But elsewhere you have the choice of whether to use something
> like a Vector or if you need to build a tree structure yourself.
>
> Specifying the growth increment of a linear structure is also
> a tradeoff but you are not forced to use a linear structure if
> you can build real trees and that's a better choice.
>
> Simon.
>

Where do you come up with the idea that in Basic the nodes in a tree must be
linear? They rarely are. There usually are forward and backward pointers in a
linked list / tree. Logically linear, but not physically linear.

You're not appearing very knowledgeable Simon.

--
David Froble Tel: 724-529-0450
Dave Froble Enterprises, Inc. E-Mail: davef@tsoft-inc.com
DFE Ultralights, Inc.
170 Grimplin Road
Vanderbilt, PA 15486

On 1/30/2022 7:09 PM, Simon Clubley wrote:
> On 2022-01-30, Arne Vajhøj <arne@vajhoej.dk> wrote:
>> On 1/30/2022 6:54 PM, Simon Clubley wrote:
>>> On 2022-01-29, Arne Vajhøj <arne@vajhoej.dk> wrote:
>>>> In this case Simon outlined a problem where Pascal and C are obvious
>>>> languages and me with no Basic experience wrote some Basic code - that
>>>> is almost ensure an "unsual style". Or to put it another way: I am
>>>> (or was) a Fortran programmer and Fortran programmers can program
>>>> in Fortran in any language. :-)
>>>
>>> Thanks for the demo program Arne.
>>>
>>> The approach you are forced to use in DEC Basic is way more ugly than
>>> doing it in C or Pascal.
>>
>> Ugly or just unfamiliar?
>>
>
> Ugly because of all the tree management stuff you have to do for
> yourself that you get for free in C or Pascal.
>
> In addition, there's the overhead of copying the tree everytime
> you run out of allocated spare space and need to extend it.

Bullshit! Just not true.

--
David Froble Tel: 724-529-0450
Dave Froble Enterprises, Inc. E-Mail: davef@tsoft-inc.com
DFE Ultralights, Inc.
170 Grimplin Road
Vanderbilt, PA 15486

On 1/30/2022 6:45 PM, Simon Clubley wrote:
> For example, could you cleanly write a CDU replacement or a TPU
> replacement in DEC Basic ? I've never seen the source code for either
> of them, but I would expect both of those to use variable sized
> tree building and processing because of the parsing they do.

I think Basic could do the parsing and tree structure
fine.

But I would be skeptical about whether Basic is the right language
to actually do what those do. CDU must be messing around in P1
space. And TPU is actually is combo of compiler/interpreter
and editor.

Arne

On 1/30/2022 8:07 PM, Dave Froble wrote:
> On 1/30/2022 7:14 PM, Simon Clubley wrote:
>> On 2022-01-30, Arne Vajhøj <arne@vajhoej.dk> wrote:
>>> On 1/30/2022 7:03 PM, Simon Clubley wrote:
>>>>                            There's also the required copying of the
>>>> current data every time you grow the tree.
>>>
>>> That is common practice in many languages for dynamic
>>> sized data structures needing linear backing.
>>>
>>
>> But elsewhere you have the choice of whether to use something
>> like a Vector or if you need to build a tree structure yourself.
>>
>> Specifying the growth increment of a linear structure is also
>> a tradeoff but you are not forced to use a linear structure if
>> you can build real trees and that's a better choice.
>
> Where do you come up with the idea that in Basic the nodes in a tree
> must be linear?  They rarely are.  There usually are forward and
> backward pointers in a linked list / tree.  Logically linear, but not
> physically linear.

I would call my example for logical tree physical linear.

Arne