I don't want help solving this question however I would like to know exactly what it's asking for. And in order to better understand what it's asking for I'm asking if anyone could provide me with an example input and its corresponding output.
Write and certify a recursive procedure check which inputs an sexp s
and a list varlst
of identifiers and decides whether s belongs to the class of fully
parenthesized infix +-expressions fpip defined as follows:
var ::= a | b | c | d | e | f | g
fpip ::= var | (fpip + fpip)
Example of valid "fpip" expressions:
a
(a + b)
((a + b) + (c + d))
Explanation:
The first definition "var" tells you that it can be one of the symbols a ... g.
The second definition "fpip" tells you have either "var" or the compound expression of (fpip + fpip). Thus that means that a is a valid "fpip" since a is a valid "var". It also means (a + b) is a valid "fpip". What you get in addition by using "fpip" in place of "var" in the compund expression is nesting, like the valid "fpip" ((a + b) + (c + d)).
As a hint. Your procedure would mirror the definition. It will check if the argument is a var and if not it needs to check if it's like the second definition, which includes two recursive calls to check each part is also valid.
What is not explained very good is the purpose of varlist. I imagine that it represents allocated variables and that a "var" need not only be a ... g to be valid, but also that the identifiers also exists in varlist for it to be valid. This is an educated guess since I've made my share of interpreters, but I think it should have been specified clearer. eg. perhaps:
(fpip? 'c '(b a q)) ; ==> #f (c is in "var" definition but not in varlist)
(fpip? 'a '(b a q)) ; ==> #t (a is in "var" definition and in varlist)
(fpip? 'q '(b a q)) ; ==> #f (q is not in "var" definition)