CSE 1729 Lecture 27: CSE 1729 - Lecture 25 - Pairs in Mutable Programming
26 Nov 2018
School
Department
Course
Professor
CSE 1729 verified notes
27/30View all
Lecture 25: Pairs in Mutable Data
Pairs:
• Our pairs are pairs of pointers, which serve as 2 adjacent memory
locations which hold and address of some other things
• A memory cell can hold a primitive SCHEME value: boolean,
character, token, number, etc
• Each memory has a unique address: a number that the computer uses
to refer to it
• First memory address is where the first thing in that pair lives,
second address is where the second things in that pair lives
• Cdr of the list can be a pair representing the rest of the list
• SCHEME reserves a special null pointer
• Then, lists are represented as nested pairs, where the car points
to the first element of the list and the cdr points to the "rest"
of the list
• Set-car! and set-cdr! Destructively set the car and cdr of the
pair
Semantics of variable assignment depend on the value:
• (define var <expr>) sets var to be the value returned by <expr>
• If the value is an atomic scheme type (number, boolean, etc) a new
ell with the value is set up and the variable is directed there
• (define var <expr>) sets car to the value returned by <expr>
• If the value is structured, like a pair, this is referred by a
pointer: a new copy is not produced
Mutable vs immutable in racket:
• Cons, car, cdr are all immutable
• Mcons, mcar, mcdr are mutable
Queue:
• Maintain a queue as a linked list that remembers its tail
• Each node must remember 2 things: a value and a pointer to its
successor
• Pair: (value . next)
• Useful functions:
o (define (value n) (car n))
o (define (next n) (cdr n))
o (define (empty? (null? Head))
o (define (front) (value head))
• To maintain a queue we maintain 2 pointers:
o Head: points to the front of the queue
o Tail: points to the end of the queue
Insertion and deletion via pointer redirection: enqueue
(define (enqueue x)
(let ((new-node (cons x '())))
(begin
(if (empty?)
(set! head new-node)
(set-cdr! tail new-node))
(set! tail new-node))))
