06 Aug 2007

macros and hygiene, resumed

posted by matthias

The Friday entry demonstrates how to break hygiene for a macro that defines a generator. Ryan Culpepper, the local macrologist, reminded me that expanding into this macro goes wrong in the syntax-case world:

(define-syntax define-that-expands-into-define/y 
  (syntax-rules ()
    ((_ (name arg ...) body ...) 
     (define/y (name arg ...) body ...))))

(define-that-expands-into-define/y (bar)
  (yield 1)
  (yield 2)
  'finished)

Run this in Pretty Big [DrScheme] and you get a strange note concerning MrEd’s yield or run it in MzScheme [Textual] and you get an error message about ‘yield’ being unbound.

What gives? The ‘stx’ of datum->syntax-object is the syntactic context of the new macro but it doesn’t bind yield; it just uses it. So the definition of yield in define/y must be a different one according to the hygiene standards. Ergo yield is free at the top-level [MzScheme] or bound to the yield import from MrEd [Pretty Big].

How can we try to fix this? The explanation suggests we use a different macro definition for define/y, one that uses a context that is guaranteed from the body of an instance of define/y:

(require (lib "control.ss"))

(define-syntax (define/y stx)
  (syntax-case stx ()
    [(_ (name arg ...) body0 body ...)
     (with-syntax 
         ((yield-name 
           (datum->syntax-object (syntax body0) 'yield)))
       (syntax
        (define (name arg ...)
          (define (yield-name x)
            (control resume-here
             (set! name 
                   (lambda ()
                     (prompt (resume-here 'dummy))))
             x))
          (prompt body0 body ...))))]))

(define-syntax define-that-expands-into-define/y 
  (syntax-rules ()
    ((_ (name arg ...) body ...) 
     (define/y (name arg ...) body ...))))

;; --- try it out ---

(define-that-expands-into-define/y (bar)
  (yield 1)
  (yield 2)
  'finished)

(list (bar) (bar) (bar) (bar))

Run it. You will find that it works as expected.

Tomorrow, time permitting, I will tell you what’s wrong with it and how you can fix it.

more →

03 Aug 2007

control and macros

posted by matthias

After reading the posts on control operators, Vlado Zlatanov decided to look into prompt, control, fcontrol and the rest of the goodies in control.ss.

So based on the example from the blog post I did this python-like snippet:

(define/y (step) 
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

He decided to look into turning it into a macro, such that the above ends up being correct code. When he got stuck, he asked on our mailing list and the resulting dialog was so informative that I decided to blog it.

My first replay was this suggestion:

(define-syntax define/y
  (syntax-rules ()
    [(_ yield-name (name arg ...) body ...)
     (define (name arg ...)
       (define exit-with #f)
       (define (switch-control-context th)
         (call/cc 
          (lambda (k)
            (set! exit-with k)
            (th))))
       (define (yield-name x)
         (call/cc 
          (lambda (resume-here)
            (set! name 
               (lambda () 
                 (switch-control-context 
                  (lambda () 
                     (resume-here 'dummy)))))
            (exit-with x))))
       (switch-control-context (lambda () body ...)))]))

I sent this out with two suggestions.

First, use control.ss to simplify the code. Second, use syntax-case to eliminate the need for the programmer-user of define/y to specify the name of yield.

So, here is the prompt-based code:

(require (lib "control.ss"))

(define-syntax define/y
  (syntax-rules ()
    [(_ yield-name (name arg ...) body ...)
     (define (name arg ...)
       (define (yield-name x)
         (control resume-here
            (set! name
                  (lambda ()
                    (prompt (resume-here 'dummy))))
            x))
       (prompt body ...))]))

(define/y yield (step) 
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

(equal? '(1 2 3) (list (step) (step) (step)))

This time I include a test case that assures the proper return behavior of yield. The definition of define/y shows how to mark the return point with prompt and how to switch to this point with control so that your generator can resume the traversal at the place where it was interrupted.

For the second challenge, I wrote this definition:

(require (lib "control.ss"))

(define-syntax (define/y stx)
  (syntax-case stx ()
    [(_ (name arg ...) body ...)
     (with-syntax 
         ((yield-name (datum->syntax-object stx 'yield)))
       (syntax
        (define (name arg ...)
          (define (yield-name x)
            (control resume-here
             (set! name 
                   (lambda ()
                     (prompt (resume-here 'dummy))))
             x))
          (prompt body ...))))]))

(define/y (step) 
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

(equal? '(1 2 3) (list (step) (step) (step)))

If you compare the two macro definitions, you notice very little difference. Indeed, what really differs is the “interface” (the API), that is, the way you can use the macro: see the test case. What also differs is that the definition uses syntax-case and with-syntax to inject yield into the body of define/y.

In response, Vlado wrote “but isn’t this non-hygienic.” Here is my response:

Hygiene is a uniformity default imposed on the expander with a provision for programmers to choose the non-default. I chose this word carefully when I coined the phrase. So what you have is a hygienic solution.

In other words, injecting an identifier into a macro is not a violation of hygiene at all. It’s just means using the full power of the macro system.

more →

03 Aug 2007

Experience Report: Scheme in Commercial Web Application Development

posted by Noel

Our paper “Experience Report: Scheme in Commercial Web Application Development” is online. As the title suggests, it describes our experiences over the past year developing a number of web-based applications in PLT Scheme. If we’d chosen a language like Java or Ruby we could have used a large number of libraries developed for web apps, whereas PLT Scheme has relatively few libraries in this area, and they haven’t been tested under high load. So we were gambling that Scheme would make us so productive we could develop our own libraries and the applications we were contracted to produce in the same time it would take to develop just the applications in another language. It was a gamble that paid off. You’ll have to read the paper for all the details, but suffice to say we delivered the applications on time (and more are in development) and our libraries already compare well against big names like Ruby on Rails and J2EE.

On thing that got cut from the paper was our use of Flapjax is parts of the interface. If you write complicated Javascript to take a look at it. It really does simplify event handling, and our code using Flapjax is half the size of our original code without it.

Update: This is more or less the same post as on Untyping

more →

02 Aug 2007

Relationally-Parametric Polymorphic Contracts

posted by Shriram Krishnamurthi

We’ve been making progress on the connection between types and contracts. This paper is a step towards answering the question, “What would polymorphic types (a la Standard ML) look like in a contract world?” If you haven’t thought much about polymorphic types, you may find the answer has some subtlety; if you have, hopefully you will find the answer reasonable.

Arjun and I want to point out that some of the work in this paper was already in an earlier paper that Jacob and Robby wrote, but the material was excised from the public version, so we weren’t aware of it. But there is some fresh material here as well, and anyway Robby and I have been gabbing about this question for years.

more →

30 Jul 2007

control, resumed

posted by matthias

Since at least some people helped me re-re-invent prompt after my last post, I thought I would remind people that PLT Scheme is the only production system in the world that provides delimited and (truly) composable continuations directly (and w/o loss of TCO properties). So here is the same fragment again:

(require (lib "control.ss"))

(define (generate-one-element-at-a-time a-list)
  (define (control-state)
    (for-each (lambda (an-element-from-a-list)
  (control resume-here
    (set! control-state resume-here)
    an-element-from-a-list))
              a-list)
    'you-fell-off-the-end-off-the-list)
  (define (generator) (prompt (control-state)))
  generator)

Take a look, compare and contrast with the previous post. Time permitting, I will continue to show you another control poem soon. P.S. See Adding Delimited and Composable Control to a Production Programming Environment for details.

more →

27 Jul 2007

call/cc and self-modifying code

posted by matthias

Today I wrote this short illustration of call/cc and posted it on wikipedia:

;; [LISTOF X] -> ( -> X u 'you-fell-off-the-end-off-the-list)
(define (generate-one-element-at-a-time a-list)
  ;; (-> X u 'you-fell-off-the-end-off-the-list)
  ;; this is the actual generator, producing one item from a-list at a time
  (define (generator)
     (call/cc control-state)) 
  ;; [CONTINUATION X] -> EMPTY
  ;; hand the next item from a-list to "return" (or an end-of-list marker)'
  (define (control-state return)
     (for-each 
        (lambda (an-element-from-a-list)
           (set! return ;; fixed
             (call/cc
               (lambda (resume-here)
                 (set! control-state resume-here)
                 (return an-element-from-a-list)))))
        a-list)
     (return 'you-fell-off-the-end-off-the-list))
  ;; time to return the generator
  generator)

It reminded of all the talk in the 1980s and 1990s that self-modifying code is bad. But look at the elegant assignment to control-state within its body. It’s such a poem, I thought I’d share it with people since nobody else blogs here anywya.

more →

14 Jun 2007

Small is Beautiful, Large is Useful, and Scheme is Both

posted by matthias

They say, Scheme is small and this is good.

Have you heard of X? No? It is the smallest computational basis. It is a single function that can compute everything a Turing machine can compute; a Church lambda calculus; a Post model; a RAM; a what-have-you model of computation. Indeed, X is so simple that two equations suffice to specify it completely [Barendregt, page 166]. Imagine that: a complete language report in two lines; a compiler that fits in a few K instead of Ms; no more arguments about smallness.

Small alone can’t be any good. If you used X alone, your programs would be the size of the universe or something like that. That’s what the theory of computability teaches us [Church and Turing]. Adding LAMBDA and a few primitives to get a pure functional language isn’t good enough either. That’s what the theory of expressiveness shows [Felleisen; Mitchell; Riecke]. And, using an R5RS Scheme to build large systems with many people at a dozen sites isn’t doable either. That’s what the PLT experience determined.

When we set out to construct DrScheme using MzScheme, we also conducted an experiment:

Could we really build a graphical system that manages (shared) resources and that provides excellent error feedback with just plain Scheme?

Could we just add enough libraries to do all this? Or would we have to change the kernel of the language? As much as we tried to keep MzScheme small, it became clear quickly that we needed exceptions, structures, module-like features, a mechanism for concurrency, a way to manage resources such as windows, tcp connections, and so on. The list isn’t infinite but it is much longer than I expected. Our “Revenge of the Son of the LISP machine” paper is a good summary for the state of the art around 1999 [Flatt and Son].

As language designers we stepped back time and again to look at our monster. What could we remove? What would we have to add in response? For some five years, we had first-class modules (units) and first-class classes in the core of the language. We had almost banned macros. They were so ugly I stopped teaching about them because I did want to use our own dog food in my courses but I couldn’t stomach the macro system. It was such a step back from Eugene’s extend-syntax. But then Matthew figured out the next big step in macro and module technology [Flatt, You Want It When?]. And with that out went units and classes from the core and many other things. So we learned lessons, and we need to keep building systems to learn more.

I have no question that the idea of Scheme is beautiful. At the same time, I have also learned that if I wish to use this beautiful idea in practice, I need to add the ingredients that it takes to build large systems. R6RS reflects this insight, and I am happy about it.

more →

09 Jun 2007

R6RS is “perfect”

posted by matthias

When I read the “side by side” and “head to head” descriptions of the alternatives facing the Scheme community (see Comp.Lang.Scheme and the R6RS mailing list), I am wondering which one is which and which one is better.

  • Is it really good that Scheme (the spec) doesn’t support a module system?

  • Is it really good that almost all major implementations support their own version of a module system?

  • Is it really good that programmers can’t even leave the module structure intact when porting code?

Imagine your own similar questions and add them here. We have lived in a side-by-side universe for a long time, and there are quite a few programmers who have suffered from this not-really-the-same-language problem. Besides the module system, there are other not-quite-the-same-but-related features that implementations have and programmers wish to use. The R6RS process has pushed several major implementors/implementations to agree on a design for module systems and other constructs. Their report declares that they are ready to put a large amount of work in to get from r5rs to r6rs. I believe that this step would help the community in several arenas, listed in increasing order of relevance:

  • the academic publishing business

  • the fund raising business

  • adapting each others innovations

  • supporting programmers who learn on one and switch to another implementation

  • supporting commercial programmers who need reassurance that there is more than one implementation and implementor [ever attended Commercial Uses of Functional Programming?]

Is the document perfect? Is every construct exactly the ‘right thing’? Of course not! Guy and Gerry revised their first Scheme report because they didn’t get it ‘right’. R3RS and R4RS and R5RS revised flaws in R(n–1)RS because the authors/editors didn’t get it ‘right’. It is extremely difficult, and usually impossible, to get the design of a complex artifacts (such as a programming language) ‘right’ the first time. In these cases, it’s all about the feedback loop and revising your design based on observations. (Remember the ‘science’ part in the name of our discipline?) Indeed, ‘right’ doesn’t exist; what exists is ‘most pragmatic and internally beautiful,’ and nothing else. Our choice is quite simple: move forward as a community with some amount of convergence (r6rs) or split into dozens of mutually incompatible sub-communities (status quo, including SRFIs). Also posted as “R6RS is perfect” at the R6RS discussion list.

more →

22 May 2007

PLT Scheme version 370

posted by Jens Axel Søgaard

PLT Scheme version 370 is now available from

http://download.plt-scheme.org/

Some highlights:

  • The conservative garbage collector (CGC) has been replaced with a precise garbage collector (3m) in the standard build. For most users, this change simply amounts to “better performance in space and time”. For example, a long-running DrScheme instance typically uses much less memory than before.

The new memory manager also supports a new “Limit Memory…” option (in DrScheme’s “Scheme” menu) to limit the memory use of a programming running inside DrScheme.

For those who work with C-implemented libraries and extensions, the switch to precise collection may complicate interoperability. To a large extent, however, (lib “foreign.ss”) works the same with both collectors. (But note that the 3m is a moving collector, so be careful with passing Scheme objects to C.)

Although our pre-built binaries use the new collector, builds from source using the conservative collector are still supported.

  • For a program written with one of the the “How to Design Programs” (HtDP) languages, DrScheme saves the program with meta-information that identifies the language and records the teachpacks used by the program. DrScheme’s teachpack GUI now works only with the HtDP languages. In other languages, use require to access teachpacks.

The meta-information is in the form of a reader extension that turns the file content into a module-based program, which means that teaching-language files can be loaded directly into MzScheme or used with other PLT Scheme tools.

  • The HtDP “world.ss” and “image.ss” teachpacks have been revised, including support for the creation of animated GIFs.

  • Unit-based servlets are no longer supported in the web server. Use module-based servlets, instead. (Servlets can be implemented using a unit within a module, but the web server’s API is provided through a module.)

  • A new (lib “unit.ss”) library replaces the old one and provides a simpler and more flexible syntax. The (lib “unitsig.ss”) library is deprecated but still available as (lib “unitsig200.ss”), and the old (lib “unit.ss”) is available as (lib “unit200.ss”). Feedback Welcome, The PLT Scheme Team

more →

16 May 2007

Looking for small Scheme scripts

posted by Sam Tobin-Hochstadt

As part of the Typed Scheme project, we are looking for small Scheme scripts that we can port from PLT Scheme to Typed Scheme. We would like to investigate if Typed Scheme is capable of checking idiomatic PLT Scheme code, as represented by scripts written by members of the PLT Scheme community.

Therefore, if you have a simple PLT Scheme program which handles a scripting/processing task, and you are willing to share it with us for the improvement of Typed Scheme, please let me know. Typed Scheme currently handles all of ‘core’ MzScheme, as well as many of the collections (the major exceptions are the class and unit systems).

In return, we will inform you of any bugs that we discover during the port.

More information about Typed Scheme is available from the webpage: http://www.ccs.neu.edu/~samth/typed-scheme.html

more →

Made with Frog, a static-blog generator written in Racket.
Source code for this blog.