понедельник, 12 марта 2007 г.

Выходные с Nemerle

Наконец-то дошли руки до популярного ныне в своих кругах языка программирования Nemerle. За развитием этого языка я слежу давно, наблющаю за активным обсуждением этого языка на сайте RSDN. Пробовал писать на этом языке какие-то вещи, но дальше примеров дело не заходило. На сей раз к этому языку меня подтолкнуло любопытство, связанное с парадигомой функционального программирования. Как практику, мне необходимо было выбрать язык программирования для своих экспериментов, а Nemerle изначально был заявлен, как поддерживающий функциональное программирование, да и один из его предков язык ML функционален по определению. Ну и хотелось иметь язык, который нативно впишется в среду .NET. Ну и его "гибридность" теоретически может позволить "быстрый ввод" и легкое "переключение" между парадигмами в зависимости от решаемых задач. Кроме того, система метапрограммирования, реализованная в этом языке, делают его настоящим комбайном, выразительные способности которого ограничиваются исключительно фантазией пишущих на нем. К слову стоит отметить, что большая часть исходников Nemerle написана на самом Nemerle.

Итак, в качестве первого "функционального" примера я решил попробовать реализовать функцию для быстрой сортировки. Этот пример очень показателен для функционального программирования, так как очень здорово иллюстрирует идею о том, что функциональные программы близки внешне к описанию формулы в математической нотации, описывающей результат, чем к пошаговому описанию алгоритма, приводящего к заданному результату в случае императивного программирования. Чтобы проверить эту идею, в принципе, достаточно ознакомится с реализацией этого алгоритма на разных языках в этой статье. Сравните реализацию на С и на Haskell. Впечатляет?
Итак, в общем случае метод сортировки описывается следующей формулой:
   quickSort([]) = []
 qs

Нам ничего не остается, кроме как просто описать эту формулу в несколько иной нотации, а другими словами - реализовать на языке Nemerle:
def qs(l)
{
    match(l)
    {
        | [] => [];
        | x :: xs  => qs( $[ y | y in xs, y < x ] ) + [x] + qs( $[y | y in xs, y >= x] );
    }
}
Неправда ли, очень похоже на исходную формулу?
Ну и пример использования:
System.Console.WriteLine(qs([1, 9, 6, 96, 9, 6, 69, 698, 98, 69, 89, -228, -234, -27, -23, -23, 63407075, 003, 069, 036, 306, 3096]));
Результатом сортировки будет:
[-234, -228, -27, -23, -23, 1, 3, 6, 6, 9, 9, 36, 69, 69, 69, 89, 96, 98, 306, 698, 3096, 63407075]
Ура, первый эксперимент удался! Будем продолжать наши опыты и результат сразу же опубликовывать.
В качестве источника научной информации в данном эксперементе использовался цикл лекций "Основы функционального программирвоания".
Опубликовать

1 комментарий:

  1. В Nemerle есть implicit match , можно писать так:
    def qs(l)
    {
    | [] > []
    | x :: xs => ...
    }

    ОтветитьУдалить