Czy semantyka TeXa (jako języka programowania) została kiedykolwiek sformalizowana?

Wydaje mi się, że język makr używany przez może być postrzegany jako pewnego rodzaju system przepisywania terminów lub jakiś język programowania z określaniem zakresu według nazw.$\TeX$

Nawet współczesne implementacje silnika (np. ) interpretują kod w dość bezpośredni sposób i nie jestem świadomy żadnej próby optymalizacji wykonania (tak jak mogą to zrobić współczesni tłumacze optymalizujący). Jednak opracowanie poprawnych poprawek optymalizacji dla języka takiego jak będzie bardzo trudne ze względu na „działanie na odległość”, które mogą mieć redefinicje makr, oraz możliwość ponownego zdefiniowania makr przez wywołanie ich po imieniu.$\TeX$$\mathit{Xe}\TeX$$\TeX$

Dlatego implementacja hipotetycznego interpretera optymalizującego dla wydaje się bardzo trudnym problemem w praktyce, ale także bardzo przydatnym, ponieważ jest używany w matematyce i nauce, a wolne czasy kompilacji są znaną wadą systemu. Zauważ, że większość czasu spędza się na interpretowaniu kodu, a nie na obliczaniu rzeczywistego składu tekstu, zwłaszcza gdy używane są ciężkie obliczeniowo pakiety (takie jak ).$\TeX$$\TeX$tikz

Może formalna semantyka języka może być początkiem rozwiązania problemu. Czy semantyka języka programowania została kiedykolwiek sformalizowana?$\TeX$

(Przepraszam za długą odpowiedź, która idzie w innym kierunku niż zakres strony: szczerze mówiąc, zdziwiłem się, widząc pytanie tutaj przede wszystkim…)

TeX został zaprojektowany do składu, a nie do programowania; więc jest co najwyżej „dziwne”, gdy jest uważane za język programowania.

- Donald Knuth, Typografia cyfrowa, strona 235

W ciągu ostatnich kilku lat dużo czytałem o wczesnej historii TeXa (około 1977 r.) I wiele z tego, co napisał Knuth. Doszedłem do wniosku, że w momencie, gdy mówimy o „TeX (jako języku programowania)” , coś już jest nie tak.

Jeśli spojrzymy na wczesne „dokumenty projektowe” napisane wcześniej dla TeXa (zobacz TEXDR.AFTi TEX.ONEopublikowane w Cyfrowej Typografii ), jasne jest, że Knuth zaprojektował system przeznaczony przede wszystkim do pisania Art of Computer Programming (powiedział (np. Tutaj ) że głównymi użytkownikami, o których myślał, byli on i jego sekretarka), z myślą, że odpowiednio zmodyfikowana może być użyteczniejsza bardziej ogólnie. Aby zaoszczędzić na pisaniu, w przypadku rzeczy, które trzeba było wielokrotnie robić (np. Za każdym razem, gdy TAOCP potrzebował dołączyć cytat od autora, chciałbyś poruszać się w pionie o określoną liczbę, ustawić określony pomijanie linii, wybrać określoną czcionkę, wpisać cytat wyrównany do prawej, wybierz inną czcionkę, wpisz nazwisko autora…), były makra.

Możesz odgadnąć resztę. To, co mamy w TeX, to przypadek „przypadkowego ukończenia Turinga” ( więcej ), z tym wyjątkiem, że zdarzyło się to pośród społeczności (informatyków i matematyków, a także sam DEK jest „winny”), którzy byli (niestety) zbyt sprytny, aby to zignorować. (Legenda głosi, że Michael Spivak nigdy nie programował przed spotkaniem z TeX-em, ale był tak zachwycony, że skończył pisaniem AMS-TeX, w tym czasie jednego z najbardziej skomplikowanych zestawów makr.) Ponieważ TeX został napisany aby być przenośnym w wielu systemach (co było wtedy wielką sprawą), zawsze istniała pokusa, aby zrobić wszystko w TeX-ie. Poza tym, ze względu na jego doświadczenie w pisaniu kompilatorów, Knuth napisał TeX jak kompilator i czasami opisywał go jako jeden, a jeśli program, który działa na twoich danych wejściowych, jest „kompilatorem”, to na pewno programujesz, prawda?

Możesz przeczytać nieco więcej o tym, że Knuth nie zamierzał programować w TeXie i jak „włączył wiele funkcji programistycznych TeXa dopiero po kopnięciu i krzyku”, w tej odpowiedzi . Bez względu na to, jakie były jego intencje, jak powiedziałem, ludzie zaczęli wymyślać sposoby (ab) korzystania z systemu makr TeX do osiągania zaskakujących wyczynów programistycznych. Knuth uznał to za fascynujące i (oprócz dodania niektórych funkcji do samego TeX-a) umieścił kilka z nich w dodatku D „Brudne sztuczki” TeXbooka, ale okazuje się, pomimo nazwy, że „dziewięć na dziesięć przykładów w nim jest wykorzystywane przy wdrażaniu LaTeX ”.

Powiem inaczej: LaTeX, system makr, który Leslie Lamport napisał na TeXie jako pomysł , jest świetny. Tworzenie dokumentów w semantyczny, uporządkowany, zorientowany na człowieka sposób, a nie (Knuth) TeX-owy zorientowany na stronę (lub jak to nazwał Lamport, logiczny, a nie wizualny ) jest świetny. Jednak implementacja czegoś tak skomplikowanego jak LaTeX przy użyciu makr TeX zamiast w „właściwym” języku programowania jest, moim zdaniem, a przynajmniej gdyby dokonano go dzisiaj, gdzieś pomiędzy gigantyczną pomyłką a aktem bezmyślnej perwersji. Nawet Knuth jest zszokowany, że ludzie nie tylko rozszerzają program TeX zamiast robić wszystko w makrach TeX.

Obecnie istnieją znacznie lepsze sposoby „programowania”; możesz używać zewnętrznego programu w dowolnym z wielu języków powszechnie dostępnych na komputerach większości ludzi lub możesz używać LuaTeX i programu w Lua (i wykonywać lepszą pracę niż kiedykolwiek z samych makr TeX, ponieważ możesz manipulować strukturami wewnętrznymi i algorytmy na właściwym poziomie). A jeśli zrobisz to dobrze, możesz mieć programy działające lepiej lub szybciej niż te zaimplementowane w makrach TeX.

Zadanie przyspieszania programów w TeX-ie jest prawie zabawne, gdy patrzy się w tym świetle, i przypomina mi ostatnie słowa artykułu opisujące inny „język przypadkowo Turinga kompletnego”: „piękny” Tom Wildenhaina „ O kompletności Turinga MS PowerPoint ( wideo ) z zeszłego roku:

Chociaż PPTXTM potwierdza teoretyczną możliwość rozwoju PowerPoint, […]. Należy również wykonać prace związane z optymalizacją aplikacji PowerPoint. Istnieje tutaj duży potencjał do wykorzystania automatycznego buforowania następnego slajdu w programie PowerPoint, który poprzez staranne umieszczenie slajdu może być użyty do znacznego zwiększenia wydajności aplikacji.

Anegdota, że Lipton opis ma charakter przykładowy. Nie tylko nigdy nie istniała formalna semantyka TeXa, ale jest też mało prawdopodobne, aby była. Jest to po prostu zbyt „dziwny” „język”, a (jak mam nadzieję wyjaśniłem powyżej) nie jest on nawet zamierzony jako język. Na przykład możesz pomyśleć, że piszesz makra jako funkcje, ale wprowadzasz do niego pojedynczy znak zbłąkany (nawet spację ), a TeX natychmiast traktuje go jako instrukcję składu.

W skrócie: TeX powraca do składu przy najbliższej okazji, a kiedy rozwija makra, robi to niechętnie (niecierpliwie, aby przejść do „prawdziwej” pracy w składaniu), a te rozszerzenia mogą same zależeć od setek rodzajów „stanu” w obrębie program TeX (wartości parametrów takich jak \hsizelub \baselineskipzawartość pól i innych rejestrów…), dlatego każda formalna semantyka TeX musi koniecznie być czymś, co uwzględnia cały stan programu i całą jego pamięć, dopóki nie kończy się czymś w rodzaju „znaczenie kodu TeX jest tym, co robi TeX”, w formie bardziej złożonej niż sam program TeX.

Tak dobrze, (jeśli cię przekonałem) TeX nie został zaprojektowany jako język programowania i nie działa jak prawdziwy, nie ma formalnej semantyki i istnieją lepsze sposoby programowania dzisiaj - ale to wszystko nie pomaga w twoim rzeczywista pytanie / problem, który jest, że w praktyce wiele dokumenty przeznaczone do przetwarzania przez TeX zrobić użytku skomplikowane makra (jak lateksu i TikZ), wspaniałe budowle z potwornym złożoności zbudowany na szczycie siebie. Jak możemy przyspieszyć i opracować „przebiegi optymalizacyjne”?

Nie dostaniesz się tam z formalną semantyką IMO. Ostatnio o tym myślałem, a poniżej znajdują się wstępne przemyślenia.

Mam wrażenie, że Knuth był jednym z doświadczonych autorów kompilatorów w latach 60. XX wieku (dlatego poproszono go o napisanie książki o kompilatorach, która przerodziła się w sztukę programowania komputerowego ), a TeX (pod wieloma względami) jest napisany tak, jak kompilatory były powiedzmy napisane w latach 70. Od tego czasu poprawiły się techniki i konstrukcja kompilatora, podobnie jak program TeX. Oto kilka rzeczy, które można zrobić, przyspieszając:

• Zasadniczo TeX jest napisany jak „procedura interpretacyjna”, w której „oczy” i „usta” TeXa (jego procedury wprowadzania) dostarczają instrukcje do „żołądka” (jego procedur semantycznych), które mają być wykonywane jeden po drugim. (Możesz zobaczyć listę w części 15 programu TeX .) Na przykład, gdy oczy / usta TeXa napotkają \hfilllub \hskipna wejściu, żołądek otrzymuje polecenie „hskip”, na które działa. Jest to podobne do tego, co dziś nazywane są interpreterami kodu bajtowego, a refaktoryzacja programu TeX może mieć wartość, aby jawnie emitować te kody bajtowe / opcody, abyśmy mogli być w stanie wykorzystać istniejące (bardziej konwencjonalne dzisiaj) techniki kompilatora. Lub przynajmniej buforuj je, aby uniknąć ponownego wykonywania pracy. Istnieje oczywiście wiele wyzwań:

  • Wykonanie polecenia w „żołądku” zwykle nadal wymaga odczytu danych wejściowych, tzn. Działanie procedur wejściowych i procedur semantycznych nie odbywa się w oddzielnych fazach. Np. Polecenie „hskip”, jeśli zostanie podane \hskip(a nie powiedz \hfill), spowoduje scan_gluewczytanie specyfikacji kleju z danych wejściowych, co z kolei może obejmować rozwijanie makr i tak dalej, aż do znalezienia wystarczającej liczby tokenów dla kleju, pozostawiając stos wejściowy w zasadniczo inny stan.

  • Silniki takie jak eTeX i pdfTeX oraz XeTeX i LuaTeX wprowadzają nowe polecenia i prymitywy (prymitywy eTeX / pdfTex są praktycznie używane przez wszystkich w praktyce); musisz je również wspierać, nie tylko te z oryginalnego programu TeX firmy Knuth.

• Możemy zrobić coś takiego jak „wykonanie spekulatywne”, przetwarzając przyszłe akapity (być może zaczynając od naturalnych punktów kontrolnych, takich jak nowe sekcje lub rozdziały) równolegle (używając wielu rdzeni), śledząc cały wewnętrzny stan TeX, którego używają (zależą od), i rzucając odejście od tej pracy (i powtórzenie jej), jeśli później dowiemy się, że wcześniejszy akapit ostatecznie zmienia część tego stanu. W tej chwili TeX działa całkowicie sekwencyjnie na 1 procesorze; typowy sprzęt przesunął się w innym kierunku i dostępnych jest wiele rdzeni.

• Jeszcze prościej, możemy po prostu buforować pracę (do jakiego stanu TeXa uzyskano dostęp i modyfikację) przez pewną sekcję pliku wejściowego. (Możemy to buforować na poziomie danych wejściowych - wynik netto rozwinięcia wszystkich makr - lub na poziomie zestawu pudełek, które zostały złożone lub aż do całkowitego stanu programu). Np. Zawartość wewnątrz \begin{tikzpicture} … \end{tikzpicture}jest mało prawdopodobne, aby zależeć dużo na stanie tex lub podobna widoku numer licznika, więc kiedy skompilować dokument TeX możemy po prostu ponownie wykorzystać całą pracę - jeśli mamy śledził wystarczających informacji, aby wiedzieć, że jest to bezpieczne. (Oczywiście TikZ w szczególności ma sposoby na uzewnętrznienie tego i uwzględnienie wyników, ale pomysł jest bardziej ogólny.)

• Możemy użyć technik (np. Stosowanych w programowaniu funkcjonalnym), aby wykonać niektóre przetwarzanie TeX-a z „dziurami” - np. Teraz, kiedy piszesz \ref{foo}w LaTeX-u, aby odwołać się do (powiedzmy, przyszłego) numeru sekcji, działa to tylko w dwóch przebiegach kompilacji: najpierw przetwarzany jest cały dokument (wszystkie składane akapity, zmiennoprzecinkowe umieszczone na stronach itp.) z numerami sekcji zapisywanymi do pliku pomocniczego, a następnie przy drugim przejściu wszystkiepraca jest wykonywana ponownie, tym razem numer sekcji jest faktycznie dostępny. (Tego rodzaju włamanie mogło być w tym czasie nieuniknione i wiem, że wpływ na czas działania jest „tylko stały czynnik”, ale…). Zamiast tego, gdybyśmy mogli po prostu przetworzyć dokument z „dziurą” ( pole z nieokreśloną zawartością, ale z pewną szacunkową szerokością) pozostawione dla numeru sekcji, a następnie na końcu przetwarzania dokumentu wypełnić pole? (Tak, nasza szacunkowa szerokość może się nie powieść, a akapit może wymagać ponownego przetworzenia, a w konsekwencji nawet strony, ale możemy albo wykonać pracę, jeśli to konieczne, albo zaakceptować, dla prędkości, tryb, w którym zezwolimy na niewłaściwą szerokość dla numer sekcji).

• Podobne techniki mogą działać w przypadku interaktywnej edycji dokumentu TeX: kiedy edytujesz akapit, można go przetwarzać „na żywo”, a przyszłe akapity po prostu przesuwają się w dół (powiedzmy). Wiemy, że jest to możliwe, ponieważ istnieją już (komercyjne) implementacje TeX, które to robią, np. BaKoMaTeX i Texpad oraz poprzednie tekstury . (Zobacz wideo na stronie głównej BaKoMa-TeX i podobnie TeXpada, np. Ten film - wypróbowałem ten drugi i był to jednak nieznośny błąd w praktyce.)

• Nie można tego nie docenić: wartość pokazywania rzeczy użytkownikowi, czyniąc TeX bardziej debugowalnym. W tej chwili użytkownicy widzą tylko swoje dane TeXa i nie mają pojęcia, co dokładnie robi TeX, np. Ile czasu spędza na łamanie wierszy akapitów lub na rozwijanie makr (i jakich makr), jakie pola montuje i wyrzucając, jakie specjalności są zapisywane przez jaki pakiet, itp. Wierzę (być może optymistycznie), że istnieją użytkownicy, którzy chcieliby zobaczyć te informacje i przydadzą się, np. aby wiedzieć, czy dziwny pakiet używają do cieniowania równania z gradientem w tle są tanie (niewiele dodając do czasu przetwarzania) lub nie. Widząc, gdzie wykonuje się dużo marnotrawnej pracy, mogą ją wyrzucić (przynajmniej do czasu ostatecznego wydrukowania). (To trochę przypomina kompilatory lub inne narzędzia wstawiające informacje profilujące do programów.) Zwiększenie przejrzystości i debugowania TeXa może na przykład znacznie poprawić użyteczność. (TeX jest już bardzo przyjazny dla użytkownika i na razie można go debugować IMO, jeśli używamy głównie zwykłego TeXa z bardzo małą liczbą makr, ale nie z LaTeX lub w jaki sposób większość użytkowników napotyka go dzisiaj.)

Ponadto wszelkie przyszłe prace powinny prawdopodobnie uwzględniać (budować) LuaTeX, który jest najlepszą modyfikacją TeXa, jaką mamy obecnie.

Wszystko to są po prostu bezmyślne myśli (nie wdrożyłem żadnego z nich, aby wiedzieć, jaki wysiłek lub ile przyspieszenia byśmy osiągnęli), ale mam nadzieję, że to w pewnym stopniu odpowiada na twoje pytanie lub daje pomysły na przyszłe kierunki .

Nie, o ile wiem, nie było pracy nad sformalizowaniem TeXa, który byłby zainteresowany.

(Poniżej znajduje się komentarz subiektywny i osobisty). Myślę, że jest to intrygujący i dobrze postawiony pomysł, a twoja motywacja do korzystania z niego do przeprowadzania optymalizacji brzmi rozsądnie - kolejne powiązane pytanie dotyczy tego, czy możesz zdefiniować format kodu bajtowego, aby przyspieszyć interpretację. Z drugiej strony pomysł ma dwie wady.

Po pierwsze, nie jest dla mnie jasne, że istnieje duży potencjał optymalizacji (na przykład, jakie transformacje zachowujące program można wykonać, aby przyspieszyć obliczenia?), Ponieważ może się zdarzyć, że semantyka języka jest ściśle związana z analizą składni przepływ znaków, a zatem niezbyt dostosowuje się do projektowania przyjaznych dla optymalizacji reprezentacji pośrednich.

Po drugie, potrzeba poprawy szybkości interpretacji TeX nie jest dobrze ustalona: szybkość budowania szybkości partii pozostała rozsądna dzięki ulepszeniom sprzętowym. Przypadki, w których przyspieszenie może być mile widziane, to złożony pakiet graficzny (tworzenie prezentacji beamerowych może zająć sporo czasu), pakiety zawierające bogate obliczenia (ale wtedy inny język może być bardziej odpowiedni), a także przypadki wymagające szybkiej przebudowy w celu uzyskania natychmiastowej opinii użytkownika (ale wtedy istotą może być przyrostowość, a nie optymalizacja; formalna semantyka z pewnością pomogłaby również w uzasadnieniu implementacji przyrostowych).

To znaczy: brzmi to zabawnie, pouczająco, ale nie jest dla mnie jasne, czy praktyczne uzasadnienia dla wykonania pracy są mocne. Jeśli ktoś byłby zainteresowany zrobieniem tego z ciekawości, brzmi to jak doskonała przygoda, ale w przeciwnym razie mogą istnieć inne sposoby wykorzystania tego samego zestawu umiejętności, którego wpływ byłby bardziej poszukiwany przez użytkowników końcowych.