vitaly_kosenko

Редко простые задачки оборачиваются маленькими приключениями, но настройка отладчика RubyOnRails в NetBeans 6.8 как раз из их числа.
Итак, задача: на локальной машине отладить логику RoR приложения, соответствующую url-у www.a.line.ru/site_setup/forum.
Заходим в File → ProjectProperties(...) и видим там поле URL, а прямо под ним замечание в скобках (relative...). Не веря своим глазам, вписываем туда абсолютный адрес и проверяем, что он будет воспринят как относительный, например в нашем случае получится http://localhost:3005/www.a.line.ru/site_setup/forum. Разочаровавшись в NetBeans после пары попыток я пустился в хождения по форумам с целью понять, как избавиться от этого глупого ограничения. Оказалось, что проблему может решить только команда NetBeans, которая уже в курсе и все исправит в новой версии. Не сидеть же сложа руки тем, кому сейчас нужно работать и кого не устраивает один localhost?
Стал просматривать конфигурационные файлы NetBeans и тупо перебирать все пункты меню, чтобы найти хоть какую-то зацепку...И я кое-что нашел!
Во вкладке General пункта Tools → Options есть возможность выбора браузера... Вот если бы был браузер, умеющий подставлять вместо localhost произвольное имя - это бы решило проблему... и почему IE, FireFox и Chrome так делать не научили...
И тут в голове пронеслась мысль: "Ты же программист, возьми и научи". Сел и написал на C#:

using System;
using System.Diagnostics;
using System.Text.RegularExpressions;

namespace browser
{
  class Program
  {
    static void Main(string[] args)
    {
      if (args.Length != 2) return;

      var re = new Regex(@"^(.*?)localhost(.*?)\/([^\/]+)");

      var url = args[0];
      var browser = args[1];

      var m = re.Match(url);

      Func<int,string> f = i => m.Groups[i].Value;

      if (m.Success) url = f(1) + f(3) + f(2);

      Process.Start(
        new ProcessStartInfo(browser, url)
        {
          UseShellExecute = false,
          CreateNoWindow = true
        }
      );
    }
  }
}
Теперь дело за малым:

• добавляем в Tools → Options новоиспеченный браузер с аргументами {URL} iexplore (к примеру)
• в File → ProjectProperties(...) пишем site_setup/forum/www.a.line.ru

 Создатели Haskell понимали, что, даже с учетом всех плюсов функционального программирования, без хорошей поддержки побочных эффектов их язык вряд ли станет популярным, и в качестве решения выбрали монады.
Рассмотрим вычислитель с целыми константами и оператором целочисленного деления

  data Term = Con Int | Div Term Term

  eval :: Term → Int
  eval(Con a) = a
  eval(Div u v) = eval u / eval v

Вопрос: как его модифицировать, чтобы при делении на нуль генерировалось исключение?

Исключение - это побочный эффект, а Haskell - функциональный язык, поэтому ничего похожего на throw new DivException(...) просто так написать не получится.

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

  data M a = Raise Exception | Just a
  type Exception = String

  eval :: Term → M Int
  eval(Con a) = Just a
  eval(Div u v) = case eval u of
    Raise e → Raise e
    Just x →
      case eval v of
        Raise e → Raise e
        Just y →
          if b == 0 then Raise "divide by zero" else Just (x / y)

Все отлично, задача решена, но при такой реализации неудобно добавлять новые операторы - приходится писать одинаковые конструкции:

  eval(Mul u v) = case eval u of
    Raise e → Raise e
    Just x →
      case eval v of
        Raise e → Raise e
        Just y → Just (x * y)

Тут на помощь приходят монады :)

Определим два оператора, один - return, другой - bind

  return :: a → M a
  (>>=) :: M a → ( a → M b ) → M b

  return x  = Just x
  (>>=) m g = case m of
    Raise e → Raise e
    Just x → g x

и перепишем вычислитель

eval(Div u v) = eval u >>= ( \ x → eval v >>= ( \ y → if y==0 then Raise "divide by zero" else Just (x / y) ) )
eval(Mul u v) = eval u >>= ( \ x → eval v >>= ( \ y → Just (x * y) ) )

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

eval(Div u v) = do {
  x ← eval u;
  y ← eval v;
  if y==0 then Raise "divide by zero" else Just (x / y);
}
eval(Mul u v) = do {
  x ← eval u;
  y ← eval v;
  return (x * y)
}

Для того, чтобы и на семантическом уровне не возникало проблем, все монады Haskell должны удовлетворять трем законам:
return не выполняет ни каких вычислений:
  1. m >>= return = m  //правая единица
  2. return x >>= f = f x  //левая единица
результат зависит от последовательности операторов, но не от их группировки
  3. ( m >>= f ) >>= g = m >>= ( \ x → f x >>= g)  //ассоциативность

Литература:

1. Monads for functional programming. Philip Wadler. 1992
2. http://en.wikibooks.org/wiki/Haskell/Understanding_monads

Функциональное программирование:

• программа - λ-терм
• исполнение программы - редукция исходного терма

Если терм удается свести к нормальной форме (нф) из одних констант, вычисления успешны, нф - их результат.

Нф любого терма зависит только от переменных и констант, лежащих в его основе, причем зависимость от переменных легко свести к вертикальной зависимости от констант:

если x - переменная ⇒ ∃ минимальный терм вида t_λ = λ x . ( ... x ... ) и ∃ t_β = t_λ y
  если y - константа
    доказано
  иначе
    y содержит переменные x₁ ... x_N
    x₁ - переменная ⇒ ∃ минимальный терм вида t_λ1 = λ x₁ . ( ... x₁ ... ) и ∃ t_β1 = t_λ1 y₁ и так далее
    ...
высота синтаксического дерева ограничена ⇒ процесс сходится.

Вывод: в функциональных программах нет никаких зависимостей, кроме вертикальных.

Для полноты картины, сделаем одно отступление.

Императивное программирование:

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

Легко показать, что в императивном программировании могут быть не только вертикальные зависимости: пусть S = (define x; s1; s2) - исходная область, s_i - вложены в S. Не исключен сценарий, когда s₁ запишет x, а s₂ его прочитает и вычисления в s₂ окажутся зависимыми от x. Запись в x не является результатом s₁ в классическом смысле, это побочный эффект.

Замечание: от переменных можно абстрагироваться и рассматривать любой ввод/вывод (например работать не с переменной, а с файлом).

Утверждение: В функциональном программировании (чего не скажешь об императивном) нет побочных эффектов.

Что из этого можно извлечь?

Несколько важных плюсов:

1. Отладка осуществляется за один проход вверх по дереву
2. Дерево можно обсчитывать по слоям, вычисляя узлы каждого слоя параллельно
3. Можно не вычислять узлы, не влияющие на конечный результат (агрессивная оптимизация, ленивое вычисление)

При императивном подходе:

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

И только один минус: программирование без ввода/вывода :)

Задача: написать λ-терм для итерационного процесса g(n, f, x)

g(n, f, x) = f ( g(n-1, f, x) )
g(0, f, x) = x

Решение: построим следующую рекурсивную конструкцию

g = λ n f x . zero? n x ( g ( pred n ) f ( f x ) )

Если n=0, результатом будет x, иначе (n>0) вернется g(n-1, f, f(x)). Семантика верная, но из-за явной рекурсии такой терм не свернуть к нормальной форме: получим бесконечное число замен.

Введем терм S = λ M n f x . zero? n x ( M ( pred n ) f ( f x ) ). Очевидно, что g - неподвижная точка S.

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

Y = ( λ x y . y ( x x y ) )( λ x y . y ( x x y ) )

и это легко проверить:

Y M = Z Z M = (λ x y . y ( x x y ) ) Z M = M ( Z Z M ) = M ( Y M )

Всё! Можем писать ответ.

Ответ: g = Y S.

Замечание: Комбинаторы очень важны. Например в типизированном λ-исчислении нет комбинатора Тьюринга (нет нормальной формы и тип для него сразу не строится) и для полноты по Тьюрингу уже требуется дополнительная константа Y_σ - комбинатор неподвижных точек типа σ. Своего рода "внешний" комбинатор :)

Литература:

1. A short introduction to the Lambda Calculus. Achim Jung. 2004

Определение. λ-терм - слово, выводимое в грамматике:

Term =
  Atom | Abstraction | Application

Atom =
  Variable | Constant | ( Term )

Abstraction =
  λ Variable . Term

Application =
  Application Atom | Atom Atom

Variable =
  x | y ...

Constant =
  1 | 2 ... + | - ...

термы вида λ x .( λ y . (...)) часто сокращают до λ x y . (...)

Редукция:

• α-преобразование - переименование параметра абстракции (применяется первой)
• β-редукция - подстановка значения параметра абстракции
• η-редукция - отбрасывание избыточной абстракции

Нередуцируемая форма называется нормальной. Каждый λ-терм имеет не более одной нормальной формы.

Пример:

( ( λ a . ( λ b . + a b ) ( λ a x . * 2 a ) ) 3 ) 4
α=
( ( λ a . ( λ b . + a b ) ( λ c x . * 2 c ) ) 3 ) 4
η=
( ( λ a . ( λ b . + a b ) ( λ c . * 2 c ) ) 3 ) 4
β=
( λ b . + ( λ c . * 2 c ) b ) 3 ) 4
=
( ( λ b с . + * 2 c b ) 3 ) 4
β=
( λ c . + * 2 c 3 ) 4
β=
+ * 2 4 3 = 2*4 + 3 = 11

Теорема (о полноте λ-исчислений по Тьюрингу). Любую вычислимую ƒ : Z* → Z* можно записать как λ-терм и вычислить при помощи правил редукции, если в качестве констант использовать множество Z*∪{pred, succ, zero?}.

zero? 0 x y = x
zero? n x y = y ( n ≠ 0 )

succ 0 = 1
...
succ ( pred x ) = pred ( succ x ) = x

Можно обойтись и без Z*, если принять

0 = λ f x . x
1 = λ f x . f x
2 = λ f x . f ( f x )
...

Литература:

1. A short introduction to the Lambda Calculus. Achim Jung. 2004

Совершенно естественно, что первым языком программирования высокого уровня стал императивный FORTRAN (созданный во второй половине 1950-х годов).

Когда перед вами стоят вычислительные задачи и есть только

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

простейшим способом построения программ является именно императивный

• память отражает текущее состояние вычисления
• каждая следующая команда его изменяет (делает ближе к искомому результату)

(императивность как следствие из определений классического вычислителя).

Совершенно не понятно почему, но примерно в тоже время создатели языка Lisp работали над проблемами динамической типизации, списками, ассоциативными массивами, функциями высоких порядков и автоматической сборкой мусора, взяв за основу лямбда исчисления Чёрча, а не машину Тьюринга.

Большое дело - талантливые люди во главе с настоящим ученым.

Литература:

1. History of Lisp. John McCarthy. 1979
2. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. John McCarthy. 1960
3. LISP 1.5 Programmer's Manual. John McCarthy. 1962