[R] Implementating streams in R

[Gabriel Baud-Bovy]

Dear all,

I have an implementation of streams in R. The current implementation of 
delay() and force() is
inspired from  the LISP implementation found in Part VI "Languages for AI 
problem solving" of
"Artificial Intelligence" by G. Luger.

I have tested it with the Fibonacci example in the same book (see examples 
below).  It works
but I do run into a problem when I try to generate fibonacci series more 
than 25 elements.

 > accumulate.into.list(25,fibonacci.stream(0,1))
Error in cons.stream(fibonacci1 + fibonacci2, 
fibonacci.stream(fibonacci2,  : evaluation is nested too deeply: infinite 
recursion?

Traceback show that the call stack has 101 elements at this point. What is 
the parameter
limiting the number of recursive calls to 100?  What is its relation to the 
"expressions" setting
in options()?

More fundamentally, I would appreciate any comment on this implementation 
or suggestion about
the best way of implementing streams in R.  My objective is to implement 
logic programming
interpreter in R as done in LISP by G.F.Luger in his book or by  Abelson & 
Sussman in "Structure
and Interpreation of Computer Program".

Thank you,

Gabriel


###
### Examples
###


 > fib<-fibonacci.stream(0,1)

Note that the  fibonacci.stream() function is a nonterminating recursive 
function. It works only because
of the delayed evaluation introduced by the delay() function in 
cons.stream() . It would not work if I
implemented streams as simple list (see example at the very end of this 
posting).

 > head.stream(fib)   # get the first element
[1] 1
 > tail.stream(fib)     # get the second element
[[1]]
[1] 2
[[2]]
function ()
expression
<environment: 00F343E0>

 > tail.stream(tail.stream(fib)) # get the third element
[[1]]
[1] 3
[[2]]
function ()
expression
<environment: 01958774>

 > accumulate.into.list(5,fibonacci.stream(0,1)) # construct a list with 
the 5 first Fibonacci numbers
 > accumulate.into.list(5,filter.odds(fibonacci.stream(0,1)))  # construct 
a list with the 5 first Fibonacci odd numbers


###
### Fibonaccy stream
###

fibonacci.stream<-function(fibonacci1,fibonacci2) {
         cons.stream(fibonacci1+fibonacci2,
                 fibonacci.stream(fibonacci2, fibonacci1+fibonacci2))
}

filter.odds<-function(stream) {
         if(is.even(head.stream(stream))) {
                 filter.odds(tail.stream(stream))
         } else {
                 cons.stream(head.stream(stream),filter.odds(tail.stream(stream)))
         }
}

accumulate.into.list<-function(n,stream) {
         if(n==0) {
                 NULL
         } else {
                 cons(head.stream(stream),
                         accumulate.into.list(n-1,tail.stream(stream)))
         }
}

is.even<-function(x) x%%2==0

###
### stream functions
###

delay<-function(expression) {
         as.function(alist(expression))
}

force<-function(function.closure) {
         function.closure()
}

cons.stream<-function(expression,stream) {
         list(expression,delay(stream))
}

head.stream<-function(stream) {
         stream[[1]]
}

tail.stream<-function(stream) {
         force(stream[[2]])
}


###
### lists
###

cons<-function(element,list) {
         c(list(element),list)
}

car<-function(list) {
         list[[1]]
}

cdr<-function(list)  {
         list[-1]
}

is.empty.list<-function(list) {
         length(list)==0
}

make.empty.list<-function() {
         vector(mode="list",length=0)
}



if(0) {

# This implementation of streams as simple lists (see definition of cons, 
car and cdr below) leads
# to an infinite recursion because fibonacci is a nonterminating recursive 
function and that both
# arguments are evaluated.

cons.stream<-function(expression,stream) cons(expression,stream)
head.stream<-function(stream) car(stream)
tail.stream<-function(stream) cdr(stream)

 > fibonacci.stream(0,1)
Error in cons(expression, stream) : evaluation is nested too deeply: 
infinite recursion?

}

--------------------------------------------------------------------
Gabriel Baud-Bovy
Faculty of Psychology
UHSR University
via Olgettina, 58	tel: (+39) 02 2643 4839
20132 Milan, Italy	fax: (+39) 02 2643 4892