MSPLS Spring 2006 Meeting

MSPLS Logo

The Spring 2006 meeting of the Midwest Society for Programming Languages and Systems will be held on Saturday, April 22nd, 2006, at the University of Illinois Urbana-Champaign.

Registration

While registration is not required, it is recommended. Please send registration requests to Grigore Rosu or Mark Hills with the subject Register.

Submissions

If you are interested in presenting, please send the presentation title, the names of the speaker and any additional authors, and a brief abstract to Grigore Rosu or Mark Hills with the subject "submit:". If this talk is based on an existing paper or papers, you can also send .dvi, .ps, or .pdf versions of the papers, or links to the papers, and they will be included on this site in the workshop schedule. We are looking at the feasability of putting together proceedings as a departmental technical report as well.

Submissions will be accepted based on available time slots and appropriateness for the workshop. The presentation can be based on already published work, although we encourage presentation of early-stage research that has not yet been published as well.

Agenda

Presentation Schedule
Time Speaker Title Abstract Links
10:00 - 10:45 Maria Garzaran
University of Illinois Urbana-Champaign
Programming for Parallelism and Locality with Hierarchically Tiled Arrays

Tiling has proven to be an effective mechanism to develop high performance implementations of algorithms. Tiling can be used to organize computations so that communication costs in parallel programs are reduced and locality in sequential codes or sequential components of parallel programs is enhanced.

In this paper, a data type - Hierarchically Tiled Arrays or HTAs - that facilitates the direct manipulation of tiles is introduced. HTA operations are overloaded array operations. We argue that the implementation of HTAs in sequential OO languages transforms these languages into powerful tools for the development of high-performance parallel codes and codes with high degree of locality. To support this claim, we discuss our experiences with the implementation of HTAs for MATLAB and C++ and the rewriting of the NAS benchmarks and a few other programs into HTA-based parallel form.

Authors: Ganesh Bikshandi(1) , Jia Guo (1) , Daniel Hoeflinger (1) , Gheorghe Almasi (2) , Basilio B. Fraguela (3) , Maria J. Garzaran (1), David Padua (1) and Christoph von Praun (2)

(1) University of Illinois at Urbana-Champaign
(2) IBM T.J. Watson Research Center
(3) Universidade da Coruna,Spain

 
10:45 - 11:15 T. Baris Aktemur
University of Illinois Urbana-Champaign
Data-flow analysis of program fragments with holes In the context of Runtime Program Generation, complete information about the program that will be generated is not available until the program fragments come together at runtime to form the final program. Not having this information at compile-time prevents us from performing a complete pre-runtime analysis of the program. The most naive approach is to wait until the program fragments are put together, and then to run the analysis on the program. The drawback of this approach is the high run-time cost of the analysis. To address this problem, we stage the analysis into two phases, offline and online, with the goal of pushing as much of the analysis as possible to the offline stage. We show that the results of the offline phase can be represented compactly for left-distributive data flow problems. We give preliminary performance benchmarks of several sample programs. These benchmarks are promising. Joint work with Samuel Kamin and Michael Katelman.  
11:15 - 11:45 Mark Hills
University of Illinois Urbana-Champaign
Using Rewriting Logic for Modular Language Design and Interpretation Rewriting logic provides a simple, flexible method for specifying the semantics of programming languages. Using term rewriting engines that support rewriting logic, such as Maude, allows these definitions to be used as executable interpreters for programs in the defined language. In this talk, we present our current work on using rewriting logic to define programming languages, including work on K, a domain-specific "sugaring" of rewriting logic for defining programming languages. We show several examples of using K and rewriting logic to define languages and language fragments, compare use of K to our past efforts, and discuss future directions. Joint work with Grigore Rosu and Traian Serbanuta (both UIUC).  
11:45 - 12:15 Danny Dig
University of Illinois Urbana-Champaign
Automated Detection of Refactorings in Evolving Components One of the costs of reusing software components is updating applications to use the new version of the components. Updating an application can be error-prone, tedious, and disruptive of the development process. Our previous study showed that more than 80% of the disruptive changes in five different components were caused by refactorings. If the refactorings that happened between two versions of a component could be automatically detected, a refactoring tool could replay them on applications. We present an algorithm that detects refactorings performed during component evolution. Our algorithm uses a combination of a fast syntactic analysis to detect refactoring candidates and a more expensive semantic analysis to refine the results. The experiments on components ranging from 17 KLOC to 352 KLOC show that our algorithm detects refactorings in real-world components with accuracy over 85%. Joint work with Can Comertoglu, Darko Marinov, Ralph Johnson (all UIUC)  
12:15 - 1:45 Lunch      
1:45 - 2:30 Alley Stoughton
Kansas State University
On the Future of eXene Up through the mid-1990s, Gansner and Reppy designed and implemented eXene---a multi-threaded, higher-order user-interface toolkit for the X window system. EXene is implemented in Concurrent ML (CML), which is a Standard ML of New Jersey (SML/NJ) library, and is provided as part of the SML/NJ distribution. EXene has many appealing attributes and is certainly usable in its current state. But it suffers from some deficiencies which have limited its use, and there are a number of ways in which it could usefully be improved. In this talk, we describe our efforts at restarting the development of eXene, saying what we have accomplished so far, and detailing our plans for the future. Joint work with Dustin deBoer. eXene
2:30 - 3:00

Dinakar Dhurjati
University of Illinois Urbana-Champaign

SAFECode: Enforcing Alias Analysis for Weakly Typed Languages
Static analysis of programs in weakly typed languages such as C and C++ is generally not sound because of possible memory errors due to dangling pointer references, uninitialized pointers, and array bounds overflow. Optimizing compilers can produce unpredictable results when such errors occur, but this is quite undesirable for many tools that aim to analyze security and reliability properties with guarantees of soundness. We describe a compilation strategy for standard C programs that guarantees sound semantics for an aggressive interprocedural pointer analysis (or simpler ones), a call graph, and type information for a subset of memory. These provide the foundation for sophisticated static analyses to be applied to such programs with a guarantee of soundness. Our work builds on a previously published transformation called Automatic Pool Allocation to ensure that hard-to-detect memory errors (dangling pointer references and certain array bounds errors) cannot invalidate the call graph, points-to information or type information. The key insight behind our approach is that pool allocation can be used to create a run-time partitioning of memory that matches the compile-time memory partitioning in a points-to graph, and efficient checks can be used to isolate the run-time partitions. Furthermore, we show that the sound analysis information enables static checking techniques that \emph{reliably} eliminate many run-time checks. We formalize our approach as a new type system with the necessary run-time checks in operational semantics and prove the correctness of our approach for a subset of C. Our approach requires no source code changes, allows memory to be managed explicitly, and does not use meta-data on pointers or individual tag bits for memory. Using several benchmarks and system codes, we show experimentally that the run-time overheads are low (less than 10% in nearly all cases and 30% in the worst case we have seen). We also show the effectiveness of reliable static analyses in eliminating run-time checks. Joint work with Sumant Kowshik and Vikram Adve. paper
3:00 - 3:45 Jacob Matthews
University of Chicago
The meaning of multi-language programs We present a technique for modeling the operational semantics and type systems of multi-language systems, e.g., foreign-function interfaces. In contrast to most multi-language work to date, our technique does not focus on low-level details of interoperability like garbage collection and representation coherence. Instead, we combine the models of two languages in a natural way that abstracts implementation concerns and allows us to focus on the resulting system's semantics. Joint work with Robert Bruce Findler (U Chicago).  
3:45 - 4:15 Sameer Sundresh
University of Illinois Urbana-Champaign
An Extensible Language Framework
Traditionally, programming languages are designed with a fixed syntax and associated semantics, and implemented as a fixed translation from source code to machine code or interpreted behavior. Macros and templates have been developed to allow customized code generation, however, the input and target languages are still to a large degree fixed; moreover, these mechanisms tend to complicate program modularity. To avoid these limitations, we explore the notion of a compiler as a generic tool for composing and orchestrating the transformation of program modules from one language to another. Towards this end, we have designed a programming language for the hierarchical definition of language syntaxes, program modules in these languages, and transformation modules between languages.
At the high level, this language can be viewed as a typed lambda-calculus with languages as types and modules as functions and values. The resulting framework shows promise for multi-language interoperability and development of domain-specific languages, especially for embedded systems. Joint work with Gul Agha (UIUC).
 
4:15 - 4:55

Trevor Cickovski
University of Notre Dame

Domain-Specific Languages in Computational Biology

Domain-Specific Languages (DSLs) can contribute to software usability by allowing expression of phenomena within a particular domain of study using syntax understandable to domain experts and a high level of abstraction that simplifies these expressions. Computational biology is one domain where DSLs can be highly useful, and we demonstrate this through two DSLs: BioLogo and MDL (Molecular Dynamics Language) which although possessing vastly different designs, accomplish many of the goals of DSLs in their respective computational biology subdomains. BioLogo is a language extension of XML for morphogenesis modeling, able to represent cellular phenomena such as type differentiation, adhesion, volume constraints; as well as chemical reaction-diffusion. MDL builds upon Python and is useful for creating and executing interactive simulations of molecular dynamics, and prototyping new algorithms. We present their designs, along with some example biologically relevant simulations which can be run using these languages. Joint work with Jesus A. Izaguirre.

Related work:

* Trevor Cickovski, Chengbang Huang, Rajiv Chaturvedi, Tilmann Glimm, H. George E. Hentschel, Mark Alber, James A. Glazier, Stuart A. Newman, and Jesus A. Izaguirre. A Framework For Three-Dimensional Simulation of Morphogenesis. ACM Transactions on Computational Biology and Biocomplexity 2(4):273-288, 2005.

* Dylan Brandtner, Trevor Cickovski and Jesus A. Izaguirre. Interactive Molecular Dynamics. Notre Dame Technical Report 2005-11, July 2005.

* Chun Bong Benjamin Yau, Trevor Cickovski and Jesus A. Izaguirre.
Molecular Dynamics Language (MDL). Notre Dame Technical Report 2005-13, August 2005.

 
4:55 - ??? Business meeting   Elect a new president, discuss location for next workshop.  

 

 

Contact

The host of this meeting is Grigore Rosu, grosu@cs.uiuc.edu. You may also contact Mark Hills with any questions at mhills@cs.uiuc.edu.

Location

The MSPLS workshop will be held at the Siebel Center for Computer Science, the home of the Department of Computer Science at UIUC, in room 3405 (a map of the third floor can be found here). Parking is plentiful on weekends, although you should look for University parking lots, garages, and meters, which are usually free (Champaign and Urbana both require you to feed the meter on Saturday). On the map below, the North Campus Parking Deck to the north and the parking lot (marked B2) next to University High directly to the South are both available for free parking on Saturdays.

map of Siebel Center

For additional information about reaching campus, including campus maps and directions, click here.