820529
Combining programming with theorem proving
Applied Type System (ATS) is recently proposed as a framework for designing and formalizing (advanced) type systems in support of practical programming. In ATS, the definition of type equality involves a constraint relation, which may or may not be algorithmically decidable. To support practical programming, we adopted a design in the past that imposes certain restrictions on the syntactic form of constraints so that some effective means can be found for solving constraints automatically. Evidently, this is a rather em ad hoc design in its nature. In this design, which we claim to be both novel and practical. Instead of imposing syntactical restrictions on constraints, we provide a means for the programmer to construct proofs that attest to the validity of constraints. In particular, we are to accommodate a programming paradigm that enables the programmer to combine programming with theorem proving. Also we present some concrete examples in support of the practicality of this design.
5896784
Implementing typeful program transformations
The notion of program transformation is ubiquitous in programming language studies on interpreters, compilers, partial evaluators, etc. In order to implement a program transformation, we need to choose a representation in the meta language, that is, the programming language in which we construct programs, for representing object programs, that is, the programs in the object language on which the program transformation is to be performed. In practice, most representations chosen for typed object programs are typeless in the sense that the type of an object program cannot be reflected in the type of its representation. This is unsatisfactory as such typeless representations make it impossible to capture in the type system of the meta language various invariants in a program transformation that are related to the types of object programs. In this paper, we propose an approach to implementing program transformations that makes use of a first-order typeful program representation formed in Dependent ML (DML), where the type of an object program as well as the types of the free variables in the object program can be reflected in the type of the representation of the object program. We introduce some programming techniques needed to handle this typeful program representation, and then present an implementation of a CPS transform function where the relation between the type of an object program and that of its CPS transform is captured in the type system of DML. In a broader context, we claim to have taken a solid step along the line of research on constructing certifying compilers.
61965299
Implementing typeful program transformations
The notion of program transformation is ubiquitous in programming language studies on interpreters, compilers, partial evaluators, etc. In order to implement a program transformation, we need to choose a representation in the meta language, that is, the programming language in which we construct programs, for representing object programs, that is, the programs in the object language on which the program transformation is to be performed. In practice, most representations chosen for typed object programs are typeless in the sense that the type of an object program cannot be reflected in the type of its representation. This is unsatisfactory as such typeless representations make it impossible to capture in the type system of the meta language various invariants in a program transformation that are related to the types of object programs. In this paper, we propose an approach to implementing program transformations that makes use of a first-order typeful program representation formed in Dependent ML (DML), where the type of an object program as well as the types of the free variables in the object program can be reflected in the type of the representation of the object program. We introduce some programming techniques needed to handle this typeful program representation, and then present an implementation of a CPS transform function where the relation between the type of an object program and that of its CPS transform is captured in the type system of DML. In a broader context, we claim to have taken a solid step along the line of research on constructing certifying compilers.
41922638
Guarded recursive datatype constructors
11896625
Distributed meta-programming
Distributed meta-programming (DMP), which allows code to be generated and distributed at run-time, has already become a common practice. However, code generation currently often relies on rather ad hoc approaches that represent code as plain text, making DMP notoriously error-prone. This unfortunate situation is further exacerbated due to issues such as mobility (of code) and locality and heterogeneity (of resources), which complicate testing and debugging drastically.In this paper, we study distributed meta-programming from a type-theoretic perspective, presenting a language to facilitate the construction of programs that may generate and distribute code at run-time. The approach we take makes use of a form of typeful code representation developed in a previous study on meta-programming, and it guarantees statically that only well-typed code (according to some chosen type discipline) can be constructed at run-time and sent to proper locations for execution. We also mention a prototype implementation in support of the practicality of our approach to DMP, providing a solid proof of concept.
45241367
Meta-programming through typeful code representation
By allowing the programmer to write code that can generate code at run-time, meta-programming offers a powerful approach to program construction. For instance, meta-programming can often be employed to enhance program efficiency and facilitate the construction of generic programs. However, meta-programming, especially in an untyped setting, is notoriously error-prone. In this paper, we aim at making meta-programming less error-prone by providing a type system to facilitate the construction of correct meta-programs. We first introduce some code constructors for constructing typeful code representation in which program variables are represented in terms of deBruijn indexes, and then formally demonstrate how such typeful code representation can be used to support meta-programming. With our approach, a particular interesting feature is that code becomes first-class values, which can be inspected as well as executed at run-time. The main contribution of the paper lies in the recognition and then the formalization of a novel approach to typed meta-programming that is practical, general and flexible.
16174275
Bit rate optimized time-domain equalizers for DMT systems
The discrete multitone (DMT) transceivers have enjoyed great success in high speed data transmission. It is known that when the cyclic prefix is no shorter than the channel impulse response (CIR), the DMT system is ISI free. For channels with very long CIR such as DSL loops, a time-domain equalizer (TEQ) is typically added at the receiver to shorten the effective impulse response. This paper proposes a filterbank approach to the design of TEQ for maximizing the bit rate. Moreover we introduce the structure of a DMT system with multiple TEQs. The optimal solution for multiple TEQs is given in closed form and it can serve as a theoretical upper bound for all other TEQs. From the multiple TEQ structure, we propose a DMT system with a pair of complex conjugating TEQs. Simulation examples are given to verify the merit of the proposed TEQ.
15500231
Image Copy Detection via Grouping in Feature Space Based on Virtual Prior Attacks
In the past, many researches on image copy detection focused on finding a feature that is robust enough for various kinds of image attacks. But it is difficult to find a globally effective feature that is appropriate for many situations. In this paper, we introduce a classification framework to this problem, instead of solving the feature-selection problem. In our approach, novel features are generated by applying virtual prior attacks to copyrighted images, and the copy-detection problem is converted to a classification one that is more robust to solve. Our approach can combine existing image copy detectors and further raise their performances.
15424500
Semantically modified diffusion limited aggregation for visualizing large-scale networks
Diffusion-limited aggregation (DLA) is a model of fractal growth. Computer models can simulate the fast aggregation of millions of particles. We propose a modified version of DLA, called semantically modified DLA (SM-DLA), for visualizing large-scale networks. SM-DLA introduces similarity measures between particles so that instead of attaching to the nearest particle in the aggregation, a new particle is stochastically directed to attach to particles that are similar to it. The results of our initial experiment with a co-citation network using SM-DLA are encouraging, suggesting that the algorithm has the potential as an alternative paradigm for visualizing large-scale networks. Further studies in this direction are recommended.
18159266
A Distributed Simulation-Based Computational Intelligence Algorithm for Nanoscale Semiconductor Device Inverse Problem
In this paper, a distributed simulation-based computational intelligence algorithm for inverse problem of nanoscale semiconductor device is presented. This approach features a simulation-based optimization strategy, and mainly integrates the semiconductor process simulation, semiconductor device simulation, evolutionary strategy, and empirical knowledge on a distributed computing environment. For a set of given target current-voltage (I-V) curves of metal-oxide-semiconductor field effect transistors (MOSFETs) devices, the developed prototype executes evolutionary tasks to solve an inverse doping profile problem, and therefore optimize fabrication recipes. In the evolutionary loop, the established management server allocates the jobs of process simulation and device simulation on a PC-based Linux cluster with message passing interface (MPI) libraries. Good benchmark results including the speed-up, the load balancing, and the parallel efficiency are presented. Computed results, compared with the realistic measured data of 65 nm n-type MOSFET, show the accuracy and robustness of the method.
61209915
CiteSpace II: Detecting and visualizing emerging trends and transient patterns in scientific literature
This article describes the latest development of a generic approach to detecting and visualizing emerging trends and transient patterns in scientific literature. The work makes substantial theoretical and methodological contributions to progressive knowledge domain visualization. A specialty is conceptualized and visualized as a time-variant duality between two fundamental concepts in information science: research fronts and intellectual bases. A research front is defined as an emergent and transient grouping of concepts and underlying research issues. The intellectual base of a research front is its citation and co-citation footprint in scientific literature—an evolving network of scientific publications cited by research-front concepts. Kleinberg's (2002) burst-detection algorithm is adapted to identify emergent research-front concepts. Freeman's (1979) betweenness centrality metric is used to highlight potential pivotal points of paradigm shift over time. Two complementary visualization views are designed and implemented: cluster views and time-zone views. The contributions of the approach are that (a) the nature of an intellectual base is algorithmically and temporally identified by emergent research-front terms, (b) the value of a co-citation cluster is explicitly interpreted in terms of research-front concepts, and (c) visually prominent and algorithmically detected pivotal points substantially reduce the complexity of a visualized network. The modeling and visualization process is implemented in CiteSpace II, a Java application, and applied to the analysis of two research fields: mass extinction (1981–2004) and terrorism (1990–2003). Prominent trends and pivotal points in visualized networks were verified in collaboration with domain experts, who are the authors of pivotal-point articles. Practical implications of the work are discussed. A number of challenges and opportunities for future studies are identified. © 2006 Wiley Periodicals, Inc.