#lang racket #| ★ CSC324 2017 Fall Exercise 3 ★ |# #| The fixed point iteration operation, and some term rewriting. |# (provide fixed-point deep-map-once If-rule Let-rule) #| ★ Implement ‘fixed-point’. fixed-point : [any → any] any → any (fixed-point f v₀) is the first value v in the sequence v₀ (f v₀) (f (f v₀)) ... such that v is equal to (f v). |# ; Some test cases. (module+ test (require rackunit) (define (a v) (min 128 (add1 v))) (check-equal? (fixed-point a 128) 128) (check-equal? (fixed-point a 127) 128) (check-equal? (fixed-point a 123) 128) (define (b v) (cond [(list? v) (first v)] [else v])) (check-equal? (fixed-point b '(((a (b)) c) (d e) f)) 'a) ; And some partial partial designs, which you might find useful to fix and work with. ; However, you may ignore these if you prefer. #;(check-equal? (fixed-point a 123) (local [(define v′ (a 123))] "replace")) #;(check-equal? (fixed-point a 127) (local [(define v′ (a 127))] "replace")) #;(check-equal? (fixed-point a 128) (local [(define v′ (a 128))] "replace"))) (define (fixed-point f v₀) v₀) #| ★ Implement ‘deep-map-once’. deep-map-once : [any → any] any → any If (f v) is different from v, then produce (f v). If not, and v is a list, produce the list where deep-map-once is used with f on each element of v. Otherwise, just produce v. |# ; Example. (module+ test (define (malkovich v) (deep-map-once (λ (v) (cond [(list? v) (list* 'malkovich (rest v))] [else v])) v)) (define v '(the (rain (in spain)) falls (mainly on (the plain)))) (check-equal? (malkovich v) '(malkovich (rain (in spain)) falls (mainly on (the plain)))) (check-equal? (malkovich (malkovich v)) '(malkovich (malkovich (in spain)) falls (malkovich on (the plain)))) (check-equal? (fixed-point malkovich v) '(malkovich (malkovich (malkovich spain)) falls (malkovich on (malkovich plain))))) (define (deep-map-once f v) v) #| ★ Implement the Lambda Calculus rewrite rules for ‘If’, and for simple ‘Let’ abbreviations. Use ‘match’ appropriately. |# ; A "rewrite" system, which in the context of rewriting source code syntactic shorthands is also ; called "expansion". (define (expand f v) (fixed-point (λ (v) (deep-map-once f v)) v)) ; Example of a rule and its use with expand. (module+ test (define (Define-rule term) (match term ; (Define ( ) ) → (Define (Lambda () )) [`(Define (,f-id ,id) ,e ) `(Define ,f-id (Lambda (,id ) ,e ))] ; Equivalently, in list constructor form for the pattern, and for the result expression. #;[(list 'Define (list f-id id) e) (list 'Define f-id (list 'Lambda (list id) e))] ; A variable matches anything. [t t])) (check-equal? (expand Define-rule '(Local [(Define (False t) (Lambda (e) e)) (Define ((True t) e) t) (Define Not (Lambda (b) (If b False True)))] (Local [(Define (Two f x) (f (f x))) (Define (g a) (g a))]) (g Two))) '(Local ((Define False (Lambda (t) (Lambda (e) e))) (Define True (Lambda (t) (Lambda (e) t))) (Define Not (Lambda (b) (If b False True)))) (Local ((Define (Two f x) (f (f x))) (Define g (Lambda (a) (g a))))) (g Two)))) ; ★ Implement Let-rule to transform terms of the form #;(Let ( ) ) ; into #;((Lambda () ) ) ; leaving alone terms that are not of that form. ; (define (Let-rule term) term) (module+ test (check-equal? (Let-rule '(Let (g (Lambda (a) (g a))) (g g))) '((Lambda (g) (g g)) (Lambda (a) (g a))))) ; ★ Implement If-rule to transform terms of the form #;(If ) ; into #;( (Lambda () ) (Lambda () )) ; leaving alone terms that are not of that form. ; (define (If-rule term) term) ; ★ Make at least one unit test for If-rule, and at least one test with expand on a term ; that contains nested Ifs. (module+ test )