Каким образом происходит поиск семантических ошибок

Статья главы «Порядок выполнения программы и обработка ошибок» из серии «Изучаем C++». В этом уроке мы рассмотрим ряд наиболее распространенных типов семантических ошибок, возникающих в C++ (большинство из которых так или иначе связаны с управлением порядком выполнения программы).

Добавлено 30 мая 2021 в 17:27

В уроке «3.1 – Синтаксические и семантические ошибки» мы рассмотрели синтаксические ошибки, которые возникают, когда вы пишете код, который не соответствует грамматике языка C++. Компилятор уведомит вас об ошибках этого типа, поэтому их легко обнаружить и обычно легко исправить.

Мы также рассмотрели семантические ошибки, которые возникают, когда вы пишете код, который выполняет не то, что вы планировали. Как правило, компилятор не обнаруживает семантических ошибок (хотя в некоторых случаях умные компиляторы могут генерировать предупреждения).

Семантические ошибки могут вызывать большинство из симптомов неопределенного поведения, например, приводить к тому, что программа выдает неправильные результаты, быть причиной неустойчивого поведения, искажать данные программы, вызывать сбой программы – или они могут вообще никак не влиять.

При написании программ семантические ошибки практически неизбежны. Некоторые из них вы, вероятно, заметите, просто используя программу: например, если вы писали игру лабиринт, а ваш персонаж может проходить сквозь стены. Тестирование вашей программы (7.12 – Введение в тестирование кода) также может помочь выявить семантические ошибки.

Но есть еще одна вещь, которая может помочь – это знание того, какой тип семантических ошибок наиболее распространен, чтобы вы могли потратить немного больше времени на то, чтобы убедиться, что в этих случаях всё правильно.

В этом уроке мы рассмотрим ряд наиболее распространенных типов семантических ошибок, возникающих в C++ (большинство из которых так или иначе связаны с управлением порядком выполнения программы).

Условные логические ошибки

Один из наиболее распространенных типов семантических ошибок – это условная логическая ошибка. Условная логическая ошибка возникает, когда программист неправильно пишет логику условного оператора или условия цикла. Вот простой пример:

#include <iostream>
 
int main()
{
    std::cout << "Enter an integer: ";
    int x{};
    std::cin >> x;
 
    if (x >= 5) // упс, мы использовали operator>= вместо operator>
        std::cout << x << " is greater than 5";
 
    return 0;
}

А вот результат запуска программы, при котором была обнаружена эта условная логическая ошибка:

Enter an integer: 5
5 is greater than 5

Когда пользователь вводит 5, условное выражение x >= 5 принимает значение true, поэтому выполняется соответствующая инструкция.

Вот еще один пример для цикла for:

#include <iostream>
 
int main()
{
    std::cout << "Enter an integer: ";
    int x{};
    std::cin >> x;
 
    // упс, мы использовали operator> вместо operator<
    for (unsigned int count{ 1 }; count > x; ++count)
    {
        std::cout << count << ' ';
    }
 
    return 0;
}

Эта программа должна напечатать все числа от 1 до числа, введенного пользователем. Но вот что она на самом деле делает:

Enter an integer: 5

Она ничего не напечатала. Это происходит потому, что при входе в цикл for условие count > x равно false, поэтому цикл вообще не повторяется.

Бесконечные циклы

В уроке «7.7 – Введение в циклы и инструкции while» мы рассмотрели бесконечные циклы и показали этот пример:

#include <iostream>
 
int main()
{
    int count{ 1 };
    while (count <= 10) // это условие никогда не будет ложным
    {
        std::cout << count << ' '; // поэтому эта строка выполняется многократно
    }
 
    return 0; // эта строка никогда не будет выполнена
}

В этом случае мы забыли увеличить count, поэтому условие цикла никогда не будет ложным, и цикл продолжит печатать:

1 1 1 1 1 1 1 1 1 1

пока пользователь не закроет программу.

Вот еще один пример, который преподаватели любят задавать в тестах. Что не так со следующим кодом?

#include <iostream>
 
int main()
{
    for (unsigned int count{ 5 }; count >= 0; --count)
    {
        if (count == 0)
            std::cout << "blastoff! ";
        else
          std::cout << count << ' ';
    }
 
    return 0;
}

Эта программа должна напечатать «5 4 3 2 1 blastoff!«, что она и делает, но не останавливается на достигнутом. На самом деле она печатает:

5 4 3 2 1 blastoff! 4294967295 4294967294 4294967293 4294967292 4294967291

а затем просто продолжает печатать уменьшающиеся числа. Программа никогда не завершится, потому что условие count >= 0 никогда не может быть ложным, если count является целым числом без знака.

Ошибки на единицу

Ошибки «на единицу» возникают, когда цикл повторяется на один раз больше или на один раз меньше, чем это необходимо. Вот пример, который мы рассмотрели в уроке «7.9 – Инструкции for»:

#include <iostream>
 
int main()
{
    for (unsigned int count{ 1 }; count < 5; ++count)
    {
        std::cout << count << ' ';
    }
 
    return 0;
}

Этот код должен печатать «1 2 3 4 5«, но он печатает только «1 2 3 4«, потому что был использован неправильный оператор отношения.

Неправильный приоритет операторов

Следующая программа из урока «5.7 – Логические операторы» допускает ошибку приоритета операторов:

#include <iostream>
 
int main()
{
    int x{ 5 };
    int y{ 7 };
 
    if (!x > y)
        std::cout << x << " is not greater than " << y << 'n';
    else
        std::cout << x << " is greater than " << y << 'n';
 
    return 0;
}

Поскольку логическое НЕ имеет более высокий приоритет, чем operator>, условное выражение вычисляется так, как если бы оно было написано (!x) > y, что не соответствует замыслу программиста.

В результате эта программа печатает:

5 is greater than 7

Это также может произойти при смешивании в одном выражении логического ИЛИ и логического И (логическое И имеет больший приоритет, чем логическое ИЛИ). Используйте явные скобки, чтобы избежать подобных ошибок.

Проблемы точности с типами с плавающей запятой

Следующая переменная с плавающей запятой не имеет достаточной точности для хранения всего числа:

#include <iostream>
 
int main()
{
    float f{ 0.123456789f };
    std::cout << f;
}

Как следствие, эта программа напечатает:

0.123457

В уроке «5.6 – Операторы отношения и сравнение чисел с плавающей запятой» мы говорили о том, что использование operator== и operator!= может вызывать проблемы с числами с плавающей запятой из-за небольших ошибок округления (а также о том, что с этим делать). Вот пример:

#include <iostream>
 
int main()
{
    // сумма должна быть равна 1.0
    double d{ 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 };
 
    if (d == 1.0)
        std::cout << "equal";
    else
        std::cout << "not equal";
}

Эта программа напечатает:

not equal

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

Целочисленное деление

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

#include <iostream>
 
int main()
{
    int x{ 5 };
    int y{ 3 };
 
    std::cout << x << " divided by " << y << " is: " << x / y; // целочисленное деление
 
    return 0;
}

Этот код напечатает:

5 divided by 3 is: 1

В уроке «5.2 – Арифметические операторы» мы показали, что мы можем использовать static_cast для преобразования одного из целочисленных операндов в значение с плавающей запятой, чтобы выполнять деление с плавающей запятой.

Случайные пустые инструкции

В уроке «7.3 – Распространенные проблемы при работе с операторами if» мы рассмотрели пустые инструкции, которые ничего не делают.

В приведенной ниже программе мы хотим взорвать мир, только если у нас есть разрешение пользователя:

#include <iostream>
 
void blowUpWorld()
{
    std::cout << "Kaboom!n";
} 
 
int main()
{
    std::cout << "Should we blow up the world again? (y/n): ";
    char c{};
    std::cin >> c;
 
    if (c=='y'); // здесь случайная пустая инструкция
        blowUpWorld(); // поэтому это всегда будет выполняться, так как это не часть оператора if
 
    return 0;
}

Однако из-за случайной пустой инструкции вызов функции blowUpWorld() выполняется всегда, поэтому мы взрываем независимо от ввода:

Should we blow up the world again? (y/n): n
Kaboom!

Неиспользование составной инструкции, когда она требуется

Еще один вариант приведенной выше программы, которая всегда взрывает мир:

#include <iostream>
 
void blowUpWorld()
{
    std::cout << "Kaboom!n";
} 
 
int main()
{
    std::cout << "Should we blow up the world again? (y/n): ";
    char c{};
    std::cin >> c;
 
    if (c=='y')
        std::cout << "Okay, here we go...n";
        blowUpWorld(); // упс, всегда будет выполняться. Должно быть внутри составной инструкции.
 
    return 0;
}

Эта программа печатает:

Should we blow up the world again? (y/n): n
Kaboom!

Висячий else (рассмотренный в уроке «7.3 – Распространенные проблемы при работе с операторами if») также попадает в эту категорию.

Что еще?

Приведенные выше примеры представляют собой хороший образец наиболее распространенных типов семантических ошибок, которые склонны совершать на C++ начинающие программисты, но их гораздо больше. Читатели, если у вас есть дополнительные примеры, которые, по вашему мнению, являются распространенными ошибками, напишите об этом в комментариях.

Теги

C++ / CppLearnCppДля начинающихОбучениеПрограммирование

Источник

Отладка
программ. Классификация ошибок. Методы
поиска семантических и логических
ошибок.

Отладка –
это этап разработки компьютерной
программы, на которой обнаруживают,
локализуют и устраняют ошибки.

Классификация
ошибок:

1. Синтаксические
– нарушения правил языка программирования.

2. Семантические
– нарушение порядка следования параметров
функции, некорректное использование
переменных (использование индекса,
выходящего за пределы массива), ошибки
вычисления (незнание приоритетов
выполнения операций).

3. Прагматические
или логические – нарушение логики
алгоритма, ошибки алгоритма.

Методы
отладки:

а) Отладка
за “столом” – просмотреть программу,
проверить

б) Программный
способ отладки – эхо — печать входных
данных, печать в ветвях, узлах программы.

Это
расстановка в тексте программы отладочных
печатей промежуточных результатов
вычислений, позволяющих проследить
логический и арифметический следы
программы, то есть каким образом она
выполнялась и что она вычисляла.
Отладочные печати ставятся в узловых
точках (это такие точки, в которых
переменные меняют свои значения)
программы, позволяющих контролировать
ошибки ввода (эхо – печать введенных
данных), результаты вычислительных
операций и логику работы программы или
отдельных ее частей, то есть понять,
когда были получены неправильные
значения. Например, такой отладочный
вывод следует предусмотреть до и после
завершения цикла некоторого массива
значений.

в)
Интегрированные средства отладки

Большинство
современных средств программирования
включают средства отладки. Они позволяют:
предусматривать точки останова, выполнять
программу по шагам, отображать содержимое
любых переменных при пошаговом выполнении.

Общая
методика отладки программы:

Изучение проявления ошибки (метод
индукции – выявление симптомов ошибки,
выдвижение гипотезы, дедукции – выявление
причин, затем исключение тех причин,
которые противоречат имеющимся данным)

Локализация
ошибки (методом отсечения программы,
отладочными средствами)

Определение
причин ошибки (благодаря отладочным
средствам)

Исправление
ошибки

Повторное
тестирование

Соседние файлы в папке Экзамен

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
Источник

Семантические ошибки в программировании

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

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

Поскольку языки программирования — это тоже языки, то и правила и термины лингвистики точно также применимы и к языкам программирования. А семантика в языке программирования означает то же самое, что и в человеческом языке, например, в русском.

Семантика определяет смысл программы, а семантические ошибки связаны с нарушением смысла программы. То есть семантические ошибки нарушают логику программы (поэтому я и назвал их ранее логическими).

С точки зрения синтаксиса программа может быть безупречной. И даже во время выполнения в ней может не быть никаких ошибок. Но при этом она может быть бессмысленна с точки зрения решаемой задачи.

Например, вам надо было написать программу, которая вычисляет площадь круга. А вы “немного” ошиблись, и ваша программа вычисляет площадь прямоугольника.

При этом:

  • Программа компилируется без ошибок
  • Программа запускается, работает и завершается без ошибок
  • Программа получает данные, обрабатывает их и выдаёт результат

Но, что самое страшное — пользователь думает, что результат правильный!!!

То есть программа безупречна во всём. Кроме одного — она решает не ту задачу, которую нужно решить пользователю. Поэтому с точки зрения пользователя она бессмысленна.

А с точки зрения программиста она содержит семантическую ошибку.

Такая программа делает не то, что вы от неё хотели, а то, что вы ей сказали. Вы ей сказали вычислять площадь прямоугольника, и она делает это. И это не её вина, а ваша. Вы дали неправильное указание.

Кстати, плохие руководители в жизни ведут себя точно также — дают сотрудникам неправильные или неоднозначные распоряжения, а потом удивляются, что работа выполнена неправильно. И обвиняют в этом, конечно, сотрудников.

Находить семантические ошибки бывает очень трудно. Особенно в чужих программах. Я это знаю не понаслышке. Иногда на это уходит несколько дней или даже недель. Иногда вообще хочется плюнуть на это и написать новую программу.

Так что старайтесь ещё до того, как начнёте писать код, тщательно продумать алгоритмы и прочие способы решения задачи, чтобы потом не было мучительно больно при поиске таких ошибок, которые не видит компилятор, и мучительно стыдно перед заказчиком.

А на сегодня всё. Подключайтесь к каналу в Телеграм или к другим моим группам, чтобы ничего не пропустить.

Основы программирования

 Основы программирования
Каждый профессионал когда-то был чайником. Наверняка вам знакомо состояние, когда “не знаешь как начать думать, чтобы до такого додуматься”. Наверняка вы сталкивались с ситуацией, когда вы просто не знаете, с чего начать.
Эта книга ориентирована как раз на таких людей, кто хотел бы стать программистом, но совершенно не знает, как начать этот путь.
Подробнее…
Источник

The third type of error is the semantic error, also called a logic error. If there is a semantic error
in your program, it will run successfully in the sense that the computer will
not generate any error messages. However, your program will not do the right thing. It will do
something else. Specifically, it will do what you told it to do, not what you wanted it to do.

The following program has a semantic error. Execute it to see what goes wrong:

This program runs and produces a result. However, the result is not what the programmer intended. It contains
a semantic error. The error is that the program performs concatenation instead of addition, because the programmer
failed to write the code necessary to convert the inputs to integers.

With semantic errors, the problem is that the program you wrote is not the program you wanted to
write. The meaning of the program (its semantics) is wrong. The computer is
faithfully carrying out the instructions you wrote, and its results
are correct, given the instructions that you provided. However, because your instructions
have a flaw in their design, the program does not behave as desired.

Identifying semantic errors can be tricky because no error message appears to make it obvious that the results are
incorrect. The only way you can detect semantic errors is if you know in advance what the program should do for a given set
of input. Then, you run the program with that input data and compare the output of the program with what you expect. If
there is a discrepancy between the actual output and the expected output, you can conclude that there is either 1) a
semantic error or 2) an error in your expected results.

Once you’ve determined that you have a semantic error, locating it can be tricky because you must work
backward by looking at the output of the program and trying to figure out what it is doing.

3.7.1. Test Cases¶

To detect a semantic error in your program, you need the help of something called a test case.

Test Case

A test case is a set of input values for the program, together with the output that you expect the program should produce when it is run with those particular
inputs.

Here is an example of a test case for the program above:

Test Case
---------
Input: 2, 3
Expected Output: 5

If you give this test case to someone and ask them to test the program, they can type in the inputs, observe the output,
check it against the expected output, and determine whether a semantic error exists based on whether the actual output
matches the expected output or not. The tester doesn’t even have to know what the program is supposed to do. For this reason,
software companies often have separate quality assurance departments whose responsibility is to check that the programs written
by the programmers perform as expected. The testers don’t have to be programmers; they just have to be able to operate the
program and compare its results with the test cases they’re given.

In this case, the program is so simple that we don’t need to write down a test case at all; we can compute the expected output
in our heads with very little effort. More complicated programs require effort to create the test case (since you shouldn’t use
the program to compute the expected output; you have to do it with a calculator or by hand), but the effort pays off when
the test case helps you to identify a semantic error that you didn’t know existed.

Semantic errors are the most dangerous of the three types of errors, because in some cases they are not noticed by either
the programmers or the users who use the program. Syntax errors cannot go undetected (the program won’t run at all if
they exist), and runtime errors are usually also obvious and typically detected by developers before a program is
released for use (although it is possible for a runtime error to occur for some inputs and not for
others, so these can sometimes remain undetected for a while). However, programs often go for years with undetected
semantic errors; no one realizes that the program has been producing incorrect results. They just assume that because the
results seem reasonable, they are correct. Sometimes, these errors are relatively harmless. But if they involve
financial transactions or medical equipment, the results can be harmful or even deadly. For this reason, creating test
cases is an important part of the work that programmers perform in order to help them produce programs that work
correctly.

Check your understanding

    Which of the following is a semantic error?

  • Attempting to divide by 0.
  • A semantic error is an error in logic. In this case the program does not produce the correct output because the problem is not solved correctly. This would be considered a run-time error.
  • Forgetting a semi-colon at the end of a statement where one is required.
  • A semantic error is an error in logic. In this case the program does not produce the correct output because the code can not be processed by the compiler or interpreter. This would be considered a syntax error.
  • Forgetting to divide by 100 when printing a percentage amount.
  • This will produce the wrong answer because the programmer implemented the solution incorrectly. This is a semantic error.

    Who or what typically finds semantic errors?

  • The programmer.
  • You must fully understand the problem so the you can tell if your program properly solves it.
  • The compiler / interpreter.
  • The compiler and / or interpreter will only do what you instruct it to do. It does not understand what the problem is that you want to solve.
  • The computer.
  • The computer does not understand your problem. It just executes the instructions that it is given.
  • The teacher / instructor.
  • Your teacher and instructor may be able to find most of your semantic errors, but only because they have experience solving problems. However it is your responsibility to understand the problem so you can develop a correct solution.

You have attempted of activities on this page

Источник

The third type of error is the semantic error, also called a logic error. If there is a semantic error
in your program, it will run successfully in the sense that the computer will
not generate any error messages. However, your program will not do the right thing. It will do
something else. Specifically, it will do what you told it to do, not what you wanted it to do.

The following program has a semantic error. Execute it to see what goes wrong:

This program runs and produces a result. However, the result is not what the programmer intended. It contains
a semantic error. The error is that the program performs concatenation instead of addition, because the programmer
failed to write the code necessary to convert the inputs to integers.

With semantic errors, the problem is that the program you wrote is not the program you wanted to
write. The meaning of the program (its semantics) is wrong. The computer is
faithfully carrying out the instructions you wrote, and its results
are correct, given the instructions that you provided. However, because your instructions
have a flaw in their design, the program does not behave as desired.

Identifying semantic errors can be tricky because no error message appears to make it obvious that the results are
incorrect. The only way you can detect semantic errors is if you know in advance what the program should do for a given set
of input. Then, you run the program with that input data and compare the output of the program with what you expect. If
there is a discrepancy between the actual output and the expected output, you can conclude that there is either 1) a
semantic error or 2) an error in your expected results.

Once you’ve determined that you have a semantic error, locating it can be tricky because you must work
backward by looking at the output of the program and trying to figure out what it is doing.

3.7.1. Test Cases¶

To detect a semantic error in your program, you need the help of something called a test case.

Test Case

A test case is a set of input values for the program, together with the output that you expect the program should produce when it is run with those particular
inputs.

Here is an example of a test case for the program above:

Test Case
---------
Input: 2, 3
Expected Output: 5

If you give this test case to someone and ask them to test the program, they can type in the inputs, observe the output,
check it against the expected output, and determine whether a semantic error exists based on whether the actual output
matches the expected output or not. The tester doesn’t even have to know what the program is supposed to do. For this reason,
software companies often have separate quality assurance departments whose responsibility is to check that the programs written
by the programmers perform as expected. The testers don’t have to be programmers; they just have to be able to operate the
program and compare its results with the test cases they’re given.

In this case, the program is so simple that we don’t need to write down a test case at all; we can compute the expected output
in our heads with very little effort. More complicated programs require effort to create the test case (since you shouldn’t use
the program to compute the expected output; you have to do it with a calculator or by hand), but the effort pays off when
the test case helps you to identify a semantic error that you didn’t know existed.

Semantic errors are the most dangerous of the three types of errors, because in some cases they are not noticed by either
the programmers or the users who use the program. Syntax errors cannot go undetected (the program won’t run at all if
they exist), and runtime errors are usually also obvious and typically detected by developers before a program is
released for use (although it is possible for a runtime error to occur for some inputs and not for
others, so these can sometimes remain undetected for a while). However, programs often go for years with undetected
semantic errors; no one realizes that the program has been producing incorrect results. They just assume that because the
results seem reasonable, they are correct. Sometimes, these errors are relatively harmless. But if they involve
financial transactions or medical equipment, the results can be harmful or even deadly. For this reason, creating test
cases is an important part of the work that programmers perform in order to help them produce programs that work
correctly.

Check your understanding

    Which of the following is a semantic error?

  • Attempting to divide by 0.
  • A semantic error is an error in logic. In this case the program does not produce the correct output because the problem is not solved correctly. This would be considered a run-time error.
  • Forgetting a semi-colon at the end of a statement where one is required.
  • A semantic error is an error in logic. In this case the program does not produce the correct output because the code can not be processed by the compiler or interpreter. This would be considered a syntax error.
  • Forgetting to divide by 100 when printing a percentage amount.
  • This will produce the wrong answer because the programmer implemented the solution incorrectly. This is a semantic error.

    Who or what typically finds semantic errors?

  • The programmer.
  • You must fully understand the problem so the you can tell if your program properly solves it.
  • The compiler / interpreter.
  • The compiler and / or interpreter will only do what you instruct it to do. It does not understand what the problem is that you want to solve.
  • The computer.
  • The computer does not understand your problem. It just executes the instructions that it is given.
  • The teacher / instructor.
  • Your teacher and instructor may be able to find most of your semantic errors, but only because they have experience solving problems. However it is your responsibility to understand the problem so you can develop a correct solution.

You have attempted of activities on this page

Источник

Dyslexia (Acquired) and Agraphia

M. Coltheart, in International Encyclopedia of the Social & Behavioral Sciences, 2001

1.6 Deep Dyslexia

This acquired dyslexia is reviewed in detail by Coltheart et al. (1980). Its cardinal symptom is the semantic error in reading aloud. When single isolated words are presented for reading aloud with no time pressure, the deep dyslexic will often produce as a response a word that is related in meaning, but in no other way, to the word he or she is looking at: dinner→‘food,’ uncle→‘cousin,’ and close→‘shut’ are examples of the semantic errors made by the deep dyslexic GR (Coltheart et al. 1980). Visual errors such as quarrel→‘squirrel’ or angle→‘angel,’ and morphological errors such as running→‘runner’ or unreal→‘real,’ are also seen. Concrete (highly-imageable) words such as tulip or green are much more likely to be successfully read than abstract (difficult-to-image) words such as idea or usual. Function words such as and, the, or or are very poorly read. Nonwords such as vib or ap cannot be read aloud at all.

As noted above, Marshall and Newcombe (1973) proposed that different forms of acquired dyslexia might be interpretable as consequences of specific different patterns of breakdown within a multicomponent model of the normal skilled reading system. That kind of interpretation has also been offered for deep dyslexia, by Morton and Patterson (1980). However, this way of approaching the explanation of deep dyslexia was rejected by Coltheart (1980) and Saffran et al. (1980), who proposed that deep dyslexic reading was not accomplished by an impaired version of the normal skilled reading system, located in the left hemisphere of the brain, but relied instead on reading mechanisms located in the intact right hemisphere.

Subsequent research has strongly favored the right-hemisphere interpretation of deep dyslexia. Patterson et al. (1987) report the case of an adolescent girl who developed a left-hemisphere pathology that necessitated removal of her left hemisphere. Before the onset of the brain disorder, she was apparently a normal reader for her age; after the removal of her left hemisphere, she was a deep dyslexic. Michel et al. (1996) report the case of a 23-year-old man who as a result of neurosurgery was left with a lesion of the posterior half of the corpus callosum. They studied his ability to read tachistoscopically displayed words presented to the left or right visual hemifields. With right hemifield (left hemisphere) presentation, his reading was normal. With left hemifield (right hemisphere) presentation, his reading showed all the symptoms of deep dyslexia. In a brain imaging study, Weekes et al. (1997) found that brain activation associated with visual word recognition was greater in the right than the left hemisphere for a deep dyslexic, but not for a surface dyslexic, nor for two normal readers.

It seems clear, then, that deep dyslexia is unlike all the other patterns of acquired dyslexia discussed here, in that deep dyslexics do not read via some damaged version of the normal (left-hemisphere) reading system, whereas patients with other forms of acquired dyslexia do.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B0080430767035816

The Development Process

Heinz Züllighoven, in Object-Oriented Construction Handbook, 2005

DISCUSSION

Advantages of pair programming

Pair programming has several advantages:

•

It can improve the quality of the source code, because two people work together. There is a greater chance that concepts and programming conventions will be maintained. Formal and semantic errors are usually discovered right away.

•

When pairs change systematically, knowledge about the overall system is dispersed throughout the team. The departure or unavailability of a developer thus has no serious effect on project progress.

•

The developers frequently question design decisions. Any blocked thinking or dead ends are avoided in development.

Pair programming for team training

In addition to these advantages, which mainly apply to homogeneous pairs, pair programming can also be used for team training. For example, an experienced programmer works with the new team member in pairs. Two things are important when using pair programming for team training:

•

New team members should have good basic programming knowledge; this is particularly important for retraining in a new technology. Without minimum qualification and experience, the gap between experienced and novice team members is too great, with the result that the inexperienced person does not understand the work at hand and is usually too timid to ask questions.

•

Experienced programmers should keep an eye on the training task assigned to them. It should be made clear that this task does not focus on development work.

Training in pairs is efficient, but it requires a high degree of patience and discipline from the experienced programmer. We have successfully used this approach in projects and found that the technical and domain knowledge of new team members was quickly brought up to the level of the other members.

Pair programming develops its full potential when used in conjunction with refactoring (see Section 12.3.5), design by contract (see Section 2.3), test classes (see Section 12.4.2), continuous integration, and collective ownership. Continuous integration simply means that sources that have been changed are integrated as quickly as possible. Integration should take place several times a day during the construction phase.

Collective ownership means that each developer may basically change all documents and source texts of a project at any time. The overall project knowledge required for this can be disseminated effectively in pair programming.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9781558606876500128

Multiobjective Optimization for Software Refactoring and Evolution

Ali Ouni, … Houari Sahraoui, in Advances in Computers, 2014

5.1 Approach Overview

Our approach aims at exploring a huge search space to find refactoring solutions, i.e., sequence of refactoring operations, to correct bad smells. In fact, the search space is determined not only by the number of possible refactoring combinations but also by the order in which they are applied. Thus, a heuristic-based optimization method is used to generate refactoring solutions. We have four objectives to optimize: (1) maximize quality improvement (bad-smells correction), (2) minimize the number of semantic errors by preserving the way how code elements are semantically grouped and connected together, (3) minimize code changes needed to apply refactoring, and (4) maximize the consistency with development change history. To this end, we consider the refactoring as a multiobjective optimization problem instead of a single-objective one using the NSGA-II [50].

Our approach takes as inputs a source code of the program to be refactored, a list of possible refactorings that can be applied, a set of bad-smells detection rules [21,24], our technique for approximating code changes needed to apply refactorings, a set of semantic measures, and a history of applied refactorings to previous versions of the system. Our approach generates as output the optimal sequence of refactorings, selected from an exhaustive list of possible refactorings, that improve the software quality by minimizing as much as possible the number of design defects, minimize code change needed to apply refactorings, preserve semantic coherence, and maximize the consistency with development change history.

In the following, we describe the formal formulation of our four objectives to optimize.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780128001615000049

Infrastructure and technology

Krish Krishnan, in Building Big Data Applications, 2020

Execution—how does Hive process queries?

A HiveQL statement is submitted via the CLI, the web UI, or an external client using the Thrift, ODBC, or JDBC API. The driver first passes the query to the compiler where it goes through parse, type check, and semantic analysis using the metadata stored in the metastore. The compiler generates a logical plan that is then optimized through a simple rule–based optimizer. Finally an optimized plan in the form of a DAG of mapreduce tasks and HDFS tasks is generated. The execution engine then executes these tasks in the order of their dependencies, using Hadoop.

We can further analyze this workflow of processing as follows:

•

Hive client triggers a query

•

Compiler receives the query and connects to metastore

•

Compiler receives the query and initiates the first phase of compilation

•

Parser—Converts the query into parse tree representation. Hive uses ANTLR to generate the abstract syntax tree (AST)

•

Semantic Analyzer—In this stage the compiler builds a logical plan based on the information that is provided by the metastore on the input and output tables. Additionally the complier also checks type compatibilities in expressions and flags compile time semantic errors at this stage. The best step is the transformation of an AST to intermediate representation that is called the query block (QB) tree. Nested queries are converted into parent–child relationships in a QB tree during this stage

•

Logical Plan Generator—In this stage the compiler writes the logical plan from the semantic analyzer into a logical tree of operations

•

Optimization—This is the most involved phase of the complier as the entire series of DAG optimizations are implemented in this phase. There are several customizations than can be done to the complier if desired. The primary operations done at this stage are as follows:

—

Logical optimization—Perform multiple passes over logical plan and rewrites in several ways

—

Column pruning—This optimization step ensures that only the columns that are needed in the query processing are actually projected out of the row

—

Predicate pushdown—Predicates are pushed down to the scan if possible so that rows can be filtered early in the processing

—

Partition pruning—Predicates on partitioned columns are used to prune out files of partitions that do not satisfy the predicate

—

Join optimization

—

Grouping and regrouping

—

Repartitioning

—

Physical plan generator converts logical plan into physical.

—

Physical plan generation creates the final DAG workflow of MapReduce

•

Execution engine gets the compiler outputs to execute on the Hadoop platform.

—

All the tasks are executed in the order of their dependencies. Each task is only executed if all of its prerequisites have been executed.

—

A map/reduce task first serializes its part of the plan into a plan.xml file.

—

This file is then added to the job cache for the task and instances of ExecMapper and ExecReducers are spawned using Hadoop.

—

Each of these classes deserializes the plan.xml and executes the relevant part of the task.

—

The final results are stored in a temporary location and at the completion of the entire query, the results are moved to the table if inserts or partitions, or returned to the calling program at a temporary location

The comparison between how Hive executes versus a traditional RDBMS shows that due to the schema on read design, the data placement, partitioning, joining, and storage can be decided at the execution time rather than planning cycles.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780128157466000028

Data Types

Michael L. Scott, in Programming Language Pragmatics (Third Edition), 2009

Coercion

Example 7.27

Coercion in Ada

Whenever a language allows a value of one type to be used in a context that expects another, the language implementation must perform an automatic, implicit conversion to the expected type. This conversion is called a type coercion. Like the explicit conversions discussed above, a coercion may require run-time code to perform a dynamic semantic check, or to convert between low-level representations. Ada coercions sometimes need the former, though never the latter:

d : weekday;  — as in Example 7.3

k : workday;  — as in Example 7.9

type calendar_column is new weekday;

c : calendar_column;

…

k := d; — run-time check required

d := k; — no check required; every workday is a weekday

c := d; — static semantic error;

   — weekdays and calendar_columns are not compatible

To perform this third assignment in Ada we would have to use an explicit conversion:

c := calendar_column(d);

Example 7.28

Coercion in C

As we noted in Section 3.5.3, coercions are a controversial subject in language design. Because they allow types to be mixed without an explicit indication of intent on the part of the programmer, they represent a significant weakening of type security. C, which has a relatively weak type system, performs quite a bit of coercion. It allows values of most numeric types to be intermixed in expressions, and will coerce types back and forth “as necessary.” Here are some examples:

short int s;

unsigned long int l;

char c; /* may be signed or unsigned — implementation-dependent */

float f; /* usually IEEE single-precision */

double d;  /* usually IEEE double-precision */

…

s = l; /* l’s low-order bits are interpreted as a signed number. */

l = s; /* s is sign-extended to the longer length, then

   its bits are interpreted as an unsigned number. */

s = c; /* c is either sign-extended or zero-extended to s’s length;

   the result is then interpreted as a signed number. */

f = l; /* l is converted to floating-point. Since f has fewer

   significant bits, some precision may be lost. */

d = f; /* f is converted to the longer format; no precision lost. */

f = d; /* d is converted to the shorter format; precision may be lost.

   If d’s value cannot be represented in single-precision, the

   result is undefined, but NOT a dynamic semantic error. */

Fortran 90 allows arrays and records to be intermixed if their types have the same shape. Two arrays have the same shape if they have the same number of dimensions, each dimension has the same size (i.e., the same number of elements), and the individual elements have the same shape. (In some other languages, the actual bounds of each dimension must be the same for the shapes to be considered the same.) Two records have the same shape if they have the same number of fields, and corresponding fields, in order, have the same shape. Field names do not matter, nor do the actual high and low bounds of array dimensions.

Ada’s compatibility rules for arrays are roughly equivalent to those of Fortran 90. C provides no operations that take an entire array as an operand. C does, however, allow arrays and pointers to be intermixed in many cases; we will discuss this unusual form of type compatibility further in Section 7.7.1. Neither Ada nor C allows records (structures) to be intermixed unless their types are name equivalent.

In general, modern compiled languages display a trend toward static typing and away from type coercion. Some language designers have argued, however, that coercions are a natural way in which to support abstraction and program extensibility, by making it easier to use new types in conjunction with existing ones. This ease-of-programming argument is particularly important for scripting languages (Chapter 13). Among more traditional languages, C++ provides an extremely rich, programmer-extensible set of coercion rules. When defining a new type (a class in C++), the programmer can define coercion operations to convert values of the new type to and from existing types. These rules interact in complicated ways with the rules for resolving overloading (Section 3.5.2); they add significant flexibility to the language, but are one of the most difficult C++ features to understand and use correctly.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780123745149000173

Programming Language Syntax

Michael L. Scott, in Programming Language Pragmatics (Third Edition), 2009

2.3.4 Syntax Errors

Example 2.42

A Syntax Error in C

Suppose we are parsing a C program and see the following code fragment in a context where a statement is expected:

A = B : C + D;

We will detect a syntax error immediately after the B, when the colon appears from the scanner. At this point the simplest thing to do is just to print an error message and halt. This naive approach is generally not acceptable, however: it would mean that every run of the compiler reveals no more than one syntax error. Since most programs, at least at first, contain numerous such errors, we really need to find as many as possible now (we’d also like to continue looking for semantic errors). To do so, we must modify the state of the parser and/or the input stream so that the upcoming token(s) are acceptable. We shall probably want to turn off code generation, disabling the back end of the compiler: since the input is not a valid program, the code will not be of use, and there’s no point in spending time creating it.

In general, the term syntax error recovery is applied to any technique that allows the compiler, in the face of a syntax error, to continue looking for other errors later in the program. High-quality syntax error recovery is essential in any production-quality compiler. The better the recovery technique, the more likely the compiler will be to recognize additional errors (especially nearby errors) correctly, and the less likely it will be to become confused and announce spurious cascading errors later in the program.

In More Depth

On the PLP CD we explore several possible approaches to syntax error recovery. In panic mode, the compiler writer defines a small set of “safe symbols” that delimit clean points in the input. Semicolons, which typically end a statement, are a good choice in many languages. When an error occurs, the compiler deletes input tokens until it finds a safe symbol, and then “backs the parser out” (e.g., returns from recursive descent subroutines) until it finds a context in which that symbol might appear. Phrase-level recovery improves on this technique by employing different sets of “safe” symbols in different productions of the grammar (right parentheses when in an expression; semicolons when in a declaration). Context-specific look-ahead obtains additional improvements by differentiating among the various contexts in which a given production might appear in a syntax tree. To respond gracefully to certain common programming errors, the compiler writer may augment the grammar with error productions that capture language-specific idioms that are incorrect but are often written by mistake.

Niklaus Wirth published an elegant implementation of phrase-level and context-specific recovery for recursive descent parsers in 1976 [Wir76, Sec. 5.9]. Exceptions (to be discussed further in Section 8.5) provide a simpler alternative if supported by the language in which the compiler is written. For table-driven top-down parsers, Fischer, Milton, and Quiring published an algorithm in 1980 that automatically implements a well-defined notion of locally least-cost syntax repair. Locally least-cost repair is also possible in bottom-up parsers, but it is significantly more difficult. Most bottom-up parsers rely on more straightforward phrase-level recovery; a typical example can be found in Yacc/bison.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780123745149000112

Introduction

Michael L. Scott, in Programming Language Pragmatics (Third Edition), 2009

1.8 Exercises

1.1

Errors in a computer program can be classified according to when they are detected and, if they are detected at compile time, what part of the compiler detects them. Using your favorite imperative language, give an example of each of the following.

(a)

A lexical error, detected by the scanner

(b)

A syntax error, detected by the parser

(c)

A static semantic error, detected by semantic analysis

(d)

A dynamic semantic error, detected by code generated by the compiler

(e)

An error that the compiler can neither catch nor easily generate code to catch (this should be a violation of the language definition, not just a program bug)

1.2

Consider again the Pascal tool set distributed by Niklaus Wirth (Example 1.15). After successfully building a machine language version of the Pascal compiler, one could in principle discard the P-code interpreter and the P-code version of the compiler. Why might one choose not to do so?

1.3

Imperative languages like Fortran and C are typically compiled, while scripting languages, in which many issues cannot be settled until run time, are typically interpreted. Is interpretation simply what one “has to do” when compilation is infeasible, or are there actually some advantages to interpreting a language, even when a compiler is available?

1.4

The gcd program of Example 1.20 might also be written

int main() {

 int i = getint(), j = getint();

 while (i != j) {

 if (i > j) i = i % j;

 else j = j % i;

 }

 putint(i);

}

Does this program compute the same result? If not, can you fix it? Under what circumstances would you expect one or the other to be faster?

1.5

In your local implementation of C, what is the limit on the size of integers? What happens in the event of arithmetic overflow? What are the implications of size limits on the portability of programs from one machine/compiler to another? How do the answers to these questions differ for Java? For Ada? For Pascal? For Scheme? (You may need to find a manual.)

1.6

The Unix make utility allows the programmer to specify dependences among the separately compiled pieces of a program. If file A depends on file B and file B is modified, make deduces that A must be recompiled, in case any of the changes to B would affect the code produced for A. How accurate is this sort of dependence management? Under what circumstances will it lead to unnecessary work? Under what circumstances will it fail to recompile something that needs to be recompiled?

1.7

Why is it difficult to tell whether a program is correct? How do you go about finding bugs in your code? What kinds of bugs are revealed by testing? What kinds of bugs are not? (For more formal notions of program correctness, see the bibliographic notes at the end of Chapter 4.)

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780123745149000100

Names, Scopes, and Bindings

Michael L. Scott, in Programming Language Pragmatics (Third Edition), 2009

3.3.3 Declaration Order

In our discussion so far we have glossed over an important subtlety: suppose an object x is declared somewhere within block B. Does the scope of x include the portion of B before the declaration, and if so can x actually be used in that portion of the code? Put another way, can an expression E refer to any name declared in the current scope, or only to names that are declared before E in the scope?

Several early languages, including Algol 60 and Lisp, required that all declarations appear at the beginning of their scope. One might at first think that this rule would avoid the questions in the preceding paragraph, but it does not, because declarations may refer to one another.7

Example 3.7

A “Gotcha” in Declare-Before-Use

In an apparent attempt to simplify the implementation of the compiler, Pascal modified the requirement to say that names must be declared before they are used (with special-case mechanisms to accommodate recursive types and subroutines). At the same time, however, Pascal retained the notion that the scope of a declaration is the entire surrounding block. These two rules can interact in surprising ways:

1.

const N = 10;

2.

…

3.

procedure foo;

4.

const

5.

 M = N; (* static semantic error! *)

6.

 …

7.

 N = 20; (* local constant declaration; hides the outer N *)

Pascal says that the second declaration of N covers all of foo, so the semantic analyzer should complain on line 5 that N is being used before its declaration. The error has the potential to be highly confusing, particularly if the programmer meant to use the outer N:

const N = 10;

…

procedure foo;

const

 M = N; (* static semantic error! *)

var

 A : array [1..M] of integer;

 N : real; (* hiding declaration *)

Here the pair of messages “N used before declaration” and “N is not a constant” are almost certainly not helpful.

In order to determine the validity of any declaration that appears to use a name from a surrounding scope, a Pascal compiler must scan the remainder of the scope’s declarations to see if the name is hidden. To avoid this complication, most Pascal successors (and some dialects of Pascal itself) specify that the scope of an identifier is not the entire block in which it is declared (excluding holes), but rather the portion of that block from the declaration to the end (again excluding holes). If our program fragment had been written in Ada, for example, or in C, C++, or Java, no semantic errors would be reported. The declaration of M would refer to the first (outer) declaration of N.

Design & Implementation

Mutual Recursion

Some Algol 60 compilers were known to process the declarations of a scope in program order. This strategy had the unfortunate effect of implicitly outlawing mutually recursive subroutines and types, something the language designers clearly did not intend [Atk73].

Example 3.8

Whole-Block Scope in C#

C++ and Java further relax the rules by dispensing with the define-before-use requirement in many cases. In both languages, members of a class (including those that are not defined until later in the program text) are visible inside all of the class’s methods. In Java, classes themselves can be declared in any order. Interestingly, while C# echos Java in requiring declaration before use for local variables (but not for classes and members), it returns to the Pascal notion of whole-block scope. Thus the following is invalid in C#.

class A

 const int N = 10;

 void foo()

 const int M = N; // uses inner N before it is declared

 const int N = 20;

Example 3.9

“Local if written” in Python

Perhaps the simplest approach to declaration order, from a conceptual point of view, is that of Modula-3, which says that the scope of a declaration is the entire block in which it appears (minus any holes created by nested declarations), and that the order of declarations doesn’t matter. The principal objection to this approach is that programmers may find it counterintuitive to use a local variable before it is declared. Python takes the “whole block” scope rule one step further by dispensing with variable declarations altogether. In their place it adopts the unusual convention that the local variables of subroutine S are precisely those variables that are written by some statement in the (static) body of S. If S is nested inside of T, and the name x appears on the left-hand side of assignment statements in both S and T, then the x‘s are distinct: there is one in S and one in T. Non-local variables are read-only unless explicitly imported (using Python’s global statement). We will consider these conventions in more detail in Section 13.4.1, as part of a general discussion of scoping in scripting languages.

Example 3.10

Declaration Order in Scheme

In the interest of flexibility, modern Lisp dialects tend to provide several options for declaration order. In Scheme, for example, the letrec and let* constructs define scopes with, respectively, whole-block and declaration-to-end-of-block semantics. The most frequently used construct, let, provides yet another option:

(let ((A 1))  ; outer scope, with A defined to be 1

 (let ((A 2)  ; inner scope, with A defined to be 2

 (B A))  ;  and B defined to be A

 B))  ; return the value of B

Here the nested declarations of A and B don’t until after the end of the declaration list. Thus when B is defined, the redefinition of A has not yet taken effect. B is defined to be the outer A, and the code as a whole returns 1.

Declarations and Definitions

Example 3.11

Declarations vs Definitions in C

Recursive types and subroutines introduce a problem for languages that require names to be declared before they can be used: how can two declarations each appear before the other? C and C++ handle the problem by distinguishing between the declaration of an object and its definition. A declaration introduces a name and indicates its scope, but may omit certain implementation details. A definition describes the object in sufficient detail for the compiler to determine its implementation. If a declaration is not complete enough to be a definition, then a separate definition must appear somewhere else in the scope. In C we can write

struct manager;  /* declaration only */

struct employee {

 struct manager *boss;

 struct employee *next_employee;

 …

};

struct manager {  /* definition */

 struct employee *first_employee;

 …

};

and

void list_tail(follow_set fs);  /* declaration only */

void list(follow_set fs)

{

 switch (input_token) {

 case id : match(id); list_tail(fs);

 …

}

void list_tail(follow_set fs) /* definition */

{

 switch (input_token) {

 case comma : match(comma); list(fs);

 …

}

The initial declaration of manager needed only to introduce a name: since pointers are all the same size, the compiler could determine the implementation of employee without knowing any manager details. The initial declaration of list_tail, however, must include the return type and parameter list, so the compiler can tell that the call in list is correct.

Nested Blocks

In many languages, including Algol 60, C89, and Ada, local variables can be declared not only at the beginning of any subroutine, but also at the top of any begin…end ({…}) block. Other languages, including Algol 68, C99, and all of C’s descendants, are even more flexible, allowing declarations wherever a statement may appear. In most languages a nested declaration hides any outer declaration with the same name (Java and C# make it a static semantic error if the outer declaration is local to the current subroutine).

Example 3.12

Inner Declarations in C

Variables declared in nested blocks can be very useful, as for example in the following C code:

{

 int temp = a;

 a = b;

 b = temp;

}

Keeping the declaration of temp lexically adjacent to the code that uses it makes the program easier to read, and eliminates any possibility that this code will interfere with another variable named temp.

No run-time work is needed to allocate or deallocate space for variables declared in nested blocks; their space can be included in the total space for local variables allocated in the subroutine prologue and deallocated in the epilogue. Exercise 3.9 considers how to minimize the total space required.

Design & Implementation

Redeclarations

Some languages, particularly those that are intended for interactive use, permit the programmer to redeclare an object: to create a new binding for a given name in a given scope. Interactive programmers commonly use redeclarations to fix bugs. In most interactive languages, the new meaning of the name replaces the old in all contexts. In ML, however, the old meaning of the name may remain accessible to functions that were elaborated before the name was redeclared. This design choice in ML can sometimes be counterintuitive. It probably reflects the fact that ML is usually compiled, bit by bit on the fly, rather than interpreted. A language like Scheme, which is lexically scoped but usually interpreted, stores the binding for a name in a known location. A program accesses the meaning of the name indirectly through that location: if the meaning of the name changes, all accesses to the name will use the new meaning. In ML, previously elaborated functions have already been compiled into a form (often machine code) that accesses the meaning of the name directly.

Check Your Understanding

12.

What do we mean by the scope of a name-to-object binding?

13.

Describe the difference between static and dynamic scoping.

14.

What is elaboration?

15.

What is a referencing environment?

16.

Explain the closest nested scope rule.

17.

What is the purpose of a scope resolution operator?

18.

What is a static chain? What is it used for?

19.

What are forward references? Why are they prohibited or restricted in many programming languages?

20.

Explain the difference between a declaration and a definition. Why is the distinction important?

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780123745149000124

Named Entity Resolution in Social Media

Paul A. Watters, in Automating Open Source Intelligence, 2016

Discussion

In this chapter, I have sketched out two different algorithmic approaches that could be used undertake named entity resolution. The first takes a dynamical systems view of the machine translation process and how it can account for translations that either succeed or fail, and provides a metaphor for how dynamical system states can be related to single-pass translations using the iterative semantic processing paradigm. In the three examples presented in this chapter, I have demonstrated how dynamical system states correspond to the different kinds of translation errors of semantic material in the context of direct translations systems (e.g., word sense disambiguation of polysemous words). In terms of the absolute preservation of meaning across sentences, the aim of the translation system is to form a point attractor in a “translation space,” although we have also seen that for practical purposes, limit cycles are also acceptable. Unacceptable translations defined by the iterative method are those that rapidly lose information about their initial semantic conditions, perhaps by a translation system equivalent to the period-doubling route to chaos.

What is important about describing machine translation systems using this methodology is that it is possible to use these states as benchmarks for the performance of translation systems. Thus, when translation systems are modified to correct characteristic semantic errors, it is possible to directly assess the performance improvement by using the two statistical measures we have introduced in this chapter, the iterative information loss index, ILOSS, and the cumulative information losses, ITOTAL. An attempt to reduce errors at any particular translation stage can be monitored by examining ILOSS at that particular iteration – for example, some direct translation systems have excellent source→target dictionaries, but poor target→source dictionaries. Improvement of the latter can be tracked at iteration 2 (and indeed, all even-numbered iterations thereafter), with a reduction in ITOTAL after all translations being the main indicator of overall performance.

Obviously, computing these statistics from single sentences is misleading in the sense that they are drawn from larger discourse, and should always be considered with respect to their literary or linguistic origins. Discourse longer than single sentences or phrases is needed for measures of entropy or of information loss to become statistically reliable. In addition, the computation of numerical exponents to quantify the rate of information loss in terms of the system’s entropy (e.g., Lyapunov exponent) needs to be developed and applied to both single sentences and large corpora.

From a neural network perspective, the dynamics of resolving named entities has similarities to resolving the senses of polysemous terms, especially by taking advantage of local context through semantic priming. From the simple examples shown here, it should be obvious how similar contextual information could be used to resolve the identities of individual names on social media. A key question remains as to how such context can be readily gathered using an automated process: for semantic priming of polysemous terms, parameter estimates must be supplied to the model a priori, yet fully automated OSINT systems would not necessarily have trusted access (Tran, Watters, & Hitchens, 2005) to this kind of data. Future research is needed to determine the extent to which names can be automatically resolved, versus a set of candidate choices should be presented to a knowledgeable analyst.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780128029169000026

Fundamental Concepts

Peter J. Ashenden, in The Designer’s Guide to VHDL (Third Edition), 2008

1.4.5 Analysis, Elaboration and Execution

One of the main reasons for writing a model of a system is to enable us to simulate it. This involves three stages: analysis, elaboration and execution. Analysis and elaboration are also required in preparation for other uses of the model, such as logic synthesis.

In the first stage, analysis, the VHDL description of a system is checked for various kinds of errors. Like most programming languages, VHDL has rigidly defined syntax and semantics. The syntax is the set of grammatical rules that govern how a model is written. The rules of semantics govern the meaning of a program. For example, it makes sense to perform an addition operation on two numbers but not on two processes.

During the analysis phase, the VHDL description is examined, and syntactic and static semantic errors are located. The whole model of a system need not be analyzed at once. Instead, it is possible to analyze design units, such as entity and architecture body declarations, separately. If the analyzer finds no errors in a design unit, it creates an intermediate representation of the unit and stores it in a library. The exact mechanism varies between VHDL tools.

The second stage in simulating a model, elaboration, is the act of working through the design hierarchy and creating all of the objects defined in declarations. The ultimate product of design elaboration is a collection of signals and processes, with each process possibly containing variables. A model must be reducible to a collection of signals and processes in order to simulate it.

We can see how elaboration achieves this reduction by starting at the top level of a model, namely, an entity, and choosing an architecture of the entity to simulate. The architecture comprises signals, processes and component instances. Each component instance is a copy of an entity and an architecture that also comprises signals, processes and component instances. Instances of those signals and processes are created, corresponding to the component instance, and then the elaboration operation is repeated for the subcomponent instances. Ultimately, a component instance is reached that is a copy of an entity with a purely behavioral architecture, containing only processes. This corresponds to a primitive component for the level of design being simulated. Figure 1.7 shows how elaboration proceeds for the structural architecture body of the reg4 entity from Example 1.3. As each instance of a process is created, its variables are created and given initial values. We can think of each process instance as corresponding to one instance of a component.

Figure 1.7. The elaboration of the reg4 entity using the structural architecture body. Each instance of the d_ff and and2 entities is replaced with the contents of the corresponding basic architecture. These each consist of a process with its variables and statements.

The third stage of simulation is the execution of the model. The passage of time is simulated in discrete steps, depending on when events occur. Hence the term discrete event simulation is used. At some simulation time, a process may be stimulated by changing the value on a signal to which it is sensitive. The process is resumed and may schedule new values to be given to signals at some later simulated time. This is called scheduling a transaction on that signal. If the new value is different from the previous value on the signal, an event occurs, and other processes sensitive to the signal may be resumed.

The simulation starts with an initialization phase, followed by repetitive execution of a simulation cycle. During the initialization phase, each signal is given an initial value, depending on its type. The simulation time is set to zero, then each process instance is activated and its sequential statements executed. Usually, a process will include a signal assignment statement to schedule a transaction on a signal at some later simulation time. Execution of a process continues until it reaches a wait statement, which causes the process to be suspended.

During the simulation cycle, the simulation time is first advanced to the next time at which a transaction on a signal has been scheduled. Second, all the transactions scheduled for that time are performed. This may cause some events to occur on some signals. Third, all processes that are sensitive to those events are resumed and are allowed to continue until they reach a wait statement and suspend. Again, the processes usually execute signal assignments to schedule further transactions on signals. When all the processes have suspended again, the simulation cycle is repeated. When the simulation gets to the stage where there are no further transactions scheduled, it stops, since the simulation is then complete.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780120887859000010

Источник

Dyslexia (Acquired) and Agraphia

M. Coltheart, in International Encyclopedia of the Social & Behavioral Sciences, 2001

1.6 Deep Dyslexia

This acquired dyslexia is reviewed in detail by Coltheart et al. (1980). Its cardinal symptom is the semantic error in reading aloud. When single isolated words are presented for reading aloud with no time pressure, the deep dyslexic will often produce as a response a word that is related in meaning, but in no other way, to the word he or she is looking at: dinner→‘food,’ uncle→‘cousin,’ and close→‘shut’ are examples of the semantic errors made by the deep dyslexic GR (Coltheart et al. 1980). Visual errors such as quarrel→‘squirrel’ or angle→‘angel,’ and morphological errors such as running→‘runner’ or unreal→‘real,’ are also seen. Concrete (highly-imageable) words such as tulip or green are much more likely to be successfully read than abstract (difficult-to-image) words such as idea or usual. Function words such as and, the, or or are very poorly read. Nonwords such as vib or ap cannot be read aloud at all.

As noted above, Marshall and Newcombe (1973) proposed that different forms of acquired dyslexia might be interpretable as consequences of specific different patterns of breakdown within a multicomponent model of the normal skilled reading system. That kind of interpretation has also been offered for deep dyslexia, by Morton and Patterson (1980). However, this way of approaching the explanation of deep dyslexia was rejected by Coltheart (1980) and Saffran et al. (1980), who proposed that deep dyslexic reading was not accomplished by an impaired version of the normal skilled reading system, located in the left hemisphere of the brain, but relied instead on reading mechanisms located in the intact right hemisphere.

Subsequent research has strongly favored the right-hemisphere interpretation of deep dyslexia. Patterson et al. (1987) report the case of an adolescent girl who developed a left-hemisphere pathology that necessitated removal of her left hemisphere. Before the onset of the brain disorder, she was apparently a normal reader for her age; after the removal of her left hemisphere, she was a deep dyslexic. Michel et al. (1996) report the case of a 23-year-old man who as a result of neurosurgery was left with a lesion of the posterior half of the corpus callosum. They studied his ability to read tachistoscopically displayed words presented to the left or right visual hemifields. With right hemifield (left hemisphere) presentation, his reading was normal. With left hemifield (right hemisphere) presentation, his reading showed all the symptoms of deep dyslexia. In a brain imaging study, Weekes et al. (1997) found that brain activation associated with visual word recognition was greater in the right than the left hemisphere for a deep dyslexic, but not for a surface dyslexic, nor for two normal readers.

It seems clear, then, that deep dyslexia is unlike all the other patterns of acquired dyslexia discussed here, in that deep dyslexics do not read via some damaged version of the normal (left-hemisphere) reading system, whereas patients with other forms of acquired dyslexia do.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B0080430767035816

The Development Process

Heinz Züllighoven, in Object-Oriented Construction Handbook, 2005

DISCUSSION

Advantages of pair programming

Pair programming has several advantages:

•

It can improve the quality of the source code, because two people work together. There is a greater chance that concepts and programming conventions will be maintained. Formal and semantic errors are usually discovered right away.

•

When pairs change systematically, knowledge about the overall system is dispersed throughout the team. The departure or unavailability of a developer thus has no serious effect on project progress.

•

The developers frequently question design decisions. Any blocked thinking or dead ends are avoided in development.

Pair programming for team training

In addition to these advantages, which mainly apply to homogeneous pairs, pair programming can also be used for team training. For example, an experienced programmer works with the new team member in pairs. Two things are important when using pair programming for team training:

•

New team members should have good basic programming knowledge; this is particularly important for retraining in a new technology. Without minimum qualification and experience, the gap between experienced and novice team members is too great, with the result that the inexperienced person does not understand the work at hand and is usually too timid to ask questions.

•

Experienced programmers should keep an eye on the training task assigned to them. It should be made clear that this task does not focus on development work.

Training in pairs is efficient, but it requires a high degree of patience and discipline from the experienced programmer. We have successfully used this approach in projects and found that the technical and domain knowledge of new team members was quickly brought up to the level of the other members.

Pair programming develops its full potential when used in conjunction with refactoring (see Section 12.3.5), design by contract (see Section 2.3), test classes (see Section 12.4.2), continuous integration, and collective ownership. Continuous integration simply means that sources that have been changed are integrated as quickly as possible. Integration should take place several times a day during the construction phase.

Collective ownership means that each developer may basically change all documents and source texts of a project at any time. The overall project knowledge required for this can be disseminated effectively in pair programming.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9781558606876500128

Multiobjective Optimization for Software Refactoring and Evolution

Ali Ouni, … Houari Sahraoui, in Advances in Computers, 2014

5.1 Approach Overview

Our approach aims at exploring a huge search space to find refactoring solutions, i.e., sequence of refactoring operations, to correct bad smells. In fact, the search space is determined not only by the number of possible refactoring combinations but also by the order in which they are applied. Thus, a heuristic-based optimization method is used to generate refactoring solutions. We have four objectives to optimize: (1) maximize quality improvement (bad-smells correction), (2) minimize the number of semantic errors by preserving the way how code elements are semantically grouped and connected together, (3) minimize code changes needed to apply refactoring, and (4) maximize the consistency with development change history. To this end, we consider the refactoring as a multiobjective optimization problem instead of a single-objective one using the NSGA-II [50].

Our approach takes as inputs a source code of the program to be refactored, a list of possible refactorings that can be applied, a set of bad-smells detection rules [21,24], our technique for approximating code changes needed to apply refactorings, a set of semantic measures, and a history of applied refactorings to previous versions of the system. Our approach generates as output the optimal sequence of refactorings, selected from an exhaustive list of possible refactorings, that improve the software quality by minimizing as much as possible the number of design defects, minimize code change needed to apply refactorings, preserve semantic coherence, and maximize the consistency with development change history.

In the following, we describe the formal formulation of our four objectives to optimize.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780128001615000049

Infrastructure and technology

Krish Krishnan, in Building Big Data Applications, 2020

Execution—how does Hive process queries?

A HiveQL statement is submitted via the CLI, the web UI, or an external client using the Thrift, ODBC, or JDBC API. The driver first passes the query to the compiler where it goes through parse, type check, and semantic analysis using the metadata stored in the metastore. The compiler generates a logical plan that is then optimized through a simple rule–based optimizer. Finally an optimized plan in the form of a DAG of mapreduce tasks and HDFS tasks is generated. The execution engine then executes these tasks in the order of their dependencies, using Hadoop.

We can further analyze this workflow of processing as follows:

•

Hive client triggers a query

•

Compiler receives the query and connects to metastore

•

Compiler receives the query and initiates the first phase of compilation

•

Parser—Converts the query into parse tree representation. Hive uses ANTLR to generate the abstract syntax tree (AST)

•

Semantic Analyzer—In this stage the compiler builds a logical plan based on the information that is provided by the metastore on the input and output tables. Additionally the complier also checks type compatibilities in expressions and flags compile time semantic errors at this stage. The best step is the transformation of an AST to intermediate representation that is called the query block (QB) tree. Nested queries are converted into parent–child relationships in a QB tree during this stage

•

Logical Plan Generator—In this stage the compiler writes the logical plan from the semantic analyzer into a logical tree of operations

•

Optimization—This is the most involved phase of the complier as the entire series of DAG optimizations are implemented in this phase. There are several customizations than can be done to the complier if desired. The primary operations done at this stage are as follows:

—

Logical optimization—Perform multiple passes over logical plan and rewrites in several ways

—

Column pruning—This optimization step ensures that only the columns that are needed in the query processing are actually projected out of the row

—

Predicate pushdown—Predicates are pushed down to the scan if possible so that rows can be filtered early in the processing

—

Partition pruning—Predicates on partitioned columns are used to prune out files of partitions that do not satisfy the predicate

—

Join optimization

—

Grouping and regrouping

—

Repartitioning

—

Physical plan generator converts logical plan into physical.

—

Physical plan generation creates the final DAG workflow of MapReduce

•

Execution engine gets the compiler outputs to execute on the Hadoop platform.

—

All the tasks are executed in the order of their dependencies. Each task is only executed if all of its prerequisites have been executed.

—

A map/reduce task first serializes its part of the plan into a plan.xml file.

—

This file is then added to the job cache for the task and instances of ExecMapper and ExecReducers are spawned using Hadoop.

—

Each of these classes deserializes the plan.xml and executes the relevant part of the task.

—

The final results are stored in a temporary location and at the completion of the entire query, the results are moved to the table if inserts or partitions, or returned to the calling program at a temporary location

The comparison between how Hive executes versus a traditional RDBMS shows that due to the schema on read design, the data placement, partitioning, joining, and storage can be decided at the execution time rather than planning cycles.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780128157466000028

Data Types

Michael L. Scott, in Programming Language Pragmatics (Third Edition), 2009

Coercion

Example 7.27

Coercion in Ada

Whenever a language allows a value of one type to be used in a context that expects another, the language implementation must perform an automatic, implicit conversion to the expected type. This conversion is called a type coercion. Like the explicit conversions discussed above, a coercion may require run-time code to perform a dynamic semantic check, or to convert between low-level representations. Ada coercions sometimes need the former, though never the latter:

d : weekday;  — as in Example 7.3

k : workday;  — as in Example 7.9

type calendar_column is new weekday;

c : calendar_column;

…

k := d; — run-time check required

d := k; — no check required; every workday is a weekday

c := d; — static semantic error;

   — weekdays and calendar_columns are not compatible

To perform this third assignment in Ada we would have to use an explicit conversion:

c := calendar_column(d);

Example 7.28

Coercion in C

As we noted in Section 3.5.3, coercions are a controversial subject in language design. Because they allow types to be mixed without an explicit indication of intent on the part of the programmer, they represent a significant weakening of type security. C, which has a relatively weak type system, performs quite a bit of coercion. It allows values of most numeric types to be intermixed in expressions, and will coerce types back and forth “as necessary.” Here are some examples:

short int s;

unsigned long int l;

char c; /* may be signed or unsigned — implementation-dependent */

float f; /* usually IEEE single-precision */

double d;  /* usually IEEE double-precision */

…

s = l; /* l’s low-order bits are interpreted as a signed number. */

l = s; /* s is sign-extended to the longer length, then

   its bits are interpreted as an unsigned number. */

s = c; /* c is either sign-extended or zero-extended to s’s length;

   the result is then interpreted as a signed number. */

f = l; /* l is converted to floating-point. Since f has fewer

   significant bits, some precision may be lost. */

d = f; /* f is converted to the longer format; no precision lost. */

f = d; /* d is converted to the shorter format; precision may be lost.

   If d’s value cannot be represented in single-precision, the

   result is undefined, but NOT a dynamic semantic error. */

Fortran 90 allows arrays and records to be intermixed if their types have the same shape. Two arrays have the same shape if they have the same number of dimensions, each dimension has the same size (i.e., the same number of elements), and the individual elements have the same shape. (In some other languages, the actual bounds of each dimension must be the same for the shapes to be considered the same.) Two records have the same shape if they have the same number of fields, and corresponding fields, in order, have the same shape. Field names do not matter, nor do the actual high and low bounds of array dimensions.

Ada’s compatibility rules for arrays are roughly equivalent to those of Fortran 90. C provides no operations that take an entire array as an operand. C does, however, allow arrays and pointers to be intermixed in many cases; we will discuss this unusual form of type compatibility further in Section 7.7.1. Neither Ada nor C allows records (structures) to be intermixed unless their types are name equivalent.

In general, modern compiled languages display a trend toward static typing and away from type coercion. Some language designers have argued, however, that coercions are a natural way in which to support abstraction and program extensibility, by making it easier to use new types in conjunction with existing ones. This ease-of-programming argument is particularly important for scripting languages (Chapter 13). Among more traditional languages, C++ provides an extremely rich, programmer-extensible set of coercion rules. When defining a new type (a class in C++), the programmer can define coercion operations to convert values of the new type to and from existing types. These rules interact in complicated ways with the rules for resolving overloading (Section 3.5.2); they add significant flexibility to the language, but are one of the most difficult C++ features to understand and use correctly.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780123745149000173

Programming Language Syntax

Michael L. Scott, in Programming Language Pragmatics (Third Edition), 2009

2.3.4 Syntax Errors

Example 2.42

A Syntax Error in C

Suppose we are parsing a C program and see the following code fragment in a context where a statement is expected:

A = B : C + D;

We will detect a syntax error immediately after the B, when the colon appears from the scanner. At this point the simplest thing to do is just to print an error message and halt. This naive approach is generally not acceptable, however: it would mean that every run of the compiler reveals no more than one syntax error. Since most programs, at least at first, contain numerous such errors, we really need to find as many as possible now (we’d also like to continue looking for semantic errors). To do so, we must modify the state of the parser and/or the input stream so that the upcoming token(s) are acceptable. We shall probably want to turn off code generation, disabling the back end of the compiler: since the input is not a valid program, the code will not be of use, and there’s no point in spending time creating it.

In general, the term syntax error recovery is applied to any technique that allows the compiler, in the face of a syntax error, to continue looking for other errors later in the program. High-quality syntax error recovery is essential in any production-quality compiler. The better the recovery technique, the more likely the compiler will be to recognize additional errors (especially nearby errors) correctly, and the less likely it will be to become confused and announce spurious cascading errors later in the program.

In More Depth

On the PLP CD we explore several possible approaches to syntax error recovery. In panic mode, the compiler writer defines a small set of “safe symbols” that delimit clean points in the input. Semicolons, which typically end a statement, are a good choice in many languages. When an error occurs, the compiler deletes input tokens until it finds a safe symbol, and then “backs the parser out” (e.g., returns from recursive descent subroutines) until it finds a context in which that symbol might appear. Phrase-level recovery improves on this technique by employing different sets of “safe” symbols in different productions of the grammar (right parentheses when in an expression; semicolons when in a declaration). Context-specific look-ahead obtains additional improvements by differentiating among the various contexts in which a given production might appear in a syntax tree. To respond gracefully to certain common programming errors, the compiler writer may augment the grammar with error productions that capture language-specific idioms that are incorrect but are often written by mistake.

Niklaus Wirth published an elegant implementation of phrase-level and context-specific recovery for recursive descent parsers in 1976 [Wir76, Sec. 5.9]. Exceptions (to be discussed further in Section 8.5) provide a simpler alternative if supported by the language in which the compiler is written. For table-driven top-down parsers, Fischer, Milton, and Quiring published an algorithm in 1980 that automatically implements a well-defined notion of locally least-cost syntax repair. Locally least-cost repair is also possible in bottom-up parsers, but it is significantly more difficult. Most bottom-up parsers rely on more straightforward phrase-level recovery; a typical example can be found in Yacc/bison.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780123745149000112

Introduction

Michael L. Scott, in Programming Language Pragmatics (Third Edition), 2009

1.8 Exercises

1.1

Errors in a computer program can be classified according to when they are detected and, if they are detected at compile time, what part of the compiler detects them. Using your favorite imperative language, give an example of each of the following.

(a)

A lexical error, detected by the scanner

(b)

A syntax error, detected by the parser

(c)

A static semantic error, detected by semantic analysis

(d)

A dynamic semantic error, detected by code generated by the compiler

(e)

An error that the compiler can neither catch nor easily generate code to catch (this should be a violation of the language definition, not just a program bug)

1.2

Consider again the Pascal tool set distributed by Niklaus Wirth (Example 1.15). After successfully building a machine language version of the Pascal compiler, one could in principle discard the P-code interpreter and the P-code version of the compiler. Why might one choose not to do so?

1.3

Imperative languages like Fortran and C are typically compiled, while scripting languages, in which many issues cannot be settled until run time, are typically interpreted. Is interpretation simply what one “has to do” when compilation is infeasible, or are there actually some advantages to interpreting a language, even when a compiler is available?

1.4

The gcd program of Example 1.20 might also be written

int main() {

 int i = getint(), j = getint();

 while (i != j) {

 if (i > j) i = i % j;

 else j = j % i;

 }

 putint(i);

}

Does this program compute the same result? If not, can you fix it? Under what circumstances would you expect one or the other to be faster?

1.5

In your local implementation of C, what is the limit on the size of integers? What happens in the event of arithmetic overflow? What are the implications of size limits on the portability of programs from one machine/compiler to another? How do the answers to these questions differ for Java? For Ada? For Pascal? For Scheme? (You may need to find a manual.)

1.6

The Unix make utility allows the programmer to specify dependences among the separately compiled pieces of a program. If file A depends on file B and file B is modified, make deduces that A must be recompiled, in case any of the changes to B would affect the code produced for A. How accurate is this sort of dependence management? Under what circumstances will it lead to unnecessary work? Under what circumstances will it fail to recompile something that needs to be recompiled?

1.7

Why is it difficult to tell whether a program is correct? How do you go about finding bugs in your code? What kinds of bugs are revealed by testing? What kinds of bugs are not? (For more formal notions of program correctness, see the bibliographic notes at the end of Chapter 4.)

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780123745149000100

Names, Scopes, and Bindings

Michael L. Scott, in Programming Language Pragmatics (Third Edition), 2009

3.3.3 Declaration Order

In our discussion so far we have glossed over an important subtlety: suppose an object x is declared somewhere within block B. Does the scope of x include the portion of B before the declaration, and if so can x actually be used in that portion of the code? Put another way, can an expression E refer to any name declared in the current scope, or only to names that are declared before E in the scope?

Several early languages, including Algol 60 and Lisp, required that all declarations appear at the beginning of their scope. One might at first think that this rule would avoid the questions in the preceding paragraph, but it does not, because declarations may refer to one another.7

Example 3.7

A “Gotcha” in Declare-Before-Use

In an apparent attempt to simplify the implementation of the compiler, Pascal modified the requirement to say that names must be declared before they are used (with special-case mechanisms to accommodate recursive types and subroutines). At the same time, however, Pascal retained the notion that the scope of a declaration is the entire surrounding block. These two rules can interact in surprising ways:

1.

const N = 10;

2.

…

3.

procedure foo;

4.

const

5.

 M = N; (* static semantic error! *)

6.

 …

7.

 N = 20; (* local constant declaration; hides the outer N *)

Pascal says that the second declaration of N covers all of foo, so the semantic analyzer should complain on line 5 that N is being used before its declaration. The error has the potential to be highly confusing, particularly if the programmer meant to use the outer N:

const N = 10;

…

procedure foo;

const

 M = N; (* static semantic error! *)

var

 A : array [1..M] of integer;

 N : real; (* hiding declaration *)

Here the pair of messages “N used before declaration” and “N is not a constant” are almost certainly not helpful.

In order to determine the validity of any declaration that appears to use a name from a surrounding scope, a Pascal compiler must scan the remainder of the scope’s declarations to see if the name is hidden. To avoid this complication, most Pascal successors (and some dialects of Pascal itself) specify that the scope of an identifier is not the entire block in which it is declared (excluding holes), but rather the portion of that block from the declaration to the end (again excluding holes). If our program fragment had been written in Ada, for example, or in C, C++, or Java, no semantic errors would be reported. The declaration of M would refer to the first (outer) declaration of N.

Design & Implementation

Mutual Recursion

Some Algol 60 compilers were known to process the declarations of a scope in program order. This strategy had the unfortunate effect of implicitly outlawing mutually recursive subroutines and types, something the language designers clearly did not intend [Atk73].

Example 3.8

Whole-Block Scope in C#

C++ and Java further relax the rules by dispensing with the define-before-use requirement in many cases. In both languages, members of a class (including those that are not defined until later in the program text) are visible inside all of the class’s methods. In Java, classes themselves can be declared in any order. Interestingly, while C# echos Java in requiring declaration before use for local variables (but not for classes and members), it returns to the Pascal notion of whole-block scope. Thus the following is invalid in C#.

class A

 const int N = 10;

 void foo()

 const int M = N; // uses inner N before it is declared

 const int N = 20;

Example 3.9

“Local if written” in Python

Perhaps the simplest approach to declaration order, from a conceptual point of view, is that of Modula-3, which says that the scope of a declaration is the entire block in which it appears (minus any holes created by nested declarations), and that the order of declarations doesn’t matter. The principal objection to this approach is that programmers may find it counterintuitive to use a local variable before it is declared. Python takes the “whole block” scope rule one step further by dispensing with variable declarations altogether. In their place it adopts the unusual convention that the local variables of subroutine S are precisely those variables that are written by some statement in the (static) body of S. If S is nested inside of T, and the name x appears on the left-hand side of assignment statements in both S and T, then the x‘s are distinct: there is one in S and one in T. Non-local variables are read-only unless explicitly imported (using Python’s global statement). We will consider these conventions in more detail in Section 13.4.1, as part of a general discussion of scoping in scripting languages.

Example 3.10

Declaration Order in Scheme

In the interest of flexibility, modern Lisp dialects tend to provide several options for declaration order. In Scheme, for example, the letrec and let* constructs define scopes with, respectively, whole-block and declaration-to-end-of-block semantics. The most frequently used construct, let, provides yet another option:

(let ((A 1))  ; outer scope, with A defined to be 1

 (let ((A 2)  ; inner scope, with A defined to be 2

 (B A))  ;  and B defined to be A

 B))  ; return the value of B

Here the nested declarations of A and B don’t until after the end of the declaration list. Thus when B is defined, the redefinition of A has not yet taken effect. B is defined to be the outer A, and the code as a whole returns 1.

Declarations and Definitions

Example 3.11

Declarations vs Definitions in C

Recursive types and subroutines introduce a problem for languages that require names to be declared before they can be used: how can two declarations each appear before the other? C and C++ handle the problem by distinguishing between the declaration of an object and its definition. A declaration introduces a name and indicates its scope, but may omit certain implementation details. A definition describes the object in sufficient detail for the compiler to determine its implementation. If a declaration is not complete enough to be a definition, then a separate definition must appear somewhere else in the scope. In C we can write

struct manager;  /* declaration only */

struct employee {

 struct manager *boss;

 struct employee *next_employee;

 …

};

struct manager {  /* definition */

 struct employee *first_employee;

 …

};

and

void list_tail(follow_set fs);  /* declaration only */

void list(follow_set fs)

{

 switch (input_token) {

 case id : match(id); list_tail(fs);

 …

}

void list_tail(follow_set fs) /* definition */

{

 switch (input_token) {

 case comma : match(comma); list(fs);

 …

}

The initial declaration of manager needed only to introduce a name: since pointers are all the same size, the compiler could determine the implementation of employee without knowing any manager details. The initial declaration of list_tail, however, must include the return type and parameter list, so the compiler can tell that the call in list is correct.

Nested Blocks

In many languages, including Algol 60, C89, and Ada, local variables can be declared not only at the beginning of any subroutine, but also at the top of any begin…end ({…}) block. Other languages, including Algol 68, C99, and all of C’s descendants, are even more flexible, allowing declarations wherever a statement may appear. In most languages a nested declaration hides any outer declaration with the same name (Java and C# make it a static semantic error if the outer declaration is local to the current subroutine).

Example 3.12

Inner Declarations in C

Variables declared in nested blocks can be very useful, as for example in the following C code:

{

 int temp = a;

 a = b;

 b = temp;

}

Keeping the declaration of temp lexically adjacent to the code that uses it makes the program easier to read, and eliminates any possibility that this code will interfere with another variable named temp.

No run-time work is needed to allocate or deallocate space for variables declared in nested blocks; their space can be included in the total space for local variables allocated in the subroutine prologue and deallocated in the epilogue. Exercise 3.9 considers how to minimize the total space required.

Design & Implementation

Redeclarations

Some languages, particularly those that are intended for interactive use, permit the programmer to redeclare an object: to create a new binding for a given name in a given scope. Interactive programmers commonly use redeclarations to fix bugs. In most interactive languages, the new meaning of the name replaces the old in all contexts. In ML, however, the old meaning of the name may remain accessible to functions that were elaborated before the name was redeclared. This design choice in ML can sometimes be counterintuitive. It probably reflects the fact that ML is usually compiled, bit by bit on the fly, rather than interpreted. A language like Scheme, which is lexically scoped but usually interpreted, stores the binding for a name in a known location. A program accesses the meaning of the name indirectly through that location: if the meaning of the name changes, all accesses to the name will use the new meaning. In ML, previously elaborated functions have already been compiled into a form (often machine code) that accesses the meaning of the name directly.

Check Your Understanding

12.

What do we mean by the scope of a name-to-object binding?

13.

Describe the difference between static and dynamic scoping.

14.

What is elaboration?

15.

What is a referencing environment?

16.

Explain the closest nested scope rule.

17.

What is the purpose of a scope resolution operator?

18.

What is a static chain? What is it used for?

19.

What are forward references? Why are they prohibited or restricted in many programming languages?

20.

Explain the difference between a declaration and a definition. Why is the distinction important?

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780123745149000124

Named Entity Resolution in Social Media

Paul A. Watters, in Automating Open Source Intelligence, 2016

Discussion

In this chapter, I have sketched out two different algorithmic approaches that could be used undertake named entity resolution. The first takes a dynamical systems view of the machine translation process and how it can account for translations that either succeed or fail, and provides a metaphor for how dynamical system states can be related to single-pass translations using the iterative semantic processing paradigm. In the three examples presented in this chapter, I have demonstrated how dynamical system states correspond to the different kinds of translation errors of semantic material in the context of direct translations systems (e.g., word sense disambiguation of polysemous words). In terms of the absolute preservation of meaning across sentences, the aim of the translation system is to form a point attractor in a “translation space,” although we have also seen that for practical purposes, limit cycles are also acceptable. Unacceptable translations defined by the iterative method are those that rapidly lose information about their initial semantic conditions, perhaps by a translation system equivalent to the period-doubling route to chaos.

What is important about describing machine translation systems using this methodology is that it is possible to use these states as benchmarks for the performance of translation systems. Thus, when translation systems are modified to correct characteristic semantic errors, it is possible to directly assess the performance improvement by using the two statistical measures we have introduced in this chapter, the iterative information loss index, ILOSS, and the cumulative information losses, ITOTAL. An attempt to reduce errors at any particular translation stage can be monitored by examining ILOSS at that particular iteration – for example, some direct translation systems have excellent source→target dictionaries, but poor target→source dictionaries. Improvement of the latter can be tracked at iteration 2 (and indeed, all even-numbered iterations thereafter), with a reduction in ITOTAL after all translations being the main indicator of overall performance.

Obviously, computing these statistics from single sentences is misleading in the sense that they are drawn from larger discourse, and should always be considered with respect to their literary or linguistic origins. Discourse longer than single sentences or phrases is needed for measures of entropy or of information loss to become statistically reliable. In addition, the computation of numerical exponents to quantify the rate of information loss in terms of the system’s entropy (e.g., Lyapunov exponent) needs to be developed and applied to both single sentences and large corpora.

From a neural network perspective, the dynamics of resolving named entities has similarities to resolving the senses of polysemous terms, especially by taking advantage of local context through semantic priming. From the simple examples shown here, it should be obvious how similar contextual information could be used to resolve the identities of individual names on social media. A key question remains as to how such context can be readily gathered using an automated process: for semantic priming of polysemous terms, parameter estimates must be supplied to the model a priori, yet fully automated OSINT systems would not necessarily have trusted access (Tran, Watters, & Hitchens, 2005) to this kind of data. Future research is needed to determine the extent to which names can be automatically resolved, versus a set of candidate choices should be presented to a knowledgeable analyst.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780128029169000026

Fundamental Concepts

Peter J. Ashenden, in The Designer’s Guide to VHDL (Third Edition), 2008

1.4.5 Analysis, Elaboration and Execution

One of the main reasons for writing a model of a system is to enable us to simulate it. This involves three stages: analysis, elaboration and execution. Analysis and elaboration are also required in preparation for other uses of the model, such as logic synthesis.

In the first stage, analysis, the VHDL description of a system is checked for various kinds of errors. Like most programming languages, VHDL has rigidly defined syntax and semantics. The syntax is the set of grammatical rules that govern how a model is written. The rules of semantics govern the meaning of a program. For example, it makes sense to perform an addition operation on two numbers but not on two processes.

During the analysis phase, the VHDL description is examined, and syntactic and static semantic errors are located. The whole model of a system need not be analyzed at once. Instead, it is possible to analyze design units, such as entity and architecture body declarations, separately. If the analyzer finds no errors in a design unit, it creates an intermediate representation of the unit and stores it in a library. The exact mechanism varies between VHDL tools.

The second stage in simulating a model, elaboration, is the act of working through the design hierarchy and creating all of the objects defined in declarations. The ultimate product of design elaboration is a collection of signals and processes, with each process possibly containing variables. A model must be reducible to a collection of signals and processes in order to simulate it.

We can see how elaboration achieves this reduction by starting at the top level of a model, namely, an entity, and choosing an architecture of the entity to simulate. The architecture comprises signals, processes and component instances. Each component instance is a copy of an entity and an architecture that also comprises signals, processes and component instances. Instances of those signals and processes are created, corresponding to the component instance, and then the elaboration operation is repeated for the subcomponent instances. Ultimately, a component instance is reached that is a copy of an entity with a purely behavioral architecture, containing only processes. This corresponds to a primitive component for the level of design being simulated. Figure 1.7 shows how elaboration proceeds for the structural architecture body of the reg4 entity from Example 1.3. As each instance of a process is created, its variables are created and given initial values. We can think of each process instance as corresponding to one instance of a component.

Figure 1.7. The elaboration of the reg4 entity using the structural architecture body. Each instance of the d_ff and and2 entities is replaced with the contents of the corresponding basic architecture. These each consist of a process with its variables and statements.

The third stage of simulation is the execution of the model. The passage of time is simulated in discrete steps, depending on when events occur. Hence the term discrete event simulation is used. At some simulation time, a process may be stimulated by changing the value on a signal to which it is sensitive. The process is resumed and may schedule new values to be given to signals at some later simulated time. This is called scheduling a transaction on that signal. If the new value is different from the previous value on the signal, an event occurs, and other processes sensitive to the signal may be resumed.

The simulation starts with an initialization phase, followed by repetitive execution of a simulation cycle. During the initialization phase, each signal is given an initial value, depending on its type. The simulation time is set to zero, then each process instance is activated and its sequential statements executed. Usually, a process will include a signal assignment statement to schedule a transaction on a signal at some later simulation time. Execution of a process continues until it reaches a wait statement, which causes the process to be suspended.

During the simulation cycle, the simulation time is first advanced to the next time at which a transaction on a signal has been scheduled. Second, all the transactions scheduled for that time are performed. This may cause some events to occur on some signals. Third, all processes that are sensitive to those events are resumed and are allowed to continue until they reach a wait statement and suspend. Again, the processes usually execute signal assignments to schedule further transactions on signals. When all the processes have suspended again, the simulation cycle is repeated. When the simulation gets to the stage where there are no further transactions scheduled, it stops, since the simulation is then complete.

Read full chapter

URL: 

https://www.sciencedirect.com/science/article/pii/B9780120887859000010

Источник

Понравилась статья? Поделить с друзьями:

Читайте также:

  • Каким образом можно устранить систематическую ошибку
  • Какие ошибки присущи сплошному статистическому наблюдению
  • Каким образом можно уменьшить влияние ошибок восприятия на общение
  • Какие ошибки приводят к нарушению лексических норм
  • Каким образом можно избежать ошибки при каузальной атрибуции

    • 0 0 голоса
    Рейтинг статьи
    Подписаться
    Уведомить о
    guest

    0 комментариев
    Старые
    Новые Популярные
    Межтекстовые Отзывы
    Посмотреть все комментарии