Подробная трассировка событий токийского финала ACM ICPC: http://aldanur.livejournal.com/266265.html#cutid1

Блог Петра Митричева со свежими впечатлениями от атмосферы соревнований в Токио: http://programmer.livejournal.com/

P.S. На блоге саратовцев указаны и задачи их мини-конкурса, не перепутайте, где что обсуждается.

Дополнительная информация по задачам чемпионата мира ACM ICPC.

Обсуждение их ведется в блоге саратовской команды -- чемпиона 2006 г. См. http://blogs.mail.ru/community/icpc/

Ответ на »сообщение 3279« (AVC)
___________________________

Правильно ли я понял, что в таком виде это какая-то разновидность карринга? В том неформальном смысле, какой придает ему следующая фраза из Википедии:

Насколько я знаю, карринг (currying) -- это просто сведение обработки функции от n-аргументов к конкатенации n-функций от одного аргумента. При этом разбиение на несколько функций происходит так, что функция применяется к ближнему левому аргументу. Принцип принадлежит американскому математику Хаскелю Карри (Haskell Curry), в честь которого язык Haskell и назвали.

А насчет closure давайте заглянем все в ту же Wikipedia:  closure is a semantic concept referring to a function paired with an environment. When called, the function can reference elements of the environment required for the function’s evaluation. Typically, a closure occurs when one function appears entirely within the body of another, and the inner function refers to local variables of the outer function. At runtime, when the outer function executes, a closure is formed, consisting of the inner function’s code and references to any variables of the outer function required by the closure.

Что из этого следует? Closure ("герметик") -- это контекст вызываемой функции, который принадлежит инициатору вызова -- вызывающей функции. Функция может попользовать внешние данные как read-only. Переводя на язык императивщиков, получается, что если программу оформить как "пусковую" функцию (в теле инициализации), из которой потом все и будет вызваться, то ее локальные данные по линии closure всегда будут доступны другим функциям.

Вопрос: а чем это отличается от глобальных данных программы?

Ответ на »сообщение 3278« (Geniepro)
___________________________

Как поётся в Советском Гимне - "Мы старый_мир разрушим до основанья, а затем, мы наш, мы новый_мир построим..."

Ничего себе оговорочки :)

Во-первых, текст звучит как "Весь мир насилья мы разрушим...". Во-вторых, это слова "Интернационала", которые написал легендарный парижский коммунар Эжен Потье (на русский язык переводил студент Парижского горного института Аркадий Коц). Хотя, строго говоря, "Интернационал" был одно время (до новогодней ночи на 1 января 1944 г.) гимном Советского Союза.

Занятно, что Вы вспомнили об этом в такой знаменательный день. Ведь именно 18 марта -- день Парижской Коммуны. Не так давно в ходе одной дискуссии некий "политолог" обмолвился: "Да что там говорить об этих коммунистах! Ведь даже в их гимне поется: "Весь мир насильем мы разрушим!" Бедный Интернационал, как же ему не везет на оговорки!

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

Тьма государственных людей,
Как трутни, грабят улей.
Чиновники любых мастей
Бюджет страны раздули...
Все так же бедняки живут
Под властью Капитала.
Рабочим за тяжелый труд,
Как раньше, платят мало...
Ось этой жизни -- ложь одна.
Чтоб вырваться из ада,
Переменить не имена,
А жизнь по сути надо.

Так ведь никто Вас не заставляет делать closures, изменяя при этом состояние каких-то глобальных переменных.

По-моему вопрос о состоянии -- фундаментальный вопрос, вызывающее очевидное недопонимание. Нельзя ли было бы разобрать его поподробнее?

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

Таким образом, общая схема программы в ФП -- набор трансформаций, обусловленных композицией функций. Так что же есть состояние в ФП и есть ли оно?

Ответ на »сообщение 3275« (Geniepro)
___________________________

Ответ на »сообщение 3270« (Илья Ермаков)
___________________________

Оберон хорош тем, что на нем так написать НЕЛЬЗЯ. Написать глупо, неверно и т.п. - можно. Написать непонятно - нельзя :-)

Ох не уверен! Для меня Ваша программа отнюдь не очевидна. Что бы разобраться в ней - по-любому думать придётся... :о))


Не очевиден алгоритм в целом -- локально все понимается без проблем (почти -- для незнакомых конкретно с КП).
Для локального понимания хаскелевского варианта нужно знать гораздо больше.

Ответ на »сообщение 3278« (Geniepro)
___________________________

новый_мир := программа (старый_мир)

Как поётся в Советском Гимне - "Мы старый_мир разрушим до основанья, а затем, мы наш, мы новый_мир построим..."

Что противоречит фундаментальному принципу управления сложностью DIVIDE ET IMPERA.

Того же порядка крайность, как единая общая память в машине Тьюринга.

Ответ на »сообщение 3279« (AVC)
___________________________

>>>Чистое же ФП заставило бы нас переместить текущее значение x на более высокий уровень.

Это я как-то уж совсем небрежно выразился. :(
Конечно, надо было так:
Чистое же ФП заставило бы нас переместить переменную x на более высокий уровень.

Ответ на »сообщение 3278« (Geniepro)
___________________________

Создание closure-функции - не есть изменение глобальных переменных, это просто создание ещё одного объекта, возможно временного.

Правильно ли я понял, что в таком виде это какая-то разновидность карринга?
В том неформальном смысле, какой придает ему следующая фраза из Википедии:
Intuitively, currying says "if you fix some arguments, you get a function of the remaining arguments".
http://en.wikipedia.org/wiki/Currying
Окружение как бы позволяет фиксировать часть аргументов функции наиболее удобным способом в конкретном контексте.


Эту мысль я не понял... Что значит "состояние имеет тенденцию всплывать на глобальный уровень"?


Я все время ссылаюсь на один и тот же пример: раздел 3.1.2 из книги SICP (которой, благодаря Вам, мне теперь пользоваться гораздо удобнее).


(define rand
  (let ((x random-init))
  (lambda ()
    (set! x (rand-update x))
  x)))

Разумеется, ту же последовательность случайных чисел мы могли бы получить без
использования присваивания, просто напрямую вызывая rand-update. Однако это
означало бы, что всякая часть программы, которая использует случайные числа, должна явно запоминать текущее значение x, чтобы передать его как аргумент rand-update.
Чтобы понять, насколько это было бы неприятно, рассмотрим использование случай-
ных чисел для реализации т. н. моделирования методом Монте-Карло (Monte Carlo
simulation).


Там достаточно подробно разбирается, чем плох в данном случае отказ от присваивания.
Обсуждение ведется при полной ясности, что приведенный кусок исходного кода никоим образом к ФП не относится.
Чистое же ФП заставило бы нас переместить текущее значение x на более высокий уровень.

Ответ на »сообщение 3274« (AVC)
___________________________

Я не вполне понял мысль о closures.
Насколько я понимаю, если у нас есть closures с присваиваниями, то это вряд ли (чистое) ФП.

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

Создание closure-функции - не есть изменение глобальных переменных, это просто создание ещё одного объекта, возможно временного.


Можно ли это понимать так, что в ФП состояние имеет тенденцию всплывать на глобальный уровень?
Ведь "изменяемые" параметры функций откуда-то же приходят...

Эту мысль я не понял... Что значит "состояние имеет тенденцию всплывать на глобальный уровень"?

В конечном счёте на самом глобальном уровне (ввод/вывод данных) мы, естественно, изменяем состояние компьютера и/или нашего представления о компьютере (тут разные мнения, например, у info21 и Владимира Лося).
Если мы пишем фломастером (или принтером) на листке бумаги, то мы изменяем состояние бумаги. Такова природа вещей, что поделать...
Просто современное ФП предлагает создать жёсткие границы для мирового состояния, заключив его в монадный ввод/вывод, который упрощённо можно представить в виде такой формулы:

новый_мир := программа (старый_мир)

Как поётся в Советском Гимне - "Мы старый_мир разрушим до основанья, а затем, мы наш, мы новый_мир построим..."

Ответ на »сообщение 3273« (Сергей Перовский)
___________________________

Как сторонний наблюдатель могу сказать, что читаются оба текста достаточно легко.
Может быть потому, что Geniepro больше уделил внимания комментариям, но это тоже может характеризовать не только программиста, но и выбранный язык.

На самом деле все эти комментарии я проставил не для других людей, которые, возможно, захотят прочесть мой код, а для самого себя - как руководство к действию, описание того, что собственно нужно сделать... (Вот так вот я привык делать постановку задачи...) :о))
Удалять не стал, только подправил в нескольких местах (уже для читателей)...