Стратегії обчислення

Мова програмування використовує стратегії обчислення для того, щоб визначити, коли обчислювати аргумент(и) виклику функції (або операції, методу чи співвідношення) і які значення передавати до функції. Наприклад, виклик за значенням/виклик за посиланням визначають, що аргумент обчислюється до виконання тіла функції, і надає дві можливості для функції – отримати поточне значення аргументу та змінити його через вираз присвоєння. Поняття стратегії скорочення в лямбда обчисленнях є схожим, але має відмінності.

На практиці, багато сучасних мов програмування зійшлись на використанні стратегії виклику по значенню/виклику по посиланню для виклику функцій (C#, Java). Деякі мови, особливо нижчого рівня, такі як С++, поєднують декілька ідей передачі параметрів. Історично, виклик за значенням/виклик за посиланням бере свій початок в ALGOL 60, мові, створеній в пізніх 1950-х. Виклик по посиланню використовується в PL/I та деяких дистрибутивах Fortran. Виключно функціональні мови, такі як Haskell, а також не повністю функціональні мови, такі як R, використовують виклик за потребою.

Строгі обчислення ред.

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

Аплікативний порядок ред.

Аплікативний порядок (або найлівіший найглибший) – стратегія, при якій аргументи функції обчислюються зліва направо в зворотному порядку обходу дерева виразу. Аплікативний порядок відноситься до виклику за значенням.

Виклик за значенням ред.

Виклик за значенням це найпоширеніша стратегія обчислень, яка використовується в різноманітних мовах як С чи Scheme. У виклику за значенням вираз аргументу обчислюється і отримане значення прикріплюється до відповідної змінної у функції (найчастіше копіюванням значення у нову область пам'яті). Якщо функція чи процедура може присвоювати значення своїм параметрам, то тільки локальна копія змінюється, тобто все, що було передане під час виклику, після закінчення роботи функції у зовнішній області видимості не змінюється.

Виклик за значенням це швидше не конкретна стратегія обчислень, а ціле сімейство стратегій обчислень в яких аргумент функції обчислюється перед передачею до функції. Більшість мов програмування, які використовують виклик за значенням (такі як Common Lisp, Eiffel і Java) обчислюють аргументи зліва направо, деякі обчислюють функції та аргументи справа наліво, інші (такі як Scheme, OCaml і C) не встановлюють порядок обчислень.

Неявні обмеження ред.

Іноді термін “виклик за значенням” не є коректним, тому що значення, яке передається, не є значенням змінної як мається на увазі в звичайному значенні змінної, а є посиланням на значення, яке залежить від реалізації. Наслідком є те, що код, який синтаксично виглядає як виклик за значенням може поводити себе як виклик за посиланням чи виклик за співвикористанням (англ. call-by-sharing), що залежить від тонких аспектів семантики мови.

Причина передачі за посиланням зазвичай полягає в тому, що технічно мова не надає конкретне значення для складних даних, а замість цього надає структуру даних, хоча в коді вони виглядають схожими на єдине значення. Важко точно провести межу між власне значеннями та замаскованими під них структурами даних. У С вектор (одномірний масив, частковим випадком якого є символьний рядок) є структурою даних, і тому розглядається як символьний рядок, але структура представляє собою значення, навіть якщо його полем є вектор. У Maple, вектор це частковий випадок таблиці, і тому це структура даних, але список (який будується і може бути проіндексований таким самим способом) є значенням. В Tcl, значення є двоякими, тобто на рівні сценарію вони використовуються у вигляді значення, а мова керує відповідною структурою даних, якщо вона потрібна. Зміни, зроблені зі структурою даних відображаються на значенні і навпаки.

Пояснення “виклик за значенням, де значення це посилання” є загальновживаним (але не слід розуміти це як виклик за посиланням); інший термін - виклик за співвикористанням. Таким чином виклик за значенням у Java або Visual Basic і виклик за значенням у С чи Pascal є істотно різними: у С чи Pascal виклик функції з аргументом, представленим у вигляді великої структури призведе до того, що вся структура буде скопійована (за винятком випадку, коли це буде посилання на структуру), потенційно викликаючи серйозне зниження продуктивності, і зміни в структурі будуть невидимі для того, хто викликав. А в Java або Visual Basic копіюється лише посилання на структуру, що відбувається швидко, і зміни до структури видимі ззовні.

Виклик по посиланню ред.

При виклику по посиланню (також відомий як передача по посиланню) функція отримує неявне посилання на змінну, що використовується як аргумент, а не копію цієї змінної. Зазвичай це означає, що функція може змінювати (тобто присвоювати нове значення) змінній, що передана як аргумент - так, що це буде помітно, для того хто викликав цю функцію. Тому виклик по посиланню може бути використаний для забезпечення додаткового каналу зв'язку між функцією що викликається та функцією яка викликає. У мовах з викликом по посиланню програмісту набагато важче відстежити ефекти виклику функції, що може привести до багів, буде складно виявити.

Багато мов підтримують виклик по посиланню в тій чи іншій формі, але порівняно небагато використовують його за умовчанням. FORTRAN II це може бути прикладом першої з викликом за посиланням. Незначна кількість мов, наприклад C++, PHP, Visual Basic, .NET, C# і REALbasic за умовчанням використовують виклик за значенням, але надають спеціальний синтаксис для виклику за посиланням. У C++ також є виклик за посиланням на константу.

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

Аналогічний ефект досягається через виклик з співвикористанням (передача об'єкту, що може бути змінений), використовується у мовах Java, Python та Ruby.

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

Приклад, що демонструє виклик за посиланням в C:

void Modify(int p, int &q)
{
    p = 27; // передано за значенням - тільки локальна копія змінюється    
    q = 27; // передано за посиланням - початкова змінна теж отримає нове значення
}

int main()
{
    int a = 1;
    int b = 1;
    Modify(a, b);
    std::cout << "a=" << a << std::endl; //на екран виведеться a=1
    std::cout << "b=" << b << std::endl; //на екран виведеться b=27
    return(0);
}

Виклик з співвикористанням ред.

Використовується в мовах Python, Iota, Java (для посилань на об'єкти), Ruby, JavaScript, Scheme, OCaml, AppleScript, та багатьох інших. При виклику з співвикористанням мається на увазі, що всі значення в мові засновані на об'єктах а не примітивах, тобто всі значення “запаковано” (англ. boxed).

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

def f(l):
    l.append(1)
m = []
f(m)
print(m)

... виводить [1] тому що метод append змінює об'єкт для якого він був викликаний. Присвоєння всередині функції невидимі ззовні, тому що присвоєння прив'язує змінну до іншого об'єкту, а не змінює сам об'єкт. Оскільки цей об'єкт буде існувати лише в області видимості функції, зовнішня копія збереже свою початкову прив'язку. Цей код присвоює формальному параметру новий об'єкт:

def f(l):
    l = [1]
m = []
f(m)
print(m)

... і виводить [], тому що вираз l = [1] присвоює новий список локальній змінній замість присвоєння нового значення для оригінальної змінної.

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

Цей термін отримав розповсюдження в спільноті Python, аналогічні семантики в інших мовах, як Java та Visual Basic зазвичай визначаються як виклик за значенням, де під значенням мається на увазі посилання на об'єкт.

Виклик з копіюванням та відновленням ред.

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

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

Часткове обчислення ред.

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

Нестрогі обчислення ред.

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

Нормальний порядок ред.

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

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

Виклик по імені ред.

В стратегії виклик по імені аргументи функції не обчислюються перед тим, як функція буде викликана, а передаються прямо в тіло функції (використовуючи підстановку, що запобігає захопленню^{[уточнити]}), і далі обчислюються при появі у функції. Якщо аргумент в тілі функції не використовується, то він ніколи не обчислюється, якщо він використовується декілька разів, то він обчислюється при кожній появі.

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

Вперше був використаний в ALGOL 60. У Scala за умовчанням використовується виклик за значенням, але виклик за іменем також доступний. Сучасні мови .NET можуть імітувати виклик по імені використовуючи делегати або параметри типу Expression<T>. В останньому випадку у функцію передається абстрактне синтаксичне дерево. В мові Eiffel реалізовані агенти, які представляють операції, що обчислюються за потребою. В мові Seed7 реалізований виклик за іменем з параметрами функції.

Виклик за потребою ред.

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

Оскільки обчислення виразів може мати високий ступінь вкладення, мови, що використовують виклик за потребою зазвичай не підтримують побічні ефекти, окрім використання монад. Це виключає будь-яке непередбачувані ефекти зі змінних, чиї значення змінюються при відкладених обчисленнях.

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

Haskell є найвідомішою мовою, що використовує стратегію виклику за потребою. R також використовує форму виклику за потребою. Мови платформи .NET можуть емулювати виклик за потребою використовуючи тип Lazy<T>.

Виклик із розкриттям макросів ред.

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

Недетерміновані обчислення ред.

Повне β-скорочення ред.

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

Виклик в майбутньому ред.

Виклик в майбутньому (або паралельний виклик за іменем) це стратегія паралельних обчислень. Значення запланованого виразу обчислюється паралельно разом з потоком програми. Коли значення стає потрібним, основна програма блокується поки обчислення запланованого виразу не закінчиться.

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

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

Оптимістичні обчислення ред.

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