Комментарии 224
Тоже с год как подсел на метапрограммирование. Правда, на плюсах)
Конечно, выписывать вручную все эти типы будет несколько утомительно, но если сюда прикрутить макросы — можно процедурные для красивого синтаксиса
fn main() {
<List as AsStrList<{ n_digits(<N as NumericValue>::VALUE) }>>::LIST
.for_each(|s| println!("{}", s.as_str()));
}
Наверное интервьюер решил, что в продакшене потом так же будет, и сбежал.
Хороший рассказ, качественно написан.
Meanwhile, in our universe:
…
Я открыл Rust playground и начал писать код:
struct Z;
struct S<T>(T);Интервьюер слегка нахмурился.
— Не могли бы вы пояснить, что вы делаете?
— Конечно. Я делаю свои собственные числа согласно аксиоматике Пеано...
— Извините, вы не подходите нам по софт-скиллам
Шутки шутками, но на своё "джунство" я попал благодаря софт-скиллам, у меня были(есть) пробелы в знаниях, но по фидбэку от HR моему ПМ и ПО я понравился как человек, манера общения, реакции в стрессовых ситуациях. Пробелы сказали, что заполнят.
Это если у самого интервьюера хорошо прокачаны софт скиллы. А ведь может и му***ом назвать
Мне кажется, если интервьюер заворачивает соискателя только из-за того, что не понимает терминологии, которой употребляет соискатель, и при этом даже не пытается спросить её значение, то это не очень хороший интервьюер.
Так может он понял терминологию и именно поэтому и завернул.
Заворачивать сразу считаю тут дурным тоном. Я бы чисто из интереса посмотрел, что интервьювер напишет. А бонус раундом был бы ответ "а в прод в бы так же писали?" — ответы могут быть совершенно разными. Ну а если время отведенное на задачу давно вышло а она сделана только на половину — что ж, тут уже очевидный пробел в грамотной оценки трудоемкости задач, и вот это уже может быть основанием ля отказа. Но никак не "ой, он написал data Num = Z | S Num"
Я бы чисто из интереса посмотрел, что интервьювер напишет.
Оговорка по фрейду или взгляд глазами соискателя?..
Трудоемкость скорее всего оценили неверно — но кто из двоих, как раз совсем не очевидно. Вы же наверняка читали похожую историю про задачу на копирование файла? Интервьюер там тоже наверняка считал ее простой, в тоже время, при всей дотошности (и даже занудстве) кандидата, нельзя сказать, чтобы он задавал бессмысленные вопросы, не имеющие отношения к делу. Ну и потом, если вы хотите оценить способности кандидата к планированию — можно же прямо задать ему вопрос, за какое время он планирует это реализовать?
И еще аспект — я лично обычно пытаюсь кандидата разговорить, думаю что многие делают тоже самое — потому что кроме умения решать задачи обычно интересно и умение человека рассказать, что он сделал и почему, а еще интересно узнать, как он думает. В такой ситуации считать промашку с оценкой серьезной вряд ли стоит. Уж лучше сразу кандидату временные рамки ограничить. Не сумеешь за 15 минут рассказать, как на типах в расте решить вот это — не начинай, выбери решение попроще.
Интервьюер там тоже наверняка считал ее простой, в тоже время, при всей дотошности (и даже занудстве) кандидата, нельзя сказать, чтобы он задавал бессмысленные вопросы, не имеющие отношения к делу. Ну и потом, если вы хотите оценить способности кандидата к планированию — можно же прямо задать ему вопрос, за какое время он планирует это реализовать?
Время интервью обычно заранее известно и стоит в каленаре. Задача не должна занять больше, чем все время собеседования.
И еще аспект — я лично обычно пытаюсь кандидата разговорить, думаю что многие делают тоже самое — потому что кроме умения решать задачи обычно интересно и умение человека рассказать, что он сделал и почему, а еще интересно узнать, как он думает.
Ну так тут вполне хватало и разговоров, и озвучивания что делается и почему.
Уж лучше сразу кандидату временные рамки ограничить. Не сумеешь за 15 минут рассказать, как на типах в расте решить вот это — не начинай, выбери решение попроще.
На собесах в фаанги принято кстати сначала сделать дуболомное решение, а потом уже его улучшать. Как раз чтобы в любой момент "время стоп" было хоть что-то рабочее.
Именно. Так я и говорю — интервьюеру-то чего тут обижаться? Тут все прекрасно о человеке понятно, а если ты скажем не понимаешь, что такое аксиоматика Пеано, или не знаешь чего о расте (но тебя ведь за язык не тянули разрешать писать на чем угодно, верно?) — ну так эта, тебе же язык для этого дан, спроси, правда же?
Будь я реально интервьюером в такой ситуации — я бы скорее остановил бы автора по другой причине. То есть, спросил бы достаточно рано, а какие другие решения он видит, и каковы их преимущества и недостатки. А потом уточнил бы критерии качества решения.
>Как раз чтобы в любой момент «время стоп» было хоть что-то рабочее.
В этом наверное есть смысл, но с учетом желания разговорить — лично для меня наличие рабочего уже не так важно.
А если интервьюер как раз таки понимает в метапрограммировании но ему в команде не нужны душнилы пытающиеся щегольнуть своим знанием всяческой эзотерики и воспринимающие это знание языка как индикатор превосходства над простыми смертными а не как инструмент для решения задач?
Если вы пропустили, этот рассказ достаточно толсто отсылается к другому прекрасному посту.
О чём был этот пост, скажите, пожалуйста. По ссылке нет доступа.
Автора почему-то тотально удалили с Хабра. Вот ссылка на копию в web archive
Я что-то подобное всегда представляю, когда в Discord пишет %USERNAME% is playing Rust.
— На хаскеле было понятнее, — резюмировал интервьюер, и подняв взгляд куда-то в окно добавил, — а где доказательство что компилятор не ошибся?
— Корректную работу компилятора мы принимаем за аксиому, без этого мы бы просто не смогли писать программы.
Существование багов и разночтений в компиляторах - хорошо известный факт. (Разночтения возникают на дефектах спецификации языка).
И при программировании нужно учитывать, какие места в языке компилируются хорошо, а какие - нет.
Юнит-тесты, в том числе, служат выборочной проверкой корректности скомпилированной программы. А уж разбираться, кто ошибся - программист в программе, или компилятор, - дело второе.
Не скажу за Rust, а вот на C++ точно - в хитровывернутых шаблонах можно отгрести люлей от ошибок компилятора или стандарта. Если знать, где искать, или если натолкнуться на свежий баг.
Существование багов и разночтений в компиляторах — хорошо известный факт. (Разночтения возникают на дефектах спецификации языка).
А ещё есть errata. И космические лучи. И ещё 100500 источников багов, которые учитывать в разработке совершенно непрактично. Мы берем это за аксиому вне зависимости от того, верно это или нет. Просто потому что там проще жить. Я больше доверяю условному гхц/гцц, чем с обственному коду.
Не скажу за Rust, а вот на C++ точно — в хитровывернутых шаблонах можно отгрести люлей от ошибок компилятора или стандарта. Если знать, где искать, или если натолкнуться на свежий баг.
Пока что не встречал ни 1 бага от компилятора раста, который бы не упал с паников проверки инварианта в его кишках. Да и с ними тоже встречался в сложных случаях и буквально пару раз за 5 лет.
https://github.com/rust-lang/rust/issues?q=is%3Aissue+is%3Aopen+label%3AC-bug
2729 Open, 5645 Closed.
Ну такая себе аксиома, конечно.
Лучше ответить, что на этот случай у нас должен быть отдел QA с автоматическими интеграционными тестами для проверки требований заказчика/бизнеса, написанными с использованием инструментов никак не связанных с языком разработки. И весьма маловероятно что никак не связанные друг с другом тулы сломаются таким образом, что при выполнении разных алгоритмов для достижения одинакового результата будут показывать одинаковый неправильный ответ
А у вас (где вы щас работаете) такой отдел есть? У нас вот просто нет, и я даже лично не знаю никого, у кого бы такой был.
Уже в паре компаний встречал такое.
В одной продукт на C#, а тесты на Java. В другой продукт на C#, тесты на JS.
Я что-то не понял, как это защищает хоть от чего-то. У нас вот тоже код на C# написан, а тесты на TS и питоне.
Я про проверку того, что компилятор правильно скомпилировал наш код. Как это сделать, не реимплементируя компилятор мне даже не сильно понятно сходу. И уж точно я не видел это в реально продакшне, там куда более ценные и дешевые проверки зачастую не делают ведь "и так понятно что работает".
Отличное уточнение в вопросе! Ведь не нужно проверять правильность всего компилятора, достаточно проверить что программа написана, скомпилирована и отконфигурирована без ошибок.
С т.з. бизнеса - эти все ошибки вообще равноценны - его интересует лишь возвращает ли разработанная система (сколь сложной бы она ни была) ожидаемый результат или нет.
Хороший способ убедиться - запустить систему в контролируемом окружении и сравнить возвращаемый результат и ожидаемый для определенного набора входных данных.
Это кажется и есть определение тестирования.
Ну а дальше уже пытаемся как можно сильнее отделить тестовое окружение от возможных сайд-эффектов, балансируя между требуемым уровнем уверенности в результате, ресурсами и здравым смыслом. Если ожидаем подвоха от реализации, генерируем ожидаемый ответ используя другой алгоритм (например вычисляем ожидаемое значение вручную и хардкодим). Если нет уверенности в компиляторе, то для генерации тестов очевидно нужно использовать независимый компилятор. Тем самым мы сильно уменьшаем вероятность того что разные люди ошибутся по разному, но их ошибки в тесте компенсируют друг друга таким образом, что тест даст ложно-позитивный результат.
Ну а дальше уже пытаемся как можно сильнее отделить тестовое окружение от возможных сайд-эффектов, балансируя между требуемым уровнем уверенности в результате, ресурсами и здравым смыслом.
Как известно, тесты показывают только то, что тестовые сценарии проходят. В отличие от типов, которые корректность доказывают для открытого класса проблем. И подходу "компилятор в котором может быть ошибка, но который верифицирует программу" против "просто написали что угодно а дальше накрутили тестов" я всегда предпочту первый. Если только ублажать компилятор не слишком дорого.
Тем самым мы сильно уменьшаем вероятность того что разные люди ошибутся по разному, но их ошибки в тесте компенсируют друг друга таким образом, что тест даст ложно-позитивный результат.
Немного наивное предположение, как мне кажется. Особенно когда разработчики второго компилятора пишут не с закрытыми глазами код, а поглядывая в первый (привет, реактос).
Есть же исследование по GitHub, в котором показано, что типы не снижают концентрацию багов. Так что... Ошибки в типах обычно довольно грубые, и сразу же проявляются на тестах, поэтому редко просачиваются в коммиты.
Более же тонкие алгоритмические ошибки системы типов не вылавливают. Даже с зависмыми типами можно написать так, что всё будет проходить проверки, а фактическое поведение будет багованное и не будет соответствовать реальности.
и далеко не все проекты одинакового уровня
Но также и то, что случайный человек не пойдет в хаскел и агду, в отличие от питона с js, а значит и требования к такому человеку выше.
но и как быстро вы разрабатываете код, и насколько этот код поддерживаем
Вроде была чуть похожая статья
Сложно сказать, насколько это всё релевантно. Они проделали это с конкретными 400 bugfix-ами, говорят, что случайными, но даже негде посмотреть на список этих bugfix-ов. В статье есть битая ссылка. Поэтому, ну... Может быть, а может быть и нет.
Независимое исследование от PVS говорило ровно о том же, к слову.
Доверия к "On Programming Language Impact" у меня больше, потому что есть данные и методика, и исходники, можно всё проверить. В "To Type or Not to Type" есть только текст статьи и битая ссылка на данные, с которыми они работали.
Как-то это не очень...
Если у PVS более качественное исследование, был бы весьма признателен за ссылку.
Заключение обсуждаемой статьи формулируется так "Количество выявляемых багов в популярных проектах на GitHub не зависит от языка программирования". Можно говорить, что на разных языках пишут разное по сложности, но в статье есть описание методологии сбора данных, можно её применить, и увидеть, что в выборку попали компиляторы не только на Haskell.
Гонки вообще плохо выявляются. Системы типов в этом не помогают. Rust обещает, что гонок не будет, но учитывая объёмы unsafe кода, который приходится писать для реализации даже простейших структур данных, сложно на это обещание полагаться. Да и баги в системе типов тоже никто не отменял. Какие-то виды гонок отлавливаются, конечно, типами, проверкой моделей, разделяющей логикой, но гораздо лучше, чтобы runtime семантика системы вообще не позволяла гонку создать.
Подходы Erlang, Oz или Clojure намного безопаснее в этом смысле.
STM помогает, но для эффективности нужны хитрые кеши. Линейные типы ограничивают выразительные возможности весьма существенно. Многие базовые алгоритмы синхронизации линейно не протипизировать (алгоритм Деккера, например). Сессионные типы помогли бы, но они сводятся к проверке моделей, что затратно для больших проектов. Нет тут панацеи, к сожалению.
В теме HFT не разбираюсь, но поиск по HFT Clojure выдаёт результаты. Ну, и на TechEmpower пишут, что Clojure может более 60000 обновлений в секунду обслуживать. Этого достаточно для HFT?
Кроме того, тут возникает вопрос: насколько эффективно это всё может быть вообще скомпилированно? Этими вопросами почти никто и не занимался, насколько я могу судить по научным публикациям. Мэйнстрим сосредоточен на теории типов и на эффективной компиляции для GPU или TPU, полиэдральные преобразования и тому подобное.
Поэтому не известно, насколько реализации агентов, процессов или распределённой унификации могут быть эффективны в пределе. Вот Haskell уделывает же Java и даже C в некоторых задачах. JS тоже поражает эффективностью. Кто бы мог подумать лет 20 назад? Но над оптимизациями в Haskell и JS усердно и долго работали. Кто знает, до чего можно раскочегарить Erlang, если взяться серьёзно?
Для эффективности Erlang специальное оборудование не нужно. Достаточно обычных межпроцессоррых прерываний, которые и так на всех платформах есть. А вот чтобы STM быстро работала нужны транзакционные кэши, которые были (не знаю, как сейчас) в IBM Power каких-то серий.
Так в этом и смысл. Да и наличие линейных типов не требует от вас их использовать там, где в линейные типы что-то не впихивается.
Не впихивается очень многое, к сожалению, из необходимого на практике.
Сессионные типы через зависимые не выражаются. Есть урезанный вариант, который можно выразить (label-dependent), но в нём коммуникация ограничена только, так называемыми, рандеву.
<просто-мысли>
Не знаю. Можно, конечно, усложнять и усложнять системы типов, увеличивать сложность чекеров, потом усложнять структуры алгоритмов, чтобы они в эти системы типов вписывались. Наверное, это приемлемый путь. Проблема, однако, в том, что не у всех есть такое количество времени и интеллектуального ресурса, которые необходимы, чтобы это всё осваивать и применять, особенно, с учётом необходимости усложнения структуры алгоритмов.
Вот прохожу я курс по компьютерному зрению для автопилотов, где нужно думать о куче математических моделей. Мне совсем не хочется при выполнении заданий думать ещё и о временах жизни переменных или о функторах. Поэтому я не буду программировать это на Haskell или Rust. Опять же, типы не схватывают корректность необходимых для решения этих задач алгоритмов. Поэтому, я использую Julia или Python. Не круто, зато, работает.
</просто-мысли>
А можно ссылку на исследование?
https://web.cs.ucdavis.edu/~filkov/papers/lang_github.pdf - исходная статья с описанием метода сбора данных, но с ошибками в статистическом анализе.
https://arxiv.org/pdf/1901.10220.pdf - статья с более точным анализом тех же данных.
Хоть авторы и говорят про "незначительную разницу", по моему разница между самым "плохим" (эх, C++) и самым "хорошим" (Typescript??) языком составляет почти 2 раза
А разница между python и haskell меньше чем 1.5 раза
Это вы о каких числах говорите?
О числах, которые называются coeff.
В первом документе написана методика подсчета
We can read the coefficients as the expected change in the log of the response for a one unit change in the predictor with all other predictors held constant; i.e., for a coefficient βi, a one unit change in βi yields an expected change in the response of e βi
Thus, if, for some number of commits, a particular project developed in an average language had four defective commits, then the choice to use C++ would mean that we should expect one additional buggy commit since e 0.23 × 4 = 5.03
e^(0.22)/e^(-0.41) = 1.88
Лучше результаты смотреть во второй статье. Там указаны ошибки первой работы, сделан пересчёт и получены другие значения, не такие впечатляющие.
Да, результаты я брал из второй статьи, а методику подсчета из первой. Если честно, не увидел прям сильного отличия в результатах
Ну такая себе аксиома, конечно.
Потому что лучше сказать, что "компилятор выдает только корректный результат компиляции".
По вашей ссылке большая часть проблем — какие-то краши компилятора, медленная работа, нестабильные (сырые) фичи и ещё тысяча вещей. Обычно компилятор просто не выдает программу в таком случае.
Гораздо лучше смотреть на приоритеты. Получается отношение open/closed такое: P-high: 88/945, P-critical: 1/75. Уже гораздо выглядит, причем их них I-unsound только 21/80, а единственная открытая critical про то, что некоторый код вдруг перестал компилироваться на бета-ветке.
Не говорю, что это идеально, но уже гораздо ближе к правде, чем страшные 2729/5645.
Задача FizzBuzz - это мемчик (хотя половина соискателей написать не могут), а статья - ирония. Как я понял, автор решает задачу на основе введения типизации компилятора, так, чтобы ответ был до запуска программы.
Пожалуйста, и не один.
у вас же ошибка, число печатается в любом случае, а нужно fuzzbuzz печатать ВМЕСТО числа.
Кроме того, работа с i в трех местах, что мешало использовать классический for цикл ?
print('\n'.join(f"{'' if i%3 else 'Fiz'}{'' if i%5 else 'Buz'}" or f'{i}' for i in range(100)))
deleted
Во-первых, ваша программа работает неверно. Вы печатаете число вообще всегда, а по условию задачи "если ни одно из этих условий не выполняется, то выведете число как обычно".
Во-вторых, статья вообще не об этом.
Функциональное программирование — разновидность декларативного.
Поспорить можно всегда, но я не хочу заниматься буквоедством, а руководствуюсь более-менее общепринятой классификацией, описанной в т. ч. в Википедии.
Контрол флоу может быть неочевидным для ленивого ЯП, но для строго ЯП вполне определен. А строгие ФП языки есть, тот же идрис.
Получается, почти любой язык функциональный (и заодно декларативный).
Да, а в чём проблема? Так же как почти любой язык императивный. Одно другого не исключает, если имеется более-менее полноценная возможность писать в любом из вариантов.
То что определение, в которое попадает всё множество объектов — тавтология, и бесполезность. Определения нам нужны, чтобы разбивать объекты на классы, а не просто чтобы придумать новый синоним слову "любой объект".
Так ведь не всё множество, а большинство современных. Остаётся как минимум пачка более старых языков, которые живее всех живых, но даже лямбдами не обзавелись (ну там C, Fortran, COBOL...)
Насколько функционален Rust с учётом проблем с funarg и композируемостью — вопрос тоже дискуссионный.
Мне сложно вводить определения, но чисто эмпирически кажется что Haskell/Idris/Scala функциональные, а Rust/C#/Java/JS — нет. И если пытаться их кластеризовать, то кажется что функциональность в первую очередь про систему типов, которая позволяет выражать и удобно работать с эффектами. Без этого нет ссылочной прозрачности, а без неё нет и ФП. Это куда полезнее чем некие first class citizen функции.
Плюс там нет условия для fizzbuzz вывода т.е. когда одновременно модуль равен нуль при делении на 3 и на 5
Но ведь ваш код неправильный. Для числа 3 будет выведено "3fizz".
Спасибо, вы не прошли так как не умеете делать тесты.
Т.е. вам полминуты хватило чтобы начать строчить "КГ/АМ, статья мусор"? Стоит наверное побольше времени уделять критичности своего мышления, а то какое-то крайнее высокомерие и желание поиграть в уставшего от жизни циника, вокруг которого одни бездарности.
Ага, то есть вы прочитали тз, потратили кучу времени на относительно левый материал, забыли конкретное тз за 10 минут и.... вместо того, чтобы потратить 30 секунд на повторное прочтение тз, вы сразу ломанулись в бой? А еще из вашего же коммента понятно, что вы вполне знакомы с задачей... но не помните такого важного уточнения?
Или вы это недосмотрели, такой микро косяк? Так это, опять же, проблема тестов и проверки. А вы кинули в прод даже без компиляции на тесте. Зато хвастаетесь скоростью. Вспоминаю анекдот.
- А я считаю со скоростью калькулятора!
- 263478 * 12786
- *мгновенно отвечает* 42!
- ???
- Я сказал быстро, а не правильно
В общем, в любом случае вы собеседование не прошли.
На самом деле я не внимательно прочитал задание и первый вариант кода родился буквально за полминуты.
Если вы еще не поняли, основной смысл fizzbuzz - написать без ошибок с первого раза. Проверка идет не знаний языка программирования, а вашей внимательности к тех.условиям и вашему результату.
P.S. Понятно, что без фанатизма - без ошибок с первого раза программа не обязана отработать корректно, но ожидается, что она должна без ошибок отработать, когда вы ее уже "сдаете заказчику", а это вы сделали, когда опубликовали ваш код в первом комментарии.
Чего только люди не делают, чтобы не писать на Idris, Agda.
Так из контекста ясно, что он собеседовался на позицию в компьютер-сайенс-ресерче и ему не перезвонили именно из-за этого. Он просто выбрал не тот язык.
А для этого я слишком тупой, извините ?
На идрисе по-моему ничего практичного написать нельзя. По крайней мере даже примеры из конца книжки TyDD компилируются по 10 секунд, и это для пары сотен строк кода. Агда же лично меня вымораживает ютфом — можете называть меня старомодным, но если я вижу код который нельзя написать с помощью ascii клавиатуры то мне становится грустно. Да и честно говоря для людей, не изучавших 5 лет в универе математику какой-нибудь isValid(isMemberOfSet(x, Y)) проще математической нотации говорящей о том же самом. Даже если она в 10 раз короче.
Если честно, я не припомню, по крайней мере, своей фрустрации от этого, может, после C++ было норм. В любом случае, в Idris 2 сильно улучшили скорость тайпчекинга, особенно на богатом имплиситами коде.
Ну мне на полном серьезе говорили не использовать Nat чуть менее чем везде. Попытка сделать toNat intMaxValue закончилась для меня печально.
Пишу на обычной клавиатуре, полёт нормальный, просто каждый уникодный символ требует пару-тройку нажатий :]
Вот что-что, а учить мнемоники каждого юникод символа я точно не хотел бы. Люди с мат. бекграундом конечно очень радуются, когда получают возможность писать на нативном языке предметной области, но мне кажется, что этот подход пусть остается в этих ваших мэплах/маткадах, а в коде должно быть ascii. ИМХО конечно, юммв.
Интересно, если заявить, что уже есть эталонная реализация FizzBuzz Enterprise Edition на Java -- это прокатит на собеседовании:
https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition.git
Кстати, а почему не попытаться сделать стандарт IEEE для FizzBuzz?
Шаблоны в С++ куда понятнее как по мне... И в С++ это пишется одной обыкновенной функцией consteval, которая формирует строку, далее constinit строки и вывод. Даже магии не надо и всё будет вычислено на этапе компиляции.
Да и без consteval штук просто на типах, скажем index sequence, вычислил бы за меньшее количество строк и понятнее
А вы покажите, как это будет выглядеть. Насколько я помню, в constexpr-функциях можно использовать std::string, но нельзя это значение возвращать.
Выглядеть это будет примерно так:
https://godbolt.org/z/664venGW3
Перевод из строки в число на компайл тайме достаточно неудобная задача, но что ш...
Благодарю. А теперь прикиньте, в скольких местах придётся править код, если нам понадобится поменять верхнюю границу. В моём варианте достаточно поменять определение N.
Вот, держи, 51 строка вообще без использования стандартной библиотеки, выдаёт результат не просто на компиляции, а в ошибке
https://godbolt.org/z/31cnb5sdf
Посмотрел. Итого выходит, что перевод из числа в строку (точнее, в структуру c) происходит при помощи специализации шаблонной структуры to_string по подставленному значению. На мой взгляд, это весьма неряшливый подход. Более того, в текущей форме он ещё и может сломаться при переносе между компиляторами: multi-character character literals определяют значения типа int, но это поведение implementation-defined, то есть, строго говоря, у нас нет гарантии, что, скажем, 'fizz' не попадёт в диапазон от 1 до 100. То, что эти значения потом неявно конвертируются из int в unsigned — тоже не прибавляет уверенности.
Если уж и сохранять общий подход к переводу в строку, то можно было бы: убрать аннотации значений у вариантов анонимного перечисления, в Transform для варианта, когда число остаётся как есть, возвращать value + 3, а в реализации to_string по умолчанию писать using type = decltype(ToString<Value - 3>);. Но этот вариант плох тем, что вносит магическую константу, которая ещё и повторяется дважды, и технически всё ещё исключает три числа из диапазона, который он в состоянии корректно напечатать — благо, это три числа из верхней границы диапазона, и компилятор, скорее всего, грохнется с OOM при попытке напечатать fizzbuzz-список с таким количеством чисел.
А, и ToString всё ещё не в состоянии обрабатывать числа больше трёх знаков.
так тут строки в тип перевели, а в версии на расте просто
struct { val: &str }Меня очень умиляет как вы придираетесь к тому что реализация выдающая результат в ошибке КОМПИЛЯТОРА "зависит от реализации компилятора". Остальные придирки того же уровня...
Товарищ, таки где нормальный ToString?
Просто не надо переводить строки в массив чаров на уровне типов, достаточно просто сделать constepxr функцию
template<size_t n>
auto constexpr gen() {
std::array<char, count_digits(n)> arr;
if (n == 0) {
arr = {'0'};
return arr;
}
size_t x = n;
auto it = arr.begin();
while (x > 0) {
if (it == arr.end()) {
throw std::logic_error{"ooops"};
}
*it = (x % 10) + '0';
x /= 10;
++it;
}
std::reverse(arr.begin(), it);
return arr;
}и получать нужный массив как constexpr auto data = gen<n>()
А ещё тут места под лишние цифры не выделяется.
FastToString выглядит так же, как у автора (за исключением того, что у него код корректен для любого N).
Что до самого вывода, то выглядит конечно ближе к обычному языку, чем акробатика на типах из статьи. Но смотря на выхлоп компилятора кажется что вышло не очень — миллион mov BYTE PTR $S1$5[rsp+531], 0. К сожалению, полученного кода автор не выложил, надеемся что добавит.
AnthonyMikh Добавь ссылку на гист в конце, интересно же поковырять :)
https://godbolt.org/z/cq9sWqMhP
- Более чистый вариант в ассемблере без
<iostream>. Хороший трюк — отправлять вывод в volatile-переменную, тогда и компилятор его и не выкинет, и не требуется I/O. - При включенной оптимизации результат вообще красиво слёг в статическую строку, а
mainвекторизовался, лол. MSVC, моё почтение.
В Rust тоже есть "const" фукнции, которые вычисляются во время компиляции. Но с их использованием статьи бы не получилось.
Юмор понятен, конечно. Но на месте интервьюера я бы пообщался с человеком еще, с целью понять - это он так странно шутит, или реально он так и работает. Если не шутит, то "мы вам перезвоним". Имею неудовольствие работать вот прямо сейчас с проектом, написанным в стародавние времена такими вот любителями все сделать "круто". На практике такая "крутизна" выливается в то, что даже очень сильные разработчики в коде разбираются плохо, и он переполнен сложно воспроизводимыми багами, которые править крайне тяжело, практически из-за каждой ерунды приходится подолгу сидеть и разгадывать "крутые ребусы". Ошибки обычно не локализуются каком-то одном легко обозримом месте, а расползаются почти по всему проекту, изменение где-то в одном месте может дать неожиданный эффект в казалось бы малосвязанным с ним другом модуле.
Ну интервьювер конечно терпеливый излишне. Возможно он ожидал, что задача вот-вот кончится, но она и не спешила заканчиваться, а он все терпел и терпел и терпел...
Какой смысл сидеть и с умным видом делать гримасы полного понимания происходящего. Если уж тебе не понятно с самого начала и далее по тексту, то зачем продолжать? Вы видите что человека так сказать понесло в интерес, ну остановите его и попросите теперь постараться объяснить все то, что он сделал до определенного момента, на языке понятном для интерна-джуна. Если он опять будет объяснять в тех же понятиях и принятой им парадигме или скажем не сможет объяснить это в виду избыточной сложности или еще чего-то, то пожалуй работать с ним в команде не получится. А если этот человек весьма уверенно может это перевести на простой язык, то пожалуй это всего лишь тонкий троллинг и кандидат умеет работать, поговорите с ним еще о чем нибудь.
Представляю картину, приходит мужик устраиваться шахтером. Его просят продолбить в стене 100 дырок. Он вместо этого начинает собирать бомбу с часовым механизмом и удаленным управлением с мобильника, объясняя это тем что хотел бы избежать ненужных долблений дырок, а лучше захреначить всю стену сразу.
А то у нас как-то один кандидат — доброжелательный интервьюер на секунду поёжился — как-то развернул список на чём-то вроде Haskell и даже тестов не написал.
Крайне порадовала отсылка к 0xd34df00d
Умей раст нормально в const и статьи бы не было
Это всё можно и на const fn написать. Но изначально у меня была цель всё сделать на типах.
С ходу не знаю можно ли: там и for и mut, хотя не проверял, но в плане того что можно в const - раст в текущем состоянии очень ущербен
Не специалист по Расту, но нельзя ли сделать реализацию попроще с той же идеей? Например, вместо списка и его обращения реализовать шаблон, или как тут это называется, который увеличивает значение на «1», а для «100» останавливается. Наверное, вместо конвертации в строку тоже можно как-то попроще…
Мне кажется, я это уже где-то читал.
Да, на Хабре, стилистика и посыл текста одинаковые https://habr.com/ru/post/463957/
O(1), ибо в рантайме код лишь выводит на печать уже вычисленное значение.
Вот реально интересно, а для компилятора какая сложность, чтобы вычислить значение?
равна сложности постоения синтаксического дерева?
Дерево построить - дурное дело нехитрое. А вот насытить синтаксис семантикой - тут уже могут быть варианты.
Программа в десяток строк может потребовать экспоненту по памяти и времени для вывода типа.
Или, например, закодируйте функцию Аккермана на арифметике Пеано, и она будет разворачиваться за время, равное своему значению.
Ввод и вывод тоже занимают время и растут линейно с тем что у вас в коде названо N.
Статью можно сделать гораздо компактней . Что-то в духе - Пасаны !!! Смари как могу!! В ответ прозвучало - Ну ты и кодер.. Ну а так опять кто-то решил усложнить себе жизнь , когда поставлена задача с 6 класса времён Паскаль АБЦ.
Интересно, а сколько реально времени это заняло и смог бы ТС повторить это на реальном собеседовании?
Как говорится, если вы не делаете такое на собеседовании - у вас нет сердца. А если делаете - то нет ума :)
Из "юмористических" решений мне больше всего нравиться https://www.youtube.com/watch?v=mZWsyUKwTbg , где предлагается решать задачу на haskell для крутости, но на самом деле код генерирует vim с помощью макросов.
Ещё бы начали с написания компилятора. И с просеивания кварцевого песка для выращивания микросхем.
Вот похожей дурью (в хорошем смысле) маются https://github.com/doctorn/trait-eval/
поэтому я бы хотел избежать ненужных вычислений в рантайме.
А что, компилятор сам не умеет развернуть цикл, заинлайнить и соптимизировать в вывод большой строки?
type One = S<Z>;
type Two = SumOf<One, One>;
type Three = SumOf<One, Two>;
type Five = SumOf<Two, Three>;
type Ten = SumOf<Five, Five>;
type TwentyFive = SumOf<Five, SumOf<Ten, Ten>>;
type Fifty = SumOf<TwentyFive, TwentyFive>;
type OneHundred = SumOf<Fifty, Fifty>;
type N = OneHundred;Вот где-то тут я бы уже спросил, "а как поменяется ваша программа, если 100 не жестко задано а читается с стандартного ввода?"
Юмор понятен, если это флек от типов, то тоже понятно, но если отталкиваться от сюжета, где автор хотел просто сделать compile-time решение то:
Пишем первое что пришло на ум:
func fb(n: int): string =
for x in 1..n:
if x mod 3 == 0:
result.add "fizz"
if x mod 5 == 0:
result.add "buzz"
if result.len > 0 and result[^1] == '\n':
result.add $x
result.add '\n'
let res = fb(100)
echo res
хм, хорошо бы это посчитать при компиляции:
const res = fb(100)
echo resГотово:
Так и в расте можно так же:
#[derive(Debug, Clone, Copy)]
enum FizzBuzz {
Fizz,
Buzz,
FizzBuzz,
Value(usize)
}
const fn fizz_buzz<const N: usize>() -> [FizzBuzz; N] {
let mut ret = [FizzBuzz::Fizz; N];
let mut i = 1;
while i <= N {
ret[i-1] = match (i%3 == 0, i%5 == 0) {
(true, true) => FizzBuzz::FizzBuzz,
(true, false) => FizzBuzz::Fizz,
(false, true) => FizzBuzz::Buzz,
(false, false) => FizzBuzz::Value(i)
};
i += 1;
}
return ret;
}
fn main() {
for x in fizz_buzz::<100>() {
println!("{:?}", x);
}
}Но ведь это будет не на типах, да?:)
Не видно где оно вшило в бинарник компайл тайм значение
"Ирония - дочь бессилия" (с)
Подход понятен, но возникает вопрос о накладных расходах. В чистом Си в embedded, например, используют предвычисленные таблицы вместо операций целочисленного деления на некратное 2^N, достигая лучшего быстродействия за счет увеличения размера скомпилированного модуля.
Интересно, из тех кому понравилась статья и кто посмеялся над нерадивостью собеседующего, сколько бы из вас действительно хотело бы быть коллегой автора статьи?
Как насчет колег, которые получают такое видимое удовольствие самоутверждаясь за счет других людей? Людей, которые не такие умные, по их мнению, как они сами? Вы не боитесь что в повседневной жизни вы сами не раз окажетесь на месте собеседующего из статьи? Только выйти из комнаты и сказать "мы вам перезвоним" уже так просто не выйдет.
Если внезапно оказывается что человек делает мою жизнь хуже и компания не реагирует то значит с такой компанией мне не по пути.
Впрочем возможен вариант что я и есть такой человек поэтому ничего такого не замечаю. Надеюсь если это так то мне кто-то об этом сообщит.
Не вижу тут никакого самоутверждения. Просто хорошая статья, причем написанная в духе другой, тоже популярной.
Вы не боитесь что в повседневной жизни вы сами не раз окажетесь на месте собеседующего из статьи?
Я бы с удовольствием провел такое интервью. например, предложил бы после всей реализации всей этой акробатики сделать ввод N с клавиатуры и посмотрел бы как соискатель начинает рвать волосы на голове) В подобную игру ведь можно играть вдвоем. И что самое характерное, по результатам такого собеседования обычно удовольствие получают обе стороны. Как и неплохое представление о способностях друг друга. Что куда лучше кмк, чем сидеть спрашивать по шпаргалке и ставить галочки знает/не знает.
>Людей, которые не такие умные, по их мнению, как они сами?
Ну, во-первых, в реальной жизни на самом деле одни не такие умные как другие. Это просто факт. А уж самоутверждаться иногда пытаются чуть ли не самые тупые.
Как где? Да вся статья, каждый следующий шаг - открытое наслаждение предполагаемой "глупостью" интервьювера. Автор прекрасно знал с самого начала что именно, от него требуется, так же как и то, что его решение поймут далеко не все (единицы?). Суть всей статьи вкратце - "я на 10 голов умнее того кто меня должен был проверять (по мной придуманной метрике), хаха, как смешно правда". Это и есть самоутверждение.
>Это и есть самоутверждение.
Не, так я этого и не отрицаю. Автор вполне себе демонстрирует «я умный». Но не за счет других. Хотя бы потому, что выбирать иньервьюера мы не можем.
>я слишком серьезно все воспринял
100%. Эта статья, как и предыдущая, в значительной степени шутка с отсылом к паре других, для тех кто помнит. Хотя возможно если вы ту не читали, то и не сразу обратили внимание.
Мне кажется, переживать тут не стоит.
У людей не бывает универсального интеллекта. Если человек запарился и виртуозно овладел typelevel программированием, значит, он не запарился и не овладел чем-то другим (и времени не потратил на это, и физического ресурса мозга меньше оставил под другие задачи). Я нередко встречаю подобных персонажей. На typelevel они творят чудеса, как им кажется, но на деле же в интерпретаторе с необычной семантикой (абстрактный интерпретатор системы типов языка) сложным образом реализуют простецкие алгоритмы (необычность поражает публику, конечно). А когда нужно разработать более сложный алгоритм теряются. Встречал даже таких, кто сортировку не может запрограммировать, хотя только что рассуждал о
-категориях.
Это не упрёк, просто все мы - узкие специалисты.
Поэтому, если такой человек заведётся в команде, то он либо окажется адекватным и поймёт, что зависит от других людей, которые лучше решают другие задачи, и начнёт работать на общее дело, либо окажется неадекватным, тогда просто вылетит, потому что конечному пользователю его typelevel не нужен, конечному пользователю (если, конечно, это не человек, занимающийся логикой) нужна эффективность в runtime, а не вот это вот всё.
Перед вами лежит доска, молоток и гвоздь.
Вас просят забить молотком гвоздь в эту доску.
Вы как и игре Rust идете делать делать плавильную печь, на которой можно будет из руды выплавить молоток и гвоздь . . .
Открыли бы Excel и может быть и перезвонили:
Option Explicit
Sub FizzBuzz_Test()
Debug.Print FizzBuzz(1, 100)
End Sub
Function FizzBuzz(low_ As Long, high As Long) As String
Dim sTxt As String
Dim indx As Long
For indx = low_ To high
sTxt = sTxt & _
Buzz( _
Fizz( _
Fizz_Buzz(indx))) & _
vbCrLf
Next
FizzBuzz = sTxt
End Function
Function Fizz(vvar As Variant) As Variant
Fizz = IIf(Mod_Var(vvar, 3), "Fizz", vvar)
End Function
Function Buzz(vvar As Variant) As Variant
Buzz = IIf(Mod_Var(vvar, 5), "Buzz", vvar)
End Function
Function Fizz_Buzz(indx As Long) As Variant
Fizz_Buzz = IIf(indx Mod 15, indx, "FizzBuzz")
End Function
Function Mod_Var(vvar As Variant, numb As Long) As Boolean
If IsNumeric(vvar) Then _
Mod_Var = (vvar Mod numb) = 0
End Function
Я бы такого соискателя тоже не взял бы. Просишь элементарную задачу решить максимально оптимально, а получаешь НИОКР на три часа, который потом нельзя ни поддерживать, ни новые фичи прикрутить. И так во всех задачах.
Если не секрет: а сколько з/п на той должности предлагали?
Shreedeer, Soarerru и др… Вы это серьёзно? Нет, правда…
Это же стёбная статья с полностью вымышленной ситуацией юмористического характера. Так называемое "ненормальное программирование" (этот хаб, кстати, указан).
Я делаю свои собственные числа согласно аксиоматике Пеано
Уже на этой фразе должны были улетучиться последние сомнения :)
Очень круто, но довольно бесполезно.
Это вы думаете, что бесполезно, а потом оказывается, что полезно. Не на таком игрушечном примере, конечно. Но у нас подобным образом в одном компоненте достигается оптимальность в tight цикле, где засчет этой акробатики выпиливаются многие вещи, которые не нужно в итоге считать в рантайме, что дает разницу в производительности в разы относительно скорости всей операции (а сам цикл ускоряется на порядки). В коде где люди с vtune лазят и префетчи руками выставляют чтобы в кэш попало что нужно заранее — и не такое бывает. И да, этим мы занимались не в каком-то компиляторе, а в обычном бизнесовом коде, чтобы быть конкурентноспособными с десятком конкурирующих компаний, включая яндекс. ИСЧХ получилось.
А почему не использовали макросы? Макросы проще, гибче и прямолинейнее в подобных оптимизациях.
Во-первых макросы не проще.
Во-вторых макросы хуже композируются: в случае с типами вы получите нормальную ошибку если где-то ошибетесь, а в километрах макросов он скажет что после подстановки что-то где-то не сошлось, и идти искать cargo expand что там накрутилось. Нет, это ан порядок сложнее. Да и не все в макросе емнип сделать можно из того, что нужно. Например, макросы не умеют останавливать рекурсию. Попробуйте написать факториал как рекурсивный макрос — не выйдет. На типах — пожалуйста.
Эвоно оно как... Вроде, хвастались, что макросы в Rust прям как в Lisp, и даже лучше... А они рекурсивный факториал не могут. Странно. Разве нельзя вызвать произвольный код пользователя?
Не знаю, кто такое сказал. Макросы раста ограничены как минимум тем, что работают с синтаксисом, а не с семантикой. Если макрос видит тип SomethingType он никак не сможет узнать, например, какие поля есть у этого типа — это нужна семантическая модель, тогда как макросы раскрываются чисто синтаксически.
Вам не перезвонили по очевидной причине: вы не решили поставленную перед собой задачу.
Вы же хотели минимизировать runtime, но на деле только увеличили его. Первый вариант с выводом ошибки через запуск rustc требует запуска компилятора, что гораздо накладнее, чем запуск простого fizzbuzz. Второй вариант требует сохранения в бинарнике большого списка строк (размер программы вылезет за размер сектора), его загрузки, релокации, большего замусоривания кэшей при исполнении, что снова приведёт к большему runtime.
Кроме этого, в такой простой задаче вы использовали unsafe, что же будет в более сложных ситуациях? Ай-я-яй!
(:
А что такое "простой запуск fizzbuzz"? Про первый говорится что запускается целый компилятор, откуда можно сделать вывод, что во втором случае компилятор запускать не нужно? Просто я всегда думал, что раст компилируемый язык.
Это первое. А во-вторых время компиляции всегда называлось compile time и отличалось от run time. Включать одно в другое как-то странно.
Кроме того, никто не говорил вроде про большой рантайм, речь шла про быстрый/медленный. А размер дата секции из-за пары строк — да ну пофиг.
</zanudaOff>
Программа должна при каждом запуске выдавать fizzbuzz-последовательность. В первом случае каждый запуск потребует запуск компилятора. Вроде как, это очевидно. Нет? Во время исполнения такого решения, то есть, в его runtime, потребуется большой объём ресурсов, чем для однократно скомпилированной программы с обычной тривиальной реализацией, которую я и назвал "простым fizzbuzz".
С чего бы каждый запуск потребует запуска компилятора? Запустили компилятор один раз, получили бинарь. Запускаем этот бинарь сколько душе угодно — где тут компилятор?
Я-то грешным делом подумал что включение compile time в рантайм это такой сарказм, но если это сказано на полном серьезе...
Так в первом решении поста нет формирования исполняемого файла, результат выдаётся в виде ошибки компиляции.
С чего бы это? Вы может не обратили внимание, но там написано:
Compiling playground v0.0.1 (/playground)
Finished dev [unoptimized + debuginfo] target(s) in 3.55s
Running `target/debug/playground`Что это за running target/debug/playground такой по-вашему?
Речь про эту цитату
Затем я нажал
Ctrl+Enterи через пару секунд с довольным видом показал интервьюеру ошибку компиляции: ...
как глухой с немым =)
Нету никакого первого решения. Есть просто решение тут
Набрав этот код, я с некоторым колебанием нажал Ctrl+Enter, и через несколько секунд отобразился результат запуска программы:как глухой с немым =)Попахивает маразмом честно
Я сказал что человек имеет ввиду (на мой взгляд), с надеждой помочь людям понять друг друга. С какой целью писался ваш комментарий для меня пока загадка.
Ну, в тексте подано всё так, что в процессе сочинения типов герой забыл о задании и попытался выдать за решение ошибку компиляции с типом, напоминающим искомый fizzbuzz.
Но, ok. Пусть в тексте есть только одно решение, но оно тоже не эффективно в runtime. Вместо того, чтобы плюсовать пару байтовых счётчиков в паре регистров и периодически выпихивать в порт вывода пару байтов или строк, оно грузит здоровый массив, по которому к тому же проходит, читает значения из памяти (sic!), ветвится по результатам чтения, и копирует их в порт вывода. Жуткая жуть, растрата и оверхед по меркам конкретно этой задачи, если мы меряемся именно эффективностью во время исполнения.
Второй вариант требует сохранения в бинарнике большого списка строк (размер программы вылезет за размер сектора)
Не понимаю, чем это плохо.
его загрузки, релокации
Как и абсолютно любой другой бинарник.
большего замусоривания кэшей при исполнении
У меня большие сомнения в том, что это использование кеша (который, кстати, тут поможет, данные-то почти наверняка лежат в памяти последовательно) будет хоть сколько-то заметно на фоне использования кешей функциями ввода-вывода.
Кроме этого, в такой простой задаче вы использовали unsafe
Само по себе это не плохо. unsafe код не безопасен не сам по себе, а из-за того, что при его вызове нужно соблюсти инварианты, которые компилятор проверить не может. У обеих использованных небезопасных функций предусловия локальные.
std::str::from_utf8_unchecked требует, чтобы все байты в слайсе были в кодировке ASCII. Это требование соблюдено, поскольку мы начинаем с массива из нулевых байтов и на каждой итерации цикла записываем код, отвечающий ASCII-цифре.
<[u8]::get_unchecked> требует, чтобы указанный диапазон лежал в пределах размера слайса. Так как мы используем диапазон с открытой нижней границей и конкретной верхней, это фактически означает, что требование сводится к тому, чтобы len не превосходил длинны массива. Это требование так же соблюдено: возвращаемое значение — это финальное значение счётчика, который используется для индексации массива. На каждой итерации это значение сначала используется для индексации, а потом инкрементируется. Таким образом, после цикла счётчик имеет значение, которое, уменьшенное на единицу, можно использовать для индексации массива, что фактически и означает, что финальное значение счётчика не превосходит длины массива. Индексация массивов в Rust проверяет диапазон, так что если я вдруг что-то напутал с реализацией, то to_str, вызванная в константном контексте, завершится ошибкой компиляции.
Можно ли было бы написать Str::as_str без unsafe? Безусловно:
impl Str {
fn as_str(&self) -> &str {
match &self.0 {
&StrInner::Plain(s) => s,
&StrInner::Decomposed(ref bytes, len) => str::str::from_utf8(
bytes.get(..len).unwrap_or(&[])
).unwrap_or(""),
}
}
}Но в этом коде проходит проверка на включение len в диапазон и UTF-8-валидация. Первое не так существенно, а вот вторая проверка требует исполнения значительного количества нетривиального кода. Я сильно сомневаюсь в том, что компилятор в состоянии убрать этот код валидации даже для аргументов, известных на этапе компиляции. Использование unsafe-варианта позволит надёжно этот код исключить.
У нас в компании уже мем есть, когда коллега написал довольно большой проект на boost::spirit, и мы потом на спор показывали фрагменты другим командам и спрашивали, на каком языке написано. Человек долго мялся, а потом говорил "ну не С++ же..".
По итогу все переписали потом на нормальном С++, потому что поддерживать было нереально.
Что-то на эльфийском, не могу прочесть.
На Rust:
fn main() {
let mut x = 0;
loop {
x += 1;
if x % 5 == 0 && x % 3 == 0 {
println!("fizzbuzz");
} else if x % 3 == 0 {
println!("fizz");
} else if x % 5 == 0 {
println!("buzz");
} else if x % 5 != 0 && x % 3 != 0 {
println!("{}", x);
} if x > 100 {
break x;
}
};
}
Забавно. Я в свободное время доказал тьюинг-полноту типовой системы Rust'а реализовав выполнитель SmallF*ck -- облегчённого brainf*ck'а. Разглядел очень много похожих моментов в реализации на типах.
Про мою реализацию написал здесь, правда очень много общего
— Теперь параметризируем задачу, — сказал интервьювер. — Алгоритм программы пусть остается без изменений, ведь вы потратили на него рабочее время. Пользователь в командной строке вводит в качестве параметров вашей программы два числа. При делении первого числа без остатка, на экран должно выводиться fizz, при делении второго без остатка - buzz, при делении без остатка обеих - fizzbuzz. Все то же самое.
Предыдущий соискатель сделал это изменение за 5 минут и его программа работала не более 150ms с нашими тестовыми данными. Вам необходимо уложиться в это же время, и улучшить его результат.
Как написать FizzBuzz на собеседовании