Assignment 3

Trace the execution of the following expressions. Give the execution snapshots just before the points marked with a ^^ and indicate what is displayed.

(define (new-point ix iy) 
     ((lambda (x y) 
          (define (getx) x) 
          (define (setx sx) (set! x sx)) 
          (define (gety) y) 
          (define (sety sy) (set! y sy)) 
          (define (dispatch m y) 
                ^^ 
               (cond    ((= m 1) (getx)) 
                            ((= m 2) (gety)) 
                            (( = m 3) (setx x)) 
                            ((= m 4) (sety y)))) 
          dispatch) 
     ix iy))
(define getx 1) 
(define gety 2) 
(define setx 3) 
(define sety 4) 
(define rectangle (list (new-point 20 40) (new-point 60 40))) ^^ 
(define first car) 
(define reset cdr) 
(display ((first rectangle) setx 32 )) ^^
(display ((first (rest rectangle)) sety 44 ))

In a manner similar to the implementation of a BankAccount object described in class, implement a Queue object that has a constructor and the behaviors enqueue, dequeue, and isEmpty. You can also provide other behaviors as requireed.

; Assignment 3, question 2
; Rakhim Davletkaliyev, 100750928
 
(define (create-queue)
  (let 
      ((mpty #t) (the-list '() ))
  (define (enque value)
 
           (set! the-list (append the-list (list value)))
           (set! mpty #f)
    the-list
 
    )
  (define (deque)
     (set! the-list (cdr the-list))
           (if (= (length the-list) 0) 
               (set! mpty #t))
 
           the-list)
 
  (define (isEmpty)
    mpty)
 
  (define (ptl)
    the-list)
 
  (define (dispatch method)
    (cond ((eq? method 'enque) enque)
          ((eq? method 'deque) deque)
          ((eq? method 'isEmpty) isEmpty)
          ((eq? method 'print) ptl)
          )
    )
 
  dispatch
           ))

Add the special forms LET and LET* to the to the metacircular interpreter. Make sure you understand the differences between let and let*. Watch out for the following common mistakes:

  (let* (( x ( + 1 2))) x) returns (+ 1 2) instead of the correct answer 3.

  (let* (( x 2)) 1 2 (+ x 4)) returns 1 instead of the correct answer 6 (the value of the last expression)

  (define x 1) 
  (let* ((x 2) (y (+ x 10))) y) returns 11 instead of the correct answer 12.

(let* is similar to let except that the bindings are evaluated in sequence from right to left and each of the bindings is within the scope of the variables to the left. Put another way, the value for variable y is computed in the environment extended with the 'new' value of x)

;;;;This file can be loaded into Scheme as a whole.
;;;;Then you can initialize and start the evaluator by evaluating
;;;; the two commented-out lines at the end of the file (setting up the
;;;; global environment and starting the driver loop).
 
;;;;**WARNING: Don't load this file twice (or you'll lose the primitives
;;;;  interface, due to renamings of apply).
 
;;;must precede def of metacircular apply
(define apply-in-underlying-scheme apply)
 
 
 
(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        ; =====================================================
        ; HERE IS 'let' 
        ((let? exp) (eval (let->combination exp) env))
        ; HERE IS 'let*'
        ((let*? exp) (eval (let*->nested-lets exp) env))
        (else
         (error "Unknown expression type -- EVAL" exp))))
 
(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type -- APPLY" procedure))))
 
 
(define (list-of-values exps env)
  (if (no-operands? exps)
      '()
      (cons (eval (first-operand exps) env)
            (list-of-values (rest-operands exps) env))))
 
(define (eval-if exp env)
  (if (true? (eval (if-predicate exp) env))
      (eval (if-consequent exp) env)
      (eval (if-alternative exp) env)))
 
(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))
 
(define (eval-assignment exp env)
  (set-variable-value! (assignment-variable exp)
                       (eval (assignment-value exp) env)
                       env)
  'ok)
 
(define (eval-definition exp env)
  (define-variable! (definition-variable exp)
                    (eval (definition-value exp) env)
                    env)
  'ok)
 
 
 
(define (self-evaluating? exp)
  (cond ((number? exp) true)
        ((string? exp) true)
        (else false)))
 
(define (quoted? exp)
  (tagged-list? exp 'quote))
 
(define (text-of-quotation exp) (cadr exp))
 
(define (tagged-list? exp tag)
  (if (pair? exp)
      (eq? (car exp) tag)
      false))
 
(define (variable? exp) (symbol? exp))
 
(define (assignment? exp)
  (tagged-list? exp 'set!))
 
(define (assignment-variable exp) (cadr exp))
 
(define (assignment-value exp) (caddr exp))
 
 
(define (definition? exp)
  (tagged-list? exp 'define))
 
(define (definition-variable exp)
  (if (symbol? (cadr exp))
      (cadr exp)
      (caadr exp)))
 
(define (definition-value exp)
  (if (symbol? (cadr exp))
      (caddr exp)
      (make-lambda (cdadr exp)
                   (cddr exp))))
 
(define (lambda? exp) (tagged-list? exp 'lambda))
 
(define (lambda-parameters exp) (cadr exp))
(define (lambda-body exp) (cddr exp))
 
(define (make-lambda parameters body)
  (cons 'lambda (cons parameters body)))
 
 
(define (if? exp) (tagged-list? exp 'if))
 
(define (if-predicate exp) (cadr exp))
 
(define (if-consequent exp) (caddr exp))
 
(define (if-alternative exp)
  (if (not (null? (cdddr exp)))
      (cadddr exp)
      'false))
 
(define (make-if predicate consequent alternative)
  (list 'if predicate consequent alternative))
 
 
(define (begin? exp) (tagged-list? exp 'begin))
 
(define (begin-actions exp) (cdr exp))
 
(define (last-exp? seq) (null? (cdr seq)))
(define (first-exp seq) (car seq))
(define (rest-exps seq) (cdr seq))
 
(define (sequence->exp seq)
  (cond ((null? seq) seq)
        ((last-exp? seq) (first-exp seq))
        (else (make-begin seq))))
 
(define (make-begin seq) (cons 'begin seq))
 
 
(define (application? exp) (pair? exp))
(define (operator exp) (car exp))
(define (operands exp) (cdr exp))
 
(define (no-operands? ops) (null? ops))
(define (first-operand ops) (car ops))
(define (rest-operands ops) (cdr ops))
 
 
(define (cond? exp) (tagged-list? exp 'cond))
 
(define (cond-clauses exp) (cdr exp))
 
(define (cond-else-clause? clause)
  (eq? (cond-predicate clause) 'else))
 
(define (cond-predicate clause) (car clause))
 
(define (cond-actions clause) (cdr clause))
 
(define (cond->if exp)
  (expand-clauses (cond-clauses exp)))
 
(define (expand-clauses clauses)
  (if (null? clauses)
      'false                          ; no else clause
      (let ((first (car clauses))
            (rest (cdr clauses)))
        (if (cond-else-clause? first)
            (if (null? rest)
                (sequence->exp (cond-actions first))
                (error "ELSE clause isn't last -- COND->IF"
                       clauses))
            (make-if (cond-predicate first)
                     (sequence->exp (cond-actions first))
                     (expand-clauses rest))))))
 
 
 
(define (true? x)
  (not (eq? x false)))
 
(define (false? x)
  (eq? x false))
 
 
(define (make-procedure parameters body env)
  (list 'procedure parameters body env))
 
(define (compound-procedure? p)
  (tagged-list? p 'procedure))
 
 
(define (procedure-parameters p) (cadr p))
(define (procedure-body p) (caddr p))
(define (procedure-environment p) (cadddr p))
 
 
(define (enclosing-environment env) (cdr env))
 
(define (first-frame env) (car env))
 
(define the-empty-environment '())
 
(define (make-frame variables values)
  (cons variables values))
 
(define (frame-variables frame) (car frame))
(define (frame-values frame) (cdr frame))
 
(define (add-binding-to-frame! var val frame)
  (set-car! frame (cons var (car frame)))
  (set-cdr! frame (cons val (cdr frame))))
 
(define (extend-environment vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (make-frame vars vals) base-env)
      (if (< (length vars) (length vals))
          (error "Too many arguments supplied" vars vals)
          (error "Too few arguments supplied" vars vals))))
 
(define (lookup-variable-value var env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (car vals))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))
 
(define (set-variable-value! var val env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable -- SET!" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))
 
(define (define-variable! var val env)
  (let ((frame (first-frame env)))
    (define (scan vars vals)
      (cond ((null? vars)
             (add-binding-to-frame! var val frame))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) (cdr vals)))))
    (scan (frame-variables frame)
          (frame-values frame))))
 
 
 
(define (setup-environment)
  (let ((initial-env
         (extend-environment (primitive-procedure-names)
                             (primitive-procedure-objects)
                             the-empty-environment)))
    (define-variable! 'true true initial-env)
    (define-variable! 'false false initial-env)
    initial-env))
 
;[do later] (define the-global-environment (setup-environment))
 
(define (primitive-procedure? proc)
  (tagged-list? proc 'primitive))
 
(define (primitive-implementation proc) (cadr proc))
 
(define primitive-procedures
  (list (list 'car car)
        (list 'cdr cdr)
        (list 'cons cons)
        (list 'null? null?)
;;      more primitives
        ))
 
(define (primitive-procedure-names)
  (map car
       primitive-procedures))
 
(define (primitive-procedure-objects)
  (map (lambda (proc) (list 'primitive (cadr proc)))
       primitive-procedures))
 
;[moved to start of file] (define apply-in-underlying-scheme apply)
 
(define (apply-primitive-procedure proc args)
  (apply-in-underlying-scheme
   (primitive-implementation proc) args))
 
 
 
(define input-prompt ";;; M-Eval input:")
(define output-prompt ";;; M-Eval value:")
 
(define (driver-loop)
  (prompt-for-input input-prompt)
  (let ((input (read)))
    (let ((output (eval input the-global-environment)))
      (announce-output output-prompt)
      (user-print output)))
  (driver-loop))
 
(define (prompt-for-input string)
  (newline) (newline) (display string) (newline))
 
(define (announce-output string)
  (newline) (display string) (newline))
 
(define (user-print object)
  (if (compound-procedure? object)
      (display (list 'compound-procedure
                     (procedure-parameters object)
                     (procedure-body object)
                     '<procedure-env>))
      (display object)))
 
;;;Following are commented out so as not to be evaluated when
;;; the file is loaded.
;;(define the-global-environment (setup-environment))
;;(driver-loop)
 
'METACIRCULAR-EVALUATOR-LOADED
 
; =========================================================================================
; =========================================================================================
; Question 3 Part 1: LET
; LET is equivalent to lambda
(define (let? exp) (tagged-list? exp 'let))
(define (let-assignment exp) (cadr exp))
(define (let-body exp) (cddr exp))
(define (let-exp assignment)
  (if (null? assignment)
      '()
      (cons (cadr (car assignment))
            (let-exp (cdr assignment)))))
(define (let-var assignment)
  (if (null? assignment)
      '()
      (cons (car (car assignment))
            (let-var (cdr assignment)))))
 
(define (let->combination exp)
  (transform-let (let-assignment exp) (let-body exp)))
(define (transform-let assignment body)
  (cons (make-lambda (let-var assignment) body)
        (let-exp assignment)))
 
; =========================================================================================
; Question 3 Part 1: LET*
; LET* is equivalent to nested LETs
(define (let*? exp) (tagged-list? exp 'let*))
(define (let*-assignment exp) (cadr exp))
(define (let*-body exp) (cddr exp))
 
(define (let*->nested-lets exp)
  (transform-let* (let*-assignment exp) (let*-body exp)))
(define (transform-let* assignment body)
  (if (null? (cdr assignment))
      (cons 'let (cons assignment body))
      (list 'let (list (car assignment))
            (transform-let* (cdr assignment) body))))