[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
> 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
More information about the R-help
mailing list