Ліниві обчислення

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

В теорії мов програмування, ліниві обчислення, або виклик за потребою це стратегії обчислення які затримують обчислення виразу до того моменту, поки воно не стане потрібним і уникають повторних обчислень.


Перевагами лінивих обчислень є:

  • Можливість визначити потік керування як абстракції замість примітивів.
  • Можливість визначати потенційно нескінченні структури данних. Це дозволяє реалізовувати деякі алгоритми більш прямолінійно.
  • Покращення продуктивності за рахунок уникання непотрібних обчислень і невиконуваних гілок в умовних виразах.

Ліниві обчислення зазвичай комбінуться з запам'ятовуванням. Після обчислення значення функції для параметру або набору параметрів, результат зберігається в таблиці, індексами якої є параметри; коли функція буде викликана знову буде зроблена перевінка, чи міститься вже обчислене значення функції з такими параметрами в таблиці. Якщо так, то збережений результат повертається. Якщо ні, то значення функції обчислюється і це значення додається в таблицю для повторного використання.

Ліниві обчислення можуть привести до зменшення використання пам'яті, тому що значення створюються лише якщо вони потрібні. Проте ліниві обчислення важко об'єднувати з імперативним програмуванням, наприклад у випадку введення/виведення чи обробки виключних ситуацій, тому що порядок операцій стає невизначеним. Також ліниві обчислення можеть привести до витоків пам'яті.

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

Історія[ред.ред. код]

Ліниві обчислення були створені для лямбда числення Кристофером Водсвортом і для мов програмування Пітером Хендерсоном та Джеймсом Моррісом і Денієлом Фрідманом та Девідом Вайзом. 

Застосування[ред.ред. код]

Відкладені обчислення в основному використовуються в функціональних мовах програмування. При використанні відкладених обчислень, вираз не обчислюється зразу ж при присвоєнні до змінної. Тобто вираз  x:=expression; (тобто присвоєння результату виразу до певної змінної) за задумом обчислюється і записується до змінної, але реально це значення буде непотрібне (і тому не обчислюється) до того моменту, поки ця змінна не з'явиться в подальших виразах, обчислення яких не можуть бути відкладені.

Затримане обчислення має перевагу у обчисленні дуже великих або нескінченних списків без використання нескінченних циклів. Наприклад можна створити функцію, що створює нескінченний список (який зазвичай називається потік) чисел Фібоначчі. Обчислення повного числа Фібоначчі буде просто звернення до відповідного елементу списку.

Наприклад, на мові Haskell список, що містить всі числа Фібоначчі може бути створений так:

 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

За умови, що програміст обережний, тільки обчислюються тільки значення, що потрібні для кінцевого виразу. Проте певні обчислення можуть приpвести  до того, що програма намагатиметься обчислити нескінченне число елементів; наприклад, спроба отримання довжини списку або обчислити суму елементів призведе до того, що програма завершить роботу через недостачу пам'яті.

Умовні конструкції[ред.ред. код]

В більшості розповсюджених мов програмуванні, вирази if обчислюються лінивим способом.


У такому записі:

if a then b else c

обчислюється вираз (а), тоді і тільки тоді коли (а) є істиною обчислюється вираз (b), в іншому випадку обчислюється вираз (с). Тобто один з виразів ((b) або (с)) не буду обчислений.


Робота з нескінченними структурами даних[ред.ред. код]

Багато мов надають можливість створювати нескінченні структури даних. Це дозволяє давати визначення даним на нескінченних проміжках або за допомогою рекурсії. Приклад такої програми на Haskell:

numberFromInfiniteList :: Int -> Int
numberFromInfiniteList n =  infinity !! n - 1
    where infinity = [1..]

main = print $ numberFromInfiniteList 4

У функції numberFromInfiniteList, значення infinity є нескінченним проміжком, але поки дійсне значення (або більш конкретно - значення з конкретним індексом) не стане потрібним, список не обчислюється, а при обчисленні обчислюється тільки потрібна частина (тобто до вказаного індексу).

Інші використання[ред.ред. код]

У операційних системах з віконним інтерфейсом виведення інформації на екран керується подіями виведення. Внаслідок цього операційна система уникає непотрібних обчислень для оновлення екрану.

Іншим прикладом лінивості в сучасних комп'ютерних системах є копіювання при записі, при якому пам'ять виділяється лише коли збережене значення змінюється.

Лінивість може бути корисною для високої продуктивності. Прикладом є функція mmap в Unix, яка робить кероване потребою завантаження файлу в пам'ять, тобто тільки ті частини, які реально використовуються, завантажуються, і пам'ять на непотрібні блоки не виділяється.

MATLAB реалізує копіювання при модифікацї при якому масиви, які компіюються міняють своє місце в пам'яті лише якщо їх зміст змінився. Але такий підхід може призвести до помилки out of memory якщо змінити елемент після копіювання замість зміни під час копіювання.

Реалізація[ред.ред. код]

Деякі мови програмування відкладають обчислення виразів за замовчанням, інші надають спеціальні функції або синтаксис для їх відкладення. Наприклад обчислення аргументів функції за замовчанням відкладається в мовах Miranda і Haskell. В багатьох інших мовах обчислення можуть бути затримані в явному вигляді з використанням спеціального синтаксису (в Scheme "delay" і "force", в OCaml "lazy" і "Lazy.force") . Об'єкт, який представляє такі відкладені обчислення називається ліниве майбутнє. Perl 6 використовує ліниве обчислення списків, тож можна створювати нескінченні списки та передавати їх до функцій, але на відміну від Haskell та Miranda, Perl 6 за замовчанням не використовує ліниві обчислення для арифметичних виразів та функцій.

Лінивість та ретельність[ред.ред. код]

Контролювання ретельності в лінивих мовах[ред.ред. код]

В мовах з лінивим програмуванням, таких як Haskell, за замовчанням вирази обчислюються лише коли їх значення стане потрібне; в деяких випадках можливо зробити код більш ретельним - або навпаки, зробити обчислення більш лінивими після того як вони були зроблені ретельними. Це можна зробити за використовуючи явні команд які форсують обчислення (що робить код більш ретельним) або уникаючи таких команд (що робить код більш лінивим). Під строгими обчисленнями зазвичай розуміють ретельність, але технічно це різні концепції.

Перевагами лінивих обчислень є:

  • Можливість визначити потік керування як абстракції замість примітивів.
  • Можливість визначати потенційно нескінченні структури данних. Це дозволяє реалізовувати деякі алгоритми більш прямолінійно.
  • Покращення продуктивності за рахунок уникання непотрібних обчислень і невиконуваних гілок в умовних виразах.

Однак, в деяких компіляторах реалізована оптимізація, яка називається аналіз строгості, яка, в деяких випадках, дозволяє компілятору визначити чи буде змінна завжди використовуватись. В таких випадках вибір програміста використовувати ліниві обчислення чи ні стає непотрібним, тому що аналіз строгості буде форсувати строгі обчислення.


Симуляція лінивості в ретельних мовах[ред.ред. код]

Python

Ліниві обчислення можуть привести до зменшення використання пам'яті, тому що значення створюються лише якщо вони потрібні. Проте ліниві обчислення важко об'єднувати з імперативним програмуванням, наприклад у випадку введення/виведення чи обробки виключних ситуацій, тому що порядок операцій стає невизначеним. Також ліниві обчислення можеть привести до витоків пам'яті.

В Python 2.x функція range() створює список цілих чисел. Весь список зберігається у пам'яті після того, як присвоєння буде виконане. Ось приклад ретельного, або негайного обчислення:

 >>> r = range(10)
 >>> print r
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 >>> print r[3]
 3

В Python 3.x функція range() повертає спеціальний об'єкт, який обчислює елементи списку на вимогу. Елементи цього об'єкту генеруються тільки тоді коли вони стають потрібні (тобто коли в прикладі обчислюється print(r[3]) ), тож це буде прикладом лінивих, або відкладених обчислень:

 >>> r = range(10)
 >>> print(r)
 range(0, 10)
 >>> print(r[3])
 3
Ця зміна до лінивих обчислень зберігає час виконання для великих проміжків які ніколи не будуть повністю використовуватись.

В Python 2.x э функція xrange() яка повертає об'єкт, що створює числа з заданому проміжку на вимогу. Перевага функції xrange є те, що такий об'єки буде займати одину й ту саму кількість пам'яті.

Застосування[ред.ред. код]

>>> r = xrange(10)
>>> print(r)
xrange(10)
>>> lst = [x for x in r]
>>> print(lst)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

З версії 2.2 і далі, Python розширив ліниві обчислення реалізацією ітераторів (ліниві послідовності) на відміну від кортежів чи списків. Наприклад (Python 2):

 >>> numbers = range(10)
 >>> iterator = iter(numbers)
 >>> print numbers
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 >>> print iterator
 <listiterator object at 0xf7e8dd4c>
 >>> print iterator.next()
 0
Цей приклад показує як списки обчислююься при виклику, але у випадку з ітератором, перший елемент '0' друкується коли така потреба виникає.
.NET Framework

В фреймворку .NET ліниві обчислення можливі з використанням класу  System.Lazy<T>. В F# є спеціалізовані колекції, такі як Microsoft.FSharp.Collections.Seq у яких є вбудована підтримка для лінивих обчислень.

let fibonacci = Seq.unfold (fun (x, y) -> Some(x, (y, x + y))) (0I,1I)
fibonacci |> Seq.nth 1000

В C# і VB.NET, використовується клас System.Lazy<T>.

public int Sum()
{
    int a = 0;
    int b = 0; 
    Lazy<int> x = new Lazy<int>(() => a + b);
    a = 3;
    b = 5;
    return x.Value; // returns 8
}

За умови, що програміст обережний, тільки обчислюються тільки значення, що потрібні для кінцевого виразу. Проте певні обчислення можуть приpвести  до того, що програма намагатиметься обчислити нескінченне число елементів; наприклад, спроба отримання довжини списку або обчислити суму елементів призведе до того, що програма завершить роботу через недостачу пам'яті. Більш практичний приклад:

// recursive calculation of the n'th fibonacci number
public int Fib(int n)
{
   return (n == 1)? 1 : (n == 2)? 1 : Fib(n-1) + Fib(n-2);
}

public void Main()
{
    Console.WriteLine("Which Fibonacci number do you want to calculate?");
    int n = Int32.Parse(Console.ReadLine()); 
    Lazy<int> fib = new Lazy<int>(() => Fib(n)); // function is prepared, but not executed
    bool execute; 
    if(n > 100)
    {
        Console.WriteLine("This can take some time. Do you really want to calculate this large number? [y/n]");
        execute = (Console.ReadLine() == "y"); 
    }
    else execute = true;
    
    if(execute) Console.WriteLine(fib.Value); // number is only calculated if needed
}

Інший спосіб - використання ключового слова yield:

Умовні конструкції[ред.ред. код]

// eager evaluation 
public IEnumerable<int> Fibonacci(int x)
{
    IList<int> fibs = new List<int>();

    int prev = -1;
    int next = 1;
    for (int i = 0; i < x; i++)
    {
     int sum = prev + next;
        prev = next;
        next = sum;
        fibs.Add(sum); 
    }
    return fibs;
}

// lazy evaluation 
public IEnumerable<int> LazyFibonacci(int x)
{
    int prev = -1;
    int next = 1;
    for (int i = 0; i < x; i++)
    {
        int sum = prev + next;
        prev = next;
        next = sum;
        yield return sum;
    }
}

обчислюється вираз (а), тоді і тільки тоді коли (а) є істиною обчислюється вираз (b), в іншому випадку обчислюється вираз (с). Тобто один з виразів ((b) або (с)) не буду обчислений.