[R] Implementating streams in R

[Luke Tierney]

I worked on this a bit a while back for a possible article for Rnews
that won't get written anytime soon.  I've put a snapshot in

	http://www.stat.uiowa.edu/~luke/R/lazy/

It is based on examples in Paulson's ML book and Abelson and Susman;
the overall design seems similar to the one you have but the details
differ.  Hope it's of some use.

luke

On Tue, 3 Feb 2004, Gabriel Baud-Bovy wrote:

> 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
> 
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://www.stat.math.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
> 

-- 
Luke Tierney
University of Iowa                  Phone:             319-335-3386
Department of Statistics and        Fax:               319-335-3017
   Actuarial Science
241 Schaeffer Hall                  email:      luke at stat.uiowa.edu
Iowa City, IA 52242                 WWW:  http://www.stat.uiowa.edu