Re: [Chicken-users] Other Cheney-MTA systems?
From: John Cowan Subject: Re: [Chicken-users] Other Cheney-MTA systems? Date: Sat, 13 Nov 2010 13:53:21 -0500 > Peter Bex scripsit: > >> What is used instead of CPS nowadays? > > The typical view is that it's more important to optimize normal calls > and returns than calls to escape procedures, so a stack is used and then > copied when call/cc is invoked. Chicken allocates stack frames on a > first-generation heap, which means that you are paying to GC that heap, > as well as the (nowadays small) space cost of retaining the C return > addresses on the stack that are never used. That's right. But the really important point is TCO which is crucial. Without generating one big function, and/or using trampolines it is not possibly to portably generate C without losing full tail calls. One bug function is in practice not possible. Trampolines pay for cross-module calls and are expensive by requiring to maintain a "shadow" stack (this may be improved by generating big C functions but that doesn't scale too well in terms of gcc compile times). Cheney-on-the-MTA handles call/cc, TCO and first-level GC using a single technique, generates small functions that compile fast and keeps the C function calling conventions. > >> Does it give you "free" call/cc? > > In effect, Chicken call/cc is not free; its cost is amortized over > all calls. However, that cost is paid even by programs that never > use call/cc. Also correct. Note that cheap continuations become important when they are used to implement threading. cheers, felix thread-list.scm ; ; usage: csi -s thread-list.scm [COUNT] (use srfi-18) (define count #f) (define (run n) (set! count n) (print "creating " n " threads ...") (let loop ((n n) (prev #f)) (cond ((negative? n) (print "starting ...") (thread-start! prev)) (else (loop (sub1 n) (make-thread (lambda () (thread-start! prev) (bump n (define (bump n) (set! count (sub1 count)) (cond ((zero? count) (newline) (exit)) ((zero? (modulo n 1000)) (print* "." (run (string->number (optional (command-line-arguments) "25"))) (thread-sleep! 604800) ; time csi -s thread-list.scm 100 -:h1g -:d ; 11 secs ; ; csc thread-list.scm -o a.out -v -O4 -f -d0 ; time a.out 100 -:h1g -:d ; 4 secs ; ; (x86, Core2 Duo, 2.4Ghz, 2GB RAM) ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] Other Cheney-MTA systems?
Peter Bex scripsit: > What is used instead of CPS nowadays? The typical view is that it's more important to optimize normal calls and returns than calls to escape procedures, so a stack is used and then copied when call/cc is invoked. Chicken allocates stack frames on a first-generation heap, which means that you are paying to GC that heap, as well as the (nowadays small) space cost of retaining the C return addresses on the stack that are never used. > Does it give you "free" call/cc? In effect, Chicken call/cc is not free; its cost is amortized over all calls. However, that cost is paid even by programs that never use call/cc. (This is not a criticism of Chicken; if you want Gambit or Bigloo, you know where to find them.) -- "Well, I'm back." --SamJohn Cowan ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] Other Cheney-MTA systems?
On Sat, Nov 13, 2010 at 02:26:42PM +0100, Felix wrote: > Another language implementation using this method is not known to me, > which is a pity. That may be caused because doing it this way is so > unorthodox and because CPS compilers have become unfashionable. What is used instead of CPS nowadays? Does it give you "free" call/cc? Cheers, Peter -- http://sjamaan.ath.cx -- "The process of preparing programs for a digital computer is especially attractive, not only because it can be economically and scientifically rewarding, but also because it can be an aesthetic experience much like composing poetry or music." -- Donald Knuth ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] Other Cheney-MTA systems?
From: Peter Bex Subject: Re: [Chicken-users] Other Cheney-MTA systems? Date: Sat, 13 Nov 2010 13:29:38 +0100 > On Fri, Nov 12, 2010 at 07:23:41PM -0500, John Tobey wrote: >> Hi all, >> >> Anyone know of an active project or system other than Chicken that uses the >> machine's stack in a similar way? > > At T-DOSE someone mentioned that REBOL uses this technique. > I was able to find this reference http://ll1.ai.mit.edu/marshall.html > but the wikipedia page and their download page at rebol.com seems > to indicate they're on version 2.7.7. I'm not sure if that version > still uses this technique and if it doesn't, why not. I'm not completely sure, but seem to remember that using this technique was considered a failure in REBOL, as it was too complex to maintain. This is understandable, since coding an interpreter in this style is awkward (to say the least). But having a compiler generate such code is a different thing and not much worse than what other compilers generate. Another language implementation using this method is not known to me, which is a pity. That may be caused because doing it this way is so unorthodox and because CPS compilers have become unfashionable. Another point is that, taditionally, Lisp implementors are quite conservative ... cheers, felix ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
Re: [Chicken-users] Other Cheney-MTA systems?
On Fri, Nov 12, 2010 at 07:23:41PM -0500, John Tobey wrote: > Hi all, > > Anyone know of an active project or system other than Chicken that uses the > machine's stack in a similar way? At T-DOSE someone mentioned that REBOL uses this technique. I was able to find this reference http://ll1.ai.mit.edu/marshall.html but the wikipedia page and their download page at rebol.com seems to indicate they're on version 2.7.7. I'm not sure if that version still uses this technique and if it doesn't, why not. Cheers, Peter -- http://sjamaan.ath.cx -- "The process of preparing programs for a digital computer is especially attractive, not only because it can be economically and scientifically rewarding, but also because it can be an aesthetic experience much like composing poetry or music." -- Donald Knuth ___ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users