Our weekly meeting and talk series, known affectionately as “PL-wonks”, is open to everyone interested in discussing programming languages research happening here at IU. Our talks include original research, experience reports, and tutorials. We also sometimes present papers from the literature that we're interested in.
Unless otherwise noted, PL talks happen every Friday at 4:15pm in Lindley Hall Room 101.
All are welcome to attend.
We have a tradition of baking cookies and other treats for our meetings (and there is usually something vegan-friendly and we avoid peanuts due to allergies).
|Sep 6||Jeremy Siek||Linking isn't Substitution||Michael Vitousek|
|Sep 13||Lindsey Kuper||LVars: Lattice-based Data Structures for Deterministic Parallelism||Ed Amsden||In LH 008|
|Abhishek Kulkarni||Embrace, Defend, Extend: A Methodology for Embedding Preexisting DSLs|
|Sep 20||Edward Amsden||TimeFlies: Push-Pull Signal-Function Functional Reactive Programming||Jason Hemann|
|Sep 27||Tentatively Cancelled for ICFP|
|Oct 4||Zach Sparks||There & Back Again: Reversible Programming||Eric Holk|
|Oct 11||Aaron Hsu||Co-Dfns Compiler||Johanna Hsu|
|Computer Science Outreach and Education with APL|
|Oct 18||Michael Vitousek||Gradual Typing||Aaron Todd|
|Oct 25||Programming Languages Fest before SPLASH|
|Nov 1||Jason Hemann||TBA||Tim Zakian||In LH 008|
|Nov 8||Cameron Swords||rKanren||Praveen Narayanan|
|Nov 15||Larisse Voufo||ConceptClang Update||Lindsey Kuper||In LH 008|
|Nov 22||Eric Holk||TBA||Wren Thornton||In LH 008|
|Nov 29||Tentatively Cancelled for T(of)urkey Day|
|Dec 6||Praveen Narayanan and Edward Amsden||TBA||Cameron Swords|
|Dec 13||Sam Tobin-Hochstadt||TBA||Zach Sparks|
|Dec 20||Will Byrd||TBA||Cameron Swords|
Come to this meeting to sign up for a talk slot and avoid being “volunteered!”
While the static semantics of separate compilation has received considerable attention in the programming languages literature, the dynamic semantics deserves further study. The meaning of linking two or more modules together is typically given by way of substitution, concatenation, or backpatching. However, none of these semantics is suitable as a specification from a compiler writer's viewpoint because they erase the boundary between modules. The compiler writer needs to know what behaviors are internal, and therefore may be optimized, versus what behaviors are external and therefore observable by other modules. Many aspects of the external behavior are specified in the application binary interface (ABI) of a language but the interaction between internal and external behavior is often ill specified. As a step towards understanding the semantics of separate compilation, we draw on trace semantics (from concurrent calculi) to give meaning to a separately compiled lambda calculus.
Programs written using a deterministic-by-construction model of parallel computation are guaranteed to always produce the same observable results, offering programmers freedom from subtle, hard-to-reproduce nondeterministic bugs that are the scourge of parallel software. We present a new model for deterministic-by-construction parallel programming that generalizes existing single-assignment models to allow multiple assignments that are monotonically increasing with respect to a user-specified partial order. Our model achieves determinism by using a novel shared data structure that allows only monotonic writes and ``threshold'' reads that block until a lower bound is reached. We give a proof of determinism and a prototype implementation for our model and describe how to extend it to support a limited form of nondeterminism that admits failures but never wrong answers.
Domain-specific languages such as StreamIt have valuable autoparallelizing code-generators, but they require learning a new language and tool-chain and may not integrate easily with a larger application. One solution is to transform such standalone DSLs into embedded languages within a general-purpose host language. This prospect comes with its own challenges, namely the compile-time and runtime integration of the two languages. We address these challenges, presenting our solutions in the context of a prototype embedding of StreamIt in Haskell. By demonstrating this methodology, we hope to encourage more reuse of DSL technology, and fewer short-lived reimplementations of existing techniques.
Functional Reactive Programming (FRP) is a promising class of abstractions for interactive programs. FRP systems provide values defined at all points in time (behaviors or signals) and values defined at countably many points in time (events) as abstractions. Signal-function FRP is a subclass of FRP which does not provide direct access to time-varying values to the programmer, but instead provides signal functions, which are reactive transformers of signals and events, as first-class objects in the program.
All signal-function implementations of FRP to date have utilized demand-driven or “pull-based” evaluation for both events and signals, producing output from the FRP system whenever the consumer of the output is ready. This greatly simplifies the implementation of signal-function FRP systems, but leads to inefficient and wasteful evaluation of the FRP system when this strategy is employed to evaluate events, because the components of the signal function which process events must be computed whether or not there is an event occurrence. In contrast, an input-driven or “push-based” system evaluates the network whenever new input is available. This frees the system from evaluating the network when nothing has changed, and then only the components necessary to react to the input are re-evaluated. This form of evaluation has been applied to events in standard FRP systems but not in signal-function FRP systems.
I describe the design and implementation of a signal-function FRP system which applies pull-based evaluation to signals and push-based evaluation to events (a “push-pull” system). The semantics of the system are discussed, and its performance and expressiveness for practical examples of interactive programs are compared to existing signal-function FRP systems through the implementation of a networking application.
(This talk was originally presented at the Rochester Institute of Technology in defense of my M.S. thesis of the same title.)
The functional programming world likes to talk about “pure” programs that are free of computational effects, but the definition of purity changes depending on the domain. In this talk, I will introduce the notion of information effects, which can duplicate or erase data, and present Pi, a programming language that is free of these effects. One benefit of eschewing information effects is that Pi is reversible: when run, any program may be reversed to run on its output, producing its input. Time permitting, I will also discuss work being to extend this to logic, higher order functions, and homotopy type theory.
Dyalog APL is fast, but faster is always better. The interpreter for Dyalog is capable of some nice optimizations thanks to things like idiom recognition, but interpretation naturally limits how much performance is readily accessible. Moreover, the language of dfns presents an ideal opportunity for compilation. This talk presents the Co-Dfns compiler, a new project to develop a compiler for an extended dfns language called Co-Dfns. The presentation includes a demonstration of the current compiler as well as illustrations of how the compiler will help to make Dyalog scale better in performance and reliability. Aaron will also explain how Co-Dfns is designed to take full advantage of modern hardware architectures.
APL was originally a device of the classroom, but most modern uses of it are distinctly industrial in nature. Why not bring APL back to the classroom? This presentation looks at the results of a summer program for high school students to introduce them to computer science. The program was very non-traditional on many fronts and leveraged APL in more than one way. Unlike many programs, students were able to work in multiple disciplines according to their interests and were never taught traditional serial programming. Instead, students used parallel programming in dfns to solve all problems. Moreover, all problems were real world problems instead of toy problems. This presentation will describe the results of the study as well as the theoretical foundations that drove the design of the study. Special consideration is given to the traditional objections to using this language and what has been learnt from observing student interaction.
Gradual typing allows a programming language to mix static and dynamic typing in a way that is straightforward to the programmer and, ideally, enables the advantages of static typing in statically typed portions of a program without sacrificing flexibility in the portions of the code that are dynamically typed. The basic operation of gradual typing is the cast, and in designing a gradual type system, it is important to be mindful in the specification for the semantics of casts. Casts on values of simple types are straightforward, and casts on functions are now fairly well understood. However, things become more complex when the heap comes into play. In this talk, I will discuss the design space of gradually typed references and objects, and will present several possible choices for the semantics of casts in a gradually-typed language with references.