Generate-Contraints Question

[Brad Seebeck]

So I thought i understood what a constraint was, but after trying to
write this function, I obviously don't. I know what a constraint is,
and what it means, but i dont understand how to go about writing a
function that does it. I read the other post about e-id and that left
me more confused. Does anyone have any hints? or at least an example
of what the function should return for a simple expression?

Thanks

[Bryan Morse]

Here's a very simple starting point for generate-constraints:

(define (generate-constraints e-id e)
(type-case Expr e
(num (n) (list (eqc (t-var e-id) (t-num))))
(id (v) (list (eqc (t-var e-id) (t-var v))))
; ...
(bin-num-op (op lhs rhs)
(local ([define lhs-id (gensym)]
[define rhs-id (gensym)]
[define lhs-c (generate-constraints lhs-id lhs)]
[define rhs-c (generate-constraints lhs-id lhs)])
(append
(list (eqc (t-var e-id) (t-num))
(eqc (t-var lhs-id (t-num)))
(eqc (t-var rhs-id (t-num))))
lhs-c
rhs-c)))
(else (error "Constraint generation not finished yet."))
))

Notice a few things about it:

1. It always generates a list of constraints created by calling the "eqc" constructor for the Constraint type.

2. For numeric literals, it just says that this expression (identified by the type variable e-id passed into the function) is a number.

3. For identifiers, it just says that this expression (again identified by the type variable e-id passed into the function) the same as the type of the variable. Remember that you've already done alpha renaming, so all identifiers are unique and you can just use their names as unique type variables.

4. For things with subexpressions (such as bin-num-op), it does the following:

a. Creates identifiers for its subexpressions by using gensym.

b. Recursively calls generate-constraints for the subexpression and passes their generated ids with them.

c. Creates new constraints based on this expression (with its e-id) and the subexpressions (with their e-ids just created). So for bin-num-op here, it makes constraints that this expression must result in a number and that each of the two subexpressions must result in a number.

d. Appends together all of the constraints generated from the subexpressions along with the constraints generated for the current expression and returns this as one big list to the caller (who probably does the same, all the way back up to the root call).

The main thing I wanted you to see with this example is the above pattern for generating e-ids, recursing on subexpressions, generating constraints, and returning all of the constraints for this subtree. You should be able to flesh out the rest from here.