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
>
|
Not Categorized, Please Help
|
|
