MASSACHVSETTS INSTITVTE OF TECHNOLOGY Department of Electrical Engineering and Computer Science 6.5150/6.5151 Spring 2024 Problem Set 5 Issued: Wed. 13 March 2024 Due: Fri. 22 March 2024 Reading: SICP Section 4.4, especially 4.4.4.3 and 4.4.4.4 MIT Scheme Reference Manual, section 2.11: Macros. This is complicated stuff, so don't try to read it until you need to. SDF Chapter 4: Pattern Matching, but 4.5 is optional Code: This time you got an enormous pile of code -- covering almost all of Chapter 4. But it is divided up so you can easily see what section each chunk is for. Besides the material in common, the SDF code directory has (flavors) subdirectories named term- rewriting, design-of-the-matcher, unification, and pattern- matching-on-graphs. This problem set only concerned with term- rewriting and design-of-the-matcher, but all of these pieces can be loaded as a combined image using the manager: (manage 'new 'term) (manage 'add 'design) (manage 'add 'unification) ;; (manage 'add 'graph) ; Optional TO DO Problem 4.4: Collecting Terms (SDF p. 164) Problem 4.5: Backtracking (SDF p. 179) Problem 4.a: Collector Variables (Not in book) A collector variable collects multiple match instances in the datum it matches. For example: (match? '(a (($ b) 2 3) ($ b) c) '(a (1 2 3) 1 c)) ;Value: ((b 1)) (match? '(a (($ b) 2 3) ($ b) c) '(a (1 2 3) 2 c)) ;Value: ((b (2 1))) Implement a new matcher procedure, match:collect, to handle this new pattern schema, and augment the pattern compiler appropriately. Problem 4.8a: Hoist by our own petard (SDF p. 182) (problem 4.8b is optional) Problem 4.14: Procedures (SDF p. 201) Problem 4.15: Parametric types (SDF p. 202)