Static type information to improve the IDE features of hybrid dynamically and statically typed languages

The flexibility offered by dynamically typed programming languages has been appropriately used to develop specific scenarios where dynamic adaptability is an important issue. This has made some existing statically typed languages gradually incorporate more dynamic features to their implementations. As a result, there are some programming languages considered hybrid dynamically and statically typed. However, these languages do not perform static type inference on a dynamically typed code, lacking those common features provided when a statically typed code is used. This lack is also present in the corresponding IDEs that, when a dynamically typed code is used, do not provide the services offered for static typing. We have customized an IDE for a hybrid language that statically infers type information of dynamically typed code. By using this type information, we show how the IDE can provide a set of appealing services that the existing approaches do not support, such as compile-time type error detection, code completion, transition from dynamically to statically typed code (and vice versa), and significant runtime performance optimizations. We have evaluated the programmer׳s performance improvement obtained with our IDE, and compared it with similar approaches.     

Union and intersection types to support both dynamic and static typing

Although static typing provides undeniable benefits for the development of applications, dynamically typed languages have become increasingly popular for specific scenarios. Since each approach offers different benefits, the StaDyn programming language has been designed to support both dynamic and static typing. This paper describes the minimal core of the StaDyn programming language. Its type system performs type reconstruction over both dynamic and static implicitly typed references. A new interpretation of union and intersection types allows statically gathering the type information of dynamic references, which improves runtime performance and robustness. The evaluation of the generated code has shown how our approach offers an important runtime performance benefit.     

Space-efficient gradual typing

Gradual type systems offer a smooth continuum between static and dynamic typing by permitting the free mixture of typed and untyped code. The runtime systems for these languages, and other languages with hybrid type checking, typically enforce function types by dynamically generating function proxies. This approach can result in unbounded growth in the number of proxies, however, which drastically impacts space efficiency and destroys tail recursion.     

Efficient virtual machine support of runtime structural reflection

Increasing trends towards adaptive, distributed, generative and pervasive software have made object-oriented dynamically typed languages become increasingly popular. These languages offer dynamic software evolution by means of reflection, facilitating the development of dynamic systems. Unfortunately, this dynamism commonly imposes a runtime performance penalty. In this paper, we describe how to extend a production JIT-compiler virtual machine to support runtime object-oriented structural reflection offered by many dynamic languages. Our approach improves runtime performance of dynamic languages running on statically typed virtual machines. At the same time, existing statically typed languages are still supported by the virtual machine.We have extended the .Net platform with runtime structural reflection adding prototype-based object-oriented semantics to the statically typed class-based model of .Net, supporting both kinds of programming languages. The assessment of runtime performance and memory consumption has revealed that a direct support of structural reflection in a production JIT-based virtual machine designed for statically typed languages provides a significant performance improvement for dynamically typed languages.     

Workload characterization of JVM languages

Originally developed with a single language in mind, the JVM is now targeted by numerous programming languages—its automatic memory management, just‐in‐time compilation, and adaptive optimizations—making it an attractive execution platform. However, the garbage collector, the just‐in‐time compiler, and other optimizations and heuristics were designed primarily with the performance of Java programs in mind. Consequently, many of the languages targeting the JVM, and especially the dynamically typed languages, are suffering from performance problems that cannot be simply solved at the JVM side. In this article, we aim to contribute to the understanding of the character of the workloads imposed on the JVM by both dynamically typed and statically typed JVM languages. To this end, we introduce a new set of dynamic metrics for workload characterization, along with an easy‐to‐use toolchain to collect the metrics. We apply the toolchain to applications written in six JVM languages (Java, Scala, Clojure, Jython, JRuby, and JavaScript) and discuss the findings. Given the recently identified importance of inlining for the performance of Scala programs, we also analyze the inlining behavior of the HotSpot JVM when executing bytecode originating from different JVM languages. As a result, we identify several traits in the non‐Java workloads that represent potential opportunities for optimization. © 2015 The Authors. Software: Practice and Experience Published by John Wiley & Sons Ltd.     

Rational Metaprogramming

Metaprogramming, using programs to manipulate other programs, is as old as programming. From self-modifying machine code in early computers to expressions involving partially applied functions in modern functional-programming languages, metaprogramming is an essential part of an advanced programmer's arsenal. Everyday metaprogramming involves on-the-fly code production. Representative examples include dynamically generated SQL statements and code created for evaluation at runtime in interpreted languages. Metaprogramming also occurs in programs that spew out HTML or XML. Although we can't classify these markup languages as code, their rich syntactic structure qualifies their generation as metaprogramming. Unfortunately, we commonly produce code on the fly by simply pasting together character strings. This means that it's difficult to verify essential properties of the generated code - such as validity, correctness, and safety - at compile time.     

Double dispatch in C++

Double dispatch is the ability to dynamically select a method not only according to the run‐time type of the receiver (single dispatch), but also according to the run‐time type of the argument. This mechanism unleashes the power of dynamic binding in object‐oriented languages, so enhancing re‐usability and separation of responsibilities. However, many mainstream languages, such as, e.g., C++ and Java, do not provide it, resorting only to single dispatch. In this paper we propose an extension of C++ (also applicable to other object‐oriented languages) that enables double dispatch as a language feature. This yields dynamic overloading and covariant specialization of methods. We define a translation from the new constructs to standard C++ and we present the preprocessor implementing this translation, called doublecpp . The translated code enjoys static type safety and implements the semantics of double dispatch by using only standard mechanisms of static overloading and dynamic binding, with minimal impact on the performance of the program. Copyright © 2006 John Wiley & Sons, Ltd.     

Efficient compilation strategy for object‐oriented languages under the closed‐world assumption

Reaching the best level of runtime performance from a high‐level, object‐oriented language is often considered challenging if not unattainable. The closed‐world assumption involves considering all of the source code of an application together at compile time. That assumption makes it possible to produce an efficient code. For instance, multiple inheritance can be implemented as efficiently as single inheritance. Our compilation strategy is the result of a prolonged project, tying together several compilation techniques: call graph analysis, dead code elimination, type flow analysis, code customization, implementation of dynamic dispatch, inlining, pointer optimization, switch optimization, objects layout, and so on. Merging all of these techniques into a global strategy appears to be quite problematic. Throughout the paper, two real‐world compilers are used as benchmarks to provide measurements for compiler writers to evaluate the applicability of our approach. Type flow analysis is a fundamental aspect of our strategy to resolve method calls. We have extended type flow analysis to deal with the content of arrays, enabling us to process additional expressions and thus making it possible to obtain a true global analysis. Typically, more than 90% of method call sites are statically resolved. Our experience indicates that the closed‐world assumption is suitable for numerous applications. Surprisingly, even library‐defined control statements from dynamic languages are perfectly processed with our strategy. The Smalltalk ifTrue:ifFalse: , whileTrue: , to:do: , and so on are, for the very first time, perfectly translated. Copyright © 2012 John Wiley & Sons, Ltd.     

一个经过证明的类型化汇编语言的类型检查器

编程语言类型系统的类型安全性可以保证程序运行时满足基本安全属性,包括控制流安全, 内存安全等.类型化编程语言都需要一个类型检查器来检查程序的良类型性,因此编程语言的具体实现是否能保证类型安全性,还依赖类型检查器的可靠性.本文给出一种类型化汇编语言,然后给出相应的类型检查器,并证明了此类型检查器的可靠性,从而保证经过类型检查的汇编程序的安全性.文本的所有工作,包括类型化汇编语言、类型检查器以及相关定理证明,均已在证明辅助工具Coq中实现.本文方法也可用于证明类型化高级语言的类型检查器的可靠性.     

Lightweight runtime checking of C programs with RTC

The C Programming Language is known for being an efficient language that can be compiled on almost any architecture and operating system. However the absence of dynamic safety checks and a relatively weak type system allows programmer oversights that are hard to spot. In this paper, we present RTC, a runtime monitoring tool that instruments unsafe code and monitors the program execution. RTC is built on top of the ROSE compiler infrastructure. RTC finds memory bugs and arithmetic overflows and underflows, and run-time type violations. Most of the instrumentations are directly added to the source file and only require a minimal runtime system. As a result, the instrumented code remains portable. In tests against known error detection benchmarks, RTC found 98% of all memory related bugs and had zero false positives. In performance tests conducted with well known algorithms, such as binary search and MD5, we determined that our tool has an average run-time overhead rate of 9.7× and memory overhead rate of 3.5×.     

A compile-time granularity analysis algorithm and its performance evaluation

A major implementation problem with implicitly parallel languages, is that small grain size can lead to execution overheads and reduced performance. We present a new granularity-analysis scheme that produces estimators, at compile time, of the relative execution weight of each procedure invocation. These estimators can be cheaply evaluated at runtime to approximate the relative task granularities, enabling intelligent scheduling decisions. Our method seeks to balance tradeoffs between analysis complexity, estimator accuracy, and runtime overhead of evaluating the estimator. To this end, rather than analyze data size or dependencies, we introduceiteration parameters to handle recursive procedures. This simplification facilitates solving the recurrence equations that describe the granularity estimators, and reduces the runtime overhead of evaluating these estimators. The algorithm is described in the context of concurrent logic programming languages, although the concepts are applicable to functional languages in general. We show, for a benchmark suite, that the method accurately estimates cost. Multiprocessor simulation results quantify the advantage of dynamically scheduling tasks with the granularity information.     

A hybrid class- and prototype-based object model to support language-neutral structural intercession

ContextDynamic languages have turned out to be suitable for developing specific applications where runtime adaptability is an important issue. Although .Net and Java platforms have gradually incorporated features to improve their support of dynamic languages, they do not provide intercession for every object or class. This limitation is mainly caused by the rigid class-based object model these platforms implement, in contrast to the flexible prototype-based model used by most dynamic languages.ObjectiveOur approach is to provide intercession for any object or class by defining a hybrid class- and prototype-based object model that efficiently incorporates structural intercession into the object model implemented by the widespread .Net and Java platforms.MethodIn a previous work, we developed and evaluated an extension of a shared-source implementation of the .Net platform. In this work, we define the formal semantics of the proposed reflective model, and modify the existing implementation to include the hybrid model. Finally, we assess its runtime performance and memory consumption, comparing it to existing approaches.ResultsOur platform shows a competitive runtime performance compared to 9 widespread systems. On average, it performs 73% and 61% better than the second fastest system for short- and long-running applications, respectively. Besides, it is the JIT-compiler approach that consumes less average memory. The proposed approach of including a hybrid object-model into the virtual machine involves a 444% performance improvement (and 65% less memory consumption) compared to the existing alternative of creating an extra software layer (the DLR). When none of the new features are used, our platform requires 12% more execution time and 13% more memory than the original .Net implementation.ConclusionOur proposed hybrid class- and prototype-based object model supports structural intercession for any object or class. It can be included in existing JIT-compiler class-based platforms to support common dynamic languages, providing competitive runtime performance and low memory consumption.     

一种新型类型化中间语言的优化实现技术

类型化中间语言是提高代码安全性的一类重要方法。然而在其实现过程中,庞大的类型信息很难被高效地表达和操作。一个未经优化的实现将会给系统带来指数级增长的开销。该文描述了一种新型的类型化中间语言的优化实现技术,并将其成功应用于Intel ORP (Open Runtime Platform)的即时编译器中。     

A scalable approach to solving dense linear algebra problems on hybrid CPU‐GPU systems

Aiming to fully exploit the computing power of all CPUs and all graphics processing units (GPUs) on hybrid CPU‐GPU systems to solve dense linear algebra problems, we design a class of heterogeneous tile algorithms to maximize the degree of parallelism, to minimize the communication volume, and to accommodate the heterogeneity between CPUs and GPUs. The new heterogeneous tile algorithms are executed upon our decentralized dynamic scheduling runtime system, which schedules a task graph dynamically and transfers data between compute nodes automatically. The runtime system uses a new distributed task assignment protocol to solve data dependencies between tasks without any coordination between processing units. By overlapping computation and communication through dynamic scheduling, we are able to attain scalable performance for the double‐precision Cholesky factorization and QR factorization. Our approach demonstrates a performance comparable to Intel MKL on shared‐memory multicore systems and better performance than both vendor (e.g., Intel MKL) and open source libraries (e.g., StarPU) in the following three environments: heterogeneous clusters with GPUs, conventional clusters without GPUs, and shared‐memory systems with multiple GPUs. Copyright © 2014 John Wiley & Sons, Ltd.     

Loadable kernel modules

Unlike monolithic kernels that must be relinked, reinstalled, and rebooted after every code change, the Linux kernel uses loadable modules to simplify and shorten development time, make dynamic configuration easier, and save kernel memory. The paper considers how new code Linux modules can be added dynamically to the kernel at runtime