#lang racket ;; thunks for delayed evaluation for performance ;; (or termination) (define (print-add x y) (begin (printf "Calling (print-add ~s ~s)\n" x y) (+ x y))) (define (my-mult x y-thunk) ;; assumes x is >= 0 (cond [(= x 0) 0] [(= x 1) (y-thunk)] [#t (+ (y-thunk) (my-mult (- x 1) y-thunk))])) ;; thunk print-add ;(my-mult 0 (lambda () (print-add 3 4))) ;(my-mult 1 (lambda () (print-add 3 4))) ;(my-mult 2 (lambda () (print-add 3 4))) ;; thunk the result of print-add ;(my-mult 0 (let ([x (print-add 3 4)]) (lambda () x))) ;(my-mult 1 (let ([x (print-add 3 4)]) (lambda () x))) ;(my-mult 2 (let ([x (print-add 3 4)]) (lambda () x))) ;; memoization (purity key) (define (my-delay th) (mcons #f th)) ;; a one-of "type" we will update /in place/ (define (my-force p) (if (mcar p) (begin (printf "Promise already evaluated. Returning...\n") (mcdr p)) (begin (printf "First force of this promise. Evaluating...\n") (set-mcar! p #t) (set-mcdr! p ((mcdr p))) (mcdr p)))) ;; for my-mult ;(my-mult 0 (let ([x (my-delay (lambda () (print-add 3 4)))]) (lambda () (my-force x)))) ;(my-mult 1 (let ([x (my-delay (lambda () (print-add 3 4)))]) (lambda () (my-force x)))) ;(my-mult 2 (let ([x (my-delay (lambda () (print-add 3 4)))]) (lambda () (my-force x)))) ;; streams -- (a.k.a. infinite lists) ;(define ones-really-bad (cons 1 ones-really-bad)) ;; Why is this one bad? (define ones-bad (lambda () (cons 1 (ones-bad)))) ;; Why is this one good? (define ones (lambda () (cons 1 ones))) ;; Natural numbers (define nats (letrec ([f (lambda (x) (cons x (lambda () (f (+ x 1)))))]) (lambda () (f 1)))) ;; bad 1 (define nats-bad-1 (letrec ([f (lambda (x) (cons x (f (+ x 1))))]) (lambda () (f 1)))) ;; bad 2 (define nats-bad-2 (letrec ([f (lambda (x) (cons x (lambda () (f (+ x 1)))))]) (f 1))) ;; Powers of two (define powers-of-two (letrec ([f (lambda (x) (cons x (lambda () (f (* x 2)))))]) (lambda () (f 2)))) ;; General function to make a stream out of a "successor" ;; function and a "step" value. (define (stream-maker fn arg) (letrec ([f (lambda (x) (cons x (lambda () (f (fn x arg)))))]) (lambda () (f arg)))) (define nats2 (stream-maker + 1)) (define powers2 (stream-maker * 2)) ;; Count a stream. (define (number-until stream tester) (letrec ([f (lambda (stream ans) (let ([pr (stream)]) (if (tester (car pr)) ans (f (cdr pr) (+ ans 1)))))]) (f stream 1))) ; (number-until powers2 (lambda (x) (= x 16))) ;; Print a stream (define (print-until stream tester) (let* ([pr (stream)] [x (car pr)] [xs (cdr pr)]) (if (tester x) null (begin (printf "~s\n" x) (print-until xs tester))))) ;(print-until powers2 (lambda (x) (= x 64))) ;; fibs (define (fibs) (letrec ([fib-next (lambda (p1 p2) (lambda () (let ([n (+ p1 p2)]) (cons n (fib-next p2 n)))))]) (cons 1 (fib-next 0 1)))) ;(print-until fibs (lambda (x) (> x 1000))) ;; 12:30 section got to here. ;; Make a new stream from an existing stream (define (every-other stream) (lambda () (let ([pr (stream)]) (cons (car pr) (every-other (cdr ((cdr pr)))))))) ;(print-until (every-other nats) (lambda (x) (> x 20))) ;; Miscellany ;;;;;;;;;;; ;; Streams are kind of like lists... they use cons cells... ;; So can we use list functions on them? ; (length (nats)) ;; assoc ;; How is this different than we would do it in ML? Why? (define (my-assoc x xys) (if (null? xys) #f ;; how do I tell "k is not in the list" from "k is in the list, mapped to value #f"? (if (equal? (car (car xys)) x) (car xys) ;; return the whole pair when a match is found. (my-assoc x (cdr xys))))) ;; 1:30 section got to here. (define (my-assoc-2 x xys) (cond ((null? xys) #f) ((equal? (caar xys) x) (car xys)) (else (my-assoc x (cdr xys))))) ; (my-assoc 3 (cons (cons 1 2) (cons (cons 3 4) (cons (cons 5 6) null)))) ; (my-assoc 3 (cons (cons 1 2) (cons (cons 3 4) (cons (cons 5 6) null)))) ; (my-assoc-2 3 (cons (cons 1 2) (cons (cons 3 4) (cons (cons 5 6) null)))) ;; further material pushed to later. ;; Useful notes that came up: (letrec ([g (lambda (x) x)] [f (g f)]) ;; uh oh, using f when not yet defined... ;; but wait, it's OK! f is #, but that's a *value* that g is willing to accept! ;; (+ 1 f) would fail, but (g f) does not. (g (cons 8 f)))