Mars 2020 - Gambit-list - mailman.iro.umontreal.ca

Gambit versus Python+GMP: Timing for Chudnovskys' algorithm for pi
by Bradley Lucier 07 Avr '22

07 Avr '22

Bakul Shah wrote a particularly elegant Scheme program for Chudnovskys' algorithm for pi based on the Common Lisp program here: https://bitbucket.org/tarballs_are_good/numericl/src/5fe8fe7089f48ab1c8a388… Nick Craig-Wood wrote a Python program using the GMP multiprecision library that appears to use exactly the same algorithm here: http://www.craig-wood.com/nick/articles/pi-chudnovsky/ I modified both programs a bit and include them here. They time the calculation of $10^n$ digits of pi for $n=1,2,3,4,5,6,7$. The results are heine:~/programs/gambiteer/gambit> !py python pi_chudnovsky_bs_gmpy.py 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679 ('chudnovsky_gmpy_mpz_bs: digits', 10, 'time', 1.0967254638671875e-05) ('chudnovsky_gmpy_mpz_bs: digits', 100, 'time', 3.0040740966796875e-05) Last 5 digits 70679 OK ('chudnovsky_gmpy_mpz_bs: digits', 1000, 'time', 0.00025582313537597656) Last 5 digits 01989 OK ('chudnovsky_gmpy_mpz_bs: digits', 10000, 'time', 0.00386810302734375) Last 5 digits 75678 OK ('chudnovsky_gmpy_mpz_bs: digits', 100000, 'time', 0.0834801197052002) Last 5 digits 24646 OK ('chudnovsky_gmpy_mpz_bs: digits', 1000000, 'time', 1.655979871749878) Last 5 digits 58151 OK ('chudnovsky_gmpy_mpz_bs: digits', 10000000, 'time', 30.67442488670349) Last 5 digits 55897 OK heine:~/programs/gambiteer/gambit> gsi chud1.scm Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10, CPU time: 0.. Last 5 digits 26535. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100, CPU time: 0.. Last 5 digits 70679. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000, CPU time: .004. Last 5 digits 1989. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000, CPU time: .028. Last 5 digits 75678. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 100000, CPU time: .472. Last 5 digits 24646. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 1000000, CPU time: 6.448. Last 5 digits 58151. Chudnovsky's algorithm using binary splitting in Gambit Scheme: digits 10000000, CPU time: 98.612. Last 5 digits 55897. So it appears that for this algorithm applied to large integers, GMP's bignum routines are about 3-4 times as fast as Gambit's bignum routines. Not so bad. For smaller bignums, GMP has a bigger advantage. The C program gmp-chudnovsky.c includes certain optimizations to this basic algorithm: http://gmplib.org/pi-with-gmp.html ftp://ftp.gmplib.org/pub/misc/gmp-chudnovsky.c On my machine, compiled with gcc -O3 -march=native -o gmp-chudnovsky gmp-chudnovsky.c -lgmp -lm the CPU times for 1,000,000 and 10,000,000 digits are 1.064 and 18.200 seconds, respectively. This is with a somewhat older machine model name : Intel(R) Core(TM)2 Quad CPU Q8200 @ 2.33GHz running Ubuntu 13.04 with heine:~/programs/gambiteer/gambit> gcc -v Using built-in specs. COLLECT_GCC=gcc COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.7/lto-wrapper Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.7.3-1ubuntu1' --with-bugurl=file:///usr/share/doc/gcc-4.7/README.Bugs --enable-languages=c,c++,go,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.7 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.7 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --with-system-zlib --enable-objc-gc --with-cloog --enable-cloog-backend=ppl --disable-cloog-version-check --disable-ppl-version-check --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.7.3 (Ubuntu/Linaro 4.7.3-1ubuntu1) heine:~/programs/gambiteer/gambit> gsi -v v4.6.9 20130607151908 x86_64-unknown-linux-gnu "./configure '--enable-single-host' '--enable-multiple-versions' '--enable-shared'" and the Ubuntu-provided GMP 5.0.5. (I'm sure the GMP folks have a better way to build GMP on my machine than the "generic" 64-bit version provided by Ubuntu.) Brad

7 18

newbie: bitwise and arithmetic runtime speed for u64
by Paolo Montrasi 17 Mai '20

17 Mai '20

Hi all, As a learning exercise, I am experimenting in chess/alpha-beta search/bitboards. In this domain lot of bitwise operations are required. My goal is to keep learning scheme and Gambit, therefore I will be happy to stay with what I have right now if the only option is to switch to C et similia. I am asking here for an advice in improving runtime speed crunching bitwise operations on u64 integers since I have no experience using scheme and Gambit. Looking at the documentation I see that fixnum is providing some help but I apparently u64 integers are not "compatible" with fixnum operations > (fixnum? 18446744073709551615) #f Can you share suggestions for my next exercise? Thank you in advance Paolo

6 9

Steps to bootstrap Git master from Gambit 4.9.3
by Lassi Kortela 19 Avr '20

19 Avr '20

Gambit's current Git head cannot be directly bootstrapped using the latest release 4.9.3 due to major internal changes. Could someone give a rough estimate for how many steps are needed from 4.9.3 to head, and which pre-release versions from Git to use as the stepping stones in between (e.g. from which month last year)? Is it possible to make do with one "stepping stone" commit (i.e. use Gambit 4.9.3 to bootstrap that commit, then use the Gambit built from that commit to bootstrap HEAD) or are two or more needed? I'm trying to build a Docker container tracking Gambit's HEAD at <https://hub.docker.com/u/schemers>, hence the question. But if we figure this out, it could also help use `git bisect` to find the commit where the MacOS poll() problem was mysteriously solved.

2 5

[CfP] 2020 Scheme and Functional Programming Workshop
by Jason Hemann 30 Mar '20

30 Mar '20

Hello, Thank you for your attention, and my apologies for any duplication you receive. Please find below the Call for Papers for the *2020 Scheme and Functional Programming Workshop*. We look forward to your submissions. *Call for Papers*The 2020 Scheme and Functional Programming Workshop is calling for submissions. We invite high-quality papers about novel research results, lessons learned from practical experience in industrial or educational setting, and even new insights on old ideas. We welcome and encourage submissions that apply to any language that can be considered Scheme: from strict subsets of RnRS to other “Scheme” implementations, to Racket, to Lisp dialects including Clojure, Emacs Lisp, Common Lisp, to functional languages with continuations and/or macros (or extended to have them) such as Dylan, ECMAScript, Hop, Lua, Scala, Rust, etc. The elegance of the paper and the relevance of its topic to the interests of Schemers will matter more than the surface syntax of the examples used. Topics of interest include (but are not limited to): Interaction: program-development environments, debugging, testing, refactoring Implementation: interpreters, compilers, tools, garbage collectors, benchmarks Extension: macros, hygiene, domain-specific languages, reflection, and how such extension affects interaction. Expression: control, modularity, ad hoc and parametric polymorphism, types, aspects, ownership models, concurrency, distribution, parallelism, non-determinism, probabilism, and other programming paradigms Integration: build tools, deployment, interoperation with other languages and systems Formal semantics: Theory, analyses and transformations, partial evaluation Human Factors: Past, present and future history, evolution and sociology of the language Scheme, its standard and its dialects Education: approaches, experiences, curricula Applications: industrial uses of Scheme Scheme pearls: elegant, instructive uses of Scheme *Important dates* Submission deadline is 15 May 2020. Authors will be notified by 12 June 2020. Camera-ready versions are due 30 June 2020. All deadlines are (23:59 UTC-12), “Anywhere on Earth”. Submission Information Paper submissions must use the format acmart and its sub-format acmlarge. They must be in PDF, printable in black and white on US Letter size. Microsoft Word and LaTeX templates for this format are available at: http://www.sigplan.org/Resources/Author/ <https://jason-hemann-dot-yamm-track.appspot.com/Redirect?ukey=1hySDOusaj9Sw…> This format is in line with ACM conferences (such as ICFP with which we are colocated). It is recommended to use the review option when submitting a paper; this option enables line numbers for easy reference in reviews. We want to encourage all kinds of submissions, including full papers, experience reports and lightning talks. Papers and experience reports are limited to 14 pages, but we encourage submitting smaller papers. Lightning talks are limited to 192 words. Each accepted paper and report will be presented by its authors in a 25 minute slot including Q&A. Each accepted lightning talk will be presented by its authors in a 5 minute slot, followed by 5 minutes of Q&A. The size limits above exclude references and any optional appendices. There are no size limits on appendices, but the papers should stand without the need to read them, and reviewers are not required to read them. Authors are encouraged to publish any code associated to their papers under an open source license, so that reviewers may try the code and verify the claims. Proceedings will be printed as a Technical Report at the University of Michigan and uploaded to arXiv.org <https://jason-hemann-dot-yamm-track.appspot.com/Redirect?ukey=1hySDOusaj9Sw…> . Publication of a paper at this workshop is not intended to replace conference or journal publication, and does not preclude re-publication of a more complete or finished version of the paper at some later conference or in a journal. Sincerely, Jason Hemann, Northeastern University *Organizing Committee* Michael D. Adams (Program Co-Chair), University of Michigan Baptiste Saleil (Program Co-Chair), IBM Canada Jason Hemann (Publicity Chair), Northeastern University *Program Committee*Michael D. Adams (Program Co-Chair), University of Michigan Baptiste Saleil (Program Co-Chair), IBM Canada Maxime Chevalier-Boisvert, Université de Montréal Ryan Culpepper, Czech Technical University Kimball Germane, University of Utah Yukiyoshi Kameyama, University of Tsukuba Andy Keep, Cisco Systems, Inc Julien Pagès, Université de Montréal Alexey Radul *Steering Committee*Will Byrd, University of Alabama at Birmingham Will Clinger, The Larceny Project Marc Feeley, Université de Montréal Dan Friedman, Indiana University Olin Shivers, Northeastern University [image: beacon]

1 0

How to distinguish procedures from procedures?
by Jörg F. Wittenberger 27 Mar '20

27 Mar '20

Hi, A few questions regarding procedures: There are several classes of objects passing the `procedure?` predicate. - Is there a full list? - How expensive are those at startup initialization and call time? (A rough ordering would do. Just to avoid expensive ones when there's the option.) - I tend to use the following receipe to control the global exports with gambit (currently nailed in practice to 0.9.2 for use with lambdanative). Does imply any runtime overhead vs. no use of `let` and resorting to gambits namespace facility? (define my-exported-proc #f) (let (...) (define (my-private-proc ...) ...) (define (my-to-be-exported ...) ...) (set! my-exported-proc my-to-be-exported)) - The real question of mine: How could I create additional runtime predicates for procedures with minimal overhead? Any way to attach tags to procedures? (Let's rule out the trivial solution to collect procedures which should pass the predicate in a data structure and look it up.) I need something where this fiction make sense (upper case be "dunno how"): ;; ATTACH-TAG! is compiletime, maybe even only compiletime. (define-macro (bless! proc tag) `(ATTACH-TAG! ,proc ',tag)) (define (make-blessed tag) (lambda (obj) (and (procedure? obj) (eq? (GET-TAG obj) tag)))) (define ispure? (make-blessed 'pure)) (bless! + 'pure) ;;; at runtime: (ispure? +) ; => #t (ispure? -) ; => #f ;; yeah, we forgot to bless is :-/ Thanks so much Jörg

3 3

Gambit universal library in the browser
by Marc Feeley 25 Mar '20

25 Mar '20

With the latest commit the Gambit universal library can be used in the browser… it is as simple as: % make _gambit.js % gsc/gsc -:= -target js -exe -o webapp.js webapp.scm % open webapp.html webapp.scm: (declare (extended-bindings)) (define (document.write html) (##inline-host-statement "document.write(g_scm2host(@1@));" html)) (document.write "<h1>Hello world!</h1>") webapp.html: <!doctype html> <html> <head> <meta charset="utf-8"> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <title>webapp</title> </head> <body> <script type="text/javascript" src="webapp.js"></script> </body> </html>

3 6

Universal library improvements
by Marc Feeley 23 Mar '20

23 Mar '20

With the most recent changes to the universal backend and library, Gambit's JavaScript and Python backends are now much easier to use. The following steps will build and install the universal library with the JavaScript and Python backends: % make % make _gambit.js _gambit.py % make install Scheme programs can be compiled to either JavaScript or Python shell scripts by specifying the -exe flag and the target language to gsc: % gsc -target js -o fib-js -exe fib.scm % ./fib-js (time (f 30)) 0.076000 secs real time 0.076000 secs cpu time (0.076000 user, 0.000000 system) no collections no bytes allocated no minor faults no major faults 832040 % cat fib.scm (declare (standard-bindings)) (define (f n) (if (< n 2) n (+ (f (- n 1)) (f (- n 2))))) (println (time (f 30))) It is also possible to build a version of the Gambit interpreter implemented in JavaScript with: % gsc -target js -o gsi-js -exe -prelude '(include"../lib/header.scm")' gsi/_gsi.scm Replacing "js" with "python" will build gsi implemented in Python: % ./gsi-python Gambit v4.9.3 > (host-decl "import os") > (define (env var) (host-eval "g_host2scm(os.environ[g_scm2host(@1@)])" var)) > (env "TERM") "dumb" > ,q % ./gsi-js Gambit v4.9.3 > (define (f n) (if (< n 2) n (+ (f (- n 1)) (f (- n 2))))) > (time (f 30)) (time (f 30)) 2.254000 secs real time 2.254000 secs cpu time (2.254000 user, 0.000000 system) no collections no bytes allocated no minor faults no major faults 832040 > (apropos 'inexact) "##" namespace: exact->inexact, fail-check-inexact-real, fail-check-inexact-real-list, flonum->inexact-exponential-format, inexact, inexact->exact, inexact? empty namespace: exact->inexact, inexact, inexact->exact, inexact? > (define (show x) (host-exec "console.log(g_scm2host(@1@));" x)) > (show "hello") hello > (show (host-eval "g_host2scm(new Date().toString())")) Sun Mar 22 2020 23:20:29 GMT-0400 (GMT-04:00) > ,q The universal library is quite large (> 30MB)... so the memory conscious may choose to link with a custom runtime library that defines only the procedures needed. The compiler's -l flag is useful to specify the library to link with. ;;; minlib.scm (println "running minlib.scm") (define (twice thunk) ;; exported procedure (thunk) (thunk)) (define (##run-each-module) (declare (extended-bindings) (not safe)) (let ((mods (##vector-ref ##program-descr 0))) (let loop ((i 1)) ;; start at module after the current one (if (##fx< i (##vector-length mods)) (let ((mod (##vector-ref mods i))) ((##vector-ref mod 4)) ;; call module's init procedure (loop (##fx+ i 1))))))) (##run-each-module) ;; run each module (after the current one) ;; To use this minimal library to compile a program prog.scm, ;; follow these steps: ;; ;; % cat prog.scm ;; (twice (lambda () (println "hello"))) ;; % TARGET=js # could also be python or php ;; % gsc -target $TARGET -c minlib.scm ;; % gsc -target $TARGET -l minlib -exe prog.scm ;; % ./prog ;; running minlib.scm ;; hello ;; hello ;; % head -1 prog ;; #! /usr/bin/env node There are still some issues with the universal backend, but it is now much closer to the features offered by the C backend. Marc

2 1

Parameter objects performance Q
by Adam 21 Mar '20

21 Mar '20

Hi Marc, I can't recall if this is somewhere in the mailing list archive from before: I recall that you indicated that parameter objects are expensive. Would you mind describing/quantifying the average/worst case/best case cost for assigning a value to a parameter object by parameterization (|parameterize|), and for accessing a parameter object (load or store operation by invoking it as a closure)? Parameter objects are very practical and have ample use scenarios, both high-level and relatively low-level. Thanks, Adam

8 31

Marc what's the rationale for "--enable-multiple-threaded-vms --enable-smp"?
by Adam 18 Mar '20

18 Mar '20

Hi Marc, Small thing, just curious, I think also this may have been clarified in some mail thread I have somewhere but I can't find it now: What is the rationale for "--enable-multiple-threaded-vms --enable-smp" to be the enabling arguments for SMP? Neither "--enable-multiple-threaded-vms" nor "--enable-smp" individually will do it. I understand "--enable-smp" enables the "SMP scheduler", I presume that is the multiple processors operate concurrently and steal work from each other. The "--enable-multiple-threaded-vms" enables the infrastructure for creating multiple processors within one GVM in the first place? But then, "--enable-multiple-threaded-vms" only allows you to create a new processor but that one will be all separate from the first one - may that ever be useful without SMP work stealing operation?? I thought anyone who wanted to do that would go with "--enable-multiple-vms". Today I dug out "--enable-multiple-threaded-vms --enable-smp" again from the manual. I looked at it twice going, hmm is this really correct, does this really look correct. After checking all over my email box I see your other email where you reiterate exactly this, and thus deduce, it's correct. So just thought, why does enabling SMP require two separate ./configure arguments. Any comment would be much appreciated. Thanks! Adam

2 3

Delimited continuations
by Adam 17 Mar '20

17 Mar '20

Hi Marc and Fare, What's the fuss about delimited continuations? Why do I want to use this. How will it improve some people's thing. Which problems that I have now, will I not have with them. Adam On Thu, 12 Mar 2020 at 19:05, Marc Feeley <feeley(a)iro.umontreal.ca> wrote: > Yes delimited continuations is on my wishlist too! > > Marc > > > > > On Mar 11, 2020, at 2:32 AM, Faré <fahree(a)gmail.com> wrote: > > > > I don't know that anyone is interested in implementing it, but I would > > be grateful if Gambit implemented delimited control, with continuation > > marks and delimited parameter bindings. Then, the value of a parameter > > potentially depends not just on "the" continuation, but on the list of > > currently active continuation frames, which can grow and shrink > > non-monotonically due to delimited control operators. > > http://okmij.org/ftp/Computation/dynamic-binding.html > > > > —♯ƒ • François-René ÐVB Rideau •Reflection&Cybernethics• > http://fare.tunes.org >

2 1