1. limitations of sequences, revisited
This is just a bit more about my concerns regarding complex data structures
represented by sequences.
Mike Nelson answered my queries by offering a couple of tools:
>where z is root[RIGHTCHILD][LEFTCHILD][LEFTCHILD][RIGHTCHILD][VALUE]
>... is there any way of modifying z without hardcoding that
>particular expression? There does not appear to be a way of "aliasing"
>that nasty expression, or saving some sort of bookmark to z that I can >
>use later to access it.
<begin Mike's code>
sequence bookmark
-- then to retrieve:
function subscript(sequence Param,sequence subsc)
object returnValue
returnValue=Param
for i=1 to length(subsc) do
returnValue=returnValue[subsc[i]]
end for
return returnValue
end function
object val
val=subscript(root,bookmark)
<end Mike's code>
Ah, so then can I write:
subscript(root, bookmark) = 'x'
No! And my "complaint" was that I cannot use such techniques to MODIFY a
value deeply buried within the structure. I could, for example. try this:
sequence bookmark
function setNodeValue(sequence myTree, sequence bookmark, object newValue)
if length(bookmark) = 0 then
puts(1, "Ha ha, you fool!\n")
abort(1)
elsif length(bookmark) = 1 then
myTree[bookmark[1]] = newValue
elsif length(bookmark) = 2 then
myTree[bookmark[1]][bookmark[2]] = newValue
elsif length(bookmark) = 3 then
myTree[bookmark[1]][bookmark[2]][bookmark[3]] = newValue
...
elsif length(bookmark) = INFINITY then
-- Where should one set an arbitrary limit on the depth of the tree?
end if
end function
I can see no way to accomplish the same thing by iteration or recursion,
because the only way to reference a sequence element for assignment is by
subscripting. If I had a pointer into the tree, and "address of" (&) and
dereferencing (*) operators as in C, I could simply write:
nodePtr = ¤tNode
...
*nodePtr = newValue
but Euphoria has no such mechanism...unless one uses Jeff Fielding's pointer
scheme, or something similar, to build the tree. Bottom line is, pointers
are needed sometimes.
If I write,
val = myTree[RIGHTCHILD][LEFTCHILD][LEFTCHILD][RIGHTCHILD]
or anything equivalent, then I can use val instead of all that other,
wherever I need the value of that particular node. However, I can take no
such shortcut when it comes to manipulating the value inside the tree at
that location. Coming from a C background, where this is not the case, this
functional asymmetry seems unattractive.
Forget "pointer arithmetic." I just want a way to assign a value to a node
whose location within my tree (or any complex, multidimensional data
structure), whose location I can easily bookmark at point a for later
manipulation at point b, somewhat later in my program. This seems to be a
fairly straightforward need and request, but the more thoroughly one
elminates all vestiges of pointers and aliasing from a language, the more
difficult it becomes to fulfill it.
>show me a routine, for an arbitrary tree represented by
>nested sequences, to change all instances of "g" to "w".
The function Mike offered to accomplish this would appear to work (on
inspection, I haven't actually tried running it). What I learn from this is
that the approach I would need to take would be tagging, rather than
bookmarking; while building or inspecting a tree, one could tag the nodes of
interest, and then use a recursive function later in life to find and modify
the tagged nodes (or just clear the tags, as the case may be).
So in the absence of pointers and aliasing, a functional approach is
required. Interesting. It still seems, though, that it would be a lot more
efficient to have a way of external bookmarking, through some sort of
pointer or alias.
To illustrate what I mean by aliasing, suppose that Euphoria had the ability
to interpret strings within a program as code. Call the procedure that would
do this "exec". Then one could write something like this:
sequence bookmark, alias, assignStmt
...
-- Assume bookmark={RIGHTCHILD,LEFTCHILD,LEFTCHILD,RIGHTCHILD}
alias = "myTree"
for index = 1 to length(bookmark) do
alias &= "[" & sprint(bookmark[index]) & "]"
end for
...
assignStmt = alias & "=" & sprint(newValue)
exec(assignStmt)
That is one possible approach that avoids pointers and does not incur the
overhead of a recursive function to find the node when you want to do the
assignment. (I am here using "overhead" as much in the sense of having to
write and deal with the code, as in terms of language / program peformance.
In code complexity, this approach would be positioned between the earlier
C-like pointer example and the tagging / recursive function approach.)
Are there any computer scientists here who are familiar with the arguments
pro and con dynamic code?
Rob, there seems to be some interest in dynamic code. Have you considered
adding it to the language? (It is a technique I have wanted to use, from
time to time. APL actually implements it, and when I programmed in that
language, I used it, sparingly. BTW, APL does not have pointers....)
I find all this extremely interesting. It's part of learning Euphoria and
acquiring the "Eu mindset." It's also part of evolving the Euphoria
programming environment.
George
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com
2. Re: limitations of sequences, revisited
On Wed, 27 Dec 2000, George Henry wrote:
> No! And my "complaint" was that I cannot use such techniques to MODIFY a
> value deeply buried within the structure. I could, for example. try this:
>
> sequence bookmark
> bookmark={RIGHTCHILD,LEFTCHILD,LEFTCHILD,RIGHTCHILD}
>
> function setNodeValue(sequence myTree, sequence bookmark, object newValue)
> if length(bookmark) = 0 then
> puts(1, "Ha ha, you fool!\n")
> abort(1)
> elsif length(bookmark) = 1 then
> myTree[bookmark[1]] = newValue
> elsif length(bookmark) = 2 then
> myTree[bookmark[1]][bookmark[2]] = newValue
> elsif length(bookmark) = 3 then
> myTree[bookmark[1]][bookmark[2]][bookmark[3]] = newValue
> ...
> elsif length(bookmark) = INFINITY then
> -- Where should one set an arbitrary limit on the depth of the tree?
> end if
> end function
>
> I can see no way to accomplish the same thing by iteration or recursion,
> because the only way to reference a sequence element for assignment is by
> subscripting. If I had a pointer into the tree, and "address of" (&) and
> dereferencing (*) operators as in C, I could simply write:
>
> George
It's late, and I'm kind of tired right now... but there is actually a way
to implement a setNodeValue function recursively:
function setNodeValue(sequence myTree, sequence bookmark, object newValue)
integer branch
if length(bookmark) then
branch = bookmark[1]
myTree[branch] = setNodeValue(myTree[branch],
bookmark[2..length(bookmark), newValue)
return myTree
else
return newValue
end if
end function
Of course, this function could be optimized... but it should work.
Jeff Fielding
3. Re: limitations of sequences, revisited
Hi George,
After I saw your last post I wrote the little include below. In the
meantime, I noticed, Jeff already answered your questions. I have very
little to add, except it's a pity you did not follow Kat's advice: my
associative lists module does not deal with binary trees specifically,
but its 'deep' set function uses exactly the same recursion technique
as Jeff's routine.
By now, I hope, you have one less reason to want your beloved pointers
back. jiri
-- btree.e
-- jbabor at paradise.net.nz
-- 00-12-28
global function fetch(object tree, sequence path)
for i=1 to length(path) do
tree = tree[path[i]]
end for
return tree
end function
global function set(object tree, sequence path, object val)
integer branch,len
len = length(path)
if len then
branch = path[1]
tree[branch] = set(tree[branch], path[2..len], val)
return tree
else
return val
end if
end function
-- test --------------------------------------------------------------
object t
t = {{{1.1, {{{2,3,-4}}, 56}}, -3}, {{{{8}, {-5}}, {1}}, {-2, {}}}}
? fetch(t, {}) -- returns original tree
? fetch(t, {1})
? fetch(t, {1,2})
? fetch(t, {2,1})
? fetch(t, {1,1,2,1,1})
? set(t, {2,2,2}, 77)
? set(t, {1,1,2}, 88)
? set(t, {1},99)
? fetch(set(t, {1}, 66), {1})
----- Original Message -----
From: "George Henry" <ghenryca at HOTMAIL.COM>
To: <EUPHORIA at LISTSERV.MUOHIO.EDU>
Sent: Wednesday, December 27, 2000 6:57 PM
Subject: limitations of sequences, revisited
> This is just a bit more about my concerns regarding complex data
structures
> represented by sequences.
>
> Mike Nelson answered my queries by offering a couple of tools:
>
> >where z is
> >... is there any way of modifying z without hardcoding that
> >particular expression? There does not appear to be a way of
"aliasing"
> >that nasty expression, or saving some sort of bookmark to z that I
can >
> >use later to access it.
>
> <begin Mike's code>
> sequence bookmark
> bookmark={RIGHTCHILD,LEFTCHILD,LEFTCHILD,RIGHTCHILD,VALUE}
>
> -- then to retrieve:
>
> function subscript(sequence Param,sequence subsc)
> object returnValue
> returnValue=Param
> for i=1 to length(subsc) do
> returnValue=returnValue[subsc[i]]
> end for
> return returnValue
> end function
>
> object val
> val=subscript(root,bookmark)
> <end Mike's code>
>
> Ah, so then can I write:
>
> subscript(root, bookmark) = 'x'
>
> No! And my "complaint" was that I cannot use such techniques to
MODIFY a
> value deeply buried within the structure. I could, for example. try
this:
>
> sequence bookmark
> bookmark={RIGHTCHILD,LEFTCHILD,LEFTCHILD,RIGHTCHILD}
>
> function setNodeValue(sequence myTree, sequence bookmark, object
newValue)
> if length(bookmark) = 0 then
> puts(1, "Ha ha, you fool!\n")
> abort(1)
> elsif length(bookmark) = 1 then
> myTree[bookmark[1]] = newValue
> elsif length(bookmark) = 2 then
> myTree[bookmark[1]][bookmark[2]] = newValue
> elsif length(bookmark) = 3 then
> myTree[bookmark[1]][bookmark[2]][bookmark[3]] = newValue
> ...
> elsif length(bookmark) = INFINITY then
> -- Where should one set an arbitrary limit on the depth of the
tree?
> end if
> end function
>
> I can see no way to accomplish the same thing by iteration or
recursion,
> because the only way to reference a sequence element for assignment
is by
> subscripting. If I had a pointer into the tree, and "address of" (&)
and
> dereferencing (*) operators as in C, I could simply write:
>
> nodePtr = ¤tNode
> ...
> *nodePtr = newValue
>
> but Euphoria has no such mechanism...unless one uses Jeff Fielding's
pointer
> scheme, or something similar, to build the tree. Bottom line is,
pointers
> are needed sometimes.
>
> If I write,
>
> val = myTree[RIGHTCHILD][LEFTCHILD][LEFTCHILD][RIGHTCHILD]
>
> or anything equivalent, then I can use val instead of all that
other,
> wherever I need the value of that particular node. However, I can
take no
> such shortcut when it comes to manipulating the value inside the
tree at
> that location. Coming from a C background, where this is not the
case, this
> functional asymmetry seems unattractive.
>
> Forget "pointer arithmetic." I just want a way to assign a value to
a node
> whose location within my tree (or any complex, multidimensional data
> structure), whose location I can easily bookmark at point a for
later
> manipulation at point b, somewhat later in my program. This seems to
be a
> fairly straightforward need and request, but the more thoroughly one
> elminates all vestiges of pointers and aliasing from a language, the
more
> difficult it becomes to fulfill it.
>
> >show me a routine, for an arbitrary tree represented by
> >nested sequences, to change all instances of "g" to "w".
>
> The function Mike offered to accomplish this would appear to work
(on
> inspection, I haven't actually tried running it). What I learn from
this is
> that the approach I would need to take would be tagging, rather than
> bookmarking; while building or inspecting a tree, one could tag the
nodes of
> interest, and then use a recursive function later in life to find
and modify
> the tagged nodes (or just clear the tags, as the case may be).
>
> So in the absence of pointers and aliasing, a functional approach is
> required. Interesting. It still seems, though, that it would be a
lot more
> efficient to have a way of external bookmarking, through some sort
of
> pointer or alias.
>
> To illustrate what I mean by aliasing, suppose that Euphoria had the
ability
> to interpret strings within a program as code. Call the procedure
that would
> do this "exec". Then one could write something like this:
>
> sequence bookmark, alias, assignStmt
> ...
> -- Assume bookmark={RIGHTCHILD,LEFTCHILD,LEFTCHILD,RIGHTCHILD}
> alias = "myTree"
> for index = 1 to length(bookmark) do
> alias &= "[" & sprint(bookmark[index]) & "]"
> end for
> ...
> assignStmt = alias & "=" & sprint(newValue)
> exec(assignStmt)
>
> That is one possible approach that avoids pointers and does not
incur the
> overhead of a recursive function to find the node when you want to
do the
> assignment. (I am here using "overhead" as much in the sense of
having to
> write and deal with the code, as in terms of language / program
peformance.
> In code complexity, this approach would be positioned between the
earlier
> C-like pointer example and the tagging / recursive function
approach.)
>
> Are there any computer scientists here who are familiar with the
arguments
> pro and con dynamic code?
>
> Rob, there seems to be some interest in dynamic code. Have you
considered
> adding it to the language? (It is a technique I have wanted to use,
from
> time to time. APL actually implements it, and when I programmed in
that
> language, I used it, sparingly. BTW, APL does not have pointers....)
>
> I find all this extremely interesting. It's part of learning
Euphoria and
> acquiring the "Eu mindset." It's also part of evolving the Euphoria
> programming environment.
>
> George
> _________________________________________________________________
> Get your FREE download of MSN Explorer at http://explorer.msn.com
>
4. Re: limitations of sequences, revisited
George Henry wrote:
> No! And my "complaint" was that I cannot
> use such techniques to MODIFY a value deeply
> buried within the structure.
I think the confusion stems from the fact that, in Euphoria, it's often
trivial to embed all the data in the same structure. And it's often
convenient to do just that.
But for cases where this is problematic (like your example), you can
trivially model the code as it is done in C by using indexes instead of
pointers.
For example, you could create the tree as an array of tuples:
constant
DATA = 1,
LEFT = 2,
RIGHT = 3
Instead of storing a subtree in the left and right nodes, store the index to
the node. Here's a trivial example showing a binary tree for the data values
"a", "b", "c" and "d":
{
{ "b", 2, 3 },
{ "a", 0, 0 },
{ "c", 0, 4 },
{ "d", 0, 0 }
}
Each node of the tree can be identified with a single index.
Or you could choose to seperate the data from the structure. The following
example is the same as the prior, but instead of placing the data in the
structure, indexes to the data (which is placed in another structure) are
used:
-- structure
{ { 1, 2, 3 },
{ 2, 0, 0 },
{ 3, 0, 4 },
{ 4, 0, 0 }
}
-- data
{ "b", "a", "c", "d" }
Another option is to keep the embedded tree structure, but store the data in
a seperate structure. The following example embeds a tree in each node, but
stores the data in a seperate structure. Instead of storing the data in the
tree, the first element of the tuple contains an index to the data:
{ index to data, left node, right node }
-- the tree
{1, {2, {}, {}}, {3, {}, {4, {}, {}}} }
-- the data
{ "b", "a", "c", "d" }
In any event, by either flattening the structure and using indexes, or
storing data in a second sequence and referencing them with indexes, you can
accomplish what you want without having to resort to pointers.
I hope this helps!
-- David Cuny
5. Re: limitations of sequences, revisited
Thanks Jiri and Jeff, for your essentially identical solutions to my
recursive assignment problem. I can see that it will work. I'm just not used
to using recursion that way.
>By now, I hope, you have one less reason to want your beloved pointers
back. jiri
Actually, I don't love pointers, I just like the convenience that they
sometimes provide. And after using them freely for quite a few years, the
parts of my brain that could easily and quickly think of non-pointer
solutions to certain classes of problems appear to have atrophied. 8^)
<Jeff's function>
function setNodeValue(sequence myTree, sequence bookmark, object newValue)
integer branch
if length(bookmark) then
branch = bookmark[1]
myTree[branch] = setNodeValue(myTree[branch],
bookmark[2..length(bookmark)], newValue)
return myTree
else
return newValue
end if
end function
<Jiri's function>
global function set(object tree, sequence path, object val)
integer branch,len
len = length(path)
if len then
branch = path[1]
tree[branch] = set(tree[branch], path[2..len], val)
return tree
else
return val
end if
end function
<end functions>
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com
6. Re: limitations of sequences, revisited
George Henry writes:
> If I had a pointer into the tree, and "address of" (&) and
> dereferencing (*) operators as in C, I could simply write:
> nodePtr = ¤tNode
> ...
> *nodePtr = newValue
> but Euphoria has no such mechanism...
> unless one uses Jeff Fielding's pointer
> scheme, or something similar, to build the tree.
> Bottom line is, pointers are needed sometimes.
Jiri and others have shown how to access
a tree that's implemented as a nested sequence.
They've provided recursive functions for retrieving
and setting nodes at any level in the tree.
If you are uncomfortable with using these functions,
you can implement a tree in a manner similar to
what I think Jeff Fielding is doing. In that case
all you need is an index into a flat (linear)
sequence to identify a node. You can use this index
just as you would use a pointer in C. It gives you quick
random access for getting and setting the node's data.
It's no harder than what you'd have to do in C.
In fact, you can take almost any C code that
uses pointers, and rewrite it in Euphoria
using indexes into a sequence. Indexes are safer
than pointers since Euphoria gives you subscript
checking, while C lets you crash and burn.
Often there's a better, more high-level, way of
implementing C data structures in Euphoria, provided you
understand the overall purpose of the code.
I don't think you have to worry that there are data structures
that you won't be able to emulate in Euphoria.
> Rob, there seems to be some interest in dynamic code.
> Have you considered adding it to the language?
> (It is a technique I have wanted to use, from time to time.
> APL actually implements it, and when I programmed
> in that language, I used it, sparingly. BTW, APL
> does not have pointers....)
Yes, I've considered it many times.
I also used it in APL, sparingly.
I wanted to use it a lot more in APL, but I could never
think of any good use for it, other than a few oddities.
It would be very difficult to add to the Euphoria interpreter,
and even harder to add to the translator.
Regards,
Rob Craig
Rapid Deployment Software
http://www.RapidEuphoria.com
7. Re: limitations of sequences, revisited
On 27 Dec 2000, at 12:18, Robert Craig wrote:
>
> > Rob, there seems to be some interest in dynamic code.
> > Have you considered adding it to the language?
> > (It is a technique I have wanted to use, from time to time.
> > APL actually implements it, and when I programmed
> > in that language, I used it, sparingly. BTW, APL
> > does not have pointers....)
>
> Yes, I've considered it many times.
> I also used it in APL, sparingly.
> I wanted to use it a lot more in APL, but I could never
> think of any good use for it, other than a few oddities.
> It would be very difficult to add to the Euphoria interpreter,
> and even harder to add to the translator.
I vote for it too.
But lets get a "goto" first. 
Kat
8. Re: limitations of sequences, revisited
George Henry wrote:
<snip>
>
> Mike Nelson answered my queries by offering a couple of tools:
>
> >where z is root[RIGHTCHILD][LEFTCHILD][LEFTCHILD][RIGHTCHILD][VALUE]
> >... is there any way of modifying z without hardcoding that
> >particular expression? There does not appear to be a way of "aliasing"
> >that nasty expression, or saving some sort of bookmark to z that I can >
> >use later to access it.
>
> <begin Mike's code>
> sequence bookmark
> bookmark={RIGHTCHILD,LEFTCHILD,LEFTCHILD,RIGHTCHILD,VALUE}
>
> -- then to retrieve:
>
> function subscript(sequence Param,sequence subsc)
> object returnValue
> returnValue=Param
> for i=1 to length(subsc) do
> returnValue=returnValue[subsc[i]]
> end for
> return returnValue
> end function
>
> object val
> val=subscript(root,bookmark)
> <end Mike's code>
>
> Ah, so then can I write:
>
> subscript(root, bookmark) = 'x'
>
> No! And my "complaint" was that I cannot use such techniques to MODIFY a
> value deeply buried within the structure. I could, for example. try this:
>
> sequence bookmark
> bookmark={RIGHTCHILD,LEFTCHILD,LEFTCHILD,RIGHTCHILD}
>
Here's a solution in the style of subscript():
function modify_subscript(sequence seq,sequence sub,object val)
integer len
len=length(sub)
if len>1 then
seq[sub[1]]=modify_subscript(seq[sub[1]],sub[2..len],val)
elsif len=1 then
seq[sub[1]]=val
end if
return seq
end function
then we can write:
root=modify_subscript(root,bookmark,newvalue)
The use of recursion handles the modifcations without needing advance
knowledge of the sequence depth. BTW, recursion is fairly cheap in
Euphoria.
Perhaps the functions would be better named get_subscript and set_subscript.
-- Mike Nelson
9. Re: limitations of sequences, revisited
I appreciate every bit of the code snippets by Jiri and Jeff
I have a new outlook and so many new idea for my codeing.
I never fully understood the power that Euphoria has useing
code this way.
THANKS
euman
10. Re: limitations of sequences, revisited
<Repost from Re: Learn DOS or Win32 first?>
Explore the sequence, it's a fantastic data type, just when you
think you've seen it all, you find another way to use one.
</Repost>
Good advice for newbies, no?
Graeme.
----------------------------------------------------
11. Re: limitations of sequences, revisited
On 27 Dec 2000, at 11:30, Euman wrote:
> I appreciate every bit of the code snippets by Jiri and Jeff
> I have a new outlook and so many new idea for my codeing.
>
> I never fully understood the power that Euphoria has useing
> code this way.
>
> THANKS
> euman
I read them all too, and save them. Sometimes these code bits just blow
my lil mind. Thanks from me too, everyone.
Kat
