?

Log in

No account? Create an account
задача на то, что такое программирование на самом деле - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задача на то, что такое программирование на самом деле [сент. 17, 2018|08:29 pm]
Anatoly Vorobey
[Tags|, ]

Недавно Роб Пайк (один из разработчиков Юникса в классическую эпоху 70-х, соавтор Кернигана, сейчас работает в Гугле) привел интересный пример задания для начинающих программистов, который мне очень понравился. Я не могу процитировать его точные слова, но перескажу суть. Пайк писал о разнице между "программированием" и "разработкой программ" (programming и software engineering), подразумевая тут то, что работа программиста лишь на малую часть обычно состоит в том, чтобы писать новый код с нуля; куда больше времени уходит на то, чтобы читать существующий код, понимать его, изменять в нем ровно то, что нужно, тестировать, отлаживать, убеждать других людей в том, что изменение правильное итд.

Мне это понравилось и потому, что соответствует моим собственным мыслям (см. пункт 1 там), и конкретным примером, который привел Пайк. Он рассказал, что в конце 90-х как-то проводил курс по теме "software engineering" в университете; студенты на этом курсе теоретически уже умели программировать на C, но реально это означало, что они умели писать крохотные программы, выполняющие конкретные домашние задания на предыдущих курсах. Пайк задумался над тем, как наглядно показать им суть рутинной работы программиста.

В итоге первым домашним заданием курса было следующее. Возьмем исходный код редактора ed из версии Юникса V7. Для тех, кто не знаком с ed - это очень простой редактор, знаменитый своей недружелюбностью для незнакомых с ним пользователей. С другой стороны, весь его исходный код укладывается в 1700 строк, и это включает в себя команды редактирования, поиска и замены регулярных выражений, работы с файлами и даже режим шифровки. Для этого задания не нужно учиться работать внутри ed, но если вам интересно, можно прочитать хорошее объяснение.

Внутри редактора ed есть полезная команда - найти и распечатать все строки, отвечающие данному регулярному выражению. Она выглядит так: g/re/p, где re это какое-то регулярное выражение (regular expression). Например, g/long/p печатает все строки, где есть слово "long", g/some.*thing/p печатает строки с словами some и thing, между которыми есть что угодно, итд. Примерно в 1970 году Кен Томпсон, один из авторов Юникса и автор редактора ed, столкнулся с надобностью сделать ровно это, но в большом файле, который был настолько большой, что ed не мог его редактировать. Одним вечером он взял исходники ed, и сделал из них отдельную программу grep (g/re/p), которая делает именно это - находит все строки в файле, отвечающие данному выражению, и печатает их - и работает даже с очень большими файлами. С тех пор это стандартная команда Юниксов.

Так вот, задание Пайка: повторите то, что сделал Томпсон. Взять исходный код ed.c. Вы его раньше не видели, это 1700 строк кода на C, написанного практически без комментариев, но вместе с тем хорошего кода, написанного мастером своего дела. Сделайте из него отдельную программу grep, которая принимает в командной строке два аргумента: регулярное выражение и имя файла. Если хочется чуть большего, добавьте также стандартные опции -v и -n. У вас (пишет Пайк) два преимущества и один недостаток в сравнении с Томпсоном в этом задании. Недостаток в том, что вы не Томпсон. Преимущества в том, что вам это не надо делать на ассемблере (первые версии ed были на ассемблере), и вы уже знаете, что надо сделать, а не придумываете.

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

Вот исходник ed.c, чуть подчищенный, так, что он компилируется на современных системах (Linux/BSD/MacOS; пример командной строки "gcc -o ed ed.c", выдаст кучу предупреждений, но сработает). Ваше задание - сделать из него grep.c. Если хотите, чтобы я проверил - присылайте код мейлом, или ссылкой на github/pastebin.com/куда угодно в комментарии.

Бонус-задание на понимание кода. Разберитесь и объясните, каким образом этот редактор ed дает возможность редактировать файлы размером больше, чем умещается в оперативную память компьютера (а это факт) - как именно это устроено в нем. Для 1700 строчек исходника это в общем впечатляет.
СсылкаОтветить

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: _kum_
2018-09-17 06:54 pm
Хм. Искать ошибку в тысячестроковом чужом коде -- это, оказывается, работа программиста? Нафиг-нафиг... то есть, сочувствую...
(Ответить) (Thread)
[User Picture]From: ppti
2018-09-17 07:26 pm
обычно все еще хуже. ((
а потом вообще оказывается, что это твой код, который ты писал 5 лет назад.

Edited at 2018-09-17 19:27 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: arno1251
2018-09-17 07:29 pm
Скажи, а итоги ты здесь же подведешь, или они будут в отдельном посте? Я участвовать не буду, но хотел бы посмотреть правильные ответы.
(Ответить) (Thread)
[User Picture]From: avva
2018-09-17 08:50 pm
Если подведу в отдельном посте, то дам ссылку здесь.
(Ответить) (Parent) (Thread) (Развернуть)
From: ald1976
2018-09-17 07:38 pm
А зачем разбираться, как именно он редактирует файлы, не влезающие в оперативку?

Классических способов сделать это известно несколько.
Также можно довольно быстро придумать еще 100500 способов неклассических.

Какая разница, как именно это сделал автор древней программы?
Тем более, что, скорее всего, сделать из ed grep можно и без понимания примененных оверлейных методов.

Edited at 2018-09-17 19:39 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2018-09-17 08:54 pm
Когда я начал читать код, мне априори было "очевидно", что такой крохотный по размеру исходника редактор просто читает весь файл в память. Код, связанный с поиском по регулярным выражениям, вполне можно понять целиком, не замечая, что это не так. Чуть позже я вчитался в другую часть кода и заметил, что это не так, и меня это позабавило и впечатлило. Поэтому я предложил это в качестве бонус-вопроса; действительно, вы правы в том, что выбросить все ненужное и подкрутить под grep можно и не разбираясь в этом.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: gul_kiev
2018-09-17 07:56 pm
Теперь кажется очевидная идея, но я не слышал, чтобы в качестве тестового задания на вакансию разработчика предлагали что-то изменить в относительно большой чужой программе, а не написать мелкую свою.
И ведь действительно очень важно уметь понять чужую логику, подстроиться под стиль, ничего не поломать...
(Ответить) (Thread)
[User Picture]From: piggymouse
2018-09-18 05:34 am
Меня так в далёком 1993м брали на мою первую full-time работу. Там был не ed, а толстенная самописная core banking система, но код был нормально организован. Я был зелёный студент-четверокурсник, но ничего, смог.
(Ответить) (Parent) (Thread)
[User Picture]From: moonofnovember
2018-09-17 08:07 pm
Красота
*p1 = t2[(t3[(t1[(*p1+n1)&0377]+n2)&0377]-n2)&0377]-n1;
(Ответить) (Thread)
[User Picture]From: migmit.dreamwidth.org
2018-09-17 10:04 pm
Японский бобёр, это там такое в исходнике?? Нафиг-нафиг.
(Ответить) (Parent) (Thread) (Развернуть)
From: a_chmykh
2018-09-17 08:25 pm
Спасибо, очень интересно и приятно; нравится как общий подход, так и это конкретное задание. Впрочем, именно этот пример ориентирован на системных программистов на чистом C, а для таких сейчас довольно узкая ниша.
Далеко не каждый программист знает, как устроен поиск по регулярным выражениям. Как бы вы оценили собеседников, которые а) знают принцип работы и могут реализовать поиск по регексам "с чистого листа", или б) способны понять реализацию исходя из предложенного кода, или в) способны отрефакторить предложенный код (обрезать всю функциональность ed, кроме grep) без понимания алгоритма?
(Ответить) (Thread)
[User Picture]From: avva
2018-09-17 08:50 pm
Я думаю, что компетентный программист на C/C++ должен уметь сделать в), даже не разбираясь в том, как работает реализация. б) тоже должно находиться в пределах досягаемости, хотя если человек никогда не имел дело с этой проблемой, потребует внимательного и настойчивого разбора кода (но это умения, которые необходимы компетентному программисту).

Насчет а). Я иногда на интервью прошу кандидата написать реализацию поиска по регулярным выражениям с ограниченным языком (например, только a-z, . и *; или другие похожие вариации). Т.е. от кандидата в Гугл я ожидаю, что он сможет за 40 минут написать это без багов на любимом языке программирования, даже если не писал в прошлом реализацию такого поиска.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: rezdm
2018-09-17 09:16 pm
Я сейчас работаю в проекте, в котором решаю, эхм, проблемы в файлах по 5000-7000к строк, с функциями на сотни строк.
(Ответить) (Thread)
[User Picture]From: efix
2018-09-17 09:53 pm
Может кто-нибудь порекомендовать почитать хороший код на С#, написанный мастером своего дела?
(Ответить) (Thread)
[User Picture]From: pigmeich
2018-09-18 01:16 am
\Github\TaylorSwift
(Ответить) (Parent) (Thread)
[User Picture]From: Dmitry Lyubarsky
2018-09-17 10:10 pm
(Только сейчас, когда решил оставить комментарий, заметил, что последние твои посты ты в фейсбук не кросспостишь. Доколе?!!)

Идея хорошая, тут главное не переборщить. Я на 2 курсе института временно передумал становиться программистом после курса, на котором нас учили "взрослому программированию". Типа: что-то там -> функциональные требования -> какие-то еще требования ->код -> тест план -> что-то там еще. Заставляли простые задачи, типа поиска подстроки в строке, через этот кошмар пропускать. Я реально подумал, что взрослые люди так программируют и решил стать "ученым". Потом выяснилось, что преподаватели наши работали в авиакосмической фирме, откуда свои стандарты перенесли на курс, не предупредив о том, что нормальные программы так не пишут. А "настоящее" программирование оказалось еще даже более интересным, чем те небольшие вещи, которые я в школе делал, потому что сложнее.

Чтобы два раза не вставать: код производит интересное впечатление. С одной стороны, завораживает, чувствуется, что "сейчас так не умеют". С другой стороны, назвать его хорошим с точки зрения современных стандартов я никак не могу. Зачем я должен гадать, что делает global()? А filename()? Или, еще хуже, мне предлагается не гадать, а _читать код_?? Вот реально, прочитать весь метод, чтобы догадаться (но и тогда непонятно). Почему нельзя тупо написать в комментарии (больше 8 символов ведь нельзя было тогда переменные называть, да?). С точки зрения современных стандартов это практически write-only code.
(Ответить) (Thread)
[User Picture]From: pigmeich
2018-09-18 01:18 am
Авиакосмические программеры != нормальные.

ОК.

P.S. Зачем я писал для авикосмоса?
(Ответить) (Parent) (Thread)
[User Picture]From: neatfires
2018-09-17 11:02 pm
Одна из вещей, которые меня раздражают в C, - это что без специальных умных инструментов (ака IDE) непонятно, какая функция откуда импортирована. Скажем, a.c includes b.h, which includes c.h, which defines f(). Чтение кода, который и так обычно скудно снабжен комментариями, становится от этого еще сложнее.

Другая - это глобальные переменные. В коде ed их просто немерянно. Даже никаких попыток структурировать информацию на глобальном уровне - тупо 55 глобальных переменных. Я понимаю, что в 70-х так писали, но уже давно нет :) Тогда, видимо, структурная информация передавалась через какие-то конвенции, к настоящему времени позабытые. Поэтому вряд ли из ed.c можно сделать подходящее задание для современного программиста. Хотя с антропологической точки зрения интересно.

О таких мелочах, как поинтеры, undefined behavior, stack corruption, отсутствие удобной обработки ошибок, супер-неудобные APIs, крайне скудный синтаксис, нехватка механизмов абстракции и структуризации кода (генерикс? модули? контракты?), плохая портабельность и verbosity я уже просто молчу :)

Edited at 2018-09-17 23:08 (UTC)
(Ответить) (Thread)
[User Picture]From: pigmeich
2018-09-18 01:11 am
> подразумевая тут то, что работа программиста лишь на малую часть обычно состоит в том, чтобы писать новый код с нуля; куда больше времени уходит на то,

Так...

>чтобы читать существующий код,

Написанный орангутантами? С использованием недокументированных фич языка?

>понимать его,

Сначала поймитите какой-нибудь advanced algorithm из Википедии.

>изменять в нем ровно то, что нужно,

Давно установлено, что проще и быстрее собрать все issue и переписать код под них всех.

>тестировать,

Манки-тестерами? Или это для манки-тестеров?

>отлаживать,

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

>убеждать других людей в том, что изменение правильное

Ну наконец-то! Надо "Лестницу в небо" прочитать оказывается.

>итд.

Под этим видимо подоразумевается сексуальное ублажение начальников и подкуп ХРюш. Или наоборот.
(Ответить) (Thread)
[User Picture]From: urod
2018-09-18 05:42 am
В пандан к этой новости: в продаже появился набор юного генного инженера. В наборе шесть живых лягушек, корм для них и всё необходимое, чтобы отредактировать генотип их лягушат с помощью CRISPR.

Не шутка.

Edited at 2018-09-18 05:42 (UTC)
(Ответить) (Thread)
[User Picture]From: grey_kristy
2018-09-18 08:43 am
> Вы его раньше не видели, это 1700 строк кода на C, написанного практически без комментариев, но вместе с тем хорошего кода, написанного мастером своего дела.

Как то не поворачивается язык назвать это хорошим кодом.
62 глобальные переменные на 1700 строк кода? Серьезно?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: old_radist
2018-09-18 09:15 am
Видно, что хороший человек писал, с правильными фигурными скобочками.
(Ответить) (Thread)
From: humanbean194
2018-09-18 01:08 pm
Правильными это когда тела функций пишутся по-сишному, а тела блоков внутри функций — по-джавовски?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: rudnev
2018-09-18 11:34 pm
а зачем вообще начинающему программисту писать на С?
это сжирает уйму времени, платят за это не то что бы очень, этот навык в другие полезные никак не конвертируется (т.е. что такое лямбда, транзакция, mapreduce, whatever - нет никакой возможности оттуда узнать).

рабочий рынок сишников сильно ограничен, к тому же.

свой проект на си не запилишь.

т.е. понятно, зачем это было нужно Пайку двадцать лет назад.

а сейчас этот навык сродни чистописанию, вышиванию крестиком, выучиванию больших текстов наизусть, - т.е. можно при желании,
но это скорее во вред.

(ну т.е. я сам потратил известное время на С\С++ под влиянием классиков, но в принципе кроме небольшого расширения кругозора и повышения ЧСВ, это мне, видимо, ничего не дало. При неиспользовании это все вымывается начисто).

И были же люди, которые улыбались и говорили: "не надо ничего делать на С. И на ассемблере не надо. И Кернигана не надо читать." И нужно было слушаться, на самом деле.
(Ответить) (Thread)
[User Picture]From: old_radist
2018-09-19 07:42 am
>> рабочий рынок сишников сильно ограничен, к тому же.

Это не недостаток, а вопрос собственного темперамента. А в ограниченных нишах хорошо платят.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: begundan
2018-09-20 04:30 pm
пилот варит мандарины
(Ответить) (Thread)
Страница 1 из 2
<<[1] [2] >>