?

Log in

No account? Create an account
О глубокой философии программирования (серьезный разговор) - ru_declarative [entries|archive|friends|userinfo]
ru_declarative

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

О глубокой философии программирования (серьезный разговор) [Feb. 18th, 2008|03:17 am]
ru_declarative

ru_declarative

[anonym_mouse]
.
Есть на Интернете программист-блоггер, 7 лет проработавший в Амазоне. Зовут его Стив Егге, и славен он тем, что в блоге публикует свои "rants" на компьютерные темы. Каждая запись - страниц 5 убористого текста. Многое разумно (ему 39 лет и он достаточно много программировал), но хотя бы из-за объема, многое противоречит себе же. Стив Егге - прототипический п..бол.

И однако одна из записей поразила меня глубоким проникновением в тему. Я давно о ней размышлял, именно в таких, грамматических, терминах. Представляю вам где-то 2/3 его записи в сокращенном несколько виде.


Steve Yegge:
ИСПОЛНЕНИЕ КОРОЛЕВСКИХ ПОСТАНОВЛЕНИЙ[*] В ЦАРСТВЕ СУЩЕСТВИТЕЛЬНЫХ

[*] - игра слов. В оригинале заголовок одновременно означает "Казнь в Царстве Существительных" (execution).

Hello, world!
Здравствуй, мир! Сегодня мы послушаем рассказ о Злом Царе Явы и его борьбу за всемирное уничтожение глаголов.

ПРЕДУПРЕЖДЕНИЕ: у этой сказки нет счастливого конца. Эта сказка не для слабых духом ни для критикующего гласа. Если вы легко обижаетесь или превращаетесь в противного парня в своих комментариях, немедленно перестаньте читать.

Прежде чем начать, разберемся с одним концептуальным изгибом.


The Garbage Overfloweth
МУСОР ПЕРЕПОЛНЯЕТ МУСОРНОЕ ВЕДРО


Все явисты любят диаграммы "use cases", с них и начнем: т.е. вынесем мусор. В том смысле, как во фразе "Джонни, вынеси мусор! Он уже через верх валится!"

Если вы - обычный, нормальный англоговорящий человек, и вас попросили описать вынос мусора, вы наверно думаете о нем примерно так:
    - достать мусорный (пластиковый) мешок из-под раковины
    - вынести его в гараж
    - запихнуть его в большое (пластиковое) ведро [которые в американских городах выставляют к бордюру и их собирают раз в день мусорщики - переводкчик]
    - вернуться в дом
    - вымыть руки
    - шлепнуться на диван
    - продолжать играть в видеигру (или что вы там делали)

Даже если вы не говорите по-английски ..... это - серия действий.
Наши мысли полны отважными, стремительными, эмоциональными действиями. Мы живем, боимся, едим, пьем, идем, останавливаемся, или выносим мусор.
.......

Разумеется, наши мысли также переполнены существительным. Мы едим существительные, покупаем существительные в магазине, мы сидим на существительных, и спим на них. Существительные могут свалиться на вашу голову, создав на голову существительное больш(ую)ое проблему существительное.
Существительные - вещи, но они только вещи. ....... Интересны изменения случающиеся с этими вещами.

Изменения требуют действия, т.е. глагола.

И, конечно, вдобавок к глаголам и существительным, есть еще прилагательные, наречия, местоимения и связки. Все играют роль, и было бы жалко их все потерять. ...........
Но как странно было бы неожиданно решить, что мы больше не можем использовать глаголы?

Сейчас я расскажу вам сказку о царстве, где произошло именно это.


The Kingdom of Nouns
КОРОЛЕВСТВО СУЩЕСТВИТЕЛЬНЫХ


В Явском королевстве, где Король Ява правит держа всех в кремниевом кулаке, людям не позволено думать как нам с вами. В Явалэнде, панимаишь, существительные очень важны, по приказу самого короля. Существительные - главные подданные королевства. Они расхаживают выглядя аристократично в ярких одеждах, которую поставляют Прилагательные, вполне довольные своей судьбой. Прилагательные принадлежат классу пониже, но они не могут нарадоваться, что не родились Глаголами.

Потому что судьба граждан-Глаголов в королестве очень, очень дурна.

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

Глаголы в Явалэнде делают всю работу, но поскольку их презирают все сословия, ни одному Глаголу не позволено передвигаться самостоятельно. Если Глагол появляется в публичном месте, то всегда только в сопровождении Существительного.

Конечно, "сопровождать", само будучи глаголом, не может бегать без одежды, для него необходимо вызвать ГлаголоСопровождающий. Но что же "вызвать"? - оказывается, Вызывающие и ВспомогательствующиеВызовам также довольно важные Существительные работа которых - присматривать за низкими глаголами "вызвать" и т.д.

Король, посоветовавшись с Богом Солнца по такому важному вопросу, иногда угрожал полностью изгнать всех Глаголов из Королевства Явы. Если такое случится, то жителям понадобится хотя бы один Глагол чтобы делать за них всю работу, и Король, обладая довольно жестоким чувством юмора, решил, что им останется глагол "ИсполнитьОкончательныйУказ" [по-английски - игра слов: execute означает одновременно "исполнить" на официальном языке, и "казнить" -- переводчик]

Глагол "Исполнить" (и его кузины-синонимы "делать", "начать", "пшел", "давайделай", и "впередвперед") могут сделать работу любого другого Глагола подменив его соответствующим ИсполнительнымСуществительным, и вызовом "исполнить()".
Вам нужно почистить зубы? - ЗубоЧиститель(моиЗубы).вперед()
Вынести мусор? -МусорВыносительПланоИсполнитель.давайделай()

В наиболее патриотических провинциях Явалэнда Существительные полностью выдавили Глалогы. Случайному наблюдателю может показаться, что глаголы все еще мелькают, здесь и там, перепахивая поля и вынося господские ночные горшки. Но если присмотреться, вскорости открывается секрет: Существительные могут просто менять имена своих Глаголов-исполнителей(), называя слуг по имени господ (что не изменяет их работы ни малейшим образом). Когда вы заметите,что ПолеВспашка "пашет()", НочноГоршкоОпорожнитель "выливает()", или МэнеджерРегистрации неожиданно сам "регистрирует()", на самом деле вы встретились с армией "Исполнителей.Указов" злого короля, переодетых в одежды своих Существительных



Verbs in Neighboring Kingdoms
О ГЛАГОЛАХ В СОСЕДНИХ КОРОЛЕВСТВАХ


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

Например, в соседнем Силэнде, Пёрлэнде и Рубилэнде можно моделировать вынос мусорного ведра серией действий, т.е. глаголов, т.е. функций. Затем они прилагают эти действия к соответствующим объектам и нужном порядке (вытащи + мусор, вынеси + что + куда и т.д.), задача выноса мусора успешно завершается, и никаких смотрителей и дуэний для глаголов не потребовалось.


В этих королевствах нет нужды создавать существительные-обертки для глаголов. У них не появляется ни МусороВыносительнойСтратегии, ни МусороВыносителеЦелеУказания для обнаружения куда идти с мешком в гараже, ни ПослеМусороВынесеннойАкцииОбратногоВызова
прежде чем вы сможете вернуться на свой диван. Они прости пишут глаголы, работающие с существительными, а за тем запускают главный глагол, "вынести_мусор()", включающий мелкие под-действия в нужном порядке.

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

Разница в том, что когда глаголам позволено существовать независимо, не приходится изобретать существительные, которые бы их содержали внутри себя.

Явалэндеское население посматривает на соседей с презрением. Так и живут люди в Программистских Королевствах.


If You Dig a Hole Deep Enough...
ЕСЛИ КОПАТЬ ОЧЕНЬ ГЛУБОКО...

[игра слов: первая часть современной американской поговорки: если выкопать очень глубокую яму, попадешь в Китай; также см. "deep hole to China" - перев.]

На другой стороне мира есть малонаселенные земли, в чьих королевствах Глаголы оказываются среди знати. Это - Функциональные Королевства, которые включают Хаскелию, Окамлику, Схемерию и несколько других. Их жители редко встречают граждан земель в округе Явалэнда. Поскольку рядом с ними мало кто живет, и когда им нечем заняться, они ведут войны друг с другом.

В Функциональных Королевствах Существительные и Глаголы обычно считаются гражданами одной касты. Однако Существительные, оставаясь существительными, в основном сидят ничего не делая. Они не видят смысла в беготне и исполнении работ, поскольку Глаголы вполне активны и уже всем этим занимаются. В этих странах нет странных законов, обязывающих создание Существительных для сопровождения каждого Глагола, поэтому здесь живет ровно столько существительных, сколько в королевстве найдется вещей.

В результате, глаголы оказываются исполнительной властью, извините за выражение. Путешественнику легко может показаться, что Глаголы (т.е. функции) - самые важные подданные. Именно поэтому королевства называют Функциональными, а не Вещественными.

На самом отшибе за Функциональными Королевствами, лежит былинная земля под названием Лямбда Окраинная (Lambda the Ultimate). В этом месте, рассказывали люди, вообще не водятся "существительные"! Там живут только глаголы! Конечно, в королевстве есть "вещи", но все они созданы из глаголов, даже сами числа чтобы пересчитывать овец [игра слов: lambda - lamb, звучат похоже -- переводчик], которые оказывается самая популярная форма денег для обменов в тех краях, если слухи не врут. Например, 0 - просто лямбда(), а 1 - лямбда(лямбда()), 2 - (лямбда(лямбда(лямбда()))) и т.д. Каждое, глагол ли, существительное или что-то еще, сконструировано из Главного Глагола, "Лямбда".

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




Are Javalanders Happy?
СЧАСТЛИВЫ ЛИ ЯВИСТЫ?


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

      [Напомню стишок-поучение - перев]:
      Не было гвоздя — подкова пропала
      Не было подковы — лошадь захромала
      Лошадь захромала — командир убит
      Конница разбита, армия бежит.
      Враг вступает в город, пленных не щадя
      Оттого, что в кузнице не было гвоздя.


    Не было гвоздя - "брось новое ПодковоГвоздьНеНайденИсключение("гвоздей нет!")

    Не было подковы - "ЛошадеДоктор.получитьМестнуюКопию().получитьЛошадеДиспетчер().давайделай()

    Лошадь захромала - СкаковойКлуб.получитьСсписокОповещенияПодписчиковНаездников().получитьРассылателя().вперед(новое СообщениеРассылка(Конюшня.получитьНулевойЛошадеОбразец()))

    ............/и так далее/.............


    For the lack of a nail,
        throw new HorseshoeNailNotFoundException("no nails!");
    
    For the lack of a horseshoe,
        EquestrianDoctor.getLocalInstance().getHorseDispatcher().shoot();
    
    For the lack of a horse,
        RidersGuild.getRiderNotificationSubscriberList().getBroadcaster().run(
          new BroadcastMessage(StableFactory.getNullHorseInstance()));
    
    For the lack of a rider,
        MessageDeliverySubsystem.getLogger().logDeliveryFailure(
          MessageFactory.getAbstractMessageInstance(
            new MessageMedium(MessageType.VERBAL),
            new MessageTransport(MessageTransportType.MOUNTED_RIDER),
            new MessageSessionDestination(BattleManager.getRoutingInfo(
                                            BattleLocation.NEAREST))),
          MessageFailureReasonCode.UNKNOWN_RIDER_FAILURE);
    
    For the lack of a message,
        ((BattleNotificationSender)
          BattleResourceMediator.getMediatorInstance().getResource(
            BattleParticipant.PROXY_PARTICIPANT,
            BattleResource.BATTLE_NOTIFICATION_SENDER)).sendNotification(
              ((BattleNotificationBuilder)
                (BattleResourceMediator.getMediatorInstance().getResource(
                BattleOrganizer.getBattleParticipant(Battle.Participant.GOOD_GUYS),
                BattleResource.BATTLE_NOTIFICATION_BUILDER))).buildNotification(
                  BattleOrganizer.getBattleState(BattleResult.BATTLE_LOST),
                  BattleManager.getChainOfCommand().getCommandChainNotifier()));
    
    For the lack of a battle,
        try {
            synchronized(BattleInformationRouterLock.getLockInstance()) {
              BattleInformationRouterLock.getLockInstance().wait();
            }
        } catch (InterruptedException ix) {
          if (BattleSessionManager.getBattleStatus(
               BattleResource.getLocalizedBattleResource(Locale.getDefault()),
               BattleContext.createContext(
                 Kingdom.getMasterBattleCoordinatorInstance(
                   new TweedleBeetlePuddlePaddleBattle()).populate(
                     RegionManager.getArmpitProvince(Armpit.LEFTMOST)))) ==
              BattleStatus.LOST) {
            if (LOGGER.isLoggable(Level.TOTALLY_SCREWED)) {
              LOGGER.logScrewage(BattleLogger.createBattleLogMessage(
                BattleStatusFormatter.format(BattleStatus.LOST_WAR,
                                             Locale.getDefault())));
            }
          }
        }
    
    For the lack of a war,
        new ServiceExecutionJoinPoint(
          DistributedQueryAnalyzer.forwardQueryResult(
            NotificationSchemaManager.getAbstractSchemaMapper(
              new PublishSubscribeNotificationSchema()).getSchemaProxy().
                executePublishSubscribeQueryPlan(
                  NotificationSchema.ALERT,
                  new NotificationSchemaPriority(SchemaPriority.MAX_PRIORITY),
                  new PublisherMessage(MessageFactory.getAbstractMessage(
                    MessageType.WRITTEN,
                    new MessageTransport(MessageTransportType.WOUNDED_SURVIVOR),
                    new MessageSessionDestination(
                      DestinationManager.getNullDestinationForQueryPlan()))),
                  DistributedWarMachine.getPartyRoleManager().getRegisteredParties(
                    PartyRoleManager.PARTY_KING ||
                    PartyRoleManager.PARTY_GENERAL ||
                    PartyRoleManager.PARTY_AMBASSADOR)).getQueryResult(),
            PriorityMessageDispatcher.getPriorityDispatchInstance())).
          waitForService();
    


    All for the lack of a horseshoe nail.


И все - из-за одного гвоздя

Глубокая мудрость, верная до сегодняшнего дня




[anonym_mouse, переводчик]
К этому добавлю от себя. К моему удивлению, первые комментаторы перевода в ru_programming просто не поняли о чем речь в этом отрывке (!!!)

А речь идет о логике программирования вообще. Человеческий язык в огромной степени "встроен" в наш мозг, и его структуры отражают структуры мышления самым точным и тонким образом. Ученым нужно делать не ЯМР-сканы мозга, а копаться в устройстве человеческой речи.

Поэтому ИДЕАЛЬНЫЙ язык программирования должен позволять ЕСТЕСТВЕННЫЙ для человека лингвистический разбор задачи на куски и их изложение.

Изложенные в заметке парадигмы - императивная (пойди, возьми, положи, повернись, вернись) и "объектно-ориентированная" - не охватывают всего. Упомянута функциональная. На псевдо-Лиспе она выглядит примерно так:
(цель - вынести мусор):
    (или 
             (и 
               (засунуть (переместить (взять мешок) в_гараж) (поднять крышку_бака)) 
               (вернуться) 
               (лечь на диван)
             ) 
             (сообщить о провале операции)
         )
    

"взять мешок" дает "существительное", состояние (вроде "мешок в руках"), которое может стать дополнением глагольной формы "переместить что куда", далее оно вложено в "засунуть что куда", где последнее "куда" также получилась из вложенного "поднять что", и так далее

Когда существительное (состояние и т.д.) образуется в результате действий над предыдущим состоянием или предметом (которых, _исходных_ предметов и их собраний, в программе относительно мало) - и вместо того, чтобы давать ему имя, мы анонимно вкладываем его в следующее по цепочке действие

В этом есть что-то очень увлекательное для мозга, и такое программирование доставляет удовольствие и имеет огромные преимущества по сравнению с выморочными, ублюдочными объектами, насилующими естественное мышление и логику, так хорошо осмеянными в заметке.

Однако осталась нерассмотренной еще одна крупная парадигма: декомпозиция задачи установкой целей. Неважно, цель выражается глагольной формой или сочетанием, или фразой существительного.

    (цель) ДОМ :- (зависит от) крыша, стены, окна, двери
    
    Крыша:- стропила, черепица
    
    стропила:- дерево_подготовить, конструкцию_поднять, конструкцию_собрать
    
    конструкцию_собрать:
        (конкретные вычисления-операторы через и, или, ...)
    

Это - логическое программирование, Пролог.
Заметьте, что я не занимаюсь выстраиванием линейной последовательности исполнения, как в случае декларативного программирования с функциями. Я думаю локально, о соседнем уровне, оставляя глобальные увязки программе

Мне возразят - но главное в логическом программировании - декларативность (сначала "описание", потом "вопросы" к нему). Нет, это лишь одна сторона языка, для работы с "базами данных", считайте его языком со встроенной БД. Самое частое и поразительно эффективное применение пролога - просто в логическом разбиении на подзадачи. Он - самая естественная парадигма, с помощью которой мозгу легче всего справиться с огромным материалом, просто потому что это отделяет конкретные вычисления от мета-уровня и позволяет "думать локально", но получать при этом верные глобально результаты.
(Тут можно возразить, что в этом качестве мой пример полностью эквивалентен разбиению на подпрограммы и функции - но странный трюк, который голова проделывает с нами, в том, что функции менее очевидны, чем мышление в терминах "целей". Оно поразительно прибавляет сил - и масштаб куска кода, с которым ты можешь справиться чисто "в уме").

Программирование происходит на двух уровнях: конкретные мелкие операторы-вычисления, и логика разбиения задачи на куски, которые можно за один раз удержать в памяти со всеми тонкостями.
Возможность сделать большой проект таким образом упирается не во время и усидчивость, а в возможность "не закопаться".


Я для себя делаю из всего этого один, для меня очевидный вывод:
поскольку все выдуманные до сего дня парадигмы языков программирования в какой-то мере "естественны" (возможно, для одного круга задач, тогда как другие - для других), то ИДЕАЛЬНЫЙ ЯЗЫК ПРОГРАММИРОВАНИЯ должен позволять выражать на себе НЕ громоздко, но кратко и изящно, ВСЕ парадигмы, т.е. подходы и логику разбиения для увязки верхнего уровня программирования - при том снабжая программиста лёгкими операторами для конкретных задач (строк, хэшей, стеков, связи с операционкой и т.д.).

Идеальный язык обязан быть "мультипарадигмальным" без вымученности.
linkReply

Comments:
[User Picture]From: thesz
2008-02-19 01:07 pm (UTC)
Вот. Все свелось к тому, что "я уже привык" и "мне так удобней."

А ты (на "вы" было ради прикола) писал программы вдвоем, хотя бы?
(Reply) (Parent) (Thread)
[User Picture]From: grundik
2008-02-19 02:24 pm (UTC)
А к чему ещё может свестись? Языки и парадигмы - они для того, чтобы было удобно решать задачи. По поводу "я привык" - я с 91 года работаю с компьютерами, и только в 2006 начал работать с лиспом и ФП. Потому что анализ показал, что это будет удобно. А раз анализ показал - то в жопу привычки, надо садиться и переучиваться. Если для какой-то задачи окажется, что надо хаскель - ну сяду и буду писать на хаскеле. При этом у меня есть задачи, которые я решаю на PHP, потому что иначе будет хуже (да, это не связано с языком, это связано с людьми, но какая нафиг разница?)

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

Замечу, что проблем с сопряжением кода у меня не было очень давно, даже с PHP. В PHP просто сложнее, потому как нельзя писать что попало, надо думать, КАК записать так, чтобы проблем не было. А в лиспе можно тупо писать то, что думаешь.
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2008-02-19 02:48 pm (UTC)
Что был за анализ? Почему подошел именно Лисп, а не камл?

И что, проблем со стыковкой нет совсем, или уже привыкли их не замечать? Например, никто не возвращает неправильно сформированных данных, никто не модифицирует что-то в процессе своих вычислений?

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

А вот в однопарадигменных языках - из коих только Clean и/или Haskell, - такого нет. Нет такой возможности вообще.
(Reply) (Parent) (Thread)
[User Picture]From: grundik
2008-02-20 05:18 am (UTC)
Лисп - потому что XML и DSL (точнее, DSEL). Не ML (OCaml) потому что в OCaml с DSL не так хорошо, как в lisp-е, плюс lisp-овские sexps можно рассматривать как способ (очень удобный способ) записи XML. Плюс в имеющихся имплементациях OCaml есть проблема с UTF-8 (ну, не проблема - нюанс), lisp-ы с UTF работают лучше. А мне надо, чтобы в регекспах можно было китайские иероглифы использовать.

Ну и чисто субъективно показалось, что в лисп порог вхождения меньше, то есть он проще. Я и сейчас считаю, что лисп проще - в OCaml даже синтаксис (полный) сложнее.

Проблем со стыковкой из-за модификации чего-либо в процессе вычислений - нет. Дисциплина плюс lexical scope.

Проблемы с неправильными данными - есть, когда стыкуются лисповый код и перловый (у меня SOA), например. При стыковке лисповского с лисповским - ну не знаю - в общем, если функция возвращает херню, это будет известно в момент, когда эта функция будет использоваться, а не в момент компиляции - это проблема? Ну пусть даже это проблема - но это не из-за мультипарадигменности. И в хаскеле такого быть не может не из-за того, что он однопарадигменен, а из-за вывода типов. Лисп хоть и динамический, но при этом строго типизированный.
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2008-02-20 08:47 am (UTC)
"Дисциплина плюс lexical scope" и переволится, как "привыкли."

И напомню твое же про "написал 4 строки, а потом 400 строк тестов." Вот и цена динамичности (то есть, отсутствию фиксированной языком парадигмы построения и передачи данных;).
(Reply) (Parent) (Thread)
[User Picture]From: grundik
2008-02-20 09:14 am (UTC)
Про 400 строк - надо генерить XML, такой XML, который понимается другой программой, контроля над которой у меня нет. Как тут поможет хаскель?

Про то, что на хаскеле нельзя написать говнокод - не верю. Говнокод можно написать где угодно. В хаскеле есть свои проблемы, например, наивные функциональные решения явно будут тормозить (потому как получится N^2, если не хуже, и ленивость не спасёт), а это никакой типизацией не словишь. То есть дисциплина всё равно нужна.

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


PS: btw, в хаскеле мемоизация вычисленных функций сделана? где-то читал, что типа в выражении (bar (foo x) (foo x)) параметр (foo x) будет вычисляться два раза, то есть мемоизации нет. Это так, или есть нюансы? Просто интересно, безотностительно темы разговора :)
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2008-02-20 09:53 am (UTC)
В хаскеле есть свои проблемы, например, наивные функциональные решения явно будут тормозить (потому как получится N^2, если не хуже, и ленивость не спасёт), а это никакой типизацией не словишь.

Сьешь свою шляпу, если докажу, что ты неправ? ;)

PS: btw, в хаскеле мемоизация вычисленных функций сделана? где-то читал, что типа в выражении (bar (foo x) (foo x)) параметр (foo x) будет вычисляться два раза, то есть мемоизации нет. Это так, или есть нюансы? Просто интересно, безотностительно темы разговора :)

y = foo x; bar = y y будет мемоизировано. В твоем примере - нет, там действительно есть какие-то нюансы (вроде, как redundant expression elimination для функицональных языков, во-первых, редко срабатывает и, во-вторых, приводит к нарушению порядка вычислений, про это где-то давно читал).
(Reply) (Parent) (Thread)
[User Picture]From: grundik
2008-02-20 10:56 am (UTC)
> Сьешь свою шляпу, если докажу, что ты неправ? ;)

Неправ в чём? В том, что наивные решения == N^2, или в том, что N^2 == тормоза, или в том, что это типизацией не ловится? :)

Шляпу есть не буду, но имхо разговор про вот это вот куда как полезнее, чем спор про мультипарадигменность.
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2008-02-20 11:30 am (UTC)
Я там подчеркнул. В основном, что "это типизацией не словишь."

Той типизацией, что есть в Хаскеле, не словишь. Но можно навесить на уже прошедшую HM типизацию программу еще одну проверку на предмет сложности. Это описывается в статьях, не так давно я про это в блоге говорил.

Ну, и зависимые типы - A Verified Staged Interpreter Is A Staged Complier, http://www.cs.st-andrews.ac.uk/~eb/writings/verified_staged.pdf

Вносишь в интерпретацию подсчет количества выполненных операций, получаешь проверку компилятором сложности вычислений.
(Reply) (Parent) (Thread)
[User Picture]From: grundik
2008-02-20 11:37 am (UTC)
Ммм... Читать внимательно некогда, но если логически подумать, то в случае, когда у меня множество допустимых значений не ограничено, то как можно посчитать количество операций?
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2008-02-20 12:28 pm (UTC)
Для этого есть первый случай, когда система типов говорит, что твоя программа имеет сложность не хуже O(|I|2n), где I - входные данные, а |I| - их "объем."

Ну, что, пересмотришь позиции? ;)
(Reply) (Parent) (Thread)
[User Picture]From: grundik
2008-02-20 02:01 pm (UTC)
Что такое "объём"?

Я пересмотрю позиции, когда увижу своими глазами, что это работает ;)
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2008-02-20 02:13 pm (UTC)
Количество элементов в списке.

Позиция понятна. "За нас должны сделать максимум работы."
(Reply) (Parent) (Thread)
[User Picture]From: grundik
2008-02-20 03:05 pm (UTC)
Такая оценка много пользы не принесёт, I think, хотя хз...

По поводу "за нас должны сделать максимум работы" - ну в принципе я бы может быть и позанимался теорией, но во-первых нет времени, а во-вторых нет необходимой квалификации. Каждому своё.
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2008-02-20 03:20 pm (UTC)
Это был пример. Возьми количество элементов в дереве. Да и какая оценка принесет пользу, если не эта?

Собственно, вот и различие. Тебе надо устаканившееся, пусть даже и с явно видными проблемами.

(А чем же вы там занимаетесь, что времени нет?;)
(Reply) (Parent) (Thread)
[User Picture]From: thesz
2008-02-21 01:21 pm (UTC)
Monads parameterized by time
Another application of number-parameterized types is to enforce timing and protocol-related restrictions. We parameterize the type of the monad with the `time metric' describing the progress of the computation. The time metric could be the number of times a particular device register has been read. We may then enforce that a register be read the same number of times in any control path through the code. Alternatively, the type checker may report the maximum number of register reads -- sort of a worst-time complexity of the code.

http://okmij.org/ftp/Haskell/number-parameterized-types.html
(Reply) (Parent) (Thread)
[User Picture]From: deni_ok
2008-02-20 10:28 am (UTC)
> ... в выражении (bar (foo x) (foo x)) параметр (foo x) будет вычисляться два раза ...

Да, и это верно (хотя это и тонкий момент, нюансы мономорфизма дискутабельны):
bar :: Int -> Float -> (Int, Float)
bar a b = (a, b)

foo :: (Num a) => a -> a
foo = (^2)

test = bar (foo 2) (foo 2)
Запускаем
*Tst> test
(4,4.0)

Так что, если хочешь унификации, не копипасть (foo x) в выражении (bar (foo x) (foo x)), а сделай let-связывание
(let y = foo x in bar y y)
(Reply) (Parent) (Thread)
[User Picture]From: kurilka
2008-02-20 10:31 am (UTC)
"дискутабельны"...
А потом хаскелисты удивляются, что обычные люди их перестают понимать :)
(Reply) (Parent) (Thread)