[R] Implementating streams in R

Luke Tierney luke at stat.uiowa.edu
Tue Feb 3 14:16:38 CET 2004

```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
> 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) {
>                  filter.odds(tail.stream(stream))
>          } else {
>          }
> }
>
> accumulate.into.list<-function(n,stream) {
>          if(n==0) {
>                  NULL
>          } else {
>                          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))
> }
>
>          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)
> 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
>

--
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

```