Reflection and time-dependent computing: Experiences with the R2 architecture

In this paper we present an application of computational reflection in the programming oftime-dependent systems. A time-dependent system performs its tasks according to timing specifications specified within the system or imposed from outside the system. Reflective techniques can be applied to programming time-dependent systems because (1) some application programs require the introduction of a new language construct for specifying timing requirements and (2) different applications may require domain-specific scheduling algorithms. To allow a programmer to add or modify language constructs or scheduling algorithms, however, a clear reflective architecture and program interfaces must be provided. This paper proposes a concurrent object-based reflective architecture (R ² architecture) for time-dependent computing. This architecture is based on anindividual reflection scheme and introduces new meta-level objects (real-time meta objects) that are responsible for time-dependent capabilities. An alarm-clock object and a scheduler object are introduced, and message protocols between them and real-time meta objects are defined. We implemented this architecture on ABCL/R2 and created the Sampled Sound Player program as an application. With this application we provided three different scheduler objects and measured the impact of different scheduling algorithms on sound playback. The measured results show that a scheduler with more complex computations at the meta level exhibited less scheduling overhead, thus was capable of better sound playback. The other example, Time-dependent Graceful Degradation Scheme, demonstrates the programming of functionality degradation triggered by failure to satisfy timing specifications.     

The mystery of the tower revealed: A nonreflective description of the reflective tower

In an important series of papers [8, 9], Brian Smith has discussed the nature of programs that know about their text and the context in which they are executed. He called this kind of knowledgereflection. Smith proposed a programming language, called 3-LISP, which embodied such self-knowledge in the domain of metacircular interpreters. Every 3-LISP program is interpreted by a metacircular interpreter, also written in 3-LISP. This gives rise to a picture of an infinite tower of metacircular interpreters, each being interpreted by the one above it. Such a metaphor poses a serious challenge for conventional modes of understanding of programming languages. In our earlier work on reflection [4], we showed how a useful species of reflection could be modeled without the use of towers. In this paper, we give a semantic account of the reflective tower. This account is self-contained in the sense that it does not employ reflection to explain reflection.     

Mirror‐based reflection in AmbientTalk

This paper introduces a novel mechanism to perform intercession (a form of reflection) in an object‐oriented programming language with the goal of making the language extensible from within itself. The proposed mechanism builds upon a mirror‐based architecture, leading to a reusable reflective application programming interface that cleanly separates interface from implementation details. However, support for intercession has been limited in contemporary mirror‐based architectures. This is due to the fact that mirror‐based architectures only support reflection explicitly triggered by metaprograms, while intercession requires reflection implicitly triggered by the language interpreter. This work reconciles mirrors with intercession in the context of an actor‐based, object‐oriented programming language named AmbientTalk. We describe this language's full reflective architecture, highlighting its novel mirror‐based approach to reflect upon both objects and concurrently executing actors. Subsequently, we apply AmbientTalk's mirror‐based reflection to implement two language features, which crucially depend on intercession, to wit future‐type message passing and leased object references. Copyright © 2008 John Wiley & Sons, Ltd.     

Computing in Finite Time

If a message can have n different values and all values are equally probable, then the entropy of the message is log(n). In the present paper, we discuss the expectation value of the entropy, for an arbitrary probability distribution. We introduce a mixture of all possible probability distributions. We assume that the mixing function is uniform

Zero—a blend of static typing and dynamic metaprogramming

Zero is an experimental statically typed, fully object-oriented reflective programming language. Reflective features cover introspection as well as structural and behavioural reflection. The reflective facilities include safe method and class replacements and detailed modification of methods. These enable Zero programs to quickly accommodate to run-time requirements. Behavioural reflection is realised using handlers (hooks), which may be attached to all language constructs based on closures. Zero provides an efficient static typing system with run-time extensions. Methods are first class values and are represented as objects when such representation is required. By using such representation, Zero provides elegant use of statically typed higher-order methods.     

A metalogic programming approach: language,semantics and applications

Abstract

This paper presents a logic programming language of novel conception, called Reflective Prolog, which allows declarative metaknowledge representation and metareasoning. The language is defined by augmenting pure Prolog (Horn clauses) with capabilities of self-reference and logical reflection. Self-reference is designed as a quotation device (a carefully defined naming relation) which allows the construction of metalevel terms that refer to object-level terms and atoms. Logical reflection is designed as an unquotation mechanism (a distinguished truth predicate) which relates names to what is named, thus extending the meaning of domain predicates. The reflection mechanism is embodied in an extended resolution procedure which automatically switches the context between levels. This implicit reflection relieves the programmer from having to explicitly deal with control aspects of the inference process. The declarative semantics of a Reflective Prolog definite program P is provided in terms of the least reflective Herbrand model of P, characterized by means of a suitable mapping defined over the Herbrand interpretations of P. The extended resolution is proved sound and complete with respect to the least reflective Herbrand model. By illustrating Reflective Prolog solutions to an organic set of problems, and by discussing the main differences with respect to other approaches to logic metaprogramming, we show that the proposed language deploys, within its field of action, greater expressive and inferential power than those available till now. The interpreter of the language has been fully implemented. Because of its enhanced power, logic semantics and working interpreter, Reflective Prolog is offered as a contribution toward making the declarative approach of logic programming applicable to the development of increasingly sophisticated knowledge-based systems.     

Goto and Concurrency Introducing Safe Jumps in Esterel

Esterel is a design language for the specification of real time embedded systems. Based on the synchronous concurrency paradigm, its semantics describes execution as a succession of instants of computation. In this work, we consider the introduction of a new gotopause instruction in the language, which acts as a non-instantaneous jump instruction compatible with concurrency. It allows the programmer to activate state control points anywhere in the program, from where the execution is resumed in the next instant. In order to provide the formal semantics of the extended language, we first define a state semantics of Esterel, which we prove observationally equivalent to the original logical behavioral semantics. Including gotopause in the state semantics is then straightforward. We sketch two key applications of our new primitive: a direct encoding of automata and a quasi-linear rewriting of programs eliminating schizophrenic behaviors.     

Continuation-based control in the implementation of parallel logic programs

Continuations are used to define the flow of messages between low level tasks in a parallel logic programming language. A combination of compiler and runtime operations reduces message traffic by up to 50% when success continuations are passed as parameters in messages that start new processes. Continuations are also the key to fast task switching, a critical operation in this fine grain parallel system. Data from sample programs shows the effectiveness of continuations in reducing message traffic and the speed with which task switches are performed on a typical host architecture.Supported by NSF Grant CCR-8707177 and grants from Motorola, Inc, and Hewlett-Packard Corp.     

Dynamic interpretation and hoare deduction

In this paper we present a dynamic assignment language which extends the dynamic predicate logic of Groenendijk and Stokhof [1991: 39–100] with assignment and with generalized quantifiers. The use of this dynamic assignment language for natural language analysis, along the lines of o.c. and [Barwise, 1987: 1–29], is demonstrated by examples. We show that our representation language permits us to treat a wide variety of donkey sentences: conditionals with a donkey pronoun in their consequent and quantified sentences with donkey pronouns anywhere in the scope of the quantifier. It is also demonstrated that our account does not suffer from the so-called proportion problem.Discussions about the correctness or incorrectness of proposals for dynamic interpretation of language have been hampered in the past by the difficulty of seeing through the ramifications of the dynamic semantic clauses (phrased in terms of input-output behaviour) in non-trivial cases. To remedy this, we supplement the dynamic semantics of our representation language with an axiom system in the style of Hoare. While the representation languages of barwise and Groenendijk and Stokhof were not axiomatized, the rules we propose form a deduction system for the dynamic assignment language which is proved correct and complete with respect to the semantics.Finally, we define the static meaning of a program of the dynamic assignment language as the weakest condition such that terminates successfully on all states satisfying , and we show that our calculus gives a straightforward method for finding static meanings of the programs of the representation language.     

Parallelism in logic programs

There is a tension between the objectives of avoiding irrelevant computation and extracting parallelism, in that a computational step used to restrict another must precede the latter. Our thesis, following [3], is that evaluation methods can be viewed as implementing a choice ofsideways information propagation graphs, or sips, which determines the set of goals and facts that must be evaluated. Two evaluation methods that implement the same sips can then be compared to see which obtains a greater degree of parallelism, and we provide a formal measure of parallelism to make this comparison.Using this measure, we prove that transforming a program using the Magic Templates algorithm and then evaluating the fixpoint bottom-up provides a most parallel implementation for a given choice of sips, without taking resource constraints into account. This result, taken in conjunction with earlier results from [3,27], which show that bottom-up evaluation performs no irrelevant computation and is sound and complete, suggests that a bottom-up approach to parallel evaluation of logic programs is very promising. A more careful analysis of the relative overheads in the top-down and bottom-up evaluation paradigms is needed, however, and we discuss some of the issues.The abstract model allows us to establish several results comparing other proposed parallel evaluation methods in the logic programming and deductive database literature, thereby showing some natural, and sometimes surprising, connections. We consider the limitations of the abstract model and of the proposed bottom-up evaluation method, including the inability of sips to describe certain evaluation methods, and the effect of resource constraints. Our results shed light on the limits of the sip paradigm of computation, which we extend in the process.     

The Theory of Fexprs is Trivial

We provide a very simple model of a reflective facility based onthe pure -calculus, and we show that its theory of contextual equivalenceis trivial: two terms in the language are contextually equivalent iff theyare -congruent.     

Cryptanalysis of a sessional blind signature based on quantum cryptography

A digital signature is a mathematical scheme for demonstrating the authenticity of a digital message or document. A blind signature is a form of digital signature in which the content of a message is disguised (blinded) before it is signed to protect the privacy of the message from the signatory. For signing quantum messages, some quantum blind signature protocols have been proposed. Recently, Khodambashi et al. (Quantum Inf Process 13:121, 2014) proposed a sessional blind signature based on quantum cryptography. It was claimed that these protocol could guarantee unconditional security. However, after our analysis, we find that the signature protocol will cause the key information leakage in the view of information theory. Taking advantage of loophole, the message sender can succeed in forging the signature without the knowledge of the whole exact key between the verifier and him. To conquer this shortcoming, we construct an improved protocol based on it and the new protocol can resist the key information leakage attacks.     

Development of programming language Espace and its application to parallel and distributed evolutionary computation

This article proposes a programming language called “Espace” for parallel and distributed computation. In general, it is difficult to code a distributed, parallel program due to multi-threading, message passing, managing clients, and so on. Espace involves a few simple syntax rules added to Java. Developers do not need to know how to write a parallel, distributed program source code in detail. This work applies Espace to parallelize an evolutionary computation program, and shows that the Espace compiler allows the conversion of an evolutionary computation program written in Java into a distributed, parallel system by adding a few words to the program.     

Recursion from iteration

In a simply-typed, call-by-value (CBV) language with first-class continuations, the usual CBV fixpoint operator can be defined in terms of a simple, infinitely-looping iteration primitive. We first consider a natural but flawed definition, based on exceptions and iterative deepening of finite unfoldings, and point out some of its shortcomings. Then we present the proper construction using full first-class continuations, with both an informal derivation and a proof that the behavior of the defined operator faithfully mimics a built-in recursion primitive. In fact, given an additional uniformity assumption, the construction is a two-sided inverse of the usual definition of iteration from recursion. Continuing, we show that the CBV looping primitive is in fact the direct-style equivalent of a continuation-passing-style fixpoint, and that this correspondence extends all the way to traditional definitions of these operators in terms of reflexive types.An earlier version of this work appeared inProceedings of the 1992 ACM SIGPLAN Workshop on Continuations.Supported in part by NSF Grant CCR-8922109 and in part by the Avionics Lab, Wright Research and Development Center, Aeronautical Systems Division (AFSC), U.S. Air Force, Wright-Patterson AFB, OH 45433-6543 under Contract F33615-90-C-1465, ARPA Order No. 7597. The views and conclusions contained in this document are those of the author and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Government.     

A Generic Reification Technique for Object-Oriented Reflective Languages

Computational reflection is gaining interest in practical applications as witnessed by the use of reflection in the Java programming environment and recent work on reflective middleware. Reflective systems offer many different reflection programming interfaces, the so-called Meta-Object Protocols (MOPs). Their design is subject to a number of constraints relating to, among others, expressive power, efficiency and security properties. Since these constraints are different from one application to another, it would be desirable to easily provide specially-tailored MOPs.In this paper, we present a generic reification technique based on program transformation. It enables the selective reification of arbitrary parts of object-oriented meta-circular interpreters. The reification process is of fine granularity: individual objects of the run-time system can be reified independently. Furthermore, the program transformation can be applied to different interpreter definitions. Each resulting reflective implementation provides a different MOP directly derived from the original interpreter definition.     

基于Irrlicht引擎的实时浅水效果模拟

本文在Irrlicht引擎的基础上结合GLSL语言,对浅水的水面波动、反射与折射特性及菲涅尔现象进行了实时模拟。将基于Gestner波的水面波动与基于纹理波的动态法线贴图相结合,真实地模拟了水面的波动与波纹效果。同时,采用渲染到纹理技术实时生成反射贴图,准确地模拟了水面的反射效果,解决了采用环境贴图渲染时的反射失真问题。在不考虑水深的情况下,本文将菲涅尔权值与材质的alpha通道相结合,去掉了实时渲染中折射贴图的生成,在满足实时浅水效果渲染的视觉需求条件下,减小了CPU与GPU的计算量。     

A unification of probabilistic choice within a design-based model of reversible computation

We see reversible computing as a generalisation of sequential computation obtained by revoking the law of the excluded miracle. Our execution language includes naked guarded commands and non-deterministic choice. Choices which lead to miraculous continuations invoke reverse computation, and non-deterministic choice plays the rôle of provisional choice within a backtracking context. We require probabilistic choice for symmetry breaking and sampling large search spaces, but must formulate it differently from previous approaches to obtain the required interactions between probabilistic choice and non-deterministic choice and between probabilistic choice and feasibility. Our formulation allows us to derive the post-distributions which characterise a program, and we use these to construct a relational model. We consider refinement as containment of convex closures within distribution space, qualified with additional conditions to avoid over-refinement. We link the non-probabilistic and probabilistic versions of the model with a Galois connection and show that classical designs are a retract of our probabilistic designs. We consider the interaction between probabilistic and non-deterministic choice and find the same initially counter-intuitive results that have been noted by other investigators. We provide an alternative formulation, within the same model, of oblivious non-determinism, which allows all non-deterministic choices to be moved to the start of a computation. We consider the interaction between probabilistic choice and feasibility that is required to match an operational interpretation in which infeasible commands provoke reverse execution, and we present a small case study to show how the interaction between probabilistic choice and feasibility can be exploited in a practical program. All programming structures described here are supported by our implementation platform, the Reversible Virtual Machine, whose development has accompanied our theoretical investigations.     

PMaude: Rewrite-based Specification Language for Probabilistic Object Systems

We introduce a rewrite-based specification language for modelling probabilistic concurrent and distributed systems. The language, based on PMaude, has both a rigorous formal basis and the characteristics of a high-level rule-based programming language. Furthermore, we provide tool support for performing discrete-event simulations of models written in PMaude, and for statistically analyzing various quantitative aspects of such models based on the samples that are generated through discrete-event simulation. Because distributed and concurrent communication protocols can be modelled using actors (concurrent objects with asynchronous message passing), we provide an actor PMaude module. The module aids writing specifications in a probabilistic actor formalism. This allows us to easily write specifications that are purely probabilistic – and not just non-deterministic. The absence of such (un-quantified) non-determinism in a probabilistic system is necessary for a form of statistical analysis that we also discuss. Specifically, we introduce a query language called Quantitative Temporal Expressions (or QuaTEx in short), to query various quantitative aspects of a probabilistic model. We also describe a statistical technique to evaluate QuaTEx expressions for a probabilistic model.     

ReSpecT Nets: Towards an Analysis Methodology for ReSpecT Specifications

A key feature for infrastructures providing coordination services is the ability to define the behaviour of coordination abstractions according to the requirements identified at design-time. We take as a representative for this scenario the logic-based language ReSpecT (Reaction Specification Tuples), used to program the reactive behaviour of tuple centres. ReSpecT specifications are at the core of the engineering methodology underlying the TuCSoN infrastructure, and are therefore the “conceptual place” where formal methods can be fruitfully applied to guarantee relevant system properties.In this paper we introduce ReSpecT nets, a formalism that can be used to describe reactive behaviours that can succeed and fail, and that allows for an encoding to Petri nets with inhibitor arcs. ReSpecT nets are introduced to give a core model to a fragment of the ReSpecT language, and to pave the way for devising an analysis methodology including formal verification of safety and liveness properties. In particular, we provide a semantics to ReSpecT specifications through a mapping to ReSpecT nets. The potential of this approach for the analysis of ReSpecT specifications is discussed, presenting initial results for the analysis of safety properties.