Ничего не мешает недоброжелателю зарегистрировать несколько аккаунтов / купить несколько SIM-карт. Поднимая порог, мы обнаружим, что ООО «Деньги прямо сейчас» в г. Челябинске невозможно заблокировать по причине отсутствия нужного количества заявок на блокировку.
Методы фильтрации должны быть существенно дороже для недоброжелателя. К примеру, заявки должен принимать модератор, просматривающий выдачу Google при поиске по конкретному номеру телефона. Подменить выдачу Google можно, но это уже намного дороже SIM-карт. Вряд ли кто захочет этим заниматься, чтобы не позволить какому-то человеку принять звонок, даже если речь идёт о бизнесе.
Как это нередко бывает в науке, три года назад статью о «классификации знаний в программировании» уже опубликовали под названием «теоретический минимум для программиста». Там есть и список литературы, и перевод на английский язык.
Перескажу вам вкратце оригинальную статью Охслина.
0) H — наша хеш-функция. Например, мд5.
1) Множество паролей, для которых строится таблица, можно пронумеровать. функция R берёт хеш (как одно число) по модулю количество_паролей и использует результат как индекс в этом множестве паролей. (Радужность таблицы, на самом деле, подразумевает, что для таблицы с номером k к хешу мы ещё добавим k)
2) Возьмем произвольный хеш. Построим чейн: применим к хешу по очереди функции R и H, к результату применим их ещё раз, и так всего N раз. Получим какой-то хеш в самом конце. N называется длиной чейна. Первый и последний хеши сохраним в таблицу. Сделаем так M раз.
3) Отсортируем таблицу по второй колонке (где последние хеши), чтобы было удобнее дальше работать.
4) Время взломать хеш. Строим вышеописанным способом чейн, начиная с данного хеша. Для каждого из промежуточных хешей делаем следующее. Мы ищем его во второй колонке. Если найден, восстанавливаем чейн по хешу из первой колонки. Если нам повезло, то исходный текст для исходного хеша попадётся в ходе вычисления чейна. Если не вполне понятно, рекомендую нарисовать себе картинку: чейн для исходного хеша и чейн из таблицы, сдвинутые друг относительно друга (некий элемент первого совпадает с последним второго).
Вы определили результат через другие понятия, а не выстроили порядок вычислений.
Вот поэтому я и говорю, что мыслить словесно о формальном языке глупо. Это было конструктивное тому доказательство, если не вполне было ясно из контекста.
А причем здесь вообще типы и Хаскель?
Потому что вы спрашивали про чудеса с типизацией комбинатора неподвижной точки, если вам изменяет память. Хаскелл был использован для примера. Могу предложить самостоятельно найти интерпретатор просто типизированного лямбда-исчисления, если Хаскелл вас по каким-то причинам не устраивает.
Причисляя язык к классу декларативных, Вы во многом определяете то, как писать на нем программы.
А, то есть декларативность можно определить только со слов автора? Я согласен на цитату.
Математика — это язык, причем формальный.
Математика это наука. То, что основной метод формального мышления, — языки, а точнее formal systems, утверждать процитированное не позволяет.
Остальное комментировать бессмысленно, поскольку контраргументы вы не прокомментировали, из чего я делаю вывод, что они до вас попросту не дошли. Не возьмусь сказать, на каком этапе восприятия это произошло, но перечитать и попытаться их оспорить рекомендую.
Декларативность связана с языком, которым изъясняются люди при постановке задачи.
Здесь зарыта очередная ошибка, состоящая в том, что устное условие задачи не является полным, и не определяет задачу как таковую. Декларативность — не мера наличия искусственного интеллекта.
Программисты пытаются придумать некоторые абстракции, чтобы для пользователя системы язык выглядел наиболее естественным.
Это не единственная причина.
Имеет возможность создавать Domain Specific Language.
Почти любой язык имеет эту возможность. Даже если язык способен только лишь определять функции, определённый набор функций (библиотека) реализует своеобразный DSEL. Кроме того, прошу не путать DSL и DSEL, потому что DSL можно реализовать вообще не любом Тьюринг-полногом языке.
является описательным языком теорем
Нет, не является.
но это потому что семантика языка другая
Здесь следовало согласиться или опровергнуть тезис, что декларативность это неправильное понятие, а не приводить абсурдные аргументы против неизвестного тезиса.
математической нотацией, которая декларативна по определению
Определение математической нотации в студию.
На Хаскеле Вы описываете предмет задачи в терминах функций
На Хаскелле вы описываете предмет задачи на весьма обширном языке, стандарт которого содержится на 200+ страницах, который даже после обстоятельного desugaring превращается в язык с 6 элементами (лямбда-абстракция, аппликация, конструкторы типов, сравнение с образцом, let и ещё что-то, я запамятовал) и десятком правил. Функции действительно встречаются какой-то частью в этом разнообразии. но не указываете напрямую способ ее решения
Ну это совсем уже смешно. Вы считаете, что нормальный порядок редукции позволяет утверждать, что Haskell не выполяет указанные действия по порядку вообще?
filter (\x. x % 2 == 0) [1..]
«Чтобы получить результат, построй бесконечный список натуральных чисел, затем отфильтруй все нечётные числа. Действия исполняй лениво.»
Ошибка в ваших рассуждениях заключается в том, что мыслить о формальном языке в терминах натурального вообще бессмысленно. Я могу придумать и императивное чтение, и декларативное чтение, и вообще состоящее из одних деепричастий. Это глупо.
Напомню Y = \f.(\x.f(xx))(\x.f(xx))
Как только вы расставите здесь типы (особенно интересует тип x), а ещё лучше — сможете запустить эту функцию в Haskell, тогда мы сможем продолжить беседу на эту тему.
в рамках лямбда-исчисления множество вычислимых функций может быть разбито на классы эквивалентности, в каждом из которых существует функция с простейшей формой.
Да что вы? А в Си или для машины Тьюринга этого сделать нельзя?
найти простейшую форму определения функции.
В смысле? Найти самую простую форму для данной семантики? Это не undecidable ли задача? Попахивает какой-то колмогоровской сложностью. Вообще впервые слышу о том, что это кому-то может понадобиться. Можно ссылку на статью?
Что за чудеса с типизацией и комбинатором неподвижной точки?
Ну проблема типизации Y-комбинатора же традиционная, и обычно попросту добавляют fix: forall a. (a -> a) -> a как дополнительный примитив, наряду с лямбда-абстракцией и аппликацией.
подразумевает описание того, что нужно вычислить, а не как это сделать
Я сейчас поясню, почему этим термином нельзя пользоваться. Возьмем Хаскелл. Да, понятно, что ADT только определяет тип, но ничего не говорит о том, как его хранить в памяти и т.п., компилятор должен «придумать» это сам. Однако, он не способен решить какую-нибудь задачу о переправе (капуста, коза и волк, ну вы помните) по одному только определению, придётся написать решение с помощью какой-нибудь монады List самому.
Возьмем С++. Он требует точно описывать, что где хранится. Но он способен сам оптимизировать возвращаемые значения функций (оптимизация RVO), и сам распределяет переменные по регистрам.
Декларативность это не имманентное свойство, это некоторое значение. Оно варьируется в разных языках, и везде отлично от нуля.
Хорошо, что мы сохраняем конструктивный стиль беседы. Я хотел бы в рамках оффтопа привести вот эту ссылку plakhov.livejournal.com/170496.html.
Монады — не только способ «эмуляции поведения, которое в рамках чистоты сложно реализовать», это только одно из их применений
О, ну конечно же, это же ещё моноиды в категории эндофункторов. Будьте прагматиком, монады это всего лишь абстракция. Не лучше и не хуже мутабильных переменных, исключений и прочего.
Функциональное программирование основано на лямбда-исчислении и комбинаторной логике.
Подробнее, пожалуйста. Я думал, что оно основано на куда более серьёзной теории, вроде теории типов, formal methods и пр., а не на частном случае их применения. Более того, лямбда-исчислений как таковых далеко не одно и не два. Даже порядков редукции на них пруд пруди (inner-most, outer-most, outer-most graph etc.)
Лямбда-исчисления является простейшим полным по Тьюрингу языком программирования.
Во-первых, я обязан попросить вас формализовать понятие «простейший». Во-вторых, это, очевидно, ложь. Даже после банального преобразования де Брейна получается более «простой» язык. А про чудеса с типизацией и комбинатором неподвижной точки я вообще молчу.
Более того, большая часть языков программирования могут быть описаны в терминах лямбда-исчисления
Вы не поверите, любой Тьюринг-полный язык можно подвергнуть трансляции в Тьюринг-полное лямбда-исчисление.
Реализовать отдельные концепции функционального программирования можно на императивном языке
Вы не поверите, но любые концепции можно реализовать на любом языке. Просто потому, что никакой разницы в парадигмах нет при наличии Т-полноты.
термин с вполне конкретным значением и глубоким смыслом
Так любят говорить филологи. Они часто утверждают, что X имеет глубокий смысл, но никогда не осмеливаются его назвать. Попробуйте ещё.
Лисп-машин нет по многим причинам. Если собрать аргументацию буквально в нескольких словах, то это будет «не могло работать». Зато есть проект Reduceron, который не так сильно попахивает распилом государственных средств.
Вынужден немного почитать вам нотации. Я не буду использовать слишком общий термин «функциональное программирование», поскольку оно бывает весьма разным, приведу в пример только Haskell. Авторы языка были заинтересованы, что же произойдёт, если все функции сделать чистыми, т.е. без побочных эффектов. Монады в нём являются лишь способом эмуляции поведения, которое в рамках чистоты сложно реализовать.
Тем не менее, нельзя считать императивное программирование подмножество функционального. В библиотеке FC++ (для С++) авторы реализовали (помимо карринга, list comprehensions и пр.) монады. Риторический вопрос: стоит ли считать, что функциональное программирование — подмножество императивного?
Декларативность как слово давно является моветоном в кругах программистов, потому что это прилагательное, а не термин.
Стоит отметить, что сообщество небольшое, но очень лояльное: практически все известные языки нашли свое отражение в современных языках (Lisp, ML -> F#, Scala; Smalltalk -> Java, Scala (агенты), скриптовые -> Ruby), в отличие от Пролог.
А почему сразу ОЗУ? Ошибки могут происходить и в контроллере на сетевой карте. Готов поспорить, что ЕСС во встроенной памяти этого контроллера не используется нигде.
Где-то на просторах читал, что в эксперименте (с одним типом памяти; возможно, она была китайской) было 12 ошибок в сутки на 1 Гб. При росте объёма памяти растёт и количество ошибок (при приблизительно том же матожидании на 1 Гб). «Этот» бит может быть и не одним, всё же DNS-запрос обрабатывается не за один такт, и не в одной ячейке памяти. Кроме того, настройки латентности операций с памятью в BIOS придумали не просто так. Не думаю, что где-то здесь есть повод для иронии.
Мой друг без аккаунта на Хабре попросил запостить следующее (надеюсь, что это не является нарушением правил, поскольку песочницы для комментариев нет):
Алгоритм вывода для систем типов Хиндли-Милнера был придуман Дамасом и Милнером. Он подходит для некоторого ряда систем типов, которые обладают общими свойствами. Оригинальная система типов, с которой работали Хиндли и Милнер была простое типизированное лямбда-исчисление. Современные алгоритмы вывода типов в языках Haskell, Ocaml, Standard ML хоть и предназначены для работы с более мощными системами типов, в основе содержат тот же алгоритм.
Язык Scala же, напротив, имеет систему типов, для которой вывод типов по этому алгоритму невозможен. Поэтому она использует другой алгоритм, он придуман Пирсом (local type inference) и улучшен Одерским (colored local type inference). Поэтому иллюстрировать текст про алгоритм Хиндли-Милнера примерами на Скале нехорошо. Спиваку об этом, кстати, несколько раз написали в комментариях к исходному посту. Он ответил, что да, он это сейчас понимает, но на момент написания текста (2008-й год) он этого не знал и текст уже переделывать не станет.
Можно и пофрилансить в «свободное» время. Кнопочки порисовать там. Но достаточно актуальным такой выбор становится только для очень высокооплачиваемых людей.
Методы фильтрации должны быть существенно дороже для недоброжелателя. К примеру, заявки должен принимать модератор, просматривающий выдачу Google при поиске по конкретному номеру телефона. Подменить выдачу Google можно, но это уже намного дороже SIM-карт. Вряд ли кто захочет этим заниматься, чтобы не позволить какому-то человеку принять звонок, даже если речь идёт о бизнесе.
Спойлер: O(N) в этом (худшем) случае.
0) H — наша хеш-функция. Например, мд5.
1) Множество паролей, для которых строится таблица, можно пронумеровать. функция R берёт хеш (как одно число) по модулю количество_паролей и использует результат как индекс в этом множестве паролей. (Радужность таблицы, на самом деле, подразумевает, что для таблицы с номером k к хешу мы ещё добавим k)
2) Возьмем произвольный хеш. Построим чейн: применим к хешу по очереди функции R и H, к результату применим их ещё раз, и так всего N раз. Получим какой-то хеш в самом конце. N называется длиной чейна. Первый и последний хеши сохраним в таблицу. Сделаем так M раз.
3) Отсортируем таблицу по второй колонке (где последние хеши), чтобы было удобнее дальше работать.
4) Время взломать хеш. Строим вышеописанным способом чейн, начиная с данного хеша. Для каждого из промежуточных хешей делаем следующее. Мы ищем его во второй колонке. Если найден, восстанавливаем чейн по хешу из первой колонки. Если нам повезло, то исходный текст для исходного хеша попадётся в ходе вычисления чейна. Если не вполне понятно, рекомендую нарисовать себе картинку: чейн для исходного хеша и чейн из таблицы, сдвинутые друг относительно друга (некий элемент первого совпадает с последним второго).
Вот поэтому я и говорю, что мыслить словесно о формальном языке глупо. Это было конструктивное тому доказательство, если не вполне было ясно из контекста.
А причем здесь вообще типы и Хаскель?
Потому что вы спрашивали про чудеса с типизацией комбинатора неподвижной точки, если вам изменяет память. Хаскелл был использован для примера. Могу предложить самостоятельно найти интерпретатор просто типизированного лямбда-исчисления, если Хаскелл вас по каким-то причинам не устраивает.
Причисляя язык к классу декларативных, Вы во многом определяете то, как писать на нем программы.
А, то есть декларативность можно определить только со слов автора? Я согласен на цитату.
Математика — это язык, причем формальный.
Математика это наука. То, что основной метод формального мышления, — языки, а точнее formal systems, утверждать процитированное не позволяет.
Остальное комментировать бессмысленно, поскольку контраргументы вы не прокомментировали, из чего я делаю вывод, что они до вас попросту не дошли. Не возьмусь сказать, на каком этапе восприятия это произошло, но перечитать и попытаться их оспорить рекомендую.
Здесь зарыта очередная ошибка, состоящая в том, что устное условие задачи не является полным, и не определяет задачу как таковую. Декларативность — не мера наличия искусственного интеллекта.
Программисты пытаются придумать некоторые абстракции, чтобы для пользователя системы язык выглядел наиболее естественным.
Это не единственная причина.
Имеет возможность создавать Domain Specific Language.
Почти любой язык имеет эту возможность. Даже если язык способен только лишь определять функции, определённый набор функций (библиотека) реализует своеобразный DSEL. Кроме того, прошу не путать DSL и DSEL, потому что DSL можно реализовать вообще не любом Тьюринг-полногом языке.
является описательным языком теорем
Нет, не является.
Здесь следовало согласиться или опровергнуть тезис, что декларативность это неправильное понятие, а не приводить абсурдные аргументы против неизвестного тезиса.
математической нотацией, которая декларативна по определению
Определение математической нотации в студию.
На Хаскеле Вы описываете предмет задачи в терминах функций
На Хаскелле вы описываете предмет задачи на весьма обширном языке, стандарт которого содержится на 200+ страницах, который даже после обстоятельного desugaring превращается в язык с 6 элементами (лямбда-абстракция, аппликация, конструкторы типов, сравнение с образцом, let и ещё что-то, я запамятовал) и десятком правил. Функции действительно встречаются какой-то частью в этом разнообразии.
но не указываете напрямую способ ее решения
Ну это совсем уже смешно. Вы считаете, что нормальный порядок редукции позволяет утверждать, что Haskell не выполяет указанные действия по порядку вообще?
filter (\x. x % 2 == 0) [1..]
«Чтобы получить результат, построй бесконечный список натуральных чисел, затем отфильтруй все нечётные числа. Действия исполняй лениво.»
Ошибка в ваших рассуждениях заключается в том, что мыслить о формальном языке в терминах натурального вообще бессмысленно. Я могу придумать и императивное чтение, и декларативное чтение, и вообще состоящее из одних деепричастий. Это глупо.
Напомню Y = \f.(\x.f(xx))(\x.f(xx))
Как только вы расставите здесь типы (особенно интересует тип x), а ещё лучше — сможете запустить эту функцию в Haskell, тогда мы сможем продолжить беседу на эту тему.
в рамках лямбда-исчисления множество вычислимых функций может быть разбито на классы эквивалентности, в каждом из которых существует функция с простейшей формой.
Да что вы? А в Си или для машины Тьюринга этого сделать нельзя?
простейшей формой
Неформально.
Это тоже абстракция :)
найти простейшую форму определения функции.
В смысле? Найти самую простую форму для данной семантики? Это не undecidable ли задача? Попахивает какой-то колмогоровской сложностью. Вообще впервые слышу о том, что это кому-то может понадобиться. Можно ссылку на статью?
Что за чудеса с типизацией и комбинатором неподвижной точки?
Ну проблема типизации Y-комбинатора же традиционная, и обычно попросту добавляют fix: forall a. (a -> a) -> a как дополнительный примитив, наряду с лямбда-абстракцией и аппликацией.
подразумевает описание того, что нужно вычислить, а не как это сделать
Я сейчас поясню, почему этим термином нельзя пользоваться. Возьмем Хаскелл. Да, понятно, что ADT только определяет тип, но ничего не говорит о том, как его хранить в памяти и т.п., компилятор должен «придумать» это сам. Однако, он не способен решить какую-нибудь задачу о переправе (капуста, коза и волк, ну вы помните) по одному только определению, придётся написать решение с помощью какой-нибудь монады List самому.
Возьмем С++. Он требует точно описывать, что где хранится. Но он способен сам оптимизировать возвращаемые значения функций (оптимизация RVO), и сам распределяет переменные по регистрам.
Декларативность это не имманентное свойство, это некоторое значение. Оно варьируется в разных языках, и везде отлично от нуля.
Хорошо, что мы сохраняем конструктивный стиль беседы. Я хотел бы в рамках оффтопа привести вот эту ссылку plakhov.livejournal.com/170496.html.
О, ну конечно же, это же ещё моноиды в категории эндофункторов. Будьте прагматиком, монады это всего лишь абстракция. Не лучше и не хуже мутабильных переменных, исключений и прочего.
Функциональное программирование основано на лямбда-исчислении и комбинаторной логике.
Подробнее, пожалуйста. Я думал, что оно основано на куда более серьёзной теории, вроде теории типов, formal methods и пр., а не на частном случае их применения. Более того, лямбда-исчислений как таковых далеко не одно и не два. Даже порядков редукции на них пруд пруди (inner-most, outer-most, outer-most graph etc.)
Лямбда-исчисления является простейшим полным по Тьюрингу языком программирования.
Во-первых, я обязан попросить вас формализовать понятие «простейший». Во-вторых, это, очевидно, ложь. Даже после банального преобразования де Брейна получается более «простой» язык. А про чудеса с типизацией и комбинатором неподвижной точки я вообще молчу.
Более того, большая часть языков программирования могут быть описаны в терминах лямбда-исчисления
Вы не поверите, любой Тьюринг-полный язык можно подвергнуть трансляции в Тьюринг-полное лямбда-исчисление.
Реализовать отдельные концепции функционального программирования можно на императивном языке
Вы не поверите, но любые концепции можно реализовать на любом языке. Просто потому, что никакой разницы в парадигмах нет при наличии Т-полноты.
термин с вполне конкретным значением и глубоким смыслом
Так любят говорить филологи. Они часто утверждают, что X имеет глубокий смысл, но никогда не осмеливаются его назвать. Попробуйте ещё.
Тем не менее, нельзя считать императивное программирование подмножество функционального. В библиотеке FC++ (для С++) авторы реализовали (помимо карринга, list comprehensions и пр.) монады. Риторический вопрос: стоит ли считать, что функциональное программирование — подмножество императивного?
Декларативность как слово давно является моветоном в кругах программистов, потому что это прилагательное, а не термин.
Можно несколько подробнее раскрыть эту мысль?
Постойте, а как же Erlang?
Алгоритм вывода для систем типов Хиндли-Милнера был придуман Дамасом и Милнером. Он подходит для некоторого ряда систем типов, которые обладают общими свойствами. Оригинальная система типов, с которой работали Хиндли и Милнер была простое типизированное лямбда-исчисление. Современные алгоритмы вывода типов в языках Haskell, Ocaml, Standard ML хоть и предназначены для работы с более мощными системами типов, в основе содержат тот же алгоритм.
Язык Scala же, напротив, имеет систему типов, для которой вывод типов по этому алгоритму невозможен. Поэтому она использует другой алгоритм, он придуман Пирсом (local type inference) и улучшен Одерским (colored local type inference). Поэтому иллюстрировать текст про алгоритм Хиндли-Милнера примерами на Скале нехорошо. Спиваку об этом, кстати, несколько раз написали в комментариях к исходному посту. Он ответил, что да, он это сейчас понимает, но на момент написания текста (2008-й год) он этого не знал и текст уже переделывать не станет.