elizabeth wei's blog

This winter break, Andrew (my brother) and I worked on board2board, a collaborative drawing web app that uses a computer's webcam for object detection. We were inspired to create this after realizing that at least on our Macs, it was annoying to draw on the trackpad or having to switch back and forth to our iPads. Why not draw in the air instead? Features include using the space bar to toggle between drawing/not drawing... ...pressing the "c" key to clear everything...   ...multiple users collaborating in the same session (hover over avatars to see full usernames)... ...and being able to choose between detecting green or blue drawing objects. For example, in the gif below, using a green marker is much more accurate. We added this feature after finding that object detection accuracy heavily depends on where the user is. If there's a lot of other blue, then a blue marker wouldn't be as easily tracked.   Check out my brother's blog post f

Part of the  tldr series , which summarizes papers I'm currently reading. Inspired by  the morning paper . tldr: ARIES - A Transaction Recovery Method [1992] Mohan et. al *With Concurrency Control and Recovery, by Franklin and an example from   http://db.csail.mit.edu/6.830/notes.php    ARIES is a protocol for DBMS recovery based on WAL. (For a review of the basics of WAL, you can take a look here .) This blog post will go over ARIES with an example and explanations along the way. Example This is the example we'll be following: CP = checkpoint, Flush = flush to disk, W = write Assume the following is the log right before the crash: SOT = start of transaction, EOT = end of transaction, UP = update (In this example, each data item is on a different page. Treat them synonymously for simplicity.) Data Structures Transaction Table The transaction table stores data about ongoing transactions. One of the pieces of data is lastLSN , which is the LSN of the

Part of the  tldr series , which summarizes papers I'm currently reading. Inspired by  the morning paper . tldr: Concurrency Control & Recovery Franklin   Concurrency control  makes sure that users see consistent states of the database even though users' operations may be concurrent. Recovery makes sure that software or hardware failures don't corrupt the database state. Together, these DBMS components make things easier for developers who create applications on top of a database.  Transactions  A transaction groups a set of logical operations into a unit, that all abort or all commit as one. If a transaction commits , all its updates become permanent and visible to other transactions. If a transaction aborts , all its updates are erased. The properties that a transaction should have are: A tomicity: all or none of the operations in a transaction succeed. C onsistency: the transaction leaves the database in a consistent * state.  *A circular definition, bu

Part of the tldr series , which summarizes papers I'm currently reading. Inspired by the morning paper . tldr: Architecture of a Database System [2007] Hellerstein, Stonebraker, Hamilton This paper focuses on DBMSs, specifically RDBMSs, the "most mature and widely used database systems in production today." The figure above shows a generic RDBMS. Before going into detail into each of the 5 main components, the paper walks through an example of a single-query transaction:  At the airport, a gate agent clicks on a link to request a flight's passenger list.  The gate agent's computer (the client) calls an API which establishes a connection over a network with the Client Communications Manager .  This component is responsible for:  Establishing and remembering the connection Responding to SQL commands from the client Returning data and control messages There are a couple types of arrangements: Client-server system : direct connection betwee

Part of the tldr series , which summarizes papers I'm currently reading. Inspired by the morning paper . tldr: The Relational Model ft. What Goes Around Comes Around [2005] Stonebraker et al. Stonebraker and Hellerstein go over the history of data model proposals, since many similar ideas have been recycled over the years. The goal of this paper is to help "future researchers avoid replaying history".  Hierarchical (IMS): Late 1960s and 1970s "Lesson 2: Tree structured data models are very restrictive" This data model arranges data in trees of record types (a collection of named fields with data types). Each record type except for the root has a unique parent record type. In a tree structure, data must often be repeated (which is undesirable because data could become inconsistent). Also, the tree structure can't represent a record type that doesn't have a parent. "Lesson 4: A record-at-a-time  user interface forces the programm

A follow-up to my previous post about building a toy language interpreter in Go. Throughout this post, I'll be referencing my repo . We'll go over a compiler which translates source code to machine code, and then a VM to execute this machine code. What is a compiler?  A compiler takes source code and translates it to executable machine code . (See my previous post for more details.) The figure below shows the high-level architecture of a simple compiler. Like the interpreter we built previously, our compiler has a lexer and a parser which turn our source code into an AST . This is our compiler's frontend . However, that's where a compiler diverges.  The compiler may translate the AST into at least one internal representation (IR) . The IR(s) may be represented using any data structure (even another AST!), but they should follow two rules: (1) be easy to produce, (2) be easy to translate into the target machine code. The IR can also be optimized

In this post, I'll be giving a high-level overview of interpreters, why they're interesting, and how they work. I'll be referencing my repo, go_interpreter , which is a simple interpreter written in Go for a toy language. The figure below shows the structure of our interpreter with an example input: What is an interpreter?  An interpreter is a language processor that seems to directly execute the source program on user input: In contrast, a compiler first takes in a source program and translates it to an executable machine code target program. Then, the user can pass in inputs to this target program and get outputs. In general, an interpreter is better at reporting errors since it's processing statements one at a time, and a compiler is faster at generating outputs from inputs. In this post, we're going to go over a simple interpreter that is capable of supporting: integers, booleans, strings, arrays, hashmaps prefix, infix operators index opera