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
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()?There isn't one. The limit is on nesting expressions, as given in options(). One call may generate several expressions, though, and your calls probably generate 5 each. -- Brian D. Ripley, ripley at stats.ox.ac.uk Professor of Applied Statistics, http://www.stats.ox.ac.uk/~ripley/ University of Oxford, Tel: +44 1865 272861 (self) 1 South Parks Road, +44 1865 272866 (PA) Oxford OX1 3TG, UK Fax: +44 1865 272595
On Tue, 03 Feb 2004 11:40:19 +0100, you wrote:>Dear all, > >I have an implementation of streams in R....>More fundamentally, I would appreciate any comment on this implementation >or suggestion about >the best way of implementing streams in R.Could you describe in a language-independent way what you mean by "streams"? My understanding of the word is matches S "connections", which are already there. Duncan Murdoch
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