Jaka jest różnica między przepisywaniem terminów a dopasowywaniem wzorców?

Ponieważ w Lambda Ultimate nie było odpowiedzi , próbuję tutaj jeszcze raz: systemy przepisywania terminów są używane na przykład w automatycznym twierdzeniu potwierdzającym obliczenia symboliczne i oczywiście do zdefiniowania gramatyki formalnej. Istnieje kilka języków programowania opartych na przepisywaniu terminów, ale o ile rozumiem, pojęcie to jest bardziej znane jako dopasowanie wzorca . Dopasowywanie wzorców jest często używane w językach funkcjonalnych. Barry Jay stworzył całą teorię zwaną rachunkiem wzorów , ale w skrócie wspomina o przepisywaniu terminów. Mam wrażenie, że wszystkie odnoszą się do tego samego podstawowego pomysłu, więc czy możesz używać synonimu przepisywania terminów i dopasowywania wzorców ?

Jednym ze sposobów spojrzenia na te dwie koncepcje jest stwierdzenie, że dopasowanie wzorców jest cechą języków programowania do łączenia dyskryminacji konstruktorów i niszczenia terminów (przy jednoczesnym wyborze i lokalnym nazewnictwie fragmentów terminów) w sposób bezpieczny, kompaktowy i wydajny. Badania nad dopasowaniem wzorców zazwyczaj koncentrują się na wydajności wdrażania, np. Na tym, jak zminimalizować liczbę porównań, które musi wykonać mechanizm dopasowywania.

W przeciwieństwie do tego, przepisywanie terminów jest ogólnym modelem obliczeń, który bada szeroki zakres (potencjalnie niedeterministycznych) metod zastępowania podwyrażeń wyrażeń składniowych (a dokładniej element algebry terminów w pewnym zbiorze zmiennych) innymi terminami. Badania nad systemami przepisywania terminów dotyczą zwykle abstrakcyjnych właściwości systemów przepisywania, takich jak zbieżność, determinizm i zakończenie, a dokładniej tego, w jaki sposób właściwości te są lub nie są zachowywane przez operacje algebraiczne w systemach przepisywania, tj. W jakim stopniu te właściwości są kompozycyjne.

$(l, r)$$C[l\sigma] \rightarrow C[r\sigma]$$C[.]$$\sigma$), podczas gdy dopasowywanie wzorców we współczesnych językach, takich jak Haskell, OCaml lub Scala, zapewnia tylko przepisywanie „na górze” terminu. Myślę, że to ograniczenie jest także nałożone w rachunku wzoru Jaya. Pozwól mi wyjaśnić, co rozumiem przez to ograniczenie. Dzięki dopasowaniu wzorców w sensie OCaml, Haskell, Scala nie można powiedzieć czegoś takiego

match M with
   | C[ x :: _ ]  -> printf "%i ...\n" x
   | C[ [] ] -> printf "[]"

Co C[.]tu jest To ma być zmienna, która rozciąga się na konteksty jednootworowe. Ale języki takie jak OCaml, Haskell lub Scala nie dają programistom zmiennych, które przekraczają dowolne konteksty (jednootworowe), a jedynie zmienne, które przekraczają wartości. Innymi słowy, w takich językach nie można dopasować wzoru na dowolnym miejscu w terminie. Zawsze musisz określić ścieżkę od katalogu głównego wzorca do interesujących cię części. Myślę, że głównym powodem nałożenia tego ograniczenia jest to, że w przeciwnym razie dopasowanie wzorca byłoby niedeterministyczne, ponieważ termin może pasować do wzorca w więcej niż jeden sposób. Na przykład termin (true, [9,7,4], "hello", 7)pasuje do wzorca C[7]na dwa sposoby, przy założeniu, że C[.] obejmuje takie konteksty.

Nie sądzę, aby nazywać je synonimami; nakładają się na siebie badania i wdrażanie. W ogóle nie jestem zaznajomiony z pracą Jaya i jestem tylko trochę zaznajomiony z systemami przepisywania terminów, więc może coś mi brakuje.

Dopasowywanie wzorców ogólnie zajmuje się następującym problemem: masz pewną strukturę (drzewo, listę lub multiset) i chcesz sprawdzić, czy struktura pasuje do wzorca (lub jednego z wielu wzorców). To pytanie z pewnością dotyczy przepisywania terminów, ponieważ w systemach do przepisywania terminów fakt, że termin pasuje do wzorca, oznacza, że ​​termin ten można przepisać na inny termin, ale nie jest to synonimiczne przepisywanie terminu. (Może być sformułowanie dopasowania wzorca jako przepisywanie: „Biorąc pod uwagę termin, możesz przepisać go, aby dopasować wzór?”, Ale nigdy tego nie widziałem.)

Dopasowywanie wzorców w funkcjonalnym języku programowania ma logiczną interpretację pod względem skupiania się (patrz na przykład „Koncentrowanie się na dopasowywaniu wzorów” Krishnaswamiego ). Z drugiej strony, systemy przepisywania terminów często dopasowują modulo do niektórych właściwości równania, które nie występują w większości funkcjonalnych języków programowania (nie można porównywać z wielodostępem w ML lub Haskell). Jednak nie ma podstawowego powodu, dla którego dopasowanie właściwości równań modulo nie powinno być obecne w językach funkcjonalnych.

(Wolę napisać to jako komentarz, ale obecnie nie mogę.)

Popraw mnie, jeśli się mylę, ale o ile rozumiem, jeszcze jedną różnicą między dopasowaniem wzorca a przepisywaniem terminów, oprócz tego, co powiedział Martin Berger w swojej doskonałej odpowiedzi , jest to, że reguły dopasowywania wzorca mają ustaloną kolejność (w implementacjach takich jak Haskell), podczas gdy w przypadku reguł przepisywania terminów niekoniecznie tak jest. Ta funkcja, jak można się spodziewać, może mieć duże znaczenie, jeśli wziąć pod uwagę zachowanie (w szczególności zakończenie) reguł (patrz „Delikatne wprowadzenie do Haskell, wersja 98” , na przykład sekcja 4.2 , lub po prostu silnia przykład w „Learn you a Haskell” ).

Ludzie bardziej znający się na teorii przepisywania mieliby więcej do powiedzenia na ten temat (na przykład, w jaki sposób pisanie pasuje dokładnie do takiego porównania?), Ale wydaje mi się, że zgadzam się z Martinem Bergerem, w tym znaczeniu przepisywanie może obejmować dopasowywanie wzorców (przynajmniej tak, jak jest to zaimplementowane w językach takich jak Haskell), w zakresie, w jakim oba można (raczej sucho) postrzegać jako urządzenia, które jedynie stosują reguły związane z terminami.