Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В компьютерном программировании, выделение программы (program slicing) – это вычисление множества операторов программы, называемого срезом программы, которые могут влиять на значения в определенной точке интереса, именуемой критерием выделения. Выделение программы может использоваться при отладке для более легкого определения источника ошибок. Другие области применения выделения включают в себя сопровождение программного обеспечения, оптимизацию, анализ программ и контроль информационных потоков. Методы выделения активно развиваются с момента первоначального определения Марком Вейзером. Изначально выделение было только статическим, то есть применялось к исходному коду без какой-либо информации, кроме самого исходного кода. Богдан Корель и Януш Ласки представили динамическое выделение, которое работает на конкретном выполнении программы (для заданного следа выполнения). Существуют и другие формы выделения, например, выделение по пути.
In computer programming, program slicing is the computation of the set of program statements, the program slice, that may affect the values at some point of interest, referred to as a slicing criterion. Program slicing can be used in debugging to locate source of errors more easily. Other applications of slicing include software maintenance, optimization, program analysis, and information flow control. Slicing techniques have been seeing a rapid development since the original definition by Mark Weiser. At first, slicing was only static, i. e., applied on the source code with no other information than the source code. Bogdan Korel and Janusz Laski introduced dynamic slicing, which works on a specific execution of the program (for a given execution trace). Other forms of slicing exist, for instance path slicing.
Статика
Основываясь на первоначальном определении Вайзера, неформально, статический программный срез S состоит из всех операторов в программе P, которые могут повлиять на значение переменной v в операторе x. Срез определяется для критерия выделения C=(x,v), где x – оператор в программе P, а v – переменная в x. Статический срез включает в себя все операторы, которые могут повлиять на значение переменной v в операторе x для любого возможного ввода. Статические срезы вычисляются путем прослеживания зависимостей между операторами в обратном направлении. В частности, для вычисления статического среза для (x,v) мы сначала находим все операторы, которые могут непосредственно повлиять на значение v до того, как будет достигнут оператор x. Рекурсивно, для каждого оператора y, который может повлиять на значение v в операторе x, мы вычисляем срезы для всех переменных z в y, которые влияют на значение v. Объединение всех этих срезов и является статическим срезом для (x,v).
Based on the original definition of Weiser, informally, a static program slice S consists of all statements in program P that may affect the value of variable v in a statement x. The slice is defined for a slicing criterion C=(x,v) where x is a statement in program P and v is variable in x. A static slice includes all the statements that can affect the value of variable v at statement x for any possible input. Static slices are computed by backtracking dependencies between statements. More specifically, to compute the static slice for (x,v), we first find all statements that can directly affect the value of v before statement x is encountered. Recursively, for each statement y which can affect the value of v in statement x, we compute the slices for all variables z in y that affect the value of v. The union of all those slices is the static slice for (x,v).
Легкий передовый статический подход к резке
Очень быстрый и масштабируемый, но несколько менее точный метод нарезки (slicing) чрезвычайно полезен по ряду причин. Разработчики получат недорогой и практичный способ оценить влияние изменения за минуты вместо дней. Это очень важно для планирования реализации новых функций и понимания взаимосвязи изменения с другими частями системы. Он также предоставит недорогой способ определить, оправдана ли более полная и дорогостоящая аналитика системы. Быстрый метод нарезки откроет новые направления исследований в области метрик и извлечения информации из истории изменений на основе нарезки. Иными словами, теперь нарезку можно проводить на очень больших системах и по всей истории версий за приемлемое время. Это открывает возможности для ряда экспериментов и эмпирических исследований, которые ранее были слишком затратными.
A very fast and scalable, yet slightly less accurate, slicing approach is extremely useful for a number of reasons. Developers will have a very low cost and practical means to estimate the impact of a change within minutes versus days. This is very important for planning the implementation of new features and understanding how a change is related to other parts of the system. It will also provide an inexpensive test to determine if a full, more expensive, analysis of the system is warranted. A fast slicing approach will open up new avenues of research in metrics and the mining of histories based on slicing. That is, slicing can now be conducted on very large systems and on entire version histories in very practical time frames. This opens the door to a number of experiments and empirical investigations previously too costly to undertake.
Динамическое нарезание
Динамическое срезание использует информацию о конкретном выполнении программы. Динамический срез содержит все операторы, которые фактически влияют на значение переменной в заданной точке программы для конкретного выполнения программы, а не все операторы, которые могли повлиять на значение переменной в заданной точке программы для любого произвольного выполнения программы. Рассмотрим пример, чтобы прояснить разницу между статическим и динамическим срезанием. Представим небольшой фрагмент программного модуля, содержащий цикл с блоком if-else. В обоих блоках, if и else, есть несколько операторов, которые влияют на переменную. В случае статического срезания, поскольку рассматривается весь программный модуль вне зависимости от конкретного выполнения программы, в срез будут включены операторы из обоих блоков. Однако, в случае динамического срезания мы рассматриваем конкретное выполнение программы, при котором выполняется блок if, а операторы в блоке else не выполняются. Поэтому, в данном конкретном случае, динамический срез будет содержать только операторы из блока if.
Dynamic slicing makes use of information about a particular execution of a program. A dynamic slice contains all statements that actually affect the value of a variable at a program point for a particular execution of the program rather than all statements that may have affected the value of a variable at a program point for any arbitrary execution of the program. An example to clarify the difference between static and dynamic slicing. Consider a small piece of a program unit, in which there is an iteration block containing an if else block. There are a few statements in both the if and else blocks that have an effect on a variable. In the case of static slicing, since the whole program unit is looked at irrespective of a particular execution of the program, the affected statements in both blocks would be included in the slice. But, in the case of dynamic slicing we consider a particular execution of the program, wherein the if block gets executed and the affected statements in the else block do not get executed. So, that is why in this particular execution case, the dynamic slice would contain only the statements in the if block.