Рефал (акроним от слов «рекурсивных функций алгоритмический») — один из старейших функциональных языков программирования, ориентированный на символьные вычисления: обработку символьных строк (например, алгебраические выкладки); перевод с одного языка (искусственного или естественного) на другой; решение проблем, связанных с искусственным интеллектом. Соединяет в себе математическую простоту с практической направленностью на написание больших и сложных программ.
Отличительной чертой языка является использование сопоставления с образцом и переписывания термов как основного способа определения функций.
Программа на Рефале может состоять из одного или нескольких модулей (файлов), каждый из которых, в свою очередь, состоит из функций.
Рефал-функция — упорядоченный набор предложений, состоящих из образца и шаблона. На вход функции подаётся некоторое выражение; вычисление функции состоит в сопоставлении выражения поочерёдно образцам, взятым из первого, второго и дальнейших предложений. Если очередное сопоставление проходит успешно, то на основании шаблона, взятого из того же предложения, формируется новое рефал-выражение, которое и будет результатом функции. В случае, если ни с одним из имеющихся образцов аргумент функции сопоставить не удалось (неуспех), фиксируется ошибка (аварийно завершается вся программа). Во избежание этого часто в конце функции помещают предложение, с образцом которого можно сопоставить вообще произвольное выражение. В некоторых современных реализациях Рефала (например, Рефал+) неуспех любого выражения функции вместо ошибки порождает неуспех самой функции.
Выражения языка Рефал представляют собой последовательности термов, в качестве которых могут выступать:
В зависимости от ситуации на выражение могут быть наложены ограничения; так, в образцах запрещено использовать выражения, содержащие угловые скобки, а в «поле зрения» рефал-машины не могут присутствовать переменные.