Author: dlh6014

This week I learned about the wild wacky world of lambda calculus, and I want to share it with everyone because it’s cool and also kinda stupid, so it should be fun.

If you look up what lambda calculus is, Wikipedia will tell you “Lambda calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.” Basically, lambda calculus is a really dumb way of saying that it’s a method of computing things using very simple functions. The syntax of performing a function in lambda calculus is literally as simple as it can possibly be because the point of it is to represent complex problems with the most basic functional building blocks there are.

There are only three rules that define what a “lambda term” is, and they go as follows:

Any variable x is a lambda term
If t is a lambda term, so is λx.t (this is called abstraction)
If t1, t2 are lambda terms, so is t1 t2 (this is called application)

These three sentences obviously make little to no sense at all, and I don’t know why they’re the first thing that everyone says when they’re introducing this subject. I prefer to think of the syntax of lambda calculus in more concrete terms. Here’s how I think about it:

The expression λx.t is a function that takes in a variable x as an input and returns a different variable t as an output
The expression t1 t2 means that you are applying a function t1 to the variable t2

Knowing this, we can start to see how functions will be evaluated. For example, the identity function, which takes in an input and then returns that same input, would be written as λx.x, because this function takes in a variable x and then returns that variable x as its output. What comes after the lambda symbol but before the period is an input, and what comes after the period is the output. To put a value into a function we write (λx.x) y which is the same as having written t1 = λx.x and t2 = y, evaluate t1 t2. The applied function (λx.x) y will return the value y because it takes the value y into the function’s input and then the function returns the input it was given as an output.

To look at a more complicated example, we can write a function with two inputs, (λx y.x y). This function will take in two inputs, x and y, and then return the function x applied to the value y. If we wanted to give some sample inputs to this function we could say (λx y.x y) (λa.a) b. Function application is left associative, so the expressions to the left are resolved before the ones to the right. That means, instead of putting b into the identity function (λa.a), we put the function (λa.a) and value b into the function (λx y.x y) as the inputs x and y respectively. This function application can then be simplified like this:

(λx y.x y) (λa.a) b
(λa.a) b
b

I think that next week I’ll get more into why this is actually cool and not just weird and confusing. We can build up all of modern computation from these simple functions, but for now, I’ll leave you with just the syntax and an idea of how to solve the equations you’re given.

I did not have a fun week, so my plan is to take a low-effort approach to this blog and break down an easy coding problem instead of doing math or something.

Here is the problem:

I ripped it straight from LeetCode and that’s what we’re going to be doing. Python is the easiest language to explain, so that’s what we’ll use for this solution.

Cool!

So, how do we go about solving a problem like this?

First, it’s usually good to figure out what the problem wants us to return to it. In this case, we’re receiving two sorted linked lists [1] and are asked to give them back a single sorted linked list with all the values from the first two. So, what we want to do with our code is compare all the values in each input list against one another and then put them all into a linked list. The process of comparing the numbers in each input list is made easier by the fact that they are given to us sorted. That means that we know that no value in the first list is going to be less than any value that came before it. When we parse each input list to combine them, we only have to compare the first values on each input list before we take them out because we know that if the first value in the second list is less than the first value in the first list, then it is also less than all the other values in the first list.

Awesome, very cool.

Now that we have a general idea of how to solve this problem, we can start to look at implementing it with code. If you’ve never taken any classes about coding then this part might not make much sense to you, but if you got the bit before this then you know all the important concepts and the syntax is unimportant detail.

My solution is not the shortest or the fastest, but it should roughly be the most readable, so it is here:

The comments try to explain each condition statement in the code, so I’ll talk about the broader path this implementation takes. Given two lists and inputs, it first checks to see if they are nonempty because if they’re both empty then we would just return nothing. Then, it checks to see if one of them is empty because if one of them is empty we just want to return the other as our sorted merged list. Then, knowing that neither list is empty, it compares the first value in each list to find the smaller one [2]. The smallest value between the two lists is then taken out of its corresponding list and placed into the list we want to return. Once the smallest value between the two input lists is taken out of its original list, the function is run again with the same two input lists without that smallest value. This process of calling the function within the function is called recursion; it’s a common high-level paradigm in programming, and it can be a little confusing when you first look at it. Basically, this program compares the two lists to find the smallest value between them, then it takes that value from whichever list it finds it in and places it into the merged list in the order that it was taken before going back to look for the next smallest value.

The implementation of this code definitely makes it look more complicated than it is, but if you wanted to do this problem yourself with example input lists, you would probably do the same thing the code is doing. I hope this was at least a little cool.

[1] – Linked lists are not that conceptually difficult but they can be syntactically weird for people who haven’t seen them before. For our purposes, we’ll just think about them as an ordered collection of integers, like a regular list.

[2] – If both the lists have the same number as their first value then the program takes the number from the first list because that’s the if-statement I used first.

WOOHOO!

TIME FOR A BLOG!

Today we are going to talk about public transit. Why its good in general, why its bad here, and why it should be better. : )

So…

Public transit is good because it gets people from place to place in a shared environment, efficiently, with little polluting side effects. A study by UCLA found that, “taking public transportation reduces CO2 emissions by 45%,” as opposed to taking your car [1]. Given that we are lowkey on the precipice of climate disaster, any little things we can do to mitigate our own emissions is good.

Car culture is also cringe and leads to car centric infrastructure. Car centric infrastructure creates disconnected communities and divides people. Not having walkable cities because they are crossed over by roads also inhibits peoples freedoms and encourages a further dependence on cars. If you want to read more about car centric infrastructure you can look at this link [2].

So then, with these two examples having thoroughly and unequivocally proven in everyone’s mind that public transit is better than cars, why is our public transit system so bad? If you look at other countries you can see that they broadly have much higher participation rates in public transit, so clearly there is some factor inhibiting the United States from achieving this relative success.

The first and most obvious culprit is our low population density. It’s easy to look at the United States and say that because our country is so large and our population so spread out that public transportation would be unfeasible. However, if we look at a Country like Canada which is roughly our size and population density, we will still find more comprehensive public transit participation. Clearly, this narrative is not the whole story.

The bigger picture has to do with Americans’ general political rejection of public transit as a common good. The issue has been politicized as a kind of welfare to the point where it cannot receive the public support necessary to secure its funding. If Americans can change their perspective on this issue, and decrease their dependence on cars, they could improve their country and the wider world.

Improving public transportation would also make it easier for me to get from place to place because I don’t have a car right now. So, really, thats the only reason necessary to support public transit. If the government isn’t convinced yet to change things immediately, they will really be letting me down.

[1] – https://transportation.ucla.edu/blog/5-environmental-benefits-sustainable-transportation

[2] – https://texasimpact.org/2022/06/the-unsustainable-reality-of-a-car-centric-united-states/

CHESS

ITS CHESS TIME

INSTEAD OF BEING PRODUCTIVE THIS WEEK, I PLAYED TOO MUCH CHESS SO YOU GET TO HEAR ABOUT THAT WOOHOO!

So,

We all probably know what chess is and how it works. I have played chess for a while but I sorta stopped when I got to college because I had other things taking up my time and now I’m back to playing again because I would rather do anything than be productive.

All I can really think of to share is the openings I play, so that’s what we’re gonna do. The theory I probably know best is with the black pieces against the move e4 by white so we’ll run through a theoretical line that I don’t like and can complain about.

BANG! 1 e4 is on the board by white. I usually follow up with the Caro-Kann Defense as black, which starts with c6.

WOW! WHAT A GOOD RESPONSE BY ME! White’s best and most common response to c6 is d4, where they’re trying to capture more central control with two pawns in the middle.

GOOD GOLLY! WHAT A PRINCIPLED MOVE FROM WHITE! Now that it’s my turn again I can execute the plan I set up with the seemingly pointless move c6 by pushing my other pawn to d5.

OH MAN! NOW MY CENTRAL PAWN IS SUPPORTED BY A FLANK PAWN, STRENGTHENING MY CENTRAL CONTROL! From this position, there are a lot of different lines that white can play into, but my least favorite is the main line because it’s very boring and involves a lot of piece shuffling that doesn’t really go anywhere. In the mainline, white plays their knight to the c3 square.

The traditional response to knight c3 is for black to just take the pawn on e4. There are a lot of reasons for this, it cripples white’s center, it allows our bishop to get developed on the next turn, and it forces the knight to move twice which wastes white’s early game advantage, but you don’t need to know or care about any of that. We’re just gonna do it cause the almighty computer gods told us to.

White here obviously doesn’t want to lose a pawn for nothing so they are going to recapture with the knight.

From here, black has a few options but the best one is just to develop your bishop to the center of the board by playing bishop to f5.

Now white’s knight is under attack and they have to decide where to move it. I think a lot of players that are unfamiliar with this position might assume that the best move is to just put the knight back on the square it came from, c3. However, this would take us back to basically the same position as before except now black has their bishop out so white would be left in a slightly worse position than before. To prevent this from happening and win themselves an extra turn to bring another piece out, white actually wants to go knight to g3, defending the knight while also attacking the bishop.

Stuff like this is why I’m not a huge fan of the main line Caro-Kann. In other lines, you can get very interesting and tactical play, but here we’re just sorta lightly batting each other’s pieces around the board aimlessly instead of making any real forward progress to advance our own position.

Now that our bishop is attacked, we want to slide it back to safety on g6 where it can be protected by pawns and not attacked by other pieces.

From this point, the theory starts to devolve into too many potential lines to really consider any as a main line, so there’s no point in covering them in detail [2]. I hope you thought it was at least kinda cool to see the first 5 moves in the main line Caro-Khan. If you wanted to look up a professional game and they happened to want to play the main line then you would almost certainly see these first 5 moves on the board.

[1] – DISCLAIMER: I am only ~okay~ at chess, what follows here is not financial advice and cannot be held against me in a court of law.

[2] – I could conceivably do more about the “traditional” moves from here but 1) they’re not very good and have been refuted by the engines and 2) this blog is already at the word count.

Last week I wrote a rambly civil issue blog about how misinformation within the United States is an imposing threat to our democratic system and blahdy blahdy blah. I was just planning to forget about it after I wrote it, but then a news story dropped this week that really highlights my point and honestly it depressed and enraged me enough that I felt compelled to share it with you all today.

So, here’s what happened.

There’s an election services company called Dominion that handled some of the votes cast in the 2020 presidential election. Fox News of course claimed that Dominion’s voting machines were rigged [1], and now Dominion is suing Fox for defamation against their company. Defamation is usually very hard to prove, but this week the public summary-judgment motions were released, detailing the evidence that Dominion has collected to prove that Fox hosts knew they were lying about the election claims. In private messages between one another, prominent Fox hosts like Sean Hannity, Tucker Carlson, and many others reported called the election fraud claims and the people making them “ludicrous,” “totally off the rails,” “F’ing lunatics,” “nuts,” “complete BS,” and “MIND BLOWINGLY NUTS.” In one particularly MIND BLOWINGLY NUTS incident one of their reporters fact-checked a Trump tweet and they went so far as to fire her.

[2]

The reporters at Fox never believed the stolen election claims for a second. However, when they went on TV they pushed the lies for as long as they could get away with it. If you want an actual review of what they said on air I strongly suggest you read this article from NPR, but it was basically just a full endorsement of the idea that Biden’s victory was illegitimate by either glitches or conspiracy against Trump. The reporters brought people onto their show that they privately knew were lying to spread misinformation for the sake of their party and company’s bottom line. AHHHHHHHH!

Just so we all understand the measurable harm caused by these lies. Firstly, most of the platforming and private admissions happened before January 6th so you can basically guarantee that riling up their base with these lies was at least a partial cause of the terrible things that happened that day. Second and more importantly to the lasting sustainability of our democracy 40% of Republicans still don’t believe that elections will be conducted fairly in the future [3]. Reporting like this is a clear and present danger to the future of our democracy. The Fox reporters knew they were lying; people died because of this lie, and if things don’t change people could keep dying.

Not fun at all!

I wanted to take more time in this blog to talk about solutions to the issue of misinformation because most misinformation can’t be PROVEN to be malicious lying, so the issue can be quite nuanced. However, I’ll save a more thorough deconstruction of how I think it best to address misinformation for another blog here and just say now that if you’re a dumb enough newscaster to admit the news you’re casting is a lie then you deserve whatever’s coming to you.

[1] – GIULIANI (and others) SAID THAT THE VENEZUELAN GOVERNMENT OWNED THE VOTING MACHINES AND WAS FLIPPING TRUMP VOTES TO BIDEN. This is of course false

[2] – This screenshot is pulled from the brief, which can be found here for those interested.

[3] – The statistic I pulled was from a Pew Research survey here, but other similar findings are reported here, and here.

GUESS WHAT WE’RE DOING TODAY!

…

THATS RIGHT! MORE LINEAR ALGEBRA! WOOHOO!

So,

Here we go,

This is it. This is the big one. For all the marbles. What we’ve been leading up to for the past 4 blogs.

Vector Bases.

DUN DUN DUN!

I’m mostly joking in a distinctly unfunny way here. These actually aren’t that important, but they can be reasonably powerful tools and they represent a good synthesis of the stuff we’ve covered so far.

We’ll start with a definition and then a theorem [1]:

Def – A basis is a set of linearly independent vectors that span a vector space.

Thrm – Every vector space has a basis.

Basically, a basis can be used to describe a given vector space. We take a set of independent vectors that can be used in a linear combination to make any other vector in that space. For example:

What is the basis of the vector space in R3 [2], V = {: 2x + y = 0}?

What we’re looking for here is a set of vectors that can be multiplied and added to make any vector that fits that description, so a good starting place is to figure out what vectors actually fit that description.

We can see that vectors in this space are 3D and must have values x and y such that 2x + y = 0. A little bit of algebra can show us that y = -2x and we can say that the vectors in this space are of the form . This vector is arbitrary because it has 2 variables that could be any number so it doesn’t have defined values. To find the linear combination that constructs this vector we can separate the parts that don’t share the same variable: + <0, 0, z>, and then remove the variables x * <1, -2, 0> + z * <0, 0, 1> and WHADDAYA KNOW BA-DA-BING BA-DA-BOOM THAT LOOKS TO ME LIKE A LINEAR COMBINATION OF VECTORS THAT CAN REPRESENT ANY VECTOR IN OUR DEFINED VECTOR SPACE! WE’VE FOUND OUR BASIS!

Specifically, the basis is the set B = {<1, -2, 0>, <0, 0, 1>}.

If you’d like to check, you can verify for yourself that it is infact possible to make any vector in V by multiplying and adding the ones in B. I’m not sure if you really need to because most of what we did here is algebra, but maybe I didn’t explain it well enough to convince you. Maybe you don’t even know how to check because I didn’t explain that well enough.

Anyways,

I’ll probably talk about why these bases are cool or something next week.

[1] – Theorems are just like important rules that you should know. They are usually proven when you’re given them, but we’re too cool to show our work here.

[2] – R3 is just the 3D space of real numbers, think of it like a 3D coordinate plane except instead of putting functions on it, we’re putting vectors.

More linear algebra time woohoo!

So,

Vector spaces, to my knowledge, are like the big important things about linear algebra that everyone cares about. How to make them. How to manipulate them. What they can do. So on and so forth.

So, what is a vector space?

We’ll,

For a collection of vectors to be called a vectors space it must meet the 3 criteria

Inclusion of the null space. The collection must contain a vector that looks like <0,0,0>.
Closure under addition. If you take two vectors in the vector space and add them together, their sum must also be in the vector space
Closure under scalar multiplication. If you take a vector in the vector space and multiply it by a scalar [1], like this:
2 • <1,2,3>
Then the product, <2,4,6> must also be in the vector space. [2]

So, armed with the knowledge of what it means to be a vector space, we can try and prove that a collection is a vector space ourselves.

Suppose there is a real set of three-dimensional vectors, S = { : x + y + z = 0}. Based on our definition of the set, we know that all vectors in it are of the arbitrary form because all of its terms must sum to zero to be in the set. With this knowledge we can begin looking at the requirements:

Is the zero vector in the set? Well, the vector <0,0,0> is a three-dimensional vectors where all the terms add to 0 so it must be in the set.
Is the set closed under addition? If we take two arbitrary vectors in the set and and add them together we get the vector sum <(x + a), (y + b), -(x + a) -(y+b> and off we add all the terms of that sum together we get 0, so it looks like adding any two vectors in the set will return a vector in the set and it’s therefore closed under addition
Finally, is the set closed under scalar multiplication? If we take and arbitrary vector in the set, , and an arbitrary real number, a, then multiply a • , we get as the product. Once again, if we add all these terms together we see that they sum to zero, so the product of any real number times any vector in the set is also in the set and the set is closed under scalar multiplication.

Because our set of vectors meet the three requirements, it can be considered a vector space and has a lot of cool properties that we can talk about in another blog. For now hopefully you thought the example of a proof for a vector space was cool, annnd have a good week until my next blog.

[1] – for our purposes you can think of a scalar as any real number, it just basically means a number that isn’t a vector.

[2] – the actual requirements can get a little more abstract, so there are conceivably vector spaces that wouldn’t really fit the stuff I said here but this is a good introductory way to understand vector spaces.

MATH HOMEWORK PROBLEM! SO FUN!!! VERY MUCH FUNN!!#E

WOOHOO

So,

Question,

We have 3 vectors <1, 3, 2> <0, 1, 1> .

What values of x make the vectors linearly independent?

To answer that, we’ll start off with an easier question. What does being linearly independent even mean?

Well,

If you read my last blog you’ll remember that we can create new vectors by stretching and adding other vectors together. A vector is a ~linear combination~ of other vectors if it can be written in the form v1 = a*v2 + b*v3 where v1, v2, and v3 are all vectors and a and b are real numbers. A set of vectors is then linearly independent if no vector is a linear combination of the other vectors in the set.

Cool.

Next easier question. How do we solve that?

Well, very similarly to the last blog…

WITH A MATRIX!!! WOW!

So,

We set these bad boys up (vertically) in a matrix like so

And begin the process of row reduction just like we did last time [1]. First, we begin by subtracting 3 times the first row from the second.

Then we subtract 2 times the first row from the third.

Then finally we subtract the second row from the third.

The point of this seemingly arbitrary arithmetic is to make a little triangle of zeros in the bottom left corner. Why do we do this? Kinda just because it works, but mostly because we want each column to contain the first nonzero digit in a row with only zeros below it [2]. Strange, but good for us.

What’s important to understand about this process is that the vectors are linearly independent as long as the bottom right value is anything but zero [3]. Which means we have everything we need to actually answer the problem. As long as 2x+1 doesn’t equal 0 we’re linearly independent, so a little algebra tells us that x can be any real number except -0.5.

BAM!

The problem’s solved. Easy money, simple but fun, very cool.

[1] – I realize that I sorta handwaved what row reduction is or why it works last time, but to tell you the truth I only have a very fuzzy understanding of why it actually works, so it would take a VERY long time to explain, and that is not the point right now.

[2] – this is a laughably bad explanation

[3] – trust me bro [4]

[4] – I could actually do a proof of this for next week

Linear algebra is easily the most interesting math class I’ve taken in my academic career. While the topics can be especially conceptual, the foundational logic has always seemed more straightforward to me than other subjects. I took a 200-level linear algebra class last year as a senior in high school and am now working on the 400-level here at Penn State. We haven’t really gotten to anything I haven’t done previously yet, so this week I’ll just talk about some fun matrice properties.

Firstly, we will be working with 2-dimensional vectors for simlicity, and to operate on these vectors there are two things we can do: add and multiply by a scalar.

When we add vectors we combine them tail to tip to make a new vector. In the example below, we add the vectors <1,2> and <3,1> to get the new vector <4,3>:

Very Cool.

Next, we can also multiply vectors by scalars to stretch and compress them. For example, if we take the orange vector <4,3>, we can multiply it by the scalar, 2, to get a new vector <8,6>.

Likewise, we can also shrink a vector by multiplying it by the scalar 1/2.

Armed with the knowledge of how to operate on vectors, we can begin to perform simple arithmetic with them. For example, if I have the vectors <5,-2> and <3,7> can I stretch and add them to make the vector <6,4>? If so, then what do we multiply each vector by to add them?

To find this out, we can do a lot of things because 2-dimensional vectors are a little silly, but the best thing to do is make a matrice.

We constructed this matrix by making our constituent vectors vertical and putting our answer vector in the last column [1]. With this setup, we can begin performing elementary row operations on the matrix to simplify it. The exact reason why we’re doing this and why it works is a bit out of the purview of this blog, so you’ll just have to trust me for now. Because this is only two rows, we only need to perform one operation, we take each element of row 1 and multiply it by 2, and then each element of row two and multiply them by 5, and then add each element in row one to its corresponding element in row two.

These operations leave us with a 0 in the first column and second row. This is good because it makes it much easier to tell what we need to multiply our vectors by to sum to <6,4>. We want our first two vector columns to be multiplied out to sum to the last value in their respective rows, so this is the same as solving a linear system which you might be more familiar with.

In this form, it should hopefully be easy to see that the only value for y is 32/41 because (41/41)*32 = 32. And if we know that y = 32/41 then it is easy to solve for x even though the numbers are ugly.

With this, we have our answer to the original question. If we multiply <5,-2> by 30/41 and <3,7> by 32/41 and then add them together, we get <6,4>. You can verify this for yourself if you’d like. Cool cool.

[1] – I feel like the vertical vectors could be a little confusing. They’re the same as writing <5,-2> and they multiply in the same way except they’re easier to work within the matrix.