# Representing Propositional Logic Expressions in Racket

**URL:** <https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569>\
**Category:** Questions & Answers\
**Tags:** question, propositional-logic, symbolic\
**Created:** [December 2, 2023, 11:12am UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569 "2023-12-02T11:12:51Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![xabush](https://avatars.discourse-cdn.com/v4/letter/x/bc8723/32.png) [@xabush](https://racket.discourse.group/u/xabush)\
**Post date:** [December 2, 2023, 11:12am UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/1 "2023-12-02T11:12:51Z")

</div>

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](https://github.com/aimacode/aima-python/blob/61d695b37c6895902081da1f37baf645b0d2658a/utils.py#L628)

```scheme
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.

```scheme
#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)`

---

<div class="post-metadata">

**Author:** ![soegaard](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/soegaard/32/19_2.png) [@soegaard](https://racket.discourse.group/u/soegaard)\
**Post date:** [December 2, 2023, 1:33pm UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/2 "2023-12-02T13:33:54Z")

</div>

I think, you want something like this:

```scheme
(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:

```scheme
(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:

```scheme
(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:

```scheme
(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.

---

<div class="post-metadata">

**Author:** ![xabush](https://avatars.discourse-cdn.com/v4/letter/x/bc8723/32.png) [@xabush](https://racket.discourse.group/u/xabush)\
**Post date:** [December 3, 2023, 12:28pm UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/3 "2023-12-03T12:28:53Z")

</div>

Thank you for your reply.

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

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

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

```

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

---

<div class="post-metadata">

**Author:** ![soegaard](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/soegaard/32/19_2.png) [@soegaard](https://racket.discourse.group/u/soegaard)\
**Post date:** [December 3, 2023, 12:50pm UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/4 "2023-12-03T12:50:08Z")

</div>

What does your program look like now?

---

<div class="post-metadata">

**Author:** ![xabush](https://avatars.discourse-cdn.com/v4/letter/x/bc8723/32.png) [@xabush](https://racket.discourse.group/u/xabush)\
**Post date:** [December 3, 2023, 2:18pm UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/5 "2023-12-03T14:18:44Z")

</div>

Here is the full code (including your suggestions):

```scheme
#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

```

---

<div class="post-metadata">

**Author:** ![soegaard](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/soegaard/32/19_2.png) [@soegaard](https://racket.discourse.group/u/soegaard)\
**Post date:** [December 3, 2023, 4:08pm UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/6 "2023-12-03T16:08:06Z")

</div>

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

 ![image](https://global.discourse-cdn.com/free1/uploads/racket/original/2X/9/9bcf9ee683821f10b58f841a2e7d10e22b39c4e8.jpeg)

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:

```scheme
(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))`.

---

<div class="post-metadata">

**Author:** ![LiberalArtist](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/liberalartist/32/151_2.png) [@LiberalArtist](https://racket.discourse.group/u/LiberalArtist)\
**Post date:** [December 3, 2023, 6:10pm UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/7 "2023-12-03T18:10:53Z")

</div>

> [@xabush](#):
>
> ```scheme
> (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
> 
> ```

I notice you are using `eval` in a way that will not work, because it does not provide an appropriate namespace. See [15.1&nbsp;eval](https://docs.racket-lang.org/guide/eval.html) in The Racket Guide for an introduction to the problem, and see [On `eval` in dynamic languages generally and in Racket specifically](https://blog.racket-lang.org/2011/10/on-eval-in-dynamic-languages-generally.html) 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:

> [@xabush](#):
>
> 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.

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:

```scheme
#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`.

---

<div class="post-metadata">

**Author:** ![sorawee](https://avatars.discourse-cdn.com/v4/letter/s/ea5d25/32.png) [@sorawee](https://racket.discourse.group/u/sorawee)\
**Post date:** [December 3, 2023, 6:35pm UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/8 "2023-12-03T18:35:23Z")

</div>

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`](https://github.com/aimacode/aima-python/blob/61d695b37c6895902081da1f37baf645b0d2658a/logic.py#L271). 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).

---

<div class="post-metadata">

**Author:** ![soegaard](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/soegaard/32/19_2.png) [@soegaard](https://racket.discourse.group/u/soegaard)\
**Post date:** [December 3, 2023, 7:00pm UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/9 "2023-12-03T19:00:46Z")

</div>

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

But maybe you simply wanted to experiment with macros?

---

<div class="post-metadata">

**Author:** ![LiberalArtist](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/liberalartist/32/151_2.png) [@LiberalArtist](https://racket.discourse.group/u/LiberalArtist)\
**Post date:** [December 3, 2023, 7:05pm UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/10 "2023-12-03T19:05:11Z")

</div>

> [@soegaard](#):
>
> an interpreter approach matches the book closer.
> 
> But maybe you simply wanted to experiment with macros?

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.

---

<div class="post-metadata">

**Author:** ![ulambda](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ulambda/32/1495_2.png) [@ulambda](https://racket.discourse.group/u/ulambda)\
**Post date:** [December 5, 2023, 6:06am UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/11 "2023-12-05T06:06:43Z")

</div>

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.

```scheme
(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.

```scheme
> (define exp0
    (And True (Or False False True) (And True False)))
> (exp0)
#f

```

---

<div class="post-metadata">

**Author:** ![xabush](https://avatars.discourse-cdn.com/v4/letter/x/bc8723/32.png) [@xabush](https://racket.discourse.group/u/xabush)\
**Post date:** [December 5, 2023, 8:34am UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/12 "2023-12-05T08:34:06Z")

</div>

> [@soegaard](#):
>
> FWIW I agree with @LiberalArtist and @sorawee that an interpreter approach matches the book closer.

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](https://github.com/soegaard/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:

```scheme
#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.

> [@LiberalArtist](#):
>
> what kind of "manipulat[ing] expressions symbolically" you want to support.

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](https://en.wikipedia.org/wiki/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`](https://github.com/aimacode/aima-python/blob/61d695b37c6895902081da1f37baf645b0d2658a/logic.py#L393C14-L393C14) function for completeness.

---

<div class="post-metadata">

**Author:** ![xabush](https://avatars.discourse-cdn.com/v4/letter/x/bc8723/32.png) [@xabush](https://racket.discourse.group/u/xabush)\
**Post date:** [December 6, 2023, 2:33pm UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/13 "2023-12-06T14:33:58Z")

</div>

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:

```scheme
#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:

```scheme
(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?

---

<div class="post-metadata">

**Author:** ![ulambda](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ulambda/32/1495_2.png) [@ulambda](https://racket.discourse.group/u/ulambda)\
**Post date:** [December 7, 2023, 5:49am UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/14 "2023-12-07T05:49:06Z")

</div>

There is no need for macros.

```scheme
(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))))))

```

```scheme
> (parse '(disj a (-> a b)))
(expr 'disj (list 'a (expr '-> '(a b))))

```

---

<div class="post-metadata">

**Author:** ![LiberalArtist](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/liberalartist/32/151_2.png) [@LiberalArtist](https://racket.discourse.group/u/LiberalArtist)\
**Post date:** [December 7, 2023, 6:38am UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/15 "2023-12-07T06:38:05Z")

</div>

> [@xabush](#):
>
> 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.

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

```scheme
'(& (|| (~ 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.

---

<div class="post-metadata">

**Author:** ![LiberalArtist](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/liberalartist/32/151_2.png) [@LiberalArtist](https://racket.discourse.group/u/LiberalArtist)\
**Post date:** [December 7, 2023, 7:39am UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/16 "2023-12-07T07:39:26Z")

</div>

> [@xabush](#):
>
> 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](https://en.wikipedia.org/wiki/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`](https://github.com/aimacode/aima-python/blob/61d695b37c6895902081da1f37baf645b0d2658a/logic.py#L393C14-L393C14) function for completeness.

You might find the [Nanopass Framework](https://docs.racket-lang.org/nanopass/index.html) 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:

```scheme
#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))))))

```

---

<div class="post-metadata">

**Author:** ![xabush](https://avatars.discourse-cdn.com/v4/letter/x/bc8723/32.png) [@xabush](https://racket.discourse.group/u/xabush)\
**Post date:** [December 7, 2023, 11:12am UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/17 "2023-12-07T11:12:42Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![xabush](https://avatars.discourse-cdn.com/v4/letter/x/bc8723/32.png) [@xabush](https://racket.discourse.group/u/xabush)\
**Post date:** [December 7, 2023, 11:25am UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/18 "2023-12-07T11:25:11Z")

</div>

> [@LiberalArtist](#):
>
> Previous versions of this code already did "encapsulat[e] a logical expression in some data structure," namely a list. In an expression represented as:
> 
> ```scheme
> '(& (|| (~ 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.

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)

```scheme
(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

> [@LiberalArtist](#):
>
> You might find the [Nanopass Framework](https://docs.racket-lang.org/nanopass/index.html) a nice way to write these kinds of transformations.

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.

---

<div class="post-metadata">

**Author:** ![ulambda](https://yyz2.discourse-cdn.com/free1/user_avatar/racket.discourse.group/ulambda/32/1495_2.png) [@ulambda](https://racket.discourse.group/u/ulambda)\
**Post date:** [December 12, 2023, 11:04am UTC](https://racket.discourse.group/t/representing-propositional-logic-expressions-in-racket/2569/19 "2023-12-12T11:04:00Z")

</div>

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:

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

```

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

```scheme
> (& (~ 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.

```scheme
(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.

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

```

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

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

```

```scheme
> (|| '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](https://www.greghendershott.com/fear-of-macros/)