[REBOL] Encouraging functional programming Re:(3)

[carl]

Reasonable requests... we'll add them to our list.  (The simpler ones
will be implemented first.)

-Carl


At 11/29/99 08:35 AM -0600, you wrote:
[EMAIL PROTECTED] wrote:
 
 Let's see how it performs on a structure that is naturally recursive:
 
... nice code and stack crash deleted ...
 
 But:
 
... more deletions ...
 
 140 levels can hold maximum 2^139 + 2^138 + ... + 2^0 elements...
 
 I think running out of memory is a bigger problem than running out of
 stack space ! :))
 

EXCEPT that sometimes a recursive structure is composed from input
data not under the control of the programmer!  For example, building
a sort tree from pathologically ordered data can produce a 140-level
tree that contains only 141 leaves.

Of course the program can be re-written to continually rebalance the
tree, but means that the programmer is having to make a more complex
program to work around a limitation of the implementation -- NOT a
very friendly solution for the casual (or novice) programmer.

CONCRETE SUGGESTIONS:  Why not allow the programmer or user some more
control over stack size?  I suggest that REBOL would benefit from:

1)  A command-line argument allowing the stack size to be set to a
supplied value.  On a larger box, one could simply make the size
bigger to allow deeper recursion.  (As a side note, I recently
found that I could nest recursive calls deeper under w95 than
under Solaris, even though the Sun box had WAY more RAM.
("What a rebolting development THAT is!")

2)  A primitive function allowing running code to query the amount
of total and free stack space.  This would enable a script to
predict an impending stack crash and take preventive action,
rather than simply detecting the crash after the fact.
It would also be nice to have the same capabilitiy(ies) for
heap/string space, but I'm assuming more than I know about the
implementation of REBOL.  ;-)

3)  In the best of all possible worlds, REBOL would have both of
the above, PLUS a function to grow the stack/heap/whatever by
a specified amount of memory.  Of course that function would
fail gracefully if the environment didn't have sufficient
resources to let the interpreter grow.

How about it, REBOL wizards?  I realize that these may be non-trivial
changes (depending on how the interpreter is built) but I believe they
offer some real value, both to those of us who occasionally write
quick-and-dirty code and to those who deal with really complex or
large data structures.

-jn-
 

[REBOL] Encouraging functional programming Re:(3)

[dankelg8]

On Mon, 29 Nov 1999 [EMAIL PROTECTED] wrote:

 Gisle,
 
 What do you think of the following example?  I expect the 10 could be
 increased significantly, but I get tired of waiting.
 
 Jerry
 
 
  tree: array 0  for n 1 10 1 [insert tail tree 1.0 * n]
 == []
  length? tree
 == 10
  last tree
 == 10
 
 

Oh I'm sorry I shouldn't have named the function insert !!

Try replacing the above with 

tree: []
for n 1 10 1 [insert-tree tree 1.0 * n]

After renaming the insert function:

tree-insert: func [tree item][
any [
all [tree = [] reduce [[] item []]]
all [
item  tree/:node reduce 
[tree-insert tree/:left item tree/:node tree/:right]
]
reduce [tree/:left tree/:node tree-insert tree/:right item]
]
]


And you'll see a different result :)

Sorry for any confusion caused.

Gisle

[REBOL] Encouraging functional programming Re:(3)

[70740 . 503]

I think the following example shows that in some cases recursion is
undesirable.

Jerry

 testnr 1000
== 500500
 testr 1 0.0
** Internal Error: Stack overflow.
** Where: either n  0 [testr n - 1 x + n]
 testr 1000 0.0
== 500500

testnr: func [n]
[
   x: 0.0
   for i 1 n 1 [x: x + i]
   x
]

testr: func [n x]
[
   either n  0 [testr n - 1 x + n] [return x]
]

[REBOL] Encouraging functional programming Re:(3)

[wwink2]

My understanding was that tail recursion ( or its optimized implementation )
gives a (properly written) recursive program the efficiency of an
iterative program.  Thus it is a very desirable capability to build
into a language which is intended to use a lot of recursive
program structures. 







On Fri, 26 Nov 1999, you wrote:
 Was it Ingo who mentioned that tail recursion had been removed from the
 current REBOL implementation and asked when it would be returned? That
 should take care of the stack overflow problem. The problem is a result of
 an incomplete implementation of REBOL (missing tail recursion) and I don't
 think it makes a good argument regarding the degree to which REBOL supports
 functional programming.
 
 Elan
 
 If I've comprehended that correctly, a good language should eliminate tail
 recursion and replace it by iteration. This is a feature of most CommonLISP
 systems and Scheme.
 
 After all, recursion is more expensive than iteration and should be avoided
 whenever possible, and its always possible if the function calls are proper
 tail-recursive.
 
 Greetings,
 
 Erich