19 Mar 2011

Languages as Libraries, PLDI 2011

posted by Sam Tobin-Hochstadt

We’ve just finished up the final version of our PLDI 2011 paper on language extension in Racket. The paper describes how the module system and the syntax system work together to support new languages with new static semantics, such as Typed Racket. Here’s the abstract:

Programming language design benefits from constructs for extending the syntax and semantics of a host language. While C’s string-based macros empower programmers to introduce notational shorthands, the parser-level macros of Lisp encourage experimentation with domain-specific languages. The Scheme programming language improves on Lisp with macros that respect lexical scope.

The design of Racket—a descendant of Scheme—goes even further with the introduction of a full-fledged interface to the static semantics of the language. A Racket extension programmer can thus add constructs that are indistinguishable from “native” notation, large and complex embedded domain-specific languages, and even optimizing transformations for the compiler backend. This power to experiment with language design has been used to create a series of sub-languages for programming with first-class classes and modules, numerous languages for implementing the Racket system, and the creation of a complete and fully integrated typed sister language to Racket’s untyped base language.

This paper explains Racket’s language extension API via an implementation of a small typed sister language. The new language provides a rich type system that accommodates the idioms of untyped Racket. Furthermore, modules in this typed language can safely exchange values with untyped modules. Last but not least, the implementation includes a type-based optimizer that achieves promising speedups. Although these extensions are complex, their Racket implementation is just a library, like any other library, requiring no changes to the Racket implementation.

To learn how to implement your own new language in Racket, start with this documentation.

more →

14 Feb 2011

Racket v5.1

posted by Eli Barzilay

Racket version 5.1 is now available from http://racket-lang.org/The most significant change in version 5.1 is a rewrite of the GUI library. Unix/X users will see the biggest difference with this change, because DrRacket and all Racket GUI programs now take on the desktop theme for menus, buttons, and other GUI widgets.

In the long run, Racket GUI programs on all platforms will improve as a result of the library rewrite. In the short run, beware that this first release of a new library will inevitably include a new set of bugs.

Version 5.1 changes in more detail:

  • The racket/draw library—which implements the drawing half the GUI toolkit—can be used independent of the racket/gui/base library and without a graphics display (e.g., without an X11 connection).The new library has one small incompatibility with the old GUI toolbox: ’xor drawing is no longer supported. The new library has many additional features: rotation and general affine transformations, PDF and SVG drawing contexts, gradients, and alpha-channel bitmaps.

  • The GRacket executable is no longer strictly necessary for running GUI programs, because the racket/gui/base library can be used from Racket. To the degree that a platform distinguishes GUI and console applications, however, the GRacket executable still offers some additional GUI-specific functionality (e.g., single-instance support).The new racket/gui/base library includes small incompatibilities with the old GUI toolbox: the send-event, current-ps-afm-file-paths, and current-ps-cmap-file-paths functions have been removed. The racket/gui/base library re-exports racket/draw, so it includes the same drawing functionality as before (except for ’xor drawing).

  • The new racket/snip library can be used independently of racket/gui/base to work with graphical editor content (e.g., images in student programs). Like racket/draw, the racket/snip library is re-exported by racket/gui/base.

  • The Web Server includes a backwards incompatible change that prevents X-expressions and lists of bytes from being directly returned from servlets. This change will increase performance for those types of responses and allow easier experimentation with response types. Please see "collects/web-server/compat/0/README" in the installation to learn about porting your servlets forward. Don’t worry. It’s easy.

  • The new raco demodularize tool collapses a module’s dependencies into a single module comprising the whole program. This transformation currently provides no performance improvement, but is the basis for cross-module optimization and dead-code elimination tools to come. The transformation is currently useful for static analysis of whole Racket programs.

  • The picturing-programs teachpack, formerly installed via PLaneT, is now bundled with the standard distribution. Use the teachpack with (require picturing-programs) instead of (require installed-teachpacks/picturing-programs). The old PLaneT-based installation procedure still works, but it now merely installs a stub that invokes the bundled version.

  • Slideshow picts, racket/draw bitmaps, and images created with 2htdp/image can now be used directly in Scribble documents. More generally, the new file/convertible protocol enables any value that is convertible to a PNG and/or PDF stream to be used as an image in a Scribble document.

  • The Same game sports a new look and an improved scoring system. (The current known high score is 12,429; can you beat that?)

more →

08 Dec 2010

Rebuilding Racket’s Graphics Layer

posted by Matthew Flatt

Racket version 5.1, which is scheduled for release in early February, will look a little different on the outside. Unix/X users will see the biggest difference: DrRacket and all Racket GUI programs will take on the desktop theme for menus, buttons, and other GUI widgets. Text handling is also better than before on Unix/X, especially when printing. Windows and Mac OS X users will see smaller changes, such as better printing, better handling of mouse-wheel events, and support for 64-bit Windows and Mac OS X.

On the inside, version 5.1 is the biggest single change in Racket (or PLT Scheme) history. We’ve reimplemented the GUI layer, which meant throwing out about 200,000 lines of C++ code that built on Xt, Win32, and Carbon. We’ve replaced that C++ code with about 30,000 lines of Racket code that builds on Gtk, Win32, Cocoa, Cairo, and Pango. This change modernizes Racket’s graphics support while significantly reducing the cost of maintaining the GUI and drawing libraries.

In the space between the GUI implementation and the surface, there are many API improvements:

  • You can run GUI programs with just racket, instead of having to use gracket. Depending on how much your platform distinguishes between GUI and console applications, there may still be an advantage to using gracket (i.e., to tell the OS that you mean to start a GUI application or that you want a single instance of the application), but the difference is minor.

  • Most of the drawing library has moved to racket/draw, which you can use without the rest of the GUI library – and, in the case of Unix platforms, without an X-server connection. After detangling the graphics and GUIs libraries, the graphics library is now integrated in more places, such as adding pict support for Scribble documents.

  • The drawing library includes some new capabilities, such as rotation, affine transformations, and bitmaps with alpha channels.

Replacing hundreds of thousands of lines of C++ code with tens of thousands of lines of Racket code sounds like a no-brainer. The old library was implemented in C++ because we started in 1995 by gluing together a Scheme interpreter with a portable GUI library. Then the GUI code stayed in C++, because the interpreter wasn’t fast enough and the foreign interface was too clumsy. Racket is now plenty fast and its foreign interface has improved a lot since then.

Still, the reimplementation took about 18 months. Smoothly integrating cross-platform GUI support with a programming language can be more difficult than it sounds, and mating new libraries with a legacy API creates additional challenges. Finally, many Racket tools depend Racket’s “eventspaces,” which are multiple process-like entities in the same virtual machine, each with its own GUI event loop. Implementing eventspaces on top of modern GUI toolkits turns out to be tricky, because the toolkits insist on a single event-loop per process and they cannot tolerate event-loop actions during certain callbacks. Fortunately, delimited continuations can help work around those limitations.

Cairo and Pango are the two big enablers of the Racket graphics rewrite. The old Racket graphics library depended on many toolkits (X11, Win32, QuickDraw, Quartz, PostScript, and more), and it had poor font handling. Again, the problem was that we chose the previous technology in 1995. Cairo and Pango have since solved the portable-graphics problem, and we were able to trade in 80,000 lines of C++ glue for about 8,000 lines of Racket glue. The code could be much less if we didn’t have to match most of the old drawing API, but we’re still very happy with the result.

On the GUI side, the remaining 22,000 lines of Racket code replace similar C++ code that binds to three different toolkits. The set of underlying toolkits has changed, and a few eventspace tricks are new, but the approach is essentially the same as before. The code is nevertheless much more compact, because (no surprise) Racket is better than C++. Interestingly, the amount of toolkit-specific code is right around 6,500 lines for each toolkit, even though the way that a C programmer uses the different toolkits seems very different: Objective-C classes (Cocoa) versus signal callbacks with explicit wiring (Gtk) versus a single callback function for message handling (Win32). Maybe they’re the same because we built a Racket mini-language for each toolkit that makes them all about equally convenient.

The rewrite is not perfectly compatible with old code, and no doubt we have many bugs to find before the release. The process is well on track, though, and the new library implementations give a us a solid foundation to keep making Racket better.

To try out the current development version, visit

http://pre.racket-lang.org/installers

more →

07 Nov 2010

Racket v5.0.2

posted by Eli Barzilay

Racket version 5.0.2 is now available from http://racket-lang.org/

  • Typed Racket’s optimizer is now turned on by default; error messages have been simplified and clarified.

  • Contracts: contracts on mutable containers allow functions or other higher order values, and contracts are checked when updating or dereferencing the containers. The new contracts are slower than the old ones, so the old check-once functionality is still available.A new dependent function contract combinator, ->i, properly assigns blame for contracts that violate themselves and the generated wrappers are more efficient than ->d. (Although it does more checking so your contracts may be faster or slower).See the docs for box/c, hash/c, vector/c, vectorof and ->i for more details.

  • The when, unless, cond, case, and match forms (in racket/base and derived languages) now allow immediate internal definitions.

  • Web server: the formlets library provides more HTML form elements; make-xexpr-response supports a preamble for DTD declarations; serve/servlet supports stateless servlets.

  • New WebSocket implementation, see net/websocket for details.

  • The new data collection contains implementations of several data structures, including growable vectors and order-based dictionaries.

  • racket/match is now significantly faster.

  • The Racket documentations are built in parallel by default.

  • The stepper is now compatible with programs using the Universe teachpack.

  • 2htdp/image: pinholes are now supported in the library (if you don’t use pinhole primitives you will not see them); a number of new triangle functions added; supports conversion of images to color lists and back. Also, cropping has been improved for scenes; see the documentation section on the nitty-gritty of pixels for details.

  • Signatures have been moved to ASL, BSL, BSL+, ISL, and ISL+ (HtDP teaching languages) no longer support checked signatures.

  • Student languages: one-armed check-error in all levels; ASL is extended with hash operations, and define-datatype.

  • DMdA languages: Checking for parametric signatures is now eager. This catches errors earlier, but retains the asymptotic complexity properties; signatures for record types now have generators; list-of and any signatures are now provided.

more →

03 Oct 2010

The Two-State Solution: Native and Serializable Continuations Accord

posted by Jay McCarthy

The Racket Web Server allows an expressive way of writing Web applications using first-class continuations to capture the control-flow of the server while it is waiting for the client to respond. For example:

#lang web-server/insta
(define (get-number p)
  (string->number
   (extract-binding/single
    'num
    (request-bindings
     (send/suspend
      (λ (k-url)
        `(html 
          (body
           (form ([action ,k-url])
                 ,p nbsp (input ([name "num"]))
                 (input ([type "submit"])))))))))))
(define (start req)
  (define how-many
    (get-number "How many numbers to add?"))
  (number->string
   (foldr 
    + 0
    (build-list 
     how-many
     (λ (i)
       (get-number 
        (format "Provide number: ~a" 
                (add1 i))))))))

This application creates a re-usable get-number interaction abstraction and uses it in a number of different contexts. In particular, it uses it in the higher-order context of build-list. This application also reuses useful third-party library functions like foldr, etc.

Such an application would be complicated to write in a traditional Web programming environment because the continuation of each get-number invocation is considerably more complex than is typical. Yet, the first-class continuations in Racket ensure that this continuation is captured exactly, correctly, every time.

Unfortunately, the native first-class continuations of Racket are not serializable, so they impose a per-session resource expenditure on the server. This can be alleviated through expiration policies, but such policies are inherently unsound because continuations URLs are global roots.

In the past, PLT has provided tools that automatically restructure this kind of program into one that uses serializable continuations through an acronym soup of source transformations: CPS, lambda-lifting, defunctionalization, SPS, and so on. These tools effectively create automatically what most Web programmers write manually, except the tools don’t mistakes. But the tools also don’t take into consideration what functions actually contribute to the interaction context and transform library functions like foldr (which is unnecessary in the continuation) the same as functions like build-list (which are necessary.)

Our past work (based on another PLT paper) alleviates this problem by only requiring functions like build-list to be transformed. From the perspective of a programmer, “transformed” is tantamount to “rewritten” because the source code for a third-party library may not be readily available. Programmers would have to program add-many-numbers.com as:

#lang web-server
(require web-server/servlet-env)
(define (get-number p)
  (string->number
   (extract-binding/single
    'num
    (request-bindings
     (send/suspend
      (λ (k-url)
        `(html 
          (body
           (form ([action ,k-url])
                 ,p nbsp (input ([name "num"]))
                 (input ([type "submit"])))))))))))
(define (build-list n f)
  (for/list ([i (in-range n)])
    (f i)))
(define (start req)
  (define how-many
    (get-number "How many numbers to add?"))
  (number->string
   (foldr 
    + 0
    (build-list
     how-many
     (λ (i)
       (get-number 
        (format "Provide number: ~a"
                (add1 i))))))))
; This requires a pre-release version
; to run in an un-named DrRacket buffer
(serve/servlet start #:stateless? #t)

where build-list has been re-implemented, but functions like foldr have not. This application, despite its striking similarity to the first, requires absolutely no per-session server state, so it is considerably more scalable.

Do we need to re-implement build-list? What if the third-party, higher-order function (build-list) that we use with a higher-order argument that causes Web interaction (get-number) is too complicated to re-implement?

Naturally this blog post would not exist if we didn’t solve this problem.

Our new approach, dubbed The Two-State Solution, allows the programmer to transparently use a very small amount of per-session server state to store just the part of the continuation inside functions like build-list while serializing everything else to the client.

The key is to use delimited, composable continuations to isolate the appropriate part of the continuation. The programmer designates this piece of the continuation through the serial->native and native->serial annotations. The programmer can write the application as:

#lang web-server
(require web-server/servlet-env)
(define (get-number p)
  (string->number
   (extract-binding/single
    'num
    (request-bindings
     (send/suspend
      (λ (k-url)
        `(html 
          (body
           (form ([action ,k-url])
                 ,p nbsp (input ([name "num"]))
                 (input ([type "submit"])))))))))))
(define (start req)
  (define how-many
    (get-number "How many numbers to add?"))
  (number->string
   (foldr 
    + 0
    (serial->native
     (build-list
      how-many
      (λ (i)
        (native->serial
         (get-number 
          (format "Provide number: ~a"
                  (add1 i))))))))))
; This requires a pre-release version
; to run in an un-named DrRacket buffer
(serve/servlet start #:stateless? #t)

The important distinction here is that both the build-list and the get-number abstractions do not need to change. We simply mark the context as being a “serial” or “native” context through the annotation forms. This re-written version will be more scalable than a purely native version, but represents an easier to achieve step in the evolution of a program, because third-party, higher-order functions can be used as is.

This work will be presented at OOPSLA 2010. It is also described in a paper with same name this blog post:The Two-State Solution: Native and Serializable Continuations Accord.

more →

15 Sep 2010

Extending Typed Racket, Part 1

posted by Sam Tobin-Hochstadt

The Typed Racket team is pleased to announce a number of new additions to our system. We’ll be writing a few blog posts about them, all of which you can read here.

This post begins with the core of the Typed Racket type system. The fundamental idea at the heart of Typed Racket is called occurrence typing. This is the technique that allows us to typecheck existing Racket programs without requiring rewrites. Here’s a simple example:

(if (number? x) (add1 x) 0)

The typechecker can figure out from the use of number? that the second occurrence of x is always going to be a number. This simple form of occurrence typing is enough to take Typed Racket a long way. But because we want to be able to handle all the sophisticated reasoning that programmers are already using to write their Racket programs, we have been working on extending the system further.

The new design of our system is described in a paper, Logical Types for Untyped Languages, in the upcoming International Conference on Functional Programming. The introduction provides an overview that’s acessible to any Racket programmer, but here’s the key example:

(cond
  [(and (number? x) (string? y))  1 ]
  [(number? x)                    2 ]
  [else                           3 ])

In expression 1, we know that x is a number and y is a string. In 2, we know that x is a number and y is not a string, by the logical properties of and and cond. This form of logical reasoning is enabled by the new foundation of the system, and makes the entire system significantly more expressive.

All of these improvements are available in the current version of Racket.

more →

03 Aug 2010

Racket v5.0.1

posted by Eli Barzilay

Racket version 5.0.1 is now available from http://racket-lang.org/

  • Datalog is a lightweight deductive database system with Racket integration. It is now available in the datalog collection and with #lang datalog.

  • Racklog provides Prolog-style logic programming in Racket, adapted from Dorai Sitaram’s Schelog package. It is available in the racklog collection and now as #lang racklog.

  • By default make install and raco setup compile collections in parallel on all available processors. (Use raco setup -j 1 to disable, if necessary.)

  • Changes (as part of 5.0) in the racket language compared to the scheme language: constructor-style printing, a struct alternative to define-struct that fits more naturally with match and constructor-style printing, bytecode-dependency management via SHA–1 hashes instead of just timestamps (where the openssl/sha1 library provides the SHA–1 hash function), a reorganization of scheme/foreign into ffi/unsafe and associated libraries, and new printing functions eprintf and displayln. Also, a generator from racket/generator is required to have the form (generator () body ...), which supports a planned extension to let a generator accept arguments.

  • Changes to the racket language (since 5.0): internal-definition positions allow mixing expressions with definitions, full continuations can escape past a continuation barrier, custodians can attempt to terminate subprocesses and subprocess groups (see current-subprocess-custodian-mode, subprocess-group-enabled), the JIT supports additional unboxing flonum operations and unsafe variants, ffi/unsafe provides an asychronous-call mechanism to deal with foreign threads, a new "." modifier for format string directives (e.g., "~.s" and "~.a") limits the respective output to (error-print-width) characters.

  • The core type system of Typed Racket has been substantially revised. In particular, Typed Racket can now follow significantly more sophisticated reasoning about the relationships between predicates. Additionally, Typed Racket now allows variable arity types in more places, allowing programmers to specify variable-arity lists.

  • We are working on an optimizing version of Typed Racket that takes advantage of type information for certain classes of programs. This project is a work in progress. For those interested, see the documentation for #:optimized.

  • The web-server/formlets library adds a formlet* form that allows dynamic formlet construction, as opposed to formlet which requires syntactic Xexprs and static formlets. Several new library formlets are added.

  • The syntax/parse library has new support for matching literals at different phases using the #:phase argument for literals and literal sets.

  • RackUnit now includes a GUI test runner as rackunit/gui.

  • The 2htdp/image library now includes flip-vertical and flip-horizontal operations that mirror images (vertically and horizontally).

more →

07 Jun 2010

Racket

posted by Eli Barzilay

PLT is happy to announce the release of Racket, available from http://racket-lang.org/

With Racket, you can script command shells and web servers; you can quickly prototype animations and complex GUIs; regexps and threads are here to serve you. To organize your systems, you can mix and match classes, modules or components. Best of all, you start without writing down types. If you later wish to turn your script into a program, equip your Racket modules with explicit type declarations as you wish. And Racket doesn’t just come as a typed variant; you can also write your modules in a purely functional and lazy dialect.

Racket comes in so many flavors because Racket is much more than a standard scripting language or a plain programming language. Racket supports language extensibility to an unequaled degree. A Racket programmer knows that making up a new language is as easy as writing a new library.

To help you start quickly, Racket includes batteries in all shapes and sizes, most importantly, extensive documentation and all kinds of libraries.

Racket occupies a unique position between research and practice. It inherits many major ideas from language research, among them type safety (when the type system says that x is a number, then at runtime it always is a number) and memory safety (when some memory is reclaimed by the garbage collector it is impossible to still have a reference to it). At the same time, user demand governs rigid adherence to purely theoretical principles.

Racket, formerly PLT Scheme, is a product of over 15 years of development. Although Racket starts with a mature software base and an established user community, its new name reflects our view that this is just the beginning of Racket’s evolution.

more →

02 Apr 2010

PLT Scheme v4.2.5

posted by Eli Barzilay

PLT Scheme version 4.2.5 is now available from http://plt-scheme.org/

  • PLT now supports multi-core parallelism via futures. Futures create tasks that run in parallel, as long as the tasks stay in the “fast path” of the runtime system. For more information, see the guide.
  • Our unit testing framework, schemeunit, is now included in the distribution. A graphical test runner is available via schemeunit/gui.
  • The support languages for the “Programming Languages: Application and Interpretation” textbook by Shriram Krishnamurthi are now part of PLT Scheme. In addition the PLAI GC language comes with a random mutator generator (to help test collectors) and an improved heap visualizer.
  • New Russian and Ukranian translations, thanks to Sergey Semerikov.
  • A number of improvements to Redex’s typesetting facilities.
  • Typed Scheme users can now automatically generate predicates from types with define-predicate. Typed code can be inserted in untyped modules by requiring with-type from typed/scheme.
  • The scheme/class library now provides contract combinators for classes (class/c) and objects (object/c). See the Reference and Guide for details. Also, a backwards-compatible object-contract version of object/c has replaced the old object-contract combinator.
  • Writing new kinds of contracts is now easier with keyword-based constructors (make-contract and make-flat-contract), a simpler set of structure properties (prop:contract and prop:flat-contract), and the introduction of blame objects for tracking contract metadata.
  • The Scheme-implemented bytecode reader fails less often. This is used by “mzc —decompile”. The Scheme-implemented bytecode writer uses the compact bytecode format and fails less often. This may be used in the future for Scheme-implement bytecode processors.
  • The language dialog now suggests using "#lang" more strongly as the default language. DrScheme no longer uses the term `Module language’.
more →

08 Mar 2010

Talk at Flourish

posted by Robby Findler

The image in this post shows a tree where the interior nodes represent directories and the leaf nodes represent files in the PLT source code. The leaves are colored based on the programming language used. (To avoid clutter, if there is more than one file in a given directory written in a particular language, that language only gets a single dot.)

Some highlights: the blues are Scheme-like languages, the reds are langauges we use to write documentation (see Scribble for more about them), the greens are teaching languages, orange is the language we use to bootstrap new languages, and yellow is a language for metadata about nearby files.

Curious about how we managed to write and use so many different languages? I’ll be giving a talk at Flourish 2010 next week (3/19 @11am, UIC in Chicago) explaining how. Come to learn more!

more →

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