Automatically transforming programs is hard, yet critical for automated program refactoring, rewriting, and repair. Multi-language syntax transformation is especially hard due to heterogeneous representations in synta...
详细信息
ISBN:
(纸本)9781450367127
Automatically transforming programs is hard, yet critical for automated program refactoring, rewriting, and repair. Multi-language syntax transformation is especially hard due to heterogeneous representations in syntax, parse trees, and abstract syntax trees (ASTs). Our insight is that the problem can be decomposed such that (1) a common grammar expresses the central context-free language (CFL) properties shared by many contemporary languages and (2) open extension points in the grammar allow customizing syntax (e.g., for balanced delimiters) and hooks in smaller parsers to handle language-specific syntax (e.g., for comments). Our key contribution operationalizes this decomposition using a Parser Parser combinator (PPC), a mechanism that generates parsers for matching syntactic fragments in source code by parsing declarative user-supplied templates. this allows our approach to detach from translating input programs to any particular abstract syntax tree representation, and lifts syntax rewriting to a modularly-defined parsing problem. A notable effect is that we skirt the complexity and burden of defining additional translation layers between concrete user input templates and an underlying abstract syntax representation. We demonstrate that these ideas admit efficient and declarative rewrite templates across 12 languages, and validate effectiveness of our approach by producing correct and desirable lightweight transformations on popular real-world projects (over 50 syntactic changes produced by our approach have been merged into 40+). Our declarative rewrite patterns require an order of magnitude less code compared to analog implementations in existing, language-specific tools.
A fundamental challenge in automated reasoning about programming assignments at scale is clustering student submissions based on their underlying algorithms. State-of-the-art clustering techniques are sensitive to con...
详细信息
ISBN:
(纸本)9781450367127
A fundamental challenge in automated reasoning about programming assignments at scale is clustering student submissions based on their underlying algorithms. State-of-the-art clustering techniques are sensitive to control structure variations, cannot cluster buggy solutions with similar correct solutions, and either require expensive pair-wise program analyses or training efforts. We propose a novel technique that can cluster small imperative programs based on their algorithmic essence: (A) how the input space is partitioned into equivalence classes and (B) how the problem is uniquely addressed within individual equivalence classes. We capture these algorithmic aspects as two quantitative semantic program features that are merged into a program's vector representation. Programs are then clustered using their vector representations. the computation of our first semantic feature leverages model counting to identify the number of inputs belonging to an input equivalence class. the computation of our second semantic feature abstracts the program's data flow by tracking the number of occurrences of a unique pair of consecutive values of a variable during its lifetime. the comprehensive evaluation of our tool SemCluster on benchmarks drawn from solutions to small programming assignments shows that SemCluster (1) generates far fewer clusters than other clustering techniques, (2) precisely identifies distinct solution strategies, and (3) boosts the performance of clustering-based program repair, all within a reasonable amount of time.
the proceedings contain 7 papers. the topics discussed include: fixpoint reuse for incremental JavaScript analysis;know your analysis: how instrumentation aids understanding static analysis;SootDiff: bytecode comparis...
ISBN:
(纸本)9781450367202
the proceedings contain 7 papers. the topics discussed include: fixpoint reuse for incremental JavaScript analysis;know your analysis: how instrumentation aids understanding static analysis;SootDiff: bytecode comparison across different Java compilers;modernizing parsing tools: parsing and analysis with object-oriented programming;commit-time incremental analysis;program analysis for process migration;and MetaDL: analyzing datalog in datalog.
the proceedings contain 9 papers. the topics discussed include: finite difference methods fengshui: alignment through a mathematics of arrays;data-parallel flattening by expansion;ALPyNA: acceleration of loops in pyth...
Most traditional software systems are not built withthe artificial intelligence support (AI) in mind. Among them, some may require human interventions to operate, e.g., the manual specification of the parameters in t...
详细信息
ISBN:
(纸本)9781450367127
Most traditional software systems are not built withthe artificial intelligence support (AI) in mind. Among them, some may require human interventions to operate, e.g., the manual specification of the parameters in the data processing programs, or otherwise, would behave poorly. We propose a novel framework called Autonomizer to autonomize these systems by installing the AI into the traditional programs. Autonomizer is general so it can be applied to many real-world applications. We provide the primitives and the runtime support, where the primitives abstract common tasks of autonomization and the runtime support realizes them transparently. Withthe support of Autonomizer, the users can gain the AI support with little engineering efforts. Like many other AI applications, the challenge lies in the feature selection, which we address by proposing multiple automated strategies based on the program analysis. Our experiment results on nine real-world applications show that the autonomization only requires adding a few lines to the source code. Besides, for the data-processing programs, Autonomizer improves the output quality by 161% on average over the default settings. For the interactive programs such as game/driving, Autonomizer achieves higher success rate with lower training time than existing autonomized programs.
the proceedings contain 8 papers. the topics discussed include: GPUIterator: bridging the gap between chapel and GPU platforms;calling chapel code: interoperability improvements;towards radix sorting in the chapel sta...
ISBN:
(纸本)9781450368001
the proceedings contain 8 papers. the topics discussed include: GPUIterator: bridging the gap between chapel and GPU platforms;calling chapel code: interoperability improvements;towards radix sorting in the chapel standard library;implementing stencil problems in chapel: an experience report;chapel unblocked: recent communication optimizations in chapel;Arkouda: Interactive data exploration backed by chapel;chapel graph library (CGL);and chapel in cray HPO.
Type systems and syntactic sugar are both valuable to programmers, but sometimes at odds. While sugar is a valuable mechanism for implementing realistic languages, the expansion process obscures program source structu...
详细信息
ISBN:
(纸本)9781450356985
Type systems and syntactic sugar are both valuable to programmers, but sometimes at odds. While sugar is a valuable mechanism for implementing realistic languages, the expansion process obscures program source structure. As a result, type errors can reference terms the programmers did not write (and even constructs they do not know), baffling them. the language developer must also manually construct type rules for the sugars, to give a typed account of the surface language. We address these problems by presenting a process for automatically reconstructing type rules for the surface language using rules for the core. We have implemented this theory, and show several interesting case studies.
Network operators often need to ensure that important probabilistic properties are met, such as that the probability of network congestion is below a certain threshold. Ensuring such properties is challenging and requ...
详细信息
ISBN:
(纸本)9781450356985
Network operators often need to ensure that important probabilistic properties are met, such as that the probability of network congestion is below a certain threshold. Ensuring such properties is challenging and requires both a suitable language for probabilistic networks and an automated procedure for answering probabilistic inference queries. We present BAYONET, a novel approach that consists of: (i) a probabilistic network programminglanguage and (ii) a system that performs probabilistic inference on BAYONET programs. the key insight behind BAYONET is to phrase the problem of probabilistic network reasoning as inference in existing probabilistic languages. As a result, BAYONET directly leverages existing probabilistic inference systems and offers a flexible and expressive interface to operators. We present a detailed evaluation of BAYONET on common network scenarios, such as network congestion, reliability of packet delivery, and others. Our results indicate that BAYONET can express such practical scenarios and answer queries for realistic topology sizes (with up to 30 nodes).
this paper introduces the "Search, Align, and Repair" data-driven program repair framework to automate feedback generation for introductory programming exercises. Distinct from existing techniques, our goal ...
详细信息
ISBN:
(纸本)9781450356985
this paper introduces the "Search, Align, and Repair" data-driven program repair framework to automate feedback generation for introductory programming exercises. Distinct from existing techniques, our goal is to develop an efficient, fully automated, and problem-agnostic technique for large or MOOC-scale introductory programming courses. We leverage the large amount of available student submissions in such settings and develop new algorithms for identifying similar programs, aligning correct and incorrect programs, and repairing incorrect programs by finding minimal fixes. We have implemented our technique in the SARFGEN system and evaluated it on thousands of real student attempts from the Microsoft-DEV204.1x edX course and the Microsoft Code-Hunt platform. Our results show that SARFGEN can, within two seconds on average, generate concise, useful feedback for 89.7% of the incorrect student submissions. It has been integrated withthe Microsoft-DEV204.1X edX class and deployed for production use.
We introduce inference metaprogramming for probabilistic programminglanguages, including new language constructs, a formalism, and the first demonstration of effectiveness in practice. Instead of relying on rigid bla...
详细信息
ISBN:
(纸本)9781450356985
We introduce inference metaprogramming for probabilistic programminglanguages, including new language constructs, a formalism, and the first demonstration of effectiveness in practice. Instead of relying on rigid black-box inference algorithms hard-coded into the languageimplementation as in previous probabilistic programminglanguages, inference metaprogramming enables developers to 1) dynamically decompose inference problems into subproblems, 2) apply inference tactics to subproblems, 3) alternate between incorporating new data and performing inference over existing data, and 4) explore multiple execution traces of the probabilistic program at once. Implemented tactics include gradient-based optimization, Markov chain Monte Carlo, variational inference, and sequental Monte Carlo techniques. Inference metaprogramming enables the concise expression of probabilistic models and inference algorithms across diverse fields, such as computer vision, data science, and robotics, within a single probabilistic programminglanguage.
暂无评论