Заметки на полях

Мини-гайд по началам изучения Objective C

2011-09-13T13:49:00.001+04:00

Опять же, собрано для себя.

Введение

Язык Objective C, на первый взгляд, очень простой, чтобы начать программировать – достаточно базового знания Cи и слышать что-нибудь про SmallTalk, где вызов метода – это посылка сообщения.

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

Инструменты

Как это не странно, но каких-либо удобных инструментов под платформу Windows для этого языка ~~не существует~~ не найдено мной, к сожалению.

Поэтому как обычно, пришлось брать стандартный GCC (с поддержкой Objective C) и MakeFile в руки. Для редактирования текстов и исполнения программ, я уже который год подряд использую прекрасный, хоть уже слегка и устаревший редактор Scite.

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

И далее, компилировать GCC с поддержкой Objective-C:

gcc.exe -x objective-c -lobjc -I$(OBJC_INC) -L$(OBJC_LIB) *.m $(OBJC_BASELIBS) -o Main.exe

Синтаксис

Ух, это просто сказка.

По сути, вы можете взять любую Си-программу и откомпилировать её компилятором Objective C. Полная обратная совместимость.

А всё дальнейшее – это расширения.

По сути, их несколько: новые ключевые слова, которые начинаются с символа ‘@’ (коммерческое At), посылка сообщения, обрамляемое квадратными скобками, и всё. Остальное делает рантайм – то есть библиотеки.

Например:

#import <stdio.h>
#import <objc/Object.h>

@interface MyObject : Object
{
    int field;
}

-init;
-(void) Hello: (char*) s;

@end

@implementation MyObject

-init
{
    [super init];

    field = 5;
}

-(void) Hello: (char*) s
{
    printf("%s\n", s);
}

@end

int main(void)
{
    MyObject* myObjectInstance = [[MyObject alloc] init];        
    
    [myObjectInstance Hello: "Hello, World!"];
    
    [myObjectInstance free];
}

Разбираем, по очереди.

#import – замена стандартного, и набившего всем C++-сникам оскомину, #include, – отличие с том, что #import включается ровно один раз при компиляции (да-да, та самая #pragma once).

objc/Object.h – базовый объект для всех объектов языка Objective-C. Он не является обязательным, но управление памятью реализовано в нём.

@interface – первое новое ключевое слово – это объявление нового объекта, содержит во-первых поля объекта (обычная C-структура) и объявления методов объекта в специфическом стиле.

@implementation – реализация объявленных в @interface методов объекта.

И самое интересное – это посылка сообщений.

MyObject * – указатель на объект.

[ObjectInstance Message: Parameter]

Итак, это обычные квадратные скобки, которые обозначают посылку сообщения Message некоторому объекту ObjectInstance. Сообщение может содержать упакованные параметры Parameter.

Суть примерно та же, что и в SmallTalk. Объекту можно посылать любые сообщения, обработаны будут только те, которые явно поддерживает объект.

В моём примере, происходит посылка четырёх сообщений:

1) [MyObject alloc] – посылка сообщения классу MyObject о выделении памяти и создании объекта этого типа.

Примечание: Да, да, посылка сообщения происходит именно классу объектов. Классы объектов – являются самостоятельными объектами и все создаются во время старта приложения. Соответственно, возможно им посылать сообщения, и доступна интроспекция.

2) Возвращаемому результату обработки сообщения (это указатель на созданный объект) посылается сообщение init, которое в языке Objective C является соглашением об инициализации объекта (конструктор в терминах других языков).

3) [myObjectInstance Hello: "Hello, World!"] – посылка сообщения Hello c параметром.

4) [myObjectInstance free] – освобождение памяти, ранее выделенной под объект через cообщение alloc.

Примечание: Строго говоря, вызов free – необязательно приводит к освобождению памяти, в связи с тем, что в Objective C для управления памятью используется подсчёт ссылок, а в некоторых случаях и GC.

Рантайм

Существует два немного различающихся рантайма: входящий в поставку GCC и от Apple. Отличия у них незначительные. Главное различие – это политика именования заголовочных файлов и классов объектов у Apple: везде добавляется префикс NS.

Примечание: NS – это сокращение от названия NextStep, историческое название предшественника сегодняшней MAC OS. Набор библиотек для Objective C под Windows доступен в пакете GNUStep.

Примеры:

GCC: #import <objc/Object.h>

 Apple: #import <Foundation/NSObject.h>

Аналогичный эппловскому набор рантайм-библиотек (в пределах небольших изменений) поставляется с библиотеками GNUStep.

Литература

lyxite: Compile Objective-C Programs Using gcc,
Apple: Learning Objective-C: A Primer,
Wikipedia: Objective-C,
Objective-C Begginer’s Guide

IntelliTrace – новый инструмент для отладки в Visual Studio 2010

2010-02-23T14:08:00.001+03:00

Совсем недавно вышел Release Candidate для Visual Studio 2010. Новая студия стала гораздо стабильнее и быстрее, так что пора уже обращать внимание на её новые возможности, а не только на свеженький WPF-интерфейс.

Около полугода назад я упоминал про новую штуку, которую можно найти в Visual Studio 2010: Historical Debugger. Это имя оказалось внутренним, в релиз-кандидате эта возможность называется уже по-другому: IntelliTrace. По-русски это должно звучать, примерно как, “Умный следопыт”.

Посмотрим на него (на следопыта) вживую!

Введение

Отладка в современных условиях обычно выполняется одним из следующих методов:

Printf-like отладка,

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

Использование интегрированного отладчика,

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

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

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

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

Из огня да в полымя

Начнём с наскоку методом интуитивного изучения. Запускаем Visual Studio 2010 RC и создаём простое консольное приложение. Код минимальный, только для демонстрации.

using System;

namespace Home.Andir.Examples

    class Program

        static void Main(string[] args)

            Console.WriteLine("Hello, IntelliTrace World!");

            Console.ReadKey();

Запускаем. На консоль будет выведено сообщение и программа начнёт ждать нажатия клавиши (Console.ReadKey). Этого вполне достаточно.

Открываем окно “IntelliTrace”, если его ещё не видно: Debug –> Windows –> IntelliTrace Calls.

Всё что нужно далее для активации инструмента написано прямо в этом окне.

Нажимаем кнопку и программа останавливается. Теперь можно увидеть лог событий, которые были записаны IntelliTrace’ом.

В списке событий появилось два события: Beginning of Application и Debugger Break. Ничего примечательного, но для начала сойдёт.

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

Настройки

Для настройки работы IntelliTrace появился целый узел в дереве Options:

IntelliTrace может работать в двух режимах: IntelliTrace events only и IntelliTrace events and call information, которые определяют уровень и количество записываемой информации. Оба режима настраиваются и позволяют определять какие именно события записывать, а какие игнорировать.

Если перейти на подузел настроек IntelliTrace Events, то можно увидеть тот самый список значимых событий, который подготовили в Microsoft:

О! Это уже что-то, давайте добавим к нашему первому примеру запись всех событий Console. Отмечаем галочкой группу Console и запускаем:

Теперь событий стало три. IntelliTrace залогировал событие вывода на консоль и мы можем легко перейти в это место и посмотреть состояние программы в этот момент.

Теперь пора перейти к более сложному примеру.

Пример использования с ASP.Net MVC

Для большего понимания работы инструмента, продемонстрирую запуск IntelliTrace в случае приложения на базе фреймворка ASP.Net MVC 2.

Создаём проект IntelliTrace.AspNetMvc в студии с помощью стандартного шаблона. Настраиваем IntelliTrace на логирование всех событий и информации о вызовах методов. И запускаем. Придётся подождать.

После этого жмём на Break All в инструменте IntelliTrace и смотрим на список залогированных событий:

В этот список попали два вида событий: Исключения (брошенные и пойманные) и события ASP.Net (HTTP-запрос и сохранение состояния).

Так как мы включили логирование ещё и всех вызовов, то сверху окна IntelliTrace появилась возможность переключится на Calls View – список вызовов.

В этом окне пока ничего интересного не видно.

Рассмотрим одно из залогированных событий. Пусть это будет событие ASP.Net: GET ‘/’.

При выборе этого события становится видна дополнительная информация о событии и набор ссылок, которые указывают на связанную с этим событием информацию: залогированные вызовы методов (Calls View), локальные данные (Locals) и стэк вызовов (Call Stack):

IntelliTrace Calls View:

Вот теперь в окне Calls View теперь стало гораздо больше информации: появился контекст события: стало видно какие из записанных событий IntelliTrace предшествовали данному, какие происходили после. В данном окне можно перемещаться по событиям и просматривать связанную с ними информацию.

IntelliTrace Locals:

В окне Locals отображается та информация, которая существенна для данного события: HTTP-метод, который использовался для доступа и Url. Набор этой информации весьма ограничен и определяется настройками этого типа событий IntelliTrace.

IntelliTrace Stack Trace:

Собственно снимок стэка исполнения в данной точке, хорошо известный всем разработчикам под .Net, кто хотя бы раз сталкивался с отладкой своего приложения.

Примечание: Но, честно говоря, информации о конкретном событии в заданной точке IntelliTrace залогировано достаточно мало. Хотелось бы видеть немного больше информации: например состояние HttpContext для данного вызова, данные Htpp-запроса и т.п.

Технические детали

IntelliTrace как и Code Contracts во время своей работы инжектит специальные методы в результирующую сборку (Post Build IL Rewriting).

Примечание: Кодовое имя IntelliTrace, которое довольно часто встречается в реестре и файлах VS 2010: Proteus.

Фактически сам IntelliTrace реализован как отдельный процесс, который запускается отдельно с помощью консольной программы %ProgramFiles%\Microsoft Visual Studio 10.0\Team Tools\TraceDebugger Tools\IntelliTrace.exe. Поэтому во время любого сеанса IntelliTrace этот процесс можно обнаружить у себя в диспетчере задач.

Запускается он обычно где-то так:

"C:\Program Files\Micrsoft Visual Studio 10.0\Team Tools\TraceDebugger Tools\IntelliTrace.EXE" 
    run 
    /n:"intellitrace.console.vshost.exe_00000ba0_01cab4109a27f296" 
    /cp:"C:\Users\Andir\AppData\Local\Microsoft\VisualStudio\10.0\TraceDebugger\Settings\zrnoutrh.ozc" 
    /f:"IntelliTrace.Console.vshost_00000ba0_100223_014433.iTrace"

Параметры: /n – это имя логгера, /cp – это путь до файла с настройками, /f – имя файла, в который будет складываться информация.

Вся информация, которая сохраняется во время сеанса IntelliTrace исполнения программы пишется в специальный файл бинарного формата, который находится в папке %ProgramData%\Microsoft Visual Studio\10.0\TraceDebugging\ и имеет расширение *.iTrace. Visual Studio во время сеанса отладки с использованием IntelliTrace загружает этот файл и использует для навигации по точкам исполнения и загрузки информации записанной в этих точках.

Настройки по умолчанию IntelliTrace находятся в файле: %ProgramFiles%\Microsoft Visual Studio 10.0\Team Tools\TraceDebugger Tools\en\CollectionPlan.xml. К сожалению, Visual Studio напрямую не использует этот файл для настройки IntelliTrace. Перед запуском IntelliTrace.exe студия копирует (сериализует) собственные настройки IntelliTrace в отдельный файл в папке: %LocalAppData%\Microsoft\VisualStudio\10.0\TraceDebugger\Settings\.

Взглянем на файл c настройками поподробнее:

Ничего специфического в этом файле на первый взгляд не видно: здесь просто собраны все те настройки, что видно в диалоге Options –> IntelliTrace и в студии. Но давайте приглядимся к одной немаловажной детали: TracePointProvider и DiagnosticEventSpecification.

Из их названий, собственно, уже понятно, что так скомпонованы провайдер точек, которые будет записывать IntelliTrace. А DiagnosticEventSpecification – определяет спецификацию одной из таких точек. Рассмотрим спецификацию события Console.WriteLine:

<DiagnosticEventSpecification enabled="false">
    <CategoryId>console</CategoryId>
    <SettingsName _locID="settingsName.Console.WriteLine.Object">WriteLine (Object)</SettingsName>
    <SettingsDescription _locID="settingsDescription.Console.WriteLine.Object">Console Output with an Object passed in.</SettingsDescription>
    <Bindings>
        <Binding>
            <ModuleSpecificationId>mscorlib</ModuleSpecificationId>
            <TypeName>System.Console</TypeName>
            <MethodName>WriteLine</MethodName>
            <MethodId>System.Console.WriteLine(System.Object):System.Void</MethodId>
            <ProgrammableDataQuery>
                <ModuleName>Microsoft.VisualStudio.DefaultDataQueries.dll</ModuleName>
                <TypeName>Microsoft.VisualStudio.DataQueries.Console.Output.WriteLineDataQuery</TypeName>
            </ProgrammableDataQuery>
        </Binding>
    </Bindings>
</DiagnosticEventSpecification>

Итак, первое что мы видим - это набор настроек точки: категория, название, описание. Второе – это некоторые Bindings, которые очевидно и связывают точку и те данные, которые записываются в этой точке.

Для события Console.WriteLine существует всего один биндинг, который определяет метод System.Console.WriteLine с двумя аргументами. ModuleSpecificationId – это сборка, в которой находится искомый метод, TypeName – имя типа, MethodName – имя метода и MethodId – это искомая перегрузка данного метода.

И последнее что мы видим – это некоторый ProgrammableDataQuery – который по сути является основой для IntelliTrace в получении информации о событии в точке записи.

Воспользовавшись рефлектором можно обнаружить, что ProgrammableDataQuery – это управляемый класс (в вышеприведённом примере это Microsoft.VisualStudio.DataQueries.Console.Output.WriteLineDataQuery), который отнаследован от интерфейса IProgrammableDataQuery:

public interface IProgrammableDataQuery

    // Methods

    object[] EntryQuery(object thisArg, object[] args);

    object[] ExitQuery(object returnValue);

    List<CollectedValueTuple> FormatCollectedValues(object[] results);

    string FormatLongDescription(object[] results);

    string FormatShortDescription(object[] results);

    List<Location> GetAlternateLocations(object[] results);

Гораздо чаще, чем ProgrammableDataQuery, в CollectionPlan.xml используется DataQuery. Судя по всему – это стандартная реализация, которая автоматически получает данные от текущего класса (очень похоже на Reflection). В параметрах задаётся путь к определённой внутренней переменной класса:

<DiagnosticEventSpecification>
    <CategoryId>system.data</CategoryId>
    <SettingsName _locID="settingsName.OdbcCommand.ExecuteReader">ExecuteReader (ODBCCommand)</SettingsName>
    <SettingsDescription _locID="settingsDescription.OdbcCommand.ExecuteReader">Command text was executed, building an OdbcDataReader using one of the CommandBehavior values. (just test)</SettingsDescription>
    <Bindings>
        <Binding>
            <ModuleSpecificationId>system.data</ModuleSpecificationId>
            <TypeName>System.Data.Odbc.OdbcCommand</TypeName>
            <MethodName>ExecuteReader</MethodName>
            <MethodId>System.Data.Odbc.OdbcCommand.ExecuteReader(System.Data.CommandBehavior):System.Data.Odbc.OdbcDataReader</MethodId>
            <ShortDescription _locID="shortDescription.OdbcCommand.ExecuteReader">Execute Reader "{0}"</ShortDescription>
            <LongDescription _locID="longDescription.OdbcCommand.ExecuteReader">The command text "{0}" was executed on connection "{1}", building an OdbcDataReader using one of the CommandBehavior values.</LongDescription>
            <DataQueries>
                <DataQuery index="0" maxSize="4096" type="String" name="Command Text" _locID="dataquery.OdbcCommand.ExecuteReader.CommandText" _locAttrData="name" query="_commandText"></DataQuery>
                <DataQuery index="0" maxSize="256" type="String" name="Connection String" _locID="dataquery.OdbcCommand.ExecuteReader.ConnectionString" _locAttrData="name" query="_connection._userConnectionOptions._usersConnectionString"></DataQuery>
            </DataQueries>
        </Binding>
    </Bindings>
</DiagnosticEventSpecification>

Как видно, в данном случае, с помощью запросов получают из параметра с индексом 0 (это this) строку соединения (Connection String) и команду SQL (Command Text).

Судя по файлу CollectionPlan.xml, механизм IntelliTrace представляет собой хорошо расширяемую платформу. Но пока Visual Studio не предоставляет никаких механизмов для добавления, например, своих событий для записи. Единственное, что возможно – это создавать свои собственные iTrace файлы для определённой конфигурации CollectionPlan. Полагаю, что это задел на будущее для каких-то новых инструментов, например Code Coverage.

Заключение

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

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

Литература для дальнейшего изучения

MSDN, Debugging With IntelliTrace,
Ian Huf blog: IntelliTrace Info,
John Robbins blog*: VS 2010 Beta 2 IntelliTrace In-Depth First Look,
John Robbins blog: How Does VS2010 Historical Debugging Work?,
Habib Heydarian blog: Coverage of the Visual Studio 2010 Historical Debugger,
Ian Huf blog: IntelliTrace and CollectionPlan.xml

* – John Robbins, Джон Роббинс – автор известной книги “Отладка приложений для Microsoft .NET и Microsoft Windows”.

Пример декларативного биндинга asp:TreeView

2009-09-13T14:49:00.001+04:00

Рассмотрим пример биндинга asp:TreeView к XmlDataSource.

<%@ Page

    Language="C#"

    MasterPageFile="~/Shared/Site.Master"

    AutoEventWireup="true"

    CodeBehind="TreeView.aspx.cs"

    Inherits="Home.Andir.Examples.TreeViewPage"

%>

<asp:Content ContentPlaceHolderID="BodyPlaceHolder" runat="server">

    <asp:TreeView ID="treeView" runat="server"

        DataSourceID="xmlDataSource">

        <DataBindings>

            <asp:TreeNodeBinding TextField="Name" />

        </DataBindings>

    </asp:TreeView>

    <asp:XmlDataSource ID="xmlDataSource" runat="server">

        <Data>

            <Root Name="Root">

                <Node Name="Node 1" />

                <Node Name="Node 2" />

                <Node Name="Node 3">

                    <Node Name="Node 3.1" />

                </Node>

            </Root>

        </Data>

    </asp:XmlDataSource>

</asp:Content>

И результат:

Как видим, биндинг вполне прямолинейный и полностью декларативный, XML-данные можно хранить прямо в разметке или подгружать из внешнего файла (с помощью свойства DataFile), мало того, XML можно перед биндингом трансформировать с помощью XSLT (с помощью свойства Transform).

Пример биндинга к RSS

Необходимость писать дополнительный код появляется только если требуется получать XML от какого-то внешнего источника. Например, строить по данным из БД или получать RSS-фид из интернета.

<%@ Page

    Language="C#"

    MasterPageFile="~/Shared/Site.Master"

    AutoEventWireup="true"

    CodeBehind="TreeView.aspx.cs"

    Inherits="Home.Andir.Examples.TreeViewPage"

%>

<asp:Content ContentPlaceHolderID="BodyPlaceHolder" runat="server">

    <asp:TreeView ID="treeView" runat="server"

        DataSourceID="feedDataSource">

        <DataBindings>

            <asp:TreeNodeBinding

                DataMember="feed"

                FormatString="Блог: {0}"

                TextField="title"

/>

            <asp:TreeNodeBinding

                DataMember="entry"

                FormatString="Запись: {0}"

                TextField="title"

                NavigateUrlField="url" />

        </DataBindings>

    </asp:TreeView>

    <asp:XmlDataSource ID="feedDataSource" runat="server">

        <Transform>

            <?xml version="1.0" encoding="utf-8"?>

            <xsl:stylesheet version="1.0"

                xmlns:xsl="http://www.w3.org/1999/XSL/Transform"

                xmlns:atom="http://www.w3.org/2005/Atom"

                exclude-result-prefixes="atom"

                <xsl:template match="atom:feed">

                    <feed title="{atom:title}">

                        <xsl:apply-templates />

                    </feed>

                </xsl:template>

                <xsl:template match="atom:entry">

                    <entry

                        title="{atom:title}"

                        url="{atom:link[@rel='alternate']/@href}">

                        <xsl:apply-templates />

                    </entry>

                </xsl:template>

            </xsl:stylesheet>

        </Transform>

    </asp:XmlDataSource>

</asp:Content>

и немного кода:

using System;

using System.Net;

using System.Text;

namespace Home.Andir.Examples

    public partial class TreeViewPage : System.Web.UI.Page

        protected void Page_Load(object sender, EventArgs e)

            var rssFeedUrl =

                "http://feeds2.feedburner.com/AndirNotes";

            feedDataSource.Data =

                DownloadRssFeed(rssFeedUrl);

        private static string DownloadRssFeed(string url)

            var client = new WebClient();

            var resultBytes = client.DownloadData(url);

            return Encoding.UTF8.GetString(resultBytes);

Результатом будет следующее дерево:

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

Реализация обобщённого варианта IHierarchicalDataSource

2009-09-13T14:30:00.001+04:00

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

В стандартной поставке ASP.Net есть два основных контрола, которые поддерживают отображение иерархических данных: asp:TreeView и asp:Menu. Кроме того, они также поддерживают биндинг с иерархическим источником данных, т.е. с таким источником, который реализует интерфейс IHierarchicalDataSource.

Источников, которые реализуют интерфейс IHierarchicalDataSource, существует всего два, это: XmlDataSource и SiteMapDataSource. Кроме того, эти источники одновременно являются декларативными элементами UI, которые можно использовать в разметке.

Например:

XmlDataSource.aspx

<%@ Page

    Language="C#"

    MasterPageFile="~/Shared/Site.Master"

    AutoEventWireup="true" %>

<asp:Content ContentPlaceHolderID="BodyPlaceHolder" runat="server">

    <asp:TreeView ID="treeView" runat="server"

        DataSourceID="xmlDataSource">

        <DataBindings>

            <asp:TreeNodeBinding

                DataMember="Root"

                Text="Root"

/>

            <asp:TreeNodeBinding

                DataMember="Node"

                TextField="Name" />

        </DataBindings>

    </asp:TreeView>

    <asp:XmlDataSource ID="xmlDataSource" runat="server">

        <Data>

            <Root>

                <Node Name="Node 1" />

                <Node Name="Node 2">

                    <Node Name="Node 2.1" />

                    <Node Name="Node 2.2" />

                </Node>

                <Node Name="Node 1" />

            </Root>

        </Data>

    </asp:XmlDataSource>

</asp:Content>

Примечание: Более подробный пример использования биндинга asp:TreeView к XmlDataSource можно посмотреть в следующей заметке.

А что, если требуется отобразить данные полученные из базы данных? Для этого придётся самостоятельно реализовывать указанный интерфейс IHierarchicalDataSource.

Модель

Рассмотрим типичную модель древовидных данных хранимых в БД:

Как видно на скриншоте, модель представляет собой таблицу со следующими полями: ID – уникальный идентификатор записи, ParentID – ключ для связи с родительской записью или NULL – если запись является корневой.

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

Первая – это прямолинейная проекция структуры БД на объект:

Второй вариант обычно возникает при использовании продвинутых средств отображения (ORM):

В данном случае, видим что вместо одного поля ParentID создано два дополнительных поля: Parent и Children. Parent – это ссылка на родительский элемент ORMTreeModel, а Children – перебираемая последовательность дочерних объектов ORMTreeModel.

Представим себе, что нам требуется отобразить данные смоделированные подобным образом в контроле asp:TreeView. Для этого потребуется реализовать интерфейс IHierarchicalDataSource.

Реализация интерфейса IHierarchicalDataSource

Любая реализация IHierarchicalDataSource напрямую связана с реализацией абстрактного класса HierarchicalDataSourceView и интерфейсов IHierarchicalEnumerable и IHierarchyData.

Вот как это выглядит в виде диаграммы классов:

Центральным звеном реализации является IHierarchyData, который и абстрагирует модель древовидных данных.

Примечание: На скриншоте есть одна известная ошибка диаграммы классов генерируемой Visual Studio. Дизайнер диаграмм показывает поля с именем Item переименованными в this. Что хорошо видно в интерфейсе IHierarchyData. В данном случае, это конечно же неверно.

Примечание: Также обратите внимание, что интерфейс IHierarchyData во многом повторяет класс ORMTreeModel приведённый выше.

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

Типизированные обёртки для базовых интерфейсов

Для начала, сделаем некоторые приготовления и реализуем типизированные версии интерфейсов IHierarchyData и IHierarchyEnumerable:

HierarchyData.cs

using System.Web.UI;

namespace Home.Andir.Examples

    public abstract class HierarchyData<T> : IHierarchyData

        public abstract HierarchyData<T> GetParent();

        public abstract HierarchicalEnumerable<T> GetChildren();

        public abstract T Item { get; }

        #region IHierarchyData Members

        IHierarchyData IHierarchyData.GetParent()

            return GetParent();

        public abstract bool HasChildren { get; }

        IHierarchicalEnumerable IHierarchyData.GetChildren()

            return GetChildren();

        object IHierarchyData.Item

            get { return Item; }

        public abstract string Path { get; }

        public abstract string Type { get; }

        #endregion

HierarchyEnumerable.cs

using System.Collections;

using System.Web.UI;

namespace Home.Andir.Examples

    public abstract class HierarchicalEnumerable<T>

        : IHierarchicalEnumerable

        public abstract HierarchyData<T> GetHierarchyData(

            T enumeratedItem);

        #region IHierarchicalEnumerable Members

        IHierarchyData IHierarchicalEnumerable.GetHierarchyData(

            object enumeratedItem)

            return GetHierarchyData((T)enumeratedItem);

        #endregion

        #region IEnumerable Members

        public abstract IEnumerator GetEnumerator();

        #endregion

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

Репозиторий

Определим интерфейс для обобщённого хранилища объектов, из которого мы будем получать данные для иерархического обхода:

IHierarchyDataRepository.cs

        using System.Collections.Generic;

        namespace Home.Andir.Examples

        {

            public interface IHierarchyDataRepository<T> 

                where T : class

            {

                T GetParent(T item);

                IEnumerable<T> GetChildren(T item);

                string GetItemType(T item);

                T GetItem(string hierarchyPath);

                string GetItemHierarchyPath(

                    string parentHierarchyPath, T item);

            }

        }

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

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

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

GenericHierarchicalDataSource.cs

using System;

using System.Web.UI;

namespace Home.Andir.Examples

    public sealed class GenericHierarchicalDataSource<T>

        : IHierarchicalDataSource

        where T : class

        readonly IHierarchyDataRepository<T> repository;

        public GenericHierarchicalDataSource(

            IHierarchyDataRepository<T> repository)

            this.repository = repository;

        #region IHierarchicalDataSource Members

        public event EventHandler DataSourceChanged;

        public HierarchicalDataSourceView GetHierarchicalView(

            string viewPath)

            return new GenericHierarchicalDataSourceView<T>(

                repository, viewPath);

        #endregion

Итак, сам IHierarchicalDataSource довольно примитивен: принимает в качестве параметров репозиторий и передаёт его дальше – реализации абстрактного HierarchicalDataSourceView.

GenericHierarchicalDataSourceView.cs

    using System.Web.UI;

    namespace Home.Andir.Examples

    {

        public sealed class GenericHierarchicalDataSourceView<T> 

            : HierarchicalDataSourceView 

            where T : class

        {

            readonly IHierarchyDataRepository<T> repository;

            readonly string viewPath;

            public GenericHierarchicalDataSourceView(

                IHierarchyDataRepository<T> repository, string viewPath)

            {

                this.repository = repository;

                this.viewPath = viewPath;

            }

            public override IHierarchicalEnumerable Select()

            {

                if (!string.IsNullOrEmpty(viewPath))

                {

                    var hierarchyItem = new GenericHierarchyData<T>(

                        repository, viewPath);

                    return hierarchyItem.GetChildren();

                }

                return new GenericHierarchicalEnumerable<T>(

                    repository, null, repository.GetChildren(null));

            }

        }

    }

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

В остальном реализация GenericDataSourceView также не представляет интереса, всё передаётся на откуп двум оставшимся интерфейсам.

GenericHierarchicalEnumerable.cs

    using System.Collections;

    using System.Collections.Generic;

    namespace Home.Andir.Examples

    {

        public sealed class GenericHierarchicalEnumerable<T>

            : HierarchicalEnumerable<T> 

            where T : class

        {

            readonly IHierarchyDataRepository<T> repository;

            readonly HierarchyData<T> parent;

            readonly IEnumerable<T> enumerableList;

            public GenericHierarchicalEnumerable(

                IHierarchyDataRepository<T> repository,

                HierarchyData<T> parent,

                IEnumerable<T> enumerableList

                )

            {

                this.repository = repository;

                this.parent = parent;

                this.enumerableList = enumerableList;

            }

            #region IHierarchicalEnumerable Members

            public override HierarchyData<T> GetHierarchyData(T item)

            {

                return new GenericHierarchyData<T>(

                    repository, parent, item);

            }

            #endregion

            #region IEnumerable Members

            public override IEnumerator GetEnumerator()

            {

                return enumerableList.GetEnumerator();

            }

            #endregion

        }

    }

Этот интерфейс представляет собой расширение абстракции IEnumerable – перечислимых данных – до абстракции перечисление дерева с возможностью продвижения от некоторого корневого элемента дерева до его листьев.

IHierarchicalEnumerable отличается от обычного IEnumerable только дополнительным методом GetHierarchyData, который предназначен для конвертации перебираемых элементов в реализацию иерархической модели HierarchyData.

GenericHierarchyData.cs

    using System.Collections.Generic;

    using System.Linq;

    namespace Home.Andir.Examples

    {

        public sealed class GenericHierarchyData<T> 

            : HierarchyData<T> 

            where T : class

        {

            readonly IHierarchyDataRepository<T> repository;

            readonly T item;

            readonly HierarchyData<T> parent;

            readonly IList<T> children;

            readonly string path;

            readonly string type;

            public GenericHierarchyData(

                IHierarchyDataRepository<T> repository,

                string itemPath)

            {

                this.repository = repository;

                this.item = repository.GetItem(itemPath);

                this.parent = null;

                this.children = repository.GetChildren(item).ToList();

                this.path = itemPath;

                this.type = repository.GetItemType(item);

            }

            public GenericHierarchyData(

                IHierarchyDataRepository<T> repository,

                HierarchyData<T> parent,

                T item

                )

            {

                this.repository = repository;

                this.item = item;

                this.parent = parent;

                this.children = repository.GetChildren(item).ToList();

                this.path = repository.GetItemHierarchyPath(

                    parent == null ? "" : parent.Path, item);

                this.type = repository.GetItemType(item);

            }

            #region IHierarchyData Members

            public override HierarchyData<T> GetParent()

            {

                return parent;

            }

            public override bool HasChildren

            {

                get { return children.Count > 0; }

            }

            public override HierarchicalEnumerable<T> GetChildren()

            {

                return new GenericHierarchicalEnumerable<T>(

                    repository, this, children

                    );

            }

            public override T Item { get { return item; } }

            public override string Path { get { return path; } }

            public override string Type { get { return type; } }

            #endregion

        }

    }

В реализации IHierarchyData фактически выполняется конечное извлечение данных из нашей абстракции репозитория иерархических данных.

Используется два конструктора: первый предназначен для создания объекта от некоторого начального пути itemPath в дереве, второй создаёт текущий объект обхода.

А теперь самое интересное, необходимо реализовать некоторый конечный репозиторий иерархических данных.

Реализация IHierarchyDataRepository

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

Вспоминаем наши первоначальные модели древовидных данных PlainTreeModel и ORMTreeModel.

Для первой модели, интерфейс должен выглядеть примерно так:

IPlaneTreeModelRepository.cs

using System.Collections.Generic;

namespace Home.Andir.Examples

    public interface IPlainTreeModelRepository<T>

        IEnumerable<T> GetRoots();

        IEnumerable<T> GetItems(int parentID);

        T GetItem(int id);

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

Примечание: В качестве основных полей объекта предполагается существование полей "ID" и "ParentID", если их в объекте не окажется, то возникнет ошибка времени выполнения.

PlainTreeModelRepository.cs

    using System;

    using System.Collections.Generic;

    namespace Home.Andir.Examples

    {

        public class PlainTreeModelRepository<T>

            : IHierarchyDataRepository<T> 

            where T : class

        {

            readonly Func<IEnumerable<T>> getRootsImpl;

            readonly Func<int, IEnumerable<T>> getItemsById;

            readonly Func<int, T> getItemByIdImpl;

            public PlainTreeModelRepository(

                IPlainTreeModelRepository<T> repository)

                :this(repository.GetRoots, repository.GetItems, repository.GetItem)

            { }

            public PlainTreeModelRepository(

                Func<IEnumerable<T>> getRootsImpl,

                Func<int, IEnumerable<T>> getItemsById,

                Func<int, T> getItemByIdImpl)

            {

                this.getRootsImpl = getRootsImpl;

                this.getItemsById = getItemsById;

                this.getItemByIdImpl = getItemByIdImpl;

            }

            public T GetItem(string path)

            {

                var pathItems = path.Split('/');

                if (pathItems.Length > 0)

                {

                    int itemID = int.Parse(

                        pathItems[pathItems.Length - 1]);

                    return getItemByIdImpl(itemID);

                }

                return null;

            }

            public IEnumerable<T> GetChildren(T item)

            {

                if (item == null)

                    return getRootsImpl();

                return getItemsById(

                    item.GetProperty<int>("ID")

                    );

            }

            public T GetParent(T item)

            {

                if (item == null)

                    throw new ArgumentNullException("item");

                var parentID = item.GetProperty<int>("ParentID");

                return getItemByIdImpl(parentID);

            }

            public string GetItemHierarchyPath(

                string parentHierarchyPath, T item)

            {

                if (parentHierarchyPath == null)

                    throw new ArgumentNullException("parentHierarchyPath");

                if (item == null)

                    throw new ArgumentNullException("item");

                return string.Format("{0}/{1}",

                    parentHierarchyPath,

                    item.GetProperty<int>("ID"));

            }

            public string GetItemType(T item)

            {

                if (item == null)

                    throw new ArgumentNullException("item");

                return typeof(T).ToString();

            }

        }

    }

Для составления пути внутри иерархической структуры используется нотация в виде /RootID/…/ParentID/ItemID/ChildID. В качестве типа объектов используется CLR-тип этого объекта.

Поля объектов извлекаются с помощью рефлексии (точнее TypeDescriptor'а) и следующего хелпера:

TypeDescriptorExtensions.cs

using System;

using System.ComponentModel;

namespace Home.Andir.Examples

    public static class TypeDescriptorExtensions

        public static TResult GetProperty<TResult>(

            this object item,

            string propName)

            var properties = TypeDescriptor.GetProperties(item);

            var descriptor = properties.Find(propName, true);

            if (descriptor != null

                && descriptor.PropertyType == typeof(TResult))

                return (TResult)descriptor.GetValue(item);

            else

                throw new InvalidOperationException(

                    String.Format("Property '{0}' with type '{1}' not found.",

                        propName, typeof(TResult)));

Аналогичным образом реализуем модель характерную для ORM.

Интерфейс хранилища объектов, который нам понадобится будет выглядеть так:

using System.Collections.Generic;

namespace Home.Andir.Examples

    public interface IORMTreeModelRepository<T>

        IEnumerable<T> GetRoots();

        T GetItem(int parentID);

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

Путь в иерархической структуре строится аналогично предыдущей модели.

Примечание: В качестве основных полей объекта предполагается существование полей "ID", "Parent" и "Children", если их в объекте не окажется, то возникнет ошибка времени выполнения.

ORMTreeModelRepository.cs

using System;

using System.Collections.Generic;

namespace Home.Andir.Examples

    public class ORMTreeModelRepository<T>

        : IHierarchyDataRepository<T>

        where T : class

        readonly Func<IEnumerable<T>> getRootsImpl;

        readonly Func<int, T> getItemByIdImpl;

        public ORMTreeModelRepository(

            IORMTreeModelRepository<T> repository)

            : this(repository.GetRoots, repository.GetItem)

{ }

        public ORMTreeModelRepository(

            Func<IEnumerable<T>> getRootsImpl,

            Func<int, T> getItemImpl)

            this.getRootsImpl = getRootsImpl;

            this.getItemByIdImpl = getItemImpl;

        public T GetItem(string path)

            var pathItems = path.Split('/');

            if (pathItems.Length > 0)

                int itemID = int.Parse(

                    pathItems[pathItems.Length - 1]);

                return getItemByIdImpl(itemID);

            return null;

        public IEnumerable<T> GetChildren(T item)

            if (item == null)

                return getRootsImpl();

            return item.GetProperty<IEnumerable<T>>("Children");

        public T GetParent(T item)

            if (item == null)

                throw new ArgumentNullException("item");

            return item.GetProperty<T>("Parent");

        public string GetItemHierarchyPath(

            string parentHierarchyPath, T item)

            if (parentHierarchyPath == null)

                throw new ArgumentNullException("parentHierarchyPath");

            if (item == null)

                throw new ArgumentNullException("item");

            return string.Format("{0}/{1}",

                parentHierarchyPath,

                item.GetProperty<int>("ID"));

        public string GetItemType(T item)

            if (item == null)

                throw new ArgumentNullException("item");

            return typeof(T).ToString();

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

Пример использования

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

Для доступа к этой БД будем использовать Entity Framework, модель будет выглядеть следующим образом:

Реализуем слой данных для доступа к данным в этой таблице:

using System.Collections.Generic;

using System.Linq;

namespace Home.Andir.Examples.Code.DataLayer

    public class DepartmentRepository

        public IEnumerable<Department> GetDepartments()

            using (var context = new HierarchicalDbEntities())

                var query = from d in context.DepartmentSet

                            where !d.ParentID.HasValue

                            select d;

                return query.ToList();

        public IEnumerable<Department> GetDepartments(int parentID)

            using (var context = new HierarchicalDbEntities())

                var query = from d in context.DepartmentSet

                            where d.ParentID.HasValue

                                && d.ParentID.Value == parentID

                            select d;

                return query.ToList();

        public Department GetDepartment(int id)

            using (var context = new HierarchicalDbEntities())

                var query = from d in context.DepartmentSet

                            where d.ID == id

                            select d;

                return query.First();

Сделаем страничку, на которой будем отображать организационную структуру:

<%@ Page

    Language="C#"

    MasterPageFile="~/Shared/Site.Master"

    AutoEventWireup="true"

    CodeBehind="TreeViewWithRepository.aspx.cs"

    Inherits="Home.Andir.Examples.TreeViewWithRepositoryPage" %>

<asp:Content ContentPlaceHolderID="BodyPlaceHolder" runat="server">

    <asp:TreeView ID="treeView" runat="server">

        <DataBindings>

            <asp:TreeNodeBinding ValueField="ID" TextField="Name" />

        </DataBindings>

    </asp:TreeView>

</asp:Content>

и теперь в CodeBehind реализуем биндинг данных к DepartmentRepository:

using System;

using Home.Andir.Examples.Code.DataLayer;

namespace Home.Andir.Examples

    public partial class TreeViewWithRepositoryPage

        : System.Web.UI.Page

        protected void Page_Load(object sender, EventArgs e)

            var repository = new DepartmentRepository();

            treeView.DataSource =

                new GenericHierarchicalDataSource<Department>(

                    new PlainTreeModelRepository<Department>(

                        () => repository.GetDepartments(),

                        item => repository.GetDepartments(item.ID),

                        id => repository.GetDepartment(id)));

            treeView.DataBind();

Для проверки запускаем:

Вот, наконец-то, всё заработало :-)

Полный проект с реализацией IHierarchicalDataSource можно взять здесь.

Пролог: Изучение с нуля

2009-08-25T17:36:00.001+04:00

Добрался таки до пролога. Чтобы не потерять, все источники собираю в одном месте.

Реализации:

SWI-Prolog,
GNU Prolog,
B Prolog,
SICStus Prolog (платный, 30 дневный trial выдаётся по запросу),
Strawberry Prolog (Light версия распространяется бесплатно).

Редакторы кода:

PceEmacs (встроенный Emacs для SWI-Prolog),
Emacs (prolog-mode),
Visual Prolog,
Prolog Development Tool for Eclipse.

Источники первичной информации:

Wikipedia: Prolog,

Большая статья из которой можно почерпнуть практически всю доступную информацию о языке Prolog.

Wikibooks: Prolog,

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

Prolog ISO/IEC 13211-1:1995 - стандарт языка,

В 1995 году был принят стандарт языка, но к сожалению в свободном доступе его обнаружить не удалось, есть только черновик в PostScript формате.

Prolog: ISO Standard documents.

Набор документов и программ использованных при разработке стандарта языка.

Туториалы:

Книги:

"Программирование на языке Пролог", У. Клоксин К. Меллиш ("Programming in Prolog" by W.F. Clocksin and C.S. Mellish),
"Декларативное программирование", И.А.Дехтяренко,
Программирование на языке Пролог для искусственного интеллекта, И. Братко,
Learn Prolog Now by Patrick Blackburn, Johan Bos and Kristina Striegnitz (бесплатная онлайн-версия).

Задачи:

99 Prolog problems,

Другое:

Free stuff for programming in Prolog,
The Prolog Dictionary,
Higher-order logic programming in Prolog (статья о программировании с правилами высшего порядка, сама статья в pdf лежит отдельно).

Очень краткое введение

Пролог – это декларативный логический язык программирования. Основными его конструкциями являются логические предложения (например: human('Socrat') :- true.), на основании которых пролог строит некоторые логические выводы. Предложения объединяются в правила с помощью операции and, которая обозначается знаком ','. Предложение при проверке может создавать побочные эффекты, что используется для ввода/вывода.

Краткий путеводитель по синтаксису

% Это строчный комментарий
/* А это блочный комментарий */

goal(X, Y) :-   % goal - это цель, для которой мы собираем правила,
                % имя цели всегда начинается с маленькой буквы.
                % результат у цели - это всегда true или false.
                % X, Y - параметры цели.

    X > Y       % Первое утверждение, которое утверждает что X больше Y.

    ,           % Разделитель между утверждениями, означает логическое И.

    X + 1 == Y  % Второе утверждение, которое может быть верным,
                % только если Y = X + 1.

    .           % Точка означает конец описания цели.

/*
 * Суммирую:
 * Имя цели всегда с маленькой буквы,
 * Параметры цели, и все другие переменные с большой буквы,
 * Утверждения разделяются запятой,
 * Описание цели всегда заканчивается точкой.
 */

prolog('logic language').
% Так записываются некоторые факты,
% и по сути являются сокращениями для цели,
% которая всегда возвращает true.
% в данном случае эквивалент выглядел бы так:
% prolog('logic language') :- true.

% Цели могут быть рекурсивными.
% Посчитаем сумму от 0 до X.
sum(0, 0).   % факт используется для остановки рекурсии.
sum(X, Result) :-
    Y is X - 1,             % is - это по сути присвоение значения.
    sum(Y, SubResult),      % Рекурсивный вызов.
    Result is X + SubResult.


% Цель, которая будет использоваться при запуске программы,
% имя 'main' выбрано мною произвольно.
main :-
    % запрашиваем значение факта
    prolog(Which),
    % выводим значение на экран
    format('prolog is a ~a.', [Which]),

    % newline
    nl,

    % задаём значение X
    X is 100,
    % считаем сумму от 0 до 100
    sum(X, Result),
    % выводим результат с помощью printf-like функции
    format('sum(0, ~a) = ~a.', [X, Result]),

    % newline.
    nl.

/*
 * Вывод программы при запуске:
 * prolog is a logic language.
 * sum(0, 100) = 5050.
 */

Типы данных

Атом: атом или 'атом', начинается с маленькой буквы или обрамляется одинарными кавычками.

Строка: "Строка", обрамляется двойными кавычками, по факту представляет список из чисел – кодов ASCII символов строки.

Число: 10, целые (-1,0,1), плавающая запятая (0.123, 123.456).

Список: [0, 1, 2], набор элементов перечисленных через запятую и обрамлённых квадратными скобками. Элементы могут быть разнородными (разных типов). Списки можно деструктурировать через синтаксис [Head | Tail].

Первые результаты

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

HelloWorld.pro:

main :- writeln('Hello, Prolog World!').

Factorial.pro:

% factorial implementation

factorial(1, 1).

factorial(X, Result) :-

    X > 0,

    X1 is X - 1,

    factorial(X1, Result1),

    Result is X * Result1.

main :-

    factorial(7, X),

    writeln(X).

Fibonachi.pro:

% Fibbonachi sequence implementation

fib(0, 1).

fib(1, 1).

fib(X, Result) :-

    X1 is X - 1,

    X2 is X - 2,

    fib(X1, Result1),

    fib(X2, Result2),

    Result is Result1 + Result2.

main :-

    fib(7, X),

    writeln(X).

QuickSort.pro:

qsort([], []).

qsort([X], [X]).

qsort([Head | Tail], Result) :-

    partition(Head, Tail, Left, Right),

    qsort(Left, LeftSorted),

    qsort(Right, RightSorted),

    append(LeftSorted, [Head | RightSorted], Result).

partition(_, [], [], []).

partition(Pivot, [Head | Tail], [Head | Left], Right) :-

    Head =< Pivot,

    partition(Pivot, Tail, Left, Right).

partition(Pivot, [Head | Tail], Left, [Head | Right]) :-

    Head > Pivot,

    partition(Pivot, Tail, Left, Right).

append([], Right, Right).

append([Head | Left], Right, [Head | Result]) :-

    append(Left, Right, Result).

main :-

    qsort([1, 5, 4, 6, 3, 2], X),

    writeln(X).

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

Путём нехитрых поисков в источниках близким к прологу собрал такой список:

Curry Language, "A Truly Integrated Functional Logic Language":

Расширение языка Haskell для реализации логического программирования.

Mercury Project,

Mercury is a new logic/functional programming language, which combines the clarity and expressiveness of declarative programming with advanced static analysis and error detection features.

Oz Language,

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

ALF – Algebraic logical functional language,

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