CS代写 #lang racket

#lang racket

(require racket/trace)

Copyright By PowCoder代写 加微信 powcoder

#|—————————————————————————–
;; Prelude: user defined types with `struct`
—————————————————————————–|#

;; define a `widget` type
(struct widget ; type name
(name purpose price) ; attributes
#:transparent) ; when printing a widget, show its attributes

;; we get the following functions for free:
;; – `widget`: constructor
;; – `widget?`: predicate that returns #t for widget values
;; – `widget-name`: retrieve `name` attribute
;; – `widget-purpose`: retrieve `purpose` attribute
;; – `widget-price`: retrieve `price` attribute

(define w1 (widget “wrench” “wrenching” 9.99))
(define w2 (widget “plier” “pliering” 12.99))

;; define a `doohickey` type that is a sub-type of `widget`
(struct doohickey widget (special-power) #:transparent)

(define d1 (doohickey “thingamajig” “thinging” 199.99 “time travel”))

#|—————————————————————————–
;; Our language

We’re going to start with a very simple language and slowly add to it. Our
first iteration will support integer literals, the binary arithmetic operations
+` and `*`, and `let`-bound variables. The syntax will mirror Racket’s.
—————————————————————————–|#

;; Some test cases
(define p1 ‘(+ 1 2))

(define p2 ‘(* 2 (+ 3 4)))

(define p3 ‘(+ x 1))

(define p4 ‘(* w (+ x y)))

(define p5 ‘(let ([x 10])

(define p6 ‘(let ([x 10]

(define p7 ‘(let ([x 10])
(let ([y 20])
(+ x (let ([w 30])
(* w y))))))

#|—————————————————————————–
;; Scanner

Review: What is scanning?

– Raw text input => “tokens” / words
—————————————————————————–|#

;; `read` does much more than just scan our input! Because of how simple
;; Racket syntax is, `read` returns an unadorned, list-based “syntax tree”
;; based on the input — i.e., an s-expression.

#|—————————————————————————–

Review: What is parsing?

– Tokens => Syntax tree

– Syntax tree = a representation of the syntactic structure of the code

– We can “decorate” nodes of the tree with attributes useful for evaluation,
optimization, etc.

Because Racket’s `read` does so much for us, we already have a syntax tree!
We just need to decorate it now 🙂
—————————————————————————–|#

;;; Some types for decorating our syntax tree

;; integer value
(struct int-exp (val) #:transparent)

;; arithmetic expression
(struct arith-exp (op lhs rhs) #:transparent)

;; variable
(struct var-exp (id) #:transparent)

;; let expression
(struct let-exp (ids vals body) #:transparent)

;; Parser v1
#; (define (parse sexp)
[(number? sexp) (int-exp sexp)]
[(equal? (first sexp) ‘+)
(let ([lhs (second sexp)]
[rhs (third sexp)])
[(equal? (first sexp) ‘*)
(let ([lhs (second sexp)]
[rhs (third sexp)])
(void))]))

;; Digression: pattern matching with `match`
(define (matcher sexp)
(match sexp
[(? number?) sexp]
[‘a ‘apple]
[(list _ _) ‘any-two]
[(list ‘a _ _) ‘a-and-two-things]
[(list ‘a ‘b c d) (+ c d)]
[(list a _ _ a) a]
[(list ‘foo (list b …) c) (list b c)]
[(widget “wrench” pur pri) pri]
[(doohickey name _ _ _) name]
[_ (error (format “Can’t parse: ~a” sexp))]))

;; Parser v2: using `match`
(define (parse sexp)
(match sexp
;; for interpreter v1: arithmetic
[(? integer?)
(int-exp sexp)]
[(list ‘+ lhs rhs) (arith-exp “+” (parse lhs) (parse rhs))]
[(list ‘* lhs rhs) (arith-exp “*” (parse lhs) (parse rhs))]
#; [(list (and op (or ‘+ ‘*)) lhs rhs) ; alternative to above two patterns
(arith-exp (symbol->string op) (parse lhs) (parse rhs))]

;; for interpreter v2: variables
[(? symbol?)
(var-exp sexp)]
[(list ‘let (list (list id val) …) body)
(let-exp (map parse id) (map parse val) (parse body))]

;; basic error handling
[_ (error (format “Can’t parse: ~a” sexp))]))

#|—————————————————————————–
;; Interpreter

Syntax tree => Evaluation
—————————————————————————–|#

;; Interpreter v1: Integers and Arithmetic
#; (define (eval expr)
(match expr
;; ints evaluate to themselves
[(int-exp val) val]

;; arithmetic operations
[(arith-exp “+” lhs rhs)
(+ (eval lhs) (eval rhs))]
[(arith-exp “*” lhs rhs)
(* (eval lhs) (eval rhs))]

;; basic error handling
[_ (error (format “Can’t evaluate: ~a” expr))]))

;; Let’s define a REPL!
(define (repl)
(let ([stx (parse (read))])
(println (eval stx))

;; Interpreter v2: Adding variables
(define (eval expr)
(let eval-env ([expr expr]
[env ‘()])
(match expr
;; arithmetic
[(int-exp val) val]
[(arith-exp “+” lhs rhs)
(+ (eval-env lhs env) (eval-env rhs env))]
[(arith-exp “*” lhs rhs)
(* (eval-env lhs env) (eval-env rhs env))]

;; variable binding
#; [(var-exp id)
(cdr (assoc id env))]

;; variable binding with error handling
[(var-exp id)
(let ([pair (assoc id env)])
(if pair (cdr pair) (error (format “~a not bound!” id))))]

;; let expression with a single variable
#; [(let-exp (list (var-exp id)) (list val) body)
(eval-env body (cons (cons id (eval-env val env)) env))]

;; let expression with multiple variables
[(let-exp (list (var-exp id) …) (list val …) body)
(let ([vars (map cons id
(map (lambda (v) (eval-env v env)) val))])
(eval-env body (append vars env)))]

;; basic error handling
[_ (error (format “Can’t evaluate: ~a” expr))])))

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com