OpenEuphoria

limitations of sequences, revisited

• Posted by George Henry <ghenryca at HOTMAIL.COM> Dec 27, 2000
• 650 views

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 = &currentNode
...
*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