bluuebunny/crossref_metadata_2025 huggingface dataset:
Application of metalloporphyrins as new catalysts for the efficient, mild and regioselective synthesis of quinoxaline derivatives
Authors: Mohammadi Khosro , Hasaninejad Alireza , Niad Mahmud , Najmi Mojtaba
Published: February 2011

A simple, highly efficient and green procedure for the condensation of aryl and alkyl 1,2-diamines with α-diketones in the presence of catalytic amounts of metalloporphyrins at room temperature is described. Using this method, quinoxaline derivatives as biologically interesting compounds are produced in high to excellent yields and short reaction times. In this report, the effects of central metal in porphyrin core and substituents on tetraphenylporphyrin skeleton have been studied.
Synthesis of a diimidazolylporphyrin pincer palladium complex
Authors: Yamamoto Jun , Shimizu Tomohiro , Yamaguchi Shigeru , Aratani Naoki , Shinokubo Hiroshi , Osuka Atsuhiro
Published: February 2011

A novel NCN type palladium pincer complex based on the porphyrin backbone was synthesized. The palladium atom bound to the meso-carbon of the porphyrin core was effectively supported by two imidazolyl groups. The product was characterized by spectroscopic and X-ray diffraction analysis. The structure of the porphyrinic macrocycle was revealed to be highly distorted by the coordination of the outer palladium center. The degree of deformation was found to be even larger than the analogous palladium pincer complexes in which pyridine groups were employed as the supporting ligands. The complex exhibited high catalytic activity in the Mizoroki-Heck reaction of iodobenzene with butyl acrylate with 0.005% of the catalyst loading.
MODEL VALIDATION BASED ON ENSEMBLE EMPIRICAL MODE DECOMPOSITION
Authors: CHANG YU-MEI , WU ZHAOHUA , CHANG JULIUS , HUANG NORDEN E.
Published: February 2011

We proposed a new model validation method through ensemble empirical mode decomposition (EEMD) and scale separate correlation. EEMD is used to analyze the nonlinear and nonstationary ozone concentration data and the data simulated from the Taiwan Air Quality Model (TAQM). Our approach consists of shifting an ensemble of white noise-added signal and treats the mean as the final true intrinsic mode functions (IMFs). It provides detailed comparisons of observed and simulated data in various temporal scales. The ozone concentration of Wan-Li station in Taiwan is used to illustrate the power of this new approach. Our results show that, at an urban station, the ozone concentration fluctuation has various cycles that include semi-diurnal, diurnal, and weekly time scales. These results serve to demonstrate the anthropogenic origin of the local pollutant and long-range transport effects were all important. The validation tests indicate that the model used here performs well to simulate phenomena of all temporal scales.
ON THE FILTERING PROPERTIES OF THE EMPIRICAL MODE DECOMPOSITION
Authors: WU ZHAOHUA , HUANG NORDEN E.
Published: February 2011

The empirical mode decomposition (EMD) based time-frequency analysis has been used in many scientific and engineering fields. The mathematical expression of EMD in the time-frequency-energy domain appears to be a generalization of the Fourier transform (FT), which leads to the speculation that the latter may be a special case of the former. On the other hand, the EMD is also known to behave like a dyadic filter bank when used to decompose white noise. These two observations seem to contradict each other.

In this paper, we study the filtering properties of EMD, as its sifting number changes. Based on numerical results of the decompositions using EMD of a delta function and white noise, we conjecture that, as the (pre-assigned and fixed) sifting number is changed from a small number to infinity, the EMD corresponds to filter banks with a filtering ratio that changes accordingly from 2 (dyadic) to 1; the filter window does not narrow accordingly, as the sifting number increases. It is also demonstrated that the components of a delta function resulted from EMD with any prescribed sifting number can be rescaled to a single shape, a result similar to that from wavelet decomposition, although the shape changes, as the sifting number changes. These results will lead to further understandings of the relations of EMD to wavelet decomposition and FT.
WAVELENGTH PROBING OPTICAL COHERENCE TOMOGRAPHY
Authors: CHANG SHOUDE , MAO YOUXIN
Published: February 2011

In swept-source optical coherence tomography (SSOCT), the swept-source stimulates system by a series of wavelengths in time sequence; a photo detector then collects all reflected/backscattered light from testing sample as the components of Fourier series. Due to the nature of the SSOCT, the processing in spectral domain can merge multiple swept-sources with different central wavelengths, which greatly increases the resolution of the OCT imaging. In the wavelength probing OCT, a standard broadband SSOCT system is used to extract the internal structure of the sample, and another narrow band light can be used to probe the spectral feature of the sample at the probing wavelength.
OPTICAL PROPERTIES OF SKIN, SUBCUTANEOUS, AND MUSCLE TISSUES: A REVIEW
Authors: BASHKATOV ALEXEY N. , GENINA ELINA A. , TUCHIN VALERY V.
Published: February 2011

The development of optical methods in modern medicine in the areas of diagnostics, therapy, and surgery has stimulated the investigation of optical properties of various biological tissues, since the efficacy of laser treatment depends on the photon propagation and fluence rate distribution within irradiated tissues. In this work, an overview of published absorption and scattering properties of skin and subcutaneous tissues measured in wide wavelength range is presented. Basic principles of measurements of the tissue optical properties and techniques used for processing of the measured data are outlined.
A framework for cross-layer optimization of video streaming in wireless networks
Authors: Hsu Cheng-Hsin , Hefeeda Mohamed
Published: February 2011

We present a general framework for optimizing the quality of video streaming in wireless networks that are composed of multiple wireless stations. The framework is general because: (i) it can be applied to different wireless networks, such as IEEE 802.11e WLAN and IEEE 802.16 WiMAX, (ii) it can employ different objective functions for the optimization, and (iii) it can adopt various models for the wireless channel, the link layer, and the distortion of the video streams in the application layer. The optimization framework controls parameters in different layers to optimally allocate the wireless network resources among all stations. More specifically, we address this video optimization problem in two steps. First, we formulate an abstract optimization problem for video streaming in wireless networks in general. This formulation exposes the important interaction between parameters belonging to different layers in the network stack. Then, we instantiate and solve the general problem for the recent IEEE 802.11e WLANs, which support prioritized traffic classes. We show how the calculated optimal solutions can efficiently be implemented in the distributed mode of the IEEE 802.11e standard. We evaluate our proposed solution using extensive simulations in the OPNET simulator, which captures most features of realistic wireless networks. In addition, to show the practicality of our solution, we have implemented it in the driver of an off-the-shelf wireless adapter that complies with the IEEE 802.11e standard. Our experimental and simulation results show that significant quality improvement in video streams can be achieved using our solution, without incurring any significant communication or computational overhead. We also explain how the general video optimization problem can be applied to other wireless networks, in particular, to the IEEE 802.16 WiMAX networks, which are becoming very popular.
One step forward
Authors: Viana Aline Carneiro , Maag Stephane , Zaidi Fatiha
Published: February 2011

Wireless self-organizing networks (WSONs) have attracted considerable attention from the network research community; however, the key for their success is the rigorous validation of the properties of the network protocols. Applications of risk or those demanding precision (like alert-based systems) require a rigorous and reliable validation of deployed network protocols. While the main goal is to ensure the reliability of the protocols, validation techniques also allow the establishment of their correctness regarding the related protocols' requirements. Nevertheless, even if different communities have carried out intensive research activities on the validation domain, WSONs still raise new issues for and challenging constraints to these communities. We thus, advocate the use of complementary techniques coming from different research communities to efficiently address the validation of WSON protocols. The goal of this tutorial is to present a comprehensive review of the literature on protocol engineering techniques and to discuss difficulties imposed by the characteristics of WSONs on the protocol engineering community. Following the formal and nonformal classification of techniques, we provide a discussion about components and similarities of existing protocol validation approaches. We also investigate how to take advantage of such similarities to obtain complementary techniques and outline new challenges.
A survey of DHT security techniques
Authors: Urdaneta Guido , Pierre Guillaume , Steen Maarten Van
Published: February 2011

Peer-to-peer networks based on distributed hash tables (DHTs) have received considerable attention ever since their introduction in 2001. Unfortunately, DHT-based systems have been shown to be notoriously difficult to protect against security attacks. Various reports have been published that discuss or classify general security issues, but so far a comprehensive survey describing the various proposed defenses has been lacking. In this article, we present an overview of techniques reported in the literature for making DHT-based systems resistant to the three most important attacks that can be launched by malicious nodes participating in the DHT: (1) the Sybil attack, (2) the Eclipse attack, and (3) routing and storage attacks. We review the advantages and disadvantages of the proposed solutions and, in doing so, confirm how difficult it is to secure DHT-based systems in an adversarial environment.
Auctions and bidding
Authors: Parsons Simon , Rodriguez-Aguilar Juan A. , Klein Mark
Published: February 2011

There is a veritable menagerie of auctions—single-dimensional, multi-dimensional, single-sided, double-sided, first-price, second-price, English, Dutch, Japanese, sealed-bid—and these have been extensively discussed and analyzed in the economics literature. The main purpose of this article is to survey this literature from a computer science perspective, primarily from the viewpoint of computer scientists who are interested in learning about auction theory, and to provide pointers into the economics literature for those who want a deeper technical understanding. In addition, since auctions are an increasingly important topic in computer science, we also look at work on auctions from the computer science literature. Overall, our aim is to identifying what both these bodies of work these tell us about creating electronic auctions.
ICPS offers major research venue
Authors: Rodden Tom
Published: February 2011

The ACM International Conference Proceedings Series (ICPS) has recently being relaunched as a publication venue for research activities.
Matters of design
Authors: Hong Jason
Published: February 2011

http://cacm.acm.org/blogs/blog-cacm

The
Communications
Web site, http://cacm.acm.org, features more than a dozen bloggers in the BLOG@CACM community. In each issue of
Communications
, we'll publish selected posts or excerpts.

twitter

Follow us on Twitter at http://twitter.com/blogCACM

Jason Hong considers how software companies could effectively incorporate first-rate design into their products.
Information theory after Shannon
Authors: Savage Neil
Published: February 2011

Purdue University's Science of Information Center seeks new principles to answer the question 'What is information?'
Chipping away at greenhouse gases
Authors: Goth Gregory
Published: February 2011

Power-saving processor algorithms have the potential to create significant energy and cost savings.
ACM Fellows honored
Authors: CACM Staff
Published: February 2011

Forty-one men and women are inducted as 2010 ACM Fellows.
Maurice Wilkes
Authors: Hoffmann Leah
Published: February 2011

Computer science has lost not only a great scientist, but an important link to the electronic computing revolution that took place in the 1940s.
Forest for the trees
Authors: Neville-Neil George V.
Published: February 2011

Keeping your source trees in order.
A plea from sysadmins to software vendors
Authors: Limoncelli Thomas A.
Published: February 2011

What can software vendors do to make the lives of system administrators a little easier?
System administration soft skills
Authors: Lear Christina
Published: February 2011

How can system administrators reduce stress and conflict in the workplace?
The gentle art of levitation
Authors: Chapman James , Dagand Pierre-Évariste , McBride Conor , Morris Peter
Published: February 2011

We present a closed dependent type theory whose inductive types are given not by a scheme for generative declarations, but by encoding in auniverse. Each inductive datatype arises by interpreting itsdescription- a first-class value in a datatype of descriptions. Moreover, the latter itself has a description. Datatype-generic programming thus becomes ordinary programming. We show some of the resulting generic operations and deploy them in particular, useful ways on the datatype of datatype descriptions itself. Simulations in existing systems suggest that this apparently self-supporting setup is achievable without paradox or infinite regress.
Functional pearl
Authors: Vytiniotis Dimitrios , Kennedy Andrew J.
Published: February 2011

We show how the binary encoding and decoding of typed data and typed programs can be understood, programmed, and verified with the help of question-answer games. The encoding of a value is determined by the yes/no answers to a sequence of questions about that value; conversely, decoding is the interpretation of binary data as answers to the same question scheme.

We introduce a general framework for writing and verifying game-based codecs. We present games for structured, recursive, polymorphic, and indexed types, building up to a representation of well-typed terms in the simply-typed λ-calculus. The framework makes novel use of isomorphisms between types in the definition of games. The definition of isomorphisms together with additional simple properties make it easy to prove that codecs derived from games never encode two distinct values using the same code, never decode two codes to the same value, and interpret any bit sequence as a valid code for a value or as a prefix of a valid code.
ReCaml
Authors: Buisson Jérémy , Dagnat Fabien
Published: February 2011

To fix bugs or to enhance a software system without service disruption, one has to update it dynamically during execution. Most prior dynamic software updating techniques require that the code to be changed is not running at the time of the update. However, this restriction precludes any change to the outermost loops of servers, OS scheduling loops and recursive functions. Permitting a dynamic update to more generally manipulate the program's execution state, including the runtime stack, alleviates this restriction but increases the likelihood of type errors. In this paper we present ReCaml, a language for writing dynamic updates to running programs that views execution state as a delimited continuation. ReCaml includes a novel feature for introspecting continuations called match_cont which is sufficiently powerful to implement a variety of updating policies. We have formalized the core of ReCaml and proved it sound (using the Coq proof assistant), thus ensuring that state-manipulating updates preserve type-safe execution of the updated program. We have implemented ReCaml as an extension to the Caml bytecode interpreter and used it for several examples.
Lolliproc
Authors: Mazurak Karl , Zdancewic Steve
Published: February 2011

While many type systems based on the intuitionistic fragment of linear logic have been proposed, applications in programming languages of the full power of linear logic - including double-negation elimination - have remained elusive. Meanwhile, linearity has been used in many type systems for concurrent programs - e.g., session types - which suggests applicability to the problems of concurrent programming, but the ways in which linearity has interacted with concurrency primitives in lambda calculi have remained somewhat ad-hoc. In this paper we connect classical linear logic and concurrent functional programming in the language Lolliproc, which provides simple primitives for concurrency that have a direct logical interpretation and that combine to provide the functionality of session types. Lolliproc features a simple process calculus "under the hood" but hides the machinery of processes from programmers. We illustrate Lolliproc by example and prove soundness, strong normalization, and confluence results, which, among other things, guarantees freedom from deadlocks and race conditions.
Abstracting abstract machines
Authors: Van Horn David , Might Matthew
Published: February 2011

We describe a derivational approach to abstract interpretation that yields novel and transparently sound static analyses when applied to well-established abstract machines. To demonstrate the technique and support our claim, we transform the CEK machine of Felleisen and Friedman, a lazy variant of Krivine's machine, and the stack-inspecting CM machine of Clements and Felleisen into abstract interpretations of themselves. The resulting analyses bound temporal ordering of program events; predict return-flow and stack-inspection behavior; and approximate the flow and evaluation of by-need parameters. For all of these machines, we find that a series of well-known concrete machine refactorings, plus a technique we call store-allocated continuations, leads to machines that abstract into static analyses simply by bounding their stores. We demonstrate that the technique scales up uniformly to allow static analysis of realistic language features, including tail calls, conditionals, side effects, exceptions, first-class continuations, and even garbage collection.
Polyvariant flow analysis with higher-ranked polymorphic types and higher-order effect operators
Authors: Holdermans Stefan , Hage Jurriaan
Published: February 2011

We present a type and effect system for flow analysis that makes essential use of higher-ranked polymorphism. We show that, for higher-order functions, the expressiveness of higher-ranked types enables us to improve on the precision of conventional let-polymorphic analyses. Modularity and decidability of the analysis are guaranteed by making the analysis of each program parametric in the analyses of its inputs; in particular, we have that higher-order functions give rise to higher-order operations on effects. As flow typing is archetypical to a whole class of type and effect systems, our approach can be used to boost the precision of a wide range of type-based program analyses for higher-order languages.
The reduceron reconfigured
Authors: Naylor Matthew , Runciman Colin
Published: February 2011

The leading implementations of graph reduction all target conventional processors designed for low-level imperative execution. In this paper, we present a processor specially designed to perform graph-reduction. Our processor -- the Reduceron -- is implemented using off-the-shelf reconfigurable hardware. We highlight the low-level parallelism present in sequential graph reduction, and show how parallel memories and dynamic analyses are used in the Reduceron to achieve an average reduction rate of 0.55 function applications per clock-cycle.
Lazy tree splitting
Authors: Bergstrom Lars , Rainey Mike , Reppy John , Shaw Adam , Fluet Matthew
Published: February 2011

Nested data-parallelism (NDP) is a declarative style for programming irregular parallel applications. NDP languages provide language features favoring the NDP style, efficient compilation of NDP programs, and various common NDP operations like parallel maps, filters, and sum-like reductions. In this paper, we describe the implementation of NDP in Parallel ML (PML), part of the Manticore project. Managing the parallel decomposition of work is one of the main challenges of implementing NDP. If the decomposition creates too many small chunks of work, performance will be eroded by too much parallel overhead. If, on the other hand, there are too few large chunks of work, there will be too much sequential processing and processors will sit idle.

Recently the technique of Lazy Binary Splitting was proposed for dynamic parallel decomposition of work on flat arrays, with promising results. We adapt Lazy Binary Splitting to parallel processing of binary trees, which we use to represent parallel arrays in PML. We call our technique
Lazy Tree Splitting
(LTS). One of its main advantages is its performance robustness: per-program tuning is not required to achieve good performance across varying platforms. We describe LTS-based implementations of standard NDP operations, and we present experimental data demonstrating the scalability of LTS across a range of benchmarks.
Semantic subtyping with an SMT solver
Authors: Bierman Gavin M. , Gordon Andrew D. , Hriţcu Cătălin , Langworthy David
Published: February 2011

We study a first-order functional language with the novel combination of the ideas of refinement type (the subset of a type to satisfy a Boolean expression) and type-test (a Boolean expression testing whether a value belongs to a type). Our core calculus can express a rich variety of typing idioms; for example, intersection, union, negation, singleton, nullable, variant, and algebraic types are all derivable. We formulate a semantics in which expressions denote terms, and types are interpreted as first-order logic formulas. Subtyping is defined as valid implication between the semantics of types. The formulas are interpreted in a specific model that we axiomatize using standard first-order theories. On this basis, we present a novel type-checking algorithm able to eliminate many dynamic tests and to detect many errors statically. The key idea is to rely on an SMT solver to compute subtyping efficiently. Moreover, interpreting types as formulas allows us to call the SMT solver at run-time to compute instances of types.
TeachScheme!
Authors: Felleisen Matthias
Published: February 2011

In 1995, my team and I decided to create an outreach project that would use our research on functional programming to change the K-12 computer science curriculum. We had two different goals in mind. On the one hand, our curriculum should rely on mathematics to teach programming, and it d exploit programming to teach mathematics. All students - not just those who major in computer science - should benefit. On the other hand, our course should demonstrate that introductory programming can focus on program design, not just a specific syntax. We also wished to create a smooth path from a design-oriented introductory course all the way to courses on large software projects.

My talk presents a checkpoint of our project, starting with our major scientific goal, a comprehensive theory of program design. Our work on this theory progresses through the development of program design courses for all age groups. At this point, we offer curricular materials for middle schools, high schools, three college-level freshman courses, and a junior-level course on constructing large components. We regularly use these materials to train K-12 teachers, after-school volunteers, and college faculty; thus far, we have reached hundreds of instructors, who in turn have dealt with thousands of students in their classrooms.
The impact of higher-order state and control effects on local relational reasoning
Authors: Dreyer Derek , Neis Georg , Birkedal Lars
Published: February 2011

Reasoning about program equivalence is one of the oldest problems in semantics. In recent years, useful techniques have been developed, based on bisimulations and logical relations, for reasoning about equivalence in the setting of increasingly realistic languages - languages nearly as complex as ML or Haskell. Much of the recent work in this direction has considered the interesting representation independence principles
enabled
by the use of local state, but it is also important to understand the principles that powerful features like higher-order state and control effects
disable
. This latter topic has been broached extensively within the framework of game semantics, resulting in what Abramsky dubbed the "semantic cube": fully abstract game-semantic characterizations of various axes in the design space of ML-like languages. But when it comes to reasoning about many actual examples, game semantics does not yet supply a useful technique for proving equivalences.

In this paper, we marry the aspirations of the semantic cube to the powerful proof method of
step-indexed Kripke logical relations
. Building on recent work of Ahmed, Dreyer, and Rossberg, we define the first fully abstract logical relation for an ML-like language with recursive types, abstract types, general references and call/cc. We then show how, under orthogonal restrictions to the expressive power our language - namely, the restriction to first-order state and/or the removal of call/cc - we can enhance the proving power of our possible-worlds model in correspondingly orthogonal ways, and we demonstrate this proving power on a range of interesting examples. Central to our story is the use of
state transition systems
to model the way in which properties of local state evolve over time.
A fresh look at programming with names and binders
Authors: Pouillard Nicolas , Pottier François
Published: February 2011

A wide range of computer programs, including compilers and theorem provers, manipulate data structures that involve names and binding. However, the design of programming idioms which allow performing these manipulations in a safe and natural style has, to a large extent, remained elusive.

In this paper, we present a novel approach to the problem. Our proposal can be viewed either as a programming language design or as a library: in fact, it is currently implemented within Agda. It provides a safe and expressive means of programming with names and binders. It is abstract enough to support multiple concrete implementations: we present one in nominal style and one in de Bruijn style. We use logical relations to prove that "well-typed programs do not mix names with different scope". We exhibit an adequate encoding of Pitts-style nominal terms into our system.
Experience report
Authors: Crestani Marcus , Sperber Michael
Published: February 2011

A student learning how to program learns best when the programming language and programming environment cater to her specific needs. These needs are different from the requirements of a professional programmer. Consequently, the design of teaching languages poses challenges different from the design of professional languages. Using a functional language by itself gives advantages over more popular, professional languages, but fully exploiting these advantages requires careful adaptation to the needs of the students' as-is, these languages do not support the students nearly as well as they could. This paper describes our experience adopting the didactic approach of How to Design Programs, focussing on the design process for our own set of teaching languages. We have observed students as they try to program as part of our introductory course, and used these observations to significantly improve the design of these languages. This paper describes the changes we have made, and the journey we took to get there.
Fortifying macros
Authors: Culpepper Ryan , Felleisen Matthias
Published: February 2011

Existing macro systems force programmers to make a choice between clarity of specification and robustness. If they choose clarity, they must forgo validating significant parts of the specification and thus produce low-quality language extensions. If they choose robustness, they must write in a style that mingles the implementation with the specification and therefore obscures the latter.

This paper introduces a new language for writing macros. With the new macro system, programmers naturally write robust language extensions using easy-to-understand specifications. The system translates these specifications into validators that detect misuses - including violations of context-sensitive constraints - and automatically synthesize appropriate feedback, eliminating the need for ad hoc validation code.
Functional parallel algorithms
Authors: Blelloch Guy E.
Published: February 2011

Functional programming presents several important advantages in the design, analysis and implementation of parallel algorithms:

It discourages iteration and encourages decomposition.

It supports persistence and hence easy speculation.

It encourages higher-order aggregate operations.

It is well suited for defining cost models tied to the programming language rather than the machine.

Implementations can avoid false sharing.

Implementations can use cheaper weak consistency models.

And most importantly, it supports safe deterministic parallelism.

In fact functional programming supports a level of abstraction in which parallel algorithms are often as easy to design and analyze as sequential algorithms. The recent widespread advent of parallel machines therefore presents a great opportunity for functional programming languages. However, any changes will require significant education at all levels and involvement of the functional programming community.

In this talk I will discuss an approach to designing and analyzing parallel algorithms in a strict functional and fully deterministic setting. Key ideas include a cost model defined in term of analyzing work and span, the use of divide-and-conquer and contraction, the need for arrays (immutable) to achieve asymptotic efficiency, and the power of (deterministic) randomized algorithms. These are all ideas I believe can be taught at any level.
Regular, shape-polymorphic, parallel arrays in Haskell
Authors: Keller Gabriele , Chakravarty Manuel M.T. , Leshchinskiy Roman , Peyton Jones Simon , Lippmeier Ben
Published: February 2011

We present a novel approach to regular, multi-dimensional arrays in Haskell. The main highlights of our approach are that it (1) is purely functional, (2) supports reuse through shape polymorphism, (3) avoids unnecessary intermediate structures rather than relying on subsequent loop fusion, and (4) supports transparent parallelisation.

We show how to embed two forms of shape polymorphism into Haskell's type system using type classes and type families. In particular, we discuss the generalisation of regular array transformations to arrays of higher rank, and introduce a type-safe specification of array slices.

We discuss the runtime performance of our approach for three standard array algorithms. We achieve absolute performance comparable to handwritten C code. At the same time, our implementation scales well up to 8 processor cores.
A certified framework for compiling and executing garbage-collected languages
Authors: McCreight Andrew , Chevalier Tim , Tolmach Andrew
Published: February 2011

We describe the design, implementation, and use of a machine-certified framework for correct compilation and execution of programs in garbage-collected languages. Our framework extends Leroy's Coq-certified Compcert compiler and Cminor intermediate language. We add: (i) a new intermediate language, GCminor, that includes primitives for allocating memory in a garbage-collected heap and for specifying GC roots; (ii) a precise, low-level specification for a Cminor library for garbage collection; and (iii) a proven semantics-preserving translation from GCminor to Cminor plus the GC library. GCminor neatly encapsulates the interface between mutator and collector code, while remaining simple and flexible enough to be used with a wide variety of source languages and collector styles. Front ends targeting GCminor can be implemented using any compiler technology and any desired degree of verification, including full semantics preservation, type preservation, or informal trust.

As an example application of our framework, we describe a compiler for Haskell that translates the Glasgow Haskell Compiler's Core intermediate language to GCminor. To support a simple but useful memory safety argument for this compiler, the front end uses a novel combination of type preservation and runtime checks, which is of independent interest.
Scrapping your inefficient engine
Authors: Brady Edwin C. , Hammond Kevin
Published: February 2011

Partial evaluation aims to improve the efficiency of a program by specialising it with respect to some known inputs. In this paper, we show that partial evaluation can be an effective and, unusually, easy to use technique for the efficient implementation of embedded domain-specific languages. We achieve this by exploiting dependent types and by following some simple rules in the definition of the interpreter for the domain-specific language. We present experimental evidence that partial evaluation of programs in domain-specific languages can yield efficient residual programs whose performance is competitive with their Java and C equivalents and which are also, through the use of dependent types, verifiably resource-safe. Using our technique, it follows that a verifiably correct and resource-safe program can also be an efficient program
Program verification through characteristic formulae
Authors: Charguéraud Arthur
Published: February 2011

This paper describes CFML, the first program verification tool based on characteristic formulae. Given the source code of a pure Caml program, this tool generates a logical formula that implies any valid post-condition for that program. One can then prove that the program satisfies a given specification by reasoning interactively about the characteristic formula using a proof assistant such as Coq. Our characteristic formulae improve over Honda
et al's total characteristic assertion pairs
in that they are expressible in standard higher-order logic, allowing to exploit them in practice to verify programs using existing proof assistants. Our technique has been applied to formally verify more than half of the content of Okasaki's
Purely Functional Data Structures
reference book
VeriML
Authors: Stampoulis Antonis , Shao Zhong
Published: February 2011

Modern proof assistants such as Coq and Isabelle provide high degrees of expressiveness and assurance because they support formal reasoning in higher-order logic and supply explicit machine-checkable proof objects. Unfortunately, large scale proof development in these proof assistants is still an extremely difficult and time-consuming task. One major weakness of these proof assistants is the lack of a single language where users can develop complex tactics and decision procedures using a rich programming model and in a typeful manner. This limits the scalability of the proof development process, as users avoid developing domain-specific tactics and decision procedures.

In this paper, we present VeriML - a novel language design that couples a type-safe effectful computational language with first-class support for manipulating logical terms such as propositions and proofs. The main idea behind our design is to integrate a rich logical framework - similar to the one supported by Coq - inside a computational language inspired by ML. The language design is such that the added features are orthogonal to the rest of the computational language, and also do not require significant additions to the logic language, so soundness is guaranteed. We have built a prototype implementation of VeriML including both its type-checker and an interpreter. We demonstrate the effectiveness of our design by showing a number of type-safe tactics and decision procedures written in VeriML.
Efficient modular glass box software model checking
Authors: Roberson Michael , Boyapati Chandrasekhar
Published: February 2011

Glass box software model checking incorporates novel techniques to identify similarities in the state space of a model checker and safely prune large numbers of redundant states without explicitly checking them. It is significantly more efficient than other software model checking approaches for checking certain kinds of programs and program properties.

This paper presents Pipal, a system for
modular
glass box software model checking. Extending glass box software model checking to perform modular checking is important to further improve its scalability. It is nontrivial because unlike traditional software model checkers such as Java PathFinder (JPF) and CMC, a glass box software model checker does not check every state separately---instead, it checks a large set of states together in each step. We present a solution and demonstrate Pipal's effectiveness on a variety of programs.
An experiment about static and dynamic type systems
Authors: Hanenberg Stefan
Published: February 2011

Although static type systems are an essential part in teach-ing and research in software engineering and computer science, there is hardly any knowledge about what the impact of static type systems on the development time or the resulting quality for a piece of software is. On the one hand there are authors that state that static type systems decrease an application's complexity and hence its development time (which means that the quality must be improved since developers have more time left in their projects). On the other hand there are authors that argue that static type systems increase development time (and hence decrease the code quality) since they restrict developers to express themselves in a desired way. This paper presents an empirical study with 49 subjects that studies the impact of a static type system for the development of a parser over 27 hours working time. In the experiments the existence of the static type system has neither a positive nor a negative impact on an application's development time (under the conditions of the experiment).
A domain-specific approach to architecturing error handling in pervasive computing
Authors: Mercadal Julien , Enard Quentin , Consel Charles , Loriant Nicolas
Published: February 2011

The challenging nature of error handling constantly escalates as a growing number of environments consists of networked devices and software components. In these environments, errors cover a uniquely large spectrum of situations related to each layer ranging from hardware to distributed platforms, to software components. Handling errors becomes a daunting task for programmers, whose outcome is unpredictable. Scaling up error handling requires to raise the level of abstraction beyond the code level and the try-catch construct, approaching error handling at the software architecture level.

We propose a novel approach that relies on an Architecture Description Language (ADL), which is extended with error-handling declarations. To further raise the level of abstraction, our approach revolves around a domain-specific architectural pattern commonly used in pervasive computing. Error handling is decomposed into components dedicated to platform-wide, error-recovery strategies. At the application level, descriptions of functional components include declarations dedicated to error handling.

We have implemented a compiler for an ADL extended with error-handling declarations. It produces customized programming frameworks that drive and support the programming of error handling. Our approach has been validated with a variety of applications for building automation.
An input-centric paradigm for program dynamic optimizations
Authors: Tian Kai , Jiang Yunlian , Zhang Eddy Z. , Shen Xipeng
Published: February 2011

Accurately predicting program behaviors (e.g., locality, dependency, method calling frequency) is fundamental for program optimizations and runtime adaptations. Despite decades of remarkable progress, prior studies have not systematically exploited program inputs, a deciding factor for program behaviors.

Triggered by the
strong
and
predictive
correlations between program inputs and behaviors that recent studies have uncovered, this work proposes to include program inputs into the focus of program behavior analysis, cultivating a new paradigm named input-centric program behavior analysis. This new approach consists of three components, forming a three-layer pyramid. At the base is
program input characterization
, a component for resolving the complexity in program raw inputs and the extraction of important features. In the middle is
input-behavior modeling
, a component for recognizing and modeling the correlations between characterized input features and program behaviors. These two components constitute input-centric program behavior analysis, which (ideally) is able to predict the large-scope behaviors of a program's execution as soon as the execution starts. The top layer of the pyramid is
input-centric adaptation
, which capitalizes on the novel opportunities that the first two components create to facilitate proactive adaptation for program optimizations.

By centering on program inputs, the new approach resolves a proactivity-adaptivity dilemma inherent in previous techniques. Its benefits are demonstrated through proactive dynamic optimizations and version selection, yielding significant performance improvement on a set of Java and C programs.
Composable specifications for structured shared-memory communication
Authors: Wood Benjamin P. , Sampson Adrian , Ceze Luis , Grossman Dan
Published: February 2011

In this paper we propose a communication-centric approach to specifying and checking how multithreaded programs use shared memory to perform inter-thread communication. Our approach complements past efforts for improving the safety of multithreaded programs such as race detection and atomicity checking. Unlike prior work, we focus on what pieces of code are allowed to communicate with one another, as opposed to declaring what data items are shared or what code blocks should be atomic. We develop a language that supports composable specifications at multiple levels of abstraction and that allows libraries to specify whether or not shared-memory communication is exposed to clients. The precise meaning of a specification is given with a formal semantics we present. We have developed a dynamic-analysis tool for Java that observes program execution to see if it obeys a specification. We report results for using the tool on several benchmark programs to which we added specifications, concluding that our approach matches the modular structure of multithreaded applications and that our tool is performant enough for use in development and testing.
Do I use the wrong definition?
Authors: Shi Yao , Park Soyeon , Yin Zuoning , Lu Shan , Zhou Yuanyuan , Chen Wenguang , Zheng Weimin
Published: February 2011

Software bugs, such as concurrency, memory and semantic bugs, can significantly affect system reliability. Although much effort has been made to address this problem, there are still many bugs that cannot be detected, especially concurrency bugs due to the complexity of concurrent programs. Effective approaches for detecting these common bugs are therefore highly desired.

This paper presents an invariant-based bug detection tool, DefUse, which can detect not only concurrency bugs (including the previously under-studied order violation bugs), but also memory and semantic bugs. Based on the observation that many bugs appear as violations to programmers' data flow intentions, we introduce three different types of definition-use invariants that commonly exist in both sequential and concurrent programs. We also design an algorithm to automatically extract such invariants from programs, which are then used to detect bugs. Moreover, DefUse uses various techniques to prune false positives and rank error reports.

We evaluated DefUse using
sixteen
real-world applications with twenty real-world concurrency and sequential bugs. Our results show that DefUse can effectively detect 19 of these bugs, including 2 new bugs that were never reported before, with only a few false positives. Our training sensitivity results show that, with the benefit of the pruning and ranking algorithms, DefUse is accurate even with insufficient training.
Scalable and systematic detection of buggy inconsistencies in source code
Authors: Gabel Mark , Yang Junfeng , Yu Yuan , Goldszmidt Moises , Su Zhendong
Published: February 2011

Software developers often duplicate source code to replicate functionality. This practice can hinder the maintenance of a software project: bugs may arise when two identical code segments are edited inconsistently. This paper presents DejaVu, a highly scalable system for detecting these general syntactic inconsistency bugs.

DejaVu operates in two phases. Given a target code base, a parallel /inconsistent clone analysis/ first enumerates all groups of source code fragments that are similar but not identical. Next, an extensible /buggy change analysis/ framework refines these results, separating each group of inconsistent fragments into a fine-grained set of inconsistent changes and classifying each as benign or buggy.

On a 75+ million line pre-production commercial code base, DejaVu executed in under five hours and produced a report of over 8,000 potential bugs. Our analysis of a sizable random sample suggests with high likelihood that at this report contains at least 2,000 true bugs and 1,000 code smells. These bugs draw from a diverse class of software defects and are often simple to correct: syntactic inconsistencies both indicate problems and suggest solutions.
A study of Java's non-Java memory
Authors: Ogata Kazunori , Mikurube Dai , Kawachiya Kiyokuni , Trent Scott , Onodera Tamiya
Published: February 2011

A Java application sometimes raises an out-of-memory ex-ception. This is usually because it has exhausted the Java heap. However, a Java application can raise an out-of-memory exception when it exhausts the memory used by Java that is not in the Java heap. We call this area non-Java memory. For example, an out-of-memory exception in the non-Java memory can happen when the JVM attempts to load too many classes. Although it is relatively rare to ex-haust the non-Java memory compared to exhausting the Java heap, a Java application can consume a considerable amount of non-Java memory.

This paper presents a quantitative analysis of non-Java memory. To the best of our knowledge, this is the first in-depth analysis of the non-Java memory. To do this we cre-ated a tool called Memory Analyzer for Redundant, Unused, and String Areas (MARUSA), which gathers memory statis-tics from both the OS and the Java virtual machine, break-ing down and visualizing the non-Java memory usage.

We studied the use of non-Java memory for a wide range of Java applications, including the DaCapo benchmarks and Apache DayTrader. Our study is based on the IBM J9 Java Virtual Machine for Linux. Although some of our results may be specific to this combination, we believe that most of our observations are applicable to other platforms as well.