*Review HW1 Solutions.*

# Desugaring

There are two ways to add a new feature to a programming language:

1. ☑ Give meaning to the feature via interpretation function
2. ☑ Give meaning to the feature based on existing features

(2) is done through a process called “desugaring”. Some features in programming
languages do not increase the expressive power of the language. For example,
because our language has addition and multiplication, it is possible to encode
subtraction through a combination of addition and multiplication with `-1`.

    x - y = x + (-1) × y

We now have *three* objects of interest: the “source” language (the language
which includes subtraction), the “core” language (the language with just plus
and multiplication), and the “domain” of interpretation (integers).

Formally, our source language now looks like this:

    eₛ ∈ sexpr ⩴ i
              | eₛ + eₛ
              | eₛ × eₛ
              | eₛ - eₛ

our core language looks like this:

    e ∈ cexpr ⩴ i
              | e + e
              | e × e

and our doman of interpretation looks like this:

    v ∈ value ⩴ i

The desugaring of subtraction is a recursive traversal of the term:

    desugar ∈ sexp → cexp
    desugar(i) ≜ i
    desugar(eₛ₁ + eₛ₂) ≜ desugar(eₛ₁) + desugar(eₛ₂)
    desugar(eₛ₁ × eₛ₂) ≜ desugar(eₛ₁) × desugar(eₛ₂)
    desugar(eₛ₁ - eₛ₂) ≜ desugar(eₛ₁) + (-1) × desugar(eₛ₂)

☑ Note that the right-hand-side is syntax, not math.

The interpreter is the same as before:

    interp ∈ cexp → value
    interp(i) ≜ i
    interp(e₁ + e₂) ≜ interp(e₁) + interp(e₂)
    interp(e₁ × e₂) ≜ interp(e₁) × interp(e₂)

Q: how would you encode unary negation?

    e ∈ sexpr ⩴ i
              | eₛ + eₛ
              | eₛ × eₛ
              | eₛ - eₛ
              | neg eₛ

    desugar ∈ sexp → cexp
    𝟏 ?? desugar(neg eₛ) ≜ 0 - desugar(eₛ)
    𝟐 ?? desugar(neg eₛ) ≜ desugar(0 - eₛ)
    𝟑 ?? desugar(neg eₛ) ≜ (-1) × desugar(eₛ)

The 3rd solution is the “preferred” one. The 2nd one works. The 1st one doesn't
work. (why not??)

# Partiality in Interpretation

Let's unwind and consider another extension which can't be desugared: division:

    e ∈ cexpr ⩴ i
              | e + e
              | e × e
              | e / e

Our interpreter is changed in two ways:

1. the set `value` now contains rational numbers, not integers
2. the interpreter is undefined in some cases (a.k.a, is partial), e.g., `5 /
   0` has no meaning

To handle (1) we redefine values to be rational numbers `q ∈ ℚ`:

    v ∈ value ⩴ q ∈ ℚ

There are two ways to communicate the meaning of expressions. One is to defer
to what is defined or not in math:

    interp ∈ cexpr ⇀ value
      ⋮
    interp(e₁ / e₂) ≜ interp(e₁) / interp(e₂)

This is “not wrong”, but we can do better by making the “partiality” explicit.
To do this, we define a new set `answer` as follows:

    a ∈ answer ⩴ v
               | BAD

The answer `BAD` is an explicit result value that means “something bad
happened”. For this language, we will signal `BAD` when division by zero
happens.

    interp ∈ cexp → answer
      ⋮
    interp(e₁ / e₂) ≜ q₁ / q₂
      when interp(e₁) = q₁
      and  interp(e₂) = q₂
      and  q₂ ≠ 0
    interp(e₁ / e₂) ≜ BAD
      when interp(e₁) = BAD
      or   interp(e₂) = BAD
      or   interp(e₂) = 0

We can write this in another style as follows:

    interp ∈ cexp → answer
    interp(e₁ / e₂) ≜ 
      case interp(e₁),interp(e₂):
        q₁,q₂ | q₂ ≠ 0 → q₁ / q₂
        q₁,q₂ | q₂ = 0 → BAD
        BAD,q₂ → BAD
        q₁,BAD → BAD
        BAD,BAD → BAD

Lecture Code Notes [Lc4.hs](../lc/Lc4.hs):

    -- Lecture Code Notes
    module Lc4 where
    
    import Data.Ratio -- support for rational numbers (type Rational)
    
    -- e ∈ cexpr ⩴ i
    --           | e + e
    --           | e × e
    data ExprC = IntEC Integer
               | PlusEC ExprC ExprC
               | TimesEC ExprC ExprC
      deriving (Eq,Ord,Read,Show)
    
    -- eₛ ∈ sexpr ⩴ i
    --            | e + e
    --            | e × e
    --            | e - e
    --            | neg e
    data ExprS = IntES Integer
               | PlusES ExprS ExprS
               | TimesES ExprS ExprS
               | MinusES ExprS ExprS
               | NegateES ExprS
      deriving (Eq,Ord,Read,Show)
    
    interp :: ExprC -> Integer
    interp (IntEC i) = i
    interp (PlusEC e1 e2) = interp e1 + interp e2
    interp (TimesEC e1 e2) = interp e1 * interp e2
    
    desugar :: ExprS -> ExprC
    desugar (IntES i) = IntEC i
    desugar (PlusES e1 e2) = PlusEC (desugar e1) (desugar e2)
    desugar (TimesES e1 e2) = TimesEC (desugar e1) (desugar e2)
    desugar (MinusES e1 e2) = PlusEC (desugar e1) (TimesEC (IntEC (-1)) (desugar e2))
    desugar (NegateES e) = TimesEC (IntEC (-1)) (desugar e)
    
    -- e ∈ cexpr ⩴ i
    --           | e + e
    --           | e × e
    --           | e / e
    data ExprD = IntED Integer
               | PlusED ExprD ExprD
               | TimesED ExprD ExprD
               | DivideED ExprD ExprD
      deriving (Eq,Ord,Read,Show)
    
    -- v ∈ value ⩴ q ∈ ℚ
    type Value = Rational
    
    -- a ∈ answer ⩴ v
    --            | BAD
    data Answer = ValA Value
                | BadA
      deriving (Eq,Ord,Read,Show)
    
    interpD :: ExprD -> Answer
    interpD (IntED i) = ValA (fromIntegral i)
    interpD (PlusED e1 e2) = case (interpD e1,interpD e2) of
      (ValA q1,ValA q2) -> ValA (q1 + q2)
      _ -> BadA
    interpD (TimesED e1 e2) = case (interpD e1,interpD e2) of
      (ValA q1,ValA q2) -> ValA (q1 * q2)
      _ -> BadA
    interpD (DivideED e1 e2) = case (interpD e1,interpD e2) of
      (ValA q1,ValA q2) | q2 /= 0 -> ValA (q1 / q2)
      _ -> BadA