Привет всем!

Взялся за изучение Nemerle и появились вопросы в большом количестве. В качестве примера решил написать простую программу для вычисления размера каталога файловой системы:

using System.Console;
using System.IO;

module Applicaion
{
  DirectorySize( path : string ) : long
  {
    DirectorySize( DirectoryInfo( path ) );
  }
  DirectorySize( directoryInfo : DirectoryInfo ) : long
  {
    DirectoryFilesSize( directoryInfo.GetFiles() ) + DirectorySubdirectoriesSize( directoryInfo.GetDirectories() );
  }
  DirectoryFilesSize( fileInfos : array[FileInfo], index : int = 0 ) : long
  {
    if ( index < fileInfos.Length )
      fileInfos[index].Length + DirectoryFilesSize( fileInfos, index + 1 )
    else 
      0L
  }
  DirectorySubdirectoriesSize( directoryInfos : array[DirectoryInfo], index : int = 0 ) : long
  {
    if ( index < directoryInfos.Length )
      DirectorySize( directoryInfos[index] ) + DirectorySubdirectoriesSize( directoryInfos, index + 1 )
    else 
      0L
  }

  Main() : void
  {
    def targetPath = @"D:\Temp";
    
    WriteLine( $"Scanning $targetPath ..." );
    def lengthInBytes : decimal = DirectorySize( targetPath );
    def lengthInMegaBytes = lengthInBytes  / 1024 / 1024;
    WriteLine( "Directory size: {0:F1} Mb", lengthInMegaBytes );     
    WriteLine( "                {0} bytes", string.Format( "{0:N}", lengthInBytes ).Replace( ".00", "" ) );
    WriteLine( "Press any key to exit." );
    ignore( ReadKey() );
  }
}

Это мой первый опыт с неимперативным языком, не считая универовских шалостей на ДОСовском лиспе и прологе, так что просьба сильно не пинать, хотя совету по упрощению этого чуда я был бы рад. Не знаю, насколько получилось в духе ФП.

А вопрос такой. Глянул я в рефлектор и обнаружил, что никакой там оптимизации хвостовой рекурcии нет и в помине, хотя как минимум одна из этих функций явный претендент на такую оптимизацию. Я что-то не так понял?

И ещё один вопрос, более важный. Как можно получить offline версию документации, той что живёт по адресу http://nemerle.org/doc/ ? А то сайт их такой медленный, что невозможно работать.

Спасибо.

Здравствуйте, SergASh, Вы писали:

[[ код поскипан ]]

SAS>А вопрос такой. Глянул я в рефлектор и обнаружил, что никакой там оптимизации хвостовой рекурcии нет и в помине, хотя как минимум одна из этих функций явный претендент на такую оптимизацию. Я что-то не так понял?

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

using System.Console;
using System.IO;

module Applicaion
{
    DirectorySize(path : string) : long
    {
        DirectorySize(DirectoryInfo(path));
    }
    
    DirectorySize(directoryInfo : DirectoryInfo) : long
    {
        def files       = directoryInfo.GetFiles();
        def directories = directoryInfo.GetDirectories();
        
        DirectoryFilesSize(files) + 
        DirectorySubdirectoriesSize(directories);
    }
    
    DirectoryFilesSize(fileInfos : array[FileInfo], size: long = 0L, index : int = 0) : long
    {
        if (index < fileInfos.Length)
            DirectoryFilesSize(fileInfos, size + fileInfos[index].Length, index + 1);
        else 
            size;
    }
    
    DirectorySubdirectoriesSize(directoryInfos : array[DirectoryInfo], size: long = 0L, index : int = 0) : long
    {
        if (index < directoryInfos.Length)
            DirectorySubdirectoriesSize(directoryInfos, size + DirectorySize(directoryInfos[index]), index + 1);
        else 
            size;
    }

    Main() : void
    {
        def targetPath = @"D:\Temp";
        
        WriteLine($"Scanning $targetPath ...");
        def lengthInBytes : decimal = DirectorySize(targetPath);
        def lengthInMegaBytes = lengthInBytes    / 1024 / 1024;
        
        WriteLine("Directory size: {0:F1} Mb", lengthInMegaBytes);         
        WriteLine("\t{0} bytes", string.Format("{0:N}", lengthInBytes).Replace(".00", ""));
        WriteLine("Press any key to exit.");
        
        _ = ReadKey();
    }
}

ЗЫ. Re[2]: Nemerle и рекурсия

Автор: fmiracle
Дата: 24.07.06

Здравствуйте, SergASh, Вы писали:

SAS>Это мой первый опыт с неимперативным языком, не считая универовских шалостей на ДОСовском лиспе и прологе, так что просьба сильно не пинать, хотя совету по упрощению этого чуда я был бы рад. Не знаю, насколько получилось в духе ФП.

Как первый опыт — сойдет. В прочем, сразу даю информацию для мотания на ум (кстати, в статья на этом сайте она уже была).
Весь кайф (ну, я конечно утрирую, не весь, но все же ) фунционального подхода заключается в том, что выражения можно так же подвергать декомпозиции как более сложные сущности.
В данном примере можно воспользоваться стандартными для ФП фунциями свертки (Fold). Их можно описать как декомпозиция свортки некого вычисления над неким списком (в широком смысле этого слова), а можно как эдакий заменитель цикла с накапливающей переменной. Вот как с помощью этой фунции можно переписать твой пример (изменения выделены жирным):

using System.Console;
using System.IO;
using Nemerle.Utility;

module Applicaion
{
  Main() : void
  {
    def targetPath = @"C:\Temp";
    
    WriteLine($"Scanning $targetPath ...");
    
    def calcDirectorySize(dirInfo : DirectoryInfo)
    {
      def filesLen = dirInfo.GetFiles("").Fold(0L, (fileInfo, acc) => acc + fileInfo.Length);
      filesLen + dirInfo.GetDirectories().Fold(0L, (dirInfo,  acc) => acc + calcDirectorySize(dirInfo));
    }
    
    def lengthInBytes : decimal = calcDirectorySize(DirectoryInfo(targetPath));
    def lengthInMegaBytes = lengthInBytes  / 1024 / 1024;
    WriteLine("Directory size: {0:F1} Mb", lengthInMegaBytes);     
    WriteLine("                {0} bytes", string.Format("{0:N}", lengthInBytes).Replace(".00", ""));
    WriteLine("Press any key to exit.");
    ignore(ReadKey());
  }
}

SAS>А вопрос такой. Глянул я в рефлектор и обнаружил, что никакой там оптимизации хвостовой рекурcии нет и в помине, хотя как минимум одна из этих функций явный претендент на такую оптимизацию. Я что-то не так понял?

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

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

DirectoryFilesSize(fileInfos : array[FileInfo], index : int = 0) : long
{
    if (index < fileInfos.Length)
        fileInfos[index].Length + DirectoryFilesSize(fileInfos, index + 1)
    else 
        0L
}

пишешь:

DirectoryFilesSize(fileInfos : array[FileInfo], acc : long, index : int = 0) : long
{
    if (index < fileInfos.Length)
        DirectoryFilesSize(fileInfos, acc + fileInfos[index].Length, index + 1)
    else 
        0L
}

SAS>И ещё один вопрос, более важный. Как можно получить offline версию документации, той что живёт по адресу http://nemerle.org/doc/ ? А то сайт их такой медленный, что невозможно работать.

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

Просто внимательно прочти их и вопросов возникнуть не должно. А если возникнут, то этот форум к твоим услугам.