РЕФАЛ (РЕкурсивних Функцій АЛгоритмічна) — одна з найстаріших функційних мов програмування, орієнтована на так звані «символьні перетворення»: обробку символьних рядків (наприклад, алгебраїчні вирази); переклад з однієї мови (штучної або природної) на іншу; розв'язання задач, пов'язаних з штучним інтелектом. Поєднує в собі математичну простоту з практичною орієнтацією на написання великих і складних програм.

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

Програма на РЕФАЛі може складатись з одного або декількох модулів (файлів), кожен з яких, у свою чергу, складається з функцій.

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

Вирази мови РЕФАЛ являють собою послідовності термів, якими можуть виступати:

• Звичайні символи (літери, цифри тощо), які залежно від діалекту потрібно або не потрібно оточувати апострофами або лапками
• Символи-мітки (ідентифікатори, конкретний запис яких залежить від діалекту; так, в РЕФАЛ-5 ідентифікатором може бути довільна послідовність латинських літер і цифр, що починається з букви)
• Макроцифри — цифровий запис невід'ємних цілих чисел, що не перевищують граничне значення
• Числа з рухомою комою
• РЕФАЛ-змінні одного з декількох визначених типів
• Довільний вираз, оточений круглими дужками (в документації по РЕФАЛу такий терм називається виразом в структурних дужках)
• Довільний вираз, оточений «кутовими» дужками, означає виклик функції (такий терм називається активним виразом)

В залежності від ситуації на вирази можуть бути накладені обмеження; так, у зразках заборонено використовувати вирази, що містять кутові дужки, а в полі зору РЕФАЛ-машини не можуть бути присутніми змінні.

РЕФАЛ-змінні використовуються в зразках і залежно від свого типу можуть зіставлятися одному символу (тобто будь-якому терму, крім виразу в структурних дужках), одному терму (безпідставного), або безпідставного виразу (тобто послідовності термів довільної довжини). Відповідні типи змінних називаються S-змінними, T-змінними і E-змінними. У діалекті РЕФАЛ-2 підтримувалися ще й V-змінні, зіставлені безпідставного непорожній висловом; в сучасних діалектах такі змінні не підтримуються.

Семантика мови РЕФАЛ описана в термінах віртуальної машини, так званої «РЕФАЛ-машини» або «РЕФАЛ-автомату». Машина має поле зору, в якому може перебувати довільний РЕФАЛ-вираз, який не містить РЕФАЛ-змінних.

Виконання програми складається з кроків РЕФАЛ-автомата, на кожному з яких виконується застосування функції до виразу. Для цього РЕФАЛ-машина бере в своєму полі зору найлівіше з найвнутрішніх активних виразів; іншими словами, відшукуються парні кутові дужки, що не містять інших кутових дужок, а якщо таких пар є декілька, вибирається та з них, яка в полі зору знаходиться лівіше за решту. Перший терм виразу, вкладеного в кутові дужки, має бути символом-позначкою, що служить ім'ям функції; частина виразу, що залишилася, є аргументом функції.

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

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

Виконання програми закінчується, коли в полі зору РЕФАЛ-машини не виявиться більше кутових дужок. Вираз, що міститься в цей момент у полі зору, оголошується результатом виконання РЕФАЛ-програми.

Розглянемо найпростіший приклад виконання програми на РЕФАЛі. Нехай дана наступна функція:

  Palindrom {
      s.1 e.2 s.1 = <Palindrom e.2>;
      s.1 = True;
      = True;
      e.1 = False;
  }

Ця функція аналізує вираз і повертає як результат символ-позначку 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>>>;
}

Reverse
{
     e.Text = <DoReverse () e.Text>;
}

DoReverse
{
     (E.Scanned) = e.Scannded;
     (E.Scanned) s.Next e.Tail = <DoReverse (s.Next e.Scanned) e.Tail>;
}

Цю ж програму можна записати інакше:

$ ENTRY Go
{
     = <Prout <Reverse <Card>>>;
}

Reverse
{
     /* Якщо рядок не порожній, то переносимо перший символ в кінець */
     s.First e.Tail = <Reverse e.Tail> s.First;

     /* Обробка порожнього рядка */
     /* Порожньо */ = /* порожньо */;
}

Наступна програма на діалекті РЕФАЛ-5 отримує на вході рядок даних, що являє собою десяткове подання деякого натурального числа N, після чого обчислює і друкує число Фібоначчі з номером N:

$ ENTRY Go
{
     = <Prout <Symb <FN <Numb <Card>>>>;
}

FN
{
     /* Виклик допоміжної функції, в якій реалізовано залишково-рекурсивний цикл. */
     s.Number = <DoFN s.Number 0 1>;
}

/*
  Функція реалізує залишково-рекурсивний цикл.
  Інваріант циклу <DoFN s.Counter s.Current s.Next>
  s.Counter - кількість ітерацій, які лишились.
  s.Current - число Фібоначчі, відповідає поточній ітерації.
  s.Next - значення числа Фібоначчі на наступній ітерації.
* /
DoFN
{
     0 s.Current s.Next = s.Current;
     s.Counter s.Current s.Next =
          <DoFN <Sub s.Counter 1> s.Next <Add s.Current s.Next>>;
}

• Турчин В. Ф. Алгоритмический язык рекурсивных функций (РЕФАЛ). — М.: ИПМ АН СССР, 1968.
• Романенко С. А., Турчин В. Ф. РЕФАЛ-компилятор // Труды 2-й Всесоюзной конференции по программированию. — Новосибирск: ВЦ СО АН, 1970.
• Романенко С. А. Реализация Рефала-2. — М.: ИПМ АН СССР, 1987.
• Смирнов В.К. Аппаратная реализация языка Рефал в ИПМ им.М.В.Келдыша. — Препринты ИПМ им.М.В.Келдыша, 2003. — № 99. — С. 1-21.
• Гурин Р.Ф., Романенко С.А. Язык программирования Рефал Плюс. — Переславль : Университет города Переславля, 2006. — 13 с. — ISBN 5-901795-08-3.

• Сайт Рефал-спільноти
• Співдружність «РЕФАЛ / Суперкомпіляція»
• wiki-сайт, присвячений розвитку мови
• Самостійне вивчення РЕФАЛ-5. Погляд студента

Це незавершена стаття про мови програмування. Ви можете допомогти проєкту, виправивши або дописавши її.