[R] Implementating streams in R
Gabriel Baud-Bovy
baud-bovy.gabriel at hsr.it
Tue Feb 3 11:40:19 CET 2004
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
More information about the R-help
mailing list