DCS Foyle

Совсем недавно, кстати, рассказывая про алгоритм Краута разложения квадратной матрицы в произведение двух треугольных, столкнулся с недостатком языка Паскаль. Схема алгоритма там такая:

procedure UnsymDet (...; var fail: Boolean);
...
begin 
   { некоторые вычисления }
   for k := 1 to n do
      begin 
         { вычисление ведущего элемента x столбца k }
         if abs(x) < eps then
            { надо присвоить fail := true и выйти, но как??? }
      end
end.

( Read more... )

Есть у меня ноутбук. На ноубуке маленький загрузочный раздел и один большой для всего остального. В большом стоит Gentoo Linux на файловой системе reiser4. Но в мире дохрена программ, которые едут только под окошкам. Поэтому я держал VirtualBox, а на нем Windows 7. И вот внезапно узнал, что iTunes на виртуальной машине никак не может взаимодействовать по USB-кабелю со всякими яблочными девайсами. И решил, что надо поставить операционки не друг в друга, а параллельно. Сказано - сделано! Процесс смены конфигурации прошел так:

1) виндовым мастером переноса сохранил свой профиль в Windows 7 на флешку;
2) сделал резервную копию всего винта (500GB) на USB-Drive (CloneZilla);
3) загрузился с SystemRescueCd и скопировал весь корневой раздел reiser4-диска на другой USB-Drive (cp -a);
4) с помощью GParted уменьшил гентушный раздел и создал на освободившемся месте новый;
5) нарезал на уменьшенном разделе снова reiser4;
6) вернул (cp -a) на этот раздел сохраненные в п. 3 данные;
7) выкачал на другом компьютере помощью мелкомягкой утилиты дистрибутив Windows 7 и записал его на флешку;
8) загрузился с этой флешки на ноутбуке и поставил Windows в новый раздел;
9) вновь загрузился с SystemRescueCd, смонтировал reiser4-раздел, сделал туда chroot, поставил (emerge) дополнительный модуль к Grub2 для обнаружения сторонних операционок на диске;
10) установил grub в загрузочный раздел;
11) загрузился в Windows и путем правки реестра рассказал ей о том, что часы в компьютере идут по UTC;
12) мастером переноса восстановил в новой Windows свой профиль со старой;
13) заново установил в Windows нужные мне программы.

Все!

Александр Семенович Кронрод был математиком. А еще он был программистом. В начале 60-х годов он написан книжку "Беседы о программировании". Она так не понравилась другим математикам, что они запретили ее издание.

Книга была издана только в 2001 году.

Мне она тоже не понравилась.

В XXI веке человеку трудно понять, что такое "трехадресная машина", у которой есть "4096 ячеек памяти". К счастью, история вычислительной техники интересовала меня давно, и такие названия, как М-2, Наири, М-20 и Минск-32 мне прекрасно известны, равно как и архитектура и система команд этих машин. Поэтому я понял, о чем пишет Александр Семенович Кронрод.

Не понравилось мне то, что Александр Семенович был противником стандартизации. Это хорошо, если речь идет о стандартизации мыслей. Но плохо, если о стандартизации вычислительных машин. Кронрод справедливо отмечает, что в системе команд М-20 имеется слишком много команд останова, и что вместо лишних можно было бы создать другие полезные команды. Он с гордостью пишет, что в его институте инженеры не были ленивыми, и они переделали машину.

С того момента, как неленивые инженеры это сделали, все программы Александра Семеновича Кронрода перестали быть интересны кому-либо, кроме самого Александра Семеновича. Потому что они стали непереносимыми. Машина, для которой они написаны, существует в единственном экземпляре, в то время как машин с системой команд типа М-20 - более тысячи. Представьте, что неленивые инженеры, вдохновленные кронродами, переделали на свой лад все эти машины. Теперь любую задачу нужно решать не один раз, а тысячу раз. "Э" - эффективность.

Кроме того, Александр Семенович Кронрод не любил языки программирования. Они отрывали программиста от машины и стимулировали его лень. А ведь лень, как мы видели, не позволяет переделать машину и добиться эффективности.

Я только что закончил ковырять очень эффективную программу для ЕС ЭВМ. В той программе очень много данных заведено операторами DATA. Так вот, для большей эффективности все целые и вещественные числа были вбиты в виде шестнадцатеричных констант. Ну, транслятору же проще транслировать именно шестнадцатеричные константы, правда?!

Как вы догадываетесь, в моем распоряжении нет ЕС ЭВМ. Есть писюк с процессором AMD. В отличие от EС ЭВМ у этого процессора архитектура little-endian: байты в многобайтных числах идут в другом порядке. Запиши авторы той программы целые числа обычным образом (десятичные), забота о размещении их в памяти легла бы на плечи компилятора. Страшно неэффективно! Поэтому выворачивать шестнадцатеричные константы пришлось мне.

В процессоре ЕС ЭВМ вещественные числа представляются не так, как в процессоре AMD. Запиши авторы той программы вещественные числа обычным образом, забота о преобразовании их в машинный формат легла бы на плечи компилятора. Но как пострадала бы эффективность! Поэтому конвертировать форматы пришлось мне, а это несколько сложнее, чем просто переставить байты.

В общем, книжку Александра Семеновича Кронрода многие не смогли своевременно прочесть. Но мир это не спасло.

Многие пишут программы и упускают из виду некоторые тонкости используемого языка программирования. А потом долго ломают голову, не понимая, что не работает. (Впрочем, есть люди, которые что-то пишут, вообще не используя голову, но такие именуются не программистами, а говнокодерами). Вот пример. Допустим, вы пишете на языке Паскаль такой код:

while (a[i]>0) and (x mod a[i] <> 4) do
    { что-то делать}

Вы наивно думаете, что условие в заголовке цикла будет вычисляться по краткой схеме, т.е., если a[i]=0, то, очевидно, условие ложно, и вторая часть (x mod a[i] <> 4) вычисляться не будет. Ваша уверенность основана на том, что ваш любимый компилятор именно так и делает. Но ВДРУГ выясняется, что, будучи откомпилированной в другой среде, программа подрывается как раз при вычислении второй части (я однажды встретился с таким явлением сам). Почему?

Потому что надо читать стандарт языка, а не только инструкцию к данному конкретному компилятору. Скажем, Модифицированное сообщение о популярном в прошлом языке Алгол-60 недвусмысленно требует, чтобы в любом выражении вычислялись все его составляющие, поэтому приведенный выше трюк не должен работать ни в каком случае. Стандарт языка Паскаль ISO 7185 более лоялен к разработчикам компиляторов, но совершенно нелоялен к их пользователям, т.е. к прикладным программистам. Этот документ оставляет порядок вычисления выражений целиком на усмотрение реализаторов. И если в одном случае фрагмент будет работать, а в другом - нет, то программа оказывает непереносимой. Я полагаю, что это недостаток стандарта. Но изменить его я не в силах, как не в силах заставить разработчиков компиляторов следовать какому-то одному пути. Но я в силах изменить свою программу и сделать её, хотя и ценой потери красоты и эффективности, независимой от деталей реализации.

В приведенном примере, вроде бы, напрашивается очевидное решение

while a[i] > 0 do
    if x mod a[i] <> 4 then
        { что-то делать}

но оно неправильное, поскольку нарушение второго условия должно закончить цикл, а в таком варианте не закончит. Надо извращаться так:

cont := true;
while (a[i] > 0) and cont do
    if x mod a[i] <> 4 then
        { что-то делать}
    else
        cont := false;

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

Вообще, стандартный Паскаль содержит много неудачных решений. Видел это и его создатель Никлаус Вирт. В стандарте Модулы-2 - наследницы языка Паскаль - четко сказано, что не нужно вычислять второй операнд, если значение выражения понятно из первого. Именно, там написано:

If the left operand to a logical conjunction operator has the value false , the value of the Boolean infix operation shall be the value false , and the right operand shall not be evaluated. If the left operand to a logical conjunction operator has the value true , the value of the Boolean infix operation shall be the value of the right operand.

If the left operand to a logical disjunction operator has the value true , the value of the Boolean infix operation shall be the value true , and the right operand shall not be evaluated. If the left operand to a logical disjunction operator has the value false , the value of the Boolean infix operation shall be the value of the right operand.

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

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

Поклонники Фортрана тоже не должны обольщаться. В стандарте Фортрана-2008, например, сказано (эта фраза без изменений перешла еще из Фортрана-95):

It is not necessary for a processor to evaluate all of the operands of an expression, or to evaluate entirely each operand, if the value of the expression can be determined otherwise.

(Необязательно, чтобы процессор вычислял все операнды выражения или вычислял полностью каждый операнд, если значение выражения может быть определено иным способом).

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

Так что, предохраняйтесь, и будет вам программистское счастье!

Правильный ответ на загадку о нудном проверяющем таков.

1. В условии сказано, что количество чисел не превышает 200. Поэтому нужно создать массив на 200 чисел и сначала ввести их, и только потом анализировать.

2. В условии сказано, что введенные числа по модулю не превышают 10000. Поэтому нужно использовать тип не Integer, а, если программа на Паскале, тип-диапазон -10000..10000. Не знаю, что скажет проверяющий, когда узнает, что в большинстве языков такого типа нет. Даже Вирт, создавая Oberon, наследник Модулы-2, наследницы Паскаля, от него отказался.

3. В условии сказано, что суммировать нужно трехзначные числа, начинающиеся на 4. Поэтому нужно сначала выяснить, является ли очередное число трехзначным, потом найти его первую цифру и сравнить с 4. Сам проверяющий полагал, что для этого нужно перевести число в строку, посчитать количество символов, потом взять первый символ и сравнить с символом "4".

Вот так сейчас учат программировать.

Установка Gentoo Linux на маломощный ноутбук занимает несколько дней, потому что все собирается из исходных текстов. Но я не боюсь трудностей!

В текстах программ из JPL для доступа к эфемеридам планет обнаружил такую строчку:

Люди моего поколения еще помнят, что компьютеры появились не сразу в виде смартфонов и планшетов. Когда-то они были очень большие и занимали целый зал. Несколько сотен операций в секунду считалось высокой скоростью. И языки программирования - это не только Си и Visual Basic. Люди еще постарше (я - исключение) помнят такой язык Алгол-60. Число 60 в его названии - год официального опубликования описания этого языка. Причем, синтаксис его был описан с помощью формального языка БНФ - Нормальной Формы Бэкуса. В 60-е годы для этого языка создали массу трансляторов для самых разных машин. В СССР трансляторы с Алгола ТА-1М и ТА-2М работали на ЭВМ с системой команд М-20: М-220, М-222, БЭСМ-4. На советской транзисторной супер-ЭВМ было несколько трансляторов этого языка: ГДР-Алгол, БЭСМ-Алгол, система "Альфа" и др. В книгах и журналах публиковалась масса алгоритмов для решения самых разных (но большей частью вычислительных) задач на языке Алгол. Я уже упоминал книгу Уилкинсона и Райнша "Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра", который содержит программы непревзойденного качества.

Алгол-60 имеет, среди прочих, особенность, которая не встречается в современных языках. Это передача параметра в процедуру по наименованию. Нынешние программисты знают два способа: по значению (единственный способ в Си) и по ссылке. Передача по имени отличается и от того, и от другого, потому что в процедуру передается не значение переменной и не указатель на место в оперативной памяти. Передача выполняется так, как будто фактический параметр подставляется в процедуру вместо формального. С непривычки трудно уловить разницу. Но вот вам пример использования такой передачи под названием "трюк Йенсена":

begin
  
  procedure p(a, b);
    integer a,b;
  begin
    for a:=1 step 1 until 10 do
      b := 0
  end p;

  integer i; integer array s[1:10];
  p(i,s[i])

end

Процедура p имеет два параметра, которые передаются по имени (в противном случае они были бы специфицированы как "value a,b;"). Первый параметр используется в качестве переменной цикла, а второму в этом цикле присваивается нулевое значение. При передача по ссылке (не говоря уже о передаче по значению) такой цикл лишен смысла. Зачем, в самом деле, 10 раз записывать в одно и то же место в памяти нуль? Но в том и фокус, что место это не одно и то же! При вызове процедуры фактическими параметрами являются i и s[i]. Способ передачи по наименованию предполагает подстановку параметров в тело процедуры. И получается, что выполняется следующий цикл:

for i:=1 step 1 until 10 do
      s[i] := 0

Согласитесь, это совсем другое дело. Кстати, хорошая задача для студентов-программистов: как можно реализовать такую передачу в трансляторе?

Но, казалось бы, время этого языка прошло. Ориентированный исключительно на вычисления, он непригоден для решения всех прочих задач. В частности, язык не содержит никаких средств для работы с символами, нет в нем и средств для создания интерфейса с пользователем. А откуда они могли взяться, если в 60-е гг. интерфейсом были устройство ввод перфокарт и АЦПУ (так тогда называли принтеры)? В то же время масса записанных на нем алгоритмов по-прежнему востребована, только перед употреблением эти алгоритмы переписываются на другие, современные языки: на тот же Си, например, или Фортран (в его нынешнем, не историческом виде).

И вот недавно я узнаю, что пациент еще не умер! Частью проекта GNU является конвертер marst с Алгола-60 на Си. Очень компактная программа прекрасно работает у меня в операционных системах на базе Linux, FreeBSD и даже под Windows в окружении CygWin. Конвертер прошел замечательный тест на зрелось - Man or Boy. А вот самый известный рабочий транслятор прошлого ТА-1М такой тест не пройдет, поскольку вообще не допускает рекурсию. С помощью marst я успешно транслировал оригинальный интегратор Булирша и Штёра и проверил некоторые недавние работы, касающиеся выявления устойчивых орбит в системе α Centauri. Если справлюсь с ленью, напишу об этом позже. :)