Month: March 2023

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.