DrRacket: Desurgaring all uses of and, or, not into nested ifs

Question

So I am currently learning how to program and we started with DrRacket. This week the task consists of using pattern matching and working/translating expressions into s-expressions and vice versa. I was able to implement most of the task in a some-what satisfactory manner, but this last task is just really confusing for me and I don't even know how to start. So far, it was my task to write the "core language" and this last function is supposed to translate the "extended language" (with and, or, not) into nested ifs (the "core language" only uses if).

Do you have some tips on how to implement this with pattern matching? I have given the signature and a test so that it is clear what this function is suppose to do.

; S-Expression -> S-Expression
; Desugars all uses of and, or, not and cond into (potentially nested) ifs.
(check-expect (desugar '(and #true #false)) '(if #true (if #false #true #false) #false))

Thank you for any help!

Answer 1

The trick is to think about what it is that things like and and or need to turn into if all you have is if.

not is really too simple to talk about, so I won't.

and is reasonably easy and divides into three cases (so this is where pattern-matching is going to help you).

• (and) is true;
• (and x) true if x is true, so it's just equivalent to x
• (and x y ...) is true if x is true and if (and y ...) is true.

So the only interesting case is the last one. Well, how do you express that case? Something like (if x (and y ...) #f), right?

or is more interesting and significantly harder if you want to get the traditional Lisp/Scheme semantics.

If what you want is a simple or which returns a boolean then it is easy:

• (or) is false;
• (or x) is the same as x;
• (or x y ...) is true if x is true, or if (or y ...) is true, and this means that it is (if x #t (or y ...)).

And that's fine, but that's not what Scheme or Lisp traditionally do. For Scheme or Lisp the rules are (differences in italics):

• (or) is false;
• (or x) is the same as x;
• (or x y ...) is the value of x if x is true, and otherwise it is the value of (or y ...).

Notice that the last rule is different. It is tempting to turn the last rule into (if x x (or y ...)). Why is this incorrect? What is the correct expansion (hint: it includes let or equivalently lambda.)?

---

So now the final important thing to understand is that the thing that turns the complicated language into the simple language has to work recursively: if you get a form like (a ...) you need to decide:

• if a is a special thing you know how to deal with (like if), and if it is you will have a set of rules which tell you which parts of the form you need to inspect further (for if the answer is 'all of them');
• is a is something we know how to turn into a simpler thing (to 'expand' into a simpler thing), in which case expand it into the simpler thing and then look at that simpler thing;
• if a is something you don't know about in which case you just evaluate it to produce a function, process the other forms and then apply the function to the other forms;
• there are no other options.