Автор заявляет о революции — о наличии линейного решения для NP-полной задачи. Такое заявление требует убедительных доказательств, т.к. если бы это было правдой, то была бы опровергнута гипотеза P ≠ NP. Обычно же это свидетельствует о том, что в ходе рассуждений где-то закралась ошибка.
Немного критики
desktop-13
Скорость выполнения алгоритма на конкретном компьютере не имеет отношения к линейному/нелинейному времени. На мой взгляд, это только добавляет "воды" в статью.
Очевидно, что данный алгоритм по времени счета является линейным относительно n.
Краеугольным камнем P≠NP является оценка сложности. Хотелось бы, конечно же, видеть алгоритм на каком-нибудь псевдо-коде, и видеть оценку в стандартной О-нотации.
n-Queens Completion problem является классической не детерминированной задачей.
это утверждение противоречит формулировке задачи, данной в разделе "1. Введение". Там задача сформулирована детерминировано, как и положено задачам класса NP.
Таким образом, автор подменяет одну задачу другой.
False Negative решения
В детерминированном алгоритме решения NP-полных задач таких решений быть не может. Таким образом, предложенное автором решение не является решением задачи n-Queens Completion problem
Бизнес-логику вполне можно писать на Scala с помощью подходящего DSL. В том числе, и не столь прямолинейную.
"Премудрости" дают инструменты для хороших библиотек и DSL. На прикладном уровне хорошие библиотеки использовать достаточно легко, и можно в большинстве случаев обходиться поверхностными знаниями, не вникая в детали.
Для некоторых задач отсутствие адекватных по сложности инструментов приводит к тому, что программы получаются не очень хорошими (многословными, с повторами похожего кода, с необходимостью заново тестировать похожую функциональность).
Есть хорошие книги и курсы, с помощью которых можно освоить абстракции, используемые в функциональном программировании. Например, FP in Scala (либо аналогичная книжка на Haskell'e — haskellbook.com). На coursera есть специализация "Functional Programming in Scala".
Ну а собственно lift из обычной функции делает функцию, работающую с какой-то структурой. Например,
val inc: Int => Int = _ + 1
val linc: List[Int] => List[Int] = Functor[List].lift(inc)
val List(11,12,13) = linc(List(10,11,12))
а универсальность позволяет писать код, который не зависит от конкретной структуры:
def algorithm[F[_]: Functor, A: Numeric](fa: F[A]): F[A] = {
val N = Numeric[A]
val F = Functor[F]
val inc = N.plus(_, N.one)
val finc = F.lift(inc)
finc(fa)
}
такой алгоритм будет работать с любыми структурами данных (для которых есть Functor) и любыми числовыми типами (для которых есть Numeric).
COBOL не работает на таком уровне абстракций. lift — мощный универсальный инструмент, который затруднительно даже представить в слабо-абстрактных языках.
По поводу разрешения IP — есть в статье. Удобный вариант — прописать новый IP в /etc/hosts для предопределённого имени.
По поводу паролей — (1) разбить конфигурацию на 2 части — общая и секретная; (2) предусмотреть макрос или скрипт сборки, который будет забирать пароли из хранилища и запекать в конфигурацию; (3) по-старинке, предусмотреть runtime-загрузку паролей при старте приложения.
jar-конфигурации будет зависеть от корректных версий составных частей приложения. То есть, всё приложение можно "вытянуть" за один jar-файл. Совместимость проверяется на этапе сборки — после успешной компиляции можно запустить интеграционные тесты.
Отдельный jar для конфигурации будет, вероятно, не очень-то повторно используем. Сам микросервис, без конкретной конфигурации, — вполне себе повторно-используемый компонент. А конфигурация обычно — небольшой файлик. Просто компилируется отдельно.
Как мне кажется, статья не отражает "Haskell подход". В Haskell — простая структура данных (cons-list) + рекурсия позволяют эффективно решать перечисленные задачи. Предлагаемые в статье алгоритмы выглядят неэффективно.
Например, size использует метод tail типа List, что, в случае array-list'а будет копировать почти весь лист (O(N) по времени и по памяти), а затем не использует хвостовую рекурсию (O(N) по памяти), чтобы прибавить 1. Тем самым общая вычислительная сложность оказывается O(N^2), что отличается от обычной сложности O(N) по времени и O(1) по памяти.
В примере с хвостовой рекурсией автор также использует when(xs.size) внутри функции. В случае, если List — односвязный список, опять окажется, что каждый вызов O(N). В итоге хвостовая рекурсия не спасает, получаем O(N^2). (Можно было бы использовать when(xs.isEmpty) с O(1).)
В нашем проекте мы схожую проблему решаем с помощью gradle. В перспективе можно будет отправить maven на заслуженный отдых (люди к maven привыкли/прикипели и не готовы сразу с ним расстаться).
Насколько я понимаю, в ScalaCheck ключевым является понятие "свойства". А генераторы используются постольку поскольку, как средство, позволяющее убедиться, что свойство выполняется в широком диапазоне значений.
ScalaCheck не подходит для замены Unit-тестов во всех случаях. Этот подход прекрасно работает тогда, когда удаётся найти те самые свойства, справедливые для многих случаев. Если программа представляет собой много отдельных несвязанных случаев — switch/case/if, то маловероятно, что такие обобщённые свойства будет легко обнаружить. А вот если тестируется универсальный алгоритм, то мы можем ожидать определённой стабильности его результатов.
Если термин "свойство-ориентированное тестирование" не нравится, то можно поискать альтернативы для слова "свойство". Например, "инвариант" — тестирование на основе инвариантов. Или "предикат" — тестирование на основе валидации предикатов. Или "ограничение" — проверка ограничений, тестирование ограничений.
Насколько я понимаю, в данном случае функтор, который конструируется из монады — единственный. Морфизм f: A=>B конвертируется в M[A] => M[B] путём использования двух операций, предоставляемых монадой. Вначале функцию f превращаем в вычисление, применяя нулевое вычисление η к результату функции: φ = λa.ηfa, а затем конструируем результирующую функцию в lifted-категории с использованием моноидного умножения μ: λma.μma φ.
В Scala это выглядит, как привычный способ выразить map через flatMap и pure:
Эндофункторов, над которыми строится моноид, действительно много, но ни один из них, насколько я могу судить, не имеет такой формы, как этот — (A=>B) => (M[A] => M[B]).
Я рассматриваю монаду с точки зрения программирования. В статье Monads for functional programming (Philip Wadler) монада определяется как тройка, состоящая из конструктора типа, отображения, превращающего обычное значение в этот тип ("нулевое" вычисление), и отображения, связывающего два вычисления в одно.
То, что монада также является функтором, следует из того, что монада (как и функтор) позволяет преобразовать простые функции над базовыми типами в lifted-функции над сконструированным типом, то есть позволяет выполнить отображение категории обычных функции в категорию lifted-функций.
Несмотря на это, монада — более универсальная конструкция, чем функтор. Монада не только отображает обычные функции в lifted, но и предоставляет дополнительные возможности работы с функциями типа A => M[B], которые включают конструируемый тип — "вычислениями". При этом, сам конструируемый тип M[B] оказывается включен в класс объектов категории (поэтому, по-видимому, категория эндофункторов; при этом конструктор типа M[?] не включен в объекты категории). И вместо двух изолированных категорий, связанных функтором, мы оперируем одной категорией, в структуре которой выделены функции особого вида — вычисления, — и объекты — M[B], инкапсулирующие (потенциальный) результат вычисления. Для этих функций/вычислений монада предоставляет базовый набор действий, соответствующий моноиду, — нулевое действие (без вычислений), и комбинирование двух вычислений.
Да, вы правы. Сокрытие и инкапсуляция хоть и идут рука об руку во многих языках, всё-таки концептуально отличаются. Неизменяемые типы данных сами по себе не исключают инкапсуляцию, а лишь подрывают рациональные основания для сокрытия данных.
Инкапсуляция, как мне кажется, подразумевает, что как только мы объявили методы доступа к данным, следующий логичный шаг — скрыть прямой доступ к этим данным, чтобы исключить нарушение абстракции. Без сокрытия от инкапсуляции остаётся лишь возможность сложить в один объект данные и функции, что, по-видимому, имеет ограниченную ценность. А вот инкапсуляция вместе с сокрытием — хороший инструмент абстрагирования.
Добрый день.
Конечно, можно. Лицензия — BSD-like.
Мы сейчас этот подход используем и развиваем. В целом — достаточно удобно. При наличии неполных данных в БД (nullable колонок) — очень удобно.
Нельзя сказать, что этот подход прямо-таки сильно лучше, чем томита-парсер. Я думаю, что для своих целей томита-парсер вполне подходит. Однако есть несколько отличий, которые могут сделать предлагаемый подход предпочтительнее в некоторых прикладных задачах:
Порождающая и разбирающая грамматики описываются общими средствами. В частности, для числительных обе грамматики записываются в единственном экземпляре. Это упрощает разработку и поддержку, т.к. надо писать вдвое меньше грамматических правил. Например, для модульного тестировани можно проводить преобразование вначале в одну сторону, а затем в другую и сравнивать результаты.
Встроенность в язык программирования: (1) использование родных структур данных языка, (2) проверка типов на этапе компиляции, (3) доступность средств языка для любых целей, например, (а) можно написать свой конвертер в любой точке, (б) можно алгоритмически порождать грамматические выражения, (в) можно использовать средства модуляризации, встроенные в язык — trait'ы, (г) можно использовать удобный DSL для представления словарей.
Из исходной грамматики можно получить грамматику для произвольного парсера, обладающего требуемыми свойствами. (По-видимому, можно сгенерировать грамматику и для томита-парсера.)
Концепция уровня абстракции, лежащая в основе грамматических выражений. Преобразование между уровнями абстракции производится алгоритмически, что позволяет при разборе получать полное значение всей фразы в виде программных объектов, готовых к дальнейшей обработке, а при синтезе начинать генерацию непосредственно от семантических объектов, используемых в программе.
Разделение правил формальной грамматики и правил выбора формы слова. Правила двух видов имеют несколько различную природу, поэтому и представлять в программе их удобно разными способами.
P.S. Вышеприведённый вариант — для общего случая, для Int, Double, BigNumber… и других T, для которых есть Numeric[T]. Если delta имеет известный тип, то можно и проще:
case class SlotDelta[S <: SlotId[Int]](slotId:S, delta: Int) {
def +:(oldValue:SlotValue[Int, S]) =
SlotValue(slotId, oldValue.value+ delta)
}
2. Экономия классов не входит в цели фреймворка. Суть заключается в разрезании целого класса на отдельные компоненты и возможность оперировать данными, используя эти компоненты (слоты) в качестве ключа.
3. Пример с delta. Пусть класс Person содержит 100 полей. И пусть среди этих полей есть свойство типа T: Numeric (например, Int, Double и т.п.). Тогда мы можем объявить специальный класс PropertyDelta, который несёт изменение этого свойства
case class SlotDelta[T:Numeric, S <: SlotId[T]](slotId:S, delta:T)
Это может быть экономнее, чем копировать оставшиеся 99 полей (при сохранении в БД, при передаче по сети и т.п.). Кроме того, здесь мы явно видим, что именно изменилось, можем проверить допустимость изменения этого свойства согласно каким-либо правилам.
Теперь мы можем этот объект использовать для того, чтобы увеличить значение свойства на указанную величину:
case class SlotDelta[T:Numeric, S <: SlotId[T]](slotId:S, delta: T) {
def addTo(oldValue:SlotValue[T, S]) =
SlotValue(slotId, implicitly[Numeric[T]].plus(oldValue.value, delta))
}
Или немного поинтереснее:
implicit class SlotValueEx[T:Numeric, S <: SlotId[T]] (slotValue:SlotValue[T, S]) {
def +(delta:T) =
SlotValue(slotValue.slotId, implicitly[Numeric[T]].plus(slotValue.value, delta))
}
Здесь мы сохраняем возможность рефакторинга. Все свойства представлены объектами, хранятся в именованных константах (val'ах). С точки зрения объявления «класса» получается не сильно больше, чем объявление обычного case class'а.
case class Person(
name: String,
address: Address
)
vs.
object Person{
val name = slot[String]("name")
val address = slot[Address]("address")
}
Автор заявляет о революции — о наличии линейного решения для NP-полной задачи. Такое заявление требует убедительных доказательств, т.к. если бы это было правдой, то была бы опровергнута гипотеза P ≠ NP. Обычно же это свидетельствует о том, что в ходе рассуждений где-то закралась ошибка.
Немного критики
Скорость выполнения алгоритма на конкретном компьютере не имеет отношения к линейному/нелинейному времени. На мой взгляд, это только добавляет "воды" в статью.
Краеугольным камнем P≠NP является оценка сложности. Хотелось бы, конечно же, видеть алгоритм на каком-нибудь псевдо-коде, и видеть оценку в стандартной О-нотации.
это утверждение противоречит формулировке задачи, данной в разделе "1. Введение". Там задача сформулирована детерминировано, как и положено задачам класса NP.
Таким образом, автор подменяет одну задачу другой.
В детерминированном алгоритме решения NP-полных задач таких решений быть не может. Таким образом, предложенное автором решение не является решением задачи n-Queens Completion problem
Разные цели/задачи — разные языки.
Бизнес-логику вполне можно писать на Scala с помощью подходящего DSL. В том числе, и не столь прямолинейную.
"Премудрости" дают инструменты для хороших библиотек и DSL. На прикладном уровне хорошие библиотеки использовать достаточно легко, и можно в большинстве случаев обходиться поверхностными знаниями, не вникая в детали.
Для некоторых задач отсутствие адекватных по сложности инструментов приводит к тому, что программы получаются не очень хорошими (многословными, с повторами похожего кода, с необходимостью заново тестировать похожую функциональность).
Есть хорошие книги и курсы, с помощью которых можно освоить абстракции, используемые в функциональном программировании. Например, FP in Scala (либо аналогичная книжка на Haskell'e — haskellbook.com). На coursera есть специализация "Functional Programming in Scala".
Ну а собственно
liftиз обычной функции делает функцию, работающую с какой-то структурой. Например,а универсальность позволяет писать код, который не зависит от конкретной структуры:
такой алгоритм будет работать с любыми структурами данных (для которых есть
Functor) и любыми числовыми типами (для которых естьNumeric).COBOL не работает на таком уровне абстракций.
lift— мощный универсальный инструмент, который затруднительно даже представить в слабо-абстрактных языках.То же самое на Haskell:
не то, чтобы стало сильно легче...
Видимая сложность функции
liftсвязана с её универсальностью. При использовании, вообще говоря, всё довольно удобно и не выглядит сложным:По поводу паролей — (1) разбить конфигурацию на 2 части — общая и секретная; (2) предусмотреть макрос или скрипт сборки, который будет забирать пароли из хранилища и запекать в конфигурацию; (3) по-старинке, предусмотреть runtime-загрузку паролей при старте приложения.
Поздравляю с победой! Похоже, пользователи лайкают то, что уже лайкали раньше. И собственно контент не очень важен.
Как мне кажется, статья не отражает "Haskell подход". В Haskell — простая структура данных (cons-list) + рекурсия позволяют эффективно решать перечисленные задачи. Предлагаемые в статье алгоритмы выглядят неэффективно.
Например,
sizeиспользует методtailтипаList, что, в случае array-list'а будет копировать почти весь лист (O(N)по времени и по памяти), а затем не использует хвостовую рекурсию (O(N)по памяти), чтобы прибавить 1. Тем самым общая вычислительная сложность оказываетсяO(N^2), что отличается от обычной сложностиO(N)по времени иO(1)по памяти.В примере с хвостовой рекурсией автор также использует
when(xs.size)внутри функции. В случае, если List — односвязный список, опять окажется, что каждый вызовO(N). В итоге хвостовая рекурсия не спасает, получаемO(N^2). (Можно было бы использоватьwhen(xs.isEmpty)сO(1).)В нашем проекте мы схожую проблему решаем с помощью gradle. В перспективе можно будет отправить maven на заслуженный отдых (люди к maven привыкли/прикипели и не готовы сразу с ним расстаться).
Вроде, теперь у espruino лицензия Mozilla MPLv2 и Creative Commons
Насколько я понимаю, в ScalaCheck ключевым является понятие "свойства". А генераторы используются постольку поскольку, как средство, позволяющее убедиться, что свойство выполняется в широком диапазоне значений.
ScalaCheck не подходит для замены Unit-тестов во всех случаях. Этот подход прекрасно работает тогда, когда удаётся найти те самые свойства, справедливые для многих случаев. Если программа представляет собой много отдельных несвязанных случаев — switch/case/if, то маловероятно, что такие обобщённые свойства будет легко обнаружить. А вот если тестируется универсальный алгоритм, то мы можем ожидать определённой стабильности его результатов.
Если термин "свойство-ориентированное тестирование" не нравится, то можно поискать альтернативы для слова "свойство". Например, "инвариант" — тестирование на основе инвариантов. Или "предикат" — тестирование на основе валидации предикатов. Или "ограничение" — проверка ограничений, тестирование ограничений.
Насколько я понимаю, в данном случае функтор, который конструируется из монады — единственный. Морфизм
f: A=>Bконвертируется вM[A] => M[B]путём использования двух операций, предоставляемых монадой. Вначале функциюfпревращаем в вычисление, применяя нулевое вычисление η к результату функции:φ = λa.ηfa, а затем конструируем результирующую функцию в lifted-категории с использованием моноидного умножения μ:λma.μma φ.В Scala это выглядит, как привычный способ выразить
mapчерезflatMapиpure:Эндофункторов, над которыми строится моноид, действительно много, но ни один из них, насколько я могу судить, не имеет такой формы, как этот —
(A=>B) => (M[A] => M[B]).Я рассматриваю монаду с точки зрения программирования. В статье Monads for functional programming (Philip Wadler) монада определяется как тройка, состоящая из конструктора типа, отображения, превращающего обычное значение в этот тип ("нулевое" вычисление), и отображения, связывающего два вычисления в одно.
То, что монада также является функтором, следует из того, что монада (как и функтор) позволяет преобразовать простые функции над базовыми типами в lifted-функции над сконструированным типом, то есть позволяет выполнить отображение категории обычных функции в категорию lifted-функций.
Несмотря на это, монада — более универсальная конструкция, чем функтор. Монада не только отображает обычные функции в lifted, но и предоставляет дополнительные возможности работы с функциями типа
A => M[B], которые включают конструируемый тип — "вычислениями". При этом, сам конструируемый типM[B]оказывается включен в класс объектов категории (поэтому, по-видимому, категория эндофункторов; при этом конструктор типаM[?]не включен в объекты категории). И вместо двух изолированных категорий, связанных функтором, мы оперируем одной категорией, в структуре которой выделены функции особого вида — вычисления, — и объекты —M[B], инкапсулирующие (потенциальный) результат вычисления. Для этих функций/вычислений монада предоставляет базовый набор действий, соответствующий моноиду, — нулевое действие (без вычислений), и комбинирование двух вычислений.Да, вы правы. Сокрытие и инкапсуляция хоть и идут рука об руку во многих языках, всё-таки концептуально отличаются. Неизменяемые типы данных сами по себе не исключают инкапсуляцию, а лишь подрывают рациональные основания для сокрытия данных.
Инкапсуляция, как мне кажется, подразумевает, что как только мы объявили методы доступа к данным, следующий логичный шаг — скрыть прямой доступ к этим данным, чтобы исключить нарушение абстракции. Без сокрытия от инкапсуляции остаётся лишь возможность сложить в один объект данные и функции, что, по-видимому, имеет ограниченную ценность. А вот инкапсуляция вместе с сокрытием — хороший инструмент абстрагирования.
Похоже на то. В cats:
В scalaz похожая ситуация.
Конечно, можно. Лицензия — BSD-like.
Мы сейчас этот подход используем и развиваем. В целом — достаточно удобно. При наличии неполных данных в БД (nullable колонок) — очень удобно.
(Здесь мы используем оператор
with, который соответствует конъюнкции. Для проверки принадлежности мы инвертируем условие с помощью оператора <:<2. Экономия классов не входит в цели фреймворка. Суть заключается в разрезании целого класса на отдельные компоненты и возможность оперировать данными, используя эти компоненты (слоты) в качестве ключа.
3. Пример с delta. Пусть класс Person содержит 100 полей. И пусть среди этих полей есть свойство типа T: Numeric (например, Int, Double и т.п.). Тогда мы можем объявить специальный класс PropertyDelta, который несёт изменение этого свойства
Это может быть экономнее, чем копировать оставшиеся 99 полей (при сохранении в БД, при передаче по сети и т.п.). Кроме того, здесь мы явно видим, что именно изменилось, можем проверить допустимость изменения этого свойства согласно каким-либо правилам.
Теперь мы можем этот объект использовать для того, чтобы увеличить значение свойства на указанную величину:
Или немного поинтереснее:
vs.