[R] [newbie] stack operations, or functions with side effects (or both)

[William Dunlap]

Thanks for the improvements.  The main point in
my original post was that altering the arguments
of a function is a really bad thing to do in R
(except when using replacement functions).  A
function that alters other objects in the caller's
environment is also really bad.  By "bad" I mean
that such functions are not safe to use because
they alter things that are not theirs to alter and
thus can lead to incorrect results in a rather
unpredictable (to the user) fashion.

Objects with state, like stacks, are less bad but
they can cause problems when you decide to parallelize
your code (you need to synchronize the state across
the copies of the code).

The best code sticks with the functional paradigm that
most R functions have: data flows from a function's
arguments to its return value with no side effects or state
changes.

None of the above concerns cpu efficiency.  It is about
the programming efficiency of having reliable reusable code. 

Bill Dunlap
Spotfire, TIBCO Software
wdunlap tibco.com 

> -----Original Message-----
> From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org] On Behalf Of Martin Morgan
> Sent: Thursday, January 05, 2012 10:38 AM
> To: r-help at r-project.org; Tom Roche
> Subject: Re: [R] [newbie] stack operations, or functions with side effects (or both)
> 
> On 01/05/2012 09:18 AM, Tom Roche wrote:
> >
> > William Dunlap Wed, 4 Jan 2012 22:54:41 +0000
> >> R functions [can] use their enclosing environments to save state.
> >
> > Aha!
> >
> >> makeStack<- function () {
> >>    stack<- list()
> >>    list(pop = function() {
> >>      if (length(stack) == 0) { # get from an enclosing env.
> >>        retval<- NULL
> >>      } else {
> >>        retval<- stack[[length(stack)]] # get from an enclosing env.
> >>        stack<<- stack[-length(stack)] # assign in an enclosing env.
> >>      }
> >>      retval
> >>    }, push = function(x) {
> >>      stack[[length(stack) + 1]]<<- x # assign in an enclosing env.
> >>      invisible(x)
> >>    })
> >> }
> >
> > Thanks, that's quite clear.
> 
> One point is that subsetting with "[" or extending with
> stack[[length(stack) + 1]] triggers a copy of stack. Better to pre-allocate
> 
>     stack <- vector("list", 100)
>     curr <- 0L
> 
> and fill, e.g., push with
> 
>    curr <<- curr + 1L
>    stack[[curr]] <<- x
> 
> plus bounds check and perhaps growth when necessary.
> 
> >
> >> There are various encapsulations of this method in R. See, e.g.,
> >> "reference classes" or the "proto" package.
> >
> > I can't see a reference-class implementation, but I did find
> 
> Probably Bill was pointing to ?ReferenceClasses. My attempt at
> implementing a stack as a reference class led, ironically, to copying
> issues anyway (below; maybe there's a different implementation?)
> 
> Efficient R programming usually involves operations on vectors, rather
> than the iteration implied by a stack. This might change your conclusion
> that a stack-based solution is appropriate.
> 
> Martin
> 
> Reference class implementation
> 
> .Stack <- setRefClass("Stack",
>      fields=list(stack="list", curr="integer"),
>      methods=list(
>        initialize=function(stackSize=100L, ...) {
>            callSuper(stack=vector("list", stackSize), curr=0L, ...)
>        },
>        push=function(val) {
>            curr <<- curr + 1L
>            if (curr > length(stack))
>                ## double size; could be a bad choice
>                length(stack) <<- 2L * length(stack)
>            stack[[curr]] <<- val
>            invisible(val)
>        },
>        pop=function() {
>            if (curr == 0L)
>                NULL                      # sentinel: empty
>            else {
>                val <- stack[[curr]]
>                curr <<- curr - 1L
>                val
>            }
>        },
>        show=function() {
>            cat("Class:", class(.self), "\n")
>            cat("current size:", .self$curr, "\n")
>            cat("maximum size:", length(.self$stack), "\n")
>            if (.self$curr) {
>                cat("head:\n")
>                print(.self$stack[[1L]])
>            }
>        }))
> 
> and then
> 
>  > stack <- .Stack$new()
>  > tracemem(stack$stack)
> [1] "<0x1afc090>"
>  > stack$push(10)
> tracemem[0x1afc090 -> 0x9283a0]: <Anonymous>
> tracemem[0x9283a0 -> 0xb96450]: <Anonymous> <Anonymous>
>  > stack$push(10)
> tracemem[0xb96450 -> 0x1b2a7d0]: <Anonymous> <Anonymous>
>  > stack
> Class: Stack
> current size: 2
> maximum size: 100
> head:
> [1] 10
>  > while (!is.null(val <- stack$pop()))
> +     cat("val:", val, "\n")
> val: 10
> val: 10
> 
> >
> > https://stat.ethz.ch/pipermail/r-help/2010-March/230353.html (slightly edited)
> >> [Subject:] [R] Stack type
> >> [From:] Gabor Grothendieck ggrothendieck at gmail.com
> >> [Date:] Tue Mar 2 14:33:43 CET 2010
> >
> >> library(proto)
> >> Stack<- proto(new = function(.) proto(Stack,
> >>    stack = NULL,
> >>    push = function(., el) { .$stack<- c(list(el), .$stack) },
> >>    pop = function(.) {
> >        stopifnot(length(.$stack)>  0)
> >>      out<- .$stack[[1]]
> >>      .$stack[[1]]<- NULL
> >>      out
> >> }))
> >
> >> mystack<- Stack$new()
> >> mystack$push( 1 )
> >> mystack$push( letters )
> >> mystack$pop()
> >> mystack$pop()
> >> mystack$pop() # gives an error
> >
> > Thanks again! Tom Roche<Tom_Roche at pobox.com>
> >
> > ______________________________________________
> > R-help at r-project.org mailing list
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> > and provide commented, minimal, self-contained, reproducible code.
> 
> 
> --
> Computational Biology
> Fred Hutchinson Cancer Research Center
> 1100 Fairview Ave. N. PO Box 19024 Seattle, WA 98109
> 
> Location: M1-B861
> Telephone: 206 667-2793
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.