Archive for Июнь, 2009

Замыкания в Java: что может быть

Как определить – нужна та или иная «фишка» в языке программирования или нет? Можно ли то же самое сделать стандартными средствами, или она настолько необходима, что нужно расширить сам язык новыми конструкциями, тем самим и усложнив его, и упростив?

Появление «настоящих» замыканий в Java может спровоцировать волну новых споров о «чистоте» вроде споров об универсальных типах. Однако здесь снова всё неоднозначно, поскольку замыкания – идея очень простая, однако вместе с тем достаточно мощная.

В этой статье я кратко расскажу о замыканиях для Java, которые, возможно, появятся уже в JDK 7. Скачать текущий прототип для экспериментов вот тут.

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

Так что же такое замыкание? Говоря неформально, это «вложенная» функция, которая содержит ссылки на свободные переменные (локальные переменные внешней функции). Замыкание создаётся каждый раз при выполнении её «внешней» функции. Мы можем выполнять нашу функцию, передавать в другие функции, а так же возвращать из других функций.

Анонимные классы как замыкания

В некотором своём виде замыкания, или лямбда-функции, в Java уже косвенно поддерживаются через внутренние анонимные классы. Это вполне объектно-ориентированное решение.

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

interface I {
    void Block();
}                 

// ...                 

final String msg = "ADA";
new I() {
    public void Block() {
        System.out.println(msg);
    }
}.Block();

Замыкаем map и each с помощью анонимных классов

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

interface OneArgFunc<T> {
    T DoWork(T a);
}                 

// ...                 

public static <T> Iterable<T> map(Iterable<T> A, OneArgFunc<T> m) {
    ArrayList<T> newA = new ArrayList<T>();
    for (T pe : A)
        newA.add( m.DoWork(pe) );
    return newA;
}                 

// ...                 

Iterable<Integer> result = map(mylist,
    new OneArgFunc<Integer>() {
        public Integer DoWork(Integer a) {
            return a*a;
        }
    });

Достаточно много кода ради такой простой задачи. Помимо этого с анонимными типами мы имеем ещё несколько проблем. Например, мы не можем внутри нашего внутреннего класса изменять внешние переменные. Если мы хотим с ними работать, то мы должны объявить их как final. Так, если у нас есть метод each:

public static <T> void each(Iterable<T> A, OneArgFunc<T> m) {     for (T pe : A)         m.Proceed(pe);
}

Мы не можем сделать так:

boolean found = false;
each(mylist, new OneArgFunc<Integer>() {
        public void DoWork(Integer a) {
            if (a == 10)                found = true; // ошибка! flag должен быть final
        }
});

А если мы, например, захотим кинуть исключение из тела нашего «замыкания», то и тут нас подстерегают сложности и много излишнего кода. Компилятор может сгенерировать его автоматически, предоставив нам возможность записывать то, чего мы хотим добиться, другим, более элегантным способом. Плюс ко всему здесь значению ключевых слов this, break, continue и return придаётся не совсем не тот смысл, который мы можем ожидать от замыкания.

Замыкания как замыкания

Введение в язык «настоящих» замыканий призвано сократить количество кода, необходимого для выражения этой идеи. У нас появились новые «функциональные типы». Вот пример:

{int, int => int} sum = {int x, int y => x + y};
sum.invoke(2,3); // -> 5

Если нам необходимо будет кидать исключение из замыкания, то объявить это мы можем следующим образом:

{String => void throws IOException} print = ...

В конечном счёте, для этого генерируются интерфейсы, подобно тому, что мы рассмотрели в предыдущей главе.

Так как замыкания теперь у нас настоящие, мы можем изменять «внешние» переменные.

boolean myflag = false;
{ => void } block = { =>
	myflag = true;
	System.out.println("Hello from closure!");
};
System.out.println(myflag);
block.invoke();
System.out.println(myflag);

Даст следующий вывод:

false
Hello from closure!
true

Замыкаем map и each по-настоящему

Пользуясь новыми возможностями, перепишем нашу функцию map:

public static <T> Iterable<T> map(Iterable<T> a, {T => T} func) {
    ArrayList<T> b = new ArrayList<T>();
    for(T e : a)
        b.add( func.invoke(e) );
    return b;
}

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

Iterable<Integer> result = map(myintlist, {Integer e => e*e} );

Теперь на счёт функции each. Используя следующую версию:

public static <T> void each(Iterable<T> a, {T => void} func) {
    for (T e : a)
        func.invoke(e);
}

Мы можем проделать то, что в прошлый раз не получилось:

boolean found = false;
each(mylist, { int a =>
    if (a == 10) found = true; // всё ОК
});

Ещё пример

Допустим, нам нужно выполнить что-то в отдельном потоке. Мы можем поступить так:

final String message = "hello!";
new Thread(new Runnable() {     public void run() {
	System.out.print(message);
	System.out.printf("We in thread %d\n",              Thread.currentThread().getId());     }
}).start();

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

public static void async(final { => void } block) {
	new Thread( new Runnable() {
		public void run() {
			block.invoke();
		}
	}).start();
}

Так что теперь мы можем писать более лаконично:

String message = "hello!";
async({ =>     System.out.println(message);     System.out.printf("We in thread %d\n",
            Thread.currentThread().getId());
});

Либо вообще так (но у меня следующий вариант не скомпилировался):

String message = "hello!";
async {     System.out.println(message);     System.out.printf("We in thread %d\n",
            Thread.currentThread().getId());
}

Заключение

Думаю, введение замыканий в Java может быть хорошей идеей. Они могут помочь не только в работе с контейнерами и алгоритмами, но и других случаях. Однако мне, разбалованному фишками C# 3.0, кажется, что здесь не хватает ещё вывода типов, методов расширения и прочего «сахара». В документации по замыканиям рассказано о «Control invocation syntax», позволяющему ещё больше упростить синтаксис замыканий (например, не писать круглые скобки или => там где без этого можно обойтись), однако запустить эти примеры у меня не получилось. Видимо, всё это ещё в разработке. Тем не менее, радует, что разработка ведётся, и интересно будет проследить за тем, куда она заведёт :).

Дополнительная информация

Страница проекта – http://www.javac.info

Описание замыканий для Java – http://www.javac.info/closures-v05.html

Блог Zdeněk Troníček, посвящённый замыканиям в Java – http://tronicek.blogspot.com/

Пара видео о замыканиях в Java – тут и тут.

Functional Programming, google, html, Java

Получаем вывод дочернего процесса в Unix

Буквально вчера один человек задал мне вопрос, на который я не смог сходу ответить: как получить вывод дочернего процесса и записать его в строку? Другими словами, необходимо запустить какую-то внешнюю программу, и прочитать её вывод. Всё это должно быть реализовано программно, на Си. Судя по всему, решения могут варьироваться от одной операционной системы к другой, так, я немного повозился с данной задачей. Здесь я покажу, как это можно сделать в Unix при помощи каналов.

Анонимные каналы (anonymous pipes) – один из способов взаимодействия процессов. Мы можем записывать данные в канал на одном конце (в одном процессе), а считывать на другом конце (в другом процессе). Каналы – важная часть Unix-подобных операционных систем, они позволяют организовывать цепочки действий, когда вывод одной программы поступает на вход другой, и так далее.

В Unix shell анонимный канал создаётся при помощи символа прямого слеша |. Например:

$ ps -A | grep init
1 ?        00:00:01 init

Здесь стандартный вывод ps перенаправляется на стандартный ввод grep.

Вернёмся к нашей задаче. Нам нужно запустить дочерний процесс, который запустит внешнюю программу. Это мы проделаем при помощи fork(). По-умолчанию stdout дочернего процесса направлен на экран. Но нам нужно записать эти данные в строковой буфер, чтобы потом как-то с ними работать. Тут нам на помощь и приходят анонимные каналы. Мы создаём такой канал при помощи pipe(), а затем перенаправляем стандартный вывод дочернего процесса в ввод этого канала при помощи dup2(). После этого мы запускаем внешнюю программу при помощи execlp(), и весь её вывод пойдёт не на экран, а в наш канал.

В родительском же процессе мы читаем данные из канала в строковый буфер при помощи read().

Привожу исходный код демонстрационной программы:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>  

#define SIZE 256  

int main (int argc, char *argv[]) {
    int mypipe[2];
    pipe(mypipe);  

    switch(fork()) {
        case -1: /* error */
            perror(”fork”);
            exit(EXIT_FAILURE);
        case 0: /* child process */
            close(mypipe[0]); /* close unused in */
            dup2(mypipe[1], 1); /* stdout to pipe out */
            execlp(”ls”, NULL);
            close(mypipe[1]);
            _exit(EXIT_SUCCESS);
        }  

    /* parent process */
    close(mypipe[1]); /* close unused out */
    char buf[SIZE] = “”;
    read(mypipe[0], buf, SIZE); /* read from pipe in */
    close(mypipe[0]);
    printf(”Child output:\n%s\n”, buf);  

    return EXIT_SUCCESS;
}

Функция pipe(int filedes[2]) создаёт канал и записывает дескрипторы ввода и вывода соответственно в filedes[0] и filedes[1]. 0 – это ввод, 1 – это вывод. Мы используем знание этого при перенаправлении стандартного вывода дочернего процесса в вывод канала при помощи dup2(mypipe[1], 1). В каждом процессе мы сперва закрываем неиспользуемый «конец» канала, а затем работаем с оставшимся.

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

Вывод программы:

$ ./pipestest
Child output:
pipestest
pipestest.c

Исходный текст вы можете загрузить отсюда.

Подробную информацию о используемых функциях вы можете найти в manpages: fork(2), pipe(2), dup(2), exec(3) и т.д.

opera, Programming, Unix, аноним

Бесконечные последовательности в C#

Компьютеры – в общей массе своей, штуки дискретные. Поэтому мы не можем сказать – дайте мне последовательность чисел Фибоначчи, и работать с ней, не указав необходимую её длину. Ну, на самом деле мы можем вычислять эту последовательность динамически, при каждой потребности в следующем элементе (пока у нас хватает памяти), создавая иллюзию бесконечности. В языках программирования такие вещи наиболее элегантно проделываются с помощью ленивых вычислений. Ленивые вычисления означают такие вычисления, которые производятся только тогда, когда в них действительно возникает необходимость, а до этого времени они откладываются, как могут.

На самом деле возможность определять такие ленивые последовательности появилась ещё в С# 2.0 при помощи ключевого слова yield. Мы определяем метод, возвращающий IEnumerable или IEnumerator, а внутри него при необходимости генерации нового элемента этой последовательности вызываем yield return.

Например:

Public static IEnumerable<decimal> Fibonacci
{
    get
    {
            decimal pred = 1;
            decimal curr = 1;

            yield return pred;
            yield return curr;

            while (true)
            {
                var next = pred + curr;
                yield return next;
                pred = curr;
                curr = next;
            }
    }
}

В этом примере каждый новый элемент генерируется при каждом обращении к методу MoveNext() IEnumerator-а данной последовательности. Плюс ко всему, я сделал Fibonacci свойством для красоты. Теперь мы можем сделать следующее:

foreach(var v in Fibonacci)
        Console.WriteLine (v);

На экран будет выводиться последовательность Фибоначчи так долго, пока у вас хватит на это памяти, или не произойдёт переполнение decimal. Однако часто нам не нужны все значения бесконечной последовательности, а только первые несколько. Поэтому полезно будет определить следующий метод расширения, уже с использованием фишек C# 3.0. Конечно, данный метод должен содержаться в каком-то статическом классе.

public static IEnumerable<T> Take<T>(this
            IEnumerable<T> e, int n)
{
    var r = e.GetEnumerator();
    for (int i = 0; i < n; i++)
    {
        r.MoveNext();
        yield return r.Current;
    }
}

И теперь мы можем работать так:

foreach(var k in Fibonacci.Take(10))
     Console.WriteLine(k);

А применяя расширяющие методы из System.Linq.Enumerable, мы можем применять к нашей бесконечной последовательности различные трансформации и ограничения, перед её использованием, например, для вывода только чётных элементов последовательности Фибоначчи можно проделать следующее:

var fib = Fibonacci.Where(x => x % 2 == 0); // бесконечная из чётных чисел Фибоначчи
foreach(var k in fib.Take(10))
    Console.WriteLine(k);

Конечно, всё вышеперечисленное можно было реализовать и по-другому, но в контексте нововведений C# 3.0 конкретно данная реализация может показаться более естественной.

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

CSharp, Functional Programming, Programming, вода