Representing Propositional Logic Expressions in Racket

Questions & Answers
, ,
1

I'm reading chapter 7 of Russell & Norvig's "Artificial Intelligence: A Modern Approach" textbook that is about designing Logical Agents using propositional logic. The code for the algorithms in the chapter are available for Python. I wanted to use Racket for implementing the code instead of just reading the Python so I can understand the algorithms better. However, since I'm new to Racket I'm having difficulty representing the logical expressions in it.

In the python code, a logical expression is represented by a class that takes two parameters - the logical operator (and , or, if, iff, not) and its arguments. Here is a snippet of the python code

class Expr:
    """A mathematical expression with an operator and 0 or more arguments.
    op is a str like '+' or 'sin'; args are Expressions.
    Expr('x') or Symbol('x') creates a symbol (a nullary Expr).
    Expr('-', x) creates a unary; Expr('+', x, 1) creates a binary."""

    def __init__(self, op, *args):
        self.op = str(op)
        self.args = args

    # Operator overloads
    def __neg__(self):
        return Expr('-', self)

    def __pos__(self):
        return Expr('+', self)

    def __invert__(self):
        return Expr('~', self)

    def __add__(self, rhs):
        return Expr('+', self, rhs)

In Racket, I'm representing logical expressions as pairs, i.e (cons op args). I also added a syntactic sugar for the expressions so that I can write (& a b) and it will be transformed to (cons and '(a b)). Another requirement is that both operators and their arguments should be represented as symbols unless they are explicitly evaluated - so that I can manipulate expressions symbolically. Hence, (& a b) will be represented as (cons 'and '('a 'b)) and only when doing (! (& a b)) should this be evaluated as (and a b) - I'm using ! to denote evaluation of an logical expression. This is the part I'm struggling with.

#lang racket

#lang racket

;function wrapper for the and operator
(define (and-fn patt ...)
  (and patt ...))

;function wrapper for the or operator
(define (or-fn patt ...)
  (and patt ...))

;function wrapper for the not operator
(define (not-fn patt)
  (not patt))

(define-syntax (~ stx)
  (syntax-case stx ()
  ([_ a] #'(cons 'not-fn #'a))))

(define-syntax (& stx)
  (syntax-case stx ()
    [(_ patt ...) #'(cons 'and-fn '(patt ...))]))

(define-syntax (|| stx)
  (syntax-case stx ()
    [(_ patt ...) #'(cons 'or-fn '(patt ...))]))

(define-syntax (=> stx)
  (syntax-case stx ()
    [(_ a b) #'(cons '=> '(a b))]))

(define-syntax (<=> stx)
  (syntax-case stx ()
    [(_ a b) #'(cons '<=> '(a b))]))



(define (! stx)
  (syntax-case stx ()
    [(_ op patt ...)
     (match (op patt)
       [('=> '(a b)) #'(! (|| (~ a) b))]
       [('<=> '(a b)) #'(! (& (|| (~ a) b) (|| (~ b) a)))]
      [_ #'(eval (op patt ...))])])) 


(define a #t)
(define b #f)

(! (|| a b)) ;should evaluate to #t
(! (=> a b)) ;should evaluate to #f

When running the above code, I get match: syntax error in pattern in: ((quote =>) (quote (a b))) error. How can I fix this and implement propositional logic expressions in Racket? I'm also open to suggestions n representing logical expressions other than (cons op args)

1 Like
2

I think, you want something like this:

(define (! stx)
  (syntax-case stx (=> <=>)
    [(_ (=> a b))     #'(! (|| (~ a) b))]
    [(_ (<=> a b))    #'(! (& (|| (~ a) b) (|| (~ b) a)))]
    [(_ (op pat ...)) #'(eval (op pat ...))]))

The syntax for syntax-case is:

(syntax-case stx-expr (literal-id ...)
  clause ...)

Making => a literal means that we can use => as a pattern that only matches =>.
Therefore the pattern (_ (=> a b)) matches (! (=> a b)).

Your program won't run as-is though.

In your function wrappers you have:

(define (and-fn patt ...)
  (and patt ...))

The problem is that ... is a normal identifier, so this defines and-fn
as a function of two arguments: patt and .... The result is (and patt ...)
and that does return the correct result if you only use and-fn with two arguments.
For (and #t #t #f) you will get an error.

Here is a version that handles an arbitrary number of arguments:

(define (and-fn . ps)
  (foldl (λ (a b) (and a b))
         #t
         ps))

(and-fn #t #t #f)

Btw - the name || may or may not be problematic.
The syntax || is used to make symbols with as in '|foo bar|.
Thus || is the a symbol with the empty string as name.
I imagine error messages where the name || is printed as nothing
might be confusing.

You could use // instead to get a more "normal" name.

1 Like
3

Thank you for your reply.

Unfortunately, after applying your suggetions, I still get a syntax error. For example running the following snippet:

(define a #t)
(define b #f)

(! (& a b))  ;should evaluate to #f

gives me and-fn: bad syntax in: (and-fn a b) error

4

What does your program look like now?

5

Here is the full code (including your suggestions):

#lang racket

;function wrapper for the and operator
(define (and-fn . ps)
  (foldl (λ (a b) (and a b))
         #t
         ps))
;function wrapper for the or operator
(define (or-fn . ps)
  (foldl (λ (a b) (or a b))
         #t
         ps))

;function wrapper for the not operator
(define (not-fn patt)
  (not patt))

(define-syntax (~ stx)
  (syntax-case stx ()
  ([_ a] #'(cons 'not-fn #'a))))

(define-syntax (& stx)
  (syntax-case stx ()
    [(_ patt ...) #'(cons 'and-fn '(patt ...))]))

(define-syntax (|| stx)
  (syntax-case stx ()
    [(_ patt ...) #'(cons 'or-fn '(patt ...))]))

(define-syntax (=> stx)
  (syntax-case stx ()
    [(_ a b) #'(cons '=> '(a b))]))

(define-syntax (<=> stx)
  (syntax-case stx ()
    [(_ a b) #'(cons '<=> '(a b))]))



(define (! stx)
  (syntax-case stx (=> <=>)
    [(_ (=> a b))     #'(! (|| (~ a) b))]
    [(_ (<=> a b))    #'(! (& (|| (~ a) b) (|| (~ b) a)))]
    [(_ (op pat ...)) #'(eval (op pat ...))]))


(define a #t)
(define b #f)

;(! (|| a b)) ;should evaluate to #t
(! (& a b)) ;should evaluate to #f
6

If you use the macro stepper you will see (focus on the red parts):

image
image1920×1474 192 KB

So (! (& a b)) expands to (! (cons 'and-fn '(a b)) and then you get the error "bad syntax".

When syntax-case can't find a pattern that matches the input you get a "bad syntax" error.
It's a good idea to add a fall through pattern, so you can see which macro failed.

With this change:

(define (! stx)
  (syntax-case stx (=> <=>)
    [(_ (=> a b))     #'(! (|| (~ a) b))]
    [(_ (<=> a b))    #'(! (& (|| (~ a) b) (|| (~ b) a)))]
    [(_ (op pat ...)) #'(eval (op pat ...))]
    [_ (error "bad syntax in !")]))

It becomes clear, that your ! macro doesn't handle the input (cons 'and-fn '(a b)).

7

I notice you are using eval in a way that will not work, because it does not provide an appropriate namespace. See 15.1 eval in The Racket Guide for an introduction to the problem, and see On `eval` in dynamic languages generally and in Racket specifically for broader background on why the problem is a problem.

It is quite unusual to have a macro implementing a domain-specific language that expands to eval. Instead, you probably want to choose one of two broad strategies:

  1. Implement a compiler for your language, likely by using macros to extend the Racket compiler. In this case, evaluation happens when you run your program. With this strategy, the challenging part might be: You would probably want to use functionality like syntax-local-value, local-expand, and other "macros that work together" features. If so, I would definitely recommend switching to syntax-parse for better error messages.
    (I don't know how extensive the manipulation you have in mind for "manipulate expressions symbolically" is, though. Some things someone might describe that way might not need such advanced macro features.)
  2. Implement an interpreter for your language as an ordinary Racket function. In this case, evaluation is calling your function, and you don't need macros at all. With this strategy, the challenging part might be implementing features like variable binding and lexical scope that Racket takes care of for you—but if your language doesn't include binding constructs, maybe this is not a big challenge. Here is your example reworked as an interpreter:
    #lang racket

(define (! expr env)
  (match expr
    [(? symbol? a)
     (hash-ref env a)]
    [`(=> ,a ,b)
     (! `(|| (~ ,a) ,b)
        env)]
    [`(<=> ,a ,b)
     (! `(& (|| (~ ,a) ,b) (|| (~ ,b) ,a))
        env)]
    [`(~ ,a)
     (not (! a env))]
    [`(&)
     #t]
    [`(& ,a ,@xs)
     (and (! a env)
          (! `(& ,@xs) env))]
    [`(||)
     #f]
    [`(|| ,a ,@xs)
     (or (! a env)
         (! `(|| ,@xs) env))]))

(define env
  #hasheq([a . #t]
          [b . #f]))

(! `(|| a b) env)
(! `(=> a b) env)

You might notice that the explicit env in the interpreter version serves the same role as the namespace in Racket's eval.

2 Likes
8

I want to echo @LiberalArtist. Are you sure that this is what you actually want? In the Python version, you would evaluate a formula against an explicit truth table row / interpretation via the function pl_true. This is the interpreter approach. I don’t think there’s anything similar to ! in the Python code base (disclaimer: I never read the book, only skimmed the Python code base that you linked).

1 Like
9

FWIW I agree with @LiberalArtist and @sorawee that an interpreter approach matches the book closer.

But maybe you simply wanted to experiment with macros?

1 Like
10

I haven't read the book, but I think a macro approach could be fun! But it's hard to provide more suggestions without more specifics of what kind of "manipulat[ing] expressions symbolically" you want to support.

11

I am astonished by your obfuscated Racket code. In fact, I don't think you have to use macros. You might write a direct style interpreter, or you could organize code in the so called tagless-final style as follows.

(define ((And . exp*))
  (andmap (lambda (exp) (exp)) exp*))
(define ((Or . exp*))
  (ormap (lambda (exp) (exp)) exp*))
(define (True) #t)
(define (False) #f)

Here is an example.

> (define exp0
    (And True (Or False False True) (And True False)))
> (exp0)
#f
12

Yes, I agree, the interpreter based version is implemented in the Python code. I naively thought the right way to go about this was using macros - especially after skimming through the racket-cas library.

Using @LiberalArtist 's code I can now implement most of what I need in Racket. Here is the full code I'm using now:

#lang racket


(define-syntax (~ stx)
  (syntax-case stx ()
  ([_ a] #'(cons '~ '(a)))))

(define-syntax (& stx)
  (syntax-case stx ()
    [(_ patt ...) #'(cons '& '(patt ...))]))

(define-syntax (|| stx)
  (syntax-case stx ()
    [(_ patt ...) #'(cons '|| '(patt ...))]))

(define-syntax (=> stx)
  (syntax-case stx (=>)
    [(_ a b) #'(cons '=> '(a b))]))

(define-syntax (<=> stx)
  (syntax-case stx (<=>)
    [(_ a b) #'(cons '<=> '(a b))]))


(define (! expr env)
  (match expr
    [(? symbol? a)
     (hash-ref env a)]
    [`(=> ,a ,b)
     (! `(|| (~ ,a) ,b)
        env)]
    [`(<=> ,a ,b)
     (! `(& (|| (~ ,a) ,b) (|| (~ ,b) ,a))
        env)]
    [`(~ ,a)
     (not (! a env))]
    [`(&)
     #t]
    [`(& ,a ,@xs)
     (and (! a env)
          (! `(& ,@xs) env))]
    [`(||)
     #f]
    [`(|| ,a ,@xs)
     (or (! a env)
         (! `(|| ,@xs) env))]))



(define (primitive-op? op)
  (member op '(& || ~)))

(define (elm-impl expr)
  ;Change implications into equivalent form with only &, |, and ~ as logical operators.
  (match expr
    [`(=> ,a ,b) `(|| (~ ,(elm-impl a))
                      ,(elm-impl b))]
    [`(<=> ,a ,b) `(& (|| ,(elm-impl a) (~ ,(elm-impl b)))
                      (||  ,(elm-impl b) (~ ,(elm-impl a))))]
    [`(^ ,a ,b) `(|| (& ,(elm-impl a) (~ ,(elm-impl a)))
                     (& (~ ,(elm-impl a)) ,(elm-impl b)))]
    [`(,(? primitive-op? op) ,a ,@xs)   `,(cons op (cons (elm-impl a)
                                          (elm-impl xs)))]
    [`(,a ,@xs) `,(cons (elm-impl a) (elm-impl xs))]
    [(? symbol? a) a]
    ['() '()]))
    


(define (move-not-inwards expr)
  ;Rewrite sentences by moving negation (~) inwards
  ;(~ (|| a b)) = (& (~ a) (~ b)) 

  (define (NOT p)
    (map (lambda (e) (move-not-inwards `(~ ,e))) p))

  (match expr
    [`(~ (& ,patt ...)) (move-not-inwards (associate '|| (NOT patt)))]
    [`(~ (|| ,patt ...)) (move-not-inwards (associate '& (NOT patt)))]
    [`(~ (~ ,a)) `,(move-not-inwards a)] ;~~a = a
    [`(,(? primitive-op? op) ,a ,@xs)   (cons op (cons (move-not-inwards a)
                                            (move-not-inwards xs)))]

    [`(,a ,@xs) `,(cons (move-not-inwards a) (move-not-inwards xs))]
    [(? symbol? a) a]
    ['() '()]))

(define op-identity
  #hasheq(['& . #t]
          ['|| . #f]))

(define (associate op expr)
  (let ([args (map (lambda (e) (dissociate op e)) expr)])
    (cond [(= (length args) 0) (hash-ref op-identity op)]
          [(= (length args) 1) (car args)]
          [else `(,op ,args)])))

(define (dissociate op expr)
  (define (op? x)
    (equal? x op))
  (define (not-op? x)
    (not (op? x)))
  (match expr
    [`(,(? op? op) ,patt ,@rest) (cons (dissociate op patt) (dissociate op rest))]
    [`(,(? not-op? op) patt ...) expr]
    [`(,a ,@xs) (cons a (dissociate op xs))]
    [(? symbol? a) a]
    ['() '()]))


(define env
  #hasheq([a . #f]
          [b . #t]))

(! (|| a (=> a b)) env)
(! (<=> a b) env)

(elm-impl (=> a (<=> b (& c d e))))
(move-not-inwards (~ (& a b (|| c (~ (& d e))))))
(associate `|| (|| (& a b) c))

I added syntactic sugars via the macros so that the expressions aren't always quoted and it works.

The symbolic manipulations (like the ones implemented in elm-impl and move-not-inwards functions) are essentially casting a logical expression into a Conjunctive Normal Form (CNF). In the above code snippet, I haven't implemented the CNF transformation (elm-impl & move-not-inwards will be used in the method that implements it) and will update the code once I'm implement the distribute_and_over_or function for completeness.

13

One thing I realized is encapsulating a logical expression in some data structure is necessary to distinguish between an operator and the arguments of the operator in a logical expression. Hence, I created a expr struct:

#lang racket
(define (is-op? op)
  (member op '(& || ~ => <=>))
)

(define (not-op? op)
  (not (and (symbol? op) (is-op? op)))
)

(struct expr (op args) 
  #:transparent
  #:guard (lambda (op args type-name)
            (if (not-op? op)
                (error type-name "bad op: ~a" op)
                (if (or (list? args) (expr? args))
                  (values op args)
                  (error type-name "bad args: ~a" args)))))

And I still want to keep the syntatic forms to create expressions, i.e (|| a b) will be transformed to (expr '|| '(a b)). To do so, I have changed the macros to be like this:

(define-syntax (~ stx)
  (syntax-case stx ()
  ([_ a] #'(expr '~ '(a)))))

(define-syntax (& stx)
  (syntax-case stx ()
    [(_ patt ...) #'(expr '& '(patt ...))]))

(define-syntax (|| stx)
  (syntax-case stx ()
    [(_ patt ...) #'(expr '|| '(patt ...))]))

(define-syntax (=> stx)
  (syntax-case stx (=>)
    [(_ a b) #'(expr '=> '(a b))]))

(define-syntax (<=> stx)
  (syntax-case stx (<=>)
    [(_ a b) #'(expr '<=> '(a b))]))

The above works fine if the arguments of an operator are pure symbols like (|| a b)

For expression, it is possible that an argument of an operator can be another expression. E.g (|| a (=> a b). Using the above macros this is transformed to (expr '|| '( a (=> a b))). But what it should be transformed to is (expr '|| '(a (expr '=> '(a b)) (just like in the Python code). How can I modify the macro code to expand any subexpressions in the arguments and translate them to the appropriate syntactic form?

14

There is no need for macros.

(struct expr (op args) #:transparent)
;<exp> ::= <symbol>
;       |  (disj <exp>*)
;       |  (conj <exp>*)
;       |  (-> <exp> <exp>)
(define (parse exp)
  (match exp
    (atom #:when (symbol? atom) atom)
    (`(disj . ,exp*)
     (expr 'disj (map parse exp*)))
    (`(conj . ,exp*)
     (expr 'conj (map parse exp*)))
    (`(-> ,e1 ,e2)
     (expr '-> (list (parse e1) (parse e2))))))

> (parse '(disj a (-> a b)))
(expr 'disj (list 'a (expr '-> '(a b))))
15

Previous versions of this code already did "encapsulat[e] a logical expression in some data structure," namely a list. In an expression represented as:

'(& (|| (~ a) b) (|| (~ b) a))

the head of the list is an operator and the tail of the list is the arguments to the operator. An argument is either a symbol for a variable reference or a list for a sub-expression with another operator.

This is the same way Racket represents expressions and distinguishes between operators and operands.

16

You might find the Nanopass Framework a nice way to write these kinds of transformations. For example, it has support for automatic recursion over sub-terms. Here's something to start with:

#lang racket

(require nanopass/base)

(define variable? symbol?)

(define-language Lsrc
  (terminals
   (variable (x)))
  (Expr (e a b)
    x
    (==> a b) ; not => because nanopass uses that symbol
    (<=> a b)
    (^ a b)
    (~ e)
    (& e ...)
    (|| e ...)))

(define-language Lprimop
  (extends Lsrc)
  (Expr (e a b)
    (- (==> a b)
       (<=> a b)
       (^ a b))))

(define-pass remove-implication : Lsrc (ir) -> Lprimop ()
  (Expr : Expr (ir) -> Expr ()
    [(==> ,[a] ,[b])
     `(|| (~ ,a) ,b)]
    [(<=> ,[a] ,[b])
     `(& (|| ,a (~ ,b))
         (||  ,b (~ ,a)))]
    [(^ ,[a] ,[b])
     `(|| (& ,a (~ ,b))
          (& (~ ,a) ,b))]))

(unparse-Lprimop
 (remove-implication
  (with-output-language (Lsrc Expr)
    `(==> a (<=> b (& c d e))))))
17

Thank you for the suggestions @ulambda. You are right, I could implement what I want without using macros and perhaps using macros is an overkill. However, I'm using this project to learn more about Racket (& Logical Inference) and I prefer to use macros so that logical expressions are supported at syntax level.

18

Yeah, that's true and it was my initial intuition that the list representation suffices to encapsulate the expressions. I tried to use a struct as a desperate attempt to fix a bug in one of the functions (namely associate). However now, I realized the bug didn't have anything to do with the way the expressions are represented and I've solved it now.

Here is the updated code (for future reference)

(define (primitive-op? op)
  (member op '(& || ~)))

(define (op? op)
  (member op '(& || ~ => <=>)))

(define (not-op? op)
  (not (op? op)))

(define (not-empty? x)
  (not (empty? x)))

(define op-identity
  #hasheq([& . #t]
          [|| . #f]))

(define (member? ls)
  (lambda (x)
    (not (empty? (member x ls)))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
syntatic sugar for logical expressions implemented via macros

(define-syntax (~ stx)
  (syntax-case stx ()
  ([_ a] #'(cons '~ '(a)))))

(define-syntax (& stx)
  (syntax-case stx ()
    [(_ patt ...) #'(cons '& '(patt ...))]))

(define-syntax (|| stx)
  (syntax-case stx ()
    [(_ patt ...) #'(cons '|| '(patt ...))]))

(define-syntax (=> stx)
  (syntax-case stx (=>)
    [(_ a b) #'(cons '=> '(a b))]))

(define-syntax (<=> stx)
  (syntax-case stx (<=>)
    [(_ a b) #'(cons '<=> '(a b))]))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; interpreter of logical expressions using the model specified in env
(define (! expr env)
  (match expr
    [(? symbol? a)
     (hash-ref env a)]
    [`(=> ,a ,b)
     (! `(|| (~ ,a) ,b)
        env)]
    [`(<=> ,a ,b)
     (! `(& (|| (~ ,a) ,b) (|| (~ ,b) ,a))
        env)]
    [`(~ ,a)
     (not (! a env))]
    [`(&)
     #t]
    [`(& ,a ,@xs)
     (and (! a env)
          (! `(& ,@xs) env))]
    [`(||)
     #f]
    [`(|| ,a ,@xs)
     (or (! a env)
         (! `(|| ,@xs) env))]))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; functions that implement symbolic manipulation of logical exprs
(define (associate op expr)
  (let ([args (dissociate op (append `(,op) expr) '())])
    (cond [(= (length args) 0) (hash-ref op-identity op)]
          [(= (length args) 1) (car args)]
          [else (append `(,op) args)])))

(define (dissociate op expr acc)
  (define (equals-op? x)
    (equal? x op))
  (define (not-equals-op? x)
    (and (op? x) (not (equals-op? x))))

  (match expr
    [`(,(? equals-op? x) ,@xs) (dissociate op xs acc)]
    [`(,(? not-equals-op? x) ,@xs) (append `(,expr) acc)]
    [`(,a ,@xs) (append (dissociate op a acc) (dissociate op xs acc))]
    [(? symbol? a) (append `(,a) acc)]
    ['() '()]))

(define (remove-impl expr)
  ;Change implications into equivalent form with only &, |, and ~ as logical operators.
  (match expr
    [`(=> ,a ,b) `(|| (~ ,(remove-impl a))
                      ,(remove-impl b))]
    [`(<=> ,a ,b) `(& (|| ,(remove-impl a) (~ ,(remove-impl b)))
                      (||  ,(remove-impl b) (~ ,(remove-impl a))))]
    [`(^ ,a ,b) `(|| (& ,(remove-impl a) (~ ,(remove-impl a)))
                     (& (~ ,(remove-impl a)) ,(remove-impl b)))]
    [`(,(? primitive-op? op) ,@xs) (cons op (remove-impl xs))]
    [`(,a ,@xs) (cons (remove-impl a) (remove-impl xs))]
    [(? symbol? a) a]
    ['() '()]))

(define (move-not-inwards expr)
  ;Rewrite sentences by moving negation (~) inwards
  ;(~ (|| a b)) = (& (~ a) (~ b)) 

  (define (NOT p)
    (map (lambda (e) (move-not-inwards `(~ ,e))) p))

  (match expr
    [`(~ (& ,@xs)) (associate '|| (NOT xs))]
    [`(~ (|| ,@xs)) (associate '& (NOT xs))]
    [`(~ (~ ,a)) a] ;~~a = a
    [`(,(? op? op) ,@xs)   (cons op (move-not-inwards xs))]

    [`(,a ,@xs) (cons (move-not-inwards a) (move-not-inwards xs))]
    [(? symbol? a) a]
    ['() '()]))

(define (distribute-and-over-or expr)
  ;Given a sentence s consisting of conjunctions and disjunctions
    of literals, return an equivalent sentence in CNF.
  ; (distribute-and-over-or (|| c (& a b))) = (& (|| a c) (|| b c))
  (define (find-conj x acc)
    (if 
      (and (list? x) (> (length x) 1) (op? (car x))
        (equal? (car x) '&)) (append (cdr x) acc)
      '()))

   (define (find-non-conj x acc)
      (match x
        [`(& ,@xs) acc] 
        [`(|| ,@xs) (append xs acc)]
        [_ (append `(,x) acc)]))

  (define (or-op-handle patt)
    (let ([s (associate '|| patt)])
      (cond 
        [(= (length s) 0) #f]
        [(= (length s) 1) (distribute-and-over-or (car s))]
        [(and (op? (car s)) (not (equal? '|| (car s)))) (distribute-and-over-or s)]
        [else 
            (let* ([conj (foldl find-conj '() s)]
                   [others (foldl find-non-conj '() s)]
                   [rest (associate '|| others)]
                   [fn (lambda (e) (distribute-and-over-or `(|| ,(append (list e) rest))))])
              (if (empty? conj) s (associate '& (map fn conj))))])))

  (match expr
    [`(& ,@xs) (associate '& (map (lambda (e) (distribute-and-over-or e) ) xs))]
    [`(|| ,@xs) (or-op-handle xs)]
    [_ expr]))

(define (to-cnf expr)
  ;; convert a logical expression into a canonical Conjuctive Normal Form (CNF)
  (let* ([s (remove-impl expr)]
         [s (move-not-inwards s)])
         
      (distribute-and-over-or s)))

(define env
  #hasheq([a . #f]
          [b . #t]
          [c . #f]
          [d . #t]
          [e . #t]))

(! (|| a (=> a b)) env)
(! (<=> a b) env)

(define patt (~ (& a b (|| c (~ (=> d e))))))
(to-cnf patt)
(! (to-cnf patt) env)

The above code works as intended and the evaluations return the correct value

Nanopass looks interesting and I'll look at it. Thanks!

Anyways, thank you all for your suggestions and answers (glad I chose Racket for this project both b/c of the language features and the helpful community)! I can now build up on this basic code to implement the other algorithms in the book and I'll share the GitHub repo on this thread once I'm done.

19

Still I have one thing to say. (Another thing has been pointed out by other people, that is, no matter which representation you take, you can distinguish between variables and other syntactic forms.) [Also I don't want to talk about whether to use macros or not.] What makes your program weird to me is that your macros don't cooperate with each other at all. Assume that you write only such code:

(define-syntax (& stx)
  (syntax-case stx ()
    [(_ patt ...) #'(cons '& '(patt ...))]))

That won't stop you from writing the following expression.

> (& (~ a) b (~ c))
'(& (~ a) b (~ c))

If you had understood this point, you wouldn't ask the previous question concerning another representation. The more acceptable way (at least for me) to write your code is
as follows.

(struct expr (op args) #:transparent)
(define-syntax (=> stx)
  (syntax-case stx (=>)
    [(_ a b) #'(expr '=> (list a b))]))
(define-syntax (|| stx)
  (syntax-case stx ()
    [(_ patt ...) #'(expr '|| (list patt ...))]))

Then macros compose well.

> (|| 'a (=> 'a 'b))
(expr '|| (list 'a (expr '=> '(a b))))

(((((for me, for me, for me

(struct expr (op args) #:transparent)
(define (|| . e*)
  (expr '|| e*))
(define (=> a b)
  (expr '=> (list a b)))

> (|| 'a (=> 'a 'b))
(expr '|| (list 'a (expr '=> '(a b))))

is enough.)))))
Oh, I have another thing to say. Nanopass is good, but for your purpose, it will not make your life easier. If you are interested in AIMA, I think you may also want to read Building Problem Solvers. For learning about macros, I refer you to Fear of Macros

2 Likes