05: Mutable Data and the Metacircular Evaluator

This article is a part of a series where I go through teachyourselfcs. If you would like to start at the beginning start here.

LECTURES

L24

If sharing storage mutating may affect data, if not sharing storage it won’t.

Can’t mutate quoted list. Have to use cons or list.

eq? is when it is the same location in memory. equal? is equality.

L25

Table: association between keys and values

put: if no key in the table, create new one.

2d table: a key that has a table structure as its cdr.

Runtime for 2d table: n + y where n is the size of the table and y is the size of the second table.

2 lookups for key value store. assoc and assq.

memoization: storing previous calculations to build a result.

If underlying calculation is not functional you can’t use memoization.

L26

vector (array): indexed list

vector best if needing to access a certain element a lot, accessing a value is o(1) instead of o(n) (worse case).

if you need to build up a list element by element list are faster.

L27

streams: returns the first element, and a promise to compute the rest later.

Modern processers guess where the test is going to be and starts calculating the rest while still doing the test.

delay: constructor for promises.

(delay exp) => (lambda () exp)

promise remembers what it is returning to.

L28

Integers computes the next integer just in time for the next computation to be run.

Only use streams in functional programs. Chapter three is about systems that change state over time.

Parallelism simple with functional programming, very hard with mutating variables.

Scheme uses normal order because it supports mutations.

Haskell is a purely functional language that uses applicative order.

L29

Your operating system can assign you a port number.

packet: burst of information you throw out and hope for the best.

internet: network of networks

Router connects to people outside your network.

worldwide unreliable packets, because the network traverses many computers that could crash.

TCP: Transmission control protocol, provides worldwide reliable streams.

socket: abstract data type holds port numbers and other stuff.

thunk: procedure with no arguments

thread: way of having many things happen at once in one program.

L36

Old systems: take in variable and computes function.

new systems: take in variable and function and compute function.

This means that one machine can compute a function.

read translates what you type into box and pointer form.

L37

This lecture went over the logo language.

lexical scope:
allows local state vars (OOP)
prevents capture bugs
faster compiled code

dynamic scope:
allows first class exprs
allows “semi-global” vars
better debugging environment

LABS

Lab 5A

5A mostly drawing diagrams.

Lab 5B

Need access to Berkeley’s login for the resources for 5B.

READINGS

3.3 Mutable Data

data objects that have a setter defined are known as mutable data objects.

You can build table by gluing box-pointers together. A table with a arbitrary value at the start of the table is called a headed table.

You can use a lookup procedure to get values out of the table given a key.

4.1.1 - 4.1.6 Metalinguistic abstraction

Evaluator: A procedure that when applied to an expression can perform the action required for the expression.

The evaluator is just another program.

metacircular: An evaluator that is written in the language it evaluates.

eval: takes as arguments an argument and an expression. Then it classifies the expression and directs its evaluation. Eval also looks up variables within the expression.

Apply: Apply takes a procedure and list of arguments. Constructs a environment for compound procedures.