October 2012 - Gambit-list - mailman.iro.umontreal.ca

Efficient Compilation of Tail Calls and Continuations to JavaScript
by Marc Feeley 17 Sep '13

17 Sep '13

Eric Thivierge is in Copenhagen today, at the Scheme Workshop, presenting our latest paper: "Efficient Compilation of Tail Calls and Continuations to JavaScript" You can get the paper on the Scheme Worshop web page: http://users-cs.au.dk/danvy/sfp12/programme-sfp12.html It describes the implementation of tail calls and continuations in Gambit-JS and evaluates its performance. Even if you are not specifically interested in the JavaScript back-end the paper may be interesting to read as it provides a brief explanation of the Gambit Virtual Machine (GVM) and compiler front-end, and a complete example of compilation from Scheme, to GVM, to JavaScript. The performance evaluation (see attached tables) shows that the approach used by Gambit-JS is consistently faster than Scheme2JS and Spock. Marc Execution times using V8 (Chrome 21.0.1180.89): Gambit-JS Scheme2JS Spock fib35 .80 1.54 1.9x 2.40 3.0x nqueens12 .72 .76 1.1x 2.33 3.3x oddeven .83 1.92 2.3x 5.62 6.8x ctak .18 17.64 95.9x .59 3.2x contfib30 1.17 106.01 90.9x 3.38 2.9x btsearch2000 1.35 25.40 18.8x 7.93 5.9x threads10 1.34 24.68 18.5x 4.40 3.3x Execution times using JagerMonkey (Firefox 15.0.1): Gambit-JS Scheme2JS Spock fib35 1.07 7.66 7.2x 20.73 19.4x nqueens12 1.49 2.62 1.8x 12.97 8.7x oddeven 1.09 1.93 1.8x 33.91 31.1x ctak 1.25 30.38 24.3x 1.86 1.5x contfib30 5.88 156.79 26.7x 10.61 1.8x btsearch2000 11.19 27.16 2.4x 16.54 1.5x threads10 6.97 34.36 4.9x 22.11 3.2x Execution times using Nitro (Safari 6.0): Gambit-JS Scheme2JS Spock fib35 1.32 6.53 4.9x 84.69 64.2x nqueens12 1.31 1.89 1.4x 45.15 34.4x oddeven 2.52 1.55 .6x 143.97 57.1x ctak .30 52.88 177.4x 4.18 14.0x contfib30 1.60 2311.69 1443.0x 25.98 16.2x btsearch2000 3.46 102.98 29.7x 92.02 26.6x threads10 3.03 74.21 24.5x 74.88 24.7x

4 10

Edge triggered I/O with libevent
by Adam Langley 04 Apr '13

04 Apr '13

Gambit uses the select call on POSIX systems to multiplex IO operations. This is fine for small numbers of file descriptors, but falls apart quickly with large numbers[1]. libevent[2] is a wrapper library around a number of modern IO multiplexing systems (epoll on Linux, kqueue on the BSDs as well as poll and select). Attached is a patch which converts Gambit to using edge triggered I/O with epoll and libevent. This also requires a patch (attached) of libevent since the standard distribution doesn't include edge triggering support and the upstream appears to be on holiday. (epoll is required because I don't have a BSD box on which to develop edge triggering support for kqueue) This patch (for Gambit) preprocesses away to nothing unless --enable-libevent is passed to the configure script. (Note that, since this patches the configure.ac script, you'll need to run autoconf to regenerate). I hope I've not broken anything, but at this stage I've only tested that the console and tcp ports work. This patch (in the future) should also allow people, who write programs which use socket calls directly, to integrate into the main event loop at some point. Testing is more than welcome and, if you find a form of IO which is broken, please email me. [1] http://monkey.org/~provos/libevent/libevent-benchmark2.jpg [2] http://monkey.org/~provos/libevent/ -- Adam Langley agl(a)imperialviolet.org http://www.imperialviolet.org (+44) (0)7906 332512 PGP: 9113 256A CC0F 71A6 4C84 5087 CDA5 52DF 2CB6 3D60

2 2

ICFP 2013: Call for workshops and co-located events
by David Van Horn 29 Oct '12

29 Oct '12

CALL FOR WORKSHOP AND CO-LOCATED EVENT PROPOSALS ICFP 2013 18th ACM SIGPLAN International Conference on Functional Programming September 22 - 28, 2013 Boston, Massachusetts, USA http://icfpconference.org/icfp2013/ The 18th ACM SIGPLAN International Conference on Functional Programming will be held in Boston, Massachusetts on September 22-28, 2013. ICFP provides a forum for researchers and developers to hear about the latest work on the design, implementations, principles, and uses of functional programming. Proposals are invited for workshops (and other co-located events, such as tutorials) to be affiliated with ICFP 2013 and sponsored by SIGPLAN. These events should be more informal and focused than ICFP itself, include sessions that enable interaction among the attendees, and foster the exchange of new ideas. The preference is for one-day events, but other schedules can also be considered. The workshops are scheduled to occur on September 22-24 (the three days before ICFP) and September 28 (the day after ICFP). ---------------------------------------------------------------------- Submission details Deadline for submission: December 7, 2012 Notification of acceptance: January 7, 2013 Prospective organizers of workshops or other co-located events are invited to submit a completed workshop proposal form in plain text format to the ICFP 2013 workshop co-chairs (Patrik Jansson and Sam Tobin-Hochstadt), via email to icfp13-workshops(a)ccs.neu.edu by December 7, 2012. (For proposals of co-located events other than workshops, please fill in the workshop proposal form and just leave blank any sections that do not apply.) Please note that this is a firm deadline. Organizers will be notified if their event proposal is accepted by January 7, 2013, and if successful, depending on the event, they will be asked to produce a final report after the event has taken place that is suitable for publication in SIGPLAN Notices. The proposal form is available at: http://www.icfpconference.org/icfp2013/icfp13-workshops-form.txt Further information about SIGPLAN sponsorship is available at: http://acm.org/sigplan/sigplan_workshop_proposal.htm ---------------------------------------------------------------------- Selection committee The proposals will be evaluated by a committee comprising the following members of the ICFP 2013 organizing committee, together with the members of the SIGPLAN executive committee. Workshop Co-Chair: Patrik Jansson (Chalmers University of Technology) Workshop Co-Chair: Sam Tobin-Hochstadt (Northeastern University) General Chair : Greg Morrisset (Harvard University) Program Chair: Tarmo Uustalu (Tallinn University of Technology) ---------------------------------------------------------------------- Further information Any queries should be addressed to the workshop co-chairs (Patrik Jansson and Sam Tobin-Hochstadt), via email to icfp13-workshops(a)ccs.neu.edu

1 0

How to save s-expressions
by Richard Prescott 29 Oct '12

29 Oct '12

Good morning everybody, Forgive my ignorance, I am just learning. In order to embrace the "code is data" philosophy [1], I want to load and save data as s-expressions within files. I figured the load using (read (open-input-file "data.scm")). How can I save? Thanks in advance. Richard [1]: I just learnt that it is called http://en.wikipedia.org/wiki/Homoiconicity

3 7

Nearly 20% performance improvement with -fstrict-aliasing
by Bradley Lucier 28 Oct '12

28 Oct '12

The C memory aliasing model allows certain kinds of optimizations. For example, consider the following code that's generated at the end the main loop of the FFT in _num.scm (after pulling it out of ##bignum.*): ___F64VECTORSET(___STK(-5),___R3,___F64V53) ___F64VECTORSET(___STK(-5),___R4,___F64V52) ___F64VECTORSET(___STK(-5),___STK(1),___F64V51) ___F64VECTORSET(___STK(-5),___STK(2),___F64V50) ___F64VECTORSET(___STK(-5),___STK(3),___F64V49) ___F64VECTORSET(___STK(-5),___STK(4),___F64V48) ___F64VECTORSET(___STK(-5),___STK(5),___F64V47) ___F64VECTORSET(___STK(-5),___STK(6),___F64V46) ___SET_R3(___FIXADD(___R3,___FIX(2L))) ___POLL(9) ___DEF_SLBL(9,___L9_direct_2d_fft_2d_recursive_2d_4) ___GOTO(___L22_direct_2d_fft_2d_recursive_2d_4) Here we're alternating loading elements off the stack and storing floating-point values in a vector. Under C's memory aliasing model (i.e., with -fstrict-aliasing, the gcc default), STK(-5) can be loaded into a register and reused after each floating-point store, because gcc can assume that the floating-point store does not change the value of STK(-5), since WORDs and doubles are different types. When we call gcc with -fno-strict-aliasing, then the compiler has to assume that the floating-point store may affect the value of STK(-5), so it has to reload STK(-5) before each floating-point store. This has the following effect on the time to compute 10,000 forward and 10,000 backward complex FFTs of 1,024 elements. With -fno-strict-aliasing (used now by Gambit for reasons I'll explain below): (time (do ((i 0 (fx+ i 1))) ((fx= i 10000)) (direct-fft-recursive-4 a table) (inverse-fft-recursive-4 a table) (do ((i 0 (fx+ i 1))) ((fx= i (fx* two^n 2))) (f64vector-set! a i (fl/ (f64vector-ref a i) inexact-two^n))))) 705 ms real time 704 ms cpu time (704 user, 0 system) 6 collections accounting for 2 ms real time (0 user, 0 system) 1600000 bytes allocated 22 minor faults no major faults With -fstrict-aliasing: (time (do ((i 0 (fx+ i 1))) ((fx= i 10000)) (direct-fft-recursive-4 a table) (inverse-fft-recursive-4 a table) (do ((i 0 (fx+ i 1))) ((fx= i (fx* two^n 2))) (f64vector-set! a i (fl/ (f64vector-ref a i) inexact-two^n))))) 590 ms real time 592 ms cpu time (588 user, 4 system) 6 collections accounting for 2 ms real time (4 user, 0 system) 1600000 bytes allocated 22 minor faults no major faults That's a 19% performance improvement. (And the performance isn't bad, 1.74 GFLOPS on my 2.33GHz Core 2 quad 6600. Later I'll try to get gcc to vectorize the main loop.) As I understand it, the C memory aliasing model is that once you store something of a certain type into a memory location, then you agree that everything you read from that memory location and everything else you write to that memory location will be of the same type. So why do we need -fno-strict-aliasing? I know of two reasons: (1) in gambit.h we read and write bignums as adigits, mdigits, or fdigits, and these are chunks of the bignums of different sizes (generally 64/32/8 bits on 64-bit machines, and 64/16/8 bits on 32-bit machines) and (2) I believe we sometimes access double-precision floating-point numbers as integers. Marc, maybe you know of other instances in the code. Both of these things can be fixed by accessing the internals of a bignum through a pointer type to a union of vectors of integers of the appropriate bit sizes, and doing the same for double-precision floats. (I had a much more difficult plan in mind before, of coming up with a union type of all possible Scheme objects, but that isn't necessary, I see now.) I've been trying to figure out how to make the changes to gambit.h to do this in a clean way but without luck. Marc, you're the über programmer, do you have time to look at this? Brad

2 2

Gamsock now up on the Dumping Ground
by Jeff Read 25 Oct '12

25 Oct '12

All, The socket library I've been working off-and-on on for some time is now listed on the Dumping Ground. Gamsock is a POSIX socket library with an API similar to the Scsh socket API. It makes applications possible with Gambit that aren't possible with its built in TCP port API, including applications that use UDP, or Unix-domain or IPv6 sockets. It's available on GitHub: https://github.com/bitwize/gamsock Happy socket hacking! --Jeff

3 3

hello
by Hugh Aguilar 22 Oct '12

22 Oct '12

I'm getting started in Gambit Scheme. I'm working with Windows right now, although I may upgrade to Linux later on. My goals are these: 1.) Use Gambit as an overgrown macro-assembler for compiler-writing. 2.) Use Gambit as an embedded scripting language inside of C programs. I'm also learning Lua, which is similar, but Gambit is a lot more powerful. This is will be for a CAM program that generates gcode for CNC machines. Right now, as a learning exercise, I'm writing a toy program. This is something I wrote in SuperForth for the Commodore-64 when I was 18. It is turtle graphics in 4 dimensions (axis W, X, Y and Z). A image of the 3D aspect of the 4D object is shown, with the lines receding towards a vanishing point. The perspective can be rotated around any of the 4 axis. My intention is to make the REPL available to the user similar to Logo. I have a few questions: 1.) Where can I get the 64-bit x86 assembler that Mark Feeley mentioned to me? 2.) What C compiler can be used to compile Gambit? I don't want to spend any money right now, although I may later buy Visual C/C++. 3.) Do you have a wrapper for Cairo or anything else similar? I just need to draw straight lines --- I don't need bezier curves and all of that fancy stuff. This is for the game right now, although later on I will need something like this for the CNC. Thanks for your help --- Hugh

2 1

Systematic Segmentation fault on MacOS 10.8.2
by Richard Prescott 22 Oct '12

22 Oct '12

Hello everybody, First of all, thanks in advance to people contributing and helping out others. I am new to this list, to scheme, and even to MacOS so apologize my ignorance. Although, I am a old timer Unix C programmer so we should meet somewhere. I choose gambit to learn scheme because I am from Montreal and because I am interested into BIT and PICOBIT. Unfortunately, apart from saying hello, I come to this mailing list for help. I followed instructions off the website $ wget http://www.iro.umontreal.ca/~gambit/download/gambit/v4.3/source/gambc-v4_3_… $ tar zxf gambc-v4_3_2-devel.tgz $ cd gambc-v4_3_2-devel $ ./configure --enable-single-host $ make bootstrap and then boom! $ ./bin/gsi-script Segmentation fault: 11 Moreover: $ gdb ./bin/gsi-script GNU gdb 6.3.50-20050815 (Apple version gdb-1820) (Sat Jun 16 02:40:11 UTC 2012) Copyright 2004 Free Software Foundation, Inc. GDB is free software, covered by the GNU General Public License, and you are welcome to change it and/or distribute copies of it under certain conditions. Type "show copying" to see the conditions. There is absolutely no warranty for GDB. Type "show warranty" for details. This GDB was configured as "x86_64-apple-darwin"...Reading symbols for shared libraries .. done (gdb) r Starting program: /Users/rip/Documents/Ideas/Embedded_Lisp/BIT/gambc-v4_3_2-devel/bin/gsi-script Reading symbols for shared libraries +............................. done Program received signal EXC_BAD_ACCESS, Could not access memory. Reason: KERN_INVALID_ADDRESS at address: 0x0000000000000001 0x0000000000000001 in ?? () (gdb) bt #0 0x0000000000000001 in ?? () Cannot access memory at address 0x1 #1 0x01000000010031ba in ?? () Any idea what am I doing wrong ? Best Regards Richard Prescott

3 6

Re "SRFI 75: Unicode", rather for reference: Gambit+this lib provides all of its functionality. It would be possible to make a "srfi75" wrapper module. Re: Unicode library released
by Mikael 16 Oct '12

16 Oct '12

Ah, for a sidenote, it struck me this library extremely easily can be wrapped into a "SRFI 75: Unicode" implementation almost only through procedure renaming. For SRFI 75: Unicode, see: http://srfi.schemers.org/srfi-75/srfi-75.html So, this is just to mention that all the functionality of SRFI 75 is already implemented within the combo of Gambit + this Unicode lib. If anyone would see a reason for bringing this functionality into the exact naming used in SRFI 75 and releasing this under the name of a "srfi75" wrapper library (spontaneously I didn't quite see any reason for this til now, except for perhaps cross-Scheme-system-compatibility reasons), you're free to mention this here and/or implement it. Brgds, M Basically Gambit already implements 80% of SRFI 75 by it using Unicode fully internally and in all of its char and string representaitons, the only remaining things being case-insensitive comparison and upcasing/downcasing operations i.e. string-ci=? string-ci<? string-ci>? string-ci<=? string-ci>=? char-ci<? char-ci=? char-ci=? char-upper-case? char-lower-case? char-title-case? char-title-case? char-upcase char-downcase char-titlecase char-foldcase string-upcase string-downcase string-foldcase string-titlecase These, Gambit essentially implements but regarding the US charset only. This Unicode library implements them for the entire Unicode standard but under different function names. (I believe the functionality is implemented exactly according to the SRFI 75 spec, though this would need to be double-checked and if anything needs to be adjusted to match, it ought to be completely minor.) Perhaps there could be a benefit of having the Gambit-provided ANSI-only correspondents of the abovementioned procedures left referred to under some name though. Perhaps even the original name, and thus having the unicode ones under separate names, as it is with this Unicode lib already. 2012/5/21 Mikael <mikael.rcv(a)gmail.com> > Hi guys, > > A Unicode library for Gambit has been released. > > Many thanks to Florian Loitsch for releasing the Unicode library for > Bigloo, of which this library in many respects is a port. > > The Unicode library for Gambit does the following Unicode handling: > > unicode-char-upper unicode-char-lower > unicode-string-upper unicode-string-upper! ; "aBc" => "ABC" > unicode-string-lower unicode-string-lower! ; "aBc" => "abc" > unicode-string-capitalize-strict! unicode-string-capitalize-strict ; > "aBc" => "Abc" > string-unicode-ci<? string-unicode-ci<=? string-unicode-ci=? > string-unicode-ci>? string-unicode-ci>=? > > It runs out of the box on vanilla Gambit and on Black Hole. > > License is New BSD. > > It's both released on the Dumping grounds > http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Dumping_Grounds and > on GitHub at https://github.com/m-i-k-a-e-l/gambit-unicode . > > For some more info, please see the copy of the library headers below. > > Kind regards, > Mikael > > - > > Gambit Unicode library 1.0 > New BSD license > > Enables Gambit Scheme with Unicode handling features. > Runs out of the box on vanilla Gambit and on Black Hole. > > The Gambit-specific code and distribution: > Copyright (C) 2010-2012 Mikael More > > The unicode-data.scm generator and Bigloo unicode library this library was > inspired by, > found in the bigloo-unicode directory: > Copyright (C) 2007-2012 Florian Loitsch > > The source data for the unicode-data.scm generator, found in the > bigloo-unicode/data directory: > Copyright (C) 1991-2011 Unicode, Inc. > > ## Exports > unicode-char-upper > unicode-char-lower > unicode-string-upper unicode-string-upper! ; "aBc" => "ABC" > unicode-string-lower unicode-string-lower! ; "aBc" => "abc" > unicode-string-capitalize-strict! ; "aBc" => "Abc" > unicode-string-capitalize-strict ; > string-unicode-ci<? > string-unicode-ci<=? > string-unicode-ci=? > string-unicode-ci>? > string-unicode-ci>=? > > ## Relation with Bigloo Unicode library. Intended scope of use of this > library. > This library is based on the Unicode library for Bigloo Scheme by Florian > Loitsch, as bundled > with the js2scheme distribution as found on > http://code.google.com/p/js2scheme/source/browse/ . > A copy of this library is provided in this distribution in the > bigloo-unicode directory, > to enable you to easily generate Unicode constants based on any new > Unicode Character Database > versions. > The vesion of the Bigloo Unicode library bundled here is was pulled > from the abovementioned > repo the 13:t of May 2012. Florian's last changes were the 12:th of March > 2011. Florian's code is > to be viewed as stable since at least 2010, to the best of my knowledge > the only changes since > then have been minor restructurings. > > Please note that the scope of this library and the Bigloo unicode library > are different, in that > Gambit has complete native Unicode character handling and charset > encoding/decoding features > built-in and thus none of this needs to be provided in a separate library, > whereas the > Bigloo Unicode library provides such functionality to Bigloo. > > ## Distribution overview > unicode.scm - The Gambit Unicode handling library > unicode-data.scm - The constants required to make unicode.scm spin. > Generated out of the Unicode Character Database. > bigloo-unicode/* - Florian Loitsch's unicode-data.scm generator, and > Bigloo Unicode library > that was used as inspiration for making this > library. > Use this to generate a new unicode-data.scm out of > a Unicode Character > Database update, if that would ever be released > and relevant. > Latest version as of the 13:th of May 2012, see > more above. > bigloo-unicode/data/* - The required files of the Unicode Character > Database, see below. > > ## How to update unicode-data.scm with a new version of the Unicode > Character Database > In case by any reason this would ever be relevant, here is how to proceed: > > Update the bigloo-unicode/data/ files (namely SpecialCasing.txt and > UnicodeData.txt) with > the new Unicode Character Database files. > > As of the date of writing, these are released on > http://www.unicode.org/Public/UNIDATA/SpecialCasing.txt and > http://www.unicode.org/Public/UNIDATA/UnicodeData.txt , > and you can see the release date of the latest update of them on > http://www.unicode.org/Public/UNIDATA/ . > >

1 0

Don't understand effects of (declare fixnum)
by Bradley Lucier 12 Oct '12

12 Oct '12

Marc: Here's some code (motivated by Programming Praxis): (declare (standard-bindings) (extended-bindings) (block) ;; (fixnum) (not safe)) (define (same? n) (let loop ((n n) (rs '())) (and (not (zero? n)) (let ((r (random-integer 365))) (or (memv r rs) (loop (- n 1) (cons r rs))))))) When compiled, this expands the memv into a loop and then expands the eqv? in the memv loop: (define same? (lambda (n) (letrec ((loop (lambda (n rs) (and ('#<procedure #19 ##not> (if ('#<procedure #2 ##fixnum?> n) ('#<procedure #3 ##fxzero?> n) (if ('#<procedure #4 ##flonum?> n) ('#<procedure #5 ##flzero?> n) ('#<procedure #6 zero?> n)))) (let ((r (random-integer 365))) (or (letrec ((loop.14 (lambda (r lst1.15) (if ('#<procedure #7 ##pair?> lst1.15) (let ((x.16 ('#<procedure #8 ##car> lst1.15))) (if (or ('#<procedure #9 ##eq?> r x.16) (and ('#<procedure #10 ##subtyped?> r) (and ('#<procedure #10 ##subtyped?> x.16) (and ('#<procedure #11 ##fx=> ('#<procedure #12 ##subtype> r) ('#<procedure #12 ##subtype> x.16)) ('#<procedure #13 ##eqv?> r x.16))))) lst1.15 (loop.14 r ('#<procedure #14 ##cdr> lst1.15)))) #f)))) (loop.14 r rs)) (let ((n (if ('#<procedure #2 ##fixnum?> n) (let ((temp.21 ('#<procedure #15 ##fx-?> n 1))) (if temp.21 temp.21 ('#<procedure #16 -> n 1))) ('#<procedure #16 -> n 1))) (rs ('#<procedure #17 ##cons> r rs))) (and ('#<procedure #19 ##not> (if ('#<procedure #2 ##fixnum?> n) ('#<procedure #3 ##fxzero?> n) (if ('#<procedure #4 ##flonum?> n) ('#<procedure #5 ##flzero?> n) ('#<procedure #6 zero?> n)))) (let ((r (random-integer 365))) (or (letrec ((loop.14 (lambda (r lst1.15) (if ('#<procedure #7 ##pair?> lst1.15) (let ((x.16 ('#<procedure #8 ##car> lst1.15))) (if (or ('#<procedure #9 ##eq?> r x.16) (and ('#<procedure #10 ##subtyped?> r) (and ('#<procedure #10 ##subtyped?> x.16) (and ('#<procedure #11 ##fx=> ('#<procedure #12 ##subtype> r) ('#<procedure #12 ##subtype> x.16)) ('#<procedure #13 ##eqv?> r x.16))))) lst1.15 (loop.14 r ('#<procedure #14 ##cdr> lst1.15)))) #f)))) (loop.14 r rs)) (loop (if ('#<procedure #2 ##fixnum?> n) (let ((temp.21 ('#<procedure #15 ##fx-?> n 1))) (if temp.21 temp.21 ('#<procedure #16 -> n 1))) ('#<procedure #16 -> n 1)) ('#<procedure #17 ##cons> r rs)))))))))))) (loop n '())))) When you uncomment the (fixnum) declaration then the memv is expanded, but the eqv? is not: (define same? (lambda (n) (letrec ((loop (lambda (n rs) (and ('#<procedure #10 ##not> ('#<procedure #2 ##fxzero?> n)) (let ((r (random-integer 365))) (or (letrec ((loop.7 (lambda (r lst1.8) (if ('#<procedure #3 ##pair?> lst1.8) (let ((x.9 ('#<procedure #4 ##car> lst1.8))) (if ('#<procedure #5 ##eqv?> r x.9) lst1.8 (loop.7 r ('#<procedure #6 ##cdr> lst1.8)))) #f)))) (loop.7 r rs)) (loop ('#<procedure #7 ##fx-> n 1) ('#<procedure #8 ##cons> r rs)))))))) (loop n '())))) The trampoline call to ##eqv? in the inner loop is worse than calling the system memv once, because the call to ##eqv? in the system memv is expanded by the compiler. Brad

1 0