Nie jestem pewien, czy przyniesie ci to więcej niż już wiesz. Ale może nie rozumiem powodów, dla których zastanawiasz się nad przepisywaniem terminów. To pomaga.
Jak zapewne wiesz, gramatyki to systemy przepisywania ciągów. Na szczycie hierarchii Chomsky'ego znajdują się gramatyki typu 0, które definiują obliczenia rekurencyjnie policzalne (RE) i mają moc obliczeniową maszyn Turinga.
Oznacza to, że ogólnie systemy przepisywania mają wiele wspólnego z algorytmami wyrażania.
Problem z łańcuchami w ogóle polega na tym, że nie ma oczywistego sposobu na dołączenie do nich semantyki. Jest to rodzaj bezpostaciowego przepisywania.
To, co ludzie zazwyczaj są zainteresowani, to wyrażanie algorytmów w określonych domenach, które mają strukturę i właściwości. Domeny takie są często definiowane na podstawie elementarnych (atomowych) bytów i zamykane różnymi operacjami, być może ilorazowymi stosunkami równoważności i tak dalej. Są to często nazywane algebrami.
Domeny te są często abstrakcyjne. Ale obliczenia na ich elementach można wyrazić tylko na konkretnych reprezentacjach. Terminy są naturalną reprezentacją tych elementów, ponieważ wyrażają, w jaki sposób można uzyskać elementy dla innych elementów poprzez zastosowanie operacji, rekurencyjnie w dół do elementów atomowych (chociaż ogólne właściwości nie zawsze muszą iść w dół). Terminy są rodzajem składni struktury drzewa, którą można manipulować w celu wyrażenia algorytmów (tak jak w przypadku ciągu znaków). Ale struktura operandowa terminów pozwala również na powiązanie z nimi semantyki w jakiejś abstrakcyjnej dziedzinie za pomocą homomorfizmów.
Zamiast brać bardzo formalny pogląd na wikipedię i wiele tekstów na ten temat, wystarczy rozważyć programy. Zwykle uznaje się, że wygodną składnią reprezentacyjną programów jest tak zwane drzewo abstrakcyjnych składni (AST). Ale AST to tylko termin reprezentujący obiekt programu. Semantyka denotacyjna to sposób definiowania domen abstrakcyjnych i kojarzenia wartości z tych domen z AST (lub poddrzewami AST) za pomocą homomorfizmów. Programy w formie AST można przekształcić lub zoptymalizować, stosując reguły przepisywania (nie twierdzę, że wszystkie optymalizacje można lub należy wykonać w ten sposób).
Transformacja wyrażeń algebraicznych dla różnych celów może być wyrażona przez przepisywanie terminów. Na przykład uproszczenie niektórych wyrażeń. Różne typy obliczeń można również naturalnie wyrazić jako przepisywanie terminów, takie jak obliczanie pochodnych. Przepisywanie terminów jest również czasami używane do definiowania form kanonicznych w algebrach, gdy ta sama jednostka semantyczna może mieć kilka reprezentacji składniowych.
Radzę zajrzeć do artykułu w Wikipedii na ten temat .
