WikiDer > Программа нарезки

Program slicing

В компьютерное программирование, программа нарезки вычисление набора программных операторов, программный фрагмент, который может повлиять на значения в некоторой интересующей вас точке, называемой критерий нарезки. Программа нарезки может использоваться в отладка чтобы легче было найти источник ошибок. Другие применения нарезки включают: обслуживание программного обеспечения, оптимизация, программный анализ, и управление информационным потоком.

Методы нарезки быстро развивались с момента первоначального определения Марк Вайзер. Сначала нарезка была только статической, то есть применялась к исходному коду без какой-либо другой информации, кроме исходного кода. Богдан Корель и Януш Ласки представил динамическая нарезка, который работает с конкретным выполнением программы (для данной трассировки выполнения).[1] Существуют и другие формы нарезки, например нарезка пути.[2]

Статическая нарезка

Основываясь на первоначальном определении Вайзера,[3] неформально статический программный фрагмент 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) .

Пример

Например, рассмотрим приведенную ниже программу C. Давайте вычислим срез для (запись (сумма), сумма). На значение суммы напрямую влияют утверждения «sum = sum + i + w», если N> 1, и «int sum = 0», если N <= 1. Итак, slice (write (sum), sum) - это объединение трех срезов и оператора int sum = 0, у которого нет зависимостей:

  1. срез (сумма = сумма + я + ш, сумма)
  2. ,
  3. срез (сумма = сумма + я + ш, я)
  4. ,
  5. срез (сумма = сумма + я + ш, ш)
  6. , и
  7. {int sum = 0}.

Довольно легко увидеть, что slice (sum = sum + i + w, sum) состоит из «sum = sum + i + w» и «int sum = 0», потому что это единственные два предшествующих утверждения, которые могут повлиять на значение суммы в «сумма = сумма + я + ш». Аналогично, slice (sum = sum + i + w, i) содержит только "for (i = 1; i

Когда мы объединяем все эти операторы, у нас нет исполняемого кода, поэтому, чтобы сделать фрагмент исполняемым фрагментом, мы просто добавляем конечную скобку для цикла for и объявление i. Результирующий статический исполняемый фрагмент показан ниже исходного кода.

int я;int сумма = 0;int товар = 1;int ш = 7;за(я = 1; я < N; ++я) {  сумма = сумма + я + ш;  товар = товар * я;}записывать(сумма);записывать(товар);

Статический исполняемый фрагмент для критериев (написать (сумма), сумма) - это новая программа, показанная ниже.

int я;int сумма = 0;int ш = 7;за(я = 1; я < N; ++я) {  сумма = сумма + я + ш;}записывать(сумма);

Фактически, большинство техник статической нарезки, включая собственную технику Вайзера, также удаляют написать (сумма) утверждение. Поскольку при заявлении написать (сумма), значение сумма не зависит от самого утверждения. Часто срез для конкретного оператора x будет включать более одной переменной. Если V - это набор переменных в операторе x, то срез для (x, V) - это объединение всех срезов с критериями (x, v), где v - переменная в множестве V.

Облегченный подход к статической нарезке вперед

Очень быстрый и масштабируемый, но немного менее точный подход нарезки чрезвычайно полезен по ряду причин. Разработчики будут иметь очень низкие затраты и практичные средства для оценки воздействия изменения в течение нескольких минут, а не дней. Это очень важно для планирования внедрения новых функций и понимания того, как изменение связано с другими частями системы. Он также предоставит недорогой тест, чтобы определить, оправдан ли полный, более дорогой анализ системы. Подход с быстрым срезанием откроет новые возможности для исследования показателей и анализа историй на основе срезов. То есть теперь нарезку можно проводить на очень больших системах и на всей истории версий в очень практичные временные рамки. Это открывает двери для ряда экспериментов и эмпирических исследований, которые ранее были слишком дорогостоящими.[4]

Динамическая нарезка

Использует информацию о конкретном выполнении программы. Динамический срез содержит все операторы, которые фактически влияют на значение переменной в точке программы для конкретного выполнения программы, а не все операторы, которые могли повлиять на значение переменной в точке программы при любом произвольном выполнении программы.

Пример, поясняющий разницу между статической и динамической нарезкой. Рассмотрим небольшой фрагмент программного модуля, в котором есть блок итераций, содержащий блок if-else. В обоих если и еще блоки, которые влияют на переменную. В случае статического среза, поскольку весь программный модуль просматривается независимо от конкретного выполнения программы, затронутые операторы в обоих блоках будут включены в срез. Но в случае динамической нарезки мы рассматриваем конкретное выполнение программы, в котором если блок выполняется, и затронутые операторы в еще блок не выполняется. Вот почему в этом конкретном случае выполнения динамический срез будет содержать только операторы в если блокировать.

Смотрите также

Примечания

  1. ^ Корел, Богдан; Ласки, Януш (1988). «Динамическое нарезание программ». Письма об обработке информации. 29 (3): 155–163. CiteSeerX 10.1.1.158.9078. Дои:10.1016/0020-0190(88)90054-3.
  2. ^ Джхала, Ранджит; Маджумдар, Рупак (2005). Нарезка пути. Труды конференции ACM SIGPLAN 2005 г. по разработке и реализации языков программирования. PLDI '05. Нью-Йорк, Нью-Йорк, США: ACM. С. 38–47. Дои:10.1145/1065010.1065016. ISBN 9781595930569.
  3. ^ Вейзер, Марк Дэвид (1979). Программные фрагменты: формальные, психологические и практические исследования автоматического метода абстракции программ (Кандидатская диссертация). Анн-Арбор, Мичиган, США: Мичиганский университет.
  4. ^ Alomari, Hakam W .; Collard, Michael L .; Maletic, Джонатан I .; Альхиндави, Ноух; Мекдади, Омар (19 мая 2014 г.). «srcSlice: очень эффективный и масштабируемый прямой статический срез». Журнал программного обеспечения: эволюция и процесс. 26 (11): 931–961. CiteSeerX 10.1.1.641.8891. Дои:10.1002 / smr.1651. ISSN 2047-7473.

Рекомендации

  • Марк Вайзер. «Программа нарезки». Труды 5-й Международной конференции по программной инженерии, страницы 439–449, IEEE Computer Society Press, март 1981 г.
  • Марк Вайзер. «Программа нарезки». IEEE Transactions по разработке программного обеспечения, том 10, выпуск 4, страницы 352–357, IEEE Computer Society Press, июль 1984 г.
  • Сьюзан Хорвиц, Томас Репси Дэвид Бинкли, Межпроцедурные срезы с использованием графов зависимостей, ACM Transactions on Programming Languages ​​and Systems, Volume 12, Issue 1, pages 26-60, January 1990.
  • Фрэнк Тип. «Обзор техники нарезки программ». Журнал языков программирования, том 3, выпуск 3, страницы 121–189, сентябрь 1995 г.
  • Дэвид Бинкли и Кейт Брайан Галлахер. «Программа нарезки». Успехи в компьютерах, том 43, страницы 1–50, Академическая пресса, 1996.
  • Андреа де Люсия. «Нарезка программ: методы и приложения», Международный семинар по анализу исходного кода и манипуляции с ним, страницы 142–149, 2001 г., IEEE Computer Society Нажмите.
  • Марк Харман и Роберт Хиеронс. «Обзор программной нарезки», Software Focus, Volume 2, Issue 3, страницы 85–92, январь 2001 г.
  • Дэвид Бинкли и Марк Харман. «Обзор эмпирических результатов нарезки программ», «Достижения в области компьютеров», том 62, страницы 105–178, Академическая пресса, 2004.
  • Йенс Кринке. «Program Slicing», В Справочнике по разработке программного обеспечения и инженерии знаний, Том 3: Последние достижения. World Scientific Publishing, 2005
  • Сильва, Жозеп. «Словарь методов, основанных на нарезке программ», ACM Computing Surveys, том 44, выпуск 3, Ассоциация вычислительной техники, Июнь 2012 г.
  • Аломари HW и другие. «srcSlice: очень эффективный и масштабируемый прямой статический срез». Wiley Journal of Software: эволюция и процесс (JSEP), DOI: 10.1002 / smr.1651, Vol. 26, No. 11, pp. 931-961, 2014.

внешняя ссылка