Ліниві обчислення: відмінності між версіями

Стратегії обчислення
Строгі обчислення Ліниві обчислення Часткові обчислення Віддалені обчислення Обчислення за короткою схемою

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

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

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

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

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

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

Історія

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

Застосування

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

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

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

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

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

Умовні конструкції

У більшості розповсюджених мов програмування, вирази 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
}

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

// 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) або (с)) не буде обчислений.