cis352 10/11/22

10-11.rkt

#lang racket
(provide (all-defined-out))

;;
;; CIS352 (Fall '22) -- IfArith Intro
;;

;; builtin functions
(define (function-name? fn)
  (member fn '(+ - / * mod == =0? not)))

;; values are just numbers
(define value? number?)

;; expressions: no lambdas
;; evaluate to values -- there is an operation,
;; (eval-expr e env)
(define (expr? e)
  (match e
    [(? number? n) #t]
    ;; variables
    [(? symbol? x) #t]
    ;; named function application (no lambdas)
    [`(,(? function-name? fn) ,(? expr? e-args) ...) #t]
    [_ #f]))

;; statements chain together basic expressions
;; consume: - expressions, and environments
;; produce: - new (potentially changed) environments
(define (stmt? st)
  (match st
    ['skip #t]
    ;; '(x := 5)
    ;; '(y := x)
    [`(,(? symbol? x) := ,(? expr? e)) #t]
    ;; '(print (* 5 x))
    ;; '(print (* 5 (+ x (* y 2))))
    [`(print ,(? expr? e)) #t]
    ;; '(if0 (- 1 1) (print 5) (print 4))
    ;; ^^ prints 5
    [`(if0 ,(? expr? e-guard) ,(? stmt? s-true) ,(? stmt? s-false)) #t]
    ;; (begin (x := 1) (x := (+ x 1)) (print x))
    ;; ^^ prints 2
    ;; returns the updated environment { x |-> 2 }
    [`(begin ,(? stmt? es) ...) #t]
    ;; (begin (x := 10)
    ;;        (while-not0 x
    ;;           do
    ;;           (begin (print x) (x := (- x 1)))))
    [`(while-not0 ,(? expr? e-guard) do ,(? stmt? e)) #t]
    [_ #f]))

;; assuming args has been evaluated to a list of numbers, apply fn to
;; args.
(define (apply-builtin fn args)
  (define functions
    (hash '+ + '- - '* * '/ / '== =
          '=0? (lambda (x) (if (equal? (first x) 0) 0 1))
          'not (lambda (x) (if (= x 0) 1 0))))
  (apply (hash-ref functions fn) args))

(define environment? any/c)

;; (interp-ifarith e env) -- Interpret the expression e in the
;; environment. Return a number. Note: you should only ever
;; recursively call interp-expr, *not* interp.
(define/contract (interp-expr e env)
  (-> expr? environment? value?)
  (match e
    ;; return the number n
    [(? number? n) n]
    ;; look up the symbol x in the environment
    [(? symbol? x) (hash-ref env x)]
    [`(,op-name ,args ...)
     ;; args are current expressions
     ;;
     ;; use the function map to walk over each argument in args
     ;; and translate that down into a number by calling interp-expr
     ;; on it
     (define evaluated-arguments
       (map (lambda (arg) (interp-expr arg env)) args))
     (apply-builtin op-name evaluated-arguments)]
    
    ;; DEAD CODE
    ;; to interpret a builtin function named f, evaluate each of its
    ;; arguments (why is this important?) and then apply the function using apply-function
    [`(* ,e0 ,e1)
     (* (interp-expr e0 env) (interp-expr e1 env))]
    [`(+ ,e0 ,e1)
     (+ (interp-expr e0 env) (interp-expr e1 env))]
    [`(- ,e0 ,e1)
     (- (interp-expr e0 env) (interp-expr e1 env))]
    [`(/ ,e0 ,e1)
     (/ (interp-expr e0 env) (interp-expr e1 env))]
    [`(mod ,e0 ,e1)
     (modulo (interp-expr e0 env) (interp-expr e1 env))]
    [`(== ,e0 ,e1)
     (let ([v0 (interp-expr e0 env)]
           [v1 (interp-expr e1 env)])
       (if (= v0 v1)
           ;; true
           0
           ;; false
           1))]
    [`(=0? ,e0)
     (if (= 0 (interp-expr e0 env))
         0
         1)]
    [`(not ,e0)
     (if (= 0 (interp-expr e0 env))
         ;; e0 evals to true, thus return false
         1
         ;; e1 evals to false, thus return true
         0)]))

;; (mod 2 1)

;; (interp stmt env) -- Interpret the statement stmt in the
;; environment stmt.
(define/contract (interp stmt env)
  (-> stmt? environment? environment?)
  (match stmt
    ;; skipping this statement just returns the old environment
    ['skip env]
    ;; assign s to the value computed by e
    [`(,x := ,e)
     ;; evaluate the expression e (using the expression evaluator)
     ;; then assign it to the variable s in the environment env
     (define v (interp-expr e env))
     (hash-set env x v)]
    ;; compute e--print its value, return same environment
    [`(print ,e)
     (define v (interp-expr e env))
     (displayln v)
     env]
    ;; run each of es, return the final resulting environment hint:
    ;; use foldl, start with the initial environment, call interp on
    ;; the accumulated current environment, iterate over the
    ;; statements within the begin.
    [`(begin ,stmts ...) (foldl (lambda (e env) 'todo) env stmts)]
    ;; evaluate e0, if it's 0 evaluate e1, otherwise evaluate e2
    [`(if0 ,e0 ,s1 ,s2) 'todo]
    ;; while e-guard is not 0, evaluate e
    ;; hint: define a helper function that recursively evaluates the guard
    [`(while-not0 ,e-guard do ,s)
     (define (h env)
       'todo)
     (h env)]))

;; write a program here which swaps the value of x and y, and then
;; doubles y.
;; hint: use '(begin ...), introduce a new helper variable
(define swap-then-double
  'todo)

;; write a program here which computes the factorial, assume the input
;; variable is stored in x, leave your output in the variable `res`
;; 
;; your program should look something like ...
;; '(begin (res := 1) ...)
;; 
;; hint: use while-not0, count x down to 0, etc...
(define factorial
  'todo)