[racket] circular lists are not lists or sequences

If it denoted the largest set, it wouldn't be very Rackety, especially the remark in the docs that it exploits cached information so that it can get the response in (near-) constant time. 

Having said this, I would like to argue for an exploration of co-inductive programming in Racket. 

#lang racket

;; An Expression is one of: 
;; -- ('id Symbol)
;; -- ('abs Symbol Expression)
;; -- ('app Expression Expression)
;; and 'regular' expressions generated over this domain 

;; Expression 
(define e0 
  (shared ((t `(app (id x) ,u))
           (u `(app (id y) ,t)))
    t))

;; Expression -> [Setof Symbol]

(module+ test 
  (require rackunit)
  (check-equal? (fv '(id x)) (set 'x))
  (check-equal? (fv '(app (id x) (id y))) (set 'x 'y))
  (check-equal? (fv '(app (abs x (id x)) (id y))) (set 'y))
  (check-equal? (fv e0) (set 'x 'y)))

(define (fv e0)
  ;; Expression [Hashof Expression] -> [Setof Symbol]
  (define (fv e seen)
    (cond
      [(hash-has-key? seen e) (set)] ;; added stop condition 
      [else (define seen-1 (hash-set seen e #true))
            (match e
              [`(id ,name) (set name)]
              [`(abs ,name ,body) (set-remove (fv body seen-1) name)]
              [`(app ,rator ,rand) (set-union (fv rator seen-1) (fv rand seen-1))])]))
  (fv e0 #hash()))


Note that tail-calls vanish but continuation marks might be able to recover it. 

Imagine things like this in list shape and for-loop sequences we can use. 

Lots of things to do for a PhD student. -- Matthias






On Dec 10, 2012, at 10:51 AM, David Van Horn wrote:

> On 12/10/12 10:46 AM, Matthias Felleisen wrote:
>> 
>> I disagree. See first sentence of list? docs:
>> 
>> 
>>> Returns #t if v is a list: either the empty list, or a pair whose second element is a list.
> 
> It's not clear whether this is the biggest set or the smallest set that satisfies this spec.
> 
> (But OK, I give up.)
> 
> David
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4373 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20121210/c3fc44f5/attachment.p7s>