РЕФАЛ (Рекурсивних Функцій Алгоритмічний) — один з найстаріших функціональних мов програмування, орієнтований на символьні обчислення: опрацювання символьних рядків (наприклад, алгебраїчні викладення); переклад з однієї мови (штучного чи природного) на інший; вирішення проблем, пов'язаних з штучним інтелектом. Поєднує в собі математичну простоту з практичною спрямованістю на написання великих і складних програм.
Відмінною рисою мови є використання зіставлення зі зразком і переписування термів як основного способу визначення функцій.
Програма на Рефале може складатися з одного або декількох модулів (файлів), кожен з яких, у свою чергу, складається з функцій.
Рефал-функція являє собою упорядкований набір речень, що складаються із зразка та шаблону. На вхід функції подається деякий вираз; обчислення функції полягає в зіставленні вираження почергово зразками, взятими з першого, другого і т. д. пропозицій. Якщо чергове зіставлення проходить успішно, то на підставі шаблону, взятого з того ж пропозиції, формується нове Рефал-вираз, який і буде результатом функції. У разі, якщо ні з одним з наявних зразків аргумент функції зіставити не вдалося (неуспіх), фіксується помилка (аварійно завершується вся програма). Щоб уникнути цього часто в кінці функції поміщають пропозиція, за зразком якого можна зіставити взагалі довільне вираження. У деяких сучасних реалізаціях Рефала (наприклад, Рефал+) неуспіх будь-якого виразу функції замість помилки породжує неуспіх самої функції.
Вирази мови Рефал являють собою послідовності термів, в якості яких можуть виступати: звичайні символи (літери, цифри тощо), які в залежності від діалекту потрібно або не потрібно укладати в апострофи або лапки символи-мітки (ідентифікатори, конкретна запис яких варіюється в залежності від діалекту мови; так, в Рефале-5 ідентифікатором може служити довільна послідовність латинських букв і цифр, що починається з літери) макроціфри — цифровий запис невід'ємних цілих чисел, що не перевищують граничне значення числа з плаваючою точкою Рефал-змінні одного з декількох визначених типів довільне вираження, укладена в круглі дужки (в документації Рефалу такий терм називається виразом в структурних дужках) довільне вираження, укладену в «кутові» дужки і означає виклик функції (такий терм називається активним виразом)
Залежно від ситуації на вираження можуть бути накладені обмеження; так, у зразках заборонено використовувати вирази, що містять кутові дужки, а в полі зору Рефал-машини не можуть бути присутніми змінні.
Рефал-змінні використовуються в зразках і в залежності від свого типу можуть зіставлятися одному символу (тобто кожному терму, крім вираження в структурних дужках), одному терму (безпідставного), або довільним виразом (тобто послідовності термів довільної довжини). Відповідні типи змінних називаються S-змінними, T-змінними і E-змінними. У діалекті Рефал-2 підтримувались ще і V-змінні, що зіставляються безпідставного непустому виразу; в сучасних діалектах такі змінні не підтримуються.
Семантика мови Рефал описується в термінах віртуальної машини, званої «рефал-машина» або «рефал-автомат». Машина має поле зору, в якому може перебувати довільне рефал-вираження, що не містить рефал-змінних.
Виконання програми складається з кроків рефал-автомата, на кожному з яких виконується застосування функції до висловом. Для цього рефал-машина відшукує у своєму полі зору саме ліве з найбільш внутрішніх активних виразів; інакше кажучи, відшукуються парні кутові дужки, не містять інших кутових дужок, а якщо таких пар є кілька, вибирається та з них, яка текстуально в полі зору знаходиться лівіше інших. Перший терм вирази, укладеної в кутові дужки, повинен являти собою символ-мітку, яка ім'ям функції; частина виразу використовується як аргумент функції.
Як було сказано вище, серед пропозицій, складових функцію, знаходиться перше таке, зразок якого можна зіставити з аргументом функції; в ході зіставлення приписуються значення змінних, що містяться в зразку. Потім шаблон, взятий з того ж пропозиції, береться за основу для формування результату обчислення функції; попросту кажучи, результатом оголошується вираз, отримане з шаблону заміною змінних на їх значення. Необхідно відзначити, що шаблон може містити тільки змінні, наявні у зразку; таким чином, всі змінні, що входять в шаблон, виявляться при формуванні результату замінені на відповідні вирази, і результат вже містити змінні не буде. З іншого боку, шаблон цілком може містити вирази в кутових дужках.
На завершення кроку рефал-автомат замінює у своєму полі зору тільки що обчислене активне вираз (включаючи обмежують його кутові дужки) на отриманий в ході обчислення функції результат. Слід зазначити, що кількість кутових дужок, які перебувають у полі зору рефал-машини, може при цьому і зрости.
Виконання програми закінчується, коли в поле зору рефал-машини не виявиться більше кутових дужок. Вираз, що міститься в цей момент в полі зору, оголошується результатом виконання рефал-програми.
Розглянемо найпростіший приклад виконання програми на Рефале. Нехай дана наступна функція:
Ця функція аналізує вираз і повертає в якості результату символ-мітку True, якщо вираз є паліндромом, і False в іншому випадку. Функція має ім'я Palindrom. Пояснимо, що s.1 — це змінна S-типу, e.1 і e.2 — змінні E-типу. Таким чином, тіло функції складається з чотирьох пропозицій, перше з яких спрацює, якщо аргумент функції являє собою вираз, що починається і закінчується одним і тим же символом; друге буде використовуватися, якщо аргумент складається рівно з одного символу; третє задіюється для порожнього аргументу і, нарешті, четверте підійде для всіх інших випадків.
Зазначимо, що шаблон у першому реченні містить активну вираз, що представляє собою рекурсивний виклик функції Palindrom. Це відображає той факт, що, якщо перший та останній символи збіглися, їх можна відкинути і перевірити на палиндромичность залишок вираження.
Нехай у полі зору рефал-автомата виявилося таке активне вираження:
<Palindrom 'abcba'>
Тоді виконання буде складатися з трьох кроків, після яких у полі зору будуть знаходитися наступні вирази:
<Palindrom 'bcb'> <Palindrom 'c'> True
На перших двох кроках використовувалося перше речення, на останньому кроці — друге. Оскільки після третього кроку поле зору більше не містить кутових дужок, робота рефал-автомата на цьому завершується.
Перша версія РЕФАЛа була створена в 1966 році Валентином Турчиным як метаязыка для опису семантики інших мов. Згодом, в результаті появи досить ефективних реалізацій на ЕОМ, він став знаходити практичне використання в якості мови програмування.
В даний час основними діалектами мови є РЕФАЛ-2 (1970-ті), РЕФАЛ-5 (1985) і РЕФАЛ+ (1990), що відрізняються один від одного деталями синтаксису і набором «додаткових коштів», що розширюють початковий варіант.
Наступна програма на діалекті РЕФАЛ-5 звертає і друкує подається на вхід рядок даних: $ENTRY Go { = <Prout <Reverse <Card>>>; }
Наступна програма на діалекті РЕФАЛ-5 одержує на вході рядок даних, що представляє собою десяткове подання деякого натурального числа N, після чого обчислює і друкує число Фібоначчі з номером N: $ENTRY Go { = <Prout <Symb <FN <Numb <Card>>>>; }
