Racket: Parsing propositional logic in 33 lines

https://micahcantor.xyz/blog/logic-racket-parser

by tosh • 6 years ago

78 18 6 years ago

micahcantor.xyz

moonchild4• 6 years ago

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.)

1. http://ix.io/2ASA

AQXt• 6 years ago

This is quite impressive!

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

moonchild4• 6 years ago

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

9214• 6 years ago

There's Red with its Parse meta-DSL.

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

ceceron2• 6 years ago

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

moonchild4• 6 years ago

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

hydroxideOH-• 6 years ago

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?

moron4hire• 6 years ago

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).

throwaway_pdp09• 6 years ago

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

fanf22• 6 years ago

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)

ocfnash• 6 years ago

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

ahelwer• 6 years ago

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.

fanf22• 6 years ago

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

kazinator2• 6 years ago

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

ceceron2• 6 years ago

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

ecshafer• 6 years ago

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.

kazinator2• 6 years ago

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

Racket: Parsing propositional logic in 33 lines

Related Stories