Racket: Parsing propositional logic in 33 lines | Hacker News Reader

Racket: Parsing propositional logic in 33 lines

micahcantor.xyz

78 pointstosh18 comments

Pretty easy in raku, too[1]. Comes in at 29 lines—a hair under racket :)

(Though, granted, the latter does need to separate lexer and parser.)

Technically, the Racket version is using a separate lexer and parser library, it's just that Racket erases the line between what is a library and what is a language when it comes to lexers and parsers. One could either say this is a Racket program that uses the Brag library, or a Brag program (though the latter is preferred in the Racket ecosystem).

(On the other hand, the raku version also implements operator precedence properly, with infix operators having lower precedence than logical negation.)

Hi, author here. I'm new to Racket and obviously no expert. I realized this problem, but I wasn't sure about the best way to go about fixing it, do you have any suggestions?

I would do something similar to the raku version and have an extra bit in the grammar. Don't know racket or brag, but maybe something like http://ix.io/2AXE

This is quite impressive!

I don't know any other programming language that implement grammars in such a clean way.

Prolog implements Definite Clause Grammars[0] which can express context-sensitive grammars. In Prolog there is a simple DSL to express DCGs, but in fact DCG just uses Prolog runtime features. I don't believe there is aanother general purpose language with such complex parsing just built-in the runtime.

Here you can see my version of the raku parser, it's arguably shorter (I'm not a Prolog expert): https://swish.swi-prolog.org/p/basic_logic_parser.pl

[0] https://en.wikipedia.org/wiki/Definite_clause_grammar

It was a logical extension of regexes, which were a very important part of perl (raku was originally perl 6). It also integrates very well with the rest of the language—even more so than does regex with perl.

However, though I think raku's reimagination of regexes is probably the best one—and the one that feels the least bound to legacy—there are other developments in that area. For instance, oil's egg expressions - http://www.oilshell.org/preview/doc/eggex.html

There's Red with its Parse meta-DSL.

https://www.red-lang.org/2013/11/041-introducing-parse.html

There’s a fun old-school spelling for the logical AND and OR operators in languages that officially spell them ∧ or ∨ but need to be typed in ASCII: /\ and \/

I am having trouble finding real world examples right now, but it happens in languages like ALGOL and CPL (tho they predate ASCII)

TLA+ is an example. What I really like about this notation is you can use alignment to indicate precedence:

  \/ /\ A
     /\ B
  \/ /\ C
     /\ D

Which represents (A & B) || (C & D). It helps quite a bit for parsing large formulas in your head. In TLA+ the individual expressions are usually much more complicated than a single variable.

Aha, occam is another example, but it uses AND and OR for logical expressions but \/ or /\ for bitwise, plus the exciting >< for xor! http://transputer.net/obooks/obooks.asp

XOR is just a Boolean "not equal to"; if I had to express that with > and <, I would crib from BASIC and use <>.

MiniZinc uses the \/, /\, ->, <-> as the logical connectives.

Coq uses this notation for (propositional) and and or.

Truth table in 94 lines, no external libs: https://stackoverflow.com/questions/29963269/boolean-express...

I am never a fan of posts about "do x in y language in z lines" because inevitably there is a library involved. These posts should really involve a pure implementation in the language.

Omg that's like jumping a hundred ants on a motorbike. Writing an RD for that shouldn't take that much space.

Reply on news.ycombinator.com