July 2006 - Gambit-list - mailman.iro.umontreal.ca

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

Re: [gambit-list] Can Gambit programs be safely fork()'ed?
by TJay 02 Aug '06

02 Aug '06

On 7/31/06, Christian <christian(a)pflanze.mine.nu> wrote: > At 1:04 Uhr +0800 31.07.2006, TJay wrote: > >I wasn't thinking about file descriptors in particular. I was > >wondering whether gambit itself has any internal state that's not > >friendly with fork(). (I have no idea what these states might > >include.) > > I think I've already given my non-authoritative answer (just a > guess): if you have multiple gambit threads running, then call fork, > both processes will continue running all the threads, and if you > print some stuff to buffered ports but do not flush nor close > (through the POSIX call) them, you'll get output being printed twice. > I don't know how I would handle the former problem (I think there's > no place where Gambit is doing this already; the only place where > Gambit calls fork is in implements > ___device_stream_setup_from_process in os_io.c and there is no need > to shut down other threads as exec is called immediately). I see. I've not thought of how threads would be affected, and I'd hate to think of the kinds of strange, hidden bugs I'd get from unflushed buffered ports. I'll have to be super careful if I do any forking. > BTW using fork as opposed to starting subprocesses using open-process > will probably not give you much of an advantage, if you load all code > as compiled shared libraries, since almost all shareable memory will > then be shared anyway, and you don't seem to want to fork chilren at > a high frequency. You're right. It might be easier to just call open-process. Thanks for the heads up. tj

2 1

creating scheme ports from filehandles
by Christian 02 Aug '06

02 Aug '06

Hello Is there a way to turn a POSIX filehandle into a Gambit scheme port, or could it be added? I'm imaging something like: (posix-fd->port 0) => returning an input-output port or (open-port (list posix-fd: 0 direction: 'input)) ;; in case one wants ;; the direction to be preserved. or similar. This would allow things like implement functions creating unix sockets, or maybe even UDP ports; well for the latter maybe more changes would actually be needed. Maybe I should ask (instead of the above) how one can, from a C function, read/write from/to a file descriptor without blocking the system (using the scheduler, thus possibly running other scheme code in the mean time). Thanks Christian.

2 3

Call for Participation: Scheme & Functional Programming Workshop 2006
by Robby Findler 31 Jul '06

31 Jul '06

Dear all, The Scheme and Functional Programming Workshop pre-registration deadline is in about 2 and a half weeks -- do be sure to register for ICFP and the workshop before then. Come to hear Manuel Serrano talk about HOP, his new language for programming the web, a status report from the R6RS editors, and presentations of the work below. I look forward to seeing you in Portland! http://scheme2006.cs.uchicago.edu/ Best, Robby ======================================== A Self-Hosting Evaluator using HOAS Eli Barzilay (Northeastern University) We demonstrate a tiny, yet non-trivial evaluator that is powerful enough to run practical code, including itself. This is made possible using a Higher-Order Abstract Syntax (HOAS) representation -- a technique that has become popular in syntax-related research during the past decade. With a HOAS encoding, we use functions to encode binders in syntax values, leading to an advantages of reflecting binders rather than re-implementing them. In Scheme, hygienic macros cover problems that are associated with binders in an elegant way, but only when extending the language, i.e., when we work at the meta-level. In contrast, HOAS is a useful object-level technique, used when we need to represent syntax values that contain bindings -- and this is achieved in a way that is simple, robust, and efficient. We gradually develop the code, explaining the technique and its benefits, while playing with the evaluator. >From Variadic Functions to Variadic Relations William E. Byrd and Daniel P. Friedman (Indiana University) Scheme makes it easy to define variadic functions, which take an arbitrary number of arguments; miniKanren, a logic programming language embedded in R5RS Scheme, makes it easy to define variadic relations. A variadic miniKanren relation takes two arguments: a list containing input arguments and an output argument. A fresh or partially-instantiated logic variable passed to a variadic relation can represent the list of input arguments. A relation may also be super-variadic---such a relation takes a list of lists of input arguments. We show the variadic and super-variadic relational equivalent of several variadic functions, examples of their use, and several abstractions over these relations. We also present a brief miniKanren overview, along with an R5RS-compliant implementation of the subset of miniKanren that we use. Experiences with Scheme in an Electro-Optics Laboratory Richard Cleis and Keith Wilson (Air Force Research Laboratory) The Starfire Optical Range is an Air Force Research Laboratory engaged in Atmospheric Research near Albuquerque, New Mexico. Since the late 1980's it has developed numerous telescope systems and auxiliary devices. Nearly all are controlled by C programs that became difficult to manage due to the large number of configurations required to support the experiments. To alleviate the problem, Scheme has been introduced in at least six distinct ways. This paper describes the uses of Scheme, emerging programming techniques, and general experiences of the past several years. Rapid Case Dispatch in Scheme William D. Clinger (Northeastern University) The case expressions of Scheme can and should be implemented efficiently. A three-level dispatch performs well, even when dispatching on symbols, and scales to large case expressions. A Stepper for Scheme Macros Ryan Culpepper, Matthias Felleisen (Northeastern University) Even in the days of Lisp's simple defmacro systems, macro developers did not have adequate debugging support from their programming environment. Modern Scheme macro expanders are more complex than Lisp's, implementing lexical hygiene, referential transparency for macro definitions, and frequently other source properties. Scheme implementations, however, have only adapted Lisp's inadequate macro inspection tools. Unfortunately, these tools rely on a rather naive model of the expansion process, thus leaving a large gap between Scheme's complex mode of expansion and what the programmer sees. In this paper, we present a macro debugger with full support for modern Scheme macros. To construct the debugger, we have extended the macro expander so that it issues a series of expansion events. A parser turns these event streams into derivations in a natural semantics for macro expansion. From these derivations, the debugger extracts a reduction-sequence (stepping) view of the expansion. A programmer can specify with simple policies which parts of a derivation to omit and which parts to show. Last but not least, the debugger includes a syntax browser that graphically displays the various pieces of information attached to syntactic tokens. Automatic construction of parse trees for lexemes Danny Dub\'e (Universit\'e Laval) and Anass Kadiri (EPITA, Paris France) Recently, Dub\'e and Feeley presented a technique that makes lexical analyzers able to build parse trees for the lexemes that match regular expressions. While parse trees usually demonstrate how a word is generated by a context-free grammar, these parse trees demonstrate how a word is generated by a regular expression, in an analogous fashion. This paper describes the adaptation and implementation of that technique in a concrete lexical analyzer generator. The adaptation of the technique includes extending it to the rich set of operators handled by the generator and reversing the direction of the parse trees construction so that it corresponds to the natural right-to-left direction of the Scheme lists construction. The implementation of the adapted technique includes modifications to both the generation-time and the run-time parts of the generator. Uses of the new addition and empirical measurements of its cost are presented. Extensions and alternatives to the technique are considered. Concurrency Oriented Programming in Termite Scheme Guillaume Germain, Marc Feeley, Stefan Monnier (Universit\'e de Montr\'eal) Termite is a language and system offering a simple and powerful tool for expressing distributed computation. It is based on a message-passing model of concurrency inspired by Erlang, and on a variant of the functional language Scheme. Our system is an appropriate tool for building custom protocols and abstractions for distributed computation. Its open network model allows for the building of non-centralized distributed applications. The possibility of failure is reflected in the model, and ways to handle them are proposed. The existence of first-class continuations is exploited in order to allow the expression of high-level concepts such as migration of processes. We describe the Termite model with its implications and describe sample applications built with Termite. We conclude with a discussion of the current implementation and its performance. An Incremental Approach to Compiler Construction Abdulaziz Ghuloum (Indiana University) Compilers are perceived to be magical artifacts, carefully crafted by the wizards, and unfathomable by the mere mortals. Books on compilers are better described as wizard-talk: written by and for a clique of all-knowing practitioners. Real-life compilers are too complex to serve as an educational tool. And the gap between real-life compilers and the educational toy compilers is too wide. The novice compiler writer stands puzzled facing an impenetrable barrier, ``better write an interpreter instead.'' The goal of this paper is to break that barrier. We show that building a compiler can be as easy as building an interpreter. The compiler we construct accepts a large subset of the Scheme programming language and produces assembly code for the Intel-x86 architecture, the dominant architecture of personal computing. The development of the compiler is broken into many small incremental steps. Every step yields a fully working compiler for a progressively expanding subset of Scheme. Every compiler step produces real assembly code that can be assembled then executed directly by the hardware. We assume that the reader is familiar with the basic computer architecture: its components and execution model. Detailed knowledge of the Intel-x86 architecture is not required. The development of the compiler is described in detail in an extended tutorial. Supporting material for the tutorial such as an automated testing facility coupled with a a comprehensive test suite are provided with the tutorial. It is our hope that current and future implementors of Scheme find in this paper the motivation for developing high-performance compilers and the means for achieving that goal. Sage: Hybrid Checking for Flexible Specifications Jessica Gronski (University of California, Santa Cruz (UCSC)), Kenneth Knowles (UCSC), Aaron Tomb (UCSC), Stephen N. Freund (Williams College), and Cormac Flanagan (UCSC) Software systems typically contain large APIs that are informally specified and hence easily misused. This paper presents the Sage programming language, which is designed to enforce precise interface specifications in a flexible manner. The Sage type system uses a synthesis of the type ``dynamic'', first-class types, and arbitrary refinement types. Since type checking for this expressive language is not statically decidable, Sage uses hybrid type checking, which extends static type checking with dynamic contract checking, automatic theorem proving, and a database of refuted subtype judgments. Interaction-Safe State for the Web Jay McCarthy and Shriram Krishnamurthi (Brown University) Recent research has demonstrated that continuations provide a clean basis to describe interactive Web programs. This account, however, provides only a limited description of state, which is essential to several Web applications. This state is affected by the numerous control operators (known as navigation buttons) in Web browsers, which make Web applications behave in unexpected and even erroneous ways. We describe these subtleties as discovered in the context of working Web applications. Based on this analysis we present linguistic extensions that accurately capture state in the context of the Web, presenting a novel form of dynamic scope. We support this investigation with a formal semantics and a discussion of applications. The results of this paper have already been successfully applied to working applications. Component Deployment with PLaneT: You Want it Where? Jacob Matthews (University of Chicago) For the past two years we have been developing PLaneT, a package manager built into PLT Scheme's module system that simplifies program development by doing away with the distinction between installed and uninstalled packages. In this paper we explain how PLaneT works and the rationales behind our major design choices, focusing particularly on our decision to integrate PLaneT into PLT Scheme and the consequences that decision had for PLaneT's design. We also report our experience as PLaneT users and developers and describe what have emerged as its biggest advantages and drawbacks. Scheme for Client-Side Scripting in Mobile Web Browsing, or AJAX-Like Behavior Without Javascript Ray Rischpater (Rocket Mobile, Inc.) I present an implementation of Scheme embedded within a Web browser for wireless terminals. Based on a port of TinyScheme integrated with RocketBrowser, an XHTML-MP browser running on Qualcomm BREW-enabled handsets, the resulting application can support the same use cases as traditional JavaScript-enabled browsers, including asynchronous programming recently popularized via AJAX (Asynchronous Javascript and XML). In addition to a comparison of the resulting script capabilities, I present the changes required to bring TinyScheme to Qualcomm BREW, including adding support for BREW components as TinyScheme data types. SHard: a Scheme to Hardware Compiler Xavier Saint-Mleux (Universit\'e de Montr\'eal), Marc Feeley (Universit\'e de Montr\'eal) and Jean-Pierre David (\'Ecole Polytechnique de Montr\'eal) Implementing embedded systems in hardware can have several benefits (performance, power usage, etc.). Current hardware/software co-design methodologies, which offer a language for describing hardware and another language for programming the software, put the burden of system partitioning on the developer, which is tedious and makes component transformation and reuse difficult. Our goal is to put most of this burden on the compiler through the use of a single, simple programming language. We describe a prototype compiler that compiles a functional subset of Scheme into a high-level description of dataflow parallel hardware. The compiler supports tail and non-tail function calls and higher-order functions. Our approach makes it possible to implement software algorithms in hardware with very few modifications (e.g. IO channel declaration). Performance results of our system are given for FPGA hardware. Gradual Typing for Functional Languages Jeremy G. Siek and Walid Taha (Rice University) Static and dynamic type systems have well-known strengths and weaknesses, and each is better suited for different programming tasks. There have been many efforts to integrate static and dynamic typing and thereby combine the benefits of both typing disciplines in the same language. The flexibility of static typing can be improved by adding a type Dynamic and a typecase form. The safety and performance of dynamic typing can be improved by adding optional type annotations or by performing type inference (as in soft typing). However, there has been little formal work on type systems that allow a programmer-controlled migration between dynamic and static typing. Thatte proposed Quasi-Static Typing, but it does not statically catch all type errors in completely annotated programs. Anderson and Drossopoulou defined a nominal type system for an object-oriented language with optional type annotations. However, developing a sound, gradual type system for functional languages with structural types is an open problem. In this paper we present a solution based on the intuition that the structure of a type may be partially known/unknown at compile-time and the job of the type system is to catch incompatibilities between the known parts of types. We define the static and dynamic semantics of a lambda-calculus with optional type annotations and we prove that its type system is sound with respect to the simply-typed lambda-calculus for fully-annotated terms. We prove that this calculus is type safe and that the cost of dynamism is ``pay-as-you-go''.

1 0

(load ...) return value?
by TJay 31 Jul '06

31 Jul '06

Is there a way to make (load "a-file") return the value of the last expression in "a-file"? I'm writing a plugin system for my program and right now, I make all plugins append themselves to a globally defined list, which is none too pretty and very much inelegant. tj

1 0

Can Gambit programs be safely fork()'ed?
by TJay 30 Jul '06

30 Jul '06

I'm new to multiprocess programming, but I know that if I fork an X program, the X connections "get duplicated", so the forked process shares the same window/etc as its parent... I'm wondering if programs compiled with Gambit can be cleanly forked, with the child and parent being completely separate. tj

3 4

runtime settings
by Ryan Prescott 28 Jul '06

28 Jul '06

What is the proper way to set runtime settings for a compiled scheme program? Does an executable compiled with: gsc -:tl myfile.scm "inherit" the -:tl setting? Likewise for c initiated scheme apps? by setting the setup struct's members? Thanks, Ryan

2 1

Gambit bugzilla
by Marc Feeley 24 Jul '06

24 Jul '06

I am pleased to announce that Gambit now has a bug tracking system (which is powered by bugzilla). If you want to report a bug, suggest a feature, or search for reported bugs please do so here: http://www.iro.umontreal.ca/~gambit/bugzilla/ This should be easier to manage that searching the mailing list. The mailing list should still be used to get general help. The bug tracking system should be used when you know, or strongly suspect, that Gambit is not behaving properly, or if you have suggestions for improvements. To submit new bug reports and to get email when new bugs are reported, you need to create an account at: http://www.iro.umontreal.ca/~gambit/bugzilla/createaccount.cgi Creating an account is a 1 minute process (give email address and real name and then retrieve password in your email). Marc

1 0

Re: [gambit-list] Hakmem bitcount.
by Bradley Lucier 24 Jul '06

24 Jul '06

(I'm replying to the mailing list too, since they're CC'ed on the original.) On Jul 23, 2006, at 10:01 PM, Marc Feeley wrote: > I could add (fxbit-count n), as per R6RS, and inline it to > ___FIXBITCOUNT which can implement hakmem. The bignum case could > be build on top of fxbit-count. Does that make sense? Sure. Sounds like the GVM is getting closer and closer to milli-code ... ;-) Brad

1 0

Hakmem bitcount.
by Bradley Lucier 24 Jul '06

24 Jul '06

Marc: This comp.lang.lisp thread http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/ b1cdf3a5106abe59/545e852f2be87053#545e852f2be87053 discusses various fixnum bitcount algorithms, so I tried these three: (declare (standard-bindings)(extended-bindings)(block)(fixnum)(not safe)(not interrupts-enabled)) (define (bits n) ;; remove one bit at a time (let loop ((i 0) (n n)) (if (zero? n) i (loop (+ i 1) (##fixnum.bitwise-and n (- n 1)))))) (define (my-bitcount x) ;; do 6 at a time, from _num.scm (define (at-most-6 x) (##u8vector-ref '#u8(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6) x)) (define (count x n) (if (##fixnum.< x 64) (##fixnum.+ n (at-most-6 x)) (count (##fixnum.arithmetic-shift-right x 6) (##fixnum.+ n (at-most-6 (##fixnum.bitwise-and x 63)))))) (count x 0)) (define (hakmem-bitcount n) (let* ((i (+ (##fixnum.bitwise-and n #x5555555) (##fixnum.bitwise-and (##fixnum.arithmetic-shift-right n 1) #x5555555))) (i (+ (##fixnum.bitwise-and i #x3333333) (##fixnum.bitwise-and (##fixnum.arithmetic-shift-right i 2) #x3333333))) (i (+ (##fixnum.bitwise-and i #xf0f0f0f) (##fixnum.bitwise-and (##fixnum.arithmetic-shift-right i 4) #xf0f0f0f))) (i (+ i (##fixnum.arithmetic-shift-right i 8))) (i (+ i (##fixnum.arithmetic-shift-right i 16) (##fixnum.arithmetic-shift-right n 28)))) (##fixnum.bitwise-and i #xff))) ;; time them, including calling the system routine (time (do ((i 0 (+ i 1))) ((= i 20000000)) (bits i))) (time (do ((i 0 (+ i 1))) ((= i 20000000)) (bit-count i))) (time (do ((i 0 (+ i 1))) ((= i 20000000)) (my-bitcount i))) (time (do ((i 0 (+ i 1))) ((= i 20000000)) (hakmem-bitcount i))) which yields [brad:~/Desktop] lucier% gsi bittest (time (do ((i 0 (+ i 1))) ((= i 20000000)) (bits i))) 927 ms real time 572 ms cpu time (565 user, 7 system) no collections no bytes allocated no minor faults no major faults (time (do ((i 0 (+ i 1))) ((= i 20000000)) (bit-count i))) 8225 ms real time 4446 ms cpu time (4394 user, 52 system) no collections no bytes allocated no minor faults no major faults (time (do ((i 0 (+ i 1))) ((= i 20000000)) (my-bitcount i))) 1067 ms real time 588 ms cpu time (582 user, 6 system) no collections no bytes allocated no minor faults no major faults (time (do ((i 0 (+ i 1))) ((= i 20000000)) (hakmem-bitcount i))) 638 ms real time 352 ms cpu time (349 user, 3 system) no collections no bytes allocated no minor faults no major faults From which I conclude that (a) doing 6 at a time really isn't better than doing one at a time, (b) as usual, the trampoline takes an enormous amount of time, (c) the hakmem approach doesn't help too much on average, and (d) it would be best to find a way to specialize bit-count (and other small routines like it that aren't single GVM instructions) for fixnum arguments. Brad

1 0