Nikov's blog

Старое, но не стареющее :-)

2009-12-27T11:33:00.000-08:00

Signs

2009-12-26T09:04:00.001-08:00

Знаете, чьи это фотографии?

2009-11-28T06:59:00.000-08:00

Полиномиальная формула простых чисел

2009-11-17T03:32:00.000-08:00

здесь

Теорема Гёделя в полиномиальной форме

2009-11-15T12:21:00.000-08:00

Недоказуемому утверждению, о котором говорит теорема Гёделя о неполноте, можно придать вполне осязаемый арифметический вид. А именно: для каждой непротиворечивой теории T можно указать такое целое значение параметра K, что уравнение не имеет решений в неотрицательных целых числах, но этот факт не может быть доказан в теории T. Более того, для каждой непротиворечивой теории можно найти бесконечное количество таких значений параметра K. Ценой увеличения количества переменных в несколько раз степень этого уравнения может быть понижена до 4. А можно, наоборот, увеличить степень, уменьшив количество переменных до 9. Подробности можно посмотреть в статье Undecidable diophantine equations и книге Юрия Матиясевича "Десятая проблема Гильберта".

Публикация файлов в Интернете

2009-10-22T07:53:00.000-07:00

Вам когда нибудь было нужно опубликовать какой-нибудь документ или архив в интернете, и получить прямую ссылку для его скачивания? Есть несколько сервисов, которые предоставляют такую возможность. Мне приходилось пользоваться hotlinkfiles.com и diino.com. Но первый из них ужасно медленный, а второй, к сожалению, сейчас стал платным. Между тем, есть еще один, очень простой и удобный способ. Идем на сайт nabble.com, регистрируемся, создаем mailing list с любым названием и получаем адрес для отправки сообщений в него. Потом отправляем туда письмо с аттачментом - и в ответ приходит копия этого письма, в котором аттачмент превратился в общедоступную ссылку для его скачивания. Файлы, ставшие ненужными, можно потом удалить вместе с содержащими их сообщениями через веб-интерфейс.

ReSharper 5.0 EAP

2009-10-19T12:08:00.000-07:00

Начался

Visual Studio 2010 Ultimate Beta 2

2009-10-19T12:07:00.000-07:00

Качаем

IntelliJ IDEA Community Edition

2009-10-15T09:35:00.000-07:00

IntelliJ IDEA Community Edition - бесплатно и с открытым исходным кодом.

Software Transactional Memory .NET

2009-10-05T09:26:00.000-07:00

Несколько интересных ссылок:

Software Transactional Memory

STM.NET

STM.NET Team Blog

Контравариантность в Haskell

2009-10-04T06:18:00.000-07:00

Писал на форуме про ко-/контравариантность в Scala, и подумал, что в Haskell тоже есть контравариантность, только относительно наследования между классами типов. Например, так как Ord наследуется от Eq, можно написать:

{-# LANGUAGE RankNTypes #-}

import List;

foo :: Eq a => [a] -> [a]
foo = nub

bar :: Ord b => (forall a. Ord a => [a] -> [a]) -> [b] -> [b]
bar f = sort . f

x :: Ord b => [b] -> [b]
x = bar foo

Пример несколько искусственный, но обратите внимание, как функция foo передается в функцию bar, ожидающую аргумент с более сильным констрейнтом (Ord a), и попробуйте объяснить себе, почему это работает.

Немного об операторе is

2009-10-03T03:45:00.001-07:00

Как известно, оператор is в C# не всегда ведет себя в соответствии со спецификацией языка. Это результат того, что в рантайме работает команда IL isinst, а у нее свои представления относительно того, какие типы являются assignment compatible. Это сознательное решение, которое в команде компилятора приняли для повышения быстродействия. Однако результаты могут быть весьма странными:

using System;

class Program
{
	static void Main()
	{
		object x = new[] { 1 };
		Console.WriteLine(x is DayOfWeek[]); // True
		Console.WriteLine((DayOfWeek[])x); // System.Int32[]

		object y = 1;
		Console.WriteLine(y is DayOfWeek); // False
		Console.WriteLine((DayOfWeek)y); // Monday
		Console.WriteLine((DayOfWeek?)y); // InvalidCastException
	}
}

Проблема и решение

2009-09-16T09:17:00.000-07:00

После убивания зависшей студии из Task Manager'а столкнулся с мистической проблемой с TFS:


Unexpected error encountered. It is recommended that you restart the application as soon as possible.

Error: The specified module could not be found.

File: vsee\internal\inc\vscomptr.inl

С помощью гугла решение нашлось за 15 секунд здесь.

Elevate

2009-09-11T10:12:00.000-07:00

Появилась интересная библиотека для .NET - Elevate, позиционирущаяся как Boost-like расширение для BCL. Помимо многого другого, она будет давать возможность делать pattern matching в таких языках, как C# и VB.NET. Скачивать ее исходники можно с здесь.

Bing vs. Google

2009-06-26T00:43:00.000-07:00

Сейчас заметил, что Google не индексирует страницы обсуждения в Википедии, а Bing индексирует.

Разработчики и Эйнштейн

2009-06-26T00:27:00.000-07:00

Steve McConnell в своей книге "Software Project Survival Guide" пишет:

Software development is process of continuous discovery and invention. The atmosphere most supportive of that process is one that is relaxed and contemplative. Effective software development requires that developers achieve a level of concentration similar to that of a mathematician or physicist. Can you imagine Albert Einstein sitting at his desk while his manager berates him, "Albert, we need that theory of relatively now! Hurry up!" Since software developers (ну, по крайней мере, многие из них) aren’t as smart as Albert Einstein, they need an even more supportive work environment.

Задачки по программированию

2009-06-24T09:52:00.000-07:00

Если кто-то хочет потренироваться в решении задач по программированию повышенной сложности, то вот хороший список (включает некоторые интересные и малоизвестные задачи): http://algolist.manual.ru/olimp. Ну и конечно, немало интересного появляется на http://www.rsdn.ru/forum/etude.

Wolfram|Alpha

2009-06-22T05:57:00.000-07:00

Около месяца назад компания Wolfram Research запустила онлайновый сервис Wolfram|Alpha. Фактически, это огромная база данных из различных областей (туда входит и математика, и физика, и кинематография, и биология, и много что еще), соединенная с движком Wolfram Mathematica для символических вычислений, и модулем по распознаванию запросов на естественном языке (пока только английском). Он довольно хорошо справляется с грамматическими ошибками, опечатками и пропущенными скобками. Умеет догадываться об общем виде последоватьности по ее первым членам, и находить замкнутую форму для действительного числа по его приближенному представлению. Знает множество свойств чисел и геометрических фигур. Примеры запросов, на которые можно получить ответ:

Representations of Pi

1+1/4+1/9+1/16+...

Largest prime number

First prime number greater than 10!

Is E^Pi algebraic?

What is the volume of dodecahedron?

Integer partitions of 20

Permutations of 1,2,3,4

24061467864032622473692149727991

5.56832799683170784528481

15th derivative of arctan

Roots of x^4+a x^3+x+7

Population of Europe

Angles of triangle 5,12,14

Isotopes of iron

Lowest temperature on Earth

Hemoglobin

Number of cells in human body

Number of species

Temperature of Ocean, 300 m depth

127.0.0.1

Intel, AMD

How old was Bill Gates in 2000?

Я разместил их окошко для запросов рядом со своим блогом, так что наслаждайтесь. :)

Парадокс закономерности

2009-04-28T06:53:00.000-07:00

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

Теорема Гёделя для программистов

2009-01-26T06:31:00.000-08:00

Рассмотрим какую-нибудь математическую теорию, имеющую формальный язык для записи высказываний, фиксированный набор аксиом и правил вывода из них. Все теоремы такой теории можно получать чисто алгоритмическим путем, многократно применяя правила вывода к аксиомам и уже выведенным теоремам. Рассматриваемая теория должна иметь достаточно богатый язык, позволяющий формализовать понятие алгоритма и его остановки (таким свойством обладает, например, арифметика Пеано). Обозначим выбранную теорию T. Будем говорить, что теория правдива, если она доказывает только истинные высказывания.

Напишем алгоритм A(F), который принимает высказывание F на формальном языке теории T, перебирает все теоремы этой теории, и останавливается в том и только том случае, если среди них обнаруживается высказывание F (то есть, если высказывание F доказуемо в теории T).

Заметим, что алгоритмы записываются конечными строками в некотором конечном алфавите, поэтому их можно пронумеровать натуральными числами. Напишем алгоритм B(N, X), который принимает натуральное число N (номер некоторого алгоритма), натуральное число X (входные данные для этого алгоритма), формирует высказывание «алгоритм с номером N не остановится, получив на вход X» на формальном языке теории T и вызывает алгоритм A, передав ему это высказывание. Таким образом, B(N, X) остановится в том и только том случае, если высказывание «алгоритм с номером N не остановится, получив на вход X» доказуемо в теории T.

Напишем алгоритм C(N), который вызывает B(N, N). Этот алгоритм остановится в том и только том случае, если высказывание «алгоритм с номером N не остановится, получив на вход N» доказуемо в теории T.

Алгоритму C тоже соответствует некоторый номер K. Напишем алгоритм D, который вызывает C(K).

Запустим алгоритм D. Он остановится в том и только том случае, если в теории T доказуемо, что он не остановится.

Если этот алгоритм в действительности остановится, то теория T не правдива (доказывает ложные утверждения).
Если алгоритм в действительности не остановится, то утверждение «алгоритм D не остановится» истинно, но не доказуемо в теории Т.

До чего техника дошла!

2008-12-19T13:39:00.000-08:00

Вышла Wolfram Research Mathematica 7. Посмотрел презентацию и обзор новой функциональности на их сайте. До чего техника дошла! Казалось, об этом можно только мечтать. Но и стоит эта штуковина тоже прилично: лицензия для нового пользователя около 3000 долларов (для студентов - около 120).

Комментарии к стандарту C#

2008-03-13T01:03:00.000-07:00

В течение последних нескольких месяцев я работал над комментариями и замечаниями к стандарту C# 3.0 (и эта работа все еще продолжается). В общей сложности получилось несколько сотен комментариев. Возможно, несколько десятков из них попадут в следующее (третье) издание книги The C# Programming Language, выпускаемое издательством Addison-Wesley. Если кому-то интересно, я могу выслать по электронной почте полные результаты моей работы.

Выложил комментарии (в виде документа MS Word в zip-архиве) здесь. На всякий случай скажу, что текст на английском.

Dynamic lookup в C#

2008-02-12T02:57:00.000-08:00

В следующией версии C# планируется добавить возможность помечать блоки кода, в которых производится dynamic lookup. При обращении к какому-либо члену объекта в таком блоке, наличие указанного члена будет проверяться не на этапе компиляции, а во время исполнения. Предполагается, что эта возможность облегчит написание кода для взаимодействия с COM (в частности, с Microsoft Office) и динамически типизированными языками (например, IronRuby и IronPython). Более подробно можно почитать об этом на английском языке в этом блоге.

My New Blog in English

2008-02-03T06:47:00.000-08:00

По просьбам моих англоязычных друзей и коллег я начинаю писать заметки на английском. Они будут расположены на отдельной страничке: http://nikov-thoughts.blogspot.com. Обещаю много интересного. Можете оставлять там свои комментарии на английском языке.

Immutable types в C#

2007-11-12T03:55:00.000-08:00

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

Eric Lippert, один из разработчиков C#, пишет на своем блоге: Immutable data structures are the way of the future in C#

Joe Duffy рассуждает о том, как аннотация атрибутами и статический анализ могли бы использоваться для поддержки immutable types

Обзор языка F#

2007-11-08T00:14:00.000-08:00

Сегодня нашел замечательный обзор языка F#. Если кто еще не знает, скажу, что это мультипарадигменный язык программирования из ML-семейства под платформу .NET, поддерживающий и функциональное и объектно-ориентированное программирование.

Почему не удалось реализовать стандарт C# 3.0

2007-11-07T08:44:00.000-08:00

Eric Lippert, один из разработчиков C#, пишет на своем блоге, почему в финальном варианте C# 3.0 не удалось реализовать некоторые сценарии вывода типов, закрепленные в черновике стандарта.

ILX

2007-11-05T23:49:00.000-08:00

Интересную вещь сделали в Microsoft Research: ILX - расширение IL для функциональных языков.

Сравнение языков программирования

2007-11-05T12:51:00.000-08:00

Создал в Википедии статью Сравнение языков программирования. Пожалуйста, исправляйте и дополняйте ее.

Отслеживание развития проекта Nemerle

2007-11-05T08:10:00.000-08:00

Развитие проекта Nemerle (а именно, логи коммитов в репозиторий) можно отследить здесь: http://cia.vc/stats/project/Nemerle. Как видно, проект продолжает жить и развиваться.

Сравнение объектов в .NET

2007-03-10T07:48:00.000-08:00

За последнее время возникло несколько задач, которые заставили меня размышлять о возможных способах сравнения объектов в .NET, и я решил опубликовать часть своих размышлений.

Разумеется, в объектно-ориентированном мире понятие "равные объекты" может иметь различный смысл. В простейшем случае речь идет о ссылочном равенстве, которое проверяется с помощью статического метода object.ReferenceEquals или встроенного в C# оператора == для объектов. Речь может идти и о сравнении "внутренней структуры". Для этой цели многие типы переопределяют виртуальный метод Equals класса System.Object. Существует также удобный статический метод object.Equals с двумя аргументами, который осуществляет проверку в несколько этапов. Сначала он проверяет свои аргументы на ссылочное равенство, возвращая true в случае успеха. Затем, если оба аргумента не равны null, сравнивает их, вызывая экземплярный метод Equals у левого аргумента и возвращая его результат. Наконец, он возвращает false, если только один из аргументов равен null. Таким образом, за выбор алгоритма сравнения в данном случае "отвечает" левый аргумент.

Давайте для начала обсудим вопрос сравнения массивов. Массивы не переопределяют экземплярный метод Equals, поэтому его использование для сравнения массивов даст такой же результат, как и их сравнение на ссылочное равенство. Поэтому мы попробуем написать алгоритм сравнения массивов самостоятельно. В первую очередь нам надо убедиться, что два массива имеют одинаковый тип, что подразумевает, что они имеют одинаковое число измерений (пропустим достаточно тривиальный случай, когда тип массивов известен на этапе компиляции). Затем мы проверим, что массивы имеют одинаковую нижнюю границу и длину по каждому из измерений. И, наконец, мы последовательно сравним их элементы с помощью метода Equals до выявления первого различия. Если различие не выявлено - то массивы равны. Код на C#, реализующий данный алгоритм, может выглядеть так:

public static bool AreEqual(Array x, Array y)
{
    // сравнение на ссылочное равенство
    if (x == y) return true;
    if (x == null || y == null) return false;

    // сравнение по типам
    Type type = x.GetType();
    if (type != y.GetType()) return false;

    // сравнение на общее число элементов
    if (x.Length != y.Length) return false;

    // сравнение нижней границы и
    // длины по каждому из измерений
    for (int i = 0; i < x.Rank; i++)
    {
        if (x.GetLowerBound(i) != y.GetLowerBound(i) ||
            x.GetLength(i) != y.GetLength(i))
            return false;
    }

    // перебор и сравнение элементов
    IEnumerator yEnum = y.GetEnumerator();
    foreach (object e in x)
    {
        yEnum.MoveNext();
        if (!Equals(e, yEnum.Current)) return false;
    }
    return true;
}

Приведенный код содержит некоторые недостатки. Во-первых, он предполагает, что перечислитель, возвращаемый методом GetEnumerator, будет перебирать элементы двух массивов в одном и том же порядке. Хотя исследование кода соответствующих методов показывает, что так оно и есть, надежный код не должен использовать такую недокументированную особенность. Во-вторых, указанный перечислитель для получения элементов массива пользуется методом GetValue, который является не самым быстрым способом доступа к элементам в случае одномерных массивов. И, наконец, приведенный код не учитывает, что элементами массива могут быть указатели, для извлечения которых надо использовать особую технику. Давайте попробуем устранить эти недостатки.

Чтобы не зависеть от недокументированного поведения встроенного перечислителя массивов, нам надо написать алгоритм, который перебирает все возможные комбинации индексов массива некоторым определенным способом. Самый естественный способ такой. Сначала устанавливаем все индексы в наименьшие значения. Затем увеличиваем последний (самый правый) индекс, пока он не превысит наибольшего значения. После этого сбрасываем его, увеличиваем на единицу предпоследний индекс и опять начинаем увеличивать последний. При превышении каким-либо индексом наибольшего значения, мы сбрасываем его, увеличивая на единицу предыдущий индекс. Продолжаем этот процесс, пока количество полученных комбинаций индексов не станет равным количеству элементов массива. На C# этот алгоритм можно записать следующим образом:

static IEnumerable<int[]> GetIndexes(Array x)
{
    int[] indexes = new int[x.Rank];
    for (int i = 0; i < x.Rank; i++)
        indexes[i] = x.GetLowerBound(i);

    for (int j = 0; j < x.Length; j++)
    {
        for (int k = x.Rank - 1; k >= 0; k--)
        {
            if (indexes[k] <= x.GetUpperBound(k)) break;
            indexes[k - 1]++;
            indexes[k] = x.GetLowerBound(k);
        }
        yield return indexes;
        indexes[x.Rank - 1]++;
    }
}

Если вам непонятна конструкция yield return, то рекомендую прочитать эту статью, а еще лучше - спецификацию C# 2.0 Ecma-334.

Давайте теперь попробуем оптимизировать работу алгоритма сравнения для случая одномерных массивов. Известно, что при работе с SZ-массивами (одномерными массивами с нулевой нижней границей) могут применяться специальные инструкции CIL, работающие эффективнее, чем вызовы соответствующих методов класса System.Array. Поэтому имеет смысл написать специальный метод для сравнения таких массивов, получающий их элементы через индексатор. Но так как тип элементов массива неизвестен на этапе компиляции, нам придется воспользоваться механизмом отражения (reflection) для вызова подходящего варианта обобщенного (generic) метода. Если вы мало знакомы с этой техникой, пожалуйста, посмотрите эту страницу в MSDN. Последовательность действий такова:

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

Вот код, реализующий данный алгоритм:

public static bool AreEqual(Array x, Array y)
{
    // ...

    if (x.Rank == 1 && x.GetLowerBound(0) == 0)
    {
        Type eltType = type.GetElementType();
        if (eltType.IsClass)
            return CompareSZArrays((object[]) x, (object[]) y);
        return (bool) GetComparator(eltType).DynamicInvoke(x, y);
    }

    // ...
}

delegate bool F<T>(T[] x, T[] y);

static readonly Type _delegateTypeStub = typeof (F<>);
static readonly MethodInfo _methodStub = new F<int>(CompareSZArrays).Method.GetGenericMethodDefinition();
static readonly Dictionary<Type, Delegate> _cache = new Dictionary<Type, Delegate>();

static Delegate GetComparator(Type elementType)
{
    Delegate comparator;
    lock (_cache)
    {
        if (!_cache.TryGetValue(elementType, out comparator))
        {
            comparator = Delegate.CreateDelegate(
                _delegateTypeStub.MakeGenericType(elementType),
                _methodStub.MakeGenericMethod(elementType));
            _cache.Add(elementType, comparator);
        }
    }
    return comparator;
}

static bool CompareSZArrays<T>(T[] x, T[] y)
{
    for (int i = 0; i < x.Length; i++)
    {
        if (!Equals(x[i], y[i])) return false;
    }
    return true;
}

Обратите внимание, что мы получаем объект MethodInfo не с помощью метода GetMethod, а через "подставной" делегат F<int> - это позволяет не хард-кодить имя метода в строковом литерале и проверять его наличие на этапе компиляции (аналогичного эффекта можно было бы добиться с помощью конструкции infoof, если бы она была в языке). Другой интересный момент - для любого SZ-массива, элементы которого имеют ссылочный тип, мы можем воспользоваться ковариантностью массивов и вызывать один и тот же вариант метода сравнения, не прибегая к отражению. Вообще говоря, использование отражения и динамическое создание делегатов - это довольно медленная техника, но благодаря использованию кэширования и тому факту, что обычно в реальной программе встречается не так много различных типов объектов, мы получим значительный выигрыш.

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

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

Brainbench

2007-03-03T04:50:00.000-08:00

Вчера сдал он-лайн экзамен на Brainbench по C#. Вот результат. Набрал 4.83 баллов из 5 возможных - оказалось, что этот результат лучше, чем у 99% людей, сдававших этот экзамен. Надеялся, что пройду вообще без ошибок, но что-то напутал с сигнатурами методов асинхронного вызова делегатов. Придется подучить...

Look out, generics!

2007-03-02T07:39:00.000-08:00

Давайте рассмотрим следующий код на C#:

public abstract class A<T>
{
  public abstract T Foo(); 
  public class B : A<B> 
  {
    public override B Foo() 
    {
      return null;
    }
  }
}

Заметьте, что класс B наследуется от одного из типов, сконструированных из класса A, в который он же и вложен. При этом класс B еще и используется в качестве типа-аргумента для класса A<B>. Такое наследование вполне допустимо в .NET.

На первый взгляд указанный тип возвращаемого значения в методе B.Foo() может показаться правильным, однако при компиляции этого кода мы получим ошибку:

error CS0508: 'A<T>.B.Foo()': return type must be
'A<T>.B' to match overridden member 'A<A<T>.B>.Foo()'

Действительно, полное имя типа B (точнее, ассоциированного с ним instance-типа) - это A<T>.B. Давайте попробуем подставить это полное имя в наш код.

public abstract class A<T>
{
  public abstract T Foo(); 
  public class B : A<A<T>.B> 
  {
    public override A<T>.B Foo() 
    {
      return null;
    }
  }
}

На сей раз компиляция проходит без ошибок. Однако, пока остается непонятным, почему в первом примере компилятор отказался интерпретировать краткое имя B как A<T>.B при указании типа возвращаемого значения в методе B.Foo(). Для разъяснения этого вопроса давайте проведем маленький эксперимент:

using System;
public abstract class A<T>
{
  public abstract T Foo(); 
  public class B : A<A<T>.B> 
  {
    public override A<T>.B Foo() 
    {
      Console.WriteLine(typeof(B));
      Console.WriteLine(typeof(A<T>.B));
      Console.WriteLine(typeof(A<A<T>.B>.B));
      return null;
    }
  }
}
public class Program
{
  static void Main() 
  {
    new A<int>.B().Foo();
  }
}

Результат:

A`1+B[A`1+B[System.Int32]]
A`1+B[System.Int32]
A`1+B[A`1+B[System.Int32]]

Теперь ситуация становится более-менее понятной. Тип B находится в двояком положении. С одной стороны, он вложен в A<T>, поэтому видит члены внешнего класса, в частности A<T>.B. С другой стороны, тип В является производным от A<A<T>.B>, поэтому он наследует члены базового класса, в частности A<A<T>.B>.B. Очевидно, что типы A<T>.B и A<A<T>.B>.B являются различными, хотя оба имеют краткое имя B. Естественно, что при разрешении краткого имени B в данном случае предпочтение будет отдаваться унаследованному типу A<A<T>.B>.B (см. Ecma-334, 10.8 Namespace and type names).

Сортировка списка с помощью бинарного дерева (Nemerle)

2007-02-24T06:38:00.000-08:00

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

using System.Console;
using Tree;


variant Tree[T] {
  | Nil
  | Node {
      left : Tree[T];
      value : T;
      right : Tree[T];
    }
}


module Program
{
  Main() : void {
    def sort(s, c) {
      def insert(t, e) {
        match(t) {
          | Node(l, v, r) => 
            if(c(e, v) < 0) 
              Node(insert(l, e), v, r)
            else 
              Node(l, v, insert(r, e))
          | Nil => Node(Nil(), e, Nil())
        }
      }
      def to_tree(s, tree = Nil()) {
        match(s) {
          | h :: t => 
              to_tree(t, insert(tree, h))
          | [] => tree
        }
      }
      def to_list(t, s = []) {
        match(t) {
          | Node(l, v, r) => 
              to_list(l) + (v :: to_list(r))
          | Nil => []
        }
      }
      to_list(to_tree(s))
    }
    
    def c = _.CompareTo(_);
    def s = sort([5, 4, 8, 1, 3], c);
    
    WriteLine(s);
  }
}

Идея программы состоит в следующем. Бинарное дерево может быть либо пустым (Tree.Nil), либо состоять из узла (Tree.Node), который имеет левую ветку, элемент и правую ветку. Каждая из веток, в свою очередь, тоже является бинарным деревом. Элементы в левой ветке (если таковые имеются) всегда меньше, чем элемент данного узла, а в правой - больше либо равны ему. При вставке нового элемента в дерево, он сначала сравнивается с элементом в корне, потом "соскальзывает" в соответствующую ветку, и, в конце концов, закрепляется на одном из концов дерева. Таким образом, вставка нового элемента в дерево из N элементов будет занимать в среднем log(N) сравнений. Вначале мы берем пустое бинарное дерево, и поочередно вставляем в него все элементы списка. Поле того, как дерево построено, мы рекурсивно обходим его и собираем элементы в результирующий список, который получается отсортированным.

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

Если вы хотите больше узнать о выводе типов, то вам сюда. Есть вопросы? Задайте их мне или спросите на этом форуме.

Кортежи в Nemerle

2007-02-23T08:04:00.000-08:00

Я продолжаю цикл заметок, посвященных языку Nemerle, который я начал здесь. В Nemerle есть такие удобные типы данных, как кортежи (tuples). Сегодня я решил написать о них. По сути, кортеж - это неименованный тип данных, содержащий несколько безымянных полей, доступных для чтения. Чтобы задать тип кортежа, надо задать типы всех его полей. В Nemerle тип кортежа записывается с использованием звездочки. Например,

// tup имеет тип (int * double * string)
def tup = (1, 2.1, "text");

Заметьте, что я не указал тип переменной tup, компилятор вывел его, зная типы литералов, использованных при конструировании кортежа. Но я мог бы указать его и явно:

def tup : (int * double * string) = (1, 2.1, "text");

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

def (n, x, s) = tup;

Это эквивалентно объявлению трех локальных переменных n, x, s и извлечению в них соответствующих полей кортежа. Типы переменных компилятор, опять-таки, выводит, зная тип переменной tup. Если нам нужно только одно поле из кортежа, мы можем не объявлять лишних переменных, а поставить вместо них специальный символ _.

def (_, x, _) = tup;

В случае несовпадения количества элементов в образце с количеством элементов в кортеже, возникнет ошибка на этапе компиляции. Надо заметить, что деконструирование кортежей - это частный случай более общей техники сопоставления с образцом (pattern matching), а использованные нами выражения (n, x, s) и (_, x, _) - это образцы (patterns). Идея, лежащая в основе их синтаксиса - это то, что образец, служащий для деконструирования определенного значения, выглядит так же, как и выражение, конструирующее это значение. Мы только что убедились в этом на примере кортежей. Однако, сопоставление с образцом - это большая тема, и мы поговорим о ней отдельно как-нибудь потом.

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

// Snippet 1
Foo(1, 2.1, "text");


// Snippet 2
def tup = (1, 2.1, "text");
Foo(tup);

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

Rev[T](s : list[T]) : list[T] {
    def loop(_) {
        | (h :: t, a) => loop(t, h :: a)
        | ([], a) => a
    }
    loop(s, [])
}

В этом примере мы видим более сложный пример сопоставления с образцом. Хотя мы будем говорить о списках в другой раз, могу пояснить, что запись (h :: t) означает список с головой h и хвостом t, а [] - пустой список. Как видите, этот синтаксис тоже может использоваться, как для конструирования списка, так и для деконструирования. Узнать о списках больше можно здесь.

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

def tup = (1, 2.1, "text");
def x = tup[1];

Здесь мы объявили переменную x, которая получает тип double и значение 2.1. Так как элементы кортежа могут иметь разные типы, а тип переменных должен быть выведен во время компиляции, кортежи разрешается индексировать только константными значениями. При этом выход индекса за допустимые пределы будет вызывать ошибку на этапе компиляции.

Внутренне кортежи представляются полиморфными (generic) типами Nemerle.Builtins.Tuple[...], определенными в сборке Nemerle.dll. Вы можете изучить их структуру рефлектором или посмотреть их исходники в репозитории. Каждый из этих типов является производящим для всех кортежей с определенным числом элементов. Например, кортеж (int * double * string) будет представляться типом Nemerle.Builtins.Tuple[int, double, string]. При такой форме внутреннего представления кортежей число производящих типов должно быть ограничено, а следовательно, должно быть ограничено и максимальное количество элементов в кортеже. В текущей версии Nemerle оно равняется 20. Вы могли заметить, что типы с 2 и 3 параметризующими типами являются размерными типами (структурами), а остальные - ссылочными (классами). Это сделано только для целей производительности и не влияет на семантику кортежей. В некоторых случаях, когда временный кортеж используется только внутри одной функции, компилятор может применить оптимизацию и вообще исключить создание временного объекта.

Если вы заинтересовались языком Nemerle, обязательно прочитайте эту статью. Есть вопросы? Задайте их мне или спросите на этом форуме.

Nemerle

2007-02-23T02:16:00.000-08:00

Прошло около месяца, как я познакомился с языком Nemerle. Впечатления потрясающие. Это компилируемый язык со статической типизацией и сборкой мусора, работающий под .NET, с интуитивно понятным C-подобным синтаксисом, полностью поддерживающий объектно-ориентированную парадигму, включая полиморфные типы (generics). Язык довольно легок для изучения для тех, кто переходит на него с C#. Если на нем писать в стиле C#, то он позволяет записать все, что можно было бы записать на C#, но более лаконично и не менее понятно (на самом деле, в текущей версии, некоторые возможности C# недоступны, но я, наверное, напишу об этом отдельно чуть попозже). Существует даже утилита для автоматической конвертации исходников с C# на Nemerle (cs2n.exe).

Но Nemerle предлагает еще целый ряд замечательных возможностей. Это:

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

выведение типов (type inference), гораздо более мощное, чем, например, в C# 3.0. В частности, поддерживается выведение сигнатуры для локальных функций

кортежи (tuples)

вариантные типы (variants)

сопоставление с образцом (pattern matching)

расширения синтаксиса, возможность внедрения DSL-языков в код программы

возможность метапрограммирования (реализованная в виде типо-безопасных макросов). Фактически, многие конструкции языка, которые выглядят как встроенные (например, lock или using), реализованы как макросы, доступные по умолчанию

Наверное, все эти возможности уже присутствовали в том или ином виде в каких-то языках. Однако я еще не встречал их все сразу в одном языке, и с таким интуитивно понятным синтаксисом.

Большим плюсом является то, что компилятор Nemerle полностью написан на управляемом (managed) коде. Более того, его исходники написаны на самом Nemerle, и они являются полностью открытыми. Да, вы можете взять из репозитория исполняемые бинарные файлы компилятора и его исходники, затем скомпилировать полученные исходники этими бинарниками - и вы опять получите полноценные исполняемые бинарные файлы.

Кроме того, компилятор имеет открытый API, который может свободно использоваться макросами, а также инструментами рефакторинга и интеграции с IDE. Например, если вы захотите написать плагин, обеспечивающий интеграцию Nemerle с вашей любимой IDE, вам не нужно будет писать свой парсер языка. Вы можете запросить всю необходимую информацию, например, тип символа на указанной позиции в коде, набор членов для списка завершения (completion list) или сведения о имеющихся в коде ошибках, прямо у компилятора! Также надо заметить, что компилятор создает сборки с помощью стандартного Reflection.Emit.

Существует открытый баг-трекер, куда можно отправлять свои сообщения об ошибках и предложения по улучшению языка. Более того, вы можете получить доступ к репозиторию на запись и сами включиться в разработку! Хотя официального релиза на момент написания этой заметки еще не было (версия языка меньше единицы), язык уже завоевал большую популярность. Уже есть интеграция языка с Visual Studio (точнее, она в процессе разработки, но ей можно пользоваться: отладчик, расцветка кода, отступы, навигация, всплывающая информация об идентификаторах и фоновая подсветка большинства ошибок). Я уверен, что в недалеком будущем появятся инструменты рефакторинга, не уступающие ReSharper'у.

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

На мой скромный взгляд, Nemerle уже полностью готов к тому, чтобы заменить C# в коммерческих проектах. Более того, его использование позволит увеличить производительность труда программиста в разы! Я думаю, что у этого языка очень большое будущее. Я могу откровенно сказать, что я успел полюбить Nemerle, и собираюсь писать о нем здесь в дальнейшем. Для начала я хочу дать ряд полезных ссылок, которыми вы можете воспользоваться, если заинтересуетесь этим языком (а вы должны им заинтересоваться!). Кроме того, я буду рад ответить на любые вопросы, которые у вас могут возникнуть.

Сайт Nemerle (там вы можете найти общую информацию по языку, объяснение его концепций, учебные материалы и многое другое; ниже я привожу несколько ссылок на отдельные страницы сайта)

Спецификация языка (незаконченная)

Контакты с создателями и разработчиками

Страница для скачивания инсталлятора (Внимание! На момент написания этой заметки там лежала очень древняя версия 0.9.3. Вы наверняка захотите после ее установки взять свежие исходники из репозитория и скомпилировать новую версию)

Репозиторий SVN (Если вы мало знакомы с SVN, то вам сюда. Или же вы можете сразу скачать клиент TortoiseSVN здесь, установить его и разобраться по встроенному help'у)

Форум по Nemerle на русском языке

Статьи по Nemerle на русском языке

Конференция по Nemerle на английском языке, где можно встретить создателей языка

Интеграция Nemerle и Visual Studio (статья на русском языке, содержащая ссылки для скачивания. Если вам будет что-то непонятно, или что-то не получится, обязательно спросите на этом форуме)

Баг-трекер (компилятор и интеграция)

Страница в википедии на русском

Страница в википедии на английском

Ну и, конечно же, гугл!