Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
РЕФАЛ (РЕкурсивних Функцій АЛгоритмічна) — одна з найстаріших функційних мов програмування, орієнтована на так звані : обробку символьних рядків (наприклад, алгебраїчні вирази); переклад з однієї мови (штучної або природної) на іншу; розв'язання задач, пов'язаних з штучним інтелектом. Поєднує в собі математичну простоту з практичною орієнтацією на написання великих і складних програм.
Відмінною рисою мови є використання зіставлення зі зразком як основного способу визначення функцій.
Основні принципи
Програма на РЕФАЛі може складатись з одного або декількох модулів (файлів), кожен з яких, у свою чергу, складається з функцій.
РЕФАЛ-функція являє собою упорядкований набір речень, що складаються зі зразка і шаблону. На вхід функції подається деякийвираз; обчислення функції полягає в зіставленні виразу по черзі зі зразками, взятих з першого, другого і т. д. речень. Якщо чергове зіставлення проходить успішно, то на підставі шаблону, взятого з того ж речення, формується новий РЕФАЛ-вираз, який і буде результатом функції. Якщо з жодним із наявних зразків аргумент функції зіставити не вдалося (невдача), фіксується помилка (аварійно завершується вся програма). Щоб уникнути цього часто наприкінці функції поміщають речення, зі зразком якого можна зіставити довільний вираз. В деяких сучасних реалізаціях РЕФАЛ (наприклад, РЕФАЛ) невдача будь-якого виразу функції замість помилки призводить повернення невдачі як результат виконання функції.
Вирази мови РЕФАЛ являють собою послідовності термів, якими можуть виступати:
- Звичайні символи (літери, цифри тощо), які залежно від діалекту потрібно або не потрібно оточувати апострофами або лапками
- Символи-мітки (ідентифікатори, конкретний запис яких залежить від діалекту; так, в РЕФАЛ-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 с. — .
Посилання
- Сайт Рефал-спільноти
- Співдружність «РЕФАЛ / Суперкомпіляція»
- wiki-сайт, присвячений розвитку мови
 | Це незавершена стаття про мови програмування. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
REFAL REkursivnihFunkcij ALgoritmichna odna z najstarishih funkcijnih mov programuvannya oriyentovana na tak zvani obrobku simvolnih ryadkiv napriklad algebrayichni virazi pereklad z odniyeyi movi shtuchnoyi abo prirodnoyi na inshu rozv yazannya zadach pov yazanih z shtuchnim intelektom Poyednuye v sobi matematichnu prostotu z praktichnoyu oriyentaciyeyu na napisannya velikih i skladnih program Vidminnoyu risoyu movi ye vikoristannya zistavlennya zi zrazkom yak osnovnogo sposobu viznachennya funkcij Osnovni principiPrograma na REFALi mozhe skladatis z odnogo abo dekilkoh moduliv fajliv kozhen z yakih u svoyu chergu skladayetsya z funkcij REFAL funkciya yavlyaye soboyu uporyadkovanij nabir rechen sho skladayutsya zi zrazka i shablonu Na vhid funkciyi podayetsya deyakijviraz obchislennya funkciyi polyagaye v zistavlenni virazu po cherzi zi zrazkami vzyatih z pershogo drugogo i t d rechen Yaksho chergove zistavlennya prohodit uspishno to na pidstavi shablonu vzyatogo z togo zh rechennya formuyetsya novij REFAL viraz yakij i bude rezultatom funkciyi Yaksho z zhodnim iz nayavnih zrazkiv argument funkciyi zistaviti ne vdalosya nevdacha fiksuyetsya pomilka avarijno zavershuyetsya vsya programa Shob uniknuti cogo chasto naprikinci funkciyi pomishayut rechennya zi zrazkom yakogo mozhna zistaviti dovilnij viraz V deyakih suchasnih realizaciyah REFAL napriklad REFAL nevdacha bud yakogo virazu funkciyi zamist pomilki prizvodit povernennya nevdachi yak rezultat vikonannya funkciyi Virazi movi REFAL yavlyayut soboyu poslidovnosti termiv yakimi mozhut vistupati Zvichajni simvoli literi cifri tosho yaki zalezhno vid dialektu potribno abo ne potribno otochuvati apostrofami abo lapkami Simvoli mitki identifikatori konkretnij zapis yakih zalezhit vid dialektu tak v REFAL 5 identifikatorom mozhe buti dovilna poslidovnist latinskih liter i cifr sho pochinayetsya z bukvi Makrocifri cifrovij zapis nevid yemnih cilih chisel sho ne perevishuyut granichne znachennya Chisla z ruhomoyu komoyu REFAL zminni odnogo z dekilkoh viznachenih tipiv Dovilnij viraz otochenij kruglimi duzhkami v dokumentaciyi po REFALu takij term nazivayetsya virazom v strukturnih duzhkah Dovilnij viraz otochenij kutovimi duzhkami oznachaye viklik funkciyi takij term nazivayetsya aktivnim virazom V zalezhnosti vid situaciyi na virazi mozhut buti nakladeni obmezhennya tak u zrazkah zaboroneno vikoristovuvati virazi sho mistyat kutovi duzhki a v poli zoru REFAL mashini ne mozhut buti prisutnimi zminni REFAL zminni vikoristovuyutsya v zrazkah i zalezhno vid svogo tipu mozhut zistavlyatisya odnomu simvolu tobto bud yakomu termu krim virazu v strukturnih duzhkah odnomu termu bezpidstavnogo abo bezpidstavnogo virazu tobto poslidovnosti termiv dovilnoyi dovzhini Vidpovidni tipi zminnih nazivayutsya S zminnimi T zminnimi i E zminnimi U dialekti REFAL 2 pidtrimuvalisya she j V zminni zistavleni bezpidstavnogo neporozhnij vislovom v suchasnih dialektah taki zminni ne pidtrimuyutsya Semantika movi REFAL opisana v terminah virtualnoyi mashini tak zvanoyi REFAL mashini abo REFAL avtomatu Mashina maye pole zoru v yakomu mozhe perebuvati dovilnij REFAL viraz yakij ne mistit REFAL zminnih Vikonannya programi skladayetsya z krokiv REFAL avtomata na kozhnomu z yakih vikonuyetsya zastosuvannya funkciyi do virazu Dlya cogo REFAL mashina bere v svoyemu poli zoru najlivishe z najvnutrishnih aktivnih viraziv inshimi slovami vidshukuyutsya parni kutovi duzhki sho ne mistyat inshih kutovih duzhok a yaksho takih par ye dekilka vibirayetsya ta z nih yaka v poli zoru znahoditsya livishe za reshtu Pershij term virazu vkladenogo v kutovi duzhki maye buti simvolom poznachkoyu sho sluzhit im yam funkciyi chastina virazu sho zalishilasya ye argumentom funkciyi Yak bulo skazano vishe sered rechen yaki skladayut funkciyu znahoditsya pershe take zrazok yakogo mozhna zistaviti z argumentom funkciyi v hodi zistavlennya pripisuyutsya znachennya zminnim sho mistyatsya v zrazku Potim shablon vzyatij z togo zh rechennya beretsya za osnovu dlya formuvannya rezultatu obchislennya funkciyi prosto kazhuchi rezultatom ogoloshuyetsya viraz otrimanij z shablonu zaminoyu zminnih na yih znachennya Neobhidno vidznachiti sho shablon mozhe mistiti tilki zminni nayavni u zrazku takim chinom vsi zminni sho vhodyat u shablon pri formuvanni rezultatu budut zamineni na vidpovidni vislovi i rezultat zminnih vzhe mistiti ne bude Z inshogo boku shablon cilkom mozhe mistiti virazi v kutovih duzhkah Na zavershennya kroku REFAL avtomat zaminyuye u svoyemu poli zoru shojno otrimanij aktivnij viraz razom z kutovimi duzhkami yaki jogo otochuyut na otrimanij v hodi obchislennya funkciyi rezultat Slid zaznachiti sho kilkist kutovih duzhok sho znahodyatsya v poli zoru REFAL mashini mozhe pri comu i zrosti Vikonannya programi zakinchuyetsya koli v poli zoru REFAL mashini ne viyavitsya bilshe kutovih duzhok Viraz sho mistitsya v cej moment u poli zoru ogoloshuyetsya rezultatom vikonannya REFAL programi Priklad vikonannyaRozglyanemo najprostishij priklad vikonannya programi na REFALi Nehaj dana nastupna funkciya Palindrom s 1 e 2 s 1 lt Palindrom e 2 gt s 1 True True e 1 False Cya funkciya analizuye viraz i povertaye yak rezultat simvol poznachku True yaksho viraz ye palindromom i False v protilezhnomu vipadku Funkciya maye im ya Palindrom Tut s 1 zminna S tipu e 1 ta e 2 zminni E tipu Takim chinom tilo funkciyi skladayetsya z chotiroh rechen pershe z yakih spracyuye yaksho argument funkciyi ye virazom sho pochinayetsya i zakinchuyetsya odnim i tim samim simvolom druge bude vikonano yaksho argument skladayetsya rivno z odnogo simvolu tretye zadiyuyetsya dlya porozhnogo argumentu i nareshti chetverte pidijde dlya vsih inshih vipadkiv Vidznachimo sho shablon v pershomu rechenni mistit aktivnij viraz sho yavlyaye soboyu rekursivnij viklik funkciyi Palindrom Ce vidobrazhaye toj fakt sho yaksho pershij ta ostannij simvoli odnakovi yih mozhna vidkinuti i pereviriti na palindromnist reshtu virazu Nehaj v poli zoru REFAL avtomata bude nastupnij aktivnij viraz lt Palindrom abcba gt Todi vikonannya bude skladatisya z troh krokiv pislya yakih v poli zoru budut taki virazi lt Palindrom bcb gt lt Palindrom c gt True Na pershih dvoh krokah bulo zastosovane pershe rechennya na ostannomu kroci druge Oskilki pislya tretogo kroku pole zoru bilshe ne mistit kutovih duzhok robota REFAL avtomata na comu zavershuyetsya IstoriyaPersha versiya REFAL bula stvorena v 1966 roci Valentinom Turchinom yak metamova dlya opisu semantiki inshih mov Zgodom vnaslidok poyavi dosit efektivnih realizacij na EOM stala znahoditi praktichne vikoristannya yak mova programuvannya Narazi osnovnimi dialektami movi ye REFAL 2 1970 ti REFAL 5 1985 i REFAL 1990 yaki vidriznyayutsya detalyami sintaksisu i naborom dodatkovih zasobiv sho rozshiryuyut pochatkovij variant Prikladi programNastupna programa na dialekti REFAL 5 obertaye navpaki i drukuye podanij na vhid ryadok ENTRY Go lt Prout lt Reverse lt Card gt gt gt Reverse e Text lt DoReverse e Text gt DoReverse E Scanned e Scannded E Scanned s Next e Tail lt DoReverse s Next e Scanned e Tail gt Cyu zh programu mozhna zapisati inakshe ENTRY Go lt Prout lt Reverse lt Card gt gt gt Reverse Yaksho ryadok ne porozhnij to perenosimo pershij simvol v kinec s First e Tail lt Reverse e Tail gt s First Obrobka porozhnogo ryadka Porozhno porozhno Nastupna programa na dialekti REFAL 5 otrimuye na vhodi ryadok danih sho yavlyaye soboyu desyatkove podannya deyakogo naturalnogo chisla N pislya chogo obchislyuye i drukuye chislo Fibonachchi z nomerom N ENTRY Go lt Prout lt Symb lt FN lt Numb lt Card gt gt gt gt FN Viklik dopomizhnoyi funkciyi v yakij realizovano zalishkovo rekursivnij cikl s Number lt DoFN s Number 0 1 gt Funkciya realizuye zalishkovo rekursivnij cikl Invariant ciklu lt DoFN s Counter s Current s Next gt s Counter kilkist iteracij yaki lishilis s Current chislo Fibonachchi vidpovidaye potochnij iteraciyi s Next znachennya chisla Fibonachchi na nastupnij iteraciyi DoFN 0 s Current s Next s Current s Counter s Current s Next lt DoFN lt Sub s Counter 1 gt s Next lt Add s Current s Next gt gt LiteraturaTurchin V F Algoritmicheskij yazyk rekursivnyh funkcij REFAL M SSSR 1968 Romanenko S A Turchin V F REFAL kompilyator Trudy 2 j Vsesoyuznoj konferencii po programmirovaniyu Novosibirsk VC SO AN 1970 Romanenko S A Realizaciya Refala 2 M IPM AN SSSR 1987 Smirnov V K Apparatnaya realizaciya yazyka Refal v IPM im M V Keldysha Preprinty IPM im M V Keldysha 2003 99 S 1 21 Gurin R F Romanenko S A Yazyk programmirovaniya Refal Plyus Pereslavl Universitet goroda Pereslavlya 2006 13 s ISBN 5 901795 08 3 PosilannyaSajt Refal spilnoti Spivdruzhnist REFAL Superkompilyaciya wiki sajt prisvyachenij rozvitku movi Ce nezavershena stattya pro movi programuvannya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi