From: Wang Yin
Subject: What's the CL equivalent of Scheme's letrec?
Date: Fri, 24 Oct 2003 14:21:12 +0000
Message-ID: <m3ismeaf8n.fsf@wangyin.com>

Hi,

Question again :)

I'm trying to do some stream processing in my real program just like
that described in SICP chapter 3.

Note this "stream" is not string stream or I/O stream in CL.


I translated some of my Scheme stream code into CL:

(defun memo-proc (proc)
  (let ((already-run? nil) (result nil))
    (lambda ()
      (if (not already-run?)
          (progn
            (setf result (funcall proc))
            (setf already-run? t)
            result)
          result))))

(defmacro delay (&rest body)
  `(memo-proc (lambda () ,@body)))

(defun force (delay)
  "Do a delayed computation, or fetch its previously-computed value."
  (funcall delay))

(defvar *the-empty-stream* nil)
(defun stream-null? (s) (null s))

(defmacro cons-stream (a b)
  `(cons ,a (delay ,b)))

(defun stream-car (stream) (car stream))

(defun stream-cdr (stream) (force (cdr stream)))


;;; useful extensions for stream operation
(defun stream-ref (s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(defun stream-for-each (proc s)
  (if (stream-null? s)
      'done
    (progn (funcall proc (stream-car s))
           (stream-for-each proc (stream-cdr s)))))


(defun stream-filter (pred stream)
  (cond ((stream-null? stream) *the-empty-stream*)
        ((funcall pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (t (stream-filter pred (stream-cdr stream)))))

(defun add-streams (s1 s2)
  (stream-map #'+ s1 s2))

(defun mul-streams (s1 s2)
  (stream-map #'* s1 s2))


....


Finally I reached this:

(define (partial-sums s)
  (letrec ((p (cons-stream (stream-car s)
                           (add-streams p (stream-cdr s)))))
    p))


I don't know how to express this letrec in CL. I tried to express like
this:


(defun partial-sums (s)
  (let ((p nil))
    (setf p (cons-stream (stream-car s)
                         (add-streams p (stream-cdr s))))
    p))

But after doing that, p becomes globally visible!
That should not happen. 
So my question is how to get the same results as Scheme's letrec?
Thanks.


Here is more code for experiments:


(defun scale-stream (stream factor)
  (stream-map #'(lambda (x) (* x factor)) stream))


(defun stream-map (proc &rest argstreams)
  (if (stream-null? (car argstreams))
      *the-empty-stream*
    (cons-stream
     (apply proc (mapcar #'stream-car argstreams))
     (apply #'stream-map
            (cons proc (mapcar #'stream-cdr argstreams))))))


(defun list->stream (l)
  (if (null l) *the-empty-stream*
      (cons-stream (car l)
                   (list->stream (cdr l)))))

(defun display-stream (s &optional (n nil))
  (if (null n)
      (stream-for-each #'print s)
    (labels ((peek-stream (s n)
                  (print (stream-car s))
                  (if (and (not (stream-null? (stream-cdr s))) (> n 1)) 
                      (peek-stream (stream-cdr s) (- n 1)))))
      (peek-stream s n))))

;; (display-stream *ones* 10)

;; (setf *ones* (cons-stream 1 *ones*))

(defun integers-starting-from (n)
  (cons-stream n (integers-starting-from (+ n 1))))



(defun stream-enumerate-interval (low high)
  (if (> low high)
      *the-empty-stream*
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))


(setf s1 (stream-enumerate-interval 1 100))
(setf s2 (stream-filter #'oddp s1))
(setf sum1 (partial-sums s2))
(setf s3 (scale-stream s1 3))
(setf s4 (list->stream '(3 "haha" 'yes 3433 34)))

(display-stream sum1 10)



-- 
Yin Wang,
EDA Lab,
Deparment of Computer Science and Technology,
Tsinghua University,
100084
Beijing China

• Re: What's the CL equivalent of Scheme's letrec? Joe Marshall
  • Re: What's the CL equivalent of Scheme's letrec? Erann Gat
• Re: What's the CL equivalent of Scheme's letrec? Barry Margolin
• Re: What's the CL equivalent of Scheme's letrec? Pascal Costanza
  • Re: What's the CL equivalent of Scheme's letrec? Wang Yin
    • Re: What's the CL equivalent of Scheme's letrec? ······@us.ibm.com
      • Re: What's the CL equivalent of Scheme's letrec? Wang Yin
        • Re: What's the CL equivalent of Scheme's letrec? Marco Antoniotti
    • Re: What's the CL equivalent of Scheme's letrec? Marco Antoniotti

From: Joe Marshall
Subject: Re: What's the CL equivalent of Scheme's letrec?
Date: Fri, 24 Oct 2003 15:58:03 +0000
Message-ID: <7k2utypg.fsf@ccs.neu.edu>

Wang Yin <··@wangyin.com> writes:

> Finally I reached this:
>
> (define (partial-sums s)
>   (letrec ((p (cons-stream (stream-car s)
>                            (add-streams p (stream-cdr s)))))
>     p))
>
>
> I don't know how to express this letrec in CL. I tried to express like
> this:
>
>
> (defun partial-sums (s)
>   (let ((p nil))
>     (setf p (cons-stream (stream-car s)
>                          (add-streams p (stream-cdr s))))
>     p))
>
> But after doing that, p becomes globally visible!
> That should not happen. 

I'm sure you accidentally did something that proclaimed P to be
special.  Restart your lisp and try this again.

From: Erann Gat
Subject: Re: What's the CL equivalent of Scheme's letrec?
Date: Fri, 24 Oct 2003 17:11:47 +0000
Message-ID: <spammers_must_die-2410031011470001@k-137-79-50-101.jpl.nasa.gov>

In article <············@ccs.neu.edu>, Joe Marshall <···@ccs.neu.edu> wrote:

> Wang Yin <··@wangyin.com> writes:
> 
> > Finally I reached this:
> >
> > (define (partial-sums s)
> >   (letrec ((p (cons-stream (stream-car s)
> >                            (add-streams p (stream-cdr s)))))
> >     p))
> >
> >
> > I don't know how to express this letrec in CL. I tried to express like
> > this:
> >
> >
> > (defun partial-sums (s)
> >   (let ((p nil))
> >     (setf p (cons-stream (stream-car s)
> >                          (add-streams p (stream-cdr s))))
> >     p))
> >
> > But after doing that, p becomes globally visible!
> > That should not happen. 
> 
> I'm sure you accidentally did something that proclaimed P to be
> special.  Restart your lisp and try this again.

Or (unintern 'p) and try again.

E.

From: Barry Margolin
Subject: Re: What's the CL equivalent of Scheme's letrec?
Date: Fri, 24 Oct 2003 15:15:31 +0000
Message-ID: <nmbmb.217$lK3.82@news.level3.com>

In article <··············@wangyin.com>, Wang Yin  <··@wangyin.com> wrote:
>Finally I reached this:
>
>(define (partial-sums s)
>  (letrec ((p (cons-stream (stream-car s)
>                           (add-streams p (stream-cdr s)))))
>    p))
>
>
>I don't know how to express this letrec in CL. I tried to express like
>this:

I think this might be it, but I'm not sure:

(defun partial-sums (s)
  (labels ((p ()
             (lambda () (cons-stream (stream-car s)
                                     (add-streams #'p (stream-cdr s))))))
    #'p))

-- 
Barry Margolin, ··············@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.

From: Pascal Costanza
Subject: Re: What's the CL equivalent of Scheme's letrec?
Date: Fri, 24 Oct 2003 14:58:27 +0000
Message-ID: <bnbemk$p74$2@f1node01.rhrz.uni-bonn.de>

Wang Yin wrote:
> Hi,
> 
> Question again :)

Answer: labels :)


Pascal

-- 
Pascal Costanza               University of Bonn
···············@web.de        Institute of Computer Science III
http://www.pascalcostanza.de  R�merstr. 164, D-53117 Bonn (Germany)

From: Wang Yin
Subject: Re: What's the CL equivalent of Scheme's letrec?
Date: Fri, 24 Oct 2003 15:20:22 +0000
Message-ID: <m3smliek7d.fsf@wangyin.com>

But it seems labels can only bind function bodies.

If I do like this:

(defun partial-sums (s)
  (labels ((p (cons-stream (stream-car s)
                           (add-streams p (stream-cdr s)))))
    p))

I got the following error:

Lambda-variable is not a symbol: (STREAM-CAR S).
Error flushed ...


I tried to solve the problem with 

(defun partial-sums (s)
  (let ((p '<undefined>))
    (let ((temp (cons-stream (stream-car s)
                             (add-streams p (stream-cdr s)))))
      (setf p temp))
    p))

just as the Scheme macro does. It works.

If there is not equivalent of letrec in CL. I'd like to write a macro
myself :)


-- 
Yin Wang,
EDA Lab,
Deparment of Computer Science and Technology,
Tsinghua University,
100084
Beijing China

From: ······@us.ibm.com
Subject: Re: What's the CL equivalent of Scheme's letrec?
Date: Fri, 24 Oct 2003 16:12:44 +0000
Message-ID: <bnbj1s$isa$1@ausnews.austin.ibm.com>

Labels is like defun or flet; you need to specify the function's 
parameters:

(defun partial-sums (s)
  (labels ((p () (cons-stream (stream-car s)
                              (add-streams p (stream-cdr s)))))
    #'p))

Hope that helps,

Justin Dubs

From: Wang Yin
Subject: Re: What's the CL equivalent of Scheme's letrec?
Date: Wed, 29 Oct 2003 07:40:40 +0000
Message-ID: <m37k2osd8n.fsf@wangyin.com>

I forgot to tell you that, p is a variable, not a function.
p is a "stream object" (a delayed list) that partial-sums return.

(defun partial-sums (s)
  (letrec ((p (cons-stream (stream-car s)
                           (add-streams p (stream-cdr s)))))
    p))

is equivalent to 

(defun partial-sums (s)
  (letrec ((p (cons (car s)
                    (lambda () (add-streams p (stream-cdr s))))))
    p))


So you see here, the second p is inside a lambda. It must refer to the
very variable p we are creating. It seems that labels will not do the
work to set a variable.


-- 
Yin Wang,
EDA Lab,
Deparment of Computer Science and Technology,
Tsinghua University,
100084
Beijing China

From: Marco Antoniotti
Subject: Re: What's the CL equivalent of Scheme's letrec?
Date: Wed, 29 Oct 2003 14:47:03 +0000
Message-ID: <HpQnb.91$KR3.40725@typhoon.nyu.edu>

Wang Yin wrote:
> I forgot to tell you that, p is a variable, not a function.
> p is a "stream object" (a delayed list) that partial-sums return.
> 
> (defun partial-sums (s)
>   (letrec ((p (cons-stream (stream-car s)
>                            (add-streams p (stream-cdr s)))))
>     p))
> 
> is equivalent to 
> 
> (defun partial-sums (s)
>   (letrec ((p (cons (car s)
>                     (lambda () (add-streams p (stream-cdr s))))))
>     p))
> 
> 
> So you see here, the second p is inside a lambda. It must refer to the
> very variable p we are creating. It seems that labels will not do the
> work to set a variable.

Functions and variables in CL live in separate spaces.  I showed you how 
you can get a similar result in CL, but I still have to point out that 
most likely in CL you have a better way of doing whatever you are trying 
to do by emulating Scheme.

Cheers
--
Marco

From: Marco Antoniotti
Subject: Re: What's the CL equivalent of Scheme's letrec?
Date: Fri, 24 Oct 2003 22:06:12 +0000
Message-ID: <pnhmb.64$KR3.17761@typhoon.nyu.edu>

Wang Yin wrote:

> But it seems labels can only bind function bodies.
> 
> If I do like this:
> 
> (defun partial-sums (s)
>   (labels ((p (cons-stream (stream-car s)
>                            (add-streams p (stream-cdr s)))))
>     p))

The syntax is wrong.  Assuming that this is the standard example of 
STREAMS (as defined in SICP,) you should write

(defun partial-sums (s)
    (labels ((p ()
               (cons-stream (stream-car s)
                            (add-streams #'p (stream-cdr s))))
            )
       #'p))

(I am not sure it will work.  I have not tested it and I do not remember 
off the top of my head if LABELS creates bindings with indefinite extent)


> I got the following error:
> 
> Lambda-variable is not a symbol: (STREAM-CAR S).
> Error flushed ...
> 
> 
> I tried to solve the problem with 
> 
> (defun partial-sums (s)
>   (let ((p '<undefined>))
>     (let ((temp (cons-stream (stream-car s)
>                              (add-streams p (stream-cdr s)))))
>       (setf p temp))
>     p))
> 
> just as the Scheme macro does. It works.
> 
> If there is not equivalent of letrec in CL. I'd like to write a macro
> myself :)


Pardon the bluntness, but.... why do you need that?

Cheers
--
Marco