Программирование: как это было [entries|friends|calendar] iljas_prg [ userinfo | livejournal userinfo ] [ calendar | livejournal calendar ]

ТРИЗ [10 Jun 2007|11:45am] Слово ТРИЗ я узнал еще в детстве из книжки про изобретения (но не спрашивайте меня, как она называлась, и кто ее написал — увы, я не помню). ТРИЗ значит «теория решения изобретательских задач». Теория?! Для такого творческого дела, как изобретательство?! Не хило, да? По весне удалось прочитать книжку Г. С. Альтшуллера «Творчество как точная наука» (где по диагонали, а иногда и вчитываясь). Я попытаюсь воспроизвести его рассуждения. Многим не давал покоя вопрос, как же делаются открытия? Сами авторы открытий объясняли это творческим вдохновением, озарением, музой, insight и т.п. Психологи подглядывали за талантливыми людьми, но ответа не нашли. Его и не могло быть, считает Альтшуллер, потому что дело сводилось к банальному перебору вариантов. А самым важным изобретением Эдисона является научный институт. Придумываются несколько идей, возможно решающих проблему, и каждая из них назначается отдельному человеку или коллективу, который занимается ее изучением. Т.о. ускоряется перебор. Чему свидетельсвто — огромное количество изобретений Эдисона (что-то около 1000). Основной целью является избавление от перебора вариантов, переход к целенаправленному поиску решения. Альтшуллер проанализировал большое количество изобретений и выделил часто встречающиеся методы решения изобретательских задач. В результате предложил алгоритм решения изобретательских задач (АРИЗ). Алгоритм в широком смысле слова, т.е. предназначенный для выполнения человеком, а не компьютером. Насколько я понял, назначение алгоритма — отсечь заведомо бесперспективные идеи и найти техническое противоречие (например, у устройства должно быть свойство A и не должно быть свойства A). Противоречия классифицированы и указаны возможные решения. Для приведенного примера — это разделение во времени (в один момент времени есть свойство A, а в другой — нет) или разделение в пространстве. А меня интересует вопрос, есть ли ТРИЗ для программирования (а также для математики). Поиск в Яндексе показал, например, неплохие статьи КАК ВСПОМНИТЬ "И ТАК ИЗВЕСТНОЕ" ОСВОБОЖДЕНИЕ УЗНИКОВ ОПЕРАТОРА "IF" О ПОТЕРЯННОМ УРОВНЕ. Но в основном поиск дает статьи, в которых ТРИЗ притянут за уши, и нет ее адаптации. Может кто-нибудь знает статейки по этой теме? UPDATE: А книжка называлась Альтов Г. И тут появился изобретатель. 5 comments|post comment

Чем мы вообще занимаемся? [31 Jan 2007|02:51pm] Чем мы вообще занимаемся? Давным-давно жили-были пифагорейцы. И Пифагор в том числе. Они считали, что арифметика — вот главная наука. «Все есть число», — заявляли пифагорейцы. И думали, что все можно объяснить с помощью чисел, даже гармонию музыки. Теорема Пифагора (квадрат гипотенузы равен сумме квадратов катетов) — она вещь тоже о числовых характеристиках. Но однажды они доказали, что диагональ единичного квадрата не является числом (а у них в ходу были только натуральные числа) и не является дробью. Как же так?! Гиппас из Метапонта, предавший огласке такую странную вещь, поплатился за это: пучина поглотила его (сама или ей помогли — история молчит об этом). Итак, диагональ квадрата существует геометрически, но не описывается числом. Позже для таких случаев придумали вещественные числа. Но это вещи сходной природы. Начнем с того, что представления вещественных чисел в виде десятичной дроби бесконечно. Или попробуйте придумать алгоритм для сложения (а еще лучше — для умножения) двух таких чисел, скажем пи и корня из двух. Ну как? Символично, что «точная» математика с использованием вещественных чисел на практике превращается в методы приближенных вычислений. Математика точная наука? Что ты думаешь об этом, дорогой читатель? В конце XIX в. Кант придумал теорию множеств. Это универсальный язык. И геометрию, и арифметику, и функции, и иное можно описать в терминах теории множеств. Математики были в восторге. Однако оказалось, что ей присущи парадоксы (противоречия), например, парадокс брадобрея: В некой деревне живет брадобрей Рассел. Он бреет бороды всем тем, кто не бреет свою бороду сам. Вопрос: бреет ли свою бороду брадобрей? От противного можно доказать, что бреет, и можно доказать, что не бреет. Это был тяжелый удар. В результате были предложены несколько систем аксиом, система типов Рассела и др. подходы для исключения противоречий. Все бы хорошо, но до сих пор не доказано, что хотя бы одна из теорий множеств, основанная на коком-то из этих подходов, в свою очередь не противоречива. И вот теперь седовласый профессор докажет какую-нибудь теорему, но на душе не спокойно: а вдруг ... а вдруг Вася Пупкин обнаружит противоречие, и половина доказанных теорем станет неправильной. Как бы и Васю не поглотила пучина или что похуже... Математика позволяет определить истину? Что ты думаешь об этом, дорогой читатель? В геометрии Евклида есть пятый постулат. Он гласит, что через точку можно провести прямую, параллельную к заданной, но только одну. Многие считали, что это вовсе не аксиома, а теорема. И пытались ее доказать. Доказывали от противного: строили теорию с противоположной аксиомой (когда можно провести несколько параллельных прямых), и искали противоречие. Но — не нашли. Кому-то хватило мужества сказать, что противоречия нет, и так появилась новая геометрия — геометрия Лобачевского. Впрочем современники не приняли ее, она казалась вещью, далекой от реальности. Позже удалось выразить ее через геометрию Евклида. Геометрия Лобачевского описывает геометрию на сфере. Т.о. одна из геометрий не более правильна, чем друга, и не более противоречива. Кто бы мог подумать. Развитие логики привело к еще одному «неудобному» результату. Гёдель доказал теорему о неполноте арифметики. Т.е. не каждую формулу, построенную средствами арифметики, можно доказать. Эта теорема также верна и для других теорий «не проще» арифметики, а таких много. Вот так, любая более-менее богатая теория не полна, все не описывает. И не понятно, противоречива ли она или нет. А может она и вовсе высосана из пальца и неприменима к жизни? Современный подход, объясняющий эти вещи таков. Математика изучает модели реальности. Модель, абстракция — это в том числе и упрощение. Выделение небольшого числа важных для решения данной задачи характеристик и игнорирование второстепенных. И поэтому она не может описывать всю реальность, она заведомо не полна. И поэтому она не может описывать реальность абсолютно точно, где-то она не точна. Логика — модель правдоподобных рассуждений, но для определенных рассуждений она может не подходить. Но у каждой теории есть область применимости, где она вполне адекватна и полезна. Важно не заблуждаться, считая, что она будет верна всегда, везде и для всех. И важно не заблуждаться, считая, что все теории бесполезны, созданы ради теории; практика, обобщая опыт, часто порождает теории. post comment

Не просто вопрос удобства [02 Dec 2006|06:07pm] Не просто вопрос удобства В чем отличие чистых математиков от программистов? Чистые математики чувствуют разницу между конечным и бесконечным, но в основном игнорируют разницу между большим и малым. Тут часто приводят пример римских и арабских чисел. И те, и другие пригодны для выполнения арифметических операций (+,-,*,\), но позиционная система счисления куда более удобна. Попробуйте, например, умножить 723 на 29 (а до этого DCCIII*XXIX). Чистые математики постараются не отвлекаться на такие «мелочи», будут рассматривать идеальное понятие числа, говоря о том, что вычислить можно и римскими числами, хотя это и труднее. Нет! Потенциально решаемые задачи ≠ реально решабельные. Часто неудобство влечет невозможность. Средневековые арабские математики известны своими таблицами синусов, шаг которых достигал 10′, а точность — 1/604. А римляне, в конце концов придумали абак (устройство типа счетов) для реальных вычислений. Также неудобно создавать программы на ассемблере (или другом низкоуровневом языке). Просто потому что между постановкой задачи на естественном языке и ассемблером — гигантская пропасть. Проще перевести задачу на промежуточный язык(и), а с него — на ассемблер. Потенциально можно запрограммировать сразу на ассемблере, но в реальности — вряд ли. Мне кажется, что сходные проблемы у Васи, обучение программированию которого свелось к всего лишь изучению языка программирования (на уровне синтаксиса). Не просто же так возникли термины программирование в малом (кодирование) и программирование в большом (проектирование). Есть также особый сорт людей с фамилией Дилетантов (у них, правда, не всегда такая фамилия). Однажды Дилетантов написал маленькую программу для простой задачи. И стал думать, что программирование — это просто. Глупо, ужасно неправильно. Так и появляются Дилетантовы, которые игнорируют разницу между большим и малым. P.S. Попробую привести более содержательный пример, нежели чем ассемблер. Пусть нужно нарисовать (векторный) рисунок африканского пейзажа с помощью какой-нибудь графической библиотекм типа GDI, Cairo или языка типа PostScript — неважно. Важно, что он(а) предоставляет простые средства вида нарисовать линию, треугольник, закрасить область и т.п. Решение Васи (того, кто не смог подняться над уровнем языка программирования/библиотеки). Рисунок — это набор базовых примитивов (точек, линий и т.п.) Его код состоит из кучи вызовов MoveTo, LineTo, Fill, ... Легко запутаться, сделать ошибку, трудно что-либо изменить (особенно, если Вася не написал комментарии). Использование абстракций. Рисунок состоит из льва, зебры, дерева, саванны, неба, солнца (красивый закат). Создаются процедуры для отрисовки этих элементов. А основной код будет имееть вид: НарисоватьЛьва(x0,y0); НарисоватьЗебру(x1,y1); НарисоватьСолнце(x2,y2); — куда более понятно. И как мне объяснить читателю то чувство, которое я испытал, когда впервые осознал, что при создании больших программ нужно поступать по второму сценарию?! Исходный код на MetaPost: input boxes; vardef Connect(suffix a,b) = save p; path p; p := a.c--b.c; drawarrow p cutbefore bpath.a cutafter bpath.b; point .5*length p of p enddef; def SetDiameter(suffix a)(expr diam) = a.n-a.s=(0,diam); a.e-a.w=(diam,0); enddef; def ddiameter(suffix a) = a.n-a.s=(0,d+4pt); a.e-a.w=(d+4pt,0); enddef; beginfig(1); u:=1cm; v := 1cm; d := 27pt; %создаем окружности circleit.ca(btex$s_0$etex); circleit.cb(btex$s_1$etex); circleit.cc(btex$s_n$etex); SetDiameter(ca, d); SetDiameter(cb, d); SetDiameter(cc, d); %система уравнений задает отношения между окружностями cb.c - ca.c = (2u,0); ca.c + dir(-60)*2u = cc.c; %рисуем окружности drawboxed(ca, cb, cc); %русуем стрелки label.top(btex$x_1$etex, Connect(ca, cb)); label.rt(btex$x_2$etex, Connect(cb, cc)); label.lft(btex$x_{n-1}$etex, Connect(cc, ca)); currentpicture := currentpicture scaled 2; endfig; Сгенерированный код на PostScript: %!PS %%BoundingBox: -19 -123 150 31 %%Creator: MetaPost %%CreationDate: 2006.12.05:1429 %%Pages: 1 %*Font: cmmi10 19.9253 9.96265 73:84 %*Font: cmr7 13.9477 6.97385 30:e %*Font: cmmi7 13.9477 6.97385 6e:8 %*Font: cmsy7 13.9477 6.97385 00:8 %%EndProlog %%Page: 1 1 0 0 moveto (s) cmmi10 19.9253 fshow 9.34 -2.9888 moveto (0) cmr7 13.9477 fshow 0 1 dtransform truncate idtransform setlinewidth pop [] 0 setdash 1 setlinejoin 10 setmiterlimit newpath 36.03848 2.7951 moveto 36.03848 17.65103 23.99533 29.69418 9.1394 29.69418 curveto -5.71652 29.69418 -17.75964 17.65106 -17.75964 2.7951 curveto -17.75964 -12.06082 -5.71652 -24.10394 9.1394 -24.10394 curveto 23.99536 -24.10394 36.03848 -12.06082 36.03848 2.7951 curveto closepath stroke 113.3858 0 moveto (s) cmmi10 19.9253 fshow 122.7258 -2.9888 moveto (1) cmr7 13.9477 fshow newpath 149.42429 2.7951 moveto 149.42429 17.65103 137.38113 29.69418 122.5252 29.69418 curveto 107.66928 29.69418 95.62616 17.65106 95.62616 2.7951 curveto 95.62616 -12.06082 107.66928 -24.10394 122.5252 -24.10394 curveto 137.38116 -24.10394 149.42429 -12.06082 149.42429 2.7951 curveto closepath stroke 55.73929 -98.19525 moveto (s) cmmi10 19.9253 fshow 65.07928 -101.18405 moveto (n) cmmi7 13.9477 fshow newpath 92.73138 -95.40015 moveto 92.73138 -80.54422 80.68823 -68.50107 65.8323 -68.50107 curveto 50.97638 -68.50107 38.93326 -80.54419 38.93326 -95.40015 curveto 38.93326 -110.25607 50.97638 -122.2992 65.8323 -122.2992 curveto 80.68826 -122.2992 92.73138 -110.25607 92.73138 -95.40015 curveto closepath stroke 1 setlinecap newpath 36.03772 2.7951 moveto 95.62592 2.7951 lineto stroke newpath 88.23453 -0.26657 moveto 95.62592 2.7951 lineto 88.23453 5.85678 lineto closepath gsave fill grestore stroke 55.66904 11.78394 moveto (x) cmmi10 19.9253 fshow 67.05682 8.79514 moveto (1) cmr7 13.9477 fshow newpath 109.07346 -20.50406 moveto 79.28378 -72.10144 lineto stroke newpath 80.32797 -64.16974 moveto 79.28378 -72.10144 lineto 85.63077 -67.23132 lineto closepath gsave fill grestore stroke 100.17874 -49.09763 moveto (x) cmmi10 19.9253 fshow 111.56653 -52.08643 moveto (2) cmr7 13.9477 fshow newpath 52.38055 -72.10098 moveto 22.59088 -20.5036 lineto stroke newpath 28.93787 -25.37372 moveto 22.59088 -20.5036 lineto 23.63507 -28.4353 lineto closepath gsave fill grestore stroke -11.14377 -48.26746 moveto (x) cmmi10 19.9253 fshow 0.24402 -51.25626 moveto (n) cmmi7 13.9477 fshow 10.09384 -51.25626 moveto (\000) cmsy7 13.9477 fshow 22.54703 -51.25626 moveto (1) cmr7 13.9477 fshow showpage %%EOF 4 comments|post comment

Расширяемость [31 Oct 2006|09:22pm] Расширяемость Чем большая программа отличается от маленькой? Ее труднее сделать, куда более труднее, существенно труднее. А маленькую — легко. Ну так давайте делать только маленькие программы! ...Разработка ПО по-английски называется development — дословно, развитие. Есть такой принцип: от простого к сложному. И есть инкрементальная модель разработки. Идея всего этого в следующем: создать прототип — маленькую программу, которая отражает в определенной степени большую. А над ним можно провести пару-тройку экспериментов, изучить реакцию пользователей, заказчиков, получить обратную связь. Т.о. идентифицировать проблемы (чем раньше их обнаружили, тем дешевле их исправление). Главное — будет получен опыт, который нужно учесть, внести в прототип. Прототип постепенно изменяется, детализируется, расширяется, пока не будет получена большая программа, ради которой все затевалось. Важно, чтобы изменения можно было производить локально. Т.е. отдельное изменение затрагивало небольшую часть программы, иначе нет смысла ее изменять — проще переписать все заново целиком. Для этого программу нужно разделить на несколько автономных частей. Возьмем процедуру в смысле, например, языка Pascal. Является ли она автономной частью? Тут возможны варианты... ответ: нет, если используются глобальные переменные попробуйте вставить текст этой процедуры в другую программу — она не будет работать, необходимо перенести еще и глобальные переменные; при использовании этой процедуры несложно породить ошибку: если процедуре не передать фактический параметр, то компилятор будет ругаться, а если не инициализировать глобальную переменную? также плоха процедура без комментария о ее предназначении, о том, как ее использовать — мало того, что для ее понимания нужно изучить ее исходный текст, при изменении ее реализации могут пострадать пользователи, использующие процедуру не так, как хотел ее автор, а использующие недокументированные возможности. Теперь я хочу повернуть свою мыслю в сторону того, что автономные части можно многократно использовать (использовать повторно, но я не люблю это словосочетание) в различных программах. И такие части любят ударяться в универсализацию. Например, алгоритм сортировки массивов сравнениями. Тип данных элементов массива может быть почти произвольным — нужна лишь операция сравнения. При использовании пользователь будет параметризовать алгоритм этой операцией , так что реализация алгоритма сможет правильно перемещать элементы в нужную сторону. Параметром может быть не только отдельная операция, но и целый тип данных (скорее — переменная определенного типа данных). Рассмотрим оконную систему. Она позволяет отображать на экране виджеты (кнопки, полосы прокрутки и т.п.) и заставляет их реагировать на различного рода события. Для этого типы данных виджетов должны поддерживать операцию Draw (которая красиво рисует этот виджет) и Handle (которая реагирует на переданное в качестве параметра сообщение о событии). Т.о. можно один раз реализовать оконную систему, отладить и зафиксировать. Далее расширять систему путем разработки новых виджетов. А оконная система сможет их все использовать, т.к. они все поддерживают необходимые операции Draw и Handle. Итак, по скромному мнению автора этой статьи, отличительной чертой ООП является способность типа данных A работать с типами данных, объявленных и реализованных позже (т.е. неизвестных для A).Это включает не только полиморфизм (как позднее связывание методов), но и т.н. отражение (reflection, элемент метапрограммирования) — способность создавать во время выполнения программы переменные нужного типа данных, зная лишь его имя, указанной в виде строки (см. платформы Java и .Net, а также Oberon System). 14 comments|post comment

[17 Oct 2006|07:59pm] Модель, абстракция Итак, спецификация (функция программы) меняется. А что же сохраняется (инвариантным)? Ответ: предметная область является достаточно стабильной. Сомнительно, что заказчик захочет из программы для бухгалтерии сделать программу для управления авиалайнером, не так ли? Что такое предметная область? Набор объектов, связанных отношениями. Модель рассматривает статические и динамические аспекты системы, в более программистских терминах — описывает строение и поведение. Все это смахивает на определение типа данных: множество допустимых значений и множество допустимых преобразований. Отсюда вывод — типы данных предназначены для реализации различного рода моделей. Есть люди, которые говорят, что программистам не нужна математика. Не верь им, мой читатель! Последние несколько сотен лет именно математику использовали для моделирования. С другой стороны, для общения с заказчиком нужны способности, которые малость отличаются от математических — тонкое знание психологии здесь не повредит. Можно посмотреть на эволюцию языков программирования. Fortran предоставлял средства для описания вычислений, встроенный небогатый набор базовых типов и ничего для определения пользовательских типов данных (ну если только массивы.) Pascal был знаменит своей богатой системой типов. Большие возможности для определения программистом структур данных плюс пользовательские процедуры и функции. Позже появились модульные языки. Наиболее известные из них — Modula-2 и Ada. Они позволяли определять типы данных в отдельных модулях, открывая клиентам лишь их интерфейс. Уровень языков программирования и проблема универсальных языков Когда-то (в 60–70-е года) некоторые люди хотели создать универсальный язык программирования. Это хорошо согласуется с верой многих программистов, неугасшей и поныне, в панацею от всех бед, в так называемые "серебряные пули". Несколько лет назад я задумался, почему мне нравятся определенные книгм по программирования, а другие, "попсовые", — нет. Плохие книги заливаются хвалебной одой описываемому языку или среде программирования. Авторы интересных книг описывают недостатки, границы области применимости средства, задают вопросы, на которые нет однозначного ответа, рассказывают о проблемах — заставляют задуматься, поразмышлять. ...Ну так вот, знаменитыми представителями языковой гигиантомании были Algol-68 и PL/I (позже Ada и C++, тест ниже верен и для них, но с некоторыми изменениями). Эти языки пытались включить средства для разработчиков программ на все случаи жизни, всевозможных видов программ и предметных областей. Пользователи были рады этому, и даже требовали еще больше возможностей. Однако Algol-68 и PL/I были побиты примитивным по сравнению с ними языком C. Странно, да? Какой язык хороший? На котором легче программировать. Программирование в контесте языков программирования мы будем трактовать как перевод задачи с естественного языка на машинный. язык природы ↓ естественный язык ↓ графический язык ↓ формальный язык ↓ язык программирования Специализированный язык программирования (наприме, HTML) — просто сказка в данном случае. Часто ими могут пользоваться даже конечные пользователи. Однако для общецелевых языков программирования встает вопрос: как приблизить язык программирования к языку прдметной области? Даже банальные (!) пользовательские процедуры служат этой цели; позволяют расширить язык и программировать в терминах предметной области. В начале предметной областью была вычислительная математика. Fortran подходил для нее практически идеально. Потом компьютеры стали использовать для экономических задач. Для них был создан Cobol. Но опять появились новые области и новые горизонты. Языки-гиганты пытались включить средства для всего спектра задач. Но новые задачи появляются каждодневно и разработчики языков программирования не могут за ними угнаться. В связи с этим общецелевые языки программирования должны быть простыми (легко изучить и держать в голове) и расширяемыми. Позволять пользователям описывать новые процедуры, структуры данных, типы данных и подобное. Это позволит адаптировать их для новых задач. post comment

[11 Oct 2006|05:46pm] Что еще там? Итак, программист определяет функции. Вычисление же функций — дело компьютера. Основной недостаток оператора Go To в том, что он не помогает определять функции, а описывает их вычисления. Постепенно Go To заменили три структурных оператора управления, соответствующих знакомым схемам определения функций: последовательное выполение — композиция функций (например, f(g(x)) ); условный оператор — определение функции разбором случаев (помните определение абсолютного значения |x|?); цикл — вычисление элемента последовательности, удовлетворяещему определенному условию. Позже также стала популярной рекурсия — вычисление функции, заданной неявно функциональным уравнением. Средством борьбы со сложностью стала декомпозиция (разработка сверху вниз, пошаговая детализация) — сложную задачу разбивали на несколько других задач, более простых. Если использовать солидные слова, то всему этому соответсвовала водопадная модель разработки ПО. Она достаточно хорошо решает нашу первую задачу (создание больших программ), но изменения спецификации порождают большой объем переделок. Что естественно, ведь весь процесс вертелся вокруг функции, описанной в спецификации. Ее изменение значит, что нужно реализовать новую функцию. И может оказаться, что новая функция реализуется существенно иначе, чем старая. Проблема была идентифицирована, и ее стали решать... post comment

[04 Oct 2006|12:49pm] "Точки роста" Целью моего цикла заметок — попытка объяснить развитие программирования, выяснить причины тех изменений, кторые произошли в ее истории. Самое важное в этом деле — конечно же, определить проблемы. Что приводит к изменениям (новациям, инновациям, развитию, прогрессу — подставь нужное)? Если текущее положение устраивает Васю, разве будет он что-либо менять? А ты, читатель, как думаешь: "лучшее — враг хорошего" или "необходимость — мать изобретательности"? Итак, в узком смысле программирование — это разработка программ. Трудности, которые подстерегают: 1. размер программ Большие программы разрабатываются принципиально иначе, чем маленькие. Поэтому то, что Алекс написал программу в 3 тыс. строк, не гарантирует, что он осилит программу в 100 тыс. строк. 2. изменчивость Клиенты не знают, чего они хотят. Отсюда частые изменения спецификаций (а также нелюбовь программистов к заказчикам). Также попытки реализовать проектные решения могут вскрыть их несостоятельность (нереализуемость, неэффективность, сложность) Их тоже иногда пересматривают. Плюс ко всему программу необходимо сопровождать. Это значит добавление новых функций к программе, изменений существующих, перенос на новые программно-аппаратные платформы и т.п. До недавнего времени сопровождение было самым дорогим этапом жизненного цикла ПО. 3. библиотеки, каркасы и многократное использование Часто в различных программах есть одинаковые (или почти одинаковые) куски кода. И естественно большое желание использовать уже готовые решения. Программы могут стать надежнее, стоимость разработки уменьшится, а жизнь программиста стать приятнее. Проблемой является совместимость версий, плохая документация и низкая надежность предлагаемых на рынке компонетов. 4. новые предметные области Программы стали разрабатываться и использоваться для все большего количества новых задач. Поначалу компьютеры использовали для вычислительных задач, потом для экономических, обработки тестов, изображений, игр, интернета и прочая и прочая... Кстати, программирование в расширенном смысле можно трактовать как моделирование. Это является ответом на вопрос, почему на ВМК так много математики и зачем ее изучать — она тоже используется для моделирования. Основыне проблемы: адекватность предметной области инструментария разработки и построение модели предметной области. post comment

[04 Oct 2006|12:46pm] Что не так с оператором Go To? Когда-то в 50–60-е гг. этот оператор был в почете. В те времена не было ни одного языка императивного программирования, который бы его не поддерживал. Откуда он вообще взялся? Честно говоря, я не знаю. Видимо, в языки высокого уровня он пришел из машинных языков, к ним –– из аппаратуры, а туда из … откуда? Знаю, что это завязано на человеческом мышлении. Возможно, следующие рассуждения покажутся правдоподобными. Однажды Вове понадобилось описать какой-нибудь алгоритм. Алгоритм он описывал в виде последовательности действий, но не всегда. Временами нужно было выполнить одни действия, а по понедельникам –– другие. Ну а продвинутым инженерам показалось, что достаточно добавить в систему команд процессора команды условных переходов. Легко и просто! Однако в 50-е появляется первый язык функционального программирования – LISP Дж. Маккарти. И там не было Go To. Естественно, программисты-практики тех времен смотрели на него с высока. Сторонники же функциональных языков считают, что программировать в функциональном стиле проще, быстрее. С чего бы это? Тем временем размеры программ росли, программы усложнялись, появились такие новые слова, как «блюдо спагетти», «кризис программирования». Логика программ стала невероятно, непостижимо сложной. Эти многочисленные переходы вниз, вверх, направо и налево уже не могли уместиться в бедной голове программиста, и даже введение блок-схем не спасало положения – стрелок было много. Вот достаточно простой пример (может читатель сможет найти что-нибудь получше): 160 J1=INT(J/100) 170 J2=FNM(J,100) 180 IF M>2 GO TO 260 190 IF J2=0 GO TO 230 200 IF FNM(J2,4)<>0 GO TO 240 210 GO TO 255 230 IF FNM(J1,4)=0 GO TO 255 240 N=2 250 GO TO 270 255 N=1 257 GO TO 270 260 N=0 И вот, попробуйте понять эту программу изменить ее без привнесения ошибок в существующий код Давным-давно, в 30-е годы математики решили формально описать понятие алгоритма. Одни из них стали описывать собственно алгоритмы (машины Тьюринга, машины Проста), а другие описывали (!) функции, которые могут быть вычислены подходящим алгоритмом (частично-рекурсивные функции, лямбда исчисление). Поразительно, да? – возиться с функциями, вместо алгоритмов. Читатель думает, к чему я об этом? Что ж, первый вопрос был понять программу. Не то, как она работает, а что она делает, т.е. функцию, которую она вычисляет (правда, вычисляет компьютер, а не программа). Вот этим и замечательно функциональное программирование – описание функции, а не вычисления. Короче говоря, появились первые статьи, призывающие к структурному программированию. И … не понравились практикующим программистам. Как же так, разве можно записать мою программу с ее многочисленными переходами и запутанной логикой с помощью каких-то трех операторов управления? – недоумевали они. Им привели доказательство, алгоритмическое сведение неструктурированной программы к программе с одним циклом. Зазвучали другие голоса: ведь так не программируют, в программах бывает много циклов. Тем временем Вирт написал статью «Конструирование программ пошаговым уточнением», которая была ответом. Ну и последний аргумент в подобных спорах – это вопрос эффективности. Большие программные системы, разработанные IBM в структурном стиле, показали, что и с этим порядок. Так структурное программирование доказало свою состоятельность. Программы стали писать сверху вниз, от целей к средствам, а не наоборот, как это было ранее. Оформление кода программ в виде лесенки (или гребешка) делало их структуру более понятной. Барьер в размерах программ был отодвинут. Но у структурного программирования оказались свои недостатки. 1 comment|post comment

Барьер в 1000 строк [27 Sep 2006|10:05pm] Барьер в 1000 строк Когда-то во времена моей юности у меня появился комьютер. Это было в конце 10-го класса. И я, как и любой любознательный человек, стал изучать Turbo Pascal. Естественно набил себе много шишек. Возможно, читателю будет интересна одна поучительная история, которая оказала на меня большое влияние. Осенью 11-го класса мой однокашник Денис подкинул идею: написать игрушку "Тетрис". Я с большим энтузиазмом взялся за дело. Как известно (тут бы ссылку на отчет какой-нибудь уважаемой аналитической компании), многие программные проекты создаются дольше, чем ожидалось, превышают смету расходов, не соответсвуют ожиданиям пользователей, а то и вовсе терпят крах. И это был тот самый случай. Поначалу ничто не предвещало неудачу. Очевидные алгоритмы, структура программы и т.п. Но известная (опять это слово -- частый аргумент в спорах) программистская мудрость говорит, что программ без ошибок не бывает. Программа к моменту интенсивной отладки перемещала по стакану одну фигурку, которую еще нельзя было поворачивать. И вот эта примитивная программа в сотню другую строк не работала как надо. Отладчик в Turbo Pascal позволял выполнять программы пошагово и отслеживать значение переменных, т.о. я погряз в трассировки. Прошла неделя, еще одна, а может и две. Ожидаемого эффекта как не было, так и нет. Я бился часами, нервничал вовсю, но ... Короче, я перестал понимать программу и никак не мог найти источник ошибок. В результате я забросил это безпереспективное дело. (Шли недели, месяцы, ...) Но все же я продолжал изучать Turbo Pascal. Прочитал пару книжек, узнал про объектно-ориентированные возможности этого языка. И весной 2002-го я применил эти знания к той же проблеме. Ты знаешь, дорогой читатель, в этот раз получилось! Я мог использовать по отношению к объектам антропоморфные термины: мол, фигурка двигает себя, отображает на экране. Ну в точности как в книжке Фаронова. После каникул (поступив заодно в КГУ ВМК) я спокойно добил программу за пару недель. Я понял: не все так просто в программировании. Вводный курс программирования нам читал замечательный преподаватель. Я понимал его, когда он говорил о сложности программирования, и ловил буквально каждое слово на эту тему. Я выучил определения таких терминов, как состояние, преобразование состояний, тип данных, в то время, как другим студентам они казались вычурными и не нужными. Во время весеннего семестра я получил ответ, почему мне помогло ООП. С тех пор я научился уверенно преодолевать барьер в 1024 строк, даже без использования ООП. Итак вопрос: что за ответ я получил? Что мне помогло в разработке Тетриса? И почему это помогает? 3 comments|post comment

navigation [ viewing | most recent entries ]