More Like this

1. Real-time MLton: A Standard ML runtime for real-time functional programs

   https://doi.org/10.1017/S0956796821000174  

   SHIVKUMAR, BHARGAV; MURPHY, JEFFREY; ZIAREK, LUKASZ (January 2021, Journal of Functional Programming)

   Abstract There is a growing interest in leveraging functional programming languages in real-time and embedded contexts. Functional languages are appealing as many are strictly typed, amenable to formal methods, have limited mutation, and have simple but powerful concurrency control mechanisms. Although there have been many recent proposals for specialized domain-specific languages for embedded and real-time systems, there has been relatively little progress on adapting more general purpose functional languages for programming embedded and real-time systems. In this paper, we present our current work on leveraging Standard ML (SML) in the embedded and real-time domains. Specifically, we detail our experiences in modifying MLton, a whole-program optimizing compiler for SML, for use in such contexts. We focus primarily on the language runtime, reworking the threading subsystem, object model, and garbage collector. We provide preliminary results over a radar-based aircraft collision detector ported to SML. 

   more » « less
2. Equivalence by Canonicalization for Synthesis-Backed Refactoring

   https://doi.org/10.1145/3656453  

   Lubin, Justin; Ferguson, Jeremy; Ye, Kevin; Yim, Jacob; Chasins, Sarah E (June 2024, Proceedings of the ACM on Programming Languages)

   We present an enumerative program synthesis framework calledcomponent-based refactoringthat can refactor direct style code that does not use library components into equivalent combinator style code that does use library components. This framework introduces a sound but incomplete technique to check the equivalence of direct code and combinator code calledequivalence by canonicalizationthat does not rely on input-output examples or logical specifications. Moreover, our approach can repurpose existing compiler optimizations, leveraging decades of research from the programming languages community. We instantiated our new synthesis framework in two contexts: (i) higher-order functional combinators such as and in the statically-typed functional programming language Elm and (ii) high-performance numerical computing combinators provided by the NumPy library for Python. We implemented both instantiations in a tool called Cobbler and evaluated it on thousands of real programs to test the performance of the component-based refactoring framework in terms of execution time and output quality. Our work offers evidence that synthesis-backed refactoring can apply across a range of domains without specification beyond the input program. 

   more » « less
3. Multilingual CS Education Pathways: Implications for Vertically-Scaled Assessment

   https://doi.org/10.1145/3478431.3499315  

   Kao, Yvonne; Weintrop, David (February 2022, SIGCSE 2022: Proceedings of the 53rd ACM Technical Symposium on Computer Science Education)

   The expansion of computer science (CS) into K-12 contexts has resulted in a diverse ecosystem of curricula designed for various grade levels, teaching a variety of concepts, and using a wide array of different programming languages and environments. Many students will learn more than one programming language over the course of their studies. There is a growing need for computer science assessment that can measure student learning over time, but the multilingual learning pathways create two challenges for assessment in computer science. First, there are not validated assessments for all of the programming languages used in CS classrooms. Second, it is difficult to measure growth in student understanding over time when students move between programming languages as they progress in their CS education. In this position paper, we argue that the field of computing education research needs to develop methods and tools to better measure students' learning over time and across the different programming languages they learn along the way. In presenting this position, we share data that shows students approach assessment problems differently depending on the programming language, even when the problems are conceptually isomorphic, and discuss some approaches for developing multilingual assessments of student learning over time. 

   more » « less
4. Provably space-efficient parallel functional programming

   https://doi.org/10.1145/3434299  

   Arora, Jatin; Westrick, Sam; Acar, Umut A. (January 2021, Proceedings of the ACM on Programming Languages)

   null (Ed.)

   Because of its many desirable properties, such as its ability to control effects and thus potentially disastrous race conditions, functional programming offers a viable approach to programming modern multicore computers. Over the past decade several parallel functional languages, typically based on dialects of ML and Haskell, have been developed. These languages, however, have traditionally underperformed procedural languages (such as C and Java). The primary reason for this is their hunger for memory, which only grows with parallelism, causing traditional memory management techniques to buckle under increased demand for memory. Recent work opened a new angle of attack on this problem by identifying a memory property of determinacy-race-free parallel programs, called disentanglement, which limits the knowledge of concurrent computations about each other’s memory allocations. The work has showed some promise in delivering good time scalability. In this paper, we present provably space-efficient automatic memory management techniques for determinacy-race-free functional parallel programs, allowing both pure and imperative programs where memory may be destructively updated. We prove that for a program with sequential live memory of R * , any P -processor garbage-collected parallel run requires at most O ( R * · P ) memory. We also prove a work bound of O ( W + R * P ) for P -processor executions, accounting also for the cost of garbage collection. To achieve these results, we integrate thread scheduling with memory management. The idea is to coordinate memory allocation and garbage collection with thread scheduling decisions so that each processor can allocate memory without synchronization and independently collect a portion of memory by consulting a collection policy, which we formulate. The collection policy is fully distributed and does not require communicating with other processors. We show that the approach is practical by implementing it as an extension to the MPL compiler for Parallel ML. Our experimental results confirm our theoretical bounds and show that the techniques perform and scale well. 

   more » « less
5. Survey of Control-flow Integrity Techniques for Real-time Embedded Systems

   https://doi.org/10.1145/3538275  

   Mishra, Tanmaya; Chantem, Thidapat; Gerdes, Ryan (July 2022, ACM Transactions on Embedded Computing Systems)

   Computing systems, including real-time embedded systems, are becoming increasingly connected to allow for more advanced and safer operation. Such embedded systems are also often resource-constrained, for example, with lower processing capabilities compared to general-purpose computing systems like desktops or servers. With the advent of paradigms such as internet-of-things (IoT), embedded systems in both commercial and industrial contexts are being increasingly interconnected and exposed to the external networks to improve automation and efficiency of operation. However, allowing external interfaces to such embedded systems increases their exposure to attackers. With an increase in attacks against embedded systems ranging from home appliances to industrial control systems operating critical equipment that have real-time requirements, it is imperative that defense mechanisms be created that explicitly consider such resource and real-time constraints. Control-flow integrity (CFI) is a family of defense mechanisms that prevent attackers from modifying the flow of execution. We survey CFI techniques, ranging from the basic to state of the art, that are built for embedded systems and real-time embedded systems and find that there is a dearth, especially for real-time embedded systems, of CFI mechanisms. We then present open challenges to the community to help drive future research in this domain. 

   more » « less