All streams
Search
Write a publication
Pull to refresh
337
0
Сергей Самойленко @samsergey

Руководитель, научный сотрудник, преподаватель

Send message

Это, кстати, не так сложно.
Перепишем ОДУ второго порядка
f′′ = –f
в систему:
f′ = –g, g′ = f
и  рассмотрим свойство выражения:
f² + g². Мы знаем только как меняется скорость наших функций f и g, так что давайте посмотрим на скорость изменения этой суммы:
(f² + g²)′ = 2ff′ – 2gg′ = –2fg + 2gf = 0.
Нулевая скорость изменения этих выражений говорит о том, что эта сумма является константой. Выбрав такие начальные условия, чтобы f(0) = 1, а g(0)=0 получаем, что эта константа равна единице.
Кроме того, можно показать, что что если какое-либо из решений системы имеет хотя бы один максимум, то обе эти функции должны иметь бесконечное множество минимумов и максимумов, причём экстремальное значение одной функции обязательно соответствует нулю другой.

Неплохая статья, правда! Но, как любитель математики не могу не прокомментировать этот пассаж:


Однако я отношусь к той касте отбитых любителей математики, которые считают, что если такие чрезвычайно просто сформулированные задачи испытывают проблемы с решением, то у самой сути разработанной математики есть какие-то проблемы и их неплохо было бы решить (попутно разработав новый аппарат).

Проблемы с решением этой задачи кроются не столько в математике, сколько в формулировке самой задачи. Что такое "конечная форма" и "аналитическое решение"? В какой именно конечной форме ищется решение, в каком поле? И тут открывается классный путь в теорию полей и трансцедентных чисел, на мой взгляд, не менее увлекательный, чем экскурс по миру метрик!


Что же до "зависимости тригонометрических функций от метрики", соглашусь с комментарием выше: тригонометрические функции, синусы и косинусы, фундаментальнее геометрии, из которой они вышли. Они являются решением важных дифференциальных уравнений (линейных второго порядка), образуют ортонормированный басис в гильбертовом пространстве (поэтому работает преобразование Фурье), кроме того, внутренняя структура этих функций глубоко связана с группой, образуемой операцией умножения в поле комплексных чисел. А то, что через них напрямую выражаются отношения в прямоугольном треугольнике, является свойством Евклидовой геометрии, а это лишь одна из многообразия возможных геометрий.
Я пишу это не чтобы позанудствовать, а чтобы показать, сколько ещё интереснейших направлений исходит от этой задачи в различные области математики!

Обожаю эту могучую "реальность", в которой всё всегда не так, как на самом деле :) Если бы реальность сопротивлялась моделированию с помощью математики, мы бы строили иную математику. Пока всё, имеющее смысл, сходится. Споры с привлечением "реальности", чаще всего, возникают вокруг утверждений смысла не имеющих.

Таких конструктивных вопросов было два. Из 42 комментов про "пользу" и "несовершенство" :)

Комментарии напомнили знаменитый анекдот про японскую лесопилку и суровых сибирских мужиков.
Интереснейшая задача, человек вплотную подошел к её реальному решению, рассказал как он это сделал и полностью открыт для общения со спецами, но! Самым интересным для уважаемых спецов оказалось тыкать в робота палкой, до тех пор, пока он не сломается, а потом гордо сказать: "ага!!" :)
Поздравляю автора с отличной задачей и классной реализацией! Уверен, что вы с сыном получили то, что искали: и пользу и удовольствие. А сын ещё и получил возможность восхититься тем, на что способны математика и папа!
В то время, как тыкатели палками могут гордиться тем, что они могут сломать что угодно, доказывая тем самым превосходство человека "над системой" :)

К сожалению, автор попадает в ловушку "убийства дракона": пытаясь победить формализм исходя из соображений "реальности" и "практической полезности", он теперь вынужден создать новый формализм, причем по всем правилам. Без четкой аксиоматики, без доказательства того, что новая система является полем, использовать её наряду с числами нельзя. Кроме того, похоже, что в этой системе есть нетривиальные делители нуля, а значит, она полем не является, значит неизбежны проблемы с единственностью разложения на множители и сокращениями при делении. Самое же главное, дракон, с которым сражается автор, столь же нереален и далёк от практики, как и указанная в самом начале "проблема формальной математики". Даже сугубо реалистичной инженерной физике никогда не мешали ограничения, накладываемые на операции с числами теорией полей, а, напротив, помогали познавать и моделировать сущности. Анализ размерности — прекрасный инструмент инженера, теория групп — инструмент теорфизика, теория конечных полей, типов и категорий — инструмент программиста. Возможно, предлагаемый здесь формализм может стать одним из таких инструментов, но пока я вижу в нём больше противоречий (указанных уже комментаторами выше), чем может позволить себе теория.
К слову, если статья на математическую тему начинается с упоминания теоремы Гёделя о полноте, это сильный признак её нематематичности. А если она, к тому же, переключается на вопросы "практичности" математики, то материал, скорее всего, не интересен и не полезен.
Лучше оставить в покое Гёделя, и построить стройную непротиворечивую аксиоматику, с выводом основных положений, типа теоремы Безу, основной теоремы арифметики и т.п. А если уж так хочется "полезности", показать пример приложения новой системы за пределами возможностей уже известных.

Конечность, строго говоря, не обязательна: \ dev\null тому пример. И вы правильно определили основные структуры, присущие файлу, как математическому объекту.

Это называется проблема поиска денотационной семантики. Работа в этом направлении идёт и далека от завершения. Для многих это жуть жуткая и муть мутная, каждый день не нужная. Но для тех кто пишет компиляторы и верификаторы это крутой инструмент.
А файл (POSIX) можно отождествить с анаморфизмом, порождающим свободный моноид, его обработчики — с гиломорфизмами. Файловая система — дерево, или более общий граф, если она реляционная и т.п. Мы используем эти понятия, не зная, что "говорим прозой".


И хотел бы добавить, современная математика огромна. Не торопитесь судить о ней в терминах "никакая математика не определит"… Например, о трех табуретках: теория устойчивости, даже линейная удовлетворительно отличит одно применение от другого.

Ну, скучно же, ребята!!! Один пишет про ошибки, допущенные другим в статье про ошибки третьих… спор о том, кто больше неправ продолжился в комментариях. Ну неправ, и что? Лучше бы написали о каком-нибудь крутом и красивом решении, которое показывает как XXX парадигма расширяет наш инструментарий, да с примерами, да так чтобы захотелось попробовать! А то "тут ООП, тут не ООП..." Как говорил Жванецкий: "Воруйте с прибылей!"

Ну да, но их же нужно откуда-то брать. И при этом не забивать память гигами нулей и единиц, используя решето, и не тратить на это даже секунды. Я далёк от теории чисел, но понимаю, что есть более эффективные способы, хотя бы, вероятностные — генерим случайное большое число и тестируем каким-нибудь Миллером-Рабином.

Я имел в виду не задачу криптографии в целом, а генерацию простых чисел (если таковая, действительно ставится при факторизации больших чисел, опять же, могу напутать по незнанию). Эта генерация, по существу, чиста и может быть встроена в чистый код, но имплементирована может быть как угодно, лишь бы эффективно. Впрочем, тут мне лучше умолкнуть.

Это да. Мне хотелось продемонстрировать не столько чистое ФП, сколько его выразительность и гибкость. Если требуют решето именно Эратосфена и именно двойным циклом и именно с вычёркиваем, то… и это можно.
А так, есть классные функциональные решения тут и тут. Но они уже не совсем то решето, о котором обычно рассуждают.
Для своих нехитрых нужд я бы взял ваш однострочник и не заморачивался. Для криптографии какой-нибудь — быстрый императивный код через FFI, но я в ней мало смыслю, если честно.

Кормящим матерям и путникам не возбраняется :)

Спасибо, это, действительно, многовато для комментария. Пройдёмся по вашим вопросам.


  • Вывод типов в ФП распространяется не только на объявление параметров/констант, но и на типы всех выражений и функций. И работает он в "обе стороны", то есть, я могу явно написать тип определяемой функции, а потом спросить у компилятора каким должен быть тип того или иного (любого) подвыражения в её теле, используя т.н. дырки, (holes). Это лучше показать, но не в комментарии. С другой стороны, я могу написать тело функции, не указывая вообще ни одного типа, и компилятор постарается вывести самый общий полиморфный тип для неё (в статике, на этапе компиляции). Если не выйдет, он скажет что именно ему не понятно, и это будет либо моя ошибка, либо неоднозначность задачи, требующая явного сужения типа, что тоже полезно и открывает глаза на программу. Особенно приятно общаться с компиляторами PureScript или Elm, но и ghc в последние годы становится более дружелюбным (или это я учусь понимать его?). А вот работа с литералами-константами (из примера с var), как раз часто требует уточнения, поскольку в Haskell выражение 5 может означать либо целое число, либо число с плавающей точкой, либо, вообще, какой-нибудь тип-обертку типа Sum или Max. Компилятор очень постарается понять из контекста, что же это такое, но программист может его здорово запутать :)
  • Я не преувеличил роль вывода типов в ФП в серьёзных исследованиях. Многие наши замечательные современники — асы ФП, создавшие целые концепции, вроде линз, кондуитов, или свободных монад, активно используют интерпретатор GHCi, как основной инструмент, получая от него ответы на вопросы (скажем, какой функтор нужно подставить в линзу, чтобы превратить его в геттер или сеттер) и целые доказательства (см. изоморфизм Карри-Ховарда) для своих идей, о чём с удовольствием рассказывают на конференциях и в блогах.
  • Я нарочно взял словосочетание «типо-ориентированное программирование» в кавычки, это не официальный термин. Типы в ФП (типизированном) это нечто большее чем "множество допустимых значений, внутреннее представление данных и возможные операции над ними". Это основа дизайна программ, предоставляющая связи между типами и законы (в математическом смысле, а не в инженерном) им присущие. Типы параметризуют друг друга и сами образуют более общую структуру Kinds, всё это выводит работу с ними на уровень настоящего исчисления. Иногда это чертовски сложно и нетривиально, иногда чертовски красиво, но вот что для меня привлекательно: тут остаётся мало места традициям, моде и вкусовщине, присущим нашему делу. Вместо них теоремы, анализ и строгие выводы, которые можно использовать, спустя десятилетия и они не устаревают, а со временем получают развитие, как, например получилось с линейными типами.
  • На последний вопрос отвечу аккуратно: отсутствие изменяемого состояния (концептуальное) заставляет писать код, в котором проблем с параллелизмом и конкурированием существенно меньше. Я не стану утверждать рекламным голосом, что в рамках ФП параллелизм станет лёгким и приятным как никогда, и теперь с этим справится даже ваша мама. Сложности всё равно остаются, но они, скажем так, иного уровня, поприятнее, что-ли.

Немного прокомментирую это решение. Я использовал Data.Vector.Unboxed.Mutable только для эффективности. От этой структуры здесь лишь конструктор M.replicate и функции доступа M.read b M.write. На месте этой структуры могли быть немутабельные векторы, Array (или даже список со всеми вытекающими проблемами эффективности). Программа и её результат бы от этого не изменились, только сигнатура. И то, её я не писал вручную, мне рассказал о ней компилятор :)


Именно этот выбор определил то, что результат будет "жить" в IO. Но ровно эту же программу можно погрузить в чистую ST, в любом случае, она принципиально императивна, что не помешало мне реализовать её в Haskell.


Циклы реализованы через рекурсию, вполне прямолинейно, в виде хвостового вызова. Из магии только монадические штучки >> и >>=, которые можно рассматривать как пайпы.
И, наконец, я нарочно написал тело цикла sieve так, чтобы он "выглядел" как изменение переменной m, чтобы показать, что если уж мы мыслим наш алгоритм императивно, то его можно и выразить императивным кодом, не изменяя принципам ФП. Мы не монахи и императивность не грех, если всё делать аккуратно, с благословения компилятора.


В бенчмарке использовался вариант с преобразованием в список, чтобы честно. Оно добавило константу, но оставило асимптотику.

Вот решение, вполне прямолинейное и наивное.


import Control.Monad.Primitive
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as M

eratosphenesArray :: Int -> IO (M.MVector (PrimState IO) Bool)
eratosphenesArray size = M.replicate size True >>= sieve 2
  where
    sieve k m
      | k*k >= size = return m
      | otherwise   = do
          next <- M.read m k
          m <- if next then fill (2*k) k m else pure m
          sieve (k+1) m

    fill n k m
      | n+k > size = return m
      | otherwise  = M.write m n False >> fill (n+k) k m

заполняет массив значениями True и False согласно оригинальному замыслу, в двух вложенных циклах (sieve и fill). Сигнатура страшная, но алгоритм прост как пробка.
Если надо список простых чисел (индексы со значениями True), то можно написать такое:


eratosphenes :: Int -> IO [Int]
eratosphenes size = do
  a <- eratosphenesArray size
  elemIndices True . V.toList <$> V.freeze a

Результаты прогона на ноуте (сплошная линия — n*log(log(n))):
image

Да, main не функция. Сказывается привычка :) Это точка входа — выражение, которое вычисляется при запуске программы.

Ага! спасибо, посмотрю, operational переводится лучше, но они не тождественны, а связаны через Coyoneda. Интересно, сам Олег Киселёв как их называет?

Придется, но это, правда, не "очень сложно"!

Мне импонирует ваше стремление разобраться! Переменное состояние и сайд-эффекты в ФП исключены вовсе не ради инкапсуляции, вернее не только ради неё. Если мы готовы принять это ограничение, то становятся возможными:


  • Однозначный вывод типов по Хиндли-Милнеру, существенно более полезный, чем var или auto, поскольку он проникает на все уровни программы от сигнатуры функции до самых мелких её деталей. И это не для экономии нажатий клавиш при определении функции, а для настоящей и осознанной типобезопасности. Компилятор в чистых типизированных ФЯП не тестировщик и не надзиратель, а друг и помощник, подсказывающий и объясняющий программисту даже не в чём состоит ошибка, а что ему писать дальше. Это не автодополнение IDE доступных полей и методов, а подсказка сложных и очень нетривиальных решений, которые потом могут превратиться в научные разработки. Это круто и от этого уже трудно отказаться!
  • "Типо-ориентированное программирование", несколько более широкое, чем data-driven design, поскольку на первый план выступают алгебраические свойства типов (и функций над ними), не нарушаемые изменением состояния.
  • Внятная и доказуемая денотационная семантика, equational reasoning, настоящее unit-тестирование с автогенерацией тестов и property-based тестированием (Quickcheck появился в Haskell и только потом разошёлся по языкам).
  • Выбор стратегии вычислений (строгая/ленивая), в чистом ФП не меняющая результат, а влияющая лишь на эффективность программы и на способы её декомпозиции (в ленивом Haskell декомпозиция вкусна до безобразия, одни только гиломормизмы и fusion чего стоят!).
  • Принципиальное отсутствие в многопоточности гонок, и проблем с общими ресурсами.
  • Наконец, осознанная свобода в выборе и конструировании семантики позволяет легко (правда, легко, монады не сложнее какого-нибуть преобразования Фурье или Лапласа, хоть и "ломают" по началу мозг) эмулировать и переменное состояние и эффекты, но со всеми перечисленными выше плюшками!
    Отсутствие сайд-эффектов и переменных не цель ФП, а средство достижения гораздо больших целей. И, более того, если надо, я всегда могу их себе завести, но они гарантированно будут локальными и с тонко настраиваемой семантикой.

Information

Rating
Does not participate
Location
Петропавловск-Камчатский, Камчатский край, Россия
Date of birth
Registered
Activity