Re: (For the Wikipedia article) Algorithms and format

On 30.11.20 08:16, Massimiliano Gubinelli wrote:
> Dear Giovanni,
>
>
>> On 28. Nov 2020, at 23:16, Giovanni Piredda <[email protected] 
>> <mailto:[email protected]>> wrote:
>>
>>
>> On 28.11.20 22:57, TeXmacs wrote:
>>> On Sat, Nov 28, 2020 at 07:20:15PM +0100, Giovanni Piredda wrote:
>>>> I have in mind that the "Turing complete" expression describes a
>>>> system of manipulation of symbols (I helped now myself with
>>>> Wikipedia for finding the word "manipulation" in this context), by
>>>> which starting with a set of symbols and applying the manipulation
>>>> rules I obtain another set of symbols.
>>> This is just to say that the parser of TeX is a complete programming
>>> language on its own.  This means that it is undecidable whether
>>> a given program is parsable.  TeX has no well-defined grammar,
>>> contrary to *ML languages (HTML, SGML, MathML) or TeXmacs.
>>> This is actually a very serious problem (it makes it impossible to
>>> write 100% reliable convertes)
>>
>> So "possibility to write converters that work always" is one point 
>> that I am going to write in the Wiki page I think.
>>
>>>> While I see a grammar as a set of rules that determine allowable
>>>> compositions of symbols, but they do not tell how to compose any set
>>>> of symbols.
>>>>
>>>> But you wrote that the grammar is Turing complete. Could you explain
>>>> more? Maybe a pointer to something to read, if it is to long to
>>>> write here.
>>> See also The Jolly Writer, section 1.8.
>>
>>
>> Thanks, here it will take a bit (the explanation on top helped).
>>
>>>> I have thought a bit on why LaTeX/TeX is so successful,
>>> One of the keys is that it cannot easily be converted to something else.
>>> Proprietary formats such as early M$ Word are another way to make 
>>> this task hard.
>>
>> Right. Once that you have many pages written in the format, it is 
>> difficult to switch to something different. This is also (perhaps) 
>> one of the reasons why the LaTeX code written by programs looks 
>> usually quite different from the one written by people---there are 
>> too many ways to do the same thing.
>>
>
> The comparison between PS and PDF can be cited in this context. PDF 
> was indeed introduced (as far as I understand) to reduce the 
> wilderness of PS documents (PS is a full-fledged programming language) 
> to a "description language" where arbitrary computations are no more 
> possible.
>
>
I understood it in this way so far (it will take more time before I am 
able to write it up on Wikipedia)---I write it here in the TeX/TeXmacs 
format conversion case, but it is more general---please let me know if 
the description is sensible, it is part of the understanding I know in 
order to write:

TeX is a programming language, and the TeXmacs format is description of 
an abstract object, which is the *output* of a programming language. The 
theorem on undecidability of the halting problem says that (expressed in 
a more general way than the formulation "you cannot know if a program 
halts for all programs") in order to know the output of a program 
(again, for all programs) you need to run the program; there may be 
programs for which you can know the output with a simpler calculation.

Applying this to the conversion between a TeX _program that generates a 
document_ and a TeXmacs _description of a document_: you cannot do it 
for all TeX programs.

Now the difficult and interesting part: for a reasonable converter, one 
needs to define (and mechanically, with an algorithm, to decide whether 
the program belongs to the subset or not) a subset of TeX programs for 
which one can do the conversion. The problem of definition looks to me 
difficult because the subset has to be "large enough to be useful" and 
"small enough that the conversion is possible" at the same time. The 
decision itself might be easy if the criteria for "belonging to the set" 
make it so (but finding criteria that help from this point of view might 
be again difficult).

It would be interesting to know on this topic what is the status of the 
"conservative conversion" described in "Conservative conversion between 
LaTeX and TeXmacs" (a good topic to include in an article in an 
encyclopedia).

Finally on this topic

> However you need also to add that the \extern primitive allows to 
> access these computational capabilities with an underlying scripting 
> language. Here the comparison can be made with HTML/JS.

And the native macro system too pushes one outside the markup system, right?


>>>> The "markup" of TeX (I call it that way even if it is not markup)
>>>> for me is the easiest to read among all of the markup languages I
>>>> have seen (for mathematics especially, for other things too).
>>>> Perhaps this has been also one factor for success.
>>> Easy in appearance.
>>>
>>> If it is that easy, try writing a converter to some other format.
>>
>> I meant "easy to read for me". This is subjective *and* only loosely 
>> related to how easy is to read it mechanically, i.e. with an 
>> algorithm---I saw this position that I am taking now only taken once 
>> by another person on the Internet, and a similar position ("reading 
>> TeX is second nature after a while", but without comparison to other 
>> markup) taken by other two persons (one in flesh and blood, one on 
>> the Internet). By the way I can read at sight only simple 
>> mathematical formulae written in TeX, but I do worse with all of the 
>> other markup systems I know.
>>
>
> In the context of markup languages you may want to link to general 
> pages like:
>
> https://en.wikipedia.org/wiki/Markup_language 
> <https://en.wikipedia.org/wiki/Markup_language>


Thanks, this link belongs there. Moreover one can write up *inside this 
article* a paragraph on the TeXmacs format; in this case it would be 
helpful (I feel it necessary in this moment) to describe in a sentence 
what distinguishes it from SGML (what makes it not a particular SGML 
like DocBook) and maybe also why it was chosen that the TeXmacs format 
would not be SGML.


>
> and also it could be mentioned that there are other interesting 
> systems like
>
> https://en.wikipedia.org/wiki/Lout_(software) 
> <https://en.wikipedia.org/wiki/Lout_(software)>
>
> which is a lazy functional description language for pages.
>
>
Thanks, I downloaded the system and looked at a few pages of the manual 
... now I need to understand why it is a lazy functional description 
language, but that I have to postpone :-)

Finally, for my remark that TeX is the easiest to read "markup" that I 
know, it occurred to me that the format of computer algebra systems is 
still easier to read; but perhaps it is not comprehensive enough to be 
used for typesetting a document, and if you include more syntactic 
expressions so that it is, it becomes as difficult to read as TeX at 
least. Maybe I will experiment a bit with Mathematica, which as far as I 
remember can format mathematical expressions as well; I need to express 
all input in linear form of course otherwise it is easier to read but 
the comparison is unfair ;-)


G.





_______________________________________________
Texmacs-dev mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/texmacs-dev