Pratt
so, I read this. https://dl.acm.org/doi/pdf/10.1145/512927.512931
but I've never done this before, so I have been having trouble getting a vibe.
A point Pratt mentions is that the central problem is that you can't get people to accept a prefix language like this:
print + * 2 3 * 4 5
(assuming + and * act on two elements)
but there are these crazy #lisp people, that if you add overspecified brackets:
(print (+ (* 2 3) (* 4 5)))
Say they will happily read and write, and can understand this expression perfectly.
@screwtape isn't this called polish notation? I remember when I first learned bison/flex (GNU YACC/lex equivalent) it got me to write a polish notation calculator which was basically this
@webhat Yeah, I heard it called [reverse] Polish notation as well, or prefix notation. The problem arises that people want to write factorial as 5! not ! 5 (maybe you could get a lisper to write (fact 5)), or worse, people including lispers want to write 2/3 and so forth.
So each token has a nud (prefix notation host language thing to do) and a led (infix or left-binding host language thing to do), and you compare the current right binding power with tokens' left binding powers or something...
= 
log
) @screwtape @webhat
Vaughn Pratt was himself a Lisp programmer, and implemented CGOL as a Maclisp reader.
He was at Stanford and MIT, and Berkeley pre-Unix, so there's no reason to think he was aware of the 'dc' RPN arithmetic tool, and the paper you reference is earlier than HP's RPN handheld calculators, which had a very loyal following.
But was there a specific question?
P.S. "Polish notation" is the most common name (after 'postfix') for operators following operands, just as Reverse Polish Notation (RPN) is the most common name (after 'prefix') for operators preceding operands.
'The description "Polish" refers to the nationality of logician Jan Łukasiewicz' but people in the early 20th century had a tough time with Polish names so they used a nickname.
He was famous for multiple things, though, for instance continuous (real-) valued logic, which in a hypothetical infinitely precise analog computer would allow hypercomputation -- computation beyond what is possible for Turing machines.
https://en.wikipedia.org/wiki/Polish_notation
https://en.wikipedia.org/wiki/Jan_%C5%81ukasiewicz
@dougmerritt
Well, I'm just being a bit slow working through, like, given the article's description of a parser, imagine I wanted to parse
(- 1 + 2 * 3 / 4)
I'm having more trouble than I thought writing a parser from the diagrams on page 47.
Ah, I might have misread Pratt's line in the article about the unwritability of
(= (+ (* a (^ b 2)) (* c (^ d 2))) (* 4 (sin (+ a b))))
:
"(But I have recently encountered some LISP users claiming the reverse, so I may be biased.)"
@webhat @mdhughes
️ 
@screwtape @dougmerritt @webhat Oh, if you actually want to parse algebraic, there's two ways to do it, and they both suck.
Shunting yard algorithm
https://en.wikipedia.org/wiki/Shunting_yard_algorithm
The other relies on expression pattern matching, you can insert parens around operators, then just evaluate the parens. I don't know a name/article for this, but it's what some FORTRAN did.
@mdhughes
Oh, yeah, I guess there's some kind of pseudocode on wikipedia here for what I'm stumbling over
https://en.wikipedia.org/wiki/Operator-precedence_parser
@dougmerritt @webhat