The MrEd virtual machine serves both as the implementation platform for the DrScheme programming environment, and as the underlying Scheme engine for executing expressions and programs entered into DrScheme's read-eval-print loop. We describe the key elements of the MrEd virtual machine for building a programming environment, and we step through the implementation of a miniature version of DrScheme in MrEd. More generally, we show how MrEd defines a high-level operating system for graphical programs. with a graphical user interface (GUI) t oo lb ox. MrEd serves both as the implementation platform for DrScheme, and as the underlying Scheme engine for executing expressions and programs entered into DrScheme's read-eval-print loop (REPL). This strategy follows a long tradition of meta-circular implementation that is virtually synonymous with Lisp, and generally understood for high-level languages as a whole [20, 25, 281. Since DrScheme exposes MrEd's language constructs directly to the REPL, DrScheme can easily execute programs that use the full MrEd language, including its GTJI toolbox. At the same time, DrScheme must protect its GUI against interference from the programs it executes, and it must be able to halt a program that has gone awry and *This research was partially supported by a Lodieska Stockbridge Vaughan Fellowship, NSF grants CCR-9619756, CDA-9713032, and CCR-9708957, and a Texas ATP grant. to make diaital or hard copies of all or part of this work for personal or classroo&se is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. ICFP '99 9/99 Paris, France 0 1999 ACM l-581 13-l 1 l-9/99/0009...$5.00 reclaim the program's resources-even though the program and DrScheme share a single virtual machine. To address this problem, MrEd provides a small set of new language constructs. These constructs allow a programrunning program, such as DrScheme, to run nested programs directly on the MrEd virtual machine without sacrificing control over the nested programs. As a result, DrScheme can execute a copy of DrScheme that is ex.ecuting its own copy of DrScheme (see Figure 1 ). The inner and middle DrSchemes cannot interfere with the operation of the outer DrScheme, and the middle DrScheme cannot interfere with the outer DrScheme's control over the inner DrScheme. In this paper, we describe the key elements of the MrEd virtual machine, and we step through the implementation of a miniature version of DrScheme in MrEd. More generally, we show how MrEd defines a high.-level operating system (OS) for graphical programs. As in other high-level OSes, safety and security in :MrEd derive from properties of the underlying programming language. Mere safety, however, provides neither the level of protection between applications nor the kind of process control that conventional OSes provide. Such protection and control is crucial for implementing many kinds of programs, including programming environments and scripting engines. By describing how we implemented DrScheme in MrEd, we demonstrate how to obtain key OS facilities through small extensions to a highlevel programming language. The remainder of the paper is organized as follows. Section 2 sketches a miniature DrScheme, called SchemeEsq, and explains in more detail the implementation challenges for creating a graphical programming environment. Section 3 provides a brief overview of MrEd. Section 4 steps through the implementation of SchemeEsq as a MrEd program. Section 5 explains how MrEd functions as a high-level OS. Section 6 discusses some problems for future work, and Section 7 compares MrEd to related systems. MrEd's make-object procedure takes a class and returns an instance of the class. Extra arguments to make-object serve as initialization arguments for the object, similar to arguments provided with new in Java. For the frame% class, the initialization arguments specify the frame's title, its parent window (#f if none), and its initial size. The above frame is titled Example, has no parent, and is 400 pixels wide and 200 pixels tall. The built-in classes provide various mechanisms for handling GUI events, which MrEd dispatches automatically. For example, when instantiating the button% class, the programmer supplies an event callback procedure to be invoked when the user clicks the button. The following example creates a Close button that hides the frame when the user clicks the button: For simple controls, such as buttons, the control's action is normalty instance-specific, so the action is best specified as a callback in the make-object vases, event-handling is often common to a class of instances, so method overriding provides a more extensible mechanism 'By convention, class names end with a percent sign (%) in MrEd. The source code in this paper runs in MrEd version 100. MrEd's GUI classes also handle the graphical layout of windows. Our example frame demonstrates a simple layout; the frame's elements are lined up top-to-bottom. In general, a programmer specifies the l,ayout of a window by assigning each GUI element to a parent container. A vertical container, such as a frame, arranges its children in a column, and a horizontal container arranges its children in a row. A container can be a child of another container; for example, to place two buttons side-by-side in a frame, a programmer creates a horizontal panel for the buttons: (define panel (make-object horizontal-pane% frame)) (make-object button% "Left" panel . ..) (make-object button% "Right" punel . ..) A programmer can adjust the minimum width, minimum height, horizontal stretchability, and vertical stretchability of each GUI element. Using these settings, MrEd picks an initial size for each frame, and it repositions controls when the user resizes a frame. Containers, Experience and Rationale: boxes provide a variety of mechanisms for geometry managecontainers with arbitrary layout strategies, we implemented DrScheme using only vertical and horizontal containers. In addition to the basic GUI building blocks, MrEd provides a collection of classes that support a broad spectrum of editor programs, from word processors to drawing programs. The editor framework addresses a wide range of real-world issues for an editor-including cut-and-paste, extensible file formats, and layered text styles-while supporting a high level of extensibility through the class system. and Rationale: MrEd's editor toolbox provides a foundation for two common kinds of applications: 1. programs that include a sophisticated text editor: MrEd's simple text field control is inadequate for textintensive applications. Many programs need editors that can handle multiple fonts and non-text items. MrEd's drawing toolbox provides a generic drawing SWface for plotting lines and boxes, but many applications need an interactive canvas, where the use? can drag and resize individual objects. The power and flexibility of the editor toolbox make it fairly complex, and using the toolbox requires a solid understanding of its structure and terminology. Nevertheless, enough applications fit one (or both) of the descriptions above to justify the depth and complexity of the toolbox and the learning investment required to use it. Conventional operating systems support multiple programs through a process abstraction that gives each program its own control flow, I/O environment, and resource controls. A process is distinguished primarily by its address space, where separate address spaces serve both as a protection barrier between programs and as a mechanism for defining a program's environment; e.g., the stdout global variable in a Unix C program contains a process-specific value. In MrEd, separate address spaces are unnecessary for protection between programs, due to the safety properties of the programming language. Nevertheless, separate programs require separate control flow, I/O environments, and resource controls. Instead of providing an all-encompassing process abstraction, MrEd provides specific mechanisms for creating threads of control, dealing with graphical I/O, and managing resources. MrEd's thread primitive consumes a procedure of no arguments and invokes it in a new thread. The following example spawns a thread that prints "tick" every second: Each thread maintains its own collection of system settings, such as the current directory and the current output port. These settings are called parameters.3 A parameter is queried and modified via a parameter procedure, such as current-directory or current-output-port. For example, (current-directory) returns the path of the current directory, while (current-directory dir) sets the current directory to dir. Modifying a parameter changes its value in the current thread only. Therefore, by setting the current-output-port in the tack-loop thread, we can redirect the "tick" printouts without modifying tick-loop and without affecting the output of any other thread: (tick-loop))) A newIy-created thread inherits the parameter values of the creating thread. Thus, if tick-loop creates its own threads, they also produce output to the "ticks" file. Parameter inheritance provides an alternative mechanism for setting the output port in the "ticking" thread. Instead of explicitly setting the port within the ticking thread, we could temporarily set the port in the main thread while creating the ticking thread: (parameterize ((current-output-port (open-output-file "ticks"))) (thread tick-loop)) A parameterize expression sets the value of a parameter during the dynamic extent of its body. In the above example, parameterize restores the output port for the main thread after the ticking thread is created, but the ticking thread inherits "ticks" as its current output port. Since the output port is set before tick-loop is called, the ticking thread has no way to access the original output port. In this way, parameters permit securely configuring the environment of a nested program (or any untrusted thread).  An eventspace in MrEd is a context for processing GUI events in a sequential manner. Each eventspace maintains its own queue of events, its own collection of frames, and its own handler thread. MrEd dispatches events within an eventspace synchronously in the handler thread, while dispatching events from different eventspaces asynchronously in separate handler threads. Creating an eventspace starts a handler thread for the eventspace implicitly. Only the handler thread dispatches events, but all threads that share an eventspace can queue events, and all threads (regardless of eventspace) can manipulate an accessible GUI object.4 When a thread creates a top-level window, it assigns the window to the current eventspace as determined by the current-eventspace parameter. Equipped with the MrEd constructs defined in the previous section, we can implement the SchemeEsq program described in Section 2. First, we create the SchemeEsq GUI using the MrEd toolbox. Then, we use threads, eventspaces, and custodians to implement secure evaluation for REPL expressions. Finally, we discuss how units and mixins let us extend SchemeEsq to implement the full DrScheme environment . When a user hits the Enter key, SchemeEsq evaluates the expression following the current prompt. SchemeEsq ultimately evaluates this expression by calling the built-in eval procedure. But before letting SchemeEsq call eval, we must ensure that code evaluated in the REPL cannot interfere with SchemeEsq itself, since both SchemeEsq and the user's code execute together in MrEd. To implement the SchemeEsq GUI, we first create a frame: (define frame (make-object frame% "SchemeEsq" #f 400 200)) and make it visible: Of course, user code must not gain direct access to the frame or editor of SchemeEsq, since it might call methods of the objects inappropriately. We can hide SchemeEsq's implementation from the user's program by putting it into a module and making all definitions private. For now, we continue to define SchemeEsq through top-level definitions, but the appendix shows the final SchemeEsq program encapsulated in a module. (send frame show #t) Next, we create the reset button to appear at the top of the frame: The remaining problems concern the interaction of control flow in the user's program and in SchemeEsq. Threads with parameters, eventspaces, and custodians provide precisely the mechanisms needed to solve these problems. (define reset-button 4.2.1 Threads in SchemeEsq (make-object button% "Reset" frame (lambda (b e) (reset-program)))) The callback procedure for the reset button ignores its arguments and calls reset-program, which we define later. Finally, we create a display area for the REPL, implemented as an editor canvas: (define repl-display-canvas An unbounded computation in the user's program must not stall SchemeEsq's GUI. Otherwise, the program would prevent the user from clicking SchemeEsq's reset button. To avoid blocking SchemeEsq on a REPL computation, we evaluate user expressions in a separate thread. The following is a first attempt at defining the evaluate procedure for evaluating user expressions? (make-object editor-canvas% frame)) At this point, our SchemeEsq GUl already resembles Figure 2, but the REPL is not yet active. The actual REPL is implemented as a text editor that is displayed by the canvas.7 The basic functionality needed in SchemeEsq's REPLincluding keyboard event handling, scrolling, and cut and paste operations-resides in MrEd's text% editor class. The esq-text% class, defined in the appendix, adapts the text% class to the needs of the REPL by overriding methods to specialize the editor's behavior. For example, when the editor receives an Enter/Return key press, it calls the evaluate procedure (which we define later). In addition to handling input, the esq-text% class defines an o&put method for printing output from the user's program into the REPL editor. Since the user's program can create many threads, the output method needs a special wrapper to convert multi-threaded output calls into singlethreaded output. The queue-output wrapper performs this conversion by changing a method call into a queued, lowpriority GUI event: (define (evaluate ezpr-str) (thread (lambda () (with-handlers ((exn? (lambda (ezn) (display (exn-message ezn))))) (write (eval (read (open-input-string ezpr-str))))) (newline) (send repl-editor new-prompt)))) Having created a thread to represent the user process, we must configure the process's environment. For simplicity, we define configuration as redirecting output from the user's program (via display or write} to the REPL editor. To redirect output for the user's program, we set the output port in the evaluation thread: (define (queue-output proc) (parameterize ((current-even&pace esq-eventspace)) (queue-callback proc #f))) (current-output-port user-output-port) ; 1 t added 1 (with-handlers Using the new esq-text% class, we create an editor instance and install it into the display canvas: (define repl-editor (make-object esq-text%)) (send rep/-display-canvas set-editor repl-editor) The SchemeEsq GUI is now complete, but we have not yet implemented evaluate (used in esg-text%) and reset-program (used by reset-button's callback). 7MrEd distinguishes between a display and its editor in the same way that Emacs distinguishes between a window and its buffer. (display (exn-message ezn))))) (write (eval (read (open-input-string ezpr-str))))) (newline) (send repl-editor new-prompt)))) The above assumes that user-output-portport acts as a pipe to the REPL editor. We can define user-output-port using 143 make-output-port, a MrEd procedure that creates a port from arbitrary string-printing and port-closing procedures: (define user-output-port In this use of make-output-port, the string-printing procedure sends the string to the REPL editor, and the port-closing procedure does nothing. (current-output-port user-output-port) (with-handlers ((exn? (lambda (em) (display (exn-message ezn))))) (write (eval (read (open-input-string ezpr-str))))) (newline) (send repl-editor new-prompt))))) We complete SchemeEsq by implementing the reset button's action with a custodian. We define user-custodian and create the user's eventspace under the management of usercustodian: (define user-custodian (make-custodian)) (define user-eventspace (parameterize (( current-custodian user-custodian)) (make-eventspace))) To implement the reset-programprocedure for the reset button, we issue a shut-down command on us'w-custodian anal then reset the REPL editor: (define (reset-program) (custodian-shutdown-all user-custodian) (parameterize ((current-custodian user-custodian)) (set! user-eventspaclf! (make-eventspace))) (send repl-editor reset)) Each reset destroys user-eve&space (by issuing a shut-down. command to user-custodian), making the eventspace unusable. Therefore, reset-program creates a new eventspace after each reset. Modularity and Extensibility in ScherneEsq The appendix assembles the pieces that we have developed into a complete implementation of SchemeEsq. The most, striking aspect of SchemeEsq's implementation-besides the fact that it fits on one page--is that half of the code exists to drive the REPL editor. In the real DrScheme environment, the REPL is considerably more complex, and its implementation occupies a correspondingly large portion of DrScheme's overall code. In implementing DrScheme, we tamed the complexity of the GUI by making extensive use of units and mixins. For example, the parenthesis-highlighting extension for an editor is implemented as a mixin in its own unit, and the interactive search interface is another mixin in a separate unit. Using units and mixins in this way, the implementation strategy that we have demonstrated for SchemeEsq scales to the more elaborate implementation of DrScheme. DrScheme also exploits units for embedd.ing program-like components. For example, DrScheme's help system runs either as a stand-alone application or embedded within the DrScheme programming environment. The help-system unit imports a class that defines a basic frame for the help window. In stand-alone mode, the class implements a frame with a generic menu bar, but when the help system is embedded in DrScheme, the imported class implements a menu bar with DrScheme-specific :menus. The development of SchemeEsq in MrEd demonstrates how a few carefully defined extensions can transform a high-level programming language into a high-level operating system. A high-level OS permits flexible and efficient communication between programs through common l.anguage mechanisms, such as procedures and methods. It also guarantees type and memory safety across programs through language mechanisms, eliminating the need for separate process address spaces and data marshaling. This flexibility increases the potential for extensible and interoperating programs. Mere safety, however, provides neither the level of protection between applications nor the kind of process control that conventional OSes provide. As an example, SchemeEsq illustrates how a graphical programming environment must protect its GUI from interference from a program executing within the environment. Although language-based safety can prevent a program from trampling on the environment's data structures, it cannot prevent a program from starving the environment process or from leaking resources. MrEd combines the programming flexibility of a highlevel OS with the conventional process controls of a conventional OS. As we have shown, three key extensions make this 144 combination possible: threads with parameters, eventspaces, and custodians. Our approach to building a high-level OS on top of Scheme should apply equally well to other languages, such as ML or Java. For example, the user's program sends output to SchemeEsq by queueing a GUI event. Since the built-in queueing operation is atomic and non-blocking, there is no danger that the user's program will break a communication invariant by killing its own thread. More sophisticated communication protocols require stronger protection during the execution of the protocol. Indeed, merely adding a limit to the size of the output queue in SchemeEsq (so that the user's thread blocks when the queue is full) requires such protection. One general solution to the protection problem is to create a new thread-owned by SchemeEsq's custodian-for each communication. This techniques solves the problem because thread creation is an atomic operation, and the newly-created thread can execute arbitrarily many instructions without the risk of being killed by the user's program. Unfortunately, thread creation is an expensive operation in MrEd compared to procedure calls, as in many systems. To reduce this cost for common protection idioms, MrEd provides a call-in-nested-thread procedure that creates a child thread, and then blocks the parent thread until the child terminates. By exploiting the mutual exclusion between the parent and child threads, MrEd can eliminate much of the thread-creation and thread-swapping overhead for protection idioms. Using a similar technique, Ford and Lepreau [17] improved the performance of Mach RPC. Nevertheless, a significant overhead remains. [7], Oberon [33], and JavaOS [31]. All of these systems simplify the implementation of cooperating graphical programs through a high-level language. Although most of these systems support multiple processes, only MrEd provides the kind of process controls that are necessary for implementing a SchemeEsq-like programming environment.g Other related work aims to replicate the safety, security, and resource control of conventional operating systems within a single address space. Architectures such as Alta [2], SPIN [5], J-Kernel [22], and Nemesis [24], emphasize protection within a single address space, but at the expense of program integration through indirect and inefficient calls. For example, the J-Kernel relies on explicit capabilities, and 'On the Lisp Machine, allowing programmers to tinker with the OS on-the-fly was considered an advantage [7, page 441. therefore sacrifices the convenience of direct procedure calls and direct data sharing. Back and Hsieh [l] p rovide a detailed explanation of the difference between process control and mere safety in a Javabased operating system. They emphasize the importance of the "'red line" that separates user code and kernel code in a conventional OS. This red line exists in MrEd, separating low-level built-in primitives from the rest of the system. For example, queue-callback is effectively an atomic operation to the calling thread. MrEd goes one step further, providing programs with the ability to define new layers of red lines. In particular, SchemeEsq defines a red line between itself and the programs that it executes. Inferno [8] achieves many of the same goals as MrEd, but in a smaller language that is targeted for communications software rather than general-purpose GUI implementation. Balfanz and Gong [3] explore extensions to Java to support multiple processes, particularly multiple processes owned by different users within a single JVM. They derive some of the same constructs that are defined by MrEd, notably eventspaces. Haggis
REF demonstrate how key OS facilities are obtained through three key extensions -threads with parameters, eventspaces, and custodians -to a high level programming language.
Programming languages as operating systems (or revenge of the son of the lisp machine)
ICFP '99
Computer Science