PasteRack.org
Paste # 70777
2025-10-25 21:14:27

Fork as a new paste.

Paste viewed 349 times.


Embed:

  1. #lang racket
  2.  
  3. (provide hours
  4.          gate1
  5.          sel-ckt
  6.          eq1-ckt
  7.          eq2-ckt
  8.          latch-ckt
  9.          eq1-config1x
  10.          eq1-config2x
  11.          sel-config1x
  12.          sel-config2x
  13.          latch-config1x
  14.          latch-config2x
  15.          clock-ckt
  16.          seq-or-ckt
  17.          one-one-ckt
  18.  
  19.  
  20.          gate gate? gate-type gate-inputs gate-output
  21.          ckt ckt? ckt-inputs ckt-outputs ckt-gates
  22.          good-gate? good-circuit?
  23.          all-wires find-gate
  24.          ha-ckt fa-ckt
  25.          ;;  entry entry? entry-key entry-value
  26.          next-value
  27.          next-config
  28.          stable? all-stable-configs output-values init-config
  29.          simulate
  30.          final-config
  31.          add-ckt
  32.          dff-ckt
  33.          timing-ckt
  34.          )
  35.  
  36. (require racket/trace)
  37.  
  38. ; Please do not edit lines above this one
  39.  
  40. ;**********************************************************
  41. ; CS 201b HW #5, due 11:59 pm Wednesday, October 30th.
  42. ; using gradescope.
  43. ;**********************************************************
  44. ; Name: Abril Linares Mendoza
  45. ; Email address: abril.linaresmendoza@yale.edu
  46. ;**********************************************************
  47.  
  48. ; Computer science topics: gates and circuits
  49.  
  50. ; Unless the problem specifies otherwise:
  51. ; * You may solve the problem using any method
  52. ; and any Racket constructs, except mutators (set! and its relatives.)
  53. ; EXCEPT you may use hash mutators, e.g., hash-set!
  54. ; * You may write auxiliary procedure(s) in addition to
  55. ; the one(s) specified in the problem.  Please include
  56. ; a comment for each one explaining its input and results.
  57.  
  58. ;**********************************************************
  59. ; ** problem 0 ** (1 point)
  60. ; Modify the following definition to reflect the number of
  61. ; hours you spent on this assignment.
  62.  
  63. (define hours 6)
  64.  
  65. ;**********************************************************
  66.  
  67. ; Wires and gates.
  68.  
  69. ; A wire is identified by a Racket symbol, for example 'x, 'y0, or 'next.
  70. ; Strings (eg, "x" or "next") are not permitted wire names.
  71.  
  72. ; A gate is a struct with three fields:
  73. ; 1) a symbol indicating the type of gate, one of:
  74. ;       'not, 'and, 'or, 'xor, 'nand, 'nor
  75. ; 2) a list of the wire identifiers of the inputs
  76. ; 3) the output wire identifier
  77.  
  78. (struct gate (type inputs output) #:transparent)
  79.  
  80. ; Examples of gates:
  81.  
  82. (define gate1 (gate 'and '(x y) 'z))
  83. (define gate2 (gate 'or '(x v) 'v))
  84. (define gate3 (gate 'not '(s) 't))
  85. (define gate4 (gate 'nand '(x x) 'z))
  86.  
  87. ;**********************************************************
  88.  
  89. ; Circuits.
  90.  
  91. ; A circuit is a struct with three fields
  92. ; (1) a list of input wire identifiers
  93. ; (2) a list of output wire identifiers
  94. ; (3) a list of gates
  95.  
  96. (struct ckt (inputs outputs gates) #:transparent)
  97.  
  98. ;**********************************************************
  99. ; Examples of circuits
  100.  
  101. ; Here is a circuit to compare the values of its two inputs
  102. ; and output 1 if they are equal, 0 if they are unequal.
  103. ; This computes one-bit compare for equality, and implements
  104. ; the sum-of-products representation.  This is a combinational
  105. ; circuit (no cycle of wires and gates.)
  106.  
  107. (define eq1-ckt
  108.   (ckt
  109.    '(x y)
  110.    '(z)
  111.    (list
  112.     (gate 'not '(x) 'cx)
  113.     (gate 'not '(y) 'cy)
  114.     (gate 'and '(x y) 't1)
  115.     (gate 'and '(cx cy) 't2)
  116.     (gate 'or '(t1 t2) 'z))))
  117.  
  118. ; This is interpreted as follows:
  119. ; the inputs of the circuit are the wires x and y,
  120. ; the outputs of the circuit consist of just the wire z,
  121. ; there are five gates specified as follows:
  122. ; wire cx is the output of a NOT gate with input x,
  123. ; wire cy is the output of a NOT gate with input y,
  124. ; wire t1 is the output of an AND gate with inputs x and y,
  125. ; wire t2 is the output of an AND gate with inputs cx and cy,
  126. ; wire z is the output of an OR gate with inputs t1 and t2.
  127.  
  128. ; Here is another implementation of comparing two bits for equality.
  129. ; This uses the implementation as the NOT of (x XOR y).
  130. ; This is also a combinational circuit.
  131. ; The inputs and output of this circuit are named as in eq1-ckt.
  132.  
  133. (define eq2-ckt
  134.   (ckt
  135.    '(x y)
  136.    '(z)
  137.    (list
  138.     (gate 'xor '(x y) 'w)
  139.     (gate 'not '(w) 'z))))
  140.  
  141. ; Here is a two-bit selector whose Boolean expressions are as follows.
  142.  
  143. ; z_1 = x_1 * s' + y_1 * s
  144. ; z_0 = x_0 * s' + y_0 * s
  145.  
  146. ; For this circuit, z_1 and z_0 are
  147. ; equal to x_1 and x_0 if s = 0, and
  148. ; z_1 and z_0 are equal to y_1 and y_0
  149. ; if s = 1.
  150.  
  151. ; This is also a combinational circuit.
  152.  
  153. (define sel-ckt
  154.   (ckt
  155.    '(x1 x0 y1 y0 s)
  156.    '(z1 z0)
  157.    (list
  158.     (gate 'not '(s) 'sc)
  159.     (gate 'and '(x1 sc) 'u1)
  160.     (gate 'and '(y1 s) 'v1)
  161.     (gate 'or '(u1 v1) 'z1)
  162.     (gate 'and '(x0 sc) 'u0)
  163.     (gate 'and '(y0 s) 'v0)
  164.     (gate 'or '(u0 v0) 'z0))))
  165.  
  166. ; This is a NAND latch, used to store one bit.
  167. ; It is a sequential (not combinational) circuit,
  168. ; because it has a loop from a wire to itself through
  169. ; other wires and gates.
  170.  
  171. (define latch-ckt
  172.   (ckt
  173.    '(x y)
  174.    '(q u)
  175.    (list
  176.     (gate 'nand '(x u) 'q)
  177.     (gate 'nand '(y q) 'u))))
  178.  
  179. ; The following is also a sequential circuit, with
  180. ; an OR gate one of whose inputs is its output.
  181. ; (The "Garden of Eden" circuit.)
  182.  
  183. (define seq-or-ckt
  184.   (ckt
  185.    '(x)
  186.    '(z)
  187.    (list
  188.     (gate 'or '(x z) 'z))))
  189.  
  190. ; The next is also a sequential circuit.
  191. ; It could serve as a clock.
  192. ; Note that this circuit has *no* inputs, but
  193. ; does have an output.
  194.  
  195. (define clock-ckt
  196.   (ckt
  197.    '()
  198.    '(z)
  199.    (list
  200.     (gate 'not '(z) 'z))))
  201.  
  202. ;**********************************************************
  203. ; ** problem 1 ** (9 points)
  204. ; Write two procedures:
  205.  
  206. ; (good-gate? value)
  207. ; (good-circuit? value)
  208.  
  209. ; (good-gate? value) takes an arbitrary value
  210. ; and returns #t if it is a well-formed gate,
  211. ; and #f otherwise.
  212. ; To be a well-formed gate, the value must be
  213. ; a gate struct whose three fields satisfy
  214. ; (1) the type field is one of the gate symbols:
  215. ;     'not, 'and, 'or, 'xor, 'nand, 'nor,
  216. ; (2) the inputs field is a list of wire identifiers
  217. ; (3) the output field is a single wire identifier
  218.  
  219. ; In addition, the number of inputs should be correct for each gate type.
  220. ; A gate of type 'not has 1 input, while
  221. ; gates of types 'and, 'or, 'xor, 'nand, 'nor have 2 inputs.
  222.  
  223. ; (good-circuit? value) takes an arbitrary value and
  224. ; returns #t if value is a well-formed circuit,
  225. ; and returns #f otherwise.
  226.  
  227. ; To be a well-formed circuit, it must be a ckt struct
  228. ; and its inputs field must be a list of wires,
  229. ; its outputs field must be a list of wires, and
  230. ; its gates field must be a list of gates that
  231. ; are well-formed according to the good-gate? procedure.
  232.  
  233. ; In addition, the circuit must satisfy the conditions:
  234. ; (1) no input of the circuit is the output of a gate,
  235. ; (2) every input of a gate is either
  236. ; an input of the circuit or the output of a gate,
  237. ; (3) no wire is the output of two or more gates,
  238. ; (4) every output of the circuit is either an input
  239. ; of the circuit or the output of a gate.
  240.  
  241. ; Examples
  242. ; (good-gate? gate1) => #t
  243. ; (.. and similarly for gate2, gate3, gate4)
  244. ; (good-gate? (gate 'not 'x 'y)) => #f
  245. ; (good-gate? (gate 'nor '("x" "y") "z")) => #f
  246. ; (good-gate? (gate 'and '(1 2) 3)) => #f
  247. ; (good-gate? (gate 'equal '(x y) 'z)) => #f
  248. ; (good-gate? (gate 'or '(w x y) 'z)) => #f
  249.  
  250. ; (good-circuit? sel-ckt) => #t
  251. ; (.. and similarly for eq1-ckt, eq2-ckt, latch-ckt, seq-or-ckt, clock-ckt)
  252. ; (good-circuit? 'hi) => #f
  253. ; (good-circuit? (ckt '() '() '())) => #t
  254. ; (good-circuit? (ckt '(x y) '(z) (list (gate 'and '(x y) 'x) (gate 'or '(x y) 'z)))) => #f
  255. ; (good-circuit? (ckt '(x y) '(z) (list (gate 'nor '(x y) 'z) (gate 'nand '(x y) 'z)))) => #f
  256. ; (good-circuit? (ckt '(x y) '(u z) (list (gate 'or '(x y) 'z)))) => #f
  257. ;**********************************************************
  258.  
  259. (define (good-gate? value)
  260.   (if (gate? value)
  261.       (if (symbol? (gate-output value))
  262.           (if (cond
  263.                 [(equal? (gate-type value) 'not) #t]
  264.                 [(equal? (gate-type value) 'and) #t]
  265.                 [(equal? (gate-type value) 'or) #t]
  266.                 [(equal? (gate-type value) 'xor) #t]
  267.                 [(equal? (gate-type value) 'nand) #t]
  268.                 [(equal? (gate-type value) 'nor) #t]
  269.                 [else #f])
  270.               (if (list? (gate-inputs value))
  271.                   (if (and (equal? (gate-type value) 'not) (= (length (gate-inputs value)) 1)) (symbol? (car (gate-inputs value)))
  272.                       (if (and (= (length (gate-inputs value)) 2) (and (symbol? (car (gate-inputs value))) (symbol? (second (gate-inputs value))))) #t #f)) #f) #f) #f) #f)
  273.   )
  274.  
  275. (define (good-circuit? value)
  276.   (and
  277.     (ckt? value) ;is it a circuit struct
  278.  
  279.     (all-symbols? (ckt-inputs value)) ;are all the inputs symbols
  280.     (all-symbols? (ckt-outputs value)) ;same with ouputs
  281.  
  282.     (all-good-gates? (ckt-gates value)) ;are all gates good gates
  283.  
  284.     (not (input-is-output? (ckt-inputs value) (ckt-gates value))) ;input wire is not = to output gate
  285.  
  286.     (check-gate-inputs (ckt-inputs value) (ckt-gates value) value) ;gate input is a circuit input or gate output
  287.  
  288.     (unique-outputs? value) ;no wire is output of more than one gate
  289.  
  290.     (valid-output? (ckt-outputs value) (ckt-inputs value) (ckt-gates value) value) ;every circuit ouput is circuit input or gate ouput
  291.     )
  292.   )
  293.  
  294. (define (all-symbols? lst)
  295.   (cond
  296.     [(empty? lst) #t]
  297.     [(symbol? (car lst)) (all-symbols? (cdr lst))]
  298.     [else #f]))
  299.  
  300. (define (all-good-gates? gates)
  301.   (cond
  302.     [(empty? gates) #t]
  303.     [(good-gate? (car gates)) (all-good-gates? (cdr gates))]
  304.     [else #f]))
  305.  
  306. (define (input-is-output? inputs gates) ;check if input is output of gate
  307.   (define (is-output? wire gates)
  308.     (cond
  309.       [(empty? gates) #f]
  310.       [(equal? wire (gate-output (car gates))) #t]
  311.       [else (is-output? wire (cdr gates))]))
  312.   (cond
  313.     [(empty? inputs) #f]
  314.     [(is-output? (car inputs) gates) #t]
  315.     [else (input-is-output? (cdr inputs) gates)]))
  316.  
  317. (define (check-gate-inputs inputslst gateslst circuit)
  318.   (cond
  319.     [(> (length (ckt-gates circuit)) 1)
  320.   (cond
  321.     [(empty? gateslst) #f]
  322.     [(or (member (car (gate-inputs (car (ckt-gates circuit)))) (ckt-inputs circuit)) (member (car (gate-inputs (car (ckt-gates circuit)))) (map gate-output (ckt-gates circuit)))) #t]
  323.     [else (check-gate-inputs inputslst (cdr gateslst) circuit)]
  324.     )]
  325.     [else #t]
  326.     )
  327.   )
  328.  
  329. ;(trace check-gate-inputs)
  330.  
  331. (define (unique-outputs? circuit)
  332.   (if (< (length (remove-duplicates (map gate-output (ckt-gates circuit)))) (length (map gate-output (ckt-gates circuit)))) #f #t))
  333.  
  334. (define (valid-output? outputs inputs gates circuit)
  335.   (cond
  336.     [(> (length (ckt-gates circuit)) 1)
  337.      (cond
  338.        [(empty? outputs) #f]
  339.        [(or (member (car outputs) (ckt-inputs circuit)) (member (car outputs) (map gate-output (ckt-gates circuit)))) #t]
  340.        [else (valid-output? (cdr outputs) inputs (cdr gates) circuit)]
  341.        )]
  342.     [(= (length (ckt-gates circuit)) 0) #t]
  343.     [else (cond
  344.             [(empty? outputs) #f]
  345.             [(or (member (car outputs) (ckt-inputs circuit)) (member (car outputs) (map gate-output (ckt-gates circuit)))) #t]
  346.             [else #f]
  347.             )]
  348.     )
  349.   )
  350.  
  351. ;**********************************************************
  352. ; ** problem 2 ** (10 points)
  353. ; Write two procedures.
  354.  
  355. ; (all-wires circuit) to return the list of all the wire names that appear
  356. ;      in the circuit, as circuit inputs, circuit outputs, gate
  357. ;      inputs or gate outputs, in that order, with duplicates removed.
  358. ; (find-gate wire circuit) to return the gate in the circuit with the given
  359. ;      output wire, or #f if there is no such gate.
  360.  
  361. ; You may assume that circuit is a well-formed circuit; in particular,
  362. ; a wire is the output of *at most one* gate.
  363.  
  364. ; Examples:
  365.  
  366. ; (all-wires eq1-ckt) => '(x y z cx cy t1 t2)
  367. ; (all-wires sel-ckt) => '(x1 x0 y1 y0 s z1 z0 sc u1 v1 u0 v0)
  368. ; (find-gate 't2 eq1-ckt) => (gate 'and '(cx cy) 't2)
  369. ; (find-gate 'w eq2-ckt) => (gate 'xor '(x y) 'w)
  370. ; (find-gate 'y sel-ckt) => #f
  371. ;**********************************************************
  372.  
  373. (define (all-wires circuit)
  374.   (remove-duplicates (append (ckt-inputs circuit) (ckt-outputs circuit) (append-map gate-inputs (ckt-gates circuit)) (map gate-output (ckt-gates circuit))))
  375.   )
  376.  
  377. ;(trace all-wires)
  378.  
  379. (define (find-gate wire circuit)
  380.   (define (find-gate-helper wire gates)
  381.     (cond
  382.       [(null? gates) #f]
  383.       [(equal? wire (gate-output (car gates))) (car gates)]
  384.       [else (find-gate-helper wire (cdr gates))]))
  385.   (find-gate-helper wire (ckt-gates circuit)))
  386.  
  387.  
  388. ;**********************************************************
  389. ; ** problem 3 ** (10 points)
  390. ; Define circuits for a half-adder and a full-adder in the representation described above.
  391.  
  392. ; Your half-adder should be called ha-ckt
  393. ; and should have input wires: x and y and output wires: z and co,
  394. ; where z is the exclusive or of x and y, and co is 1 if both x and y are 1.
  395.  
  396. ; Your full-adder should be called fa-ckt
  397. ; and should have input wires: x, y, and ci and output wires: z and co,
  398. ; where the value of z is 1 if the sum of x, y, and ci is odd,
  399. ; and the value of co is 1 if and only if at least two of x, y, and ci are 1.
  400.  
  401. ; The order and names of the circuit input and output wires should be as specified above,
  402. ; but the number and names of internal wires (wires that are neither circuit inputs
  403. ; nor circuit outputs) are up to you.
  404.  
  405. ; Examples
  406. ; (good-circuit? ha-ckt) => #t
  407. ; (good-circuit? fa-ckt) => #t
  408. ; (ckt-inputs ha-ckt) => '(x y)
  409. ; (ckt-outputs ha-ckt) => '(z co)
  410. ; (ckt-inputs fa-ckt) => '(x y ci)
  411. ; (ckt-outputs fa-ckt) => '(z co)
  412.  
  413. ; (output-values ha-ckt (final-config ha-ckt (init-config ha-ckt '(1 1)))) => (0 1)
  414. ; (output-values fa-ckt (final-config fa-ckt (init-config fa-ckt '(1 1 1)))) => (1 1)
  415.  
  416. ; For the last two tests, your procedures output-values, final-config, init-config must be working.
  417. ;**********************************************************
  418.  
  419. (define ha-ckt
  420.   (ckt '(x y) '(z co)
  421.        (list
  422.         (gate 'xor '(x y) 'z)
  423.         (gate 'and '(x y) 'co)
  424.         )
  425.        )
  426.   )
  427. ;   "ha-ckt is not defined yet")
  428.  
  429. (define fa-ckt
  430.   (ckt '(x y ci) '(z co)
  431.        (list
  432.         (gate 'xor '(x y) 'a) ;sum of x and y
  433.         (gate 'and '(x y) 'b) ;carry of x and y
  434.  
  435.         (gate 'xor '(a b) 'd) ;final sum
  436.         (gate 'and '(a b) 'e)
  437.  
  438.         (gate 'or '(e b) 'co) ;carry out
  439.  
  440.         )))
  441. ;   "fa-ckt is not defined yet")
  442.  
  443. ;**********************************************************
  444.  
  445. ; A configuration of a circuit is a hash table giving a value (0 or 1)
  446. ; for each wire in the circuit. A table is a list of key-value pairs,
  447. ; such that the key is the symbol for the wire and the value is either
  448. ; 0 or 1.
  449.  
  450.  
  451. ; Examples
  452.  
  453. ; Two configurations of the wires of the eq1-ckt Note that the order
  454. ; of wires in the configuration is that returned by (all-wires
  455. ; eq1-ckt).
  456.  
  457. (define eq1-config1x
  458.   (make-hash '((x . 0) (y . 1) (z  . 0) (cx  . 0)
  459.                (cy  . 0) (t1  . 0) (t2  . 0))))
  460.  
  461. (define eq1-config2x
  462.   (make-hash '((x . 0) (y . 0) (z  . 0) (cx  . 1)
  463.                (cy  . 1) (t1  . 0) (t2  . 0))))
  464.  
  465. ; Two configurations of the wires of the sel-ckt
  466.  
  467. (define sel-config1x
  468.   (make-hash '((x1 . 0) (x0 . 1) (y1 . 1) (y0 . 0) (s . 1)
  469.         (z1 . 0) (z0 . 0) (sc . 0) (u1 . 0) (v1 . 0)
  470.         (u0 . 0) (v0 . 0))))
  471.  
  472. (define sel-config2x
  473.   (make-hash '((x1 . 1) (x0 . 1) (y1 . 0) (y0 . 0) (s . 0)
  474.         (z1 . 0) (z0 . 0) (sc . 1) (u1 . 0) (v1 . 0)
  475.         (u0 . 0) (v0 . 0))))
  476.  
  477.  
  478. ; Two configurations of the wires of the latch-ckt
  479.  
  480. (define latch-config1x
  481.   (make-hash '((x . 0) (y . 0) (q . 0) (u . 0) )))
  482.  
  483. (define latch-config2x
  484.   (make-hash '((x . 0) (y . 1) (q . 1) (u . 0) )))
  485.  
  486. ;**********************************************************
  487. ; ** problem 4 ** (10 points)
  488. ; Write a procedure
  489.  
  490. ;(next-value wire circuit config)
  491.  
  492. ; that returns the value on the given wire of the given circuit,
  493. ; *after one gate delay* starting with the given configuration config
  494. ; of the circuit.
  495.  
  496. ; You may assume that
  497. ; (1) circuit is a well-formed circuit, according to the specifications in problem 1,
  498. ; (2) the given wire is one of the wires of circuit, and
  499. ; (3) the given configuration config specifies a value for every wire in the circuit.
  500.  
  501. ; If the given wire is an input wire of the circuit,
  502. ; its next value is just its value in the configuration config.
  503.  
  504. ; If the given wire is the output wire of a gate, its next value is
  505. ; obtained by finding the gate of circuit for which it is the output
  506. ; wire, looking up the values of the input wires of the gate in the
  507. ; configuration config, and applying the appropriate function of the
  508. ; gate to the input values.
  509.  
  510. ; Note that this doesn't compute the *eventual* value (if any) of the wire,
  511. ; just the *next* value of the wire, after one gate delay.
  512.  
  513. ; You may want to write an auxiliary procedure to look up the value of a wire in a configuration.
  514.  
  515. ; Examples
  516.  ;(next-value 'cx eq1-ckt eq1-config1x) => 1
  517. ; (next-value 't2 eq1-ckt eq1-config1x) => 0
  518. ; (next-value 'z eq1-ckt eq1-config2x) => 0
  519. ; (next-value 'x0 sel-ckt sel-config1x) => 1
  520. ; (next-value 'v1 sel-ckt sel-config1x) => 1
  521. ; (next-value 'v0 sel-ckt sel-config2x) => 0
  522. ;**********************************************************
  523.  
  524. (define (next-value wire circuit config)
  525.   (cond
  526.     [(member wire (ckt-inputs circuit)) (wirevalue config wire)] ;wire is input
  527.  
  528.     [else
  529.      (let* [(gate (find-gate wire circuit))
  530.             (inputs (map (lambda (input-wire) (wirevalue config input-wire))
  531.                          (gate-inputs gate)))]
  532.        (gatelogic (gate-type gate) inputs))
  533.      ]
  534.     )
  535.   )
  536.  
  537. (define (gatelogic type inputs)
  538.   (case type
  539.     [(not) (if (= (first inputs) 0) 1 0)]
  540.     [(and) (if (and (= (first inputs) 1) (= (second inputs) 1)) 1 0)]
  541.     [(or) (if (or (= (first inputs) 1) (= (second inputs) 1)) 1 0)]
  542.     [(xor) (if (not (= (first inputs) (second inputs))) 1 0)]
  543.     [(nand) (if (and (= (first inputs) 1) (= (second inputs) 1)) 0 1)]
  544.     [(nor) (if (or (= (first inputs) 1) (= (second inputs) 1)) 0 1)]
  545.     [else #f]
  546.     )
  547.   )
  548.  
  549. (define (wirevalue config wire) (hash-ref config wire)) ;find the value in the table
  550.  
  551. ;**********************************************************
  552. ; ** problem 5 ** (10 points)
  553. ; Write a procedure
  554.  
  555. ; (next-config circuit config)
  556.  
  557. ; that takes a circuit and a current configuration config and returns
  558. ; the "next" configuration of the circuit, after *one gate delay* has
  559. ; elapsed.
  560.  
  561. ; In the "next" configuration of the circuit the value of each wire is
  562. ; the result of applying the next-value procedure to the wire, circuit
  563. ; and the configuration config. Note that only the values of wires in
  564. ; config are used for inputs, not the new values.
  565.  
  566. ; Thus, values on the input wires do not change, and each wire that is
  567. ; the output of a gate has the value determined by its gate function
  568. ; applied the values of its input wires in the configuration config.
  569.  
  570. ; This is a rather simplified model of the time-varying behavior of
  571. ; wires and gates.
  572.  
  573. ; Examples
  574. ;> (next-config eq1-ckt eq1-config1x)
  575. ; '#hash((cx . 1) (cy . 0) (t1 . 0) (t2 . 0) (x . 0) (y . 1) (z . 0))
  576.  
  577. ;> (next-config eq1-ckt eq1-config2x)
  578. ; '#hash((cx . 1) (cy . 1) (t1 . 0) (t2 . 1) (x . 0) (y . 0) (z . 0))
  579.  
  580. ;> (next-config sel-ckt sel-config1x)
  581. ; '#hash((s . 1) (sc . 0) (u0 . 0) (u1 . 0) (v0 . 0) (v1 . 1)
  582. ;        (x0 . 1) (x1 . 0) (y0 . 0) (y1 . 1) (z0 . 0) (z1 . 0))
  583.  
  584. ;> (next-config sel-ckt (next-config sel-ckt sel-config1x))
  585. ; '#hash((s . 1) (sc . 0) (u0 . 0) (u1 . 0)  (v0 . 0) (v1 . 1)
  586. ;        (x0 . 1) (x1 . 0) (y0 . 0) (y1 . 1) (z0 . 0) (z1 . 1))
  587.  
  588. ;> (next-config latch-ckt latch-config1x)
  589. ; '#hash((q . 1) (u . 1) (x . 0) (y . 0))
  590.  
  591. ;> (next-config latch-ckt latch-config2x)
  592. ; '#hash((q . 1) (u . 0) (x . 0) (y . 1))
  593.  
  594. ;**********************************************************
  595.  
  596. (define (next-config circuit config)
  597.     (make-hash (map (lambda (a) (cons a (next-value a circuit config))) (all-wires circuit)))
  598.   )
  599.  
  600. ;create empty hash
  601. ; use let to create a result variable which is an empty hash
  602. ; then go through all the keys in the config and for each of the keys create a new hash table
  603. ; that will look up those keys using next value and return the corresponding next value
  604. ;map lambda hashkey
  605.  
  606. ;next config will use hash keys to pull in all the keys from config
  607. ; and from those it will create a new config with the next values
  608.  
  609. ;**********************************************************
  610. ; ** problem 6 ** (10 points)
  611. ; Write four procedures
  612.  
  613. ; (stable? circuit config)
  614. ; (all-stable-configs circuit)
  615. ; (output-values circuit config)
  616. ; (init-config circuit input-values)
  617.  
  618. ; (stable? circuit config)
  619. ; returns #t if the next configuration of the circuit after the
  620. ; configuration config is the same as config, ie, this configuration
  621. ; is stable for the circuit.
  622.  
  623. ; (all-stable-configs circuit)
  624. ; returns a list of all the stable configurations of the circuit. The
  625. ; wires in the configurations should be listed in the same order as
  626. ; (all-wires circuit), and the values in the configurations list
  627. ; should be in increasing order, considered as binary numbers.
  628.  
  629. ; (output-values circuit config)
  630. ; returns a list giving the Boolean values of each of the output wires
  631. ; of the circuit in the configuration config. The order is the same
  632. ; as the list of output wires of the circuit.
  633.  
  634. ; (init-config circuit input-values)
  635. ; takes a circuit and a list input-values of Boolean values which has
  636. ; the same length as the number of inputs of the circuit and returns a
  637. ; configuration in which the circuit input wires have the values
  638. ; specified (in order) by the list inputs, and all other wires have
  639. ; the value 0.
  640.  
  641. ; Examples
  642.  
  643. ; (stable? eq1-ckt (make-hash '((x . 0) (y . 0) (z . 1) (cx . 1)
  644. ;    (cy . 1) (t1 . 0) (t2 . 1)))) => #t
  645.  
  646. ; (stable? eq1-ckt (make-hash '((x . 0) (y . 0) (z . 0)
  647. ;    (cx . 1) (cy . 0) (t1 . 1) (t2 . 0)))) => #f
  648.  
  649. ;> (all-stable-configs eq2-ckt)
  650. ;'(#hash((w . 0) (x . 0) (y . 0) (z . 1))
  651. ;  #hash((w . 1) (x . 0) (y . 1) (z . 0))
  652. ;  #hash((w . 1) (x . 1) (y . 0) (z . 0))
  653. ;  #hash((w . 0) (x . 1) (y . 1) (z . 1)))
  654.  
  655. ;> (all-stable-configs seq-or-ckt)
  656. ; '(#hash((x . 0) (z . 0)) #hash((x . 0) (z . 1)) #hash((x . 1) (z . 1)))
  657.  
  658. ; (output-values eq1-ckt eq1-config2x) => '(0)
  659. ; (output-values latch-ckt latch-config2x) => '(1 0)
  660.  
  661. ; (init-config eq1-ckt '(1 0)) =>
  662. ; '#hash((cx . 0) (cy . 0) (t1 . 0) (t2 . 0) (x . 1) (y . 0) (z . 0))
  663.  
  664. ; (init-config clock-ckt '()) => '#hash((z . 0))
  665.  
  666. ;**********************************************************
  667.  
  668. (define (stable? circuit config)
  669.    (cond
  670.      [(equal? (next-config circuit config) config) #t]
  671.      [else #f]
  672.      )
  673.   )
  674.  
  675. (define (all-stable-configs circuit)
  676.   (define (good-stable configs)
  677.     (cond
  678.       [(empty? configs) '()]
  679.       [(stable? circuit (car configs)) (cons (car configs) (good-stable (cdr configs)))]
  680.       [else (good-stable (cdr configs))]
  681.       )
  682.     )
  683.   (good-stable (all-configs circuit))
  684.   )
  685.  
  686. (define (all-configs circuit)
  687.   (map (lambda (bin) (make-hash (map (lambda (w b) (cons w b)) (all-wires circuit) bin))) (all-combs (length (all-wires circuit))))
  688.   )
  689.  
  690. (define (all-combs n) ;n would be (length (all-wires circuit))
  691.   (cond
  692.     [(= n 0) '(())]
  693.     [else
  694.      (let* [(copy (all-combs (- n 1)))]
  695.        (append
  696.         (map (lambda (sublist) (cons 0 sublist)) copy)
  697.         (map (lambda (sublist) (cons 1 sublist)) copy)
  698.         )
  699.        )
  700.      ]
  701.     )
  702.   )
  703.  
  704. ;; Hint: you may want to define all-configs, which generates all
  705. ;; configurations for a given number of wires.  Much like your old
  706. ;; friend power-set.
  707.  
  708. (define (output-values circuit config)
  709.   (define (all-outputs outs)
  710.     (cond
  711.       [(empty? outs) '()]
  712.       [(hash-ref config (car outs)) (cons (hash-ref config (car outs)) (all-outputs (cdr outs)))]
  713.       [else (all-outputs (cdr outs))]
  714.       )
  715.     )
  716.   (all-outputs (ckt-outputs circuit))
  717.   )
  718.  
  719. (define (init-config circuit input-values)
  720.   (make-hash (init-config-aux circuit input-values (all-wires circuit)))
  721.   )
  722.  
  723. (define (init-config-aux circuit input-values wires)
  724.   (cond
  725.     [(empty? wires) '()]
  726.     [(member (car wires) (ckt-inputs circuit)) (cons
  727.                                                 (cons (car wires) (car input-values))
  728.                                                 (init-config-aux circuit (cdr input-values) (cdr wires)))]
  729.     [else (cons (cons (car wires) 0) (init-config-aux circuit input-values (cdr wires)))]
  730.     )
  731.   )
  732.  
  733. ;(make-hash (map (lambda (a) (cons a ((if (member a (ckt-inputs circuit)) (car input-values) 0)))) (all-wires circuit)))
  734.  
  735. ; *********************************************************
  736. ; ** problem 7 ** (10 points)
  737. ; Write a procedure
  738.  
  739. ; (simulate circuit config n)
  740.  
  741. ; which simulates the given circuit from the given configuration by
  742. ; repeatedly calling next-config until either the configuration
  743. ; reached is stable, or next-config has been called n times, whichever
  744. ; occurs first.
  745.  
  746. ; Examples
  747. ;> (simulate clock-ckt (make-hash '((z . 0))) 4)
  748. ; '(#hash((z . 0)) #hash((z . 1)) #hash((z . 0)) #hash((z . 1)) #hash((z . 0)))
  749.  
  750. ;> (simulate eq1-ckt eq1-config1x 5) =>
  751. ; '(#hash((cx . 0) (cy . 0) (t1 . 0) (t2 . 0) (x . 0) (y . 1) (z . 0))
  752. ;   #hash((cx . 1) (cy . 0) (t1 . 0) (t2 . 0) (x . 0) (y . 1) (z . 0)))
  753.  
  754. ;> (simulate sel-ckt sel-config1x 5) =>
  755. ;'(#hash((s . 1) (sc . 0) (u0 . 0) (u1 . 0) (v0 . 0) (v1 . 0)
  756. ;    (x0 . 1)  (x1 . 0) (y0 . 0) (y1 . 1) (z0 . 0) (z1 . 0))
  757. ;  #hash((s . 1) (sc . 0) (u0 . 0) (u1 . 0) (v0 . 0) (v1 . 1)
  758. ;    (x0 . 1) (x1 . 0) (y0 . 0) (y1 . 1) (z0 . 0) (z1 . 0))
  759. ;  #hash((s . 1) (sc . 0) (u0 . 0) (u1 . 0) (v0 . 0) (v1 . 1)
  760. ;    (x0 . 1) (x1 . 0) (y0 . 0) (y1 . 1) (z0 . 0) (z1 . 1)))
  761.  
  762. ;> (simulate latch-ckt latch-config2x 3) =>
  763. ; '(#hash((q . 1) (u . 0) (x . 0) (y . 1)))
  764.  
  765. ;> (simulate eq2-ckt (init-config eq2-ckt '(0 1)) 5) =>
  766. ;'(#hash((w . 0) (x . 0) (y . 1) (z . 0))
  767. ;  #hash((w . 1) (x . 0) (y . 1) (z . 1))
  768. ;  #hash((w . 1) (x . 0) (y . 1) (z . 0)))
  769.  
  770. ;**********************************************************
  771.  
  772. (define (simulate circuit config n)
  773.   (define (simulate-helper current-config steps)
  774.     (let* [(next (next-config circuit current-config))]
  775.       (cond
  776.         [(or (stable? circuit current-config) (= steps 0)) (list current-config)]
  777.         [else (cons current-config (simulate-helper next (- steps 1)))]
  778.         )
  779.       )
  780.     )
  781.   (simulate-helper config n)
  782.   )
  783.  
  784. ;equal? current-config next, this used to be in the first of the or
  785.  
  786. ;**********************************************************
  787. ; ** problem 8 ** (10 points)
  788. ; Write a procedure
  789.  
  790. ; (final-config circuit config)
  791.  
  792. ; that takes a circuit and a configuration config for the circuit. If
  793. ; the circuit would eventually reach a stable configuration from
  794. ; config, then (final-config circuit config) returns the stable
  795. ; configuration of the circuit that would be reached.
  796.  
  797. ; Otherwise, (final-config circuit config) returns the symbol 'none.
  798.  
  799. ; Examples
  800.  
  801. ; (final-config clock-ckt (make-hash '((z . 0)))) => 'none
  802.  
  803. ; (final-config eq1-ckt
  804. ;       (make-hash '((x . 1) (y . 1) (z . 0) (cx . 0)
  805. ;    (cy . 0) (t1 . 0) (t2 . 0)))) =>
  806. ; (make-hash '((x . 1) (y . 1) (z . 1) (cx . 0)
  807. ;          (cy . 0) (t1 . 1) (t2 . 0))))
  808.  
  809. ; (final-config sel-ckt
  810. ;       (make-hash '((x1 . 0) (x0 . 0) (y1 . 1) (y0 . 0)
  811. ;    (s . 0) (z1 . 1) (z0 . 1) (sc . 0)
  812. ;    (u1 . 1) (v1 . 1) (u0 . 0) (v0 . 1)))) =>
  813. ;(make-hash '((x1 . 0) (x0 . 0) (y1 . 1) (y0 . 0)
  814. ;      (s . 0) (z1 . 0) (z0 . 0) (sc . 1)
  815. ;      (u1 . 0) (v1 . 0) (u0 . 0) (v0 . 0)))
  816.  
  817. ; (final-config latch-ckt (make-hash '((x . 1) (y . 1) (q . 0) (u . 0)))) =>
  818. ;       'none
  819.  
  820. ; (final-config latch-ckt (make-hash '((x . 1) (y . 1) (q . 0) (u . 1)))) =>
  821. ; (make-hash '((x . 1) (y . 1) (q . 0) (u . 1))))
  822.  
  823.  
  824. ;**********************************************************
  825.  
  826. (define (final-config circuit config)
  827.   (define (final-aux current-config seen-configs)
  828.     (let* [(next (next-config circuit current-config))]
  829.       (cond
  830.         [(stable? circuit current-config) current-config] ;current config is stable
  831.         [(member next seen-configs) 'none] ;if config has already been outputted, then it is never going to be stable
  832.         [else (final-aux next (cons next seen-configs))] ;add the next config to the list of seen configs
  833.         )
  834.       )
  835.     )
  836.   (final-aux config '()) ;call final aux with no seen configs yet
  837.   )
  838.  
  839. ;**********************************************************
  840. ; ** problem 9 ** (10 points)
  841. ; Define a 4-bit ripple-carry adder circuit as described in lecture
  842. ; using the circuit representation developed above.
  843.  
  844. ; Please name it: add-ckt
  845.  
  846. ; Its inputs are x3, x2, x1, x0, y3, y2, y1, y0  (in order)
  847. ; Its outputs are z4, z3, z2, z1, z0 (in order)
  848. ; What it computes is the sum of the two 4-bit binary numbers
  849. ; represented by the x's and the y's.
  850. ; For example, if the inputs are
  851. ; x3 = 1, x2 = 0, x1 = 0, x0 = 1    (representing 9 in binary)
  852. ; y3 = 1, y2 = 1, y1 = 0, y0 = 1    (representing 13 in binary)
  853. ; then the output should be
  854. ; z4 = 1, z3 = 0, z2 = 1, z1 = 1, z0 = 0 (representing 22 in binary)
  855.  
  856. ; Examples:
  857. ; (good-circuit? add-ckt) => #t
  858. ; (ckt-inputs add-ckt) => '(x3 x2 x1 x0 y3 y2 y1 y0)
  859. ; (ckt-outputs add-ckt) => '(z4 z3 z2 z1 z0)
  860. ; (output-values add-ckt (final-config add-ckt (init-config add-ckt '(1 0 0 1 1 1 0 1)))) => '(1 0 1 1 0)
  861. ; (output-values add-ckt (final-config add-ckt (init-config add-ckt '(0 1 1 1 0 1 1 0)))) => '(0 1 1 0 1)
  862.  
  863. ; For the last two tests, your procedures output-values, final-config,
  864. ; init-config must be working.
  865.  
  866. ; You may construct the circuit entirely by hand,
  867. ; or you may choose to write procedures to construct your circuit.
  868. ;**********************************************************
  869.  
  870. ;; By hand
  871.  
  872. (define add-ckt
  873.   (ckt '(x3 x2 x1 x0 y3 y2 y1 y0) '(z4 z3 z2 z1 z0)
  874.        (list
  875.         (gate 'xor '(x y) 'z)
  876.         (gate 'and '(x y) 'co)
  877.         )
  878.        )
  879.   )
  880.  
  881. ;**********************************************************
  882. ; ** problem 10 ** (5 points)
  883.  
  884. ; Define a D-flipflop as described in lecture, using the given
  885. ; representation of circuits.  Please name it: dff-ckt.
  886.  
  887. ; It has inputs:  s, d (in order) and outputs q, qc (in order)
  888.  
  889. ; Examples
  890. ; (good-circuit? dff-ckt) => #t
  891. ; (ckt-inputs dff-ckt) => '(s d)
  892. ; (ckt-outputs dff-ckt) => '(q qc)
  893. ;> (output-values dff-ckt (final-config dff-ckt (init-config dff-ckt '(1 0))))
  894. ;'(0 1)
  895. ;> (output-values dff-ckt (final-config dff-ckt (init-config dff-ckt '(1 1))))
  896. ;'(1 0)
  897. ;**********************************************************
  898.  
  899. (define dff-ckt
  900.   (ckt '(s d) '(q qc)
  901.        (list
  902.         (gate 'xor '(x y) 'z)
  903.         (gate 'and '(x y) 'co)
  904.         )
  905.        )
  906.   )
  907.  
  908. ;**********************************************************
  909. ; ** problem 11 ** (5 points)
  910.  
  911. ; Design a circuit using the given representation that has no inputs
  912. ; and one output 't.  When the circuit is started in the initial (all
  913. ; zero) configuration, after a few configurations, the output is 1 for
  914. ; one step, then 0 for 4 steps, then 1 for one step, then 0 for 4
  915. ; steps, then 1 for one step, and so on.
  916.  
  917. ; Please name your circuit timing-ckt.
  918.  
  919. ; Examples
  920. ; (good-circuit? timing-ckt) => #t
  921. ; (ckt-inputs timing-ckt) => '()
  922. ; (ckt-outputs timing-ckt) => '(t)
  923. ;> (map (lambda (config) (output-values timing-ckt config)) (simulate timing-ckt (init-config timing-ckt '()) 20))
  924. ;'((0) (0) (0) (0) (0) (1) (0) (0) (0) (0) (1) (0) (0) (0) (0) (1) (0) (0) (0) (0) (1))
  925. ;**********************************************************
  926.  
  927. (define timing-ckt
  928.   (ckt '() '(t)
  929.        (list
  930.         (gate 'xor '(x y) 'z)
  931.         (gate 'and '(x y) 'co)
  932.         )
  933.        )
  934.   )
  935.  
  936. ;**********************************************************
  937. ; ** problem 12 ** (5 points)
  938.  
  939. ; Design a circuit using the given representation that has no inputs
  940. ; and one output 't. When the circuit is started in the initial (all
  941. ; zero) configuration, after a few configurations, the output is 1 for
  942. ; one step, then 0 forever after.
  943.  
  944. ; Please name your circuit one-one-ckt.
  945.  
  946. ; Examples
  947. ; (good-circuit? one-one-ckt) => #t
  948. ; (ckt-inputs one-one-ckt) => '()
  949. ; (ckt-outputs one-one-ckt) => '(t)
  950. ;> (map (lambda (config) (output-values one-one-ckt config)) (simulate one-one-ckt (init-config one-one-ckt '()) 20))
  951. ;'((0) (0) (1) (0) (0) (0) (0) (0) (0) (0) (0) (0) (0) (0) (0) (0) (0) (0) (0) (0) )
  952. ;**********************************************************
  953.  
  954. (define one-one-ckt empty)
  955.  
  956. ; ********************************************************
  957. ; ********  testing, testing. 1, 2, 3 ....
  958. ; ********************************************************
  959.  
  960. (define *testing-flag* #t)
  961. (define error display)  ;; turn off error messages
  962.  
  963. (define (testold name got expected)
  964.   (cond (*testing-flag*
  965.          (let* ((expected (if (procedure? expected)
  966.                               (and (expected got) 'OK-TEST)
  967.                               expected))
  968.                 (prefix (if (equal? got expected)
  969.                             '***OK***
  970.                             'X)))
  971.            (list 'testing name prefix 'got: got 'expected: expected)))))
  972.  
  973. (define (test name got expected)
  974.   (cond (*testing-flag*
  975.          (let* ((OK (if (procedure? expected)
  976.                         (expected got)
  977.                         (equal? got expected)))
  978.                 (prefix (if OK
  979.                             '***OK***
  980.                             '***X***)))
  981.            (list 'testing name prefix 'got: got 'expected: expected)))))
  982.  
  983. (define (runtests)
  984.   (list
  985.  
  986.    (test 'hours hours (lambda (x) (> x 0)))
  987.  
  988.    (test 'good-gate? (good-gate? gate1) #t)
  989.    (test 'good-gate? (good-gate? gate2) #t)
  990.    (test 'good-gate? (good-gate? gate3) #t)
  991.    (test 'good-gate? (good-gate? gate4) #t)
  992.  
  993.    (test 'good-gate? (good-gate? (gate 'not 'x 'y)) #f)
  994.    (test 'good-gate? (good-gate? (gate 'nor '("x" "y") "z")) #f)
  995.    (test 'good-gate? (good-gate? (gate 'and '(1 2) 3)) #f)
  996.    (test 'good-gate? (good-gate? (gate 'equal '(x y) 'z)) #f)
  997.    (test 'good-gate? (good-gate? (gate 'or '(w x y) 'z)) #f)
  998.  
  999.    (test 'good-circuit? (good-circuit? sel-ckt) #t)
  1000.    (test 'good-circuit? (good-circuit? eq1-ckt) #t)
  1001.    (test 'good-circuit? (good-circuit? eq2-ckt) #t)
  1002.    (test 'good-circuit? (good-circuit? latch-ckt) #t)
  1003.    (test 'good-circuit? (good-circuit? seq-or-ckt) #t)
  1004.    (test 'good-circuit? (good-circuit? clock-ckt) #t)
  1005.  
  1006.    (test 'good-circuit? (good-circuit? 'hi) #f)
  1007.    (test 'good-circuit? (good-circuit? (ckt '() '() '())) #t) ;ny
  1008.    (test 'good-circuit? (good-circuit? (ckt '(x y) '(z) (list (gate 'and '(x y) 'x) (gate 'or '(x y) 'z)))) #f)
  1009.    (test 'good-circuit? (good-circuit? (ckt '(x y) '(z) (list (gate 'nor '(x y) 'z) (gate 'nand '(x y) 'z)))) #f)
  1010.    (test 'good-circuit? (good-circuit? (ckt '(x y) '(u z) (list (gate 'or '(x y) 'z)))) #f)
  1011.  
  1012.  
  1013.    (test 'all-wires (all-wires eq1-ckt) '(x y z cx cy t1 t2))
  1014.    (test 'all-wires (all-wires sel-ckt) '(x1 x0 y1 y0 s z1 z0 sc u1 v1 u0 v0))
  1015.    (test 'find-gate (find-gate 't2 eq1-ckt) (gate 'and '(cx cy) 't2))
  1016.    (test 'find-gate (find-gate 'w eq2-ckt) (gate 'xor '(x y) 'w))
  1017.    (test 'find-gate (find-gate 'y sel-ckt) #f)
  1018.  
  1019. (test 'ha-ckt (good-circuit? ha-ckt) #t)
  1020. (test 'fa-ckt (good-circuit? fa-ckt) #t)
  1021. (test 'ha-ckt (ckt-inputs ha-ckt) '(x y))
  1022. (test 'ha-ckt (ckt-outputs ha-ckt) '(z co))
  1023. (test 'fa-ckt (ckt-inputs fa-ckt) '(x y ci))
  1024. (test 'fa-ckt (ckt-outputs fa-ckt) '(z co))
  1025.  
  1026. (test 'ha-ckt (output-values ha-ckt
  1027.                              (final-config ha-ckt
  1028.                                            (init-config ha-ckt '(1 1))))
  1029.       '(0 1))
  1030. (test 'fa-ckt (output-values fa-ckt (final-config fa-ckt (init-config fa-ckt '(1 1 1)))) '(1 1))
  1031.  
  1032.    (test 'next-value (next-value 'cx eq1-ckt eq1-config1x) 1)
  1033.    (test 'next-value (next-value 't2 eq1-ckt eq1-config1x) 0)
  1034.    (test 'next-value (next-value 'z eq1-ckt eq1-config2x) 0)
  1035.    (test 'next-value (next-value 'x0 sel-ckt sel-config1x) 1)
  1036.    (test 'next-value (next-value 'v1 sel-ckt sel-config1x) 1)
  1037.    (test 'next-value (next-value 'v0 sel-ckt sel-config2x) 0)
  1038.  
  1039.  
  1040.    (test 'next-config (next-config eq1-ckt eq1-config1x)
  1041.          (make-hash '((x . 0) (y . 1) (z . 0) (cx . 1) (cy . 0) (t1
  1042.                                                                  . 0) (t2 . 0))))
  1043.  
  1044.    (test 'next-config (next-config eq1-ckt eq1-config2x)
  1045.          (make-hash '((x . 0) (y . 0) (z . 0) (cx . 1) (cy . 1) (t1 . 0) (t2 . 1))))
  1046.  
  1047.    (test 'next-config (next-config sel-ckt sel-config1x)
  1048.          (make-hash '((x1 . 0) (x0 . 1) (y1 . 1) (y0 . 0) (s . 1) (z1 . 0) (z0 . 0)
  1049.                       (sc . 0) (u1 . 0) (v1 . 1) (u0 . 0) (v0 . 0))))
  1050.  
  1051.    (test 'next-config (next-config sel-ckt (next-config sel-ckt sel-config1x))
  1052.          (make-hash '((x1 . 0) (x0 . 1) (y1 . 1) (y0 . 0) (s . 1) (z1 . 1) (z0 . 0)
  1053.                       (sc . 0) (u1 . 0) (v1 . 1) (u0 . 0) (v0 . 0))))
  1054.  
  1055.    (test 'next-config (next-config latch-ckt latch-config1x)
  1056.          (make-hash '((x . 0) (y . 0) (q . 1) (u . 1))))
  1057.  
  1058.  
  1059.    (test 'next-config (next-config latch-ckt latch-config2x)
  1060.          (make-hash '((x . 0) (y . 1) (q . 1) (u . 0))))
  1061.  
  1062.  
  1063.  
  1064.    (test 'stable? (stable? eq1-ckt (make-hash '((x . 0) (y . 0) (z . 1)
  1065.                                                 (cx . 1) (cy . 1) (t1 . 0) (t2 . 1)))) #t)
  1066.  
  1067.    (test 'stable? (stable? eq1-ckt (make-hash '((x . 0) (y . 0) (z . 0)
  1068.                                                 (cx . 1) (cy . 0) (t1 . 1) (t2 . 0)))) #f)
  1069.  
  1070.    (test 'all-stable-configs (all-stable-configs eq2-ckt)
  1071.          (list
  1072.           (make-hash '((x . 0) (y . 0) (z . 1) (w . 0)))
  1073.           (make-hash '((x . 0) (y . 1) (z . 0) (w . 1)))
  1074.           (make-hash '((x . 1) (y . 0) (z . 0) (w . 1)))
  1075.           (make-hash '((x . 1) (y . 1) (z . 1) (w . 0)))))
  1076.  
  1077.    (test 'all-stable-configs (all-stable-configs seq-or-ckt)
  1078.          (list
  1079.           (make-hash '((x . 0) (z . 0)))
  1080.           (make-hash '((x . 0) (z . 1)))
  1081.           (make-hash '((x . 1) (z . 1)))))
  1082.  
  1083.    (test 'output-values (output-values eq1-ckt eq1-config2x) '(0))
  1084.    (test 'output-values (output-values latch-ckt latch-config2x) '(1 0))
  1085.  
  1086.    (test 'init-config (init-config eq1-ckt '(1 0))
  1087.          (make-hash '((x . 1) (y . 0) (z . 0) (cx . 0) (cy . 0) (t1 . 0) (t2 . 0))))
  1088.  
  1089.    (test 'init-config (init-config clock-ckt '()) (make-hash '((z . 0))))
  1090.  
  1091.    (test 'simulate (simulate clock-ckt (make-hash '((z . 0))) 4)
  1092.          (list (make-hash '((z . 0)))
  1093.                (make-hash '((z . 1)))
  1094.                (make-hash '((z . 0)))
  1095.                (make-hash '((z . 1)))
  1096.                (make-hash '((z . 0)))))
  1097.  
  1098.    (test 'simulate (simulate eq1-ckt eq1-config1x 5)
  1099.          (list
  1100.           (make-hash '((x . 0) (y . 1) (z . 0) (cx . 0) (cy . 0) (t1 . 0) (t2 . 0)))
  1101.           (make-hash '((x . 0) (y . 1) (z . 0) (cx . 1) (cy . 0) (t1 . 0) (t2 . 0)))))
  1102.  
  1103.    (test 'simulate (simulate sel-ckt sel-config1x 5)
  1104.          (list
  1105.           (make-hash '((x1 . 0) (x0 . 1) (y1 . 1) (y0 . 0) (s . 1) (z1 . 0)
  1106.                        (z0 . 0) (sc . 0) (u1 . 0) (v1 . 0) (u0 . 0) (v0 . 0)))
  1107.           (make-hash '((x1 . 0) (x0 . 1) (y1 . 1) (y0 . 0) (s . 1) (z1 . 0)
  1108.                        (z0 . 0) (sc . 0) (u1 . 0) (v1 . 1) (u0 . 0) (v0 . 0)))
  1109.           (make-hash '((x1 . 0) (x0 . 1) (y1 . 1) (y0 . 0) (s . 1) (z1 . 1)
  1110.                        (z0 . 0) (sc . 0) (u1 . 0) (v1 . 1) (u0 . 0) (v0 . 0)))))
  1111.  
  1112.    (test 'simulate (simulate latch-ckt latch-config2x 3)
  1113.          (list
  1114.           (make-hash '((x . 0) (y . 1) (q . 1) (u . 0)))))
  1115.  
  1116.    (test 'simulate (simulate eq2-ckt (init-config eq2-ckt '(0 1)) 5)
  1117.          (list
  1118.           (make-hash '((x . 0) (y . 1) (z . 0) (w . 0)))
  1119.           (make-hash '((x . 0) (y . 1) (z . 1) (w . 1)))
  1120.           (make-hash '((x . 0) (y . 1) (z . 0) (w . 1)))))
  1121.  
  1122.    (test 'final-config (final-config clock-ckt (make-hash '((z . 0))))
  1123.          'none)
  1124.  
  1125.    (test 'final-config (final-config eq1-ckt
  1126.                                      (make-hash '((x . 1) (y . 1) (z . 0) (cx . 0)
  1127.                                                   (cy . 0) (t1 . 0) (t2 . 0))))
  1128.          (make-hash '((x . 1) (y . 1) (z . 1) (cx . 0)
  1129.                       (cy . 0) (t1 . 1) (t2 . 0))))
  1130.  
  1131.    (test 'final-config (final-config
  1132.                         sel-ckt
  1133.                         (make-hash '((x1 . 0) (x0 . 0) (y1 . 1) (y0 . 0)
  1134.                                      (s . 0) (z1 . 1) (z0 . 1) (sc . 0)
  1135.                                      (u1 . 1) (v1 . 1) (u0 . 0) (v0 . 1))))
  1136.          (make-hash '((x1 . 0) (x0 . 0) (y1 . 1) (y0 . 0)
  1137.                       (s . 0) (z1 . 0) (z0 . 0) (sc . 1)
  1138.                       (u1 . 0) (v1 . 0) (u0 . 0) (v0 . 0))))
  1139.  
  1140.    (test 'final-config (final-config latch-ckt
  1141.                                      (make-hash '((x . 1) (y . 1) (q . 0) (u . 0))))
  1142.          'none)
  1143.  
  1144.    (test 'final-config (final-config
  1145.                         latch-ckt
  1146.                         (make-hash '((x . 1) (y . 1) (q . 0) (u . 1))))
  1147.          (make-hash '((x . 1) (y . 1) (q . 0) (u . 1))))
  1148.    ))
  1149.  
  1150. ;**************  end of hw # 5  **

=>