Про хвостовую рекурсию

[semka]

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

(btw, ничему не научили, у нас про рекурсию не рассказывали).

 

Вот какие у тебя претензии к рекурсиям и к хвостовой в частности? Если прямая рекурсия зло (условно, стек там, все дела), то хвостовая-то в нормальный цикл преобразуется, а читать декларативный код всё-равно проще.

[Гость kvas]

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

(btw, ничему не научили, у нас про рекурсию не рассказывали).

А я не удивлён, все нормальные программисты учились не у кого-нибудь, а сами O:)

 

Вот какие у тебя претензии к рекурсиям и к хвостовой в частности? Если прямая рекурсия зло (условно, стек там, все дела), то хвостовая-то в нормальный цикл преобразуется, а читать декларативный код всё-равно проще.

 

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

А жертвовать эффективностью кода для повышения наглядности имеет право программист, если пишет он прогу для показа студентам приёмов программирования, а не для исполнения этой проги на реальном компе. Т.е. я имею право на рекурсию, когда к лекциям готовлюсь, а ты - вообще не имеешь, пока преподавать не пойдёшь O:)

[semka]

Эээ... Я, например, очень много кода пишу на Haskell, Scheme, Erlang. Там вообще нет циклов, потому что циклы недекларативны ниразу и вынуждают использовать б~гомерзкое разрушающее присваивание.

Ну типа i = i + 1.

Просто идеологии разные, на самом деле я очень часто жертвую производительностью в пользу читаемости кода (на php, например). Это жизненно необходимо, правда.

 

Добавлено спустя 4 минуты 53 секунды:

 

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

Отсутствие любых сайд-эффектов, чёткая модульность (Каждая функция детерминирована на 100%).

 

Я на Хаскеле пишу прототипы перед тем, как написать продакшн-код на гадском, мразотном php, просто что бы понять как должен работать алгоритм.

Простенький пример, наколбасил только что, прототип шаблонов с точки зрения кукисов:

type Cookie = (String, String)



templates :: [(Integer, [Cookie])]

templates =  [(1, [("VIS_ID", "f_template"), ("VST_ID", "f_template")])]



getTemplateId  = fst							  

getCookies = snd



template :: Integer -> Maybe [Cookie]

template id  = template' id templates

where

  template' id [] = Nothing

  template' id ((id', cookies):xs) | id == id' = Just cookies

								   | otherwise = template' id xs

 

Разве это не прекрасно? (-:

[Гость mik]

Я на Хаскеле пишу прототипы перед тем, как написать продакшн-код на гадском, мразотном php

 

!!!

 

Ничего чудеснее не слышал в жизни O:)

 

Пару прогревочных кругов на Формуле-1 перед поездкой в маршрутке тоже практикуешь? O:)

[semka]

Эээ. Ну у людей есть "родной язык". На нём всё просто и прозрачно.

Когда возникает какая-то доcтаточно нетривиальная задача, которую нужно реализовать на мразотном похапе, я сначала рисую фаст-прототип, быстро и понятно.

Строк 10-30 кода на хаскеле. Потом обкатываю его минут 30 и начинаю врубаться в то, как же эту фигню сделать лучше. В итоге из 10-30 строк хаскельного кода получается 50 - 100 строк кода мразотного похапе.

 

Мик, только не говори, что ты про быстрое прототипирование не слышал (:

[Гость mik]

Да я же, это, ненастоящий сварщик-та O:)

 

Меня удивляет просто, что есть люди, которые используют хаскелл совместно с пхп. Навскидку, процентов 90 "программистов на php" ни о каком хаскелле даже и не слышали O:)

 

Кста, еще немного про:

http://users.livejournal.com/_adept_/80294.html. Уж очень понравилось O:)

[semka]

Ну, как бы помягче сказать про "90 процентов php программистов". (:

В общем ты понял (:

А адепт он из наших, ага. Он иногда отличные штуки пишет.

[Гость kvas]

Эээ... Я, например, очень много кода пишу на Haskell, Scheme, Erlang. Там вообще нет циклов, потому что циклы недекларативны ниразу и вынуждают использовать б~гомерзкое разрушающее присваивание.

Ну типа i = i + 1.

Это ещё что, я про такие языки слыхал, в них вообще можно написать i+=1 - вот уж мерзость так мерзость! Хуже того, эти языки ещё и студентам преподают...

 

Просто идеологии разные, на самом деле я очень часто жертвую производительностью в пользу читаемости кода (на php, например). Это жизненно необходимо, правда.

 

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

Отсутствие любых сайд-эффектов, чёткая модульность (Каждая функция детерминирована на 100%).

Эм-м-м... Ну, я до сих пор тащусь от TopSpeed-овских компиляторов языка Modula-2, а уж как к ним объектные расширения приделали - это вообще песня! Вообще, когда Ник Йенсен ушёл из Борланд и та стала Инпрайз, вот в ту пору вся гадостность-то и началась в индустрии ПО. Знаешь, почему в мире операционок победу в 90-х одержали ОС-ы от Microsoft а не от IBM? Потому, что в IBM умели писать операционки, а в Microsoft умели их продавать. С языками программирования ситуация та же. Пока мировое компьютерное сообщество как-то не скоординировалось и не создало для себя свободный софт - ситуация была вполне в духе словосочетания "полярный лисиц". Когда низы прочухали, что они уже не хотят, а верхи уже не могут - создалась революционная ситуация на рынке софта: (а, кстати, кого это я сейчас цитировал, не вспомнишь?) в мире языков программирования распространился gnu-тый софт, а среди операционок разнообразие свободных стало и того больше.

 

Я на Хаскеле пишу прототипы перед тем, как написать продакшн-код на гадском, мразотном php, просто что бы понять как должен работать алгоритм.

Простенький пример, наколбасил только что, прототип шаблонов с точки зрения кукисов:

type Cookie = (String, String)



templates :: [(Integer, [Cookie])]

templates =  [(1, [("VIS_ID", "f_template"), ("VST_ID", "f_template")])]



getTemplateId  = fst							  

getCookies = snd



template :: Integer -> Maybe [Cookie]

template id  = template' id templates

where

  template' id [] = Nothing

  template' id ((id', cookies):xs) | id == id' = Just cookies

								   | otherwise = template' id xs

 

Разве это не прекрасно? (-:

Как я уже говорил - это мастдайственно (не то, что ты прототипированием занимешься, а конкретно код этот, и язык на котором он создан), Приятственно веб-приложения создавались прогой Clarion версий выше 3-й, почившей в неравной борьбе с мелкомягким FoxPro.

 

Вот, лет несколько назад накропал я следующую подборочку, описывающую эволюцию компьютерщиков, сам посмотри что тебя ждёт со временем O:) http://berchat.ru/idiliya/

 

Добавлено спустя 14 минут 55 секунд:

 

Ну, как бы помягче сказать про "90 процентов php программистов". (:

В общем ты понял (:

А адепт он из наших, ага. Он иногда отличные штуки пишет.

Эх, горазды мы наезжать на 90% программистов... А если они тебя встретят, бейсбольными битами вооружившись?! O:)

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

[semka]

а, кстати, кого это я сейчас цитировал, не вспомнишь

Это сказал один Гриб.

Я вообще не врубился, как кореллирует хвостовая рекурсия с политической обстановкой на рынке ПО?

Я тебе говорю о абстракциях, а ты мне о компиляторах. Как-то странно (:

Всё, что я пытаюсь до тебя донести --- декларативное программирование объективно более выразительно и гибко чем императивное, правда если продолжать думать о ДП императивами ничего хорошего не будет. Вась, ты же умный, ты же знаешь Lisp, неужто ты будешь утверждать, что Lisp негибок или что-то в этом духе?

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

А теперь представь себе λ-исчисление, а теперь повесь на него чуть-чуть синтаксического сахара и полтонны реализаций самых различных свойств ФП, положи это всё на систему типов Хиндли-Милнера, с автоприведением к наиболее общему типу, но при этом строжайше типизирующую, накрой всё это превосходной реализацией lazy-evaluations, позволяющей совершать хлопки одной ладонью типа реально бесконечных списков.

И ещё монады сверху --- это и есть хаскель. И это самая мощная среда создания хорошо читаемого, самодокументированного декларативного кода из всех, которые я видел.

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

Для обретения просветления: http://ru.wikipedia.org/wiki/Haskell

 

не то, что ты прототипированием занимешься, а конкретно код этот, и язык на котором он создан

Я вообще ещё раз говорю: к веб-приложениям этот код относится так же как к веб-приложениям относится набросок на бумажке. Хаскель это крутое средство создания абстракций любого уровня.

Ну, конечно, лучшие инжинеры Nokia и прочие люди из исследовательских центров все поголовно лохи и лузеры, раз используют этот ужасный хаскель (:

 

Эх, горазды мы наезжать на 90% программистов...

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

[Гость kvas]

Всё' date=' что я пытаюсь до тебя донести --- декларативное программирование объективно более выразительно и гибко чем императивное, правда если продолжать думать о ДП императивами ничего хорошего не будет. Вась, ты же умный, ты же знаешь Lisp, неужто ты будешь утверждать, что Lisp негибок или что-то в этом духе?

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

А теперь представь себе λ-исчисление, а теперь повесь на него чуть-чуть синтаксического сахара и полтонны реализаций самых различных свойств ФП, положи это всё на систему типов Хиндли-Милнера, с автоприведением к наиболее общему типу, но при этом строжайше типизирующую, накрой всё это превосходной реализацией lazy-evaluations, позволяющей совершать хлопки одной ладонью типа реально бесконечных списков.

И ещё монады сверху --- это и есть хаскель. И это самая мощная среда создания хорошо читаемого, самодокументированного декларативного кода из всех, которые я видел.

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

Для обретения просветления: http://ru.wikipedia.org/wiki/Haskell

 

Эх' date=' горазды мы наезжать на 90% программистов...[/quote']

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

Ага, и на вопрос ГАИ-шников "Предъявите ваши документы!" - они отвечают <?php phpinfo() php?> И вообще , работа с битами - это скорее к программистам машины Тьюринга, а не к пыхпыховцам.

[semka]

Вася, ну ты хоть почитай для приличия, haskell --- это строго типизированный язык.

Строже не бывает, почитай про систему типов Хиндли-Милнера. Эти товарищи просто мечтали о строгой типизации λ-исчисления.

 

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

И удобнее ходить всё-таки на хаскеле, а не на пхп, поверь моему программерскому опыту, он хоть и не сильно большой в сравнении с твоим, но достаточно насыщен (;

[Гость kvas]

Вася, ну ты хоть почитай для приличия, haskell --- это строго типизированный язык.

Строже не бывает, почитай про систему типов Хиндли-Милнера. Эти товарищи просто мечтали о строгой типизации λ-исчисления.

 

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

И удобнее ходить всё-таки на хаскеле, а не на пхп, поверь моему программерскому опыту, он хоть и не сильно большой в сравнении с твоим, но достаточно насыщен (;

 

Понимаешь, я программист, а поэтому когда я говорю "строгая типизация", то я имею в виду именно строгую типизацию, то есть ту, в которой я явно задал типы всех переменных и большинства констант, а не "типизацию, приводимую к строгой" посредством той или иной системы типов двух вышеназваных типов (Хиндли и Милнера, если кто не понял моей бриллиантовой шутки юмора). Я согласен, что их система типизации однозначно _приводима_к_строгой (ключевое достоинство - "однозначно"), но самостоятельно строгая и приводимая к строгой - это не одно и то же. Поясню примером: когда-нибудь у тебя будет сын, он будет ходить в школу и получать оценки за своих знания, так вот, если он будет тебе всегда говорить о всех полученых им оценках самостоятельно, то это "честный ребёнок", а если он будет рассказывать про все свои оценки только когда ты сначала насупишься, потом потребуешь дневник, а потом пригрозишь пойти в школу и поговорить с его учителем, то это будет "ребёнок, приводимый к честному", выражаясь в контексте нашей беседы двух уважающих друг-друга коллег, один из которых до сих пор не может понять, что у меня опыта больше O:)

[semka]

Вась, а где написано, что система ХМ именно приводима к строгой? Ты не скомпилируешь программу с ошибками типизации, физически не скомпилируешь.

И, в общем случае, система типов хаскеля более строгая, чем система типов C/C++.

Этот ребёнок не только честно говорит об оценках, он ещё и прогнозы строит на основании свого дневника.

 

Пишем:

type Human   = String			 -- Новый тип Хуман, имеет имя

type Diary   = (Human, Rating)	-- Новый тип Diary, пара (Human, Rating)

type Rating  = Integer



type Son	 = (Human, Diary)	 -- Новый тип Son, Чувак с Дневником

type Teacher = (Human, Rating)	-- Учитель с оценкой на перевес



takeFive :: Son -> Teacher -> Son -- Декларация типа

takeFive (son, _) (tchr, rating) = (son, (tchr, rating))



ivanov :: Teacher				 -- Декларация типа

ivanov = ("Ivanov", 5)



petrov :: Son					-- Декларация типа

petrov = ("Petrov", ("nobody", 0))

 

А теперь запускаем:

*Main> :load "/home/semka/dev/local/prototyping/diary.hs"

[1 of 1] Compiling Main			 ( /home/semka/dev/local/prototyping/diary.hs, interpreted )

Ok, modules loaded: Main.

*Main> takeFive petrov ivanov

("Petrov",("Ivanov",5))

*Main>

Где тут нестрогая типизация?

[latrommi]

о чем говорят эти люди?

[sokol5]

о чем говорят эти люди?

latrommi, о программировании. :D