Refal - Refal

Refal
Paradygmat Dopasowywanie wzorców i przepisywanie terminów
Zaprojektowany przez Valentin Turchin
Deweloper Valentin Turchin, S. Florentsev, V. Olyunin, et al.
Po raz pierwszy pojawiły się 1968  ( 1968 )
Dyscyplina typowania mocny , dynamiczny
Stronie internetowej http://www.refal.net
Główne wdrożenia
Refal-2, Refal-5, Refal-6, Refal +

Refal ( „język algorytmiczny funkcji rekurencyjnych” ; rosyjski : РЕФАЛ ) „to funkcjonalny język programowania zorientowany na obliczenia symboliczne”, w tym „ przetwarzanie ciągów znaków , tłumaczenie języka , [i] sztuczna inteligencja ”. Jest to jeden z najstarszych członków tej rodziny, po raz pierwszy pomyślany w 1966 roku jako narzędzie teoretyczne, a pierwsza implementacja pojawiła się w 1968 roku. Celem Refal było połączenie matematycznej prostoty z praktycznością pisania dużych i wyrafinowanych programów.

Jeden z pierwszych funkcjonalnych języków programowania, który to robił, iw przeciwieństwie do ówczesnego Lispa , Refal opiera się na dopasowywaniu wzorców . Dopasowywanie wzorców działa w połączeniu z przepisywaniem terminów .

Podstawową strukturą danych Lispa i Prologu jest lista liniowa zbudowana przez działanie cons w sposób sekwencyjny, a więc z dostępem O (n) do n- tego elementu listy. Listy odwołań są budowane i skanowane z obu końców, przy czym dopasowywanie wzorców działa zarówno dla list zagnieżdżonych, jak i dla list najwyższego poziomu. W efekcie podstawową strukturą danych Refal jest raczej drzewo niż lista . Daje to swobodę i wygodę w tworzeniu struktur danych przy wykorzystaniu jedynie matematycznie prostych mechanizmów kontrolnych dopasowywania i podstawiania wzorców.

Refal zawiera również funkcję o nazwie zamrażarka, która wspiera wydajną częściową ocenę .

Refal można zastosować do przetwarzania i transformacji struktur drzewiastych, podobnie jak XSLT .

Podstawy

Przykład Refal Hello World pokazano poniżej. 

$ENTRY Go { = <Hello>;}
Hello {
   = <Prout 'Hello world'>;
}

Powyższy program zawiera dwie funkcje o nazwach Go i Hello. Funkcja jest zapisywana jako nazwa funkcji, po której następuje treść funkcji w nawiasach klamrowych. Funkcja Go jest oznaczona jako punkt wejścia programu za pomocą dyrektywy $ ENTRY.

Można by pomyśleć o wyrażeniach w ciałach funkcji jako o „wywołaniach” funkcji w składni podobnej do Lispa . Na przykład wydaje się, że funkcja Hello wywołuje wbudowaną funkcję Prout z argumentem „Hello world”. Jednak znaczenie i mechanizm wezwania są zupełnie inne. Aby zilustrować różnicę, rozważ następującą funkcję, która określa, czy ciąg jest palindromem . 

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

Ten przykład przedstawia funkcję o bardziej złożonej treści, składającą się z czterech zdań (klauzul). Zdanie zaczyna się od wzoru, po którym następuje znak równości, po którym następuje ogólne wyrażenie po prawej stronie. Zdanie kończy się średnikiem. Na przykład wzór drugiego zdania funkcji to „s.1”, a wyrażenie to „True”.

Jak widać na przykładzie, wzorce zawierają zmienne wzorcowe, które mają postać znaku identyfikującego typ zmiennej (do jakiej zmiennej pasuje), po którym następuje identyfikator zmiennej. Zmienne zaczynające się od „s” pasują do pojedynczego symbolu, a te, które zaczynają się od „e”, pasują do dowolnego wyrażenia. Identyfikator zmiennej może być dowolną sekwencją alfanumeryczną, opcjonalnie oddzieloną od identyfikatora typu kropką.

Funkcja jest wykonywana przez porównanie jej argumentu z wzorcami jej zdań w kolejności, w jakiej występują w definicji, aż do pierwszego pasującego wzorca. Następnie funkcja zastępuje argument wyrażeniem po prawej stronie dopasowanego zdania.

Jeśli wynik aplikacji funkcji zawiera podwyrażenie w nawiasach ostrych (tak jak będzie to miało miejsce po zastosowaniu trzeciego zdania naszego przykładu), wynik jest dalej przetwarzany przez Refal przez wywołanie funkcji oznaczonej pierwszym symbolem w nawiasach. Wykonywanie zatrzymuje się, gdy wynik nie ma już nawiasów ostrych do rozwinięcia w ten sposób.

Funkcję Pal można zatem odczytać nieformalnie jako: „Jeśli wyrażenie jest puste, zamień je na True. W przeciwnym razie, jeśli wyrażenie jest pojedynczym symbolem, zamień je na True. W przeciwnym razie, jeśli wyrażenie jest symbolem, po którym następuje dowolne wyrażenie e. 2, po którym następuje ten sam symbol, zamień je na wyrażenie <Pal e.2> (innymi słowy, wyrzuć dwa identyczne symbole na początku i na końcu i powtórz). W przeciwnym razie zamień wyrażenie na Fałsz (wzór e.1 zawsze pasuje). ”

Poniżej przedstawiono trzy ślady wykonywania krok po kroku z adnotacjami z numerami zdań stosowanymi w każdym kroku w celu utworzenia następnego 

 <Pal 'noon'>  (#3)
 <Pal 'oo'>    (#3)
 <Pal >        (#1)
 True

 <Pal 'wow'>   (#3)
 <Pal 'o'>     (#2)
 True

 <Pal 'revolver'>  (#3)
 <Pal 'evolve'>    (#3)
 <Pal 'volv'>      (#3)
 <Pal 'ol'>        (#4)
 False

Widzimy teraz, że przykład Hello World w rzeczywistości jest wykonywany jako sekwencja następujących przekształceń wyrażeń: 

      Seed the machine with the initial expression marked by $ENTRY:
 <Go >                 (apply the sentence in Go)
 <Hello >              (apply the sentence in Hello)
 <Prout 'Hello world'> (Prout is a built-in that prints and expands to nothing)
                       (nothing to apply; stop)

Inne przykłady

Factorial 

 Fact { 0 = 1;
    s.N = <* s.N <Fact <- s.N 1>>>; }

Tutaj 0 dopasowuje 0 do liczby i daje 1. Na każdym innym symbolu, który jest liczbą, pomnóż ją przez wynik (Fakt (- sN 1)) Zwróć uwagę na styl przedrostków operatorów.

Silnia z pętlami 

 Fact { s.n = <Loop s.n 1>; };
 Loop {
    0 s.f = s.f;
    s.n s.f = <Loop <- s.n 1> <* s.n s.f>>; }

Jak widać, sn działa jako licznik pętli.

Równość 

 Equal {
    (e.1)(e.1) = T;
    (e.1)(e.2) = F; }

Tutaj funkcja jest zdefiniowana jako, jeśli podane są dwa wyrazy, a warunki są takie same, to pierwsza klauzula pasuje i daje True. w przeciwnym razie druga klauzula pasuje i tworzy fałsz.

Ważną właściwością Refal jest to, że wszystkie funkcje w refal są jednym argumentem. (Ale można je rozłożyć na wyrażenia w powyższym wyrażeniu).

Gdyby

Definiowanie struktur sterowania jest łatwe 

 If {
    T Then (e.1) Else (e.2) = e.1;
    F Then (e.1) Else (e.2) = e.2;  }

Tutaj e1 jest obliczane tylko wtedy, gdy wprowadzone wyrażenie pasuje do „True”. Następnie e1 Else e2 jest takie samo dla e2.

Ściśnij puste miejsca 

 Squeeze {
    e.1'__'e.2 = <Squeeze e.1'_'e.2>;
    e.1 = e.1; }

(Użycie znaku „_” zamiast znaku spacji, aby wywołanie funkcji było wyraźne). Pierwsza klauzula jest dopasowywana za każdym razem, gdy funkcja Squeeze napotka podwójne spacje w swoim wyrażeniu wejściowym i zastępuje ją pojedynczym odstępem. Druga klauzula pasuje tylko wtedy, gdy pierwsza nie, i zwraca wynikową wartość, która jest bieżącym wyrażeniem.

Ściśnij używając jawnej pętli 

 Squeeze {
    '__'e.1 = <Squeeze '_'e.1>;
    s.A e.1 = s.A <Squeeze e.1>;
    = ; };

Bibliografia

  • Turchin, Valentin F. (1989). „Instrukcja programowania i instrukcja obsługi REFAL-5” . City College of New York, New England Publishing Co., Holyoke.

Zewnętrzne linki