how to automate translation from operand-based expressions to function-based ones

Question

I'm trying to re-write / translate logic statements written arithmetically, into strings of min/max functions, some of them fairly complicated. Preferably using things like sed, awk, perl, python, etc. I'm working with a program in which, for my purposes, AND=MIN and OR=MAX. I'm able to convert/rewrite XOR, IMPL, etc. so that it understands accordingly without issue - what I'm struggling with (and looking to automate) is the rearranging of the syntax.

A complex example (partially based on a constructive dilemma):

((p implies q) and (r implies s)) and (p or r)

Would be:

min(min(max(~p,q),max(~r,s)),max(p,r))

I just need to convert from the first format to the second (doesn't need to work in reverse). I can convert individual elements (like a single "(p or r)" to "max(p,r)", in isolation) but once it comes time to re-arrange and nest them relative to eachother I'm pretty lost.

Answer 1

Using TXR Lisp:

$ txr -i minmax.tl
TXR's suggested retail price is $0. (More in Canada.)
1> (mmax '(((p implies q) and (r implies s)) and (p or r)))
"min(min(max(~p,q),max(~r,s)),max(p,r))"

Code in minmax.tl:

(defun mmax (expr)
  (match-case expr
    ((@left and @right) `min(@(mmax left),@(mmax right))`)
    ((@left or @right) `max(@(mmax left),@(mmax right))`)
    ((not @term) `~@(mmax term)`)
    ((@left implies @right) `max(~@(mmax left),@(mmax right))`)
    (@else `@else`)))

From the system command line:

$ txr -e '(load "minmax")' -P "(mmax '(a and b))"
min(a,b)

From standard input:

$ echo '(a and b)' | txr -e '(load "minmax")' -P "(mmax (read))"
min(a,b)

We can make a little filtering program like this, and give it execute permissions:

$ echo '(a and b)' | ./mmax.tl
min(a,b)

where mmax.tl has execute permissions (chmod +x mmax.tl) and contains:

#!/usr/bin/env txr

(defun mmax (expr)
  (match-case expr
    ((@left and @right) `min(@(mmax left),@(mmax right))`)
    ((@left or @right) `max(@(mmax left),@(mmax right))`)
    ((not @term) `~@(mmax term)`)
    ((@left implies @right) `max(~@(mmax left),@(mmax right))`)
    (@else `@else`)))

(flow (read)
  mmax
  put-line)

Note: (read) reads an object in TXR Lisp syntax. For the example given, it is compatible: (a and (b or c)) is valid. It might not be true of all examples of that input language, in which case we need custom parsing. YMMV.