Understanding S-Expression Operators: Less, Eq, If0, App, and Rec

Posted on Feb 8, 2025 in Technology

S-Expression Operators: Less, Eq, If0, App, and Rec

  • Less refers to the less than operator (<). This checks both the left and right sides of the S-expression to ensure they are both `numType`. It then returns a `boolType`. In the assignment, it was unclear if this should also check if both sides were `boolType`.

[eq (l r)(if (and (numType? (get-type l tenv))(numType? (get-type r tenv)))(boolType)(error 'get-type "You need to match the types for the equality check operation"))]

  • Eq refers to the equality operator (==). This checks if both sides of the S-expression are the same `numType` and then returns a `boolType`.

[if0 (tst tv fv)(if (and (boolType? (get-type tst tenv))(equal? (get-type tv tenv)(get-type fv tenv)))(get-type fv tenv)(error 'get-type "Wrong types for the if condition, try again bud."))]

  • If0 refers to the if operator (cannot use `if` because it’s already a Scheme keyword).
    • Here, `get-type` is called on “tst” (the test condition) to ensure it follows correct types. `tst` could be anything like 4 < 5 or 4 == 6 or 5 * 3.
    • If that is correct and returns a `boolType`, then it checks if the two return values are correct types (`tv` and `fv` or “true value” and “false value”).
    • So, it calls `get type` on those because they as well could be their own S-expressions, and then if both of the returned types are equal, it returns the false value because it doesn’t matter since the true and false values are equal.
    • Otherwise, it returns an error.

[app (fun-expr arg-expr)(if (equal? (funType-domain (get-type fun-expr tenv)) (get-type arg-expr tenv))(funType-codomain (get-type fun-expr tenv))(error 'get-type "APP ERROR: your domain and the codomain types do not match"))]

  • App applies the substitutions to the function and creates a fun-tree at compile time. App takes two parameters: the function-expression and the arguments.
    • First, we check if the domain and codomain of the function are equal.
      • So, we check `funType-domain` — which we defined in the `TYPE-PARSE` function that will check what the type of the domain is (REFER TO TYPE-PARSE ABOVE). And we want to see if that is equal to the type of the arguments or (parameters) that will be substituted in by the `tenv` arg (this is the deferred substitution linked-list tree that is unloaded at compile time).
      • If the domain and the parameters are equal, then it will return the type of the codomain.
      • Else it will return an error.

[rec (bound-id id-type named-expr bound-body)(if (equal? (get-type bound-body (aTypeSub bound-id id-type tenv)) id-type)(funType-codomain id-type)(error 'get-type "Wrong type"))]

  • Rec handles recursion. The way this works is `rec` takes in a `bound-id` (basically a function name), an `id-type` (or just type that the function will return), and then the `named-expr` (or operation name like ‘+ or ‘- etc.), and `bound-body` which is the body of the function.
    • Then it checks the type that the body of the function returns (the `aTypeSub` with the name of the function and types and type-environment are passed along with the call to the `get-type` function).
      • This type is compared to the `id-type`.
      • The recursion is within calling `get-type` on the bound body of the function — this is because when you call `get type` on the function body there are other types within that body that could potentially needed to be checked, thus it will be checking that over and over.
    • If those are equal then it will return the type of the function’s codomain as the answer.
    • Otherwise, it will give an error.