B.Sc. Computer Engineering (1993) Kuwait University
Ph.D. Computer Science and Engineering (1999) Oregon Graduate Institute
Office: Duncan Hall, 3103
Taha's home page
Walid M. Taha
Adjunct Professor of Computer Science
Embedded systems, software engineering, programming languages, compilers, type theory, automated proof-checkers, and semantics
My interest is in the design and implementation of resource-aware progrmaming languages, and in demonstrating the positive impact of such languages on software processes and products. Resource-awareness means that the language has a clear underlying cost model, and that the programmer has fine control over the cost of programs. As embedded systems play an increasingly important role in our daily life, demand for technologies that can help enhance the reliability of such systems will continue to increase.
I have investigated two examples of resource-aware languages. My doctoral work was on the theory and applications of multi-stage languages (such as MetaML and MetaOCaml) and I have continued to work in this area ever since. More recently, I have become also interested in resource-bounded languages (such as RT-FRP and E-FRP). The following describes my work in each of these areas in more detail.
Software is rapidly becoming a critical component of almost every appliance and device around us, including cars, microwaves, defense systems, and medical equipment. As a building material, software's remarkable advantage is that it can be altered and duplicated at virtually no cost. But it is also remarkably fragile: An unintended setting for one bit - one indivisible unit of information - can alter the operation of the largest machine-controlled physical system. While research on high-level languages has produced a wide range of innovative abstraction mechanisms that make programs easier to understand, such mechanisms either have an associated runtime cost, require the programmer to relinquish control over resources, or both. Embedded software components running inside physical devices must run for long periods of time with limited resources. These strict constraints have resulted in embedded software development depending on very low level tools and notation that make programs difficult to understand, check, and manage. A wide range of practical factors, including the constant influx of new devices and the ever increasing demand for interoperability make addressing this problem an urgent matter. The goal of my research is to show that a novel class of languages called Resource-aware Programming (RAP) languages can be an effective approach to addressing this problem. A RAP languages provides two key mechanisms: 1. Allowing the programmer to write programs where part of the computation is performed on the development platform, and the rest is performed on the embedded platform. This facility can allow the programmer to use almost any abstraction mechanism without paying a runtime penalty on the embedded platform. While McIlroy's work on macros in 1960 marked the start of efforts to support this otherwise intuitive functionality, realizing this support has proven surprisingly challenging. A promising technique for achieving this goal is multi-stage programming (MSP), proposed in my doctoral dissertation and extensively developed since. Most recently I proposed the notion of environment classifiers, and showed that it subsumes various previously incompatible approaches to typing MSP languages. I also used MSP to resolve two long-standing open research questions. The first is how to achieve "optimal specialization" in typed languages. This question was posed by the partial evaluation pioneer Neil Jones and had remained open for over a decade despite several efforts before ours. The second is how to define an expressive, type-safe, macro system and to define its behavior rigorously and concisely. Along side these efforts on foundations, I have led the development and implementation of an MSP language called MetaOCaml. This implementation has proven invaluable for experimental work by our research group and by several other groups around the world.
2. Providing static analyses that ensure - ahead of time - that any computation remaining for the embedded platform will be resource-bounded. Most of our early work in this area focused on ensuring safety in the embedded platform. Our first result on resource-boundedness showed that RAP languages can statically guarantee that generated (embedded platform) programs are heap-bounded. As an in-depth case study, we showed that a RAP language can express the Fast Fourier Transform (FFT) with source code only marginally larger than the text-book definition of the Cooley-Tuckey recurrence. This RAP program generates a circuit with an optimal number of multiplications and additions. Further work led to a new insight about FFT itself. Our generator, which uses only a small number optimizations, can generate circuits with arithmatic operation counts that precisely match those of two well-established benchmarks (Split-Radix and FFTW). Furthermore, which benchmark is matched depends only on how multiplication of complex numbers is implemented. Viewed as software, the FFT implementations we generate run within a small factor of the FFTW system.
Current activity is focused on applying RAP techniques to the domain of device driver development. In addition to dealing with the basic resources of time and space, this domain requires addressing event-driven computation as well as concurrency. We also continue to explore hardware circuit design as the next challenging domain for our case studies. We expect that incorporating layout and routing information into a RAP language is possible, and that such a language would provide hardware designers with a tool that addresses some of the most pressing challenges in that domain.
Jun Inoue, Doctoral. "Reasoning About Multi-stage Programs." (2013).(Thesis or Dissertation Director)
Mathias Ricken, Doctor of Philosophy. "A Framework for Testing Concurrent programs." (2011).(Committee Member)
Cherif Salama, Doctor of Philosophy. "Static Analysis for Circuit Families." (2010).(Thesis or Dissertation Director)
Daniel Smith, Doctor of Philosophy. "Designing Type Inference for Typed Object-Oriented Languages." (2010).(Committee Member)
Jun Inoue, Master of Science. "Reasoning About Staged programs." (2010).(Thesis or Dissertation Director)
Yun Angela, Master of Science. "Acumen: An Environment for Rapid Prototyping of Cyber-physical Systems." (2010).(Thesis or Dissertation Director)
Rajarshi Bandyopadhyay, Doctor of Philosophy. "Compiling dynamic languages via statically typed functional languages ." (2009).(Thesis or Dissertation Director)
Sumit Nain, Master of Science. "Linear vs. Branching Time: A Semantical Perspective." (2009).(Committee Member)
Cheryl McCosh, Doctor of Philosophy. "A Type-Based Protype Compiler for Telescoping Languages." (2008).(Committee Member)
Gabriel Marin, Ph.D. "n/a." (2008).(Committee Member)
Hamid Nejati, Ph.D. "n/a." (2008).(Committee Member)
Joseph Young, Ph.D. "n/a." (2008).(Thesis or Dissertation Director)
Raj Bandyopadhyay, Ph.D. "Compiling dynamic languages via typed funtional languages." (2008).(Thesis or Dissertation Director)
Roumen Kaiabachev, Master of Science. "A Transactional Compiler for E-FRP With Priorities*." (2008).(Thesis or Dissertation Director)
Sami Kirolos, Ph.D. "n/a." (2008).(Committee Member)
Sumit Nain, M.S. "n/a." (2008).(Committee Member)
Tamer Ragheb, Ph.D. "n/a." (2008).(Committee Member)
Daniel Smith, Master of Science. "Completing the Java Type System." (2007).(Committee Member)
Gabriel Marin, Ph.D. "Application Insight Through Performance Modeling." (2007).(Committee Member)
Mathias Ricken, Master of Science. "A Framework for Testing Concurrent Programs." (2007).(Committee Member)
Roumen Kaiabachev, Master of Sceince. "A Transactional Compiler for E-FRP With Priorities." (2007).(Thesis or Dissertation Director)
James Hsia, Master of Science. "Adding Support for Language Levels to DrJava." (2005).(Committee Member)
James Sasitorn, Master of Science. "Efficient Implementation of Frist-class Polymorphic Methods in Java." (2005).(Committee Member)
Jason Eckhardt, Master of Science in Computer Science. "Global Register Allocation Using Program Structure." (2005).(Committee Member)
Michael Jensen, Master of Science in Computer Science. "Growing DrJava to Cope with Language Extensions Carried out in Java 5.0." (2005).(Committee Member)
Scott Crosby, Master of Science. "Algorithmic Attacks and Timing Leaks in Distributed Systems." (2005).(Committee Member)
John Garvin, Master of Science. "RCC: A Compiler for the R Language for Statistical Computing." (2004).(Committee Member)
Stephan Ellner, Master of Science. "PreVIEW: An Untyped Graphical Calculus for Resource-aware Programming." (2004).(Thesis or Dissertation Director)
Charles Reis, Master of Science. "A Pedagogic Programming Environment for Java that Scales to Production Programming." (2003).(Committee Member)