Partial evaluation in insertion modeling system
The paper relates to practical aspects of insertion modeling. Insertion modeling system is an environment for development of insertion machines, used to represent insertion models of distributed systems. The notions of insertion modeling are stated. The main features of partial evaluation are descri...
Gespeichert in:
| Datum: | 2025 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2025
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/784 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-784 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/0b/0d14b9c996c3ca2bf5c0c4e578c57f0b.pdf |
| spelling |
pp_isofts_kiev_ua-article-7842025-08-27T13:30:47Z Partial evaluation in insertion modeling system Часткові обчислення у системі інсерційного моделювання Peschanenko, V.S. UDC 004.2,004.4 УДК 004.2,004.4 The paper relates to practical aspects of insertion modeling. Insertion modeling system is an environment for development of insertion machines, used to represent insertion models of distributed systems. The notions of insertion modeling are stated. The main features of partial evaluation are described in the paper. The concep-tion of partial evaluation in insertion modeling is presented.Problems in programming 2013; 1: 14-22 Стаття відноситься до практичних аспектів інсерційного моделювання. Система інсерційного моделювання – це середовище для розробки інсерційних машин, які використовуються для представлення інсерційних моделей для розподілених систем. В статті описано основні поняття інсерційного моделювання та основні поняття змішаних обчислень. Основна концепція реалізації змішаних обчислень у інcерційному моделюванні представлена у статті.Problems in programming 2013; 1: 14-22 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-27 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/784 PROBLEMS IN PROGRAMMING; No 1 (2013); 14-22 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2013); 14-22 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2013); 14-22 1727-4907 en https://pp.isofts.kiev.ua/index.php/ojs1/article/view/784/836 Copyright (c) 2025 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-08-27T13:30:47Z |
| collection |
OJS |
| language |
English |
| topic |
UDC 004.2,004.4 |
| spellingShingle |
UDC 004.2,004.4 Peschanenko, V.S. Partial evaluation in insertion modeling system |
| topic_facet |
UDC 004.2,004.4 УДК 004.2,004.4 |
| format |
Article |
| author |
Peschanenko, V.S. |
| author_facet |
Peschanenko, V.S. |
| author_sort |
Peschanenko, V.S. |
| title |
Partial evaluation in insertion modeling system |
| title_short |
Partial evaluation in insertion modeling system |
| title_full |
Partial evaluation in insertion modeling system |
| title_fullStr |
Partial evaluation in insertion modeling system |
| title_full_unstemmed |
Partial evaluation in insertion modeling system |
| title_sort |
partial evaluation in insertion modeling system |
| title_alt |
Часткові обчислення у системі інсерційного моделювання |
| description |
The paper relates to practical aspects of insertion modeling. Insertion modeling system is an environment for development of insertion machines, used to represent insertion models of distributed systems. The notions of insertion modeling are stated. The main features of partial evaluation are described in the paper. The concep-tion of partial evaluation in insertion modeling is presented.Problems in programming 2013; 1: 14-22 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2025 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/784 |
| work_keys_str_mv |
AT peschanenkovs partialevaluationininsertionmodelingsystem AT peschanenkovs častkovíobčislennâusistemíínsercíjnogomodelûvannâ |
| first_indexed |
2025-09-17T09:22:29Z |
| last_indexed |
2025-09-17T09:22:29Z |
| _version_ |
1843502461661216768 |
| fulltext |
Формальні методи розробки програмного забезпечення
© V. Peschanenko, 2013
14 ISSN 1727-4907. Проблеми програмування. 2013. № 1
UDC 004.2,004.4
Vladimir Peschanenko
PARTIAL EVALUATION IN INSERTION MODELING SYSTEM
The paper relates to practical aspects of insertion modeling. Insertion modeling system is an environment for
development of insertion machines, used to represent insertion models of distributed systems. The notions of
insertion modeling are stated. The main features of partial evaluation are described in the paper. The concep-
tion of partial evaluation in insertion modeling is presented.
Introduction
Insertion modeling is an approach to
modeling complex distributed systems, based
on the theory of interaction of agents and en-
vironments [1–3]. Mathematical foundation
of this theory was presented in [4]. During the
last decade insertion modeling was applied
to the verification of requirements for soft-
ware systems [5–9]. First the theory of inter-
action of agents and environments was pro-
posed as an alternative to well known theories
of interaction such as Milner’s CCS [10] and
Pi-calculus [11], Hoare’s CSP [12], Cardelli’s
mobile ambients [13] and so on. The idea
of decomposition of system to composition
of environment, and agents inserted into this
environment implicitly exists in all theories
of interaction and for some special case it
appears explicitly in the model of mobile
ambients.
Another source of ideas for insertion
modeling is the search of universal program-
ming paradigms such as Gurevich’s ASM
[14], Hoare’s unified theories of program-
ming [15], rewriting logic of Meseguer [16].
These ideas were taken as a basis for the sys-
tem of insertion programming [17], developed
as the extension of algebraic programming
system APS [18]. Now this system initiated
the development of insertion modeling system
IMS which was started in Glushkov Institute
of Cybernetics. The first version of IMS and
some simple examples of its use are available
in [19]. IMS has many applications
[20-22], that is why a speed of interpretation
of the IMS is very important. One of the tech-
niques which helps to speed up interpretation
is partial evaluation.
Partial evaluation was the subject of
rapidly increasing activity over the past dec-
ade of previous century since it provides a
unifying paradigm for a broad spectrum of
work in program optimization, interpretation,
compiling, other forms of program genera-
tion, and even the generation of automatic
program generators.
Many applications today have con-
cerned compiling and compiler generation
from interpretive programming language def-
initions, but partial evaluation also has im-
portant applications in scientific computing,
logic programming, meta-programming, and
expert systems.
It is distributed a program optimiza-
tion technique, which is called program spe-
cialization. Full automation and the genera-
tion of program generators, as well as trans-
forming single programs, are central themes
and they have been achieved [23].
Presentation of partial evaluation in
IMS is the main goal of the paper. The second
section presents the insertion machines, their
properties and restrictions that can be met in
practice. The main notions about partial eval-
uations are described in the third section. Par-
tial evaluations for insertion modeling are
considered in the last section.
1. Insertion Modeling
Insertion modeling is the development
and investigation of distributed concurrent
systems by means of representing them as a
composition of interacting agents and envi-
ronments. Both agents and environments are
attributed transition systems, considered up to
dissimilarity, but environments are additional-
ly provided with insertion function used for
the composition and characterizing the behav-
ior of environment with inserted agents. At-
Формальні методи розробки програмного забезпечення
15
tributed transition systems are labeled as tran-
sition systems and the labels of transitions are
called actions, they have states labeled by
attribute labels. If s is a state of a system,
then its attributed label will be denoted as
al s . Transition system can be also enriched
by distinguishing in its set of states S the set
of initial states SS 0 and the set of terminal
states SS . For attributed transition sys-
tem we use the following notation:
sasa a :: means, there is a transition
from the state s with attributed label La to
the state s labeled by attributed label La ,
and this transition is labeled by action La .
Therefore enriched attributed system S can
be considered as a tuple
LSalSASTSSLAS :,,,,,, 0 .
A pair LA, of actions and
attributed labels is called a signature of sys-
tem S. We also distinguish hidden action
and hidden attributed label 1. Unlike other
actions and attributed labels these hidden la-
bels are not observable.
Behaviors. Each state of transition
system is characterized up to bisimilarity
by its behavior represented as an element of
behavior algebra (special kind of process
algebra). The behavior of system in given
state for the ordinary (labeled, but not
attributed) systems is specified as an element
of complete algebra of behaviors F A (with
prefixing a.u, non-deterministic choice u+v,
constants ,,0 , the approximation relation
, and the lowest upper bounds of directed
sets of behaviors). In the sequel we shall
use the term process as a synonym of be-
havior.
For attributed systems attributed
behaviors should be considered as invariants
of bisimilarity. The algebra LAU ,, of
attributed behaviors consists of three sorted
algebra. The main set is a set U of attribut-
ed behaviors, A is a set of actions, L is a set
of attribute labels. Prefixing and non-
deterministic choice are defined as usually
(nondeterministic choice is associative,
commutative and idempotent). Besides the
usual behavior constants 0 (deadlock),
(successful termination) and (unde-
fined behavior), the empty action τ is also
introduced with the identity
uu . .
The operation Uu : of labeling the be-
havior Uu with an attribute label L is
added. The empty attribute label 1 is intro-
duced with the identity
uu :1 .
The approximation is extended to labeled be-
haviors, so that
vuvu ):( ):(
Constructing a complete algebra
,F A L of labeled behaviors is similar to the
constructing of the algebra F A . Each be-
havior u in this algebra has a canonical form:
u
Jj
jj
Ii
ii uauu
.: ,
where ji a,1 , u is a termination con-
stant ( ,,,0 ), all summands are dif-
ferent and behaviors iu and ju are in the
same canonical form.
Behaviors, i.e., elements of the algebra
,F A L can be considered as the states of an
attributed transition system. The transition
relation of this system is defined as follows:
uvua
a
.
uvuvu :):(:1:
uua
a
.:
uu :::
.
Set E of behaviors is called transition
closed if EuuuEu
a
, .
Ordinary labeled transition systems
are considered as special case of attributed
ones with the set of attribute labels equal to
1 , and the algebra F A is identified with
, 1F A .
Insertion function. Environment
,,,,, MALCE is defined as a transition
Формальні методи розробки програмного забезпечення
16
closed set of behaviors LCFE , with in-
sertion function EMAFE ,: . The
only requirement for insertion function is that
it must be continuous w.r.t. approximation
relations defined on E and ,F A M . Usually
the behaviors of environment are represented
by the states of transition system considering
them up to bisimilarity. The state ),( ue of
environment resulting after agent insertion
(identified with the corresponding behavior)
is denoted as ][ue or ][ue to mention inser-
tion function explicitly and the iteration of
insertion function as
]]...)[])[[(...(],...,,[ 2121 mm uuueuuue .
Environments can be considered as agents
and therefore can be inserted into higher level
environments with other insertion functions.
So the state of multilevel environments can be
described for example by the following ex-
pression: ,...],...],[,...],,[[ 2
2
1
2
22
1
1
1
1 uueuuee .
The most of insertion functions considered in
this paper are one-step or head ones. Typical
rules for definition of insertion function are
the following (one-step insertion):
][][
,
ueue
uuee
c
aa
, (1)
][][ ueue
ee
c
c
. (2)
The first rule can be treated as follows.
Agent u asks for permission to perform
an action a, and if there an a-transition ex-
ists from state e, performance of a is al-
lowed and both agent and environment
come to the next state with observable ac-
tion c of environment. The second rule de-
scribes the move of environment with sus-
pended move of agent. The additivity condi-
tions usually are used:
][][][ veuevue ,
][][])[( ufueufe .
The rules (1-2) can also be written in
the form of rewriting rules:
fuecuaea ][.].)[.( ,
guecuec ][.])[.( .
Two kinds of insertion machines are
considered: real type or interactive and ana-
lytical insertion machines. The first ones exist
in real or virtual environment, interacting
with it in real or virtual time. Analytical ma-
chines intended for model analyses, investiga-
tion of its properties, solving problems etc.
The drivers for two kinds of machines corre-
spondingly are also divided into interactive
and analytical drivers.
Interactive driver after normalizing the
state of environment must select exactly one
alternative and perform the action, specified
as a prefix of this alternative.
Insertion machine with interactive
driver operates as an agent inserted into ex-
ternal environment with insertion function
defining the laws of functioning of this envi-
ronment. External environment, for example,
can change a behavior prefix of insertion ma-
chine according to their insertion function.
Interactive driver can be organized in a rather
complex way. If it has criteria of successful
functioning in external environment, intellec-
tual driver can accumulate the information
about its past, develop the models of external
environment, improve the algorithms of se-
lecting actions to increase the level of suc-
cessful functioning. In addition it can have
specialized tools to exchange the signals with
external environment (for example, percep-
tion of visual or acoustical information, space
movement, etc).
Analytical insertion machine opposed
to interactive one can consider different vari-
ants of making decision about performed ac-
tions, returning to choice points (as in logic
programming) and consider different paths
in the behavior tree of a model. The model
of system can include the model of external
environment of this system, and the driver
performance depends on the goals of insertion
machine. In general case analytical machine
solves the problems by search of states, hav-
ing the corresponding properties(goal states)
Формальні методи розробки програмного забезпечення
17
or states in which given safety properties are
violated. The external environment for inser-
tion machine can be represented by a user
who interacts with insertion machine, sets
problems, and controls the activity of inser-
tion machine.
Analytical machine enriched by log-
ic and deductive tools can be used for sym-
bolic modeling. The state of symbolic mod-
el is represented by means of properties of
the values of attributes rather then their co-
ncrete values.
The general architecture of insertion
machine is represented on the fig. 1.
The main component of insertion
machine is model driver, the component
which controls the machine movement on the
behavior tree of a model. The state of a model
is represented as a text in input language
of insertion machine and is considered as an
algebraic expression. The input language
includes recursive definitions of agent behav-
iors, notation for insertion function, and
Fig. 1. Architecture of Insertion Machine
possibly some compositions for environment
states. The state of a system must be reduced
to the form ,...],[ 21 uuE . This functionality
is performed by the module called agent
behavior unfolder. To make the movement,
the state of environment must be reduced to
normal form
Ii
ii Ea where ia are
actions, iE are environment states, is a
termination constant. This functionality is
performed by the module environment
interactor. It computes the insertion function
calling the agent behavior unfolder, if it is
necessary. If the infinite set I of indices
is normally allowed, the weak normal form
GFa . is used, where G is arbitrary expres-
sion of input language [9].
2. Partial Evaluations
It is well known that a one-argument
function can be obtained from two-argument
function by specialization, i.e. by fixing one
input to particular value. In analysis it is
called restriction or projection, and in logic it
is called currying. Partial evaluation, howev-
er, works with program texts rather than
mathematical functions.
Partial evaluator is an algorithm which
produces a so-called residual or specialized
program, when a program and some of its in-
put data are given. Running the residual pro-
gram on remaining input data will yield the
same result as running the original program
on all of its input data.
The theoretical possibility of partial
evaluation was established many years ago in
recursive function theory as Kleene’s “s-m-n
theorem”.
Partial evaluation sheds new light on
techniques for program optimization, compi-
lation, interpretation, and generation of pro-
gram generators. Further, it gives insight into
the properties of programming languages
themselves.
Partial evaluation can be considered as
a special case of program transformation, but
emphasizes full automation and generation of
program generators as well as transformation
of single programs.
Partial evaluation gives a remarkable
approach to compilation and compiler genera-
tion. For example, partial evaluation of an
interpreter with respect to a source program
yields target program. Thus, compilation can
be achieved without a compiler, and a target
program can be considered as a specialized
interpreter.
Moreover, provided partial evaluator
is self-applicable, compiler generation is pos-
sible: specializing the partial evaluator itself
with respect to a fixed interpreter yields a
compiler. Thus a compiler can be considered
as a specialized partial evaluator, which can
specialize only an interpreter for a particular
language. Finally, specializing the partial
evaluator with respect to itself yields a com-
piler generator. Thus, compiler generator can
be thought of as a specialized partial evalua-
tor, which can specialize itself only.
Формальні методи розробки програмного забезпечення
18
The application of partial evaluation
is not restricted to compiling and compiler
generation. If a program takes more than one
input, and one of the inputs varies more slow-
ly than the others, then specialization of the
program with respect to that input gives a
faster specialized program. Moreover, a lot of
real-life programs exhibit interpretive behav-
ior. For instance, they may be parameterized
with configuration _les, etc., which seldom
vary, and therefore they may be profitably
specialized.
The range of potential applications is
extremely large, as shown by the list of ex-
amples in [23]. All examples have been im-
plemented on the computer, by researchers
from Copenhagen, MIT, Princeton, and Stan-
ford universities; and INRIA (France) and
ECRC (Germany). All have been seen to give
significant speedups.
Pattern recognition.
Computer graphics by “ray tracing”.
Neural network training.
Answering database queries.
Spreadsheet computations.
Scientific computing.
Discrete hardware simulation.
In computing partial evaluation is a
technique for several different types of pro-
gram optimization by specialization. The
most straightforward application is to produce
new programs which run faster than the origi-
nals while being guaranteed to behave in the
same way. More advanced usages include
compiling by partially evaluating an inter-
preter with the program to be compiled as its
input; generating compilers by partially eval-
uating a partial evaluator with the interpreter
for the source language concerned as its in-
put. And finally, generating the compiler-
generator by partially evaluating the partial
evaluator with itself as its input. It is also true
and for interpretation, because partial evalu-
ation makes optimization of the source code
of program, which should perform faster.
IMS is the interpreter, that is why we will
talk about partial evaluation of interpretation.
A computer program, prog, is seen as
a mapping of input data into output data:
OIIprog dynamicstatic : .
staticI , the static data, is the part of the
input data, known at interpretation time.
The partial evaluator transforms
staticIprog, into OIprog dynamic:* by
precomputing of all static input during inter-
pretation time. *prog is called the residual
program and should run more efficiently than
the original program. The act of partial evalu-
ation is said to residualize prog to *prog [23].
3. Mixed Computation in Insertion
Modeling
There are three known possibilities to
realize partial evaluation in insertion model-
ing:
Partial behavior evaluation.
Partial actions evaluation.
Partial low level language evaluation.
Partial behavior evaluation. The be-
havior description has the following simple
syntax:
<behavior>::= Delta | bot | 0 |
< action > | <action> . <behavior> |
<behavior> + <behavior>|
<behavior>;<behavior>|
<behavior>||<behavior>|
<functional expression>|
<environment state>[<behavior>]|
<agent name>
A set of agent names is considered as
a system of equations by the following syn-
tax:
<agent equation system>::=
<list of <agent equations> separated by “,” >,
<agent equation>::=
<agent name>=< behavior>.
Therefore, the language of behavior
algebra (termination constants, prefixing
and nondeterministic choice) is extended
by functional expressions and explicit rep-
resentation of insertion function. We con-
sider extended grammar for behavior with
sequential (“;”) and parallel (“||”) composi-
tions [19].
As it was shown in grammar <agent
equation> can be recursive in general case.
It means that it is possible to substitute not
http://en.wikipedia.org/wiki/Computing
http://en.wikipedia.org/wiki/Optimization_%28computer_science%29
http://en.wikipedia.org/wiki/Optimization_%28computer_science%29
http://en.wikipedia.org/wiki/Specialization_%28logic%29
http://en.wikipedia.org/wiki/Computer_program
Формальні методи розробки програмного забезпечення
19
recursive equations in right part of other
equations and in behavior.
Let ),( Sysub be defined behavior
and SysA is set of agent names (left part of
equations), and uA is set of agent names in
behavior u. The system of equation is static
for concrete example. It means that
staticISys . In step-by-step insertion the be-
havior u is changed. Speaking generally,
dynamicIu . So, the notion of partial evalua-
tion can be used here for optimization of in-
terpretation.
However, note that equations are used
for definition of infinite behavior. So, the
partial evaluation here is to eliminate all agent
names which define finite behavior in u and
Sys. Let fA be set of agent names (left part
of equations in Sys) which defines finite
behavior. So, the idea of partial evaluation
here is to build fff ASysAuAb /,// ,
where operation “a/b” defines an algorithm of
elimination in a agent names which de-
fines finite behavior fA is the set of agent
names from SysA which behavior abeh and
Sysabeha :
}.))(
(|{ )(
Sysabeh
aAaAaaA abehSysf
Theorem 1.
)/,/(),( ff ASysAbSysb .
Proof. ),(/,/ SysbASysAb ff is
always true, because it is possible to mark
some finite behavior fb inside b and to re-
place it by a new agent name a and to add
new equation fba to the fASys / and so
on. If fA is set of agent names which has
finite behavior in Sys then it is possible to
eliminate all of them from )( fAbeh (the right
parts of equations). It means that )( fAbeh
doesn’t depend on fA . ( )( fAbehf AA ).
Then, it is possible to substitute equations
Sys to u (
fAu AA ). So, the behavior
fAb / is obtained. Next, if )( fAbehf AA
and
fAu AA then all such equations
can be removed from Sys . Finally, fASys /
was obtained and
),()/,/( SysbASysAb ff . So, the theorem
was proved.
Partial actions evaluations. Let split
the set of action A on two subsets where CngA
is the set of changing actions and NCngA is
the set of non-changing actions
NChgChg AAA . One step of insertion of
some action NChgAa is inserted in the next
way:
NChgAauEauaE ],[.].[ .
Here action a doesn’t change envi-
ronment state E and doesn’t add anything to
the resulting behavior u after its insertion.
These actions NChgA are not parameterized.
The one step insertion of some action
ChgAa is inserted in the next way:
AauEafuaE ),,,(].[ ,
where )()(: AFEAFEAf Cng , A is
the set of actions, E is a set of the environ-
ment states, F(A) is an expression in the alge-
bra of behavior. This function f could change
environments state E and could add the new
behavior into u. The set of actions CngA and
corresponded functions f for each of them are
static. It means that we could apply here the
notion of the partial evaluations.
So, let )/,/(/ fff ASysAuAb and
EAFE )(: , where E is a set of envi-
ronment states, F A is an expression in the
algebra of behavior, the function called
insertion function. One of main properties of
such function is continuity. It means that for
each action CngAa the function ),,( uEafa
is defined by insertion function . The set of
such functions is marked by F . Usually in-
sertion function is defined as a system of re-
writing rules. For one step insertion it is nec-
essary to build behavior in the normal form:
Формальні методи розробки програмного забезпечення
20
Aaa i
Ii
ii
,u
which is defined by the only way. Where is
termination constant, iu is behavior. Then, it
is made or we make non-deterministic inser-
tion: ][][][ yExEyxE , where E is envi-
ronment state, x and y are behaviors.
So, the main idea of partial evaluation
here is to build EFAFE ,:* . Let
CngAa , AFu , ),( FAFu .
FAF , is made from F A , by substitution
of an action CngAa in F A to function
),,( uEafa .
Theorem 2. uaEuaE .,., * .
Proof. Let’s collect the set of equa-
tions Fffa aa },{ , where CngAa , af
corresponding interpretation of action. Corre-
sponded function af will always exist be-
cause of continuity of insertion function. Af-
ter that obtained set }{ afa is substituted
into behavior u and the result is
),( FAFu . Finally, all Cnga AaFf ,
are replaced in the insertion function by
the following condition:
),,(].[ uEafufE aa .
From the other side
),,(].[ uEafuaE a for CngAa and the the-
orem is proved.
From the other point of view what
happens with the program if the both algo-
rithms of partial evaluations are done?
Theorem 3. Cngf AA .
Proof. fA is the set of agent names,
but agent names are not the actions because
they are defined by the equation in unfolding.
So, the theorem is proved.
From practical point of view this theo-
rem means that these two partial evaluations
are independent and could be realized in any
combinations.
4. Partial low level language
evaluation
The Algebraic Programming System
APS and Insertion Modeling System IMS
[24] are used for prototyping of the algo-
rithms first, then for research of the proper-
ties and behavior of such algorithms, and
finally for realization of a final version for
such algorithms. These systems have two
languages for realizations of this idea:
APLAN (Algebraic Programming LANguage)
and C++ (language of such systems realiza-
tion). The process of automatically conver-
sion of code from APLAN to C++ was de-
scribed in [25]. So, if some algorithm was
researched and realized in final version of it
then it is possible to consider it as a static
data of the programs. It means that the no-
tion of partial evaluation could be used here.
This idea can be used for realization of func-
tions af from the previous section and for
final realization of the Model Driver module
(fig. 1). However, note that the idea spreads
for all part of such algorithm. A user should
choose what parts of the algorithm are con-
sidered as static. And then, our partial evalu-
ation for that case should support that. For
realization of partial evaluation here the no-
tion of APLAN interpreter is used.
APLAN Interpreters are programs
designed for the interpretation of the pro-
grams written in APLAN language. They are
developing in C++ language on the base of
libraries of functions and data structures to
work with internal representation of system
data structures. Each interpreter is connect-
ed with the distinct algebra AXT , , where
is signature (the set of marks with arity),
X is set of names in APLAN, and A is set of
atoms. Names and atoms are APLAN no-
tions. The easer way to make partial evalua-
tion is to use here the translator of source
code which was developed early [25]. The
Translator transfers realization of such
codes from the set X to the A. The function
names are considered as atoms. If such
codes depend on other APLAN code then
such conversion obtains the internal
call of sub-programs only. It means that
if some APLAN sub-program is left
Формальні методи розробки програмного забезпечення
21
on APLAN language then the resulting co-
des are called C++ realization. So, the
problem of using C++ procedures in
APLAN language is solved. If the system
has both realizations APLAN and C++ with
the same name then after removing
of APLAN definition the system uses
C++. However, the problem of replacing
of some C++ procedure to APLAN proce-
dure is still actual.
The solution of this problem is to add
the set H of pairs nn fx , , where nx is
APLAN name of such procedure or Nil if cor-
responded name was not found, nf is pointer
to C++ realization of such procedure or Nil if
corresponded procedure was not realized yet.
This set H can be obtained after loading of
initial model, because that process builds the
algebra AXT , according to the current
APLAN Interpreter. The function
AXTAXTHpc ,,: is defined in
Interpreter. This function is used in C++ in-
stead of direct call of function nf . It finds
pointer for the current realization of the
APLAN procedure. This function works by
the following way:
If Nilxn then it calls corresponded
APLAN procedure.
If NilfNilx nn then it calls
corresponded C++ procedure.
If NilfNilx nn then it prints er-
ror message and returns Nil.
The most important feature of real-
ization of such function pc is strategies
calling [25]. For this case the function
AXTAXTHHpc ,,:2
is de-
fined. The case, when system of rewriting
rules (s.r.r.) can be considered as internal
function on C++, is added to all internal
strategies. Let pairs Hfxfx nnnn 2211 ,,, be
the first and the second arguments of 2pc
function respectively. Then this function
works in the following way:
If NilxNilx nn
21 then it calls
corresponded APLAN strategy with APLAN
s.r.r.
If NilxNilfNilx nnn
211
then it calls corresponded C++ strategy with
APLAN s.r.r.
If NilfNilxNilx
nnn 221
then it calls corresponded APLAN strategy
with C++ s.r.r.
If NilxNilxNilx
nnn
211
Nilf
n
2 then it calls corresponded C++
strategy with C++ s.r.r.
If NilxNilxNilx
nnn
211
Nilf
n
2 then it prints error message and
returns Nil.
This partial evaluation for low level
realization gives possibilities to research sub-
programs of final C++ program on APLAN
language. For example, if it is required to re-
search one procedure in large system then we
could realize it on APLAN only and run it
without appreciable loss of performance. It
gives us possibilities to research any sub-
program of large system that was realized in
APS and IMS systems.
Conclusion
So, the notion of the partial evalua-
tions is applicable to the insertion modeling
and could be used in practice. These ap-
proaches were realized in APS and IMS, that
makes them more applicable for industrial
projects.
1. Letichevsky A.A., Gilbert D.R. A universal
interpreter for nondeterministic concurrent
programming languages // Fifth Compulog
network area meeting on language design and
semantic analysis methods, 1996.
2. Letichevsky A., Gilbert D. A general theory of
action languages // Cybernetics and System
Analyses. – 1998. – Vol. 1. – P. 16–36.
3. Letichevsky A., Gilbert D. A Model for Inter-
action of Agents and Environments // [In
D. Bert, C. Choppy, P. Moses, (eds.)] Recent
Trends in Algebraic Development Tech-
niques. – Springer 1999 (LNCS). – Vol. 1827.
– P. 311–328.
4. Letichevsky A. Algebra of behavior transfor-
mations and its applications // [In
Формальні методи розробки програмного забезпечення
22
V.B. Kudryavtsev and I.G. Rosenberg (eds)]
Structural theory of Automata, Semigroups,
and Universal Algebra, NATO Science Series
II. Mathematics, Physics and Chemistry. –
Springer 2005. – Vol 207. – P. 241–272.
5. Baranov S., Jervis C., Kotlyarov V., Letichev-
sky A., and Weigert T. Leveraging UML to
Deliver Correct Telecom Applications // [In
L. Lavagno, G. Martin, and B.Selic, (eds.)]
UML for Real: Design of Embedded Real-
Time Systems. Kluwer, Amsterdam: Academ-
ic Publishers, 2003.
6. Letichevsky A., Kapitonova J., Letichevsky A.
jr., Volkov V., Baranov S., Kotlyarov V., Wei-
gert T. Basic Protocols, Message Sequence
Charts, and the Verification of Requirements
Specifications // Computer Networks. – 2005.
– Vol. 47. – P. 662–675.
7. Kapitonova J., Letichevsky A., Volkov V., and
Weigert T. Validation of Embedded Systems
// [In R. Zurawski, (eds.)] The Embedded Sys-
tems Handbook. Miami: CRC Press, 2005.
8. Letichevsky A., Kapitonova J., Volkov V., Let-
ichevsky A. jr., Baranov S., Kotlyarov V., and
Weigert T. System Specification with Basic
Protocols // Cybernetics and System Anal-
yses. – 2005. – Vol. 4. – P. 479–493.
9. Letichevsky A., Kapitonova J., Kotlyarov V.,
Letichevsky A. jr., Nikitchenko N., Volkov V.,
and Weigert T. Insertion modeling in distrib-
uted system design // Problems of Program-
ming. – 2008. – Vol. 4. – P. 13–39.
10. Milner R. Communication and Concurrency //
Prentice Hall, 1989.
11. Milner R. Communicating and Mobile Sys-
tems: the Pi Calculus / R. Milner Cambridge
University Press 1999.
12. Hoare C.A.R. Communicating Sequential
Processes // Prentice Hall, 1985.
13. Cardelli L. Mobile Ambients. In Foundations
of Software Science and Computational
Structures // [Gordon Maurice Nivat (eds.)]. –
Springer 1998 (LNCS). – Vol. 1378. –
P. 140–155.
14. Gurevich Y. Evolving Algebras 1993: Lipari
Guide // [In E. Borger (eds.)] Specificationand
Validation Methods. – Oxford University
Press. – 1995. – P. 9–36.
15. Hoare C.A.R. Unifying Theories of Program-
ming // He Jifeng Prentice Hall International
Series in Computer Science, 1998.
16. Meseguer J. Conditional rewriting logic as a
unified model of concurrency // Theoretical
Computer Science. – 1992. – P. 73–155.
17. Letichevsky A., Kapitonova J., Volkov V.,
Vyshemirsky V., Letichevsky A. jr. Insertion
programming // Cybernetics and System
Analyses. – 2003. – Vol. 1. – P. 19–32.
18. Kapitonova J.V., Letichevsky A.A., and
Konozenko S.V. Computations in APS //
Theoretical Computer Science. – 1993. –
P. 145–171.
19. Letichevsky A.A., Letychevskyi O.A.,
Peschanenko V.S. Insertion Modeling System
// PSI 2011, Lecture Notes in Computer Sci-
ence, Vol. 7162, Springer, 2011. –
P. 262–274.
20. VRS Tool [http://www.issukraine.com/
ISS_VRS_tool.htm].
21. Methodical Program Complex TerM 7-9
[http://riit.ksu.ks.ua/index.php?q=en/node/
228].
22. Kobets V.M. Introduction of information
technologies knowledge control from eco-
nomical disciplines // Informatin Technolo-
gies in Education. – 2019. – Vol. 3, –
P. 123–127.
23. Neil D. Jones, Carsten K. Gomard, and Peter
Sestoft: Partial Evaluation and Automatic
Program Generation, Prentice Hall Interna-
tional, 1993.
24. APS&IMS system [http://apsystem.org.ua].
25. Letichevsky A., Letichevsky A. Jr, V. Pes-
chanenko. Translation Algorithm of APLAN
code // Control's Machines and Systems. –
2010. – Vol. 6. – P. 40–46.
Data received 09.04.2012
About author:
Vladimir Peschanenko,
Associate Professor of Informatics Department
of Kherson State University. Candidate of
Physics and Mathematics, Associate Professor.
http://apsystem.org.ua/uploads/doc/ims/SSHBP.rus.pdf
http://apsystem.org.ua/uploads/doc/ims/SSHBP.rus.pdf
http://www.itu.dk/people/sestoft/pebook/
http://www.itu.dk/people/sestoft/pebook/
http://www.itu.dk/people/sestoft/pebook/
http://www.itu.dk/people/sestoft/pebook/
|