This article describes a neural semantic parser that maps natural language utterances onto logical forms that can be executed against a task-specific environment, such as a knowledge base or a database, to produce a response. The parser generates tree-structured logical forms with a transition-based approach, combining a generic tree-generation algorithm with domain-general grammar defined by the logical language. The generation process is modeled by structured recurrent neural networks, which provide a rich encoding of the sentential context and generation history for making predictions. To tackle mismatches between natural language and logical form tokens, various attention mechanisms are explored. Finally, we consider different training settings for the neural semantic parser, including fully supervised training where annotated logical forms are given, weakly supervised training where denotations are provided, and distant supervision where only unlabeled sentences and a knowledge base are available. Experiments across a wide range of data sets demonstrate the effectiveness of our parser.

Cloud computing has made the resources needed to execute large-scale in-memory distributed computations widely available. Specialized programming models, e.g., MapReduce, have emerged to offer transparent fault tolerance and fault recovery for specific computational patterns, but they sacrifice generality. In contrast, the Resilient X10 programming language adds failure containment and failure awareness to a general purpose, distributed programming language. A Resilient X10 application spans over a number of places. Its formal semantics precisely specify how it continues executing after a place failure. Thanks to failure awareness, the X10 programmer can in principle build redundancy into an application to recover from failures. In practice, however, correctness is elusive, as redundancy and recovery are often complex programming tasks. This article further develops Resilient X10 to shift the focus from failure awareness to failure recovery, from both a theoretical and a practical standpoint. We rigorously define the distinction between recoverable and catastrophic failures. We revisit the happens-before invariance principle and its implementation. We shift most of the burden of redundancy and recovery from the programmer to the runtime system and standard library. We make it easy to protect critical data from failure using resilient stores and harness elasticity—dynamic place creation—to persist not just the data but also its spatial distribution. We demonstrate the flexibility and practical usefulness of Resilient X10 by building several representative high-performance in-memory parallel application kernels and frameworks. These codes are 10× to 25× larger than previous Resilient X10 benchmarks. For each application kernel, the average runtime overhead of resiliency is less than 7%. By comparing application kernels written in the Resilient X10 and Spark programming models, we demonstrate that Resilient X10’s more general programming model can enable significantly better application performance for resilient in-memory distributed computations.

We introduce a neural semantic parser which is interpretable and scalable.Our model converts natural language utterances to intermediate, domain-general natural language representations in the form of predicate-argument structures, which are induced with a transition system and subsequently mapped to target domains.The semantic parser is trained end-to-end using annotated logical forms or their denotations.We achieve the state of the art on SPADES and GRAPHQUESTIONS and obtain competitive results on GEO-QUERY and WEBQUESTIONS.The induced predicate-argument structures shed light on the types of representations useful for semantic parsing and how these are different from linguistically motivated ones. 1

We present a generative model of natural language sentences and demonstrate its application to semantic parsing.In the generative process, a logical form sampled from a prior, and conditioned on this logical form, a grammar probabilistically generates the output sentence.Grammar induction using MCMC is applied to learn the grammar given a set of labeled sentences with corresponding logical forms.We develop a semantic parser that finds the logical form with the highest posterior probability exactly.We obtain strong results on the GeoQuery dataset and achieve state-of-the-art F1 on Jobs.

It is well established that in many scenarios there is no single solver that will provide optimal performance across a wide range of problem instances. Taking advantage of this observation, research into algorithm selection is designed to help identify the best approach for each problem at hand. This segregation is usually based on carefully constructed features, designed to quickly present the overall structure of the instance as a constant size numeric vector. Based on these features, a plethora of machine learning techniques can be utilized to predict the appropriate solver to execute, leading to significant improvements over relying solely on any one solver. However, being manually constructed, the creation of good features is an arduous task requiring a great deal of knowledge of the problem domain of interest. To alleviate this costly yet crucial step, this paper presents an automated methodology for producing an informative set of features utilizing a deep neural network. We show that the presented approach completely automates the algorithm selection pipeline and is able to achieve significantly better performance than a single best solver across multiple problem domains.

Stable matching problems have several practical applications. If preference lists are truncated and contain ties, finding a stable matching with maximal size is computationally difficult. We address this problem using a local search technique, based on Adaptive Search and present experimental evidence that this approach is much more efficient than state-of-the-art exact and approximate methods. Moreover, parallel versions (particularly versions with communication) improve performance so much that very large and hard instances can be solved quickly.

Scale-out programs run on multiple processes in a cluster. In scale-out systems, processes can fail. Computations using traditional libraries such as MPI fail when any component process fails. The advent of Map Reduce, Resilient Data Sets and MillWheel has shown dramatic improvements in productivity are possible when a high-level programming framework handles scale-out and resilience automatically.

X10 is a high-performance, high-productivity programming language aimed at large-scale distributed and shared-memory parallel applications. It is based on the Asynchronous Partitioned Global Address Space (APGAS) programming model, supporting the same fine-grained concurrency mechanisms within and across shared-memory nodes.

This paper addresses the static analysis of an important class of X10 programs, namely those with finish/async parallelism, and affine loops and array reference structure as in the polyhedral model. For such programs our analysis can certify whenever a program is deterministic or flags races.

Modern object-oriented languages such as X10 require a rich framework for types capable of expressing both value-dependency and genericity, and supporting pluggable, domain-specific extensions. In earlier work, we presented a framework for constrained types in object-oriented languages, parametrized by an underlying constraint system. Types are viewed as formulas C{c} where C is the name of a class or an interface and c is a constraint on the immutable instance state (the properties) of C. Constraint systems are a very expressive framework for partial information. Many (value-)dependent type systems for object-oriented languages can be viewed as constrained types.

Main Memory Map Reduce (M3R) is a new implementation of the Hadoop Map Reduce (HMR) API targeted at online analytics on high mean-time-to-failure clusters. It does not support resilience, and supports only those workloads which can fit into cluster memory. In return, it can run HMR jobs unchanged -- including jobs produced by compilers for higher-level languages such as Pig, Jaql, and SystemML and interactive front-ends like IBM BigSheets -- while providing significantly better performance than the Hadoop engine on several workloads (e.g. 45x on some input sizes for sparse matrix vector multiply). M3R also supports extensions to the HMR API which can enable Map Reduce jobs to run faster on the M3R engine, while not affecting their performance under the Hadoop engine.

On shared-memory systems, Cilk-style work-stealing has been used to effectively parallelize irregular task-graph based applications such as Unbalanced Tree Search (UTS). There are two main difficulties in extending this approach to distributed memory. In the shared memory approach, thieves (nodes without work) constantly attempt to asynchronously steal work from randomly chosen victims until they find work. In distributed memory, thieves cannot autonomously steal work from a victim without disrupting its execution. When work is sparse, this results in performance degradation. In essence, a direct extension of traditional work-stealing to distributed memory violates the work-first principle underlying work-stealing. Further, thieves spend useless CPU cycles attacking victims that have no work, resulting in system inefficiencies in multi-programmed contexts. Second, it is non-trivial to detect active distributed termination (detect that programs at all nodes are looking for work, hence there is no work). This problem is well-studied and requires careful design for good performance. Unfortunately, in most existing languages/frameworks, application developers are forced to implement their own distributed termination detection.

Due to the memory intensive workload and the erratic access pattern, irregular graph algorithms are notoriously hard to implement and optimize for high performance on distributed-memory systems. Although the PGAS paradigm proposed recently improves ease of programming, no high performance PGAS implementation of large-scale graph analysis is known. We present the first fast PGAS implementation of graph algorithms for the connected components and minimum spanning tree problems. By improving memory access locality, compared with the naive implementation, our implementation exhibits much better communication efficiency and cache performance on a cluster of SMPs. With additional algorithmic and PGASspecific optimizations, our implementation achieves significant speedups over both the best sequential implementation and the best single-node SMP implementation for large, sparse graphs with more than a billion edges.

The X10 programming language is organized around the notion of places (an encapsulation of data and activities operating on the data), partitioned global address space (PGAS), and asynchronous computation and communication.

Load balancing is a technique which allows efficient parallelization of irregular workloads, and a key component of many applications and parallelizing runtimes. Work-stealing is a popular technique for implementing load balancing, where each parallel thread maintains its own work set of items and occasionally steals items from the sets of other threads.

Solving large, irregular graph problems efficiently is challenging. Current software systems and commodity multiprocessors do not support fine-grained, irregular parallelism well. We present XWS, the X10 Work Stealing framework, an open-source runtime for the parallel programming language X10 and a library to be used directly by application writers. XWS extends the Cilk work-stealing framework with several features necessary to efficiently implement graph algorithms, viz., support for improperly nested procedures, global termination detection, and phased computation. We also present a strategy to adaptively control the granularity of parallel tasks in the work-stealing scheme, depending on the instantaneous size of the work queue. We compare the performance of the XWS implementations of spanning tree algorithms with that of the hand-written C and Cilk implementations using various graph inputs. We show that XWS programs (written in Java) scale and exhibit comparable or better performance.

X10 is a modern object-oriented language designed for productivity and performance in concurrent and distributed systems. In this setting, dependent types offer significant opportunities for detecting design errors statically, documenting design decisions, eliminating costly run-time checks (e.g., for array bounds, null values), and improving the quality of generated code.

In languages with distributed heap data structures, the type system typically conveys only coarse locality information: whether a reference is local or possibly remote. Often, of interest to the optimizing compiler or the user is a more fine-grain information, such as whether two remote references point to objects in the same partition of the distributed heap.

Performance of stencil computations can be significantly improved through smart implementations that improve memory locality, computation reuse, or parallelize the computation. Unfortunately, efficient implementations are hard to obtain because they often involve non-traditional transformations, which means that they cannot be produced by optimizing the reference stencil with a compiler. In fact, many stencils are produced by code generators that were tediously handcrafted.

A memory model for a concurrent imperative programming language specifies which writes to shared variables may be seen by reads performed by other threads. We present a simple mathematical framework for relaxed memory models for programming languages. To instantiate this framework for a specific language, the designer must choose the notion of atomic steps supported by the language (e.g. 32-bit reads and writes) and specify how a composite step may be broken into a sequence of atomic steps (the decomposition rule). This rule determines which sequence of intermediate writes (if any) are visible to concurrent reads by other threads. Different choices of the rule lead to models which permit a read to return any value if there is a concurrent write (race), or models which satisfy a "No Thin Air Read"property. The former is suitable for languages such as C++(programs with races have undefined behavior), and the latter for Java. Other intermediate models are possible, useful and interesting.

Two major trends are converging to reshape the landscape of concurrent object-oriented programming languages. First, trends in modern architectures (multi-core, accelerators, high performance clusters such as Blue Gene) are making concurrency and distribution inescapable for large classes of OO programmers. Second, experience with first-generation concurrent OO languages (e.g. Java threads and synchronization) have revealed several drawbacks of unstructured threads with lock-based synchronization.

Sketching is a software synthesis approach where the programmer develops a partial implementation - a sketch - and a separate specification of the desired functionality. The synthesizer then completes the sketch to behave like the specification. The correctness of the synthesized implementation is guaranteed by the compiler, which allows, among other benefits, rapid development of highly tuned implementations without the fear of introducing bugs.We develop SKETCH, a language for finite programs with linguistic support for sketching. Finite programs include many highperformance kernels, including cryptocodes. In contrast to prior synthesizers, which had to be equipped with domain-specific rules, SKETCH completes sketches by means of a combinatorial search based on generalized boolean satisfiability. Consequently, our combinatorial synthesizer is complete for the class of finite programs: it is guaranteed to complete any sketch in theory, and in practice has scaled to realistic programming problems.Freed from domain rules, we can now write sketches as simpleto-understand partial programs, which are regular programs in which difficult code fragments are replaced with holes to be filled by the synthesizer. Holes may stand for index expressions, lookup tables, or bitmasks, but the programmer can easily define new kinds of holes using a single versatile synthesis operator.We have used SKETCH to synthesize an efficient implementation of the AES cipher standard. The synthesizer produces the most complex part of the implementation and runs in about an hour.

We present an expressiveness study of linearity and persistence of processes. We choose the ð-calculus, one of the main representatives of process calculi, as a framework to conduct our study. We consider four fragments of the ð-calculus. Each one singles out a natural source of linearity/ persistence also present in other frameworks such as Concurrent Constraint Programming (CCP), Linear CCP, and several calculi for security. The study is presented by providing (or proving the non-existence of) encodings among the fragments, a processes-as-formulae interpretation and a reduction from Minsky machines.

It is now well established that the device scaling predicted by Moore's Law is no longer a viable option for increasing the clock frequency of future uniprocessor systems at the rate that had been sustained during the last two decades. As a result, future systems are rapidly moving from uniprocessor to multiprocessor configurations, so as to use parallelism instead of frequency scaling as the foundation for increased compute capacity. The dominant emerging multiprocessor structure for the future is a Non-Uniform Cluster Computing (NUCC) system with nodes that are built out of multi-core SMP chips with non-uniform memory hierarchies, and interconnected in horizontally scalable cluster configurations such as blade servers. Unlike previous generations of hardware evolution, this shift will have a major impact on existing software. Current OO language facilities for concurrent and distributed programming are inadequate for addressing the needs of NUCC systems because they do not support the notions of non-uniform data access within a node, or of tight coupling of distributed nodes.We have designed a modern object-oriented programming language, X10, for high performance, high productivity programming of NUCC systems. A member of the partitioned global address space family of languages, X10 highlights the explicit reification of locality in the form of places}; lightweight activities embodied in async, future, foreach, and ateach constructs; a construct for termination detection (finish); the use of lock-free synchronization (atomic blocks); and the manipulation of cluster-wide global data structures. We present an overview of the X10 programming model and language, experience with our reference implementation, and results from some initial productivity comparisons between the X10 and Java™ languages.

This paper focuses on policy languages for (role-based) access control [14, 32], especially in their modern incarnations in the form of trust-management systems [9] and usage control [30, 31]. Any (declarative) approach to access control and trust management has to address the following issues:

Protection systems have provided the formal basis for the study of security and access mechanisms in computer systems for many years and, more recently, in the context of trust management. The main objective in the design and analysis of such systems is to express policies that prescribe how objects interact and share information with each other, and verify that undesirable actions cannot take place. The latter problem is referred to as the safety or accessibility problem, since it is often phrased in the form "Can object p gain (illegal) access to object q by a series of legal moves (as prescribed by a policy)?". Much work has gone into designing protection systems that have significant expressive power and effective procedures for verifying accessibility. In this paper, we study one such general protectio...

This article describes our use of competitive analysis and the on-line model of computation in a product development setting; specifically, we use competitive analysis to evaluate on-line scheduling strategies for controlling a new generation of networked reprographic machines (combination printer-copier-fax machines servicing a network) currently being developed by companies such as Xerox Corporation. We construct an abstract machine model, the multipass assembly line, which not only models networked reprographic machines but also models several common manufacturing environments such as a robotic assembly line or a mixed product assembly line. We consider on-line algorithms with finite lookahead because these machines typically have limited knowledge of the future. We first prove some lower bounds on the performance of any on-line algorithm with finite lookahead. We then show that simple greedy algorithms achieve competitive ratios that are close to these general lower bounds. In particular, we show that lookahead improves the competitive ratio of these simple greedy algorithms from approximately 2 (with no lookahead) to being arbitrarily close to 1 (for large lookahead). This implies these simple greedy algorithms are realistic candidates for field use in future reprographic products.

We extend cc to allow the specification of a discrete probability distribution for random variables. We demonstrate the expressiveness of pcc by synthesizing combinators for default reasoning. We extend pcc uniformly over time, to get a synchronous reactive probabilistic programming language, Timed pcc. We describe operational and denotational models for pcc (and Timed pcc). The key feature of the denotational model(s) is that parallel composition is essentially set intersection. We show that the denotational model ofpcc (resp. Timed pcc) is conservative over cc (resp. tcc). We also show that the denotational models are fully abstract for an operational semantics that records probability information.

We extend the model of [SJG94b] to express strong time-outs (and pre-emption): if an event A does not happen through time t, cause event B to happen at time t. Such constructs arise naturally in practice (e.g. in modeling transistors) and are supported in languages such as ESTEREL (through instantaneous watchdogs) and LUSTRE (through the “current” operator).

We develop a model for timed, reactive computation by extending the asynchronous, untimed concurrent constraint programming model in a simple and uniform way. In the spirit of process algebras, we develop some combinators expressible in this model, and reconcile their operational, logical and denotational character. We show how programs may be compiled into finite-state machines with loop-free computations at each state, thus guaranteeing bounded response time.>

A general definition of constraint systems utilizing Gentzen-style sequents is given. Constraint systems can be regarded as enriching the propositional Scott information systems with minimal first-order structure: the notion of variables, existential quantification, and substitution. Approximate maps that are generic in all but finitely many variables are taken as morphisms. It is shown that the resulting structure forms a category (called ConstSys). Furthermore, the structure of Scott information systems lifts smoothly to the first-order setting. In particular, it is shown that the category is Cartesian-closed, and other usual functors over Scott information systems (lifting, sums, Smyth power-domain) are also definable and recursive domain equations involving these functors can be solved.>

Concurrent constraint programming [Sar89 ,SR90] is a simple and powerful model of concurrent computation based on the notions of store-as-constraint and process as information combinators in the language, can be used for proving liveness properties of programs, and is fully abstract with respect to the obvious notion of observation.

This paper presents a new and very rich class of (con-current) programming languages, based on the notion of comput.ing with parhal information, and the con-commitant notions of consistency and entailment. ’ In this framework, computation emerges from the inter-action of concurrently executing agents that communi-cate by placing, checking and instantiating constraints on shared variables. Such a view of computation is in-teresting in the context of programming languages be-cause of the ability to represent and manipulate partial information about the domain of discourse, in the con-text of concurrency because of the use of constraints for communication and control, and in the context of AI because of the availability of simple yet powerful mechanisms for controlling inference, and the promise that very rich representational/programming languages, sharing the same set of abstract properties, may be pos-sible. To reflect this view of computation, [Sar89] develops the cc family of languages. We present here one mem-ber of the family, CC(.L,+) (pronounced “cc with Ask and Choose”) which provides the basic operations of blocking Ask and atomic Tell and an algebra of be-haviors closed under prefixing, indeterministic choice, interleaving, and hiding, and provides a mutual recur-sion operator. cc(.L,-t) is (intentionally!) very similar to Milner’s CCS, but for the radically different under-lying concept of communication, which, in fact, pro-’ The class is founded on the notion of “constraint logic pro-gramming ” [JL87,Mah87], fundamentally generalizes concurrent logic programming, and is the subject of the first author’s disser-tation [Sar89], on which this paper is substantially based.

A significant motivation for programming language research is to find good abstractions and conceptual frameworks that enable us to understand and re* son about, certain kinds of complex computational phenomena in a simple way.In this paper we show that the specification of programs for the detection of stable properties of networks of communicating processes is facilitated -almost trivialized -in the framework of concurrent logic programming languages.We present the embedded short-circuit pr* gramming technique for detecting stable properties of networks, and illustrate its utility by providing a simple algorithm for distributed termination detection.We show that, the runtime behavior of a concurrent logic program incorporating this technique (for diffusing computations) is similar to the "DSA" scheme described in [7] for maintaining distributed counters.We modify the technique for repeated detection of quiescence for phased computations such as discrete simulations.We show that the abstraction can be mit nipulated without reference to its implementation by presenting a simple solution to the distributed knotdetection problem [IS].Finally we show that, under certain conditions, a simple extension allows repeated (live) snapshots [3] of the state of the computation to be taken almost trivially, thus providing another technique for detecting stable properties.

In this paper we present some of the control constructs of the language CP, which is based on a concurrent interpretation of Horn logic programming. We present a formal structural operational semantics and relate the meaning of programs in this language to the underlying (pure) Horn clause axioms.