Anatoly Levenchuk ([info]ailev) wrote,
@ 2009-06-26 13:26:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
Пятничное утро
Оказывается, livejournal глючит при показе медиа в постинге. Презентация про стандарты описания организаций из моего предыдущего постинга у меня в браузере регулярно заменяется роликом проекта Natal, который я опубликовал еще несколько дней назад.
* * *
Обзорчик программ для DSM (design structure matrix) со скриншотами: http://puln.livejournal.com/1790.html

Как я понимаю, [info]puln и дальше будет писать на эти темы.
* * *
Интервью с сэром Tony Hoare (автором Quicksort, Hoare logic, Communication Sequential Processes и вдохновителем языка Occam) -- http://www.infoq.com/interviews/tony-hoare-qcon-interview. В 1999 году он из Оксфордского университета уволился "на пенсию" в Microsoft Research в Кембридже.

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

Полная для меня неожиданность: он имеет базовое образование в греческих и латинских языках, а компьютерную науку и языки учил в МГУ! И целый год участвовал в проекте по машинному переводу "научного русского" на английский. Первая научная статья Tony Hoare была подана и опубликована в русскоязычном журнале "Машинный перевод", он напечатал ее на русскоязычной пишущей машинке друга. Но ему не давали посмотреть на русские компьютеры, они тогда были секретны!


(14 comments) - (Post a new comment)


[info]avlasov
2009-06-26 10:03 am UTC (link)
Выход видится в том, что все такое документирование должно делаться специальными программами, которые должны пробовать восстановить по тексту программы такое документирование, а затем использовать его для доказательства правильности программы -- и для софта в последние годы в таком инструментарии прошел значительный прогресс.
"The C language is particularly rich with ways of writing a program that totally hide the original design intent." - Stanley Chow
Для императивных языков это нереально.

(Reply to this) (Thread)


[info]ailev
2009-06-26 11:50 am UTC (link)
Как я понимаю, ровно в этом месте и наступает стремительный прогресс :)
Или они в Майкрософт начали писать Виндоуз на функциональных или логических языках? 8-()

(Reply to this) (Parent)(Thread)


[info]avlasov
2009-06-26 12:02 pm UTC (link)
Нет, просто они используют грубую силу.
Прогресс конечно тоже есть. Но сами микрософтовцы (микрософт ресерчевцы) говорят: фрейм кондишенз - это самая жопа. Фрейм кондишенз - это ограничения на состояния массивов/кучи, ну т.е. как раз императивка.

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

(Reply to this) (Parent)


[info]avlasov
2009-06-26 12:04 pm UTC (link)
Я вот люблю заниматься верификацией и сложные задачки решать. Но как только я дошел до фрейм-кондишенз, я понял, что все, стратегически это жопа. Проще заново переписывать.
Грубо говоря, описывать все эти фрейм-кондишенз - это все равно что документировать и автоматизировать хреновые бизнес-процессы.

(Reply to this) (Parent)


[info]avlasov
2009-06-26 10:05 am UTC (link)
Статическая или динамическая типизация тут не имеет значения, это в бОльшей мере инженерный, а не научный вопрос: просто для динамических языков проверка делается в ходе выполнения программы, а не перед выполнением, в обмен на гибкость мы получаем более медленное исполнение.
Вообще говоря имеет, ибо при динамической типизации верификатор сам должен догадываться, какие типы может принимать выражение. Так что символическое исполнение тоже будет более медленным. И что более важно, оно будет автоматически разрешимым в меньшем кол-ве случаев.

(Reply to this) (Thread)


[info]ailev
2009-06-26 11:49 am UTC (link)
Как я понимаю, алгоритмически разрешать просто придется в каждом проходе, включая внутри циклов...

(Reply to this) (Parent)(Thread)


[info]avlasov
2009-06-26 12:10 pm UTC (link)
А циклы как раз и требуют описания инвариантов в FOL!
Грубо говоря, надо разрабатывать эвристический детектор инвариантов, который все равно не всегда спасает.
Это все известные и исследованные проблемы, они еще при создании оптимизирующих компиляторов всплыли.
Т.е. прогресс в оптимизации застопорился, потому что на эвристиках уже далеко не уедешь. Нужен системный подход.

(Reply to this) (Parent)(Thread)


[info]ailev
2009-06-26 12:58 pm UTC (link)
Хоар как раз и говорит, что одни эвристики по доказательству сменяются другими менее эвристиками -- все как раз идет к бОльшей классической доказательности.

Он радуется, что правильно определил, что 20 лет внедрения в промышленность этих методов не будет, по факту, говорит, что даже 30 лет не было прогресса -- только-только сейчас начинается.

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

(Reply to this) (Parent)(Thread)


[info]avlasov
2009-06-26 01:16 pm UTC (link)
Ну я согласен в том, что доказательство программ синергирует с генерацией программ. Это действительно так и есть даже фундаментальный результат, что по конструктивному доказательству спецификации можно сгенерировать программу, ее реализующую.
Но вот с классическим программированием идет война - как сам Хоар говорит, тестирование конфликтует с верификацией.

(Reply to this) (Parent)


[info]kuznetsov
2009-06-26 10:13 am UTC (link)
А чо ты его латиницей пишешь? Человек в русскоязычных программыстских кругах давно известный, Хоар его фамилие. Венгр, кажется, по происхождению.

(Reply to this) (Thread)


[info]ailev
2009-06-26 11:48 am UTC (link)
А я часто имена латинницей пишу -- не только его. Насчет венгра, правда, сильно сомневаюсь. Born in Colombo (Ceylon, now Sri Lanka) to British parents (http://en.wikipedia.org/wiki/C._A._R._Hoare).

(Reply to this) (Parent)(Thread)


[info]kuznetsov
2009-06-26 07:52 pm UTC (link)
А, ну, м.б., я его с Хааром перепутал (который в теории меры).

Но человек известный во времена моей ВМК-шной юности.

(Reply to this) (Parent)

LJ медиа
[info]lusever
2009-06-26 10:19 am UTC (link)
У юраузеров вечные проблемы с кэшированиям iframe'ов. Которые использутся для медиа в жж. Можно поинтересоваться, у вас какой браузер/версия?

(Reply to this) (Thread)

Re: LJ медиа
[info]ailev
2009-06-26 11:43 am UTC (link)
У меня Firefox свежайшей (3.0.11) версии.

(Reply to this) (Parent)


(14 comments) - (Post a new comment)

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…