Programming Languages

Programming Language research at Yale emphasizes expressive, efficient, flexible, and reliable programming environments for future information, computation, and communication systems. We approach this problem from several directions including language design, formal methods, compiler implementation, programming environments, and run-time systems.

One approach to achieving high-quality programming environments is via high-quality programming languages. Several programming languages developed at or associated with the department (in particular Haskell, Linda, and Standard ML) have achieved worldwide currency, reflecting the department’s leadership in the areas of functional programming and parallel computing. Haskell is a purely functional programming language in which programs are written in a highly mathematical, declarative notation, facilitating the use of formal methods and its use as both a prototyping language and an executable specification language. Linda is a coordination language based on a shared and associative object memory model which has proved useful for distributed and ensemble computing; efficient Linda implementations exist on most asynchronous parallel architectures, and the system sees increasingly widespread use as a production programming vehicle.

Many application domains have distinct requirements that dictate the development of special-purpose software. Paul Hudak’s recent work at Yale has focused on the ultimate goal of this process: the design of domain-specific languages that capture precisely and succinctly an application domain’s underlying semantics. Research in the design, formal semantics, and implementation of such languages is underway, with applications in graphics, animation, robotics, computer vision, computer music, and general control systems. This work has led to the development of functional reactive programming (FRP), a high-level, declarative framework for specifying, prototyping, and implementing "hybrid" systems that combine both continuous values and discrete events. Of particular interest is the use of FRP in real-time and embedded systems, where resource consumption (in both time and space) is a critical issue, and must be known at compile time.

Zhong Shao’s research has demonstrated that modern type-safe languages can be implemented efficiently and used in systems and application programming. The results are smaller, better structured, and easier to maintain systems. Type-safe languages are also ideal for many emerging applications such as extensible operating systems, code migration across the internet, scripting, and multimedia programming. For example, type safety and system-wide garbage collection may allow future computer systems to utilize system resources more efficiently and reduce drastically the copying and protection boundary switching Ñ a major bottle-neck between fast processors and networks in today’s distributed systems. Applications of this software technology include secure Internet programming, evolutionary software development, and the design and implementation of modern extension languages.

On a more abstract level, Carsten Schürmann’s research puts special emphasis on intelligent tools that support the design of logical systems, which are prevalent in areas such as functional programming languages, type systems, and logics. Without any supporting tools, programming language developers typically rely on pencil and paper to convince themselves of the soundness of their design. However, this process is often extremely tedious, very time-consuming, and error-prone. With Schürmann’s tools, developers can catch fundamental flaws at early stages of their designs by means of machine-assisted reasoning. The fundamental goal of this research program is to provide solutions to common questions such as how to represent logical systems in a computer, how to formalize their properties, and how to engineer techniques that support reasoning processes about them. The tools find a large number of applications in the areas of programming language design, type systems design, and logic design, where they ensure properties such as safety, soundness, and completeness.

On a larger scale, David Gelernter’s software ensemble research is the study of programs that are built out of many separate, coordinated activities, with an emphasis on recognizing and understanding the properties that all such systems share, versus the more widespread practice of dividing the field into intellectually disjoint sub-areas. Ensemble computing includes the study of: (1) parallel programs, which focus many computers on a single problem in order to solve it faster; (2) distributed programs, which attempt to integrate many separate, autonomous computers; (3) ensembles, which include time- as opposed to space-separated activities and which pose new research challenges in the areas of file systems and databases, and; (4) the relationship between software ensembles and naturally occurring ones, as for example in economic, biological, or physical systems. All of these areas pose both theoretical and pragmatic questions. The search for a formal definition of "coordination language," and the development of Internet applications are new areas of focus in the software ensemble research effort.

Faculty members in the Programming Languages and Systems area are David Gelernter, Paul Hudak, Carsten Schürmann, and Zhong Shao. Research faculty include Nick Carriero, John Peterson, and Valery Trifonov.