Gambit-list Mai 2007

gambit-list@iro.umontreal.ca

25 participants
42 discussions

Re: [gambit-list] Mercurial
by Marc Feeley 25 Mai '07

25 Mai '07

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 25-May-07, at 8:52 AM, Aycan iRiCAN wrote: > Marc Feeley wrote: >> I have pretty much settled on Mercurial (http://www.selenic.com/ >> mercurial/wiki/) as the source control management system for Gambit. >> If you have another suggestion then please let me know ASAP. > I suggest Darcs. It's distributed, interactive and supports > spontaneous > branches. It supports various platforms including Windows, Mac OS X, > FreeBSD, NetBSD, Solaris, AIX, Linux and Cygwin. It's reliable, we're > using darcs around a year (constantly developing applications > everyday) > and had no problem. > > http://darcs.net/DarcsWiki > > Best Regards. I was considering darcs but the "conflict bug" seems serious: http://programming.reddit.com/info/19vvs/comments Marc -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.3 (Darwin) iD8DBQFGVuB+//V9Zc2T/v4RAnSPAKCNbv2IM42ui2gpZy9MIVpAuQtT/wCcCyxT TPfN2wJXpAymTwW08qVACno= =IJ5S -----END PGP SIGNATURE-----

3 2

Mercurial
by Marc Feeley 25 Mai '07

25 Mai '07

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I have pretty much settled on Mercurial (http://www.selenic.com/ mercurial/wiki/) as the source control management system for Gambit. If you have another suggestion then please let me know ASAP. Marc -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.3 (Darwin) iD8DBQFGVs94//V9Zc2T/v4RAgf6AJ9RBCKcwC00K/f2DViob4806smW3QCfYO3k njpRwe4jRqE2sJyija+4ICA= =uSIe -----END PGP SIGNATURE-----

1 0

promises are leading to memory retention
by Christian 25 Mai '07

25 Mai '07

Hello I have read SRFI-45 (Primitives for Expressing Iterative Lazy Algorithms by André van Tonder [1]), but I'm not sure whether I'm sharing his view on the necessity of the additional |lazy| operator; at least I don't think it is necessary for the stream-filter example, since one can code the iterative part without involving any (delay (force .. )) invocations. One just has to distinguish between two separate recursive calls. See my example below. (The |lazy| operator could still possibly be useful in situations where one is using code written by others where the iterative path isn't free from lazyness. Of for other kinds of freedom I'm not aware of right now, in the same way that tail call optimization has given freedom to new programming styles.) [1] http://srfi.schemers.org/srfi-45/srfi-45.html But to my disappointment, despite my belief that I could write stream-filter without the |lazy| operator, at first I couldn't get (t2 #f) to run without leaking. After much time spent debugging, I realized that it's very simple: the promise built by the outer delay in stream-filter is holding a thunk which captures the stream head. If this promise is forced, the inner, iterative loop runs, which is not by itself faulty, but which forces the stream whose head is still fixed in the thunk in the promise which is not yet freed. In my code below I've provided my own delay/force implementation to make this visible; uncommenting the line "uncomment this as a solution" makes the problem go away. Now this technique of removing the thunk from the promise already before it is being run is of course a problem if the thunk is throwing an exception, because the promise is then broken. OTOH one could argue that leaving a promise broken in such cases is even a benefit (giving the warranty that the thunk is never ever being called more than once). (Maybe the exception could even be stored, and rethrown upon subsequent force calls; kind of like thread-join! works. Not sure how this could be done efficiently.) Would changing the builtin promise be an option or would this break R5RS or some other standard? I'm also wondering if many cases for SRFI-45 is trying to provide a solution could really have been because of holding on to memory, not actually because of creating nested promises. I'd be interested to hear your thoughts on the matter; maybe I should then post to the SRFI-45 discussion list. BTW, the below code has to be run in the compiler. The interpreter will leak anyway. I guess it isn't releasing references to bindings in a scope at all before leaving the scope? Can't this be improved without lexical analysis? If this leaking cannot be avoided by an interpreter, this is disappointing, since it means that lazy code always risks running into problems in the interpreter, and thus the interpreter cannot be used to deploy code in a productive environment. I had already planned using as much interpreted code as possible in production settings because it can be debugged much better (even "post-mortem" by capturing and serializing continuations; capturing continuation also works for compiled code of course, but one cannot step through the code and not access (only see) lexical bindings from the continuation frames). Maybe the debugging features of compiled code could be improved? Or maybe some hybrid approach including an (optional) lexical analysis could be taken for the interpreter? Christian. (define-macro (cj-delay body) `(vector #f (lambda () ,body))) (define (cj-force p) (cond ((vector-ref p 1) => (lambda (thunk) ;;(vector-set! p 1 #f) ;; uncomment this as a solution. (let ((v (thunk))) (vector-set! p 0 v) (vector-set! p 1 #f) v))) (else (vector-ref p 0)))) (define-macro (F bindings . body) ;; my "macro-force-vars" `(let (,@(map (lambda (v) (if (symbol? v) `(,v (cj-force ,v)) (error "F: expecting symbol, got:" v))) bindings)) ,@body)) (define (stream-iota count #!optional (start 0) (step 1)) (if count (let rec ((val start) (count count)) (cj-delay (if (positive? count) (cons val (rec (+ val step) (- count 1))) '()))) (let rec ((val start)) (cj-delay (cons val (rec (+ val step))))))) (define (stream-filter pred strm) (cj-delay ;; <-- this promise must not hold on to the thunk/strm. (let next ((strm strm)) (F (strm) (if (null? strm) '() (if (pair? strm) (if (pred (car strm)) (cons (car strm) (cj-delay (next (cdr strm)))) (next (cdr strm))) (error "improper stream:" strm))))))) (define (stream-length strm) (let iter ((strm strm) (len 0)) (F (strm) (if (null? strm) len (if (pair? strm) (iter (cdr strm) (+ len 1)) (error "stream length" "improper stream:" strm)))))) (define (t1 n) (stream-length (stream-iota n))) (define (t2 n) (stream-length (stream-filter (lambda (v) #f) (stream-iota n))))

1 0

Mingw compile error
by Jeremie Lasalle Ratelle 24 Mai '07

24 Mai '07

make[1]: Entering directory `/home/Owner/gambc-4.0b22/gambc-4.0b22/gsi' gcc _gsi.o _gsi_.o ../lib/libgambc.a -lws2_32 -o gsi.exe ../lib/libgambc.a(os_tty.o)(.text+0x74c):os_tty.c: undefined reference to `___printf' collect2: ld returned 1 exit status make[1]: *** [gsi.exe] Error 1 make[1]: Leaving directory `/home/Owner/gambc-4.0b22/gambc-4.0b22/gsi' make: *** [all-recursive] Error 1 Thank-you Jeremie

2 1

Where is macro-character-port-rlo defined?
by Bradley Lucier 24 Mai '07

24 Mai '07

Marc: Your runtime is a masterful lesson on how to write code that writes code that writes code. But it's nearly totally undocumented, and if you really want to turn gambit into an open-source project you need to give out more information on what the code does and how it is changing. Brad

4 5

Xlib.scm and syntax-case.scm
by Eduardo Cavazos 24 Mai '07

24 Mai '07

Hello, If my ~/gambcini file contains an include for syntax-case, Xlib fails to build: /src/gambc-4.0b22/examples/Xlib-simple$ make Xlib.o1 rm -f Xlib.o* ../../gsc/gsc -:=".. \/.." -dynamic -cc-options "" -ld-options " -lSM -lICE -L/usr/X11R6/lib -lX11" Xlib.scm *** ERROR IN map -- invalid syntax () make: *** [Xlib.o1] Error 70 /src/gambc-4.0b22/examples/Xlib-simple$ Ed

2 1

Re: [gambit-list] c-struct
by TJ 23 Mai '07

23 Mai '07

On 5/23/07, Eduardo Cavazos <wayo.cavazos(a)gmail.com> wrote: > Do I stick (include "~~/syntax-case") in "c-struct.scm"? IIRC, you have to put (load "~~/syntax-case.scm") in your Gambit initialization file. Search the Gambit manual for "gambcini". > "c-struct.scm" depends on "srfi-28.scm". So do I (include "srfi-28.scm") as > well? > > Finally, should I put (include "c-struct") in "Xlib.scm"? I don't know about this at all. TJ

3 2

New fft bignum multiplication
by Bradley Lucier 23 Mai '07

23 Mai '07

Marc: After many years, I finally understand what Percival, Crandall, Brandt, et al. are trying to tell me about how to do fft bignum multiplication, and I implemented it. Here are the timing results (in ms) on my 2GHz G5 comparing the code I sent you recently with the new code and mzscheme 360. Results that had an inordinate gc time are noted. old new mzscheme (expt 3 1000000) ; a 175 101 273 (expt 3 1000001) ; b 176 103 277 (* a a) ; c 204 116 478 (* a b) ; 302 165 667 (quotient c a) ; 1433 825 1670 (sqrt c) ; 1430 865 1176 (gcd a b) ; note 1 5385 3979 6759 (* a b) 145 84 191 (expt1 3 1000000) ; note 2 179 106 277 (expt2 3 1000000) ; note 3 763 433 957 (* a a) ; a=3^1000000 202 160 (48 gc) 473 (expt 10 10000000); a 450 227 492 (fib 10000) ; note 4 25 22 130 (89 gc) (factorial 10000) ; note 5 311 310 666 (486 gc) (partial-factorial 0 10000) ; note 6 29 19 30 (binary-splitting-compute-e 10000) ; note 7 1692 1469 1857 (binary-splitting-compute-pi 10000) ; note 9 2093 1820 2334 (pi-brent-salamin) ; n. 10, beta^k=10^100000 10325 (764 gc) 5918 (473 gc) 8051 (pi-brent-salamin) ; beta^k=2^332193 7703 (683 gc) 4497 (462 gc) 3985 MzScheme uses its own hybrid version (part of gmp 3, part gmp 4) of gmp without fft multiplication and some of the more-recently-added algorithms. The new code uses less memory, so the number of gc's were reduced, too. We really need to improve our rational arithmetic if such a big improvement in basic large operations results in such a small improvement in code using rationals (binary-splitting-compute-e and binary-splitting-compute-pi). These times scale to arguments up to half a billion bits in size (after that, we slow down because we switch to Karatsuba multiply again because the floating-point error bounds get too bad). Some timings for similar things from December 2003 can be found at <http://groups.google.com/group/comp.lang.scheme/msg/4306a6bd50004f9a> Note the different parameters for many of the timings. I'm going to look at its packaging a bit more before sending it to you. So now, instead of gambit taking about 5 times as long as gmp-4.2.1 for multiplication/division/sqrt and being a bit faster for gcd, gambit takes "only" a bit less than 3 times as long as gmp-4.2.1 for multiplication/division/sqrt and is noticeably faster for gcd. (That last bit will change with version 5 of gmp, which will use a faster version of gambit's algorithm that was written by Niels Möller of Sweden.) The basic fft code in _num.scm is about half as fast as, e.g., FFTW so this isn't too bad. Brad note 1: a=(fib 1000000) b=(fib 1000001) note 2: (define (expt1 a b) (define (square x) (* x x)) (cond ((= b 0) 1) ((even? b) (square (expt1 a (quotient b 2)))) (else (* a (square (expt1 a (quotient b 2))))))) note 3: (define (expt2 a b) (define (square x) (* x x)) (cond ((= b 0) 1) ((even? b) (expt2 (square a) (quotient b 2))) (else (* a (expt2 (square a) (quotient b 2)))))) note 4: (define (fib-ratio n) (if (= n 1) 1 (+ 1 (/ (fib-ratio (- n 1)))))) (define (fib n) (numerator (fib-ratio n))) note 5: (define (factorial n) (let loop ((i 1) (result 1)) (if (> i n) result (loop (+ i 1) (* i result))))) note 6: (define (partial-factorial m n) ;; computes the product (m+1) * ... * (n-1) * n (if (< (- n m) 10) (do ((i (+ m 1) (+ i 1)) (result 1 (* result i))) ((> i n) result)) (* (partial-factorial m (quotient (+ m n) 2)) (partial-factorial (quotient (+ m n) 2) n)))) note 6: (define (partial-factorial m n) ;; computes the product (m+1) * ... * (n-1) * n (if (< (- n m) 10) (do ((i (+ m 1) (+ i 1)) (result 1 (* result i))) ((> i n) result)) (* (partial-factorial m (quotient (+ m n) 2)) (partial-factorial (quotient (+ m n) 2) n)))) note 7: (define (binary-splitting-partial-sum m n partial-term common-factor-ratio) ;; sums (partial) terms from m to n-1 ;; (partial-term n m) is the term at n with the common factors of terms >= m removed ;; (common-factor-ratio m n) is the ratio of the common factor of terms >= n divided by ;; the common factors of terms >= m (if (< (- n m) 10) (do ((i m (+ i 1)) (result 0 (+ result (partial-term m i)))) ((= i n) result)) (+ (binary-splitting-partial-sum m (quotient (+ m n) 2) partial-term common-factor-ratio) (* (common-factor-ratio m (quotient (+ m n) 2)) (binary-splitting-partial-sum (quotient (+ m n) 2) n partial-term common-factor-ratio))))) (define (binary-splitting-sum n partial-term common-factor) (binary-splitting-partial-sum 0 n partial-term common-factor)) (define (binary-splitting-compute-e n) (binary-splitting-sum n (lambda (m n) (/ (partial-factorial m n))) (lambda (m n) (/ (partial-factorial m n))))) note 9: (define (binary-splitting-compute-atan n x) ;; here we just consider the common factor to be x^(2n+1) (* x ;; common factor for all terms (binary-splitting-sum n (lambda (m n) (/ (expt x (* 2 (- n m))) (* (if (odd? n) -1 1) ( + (* 2 n) 1)))) (lambda (m n) (expt x (* 2 (- n m))))))) (define (binary-splitting-compute-pi n) (* 4 (- (* 4 (binary-splitting-compute-atan n 1/5)) (binary-splitting-compute-atan (quotient (* n 10) 34) 1/239)))) note 10: (define (fixed.+ x y) (+ x y)) (define (fixed.- x y) (- x y)) (define (fixed.* x y) (quotient (* x y) beta^k)) (define (fixed.square x) (fixed.* x x)) (define (fixed./ x y) (quotient (* x beta^k) y)) (define (fixed.sqrt x) (##exact-int.sqrt (* x beta^k))) (define (number->fixed x) (round (* x beta^k))) (define (fixed->number x) (/ x beta^k)) (define (pi-brent-salamin) (let ((one (number->fixed 1))) (let loop ((a one) (b (fixed.sqrt (quotient one 2))) (t (quotient one 4)) (x 1)) (if (= a b) (fixed./ (fixed.square a) t) (let ((new-a (quotient (fixed.+ a b) 2))) (loop new-a (fixed.sqrt (fixed.* a b)) (fixed.- t (* x (fixed.square (fixed.- new-a a)))) (* 2 x)))))))

1 3

c-struct
by Eduardo Cavazos 23 Mai '07

23 Mai '07

Hello, I defined a macro named c-struct to help with interfacing to C structs. Let's say you have a C struct: typedef struct { int x; int y; } point ; This expression: (c-struct point ((x int) (y int))) Expands into the code to generate these functions: make-point point-x point-y set-point-x! set-point-y! Here's the macro: http://dharmatech.onigirihouse.com/scheme/c-struct.scm The problem is, I'm not sure how to integrate it with Gambit-C. :-) I've tried a few variations but the compiles fail, I think due to improperly including syntax-case. One place I'd like to use it is to extend Xlib.scm. I'd like to use c-struct to generate code for the X event structs. One problem is that c-struct is a syntax-case macro. Do I stick (include "~~/syntax-case") in "c-struct.scm"? "c-struct.scm" depends on "srfi-28.scm". So do I (include "srfi-28.scm") as well? Finally, should I put (include "c-struct") in "Xlib.scm"? Thanks for any suggestions. Ed

1 0

syntax-case and DSSSL
by James Cash 22 Mai '07

22 Mai '07

Is there any way to have both the syntax-case macros and use Gambit's DSSSL parameters at the same time? I found that you can't use them normally after loading the file, as in > (load "~~/syntax-case.scm") "/usr/local/Gambit-C/4.0b22/syntax-case.scm"> (load "~~/syntax-case.scm") > (define (foo x #!key y) (list x y)) *** ERROR -- invalid syntax (define (foo x #!key y) (list x y))> (define (foo x #!key y) (list x y)) However, if I do > (##define (foo x #!key y) (list x y)) It works fine. Okay. But now, if I were to try this: > (define-syntax twice (syntax-rules () ((_ x) (begin x x)))) > (##define (bar x) (twice x)) > (bar 5) ** ERROR IN bar, (stdin)(a)55.2 -- unbound variable twice So, once I've loaded syntax-rules, I can only use the DSSSL extensions in ##define forms, but I can only use syntax macros in define forms. Is there any way around this? Do I have to prefix the syntax macros with a specific namespace? I'm assuming that's what the problem is, the macros being in a different namespace...but which one? Kind of curious, James

2 1

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

Gambit-list Mai 2007