Czym jest ta ułamkowa notacja „dyskretna matematyka” stosowana w formalnych regułach?

W artykule „Bezkonfliktowy zreplikowany typ danych JSON” napotkałem ten zapis do formalnego definiowania „reguł”:

Jak nazywa się ten zapis? Jak to czytać?

Na przykład:

• DOCreguła nie ma nic w „liczniku” - dlaczego nie?
• te EXECi GETzasady wydają się mieć dwa oddzielne terminy powyżej linii, co to znaczy?
• VARreguła wyróżnia się trochę, jak również, ponieważ podczas gdy wiele innych zasad użyć jakiegoś strzałką (który wziąłbym oznacza „implikuje”) do góry to tylko jeden zdaje się mówić, że x jest elementem czegoś.
• prawie wszystko jest przesycone inicjałem, Ap,który tekst opisuje jako „stan repliki p jest opisany przez Ap, skończona funkcja częściowa” - jak bystry czytelnik tego zapisu miał tendencję do „dostrzegania” tej części każdej reguły?

Ta strona zasugerowała powiązane pytanie, które ma bardzo podobny wygląd, w odniesieniu do pytania Jakie jest znaczenie „B, s⟩ -> ⟨B”, s'⟩ jako początkowej reguły w tym pytaniu o małym kroku semantyka? - jest to oznaczone jako semantyka operacyjna i wydaje się, że jest to silny trop. Czy rzeczywiście są to ramy, w których powinienem interpretować te liczby? Czy mógłbyś łatwo streścić to w formie „kursu awaryjnego”, aby nawet jeśli nie mogę zweryfikować poprawności ich dowodów, mógłbym przynajmniej lepiej zrozumieć, co mówią w tej sekcji?

Jest to standardowy zapis reguły wnioskowania . Pomieszczenia są umieszczone powyżej linii poziomej, a wnioski są umieszczone poniżej linii. W rezultacie wygląda to jak „ułamek”, ale z jednym lub kilkoma logicznymi zdaniami powyżej linii i pojedynczym zdaniem poniżej linii. Jeśli obok znajduje się etykieta (np. „LET” lub „VAR”), oznacza to, że jest to czytelna dla człowieka nazwa identyfikująca daną regułę.

Może to być również nazywane odliczeniem naturalnym lub odliczeniem naturalnym w stylu Gentzen .

Jest to powszechny zapis w literaturze dotyczącej języków programowania. Zobaczysz to wszędzie. Jest to bardzo wygodne dla tego rodzaju wniosków i dowodów o strukturze rekurencyjnej, które pojawiają się w tej dziedzinie.

Zobaczysz ten zapis używany do wyrażenia aksjomatów / reguł. Możesz myśleć o każdym aksjomacie jako szablonie z „meta-zmiennymi” (np. Expr ); możesz zastąpić każdą meta-zmienną jakąś składnią z języka programowania (np. dowolne wyrażenie, które jest poprawne w języku programowania), a otrzymasz instancję reguły. Reguła wnioskowania obiecuje, że jeśli wszystkie zdania znajdujące się powyżej linii są prawdziwe (w pewnym przypadku szablonu, w którym konsekwentnie zamieniasz każdą metazmowę na tę samą wartość w całej regule), to również zdanie poniżej wiersza będzie prawdziwe .

Oto bardzo nieformalne wyjaśnienie, które może pomóc osobom niezaznajomionym z formalnymi notacjami dostać się do drzwi. Nie zastępuje formalnej definicji!

Ap jest stan systemu lub programu z systemem. „Stan” może oznaczać wiele rzeczy, ale w tym przypadku wydaje się, że zawiera listę wszystkich zdefiniowanych zmiennych lokalnych i ich wartości. Dlaczego Ap jest funkcją? Ponieważ jest to wygodny sposób wyrażania przypisań zmiennych: Ap (x) podaje wartość zmiennej x .

Weźmy teraz za przykład regułę EXEC. Definiuje semantykę wykonywania polecenia cmd1, po którym następuje polecenie cmd2 , tj. Co dzieje się ze stanem Ap systemu podczas wykonywania cmd1, po którym następuje cmd2 .

• Powyżej linii: są to przesłanki. Co mówią: „Niech cmd1 będzie poleceniem. Jeśli wykonasz polecenie cmd1, gdy twój system jest w stanie Ap , twój system skończy w nowym stanie Ap” .
• Poniżej linii: tutaj reguła opisuje, co oznacza wykonywanie kolejno dwóch poleceń cmd1 i cmd2 . Co mówi: „Zakładając, że twój system jest w stanie Ap , wykonanie cmd1, a następnie cmd2 oznacza wykonanie cmd2, gdy twój system jest w stanie Ap ' ” (pamiętaj, że Ap' to stan, który otrzymujesz po uruchomieniu cmd1 , zgodnie z definicją w lokal).

Pozostałe reguły opisują semantykę poszczególnych poleceń i wyrażeń. Na przykład reguła VAR opisuje, co to znaczy „wykonać” zmienną: jeśli x jest zmienną lokalną (powyżej linii), co oznacza wycena / wykonanie zmiennej x ? Jest napisane poniżej linii: Gdy twój program jest w stanie Ap , ocena x daje ci wartość x , tj. Ap (x) .

Mam nadzieję że to pomogło.