reduce reduces compute time for list-based operations: it changes a linear series of events to divide-and-conquer so you can parallelize it

in theory reduce only works for associative operations?

in NSM, reductive paraphrase is the act of reducing all utterances in a language into semantic primes.

This is usually done with the application of an inherent, universal grammar: the conceptual grammar of semantic primes.

problems with reductive paraphrasing

In the experiment conducted by (Labov 1973), Labov (according to (Geeraerts 2009), manuscript not found) showed that the boundaries of cup vs. mug are not clearly delineated.

Thanks for opening Jack’s long rambly PDF. Please read all of it; I wanted to get this out there before anything else so I apologize in advance for a letter that’s on the longer side and I didn’t have time to write a shorter one.

Before you begin, please read Michael’s AMAZING notes on our pitch to get the context. It’s amazing. I will not repeat here anything mentioned there.

Pat yourself on the back

Oh god was that a difficult semester. We got through many a challenges and worked together to solve most of them. That’s cool. We also built a thing that the XRT team liked; so that’s cool too.

Intermediate code uses “unlimited” temporaries. We have more temporaries than there are registers. Key: assign multiple temporaries to each register

example

Consider:

a := c + d
e := a + b
f := e - 1

notice how a and e are both dead after use, we can then allocate:

r1 := r2 + r3
r1 := r1 + r4
r1 := r1 - r1

key: *you can share a register between \(t_{1}\) and \(t_{2}\) if at any point at most one of \(t_1\) and \(t_2\) are alive.

algorithm

liveness check

go through liveness analysis to see what’s live or not at any particular moment.

Regular expressions express computation as a simple, logical discretion, through closure properties (such as properties of regular languages). a family of languages which satisfy closure properties of DFA regular languages, which turns out to be exactly the set of languages that DFA and NFA both recognize.

“What is the complexity of describing the strings in a language?”

definition

Let \(\Sigma\) be an alphabet, we define the regular expressions over \(\Sigma\):

• for all \(\sigma \in \Sigma\), \(\sigma\) is a regexp
• \(\varepsilon\) (empty string) is a regexp
• \(\emptyset\) (empty set) is a regexp

If \(R_1\), \(R_2\) are regexps, then: