7c0h

Articles tagged with "programming"

I'm running out of forums

As so many immigrants expats around the world, I like to follow the news regarding what's happening back in my home country. But getting complete, reliable information has been getting more and more difficult every year, and 2020 is the year in which I finally ran out of news sources.

Unlike my parent's generation, I don't consider newspapers a reasonable source of reliable information. The problem is that, following the example set by Fox News, the largest newspapers at home have substituted fact for opinions, extremely biased articles, and outrage has replaced objectivity as the main selling point. All of this seasoned with local celebrity gossip, of course.

If despite my best judgment I decide to check what's going on based on newspapers, I currently start with the biggest newspaper (which is very right-leaning) and then compensate with their main opposition (which is, as expected, very left-leaning). I then figure out which news are common to both, and decide which version is more likely to be true - one newspaper's fair trial is the other newspaper's witch hunt, and one newspaper's smart move is the other newspaper's national betrayal. Finally, I check which news have been mentioned in only one of them, and decide on a reasonable narrative for why only one of them is talking about it. Suffice to say, doing this in the morning on my phone takes a lot of effort.

In my case, this was one problem (probably the only one) solved by the news aggregator Reddit. The sub-reddit for my country used to be relatively good at highlighting the main issues in the public conscience, and reading the main posts used to be enough to get a good, updated picture. But not anymore: extremely lax moderation and general apathy have turned the forum into a meme-laden wasteland where all information has been replaced by bad jokes, political outrage, and the occasional "kill all poors" post. So I quit it for good, and haven't looked back.

Which leads me to today. I have not yet found any source of news that I can trust to inform me. Sure, I can easily get distracted, entertained, outraged, tricked, and lied to, but informed? Good luck with that. I have remained uninformed for a couple months now, and I don't see that changing anytime soon.

Being a programmer who has spent a bit of time toying around with NLP, I have been working on a solution - a small news aggregator where I can get a proper sense of what's going on. But it hasn't been easy: news agencies no longer offer RSS feeds, important data is locked behind proprietary formats made intentionally hard to read, and there is barely any corpora around in Spanish that I could use to train models.

I don't have a deeper point. I can't promise that my solution will work, because it's entirely possible that it never makes it out of vaporware. I don't have a website to recommend, because websites are getting bad faster than good ones are propping up. And I'm not going to talk about the cesspool that are unmoderated forums because we all know about that already.

I just wanted to say: I am very unhappy with this situation.

Why programming is hard

I have been giving programming languages a lot of thought recently. And it has ocurred to me that the reason why (reportedly) lots of people fail at learning how to program is because they are introduced to it at entirely the wrong level.

If you as a beginner search "Python tutorial" right now, you will get lots of very detailed, completely correct, very polished tutorials that will teach you how to program in Python, but that will not teach you how to program. Conversely, if you search for "how to program", the first results will be either completely useless advice such as "decide what you would like to do with your programming knowledge" or they ask you to choose a programming language. You might choose Python, in which case you are now back to square one.

One of the founding principles of my field is that "Computer Science is no more about computers than astronomy is about telescopes". In other words, programming is a skill that it's expressed typicall using programming languages, but it's not exclusively about them. And programming, the skill underlying all of these programming languages, is hard.

To be a good programmer, you need to master three related skills:

  1. Understand how to convert messy real-life problems into a clearer version with less ambiguities.
  2. Understand what the best practical approach to this problem is, and choose one as a possible solution.
  3. Understand how to use programming languages and data structures to implement that solution.

Mastering the first skill requires an analytical mind, and in particular forces you to see the world in a different way. If someone asks you for a program to keep track of how many people are inside a room, you need to stop thinking in terms of people and rooms and think in terms of numbers and averages. You also need to account for badly-defined situations: if a woman gives birth inside the room, is your solution good enough to increase the room count by one?

This part alone is quite hard. Some people make a living out of it as software requirements engineers, meeting with clients and discussing some approaches that would make sense. It also requires at least a surface level understanding of the type of solutions that one could realistically employ. If you ever wondered why your high-school math teacher always asked you to turn apples and trains into equations and solving for x, well, this is why: they were teaching you how to solve real-world problems with simpler methods.

In order to master the second skill "choose a viable solution", you need to read a lot about which problems are easy and which ones are hard. There are some problems that a programmer solves daily, and some problems for which the best known solution would still take thousands of years. If you think that finding new solutions to problems is interesting, I encourage you to go knock at the Math department of your nearest university. They do this for a living, and will be very excited to have you around.

Finally, the third and last skill "implement a solution" requires you to write it down in a way that computers can understand. Half the job requires understanding common concepts for structuring programs (variables, databases, data structures, networks, and so on), and the other half requires learning the syntax of your preferred programming language.

And here we reach the core of this post's answer. If you type "Python tutorial" right now, what you'll get are very detailed guides on how to acquire the second half of the third skill, also known as "the unimportant one". Sure, programmers love discussing which programming language is better and how not to write code, but here's a little secret: in the larger scale of things, it rarely matters. Some programming languages are better suited for specific tasks, true, but the best programming language is not going to be of any help if you don't know what you are trying to build.

At its core, programming is learning how to solve problems with a specific set of tools. And while you do need to understand how to use those tools, they are completely useless if no one explains to you how to solve problems with them. If knowing how to use a pen doesn't make you a writer, and knowing how to use a wrench doesn't make you a mechanic, teaching you a programming language and expecting you to become a programmer overnight is just going to leave you confused and frustrated. But remember: it's not you, it's them.

Appendix I: what does problem solving looks like?

Let's say someone asks me to "write a program to know who I have been in contact with in any given day", a problem known as contact tracing that has been in the news in the past weeks. How would the skills above come into play?

(Note: for the sake of simplicity, I am going to solve this problem badly. It's a toy example, so don't @ me!)

The first step is to model this situation in a formal, more structured way. Real people are difficult to work with, but luckily we don't care about most things that make them human - all we care about is where they have been at any point in time. Therefore, we replace those real people with "points", keep track of their GPS coordinates at all times, and throw all of their remaining attributes away.

We have now turned our problem into "tell me which GPS coordinates (i.e., points) have been close to my GPS coordinates at any given time". We can simplify the problem further by defining what "close to me" means, and we turn the problem into "give me a list of points that have been 1 meter or closer to me at any given time".

Next, we need to find a way to efficiently identify which points have been close enough to our coordinates. Since there is a lot of people in the world, we start by crudely removing all points that are more than 10km. away from me - this can be done very quickly, and it probably won't affect our results too badly.

We now need to refine our search, and therefore we take a dive into the geometry literature. After a quick look, I decided that building a Quadtree is the best solution for what I want to build. Note that I only have a passing knowledge of what Quadtrees are, but that's fine: once I have a hint of where the solution might be, I can search further and learn the details as I go.

And finally we get down to writing code. If our programming language doesn't already include an implementation of a Quadtree data structure, we might have to do it ourselves. If we choose Python, for instance, we need to understand how to create a class, how to use lists of objects, and all those other implementation details that our Python tutorial has taught us. Similarly, storing the list of points will probably require a database. Each database has a different strong point but, as I said earlier, knowing which database to use is not as important as knowing that some database is the right tool.

Let's now picture the same exercise in revers: imagine I come to you and say "Write me a program to know who I have been in contact with in any given day. Here's a guide on how to use Quadtrees in Python". You wouldn't find that last bit of any use, would you?

Moon landing in Basic

As many other people around my age, I learned programming from a book. In particular, I started programming with a 3-books series called Computación para niños (Computers for kids). Volume 3 was dedicated to programming in BASIC, and it opened the door to what is now both my profession and hobby.

That said, that book was also the source of a 25-ish-years-long frustration, and that story is the point of today's article.

In the ancient times known as "the 90s", it was still common to get printed code for games that you had to to type yourself. This book, in particular, included a game called "Lunar rocket" in which you were supposed to (surprise!) land a rocket on the moon. For context, this is how the game was sold to me:

Picture of a book page, showing
illustrations of how to play the game

And this is what the code looks like:

Picture of a book page,
showing BASIC code for a program

Suffice to say, the program never worked and I couldn't understand why. I spent weeks trying to tweak it to no avail, getting different errors but never making a full run. And no matter how hard I tried, I could never get a single picture to show on screen. Eventually I gave up, but the weeks I spent trying to understand what I did wrong have been on my mind ever since.

That is, until last Sunday, when I realized that I should go back to this program and establish, once and for all, whose fault all of this was.

Problem number one was that the book shows pretty pictures, but the program is text-only. That one is on me, but only partially. Sure, it was too optimistic of me to expect any kind of graphics from such a short code. But I distinctly remember giving it the benefit of the doubt, and thinking "the pictures are probably included with BASIC, and one or two of these lines are loading them". That was dead wrong, but I'll argue that young me at least had half of a good idea. A few years later I would learn that the artwork and the game rarely had anything to do with each other, a problem that has not entirely gone away.

Now, problem number two... That code I showed above would never, ever work. My current best guess is that someone wrote it in a rush leaving some bugs in, and someone else typed it and introduced a lot more. In no particular order,

  • Syntax errors: Line 130 has a typo, the variable name "NÚMERO" is invalid because of the accent, and line 150 is plain wrong. The code also uses ";" to write multiple instructions in a single line, but as far as I know that's not valid BASIC syntax.
  • The typist sometimes confuses "0" with "O" and ":" with ";" and " ". This introduced bugs on its own. Line 150 (again) shows all mistakes at once.
  • Error handling is a mess: if you enter the wrong input, you are simply asked to enter it again. No notification of any kind that you did something wrong.
  • The logic itself is very convoluted. GOTOs everywhere. Line 440 is particularly bad, and could be easily improved.
  • Some of the syntax may be valid, but it was definitely not valid in my version of Basic. And seeing how my interpreter came included with the book, I feel justified in not taking the blame for that one.

And so I set out to get this to run once and for all. The following listing shows what a short rewrite looks like:

:::basic
LET DISTANCE=365000
LET BARRELS=100
LET MASS=1000
LET TIME=60
LET A0=0
LET VO0=0
LET V0=0
LET EO0=0
LET E=0
LET F=0
LET THROWS=0
DO WHILE BARRELS>0 AND E<=364900 AND THROWS <= 30 
    LET REMAINING=DISTANCE-E
    PRINT "DISTANCE SO FAR="; E
    PRINT "DISTANCE TO GO="; REMAINING
    PRINT "SPEED"; V
    PRINT "BARRELS LEFT="; BARRELS
    PRINT "THROWS LEFT(MAX 30)="; THROWS
    PRINT "-----"
    INPUT "NUMBER OF BARRELS?"; NUMBER
    INPUT "DO YOU WANT TO BRAKE (Y/N)"; RESP$
    IF NUMBER>BARRELS THEN
        PRINT "NOT ENOUGH BARRELS!"
    ELSEIF RESP$ <> "Y" AND RESP$ <> "N" THEN
        PRINT "INVALID INPUT!"
    ELSE        
        LET THROWS=THROWS+1
        LET BARRELS=BARRELS-NUMBER
        IF RESP$="N" THEN
            LET F=(F+NUMBER*1000)*0.5
        ELSE
            LET F=(F-NUMBER*1000)*0.5
        END IF
        LET A=F/MASS
        LET V=VO+A*TIME
        LET E=EO+VO*TIME+0.5*A*TIME*TIME
        LET EO=E
        LET VO=V
    END IF
LOOP
IF BARRELS <= 0 THEN PRINT "MISSION FAILED - NOT ENOUGH FUEL"
IF THROWS > 30 THEN PRINT "MISSION FAILED - NOT ENOUGH OXYGEN"
IF E>364900 THEN
    IF V<5 THEN
        PRINT "MISSION ACCOMPLISHED. ROCKET LANDED ON THE MOON."
    ELSE
        PRINT "MISSION FAILED. ROCKET CRASHED AGAINST THE MOON SURFACE."
    END IF
END IF

I think this version is much better for beginners. The code now runs in a loop with three clearly-defined stages (showing information, input validation, and game status update), making it easier to reason about it. And now that the GOTOs are gone, so are the line numbers. However, and in order to keep that old-time charm, I kept all strings in uppercase and added no comments whatsoever.

I also added some input validation: the BASIC interpreter I'm using (Bywater Basic) will still crash if you enter a letter when a number is expected, but that's outside what I can fix. At least you now get a message when you use too many barrels and/or you choose other than "Y" or "N".

It is only fair to point out something that I do like about the original code: that the variable names are descriptive, and in particular that the physics equations use the proper terms. If you are familiar with the physics involved here, those equations will jump at you immediately.

If I had time, I would still tie a couple loose ends in my version. A proper rewrite would ensure that the new code behaves exactly like the old one, bugs and all. And there's a good chance that I have introduced some new bugs too, given that I barely tested it. I also feel like making a graphical version, using the original artwork and adding some simple animations on top.

But even then, I finally feel vindicated knowing that younger me had no chance of making this work. Even better: the next exercise, a car race game, just gave you a couple pointers on how to draw something on the screen, and then left you on your own. That one would take me some time today.

Next on my list: finally read the source code of Gorilla.bas. I know I tried really hard to understand it when I was 10, so maybe I should get closure for that one too.

A neural network in Javascript

A couple days ago I found a very interesting article, titled A neural network in 11 lines of Python. I always wanted to get a visualization of how a neural network works, so I took this as my opportunity. Taking that article as a base, I created a nice visualization of the simple case, and it ended up looking very nice.

This post is a small version of that. I'm going to show you how a neural network does its magic, using the magic of Javascript and SVG graphics.

InputsOutput
0010
1110
1011
0111

This is the function we'll learn. Implementing XOR is pretty much the "Hello, World" of neural networks, so we'll be doing the same here.

Also, note that the third input column is all 1's. This will be our bias unit (i.e., a column that always equals 1).

Now, let's plug this into our network.


This is a graphical representation of our neural network. The weights have been randomly initialized (you can check that by reloading the page). Neurons 0-2 are input, neurons 3-4 are the hidden layer, and neuron 5 is output. Given that we have 4 training examples, we'll follow each training example individually.

The computation should proceed as follows: for neuron 3, we'll first multiply neurons 0-2 by the value of the edge that connects both neurons, sum those three values, and apply the sigmoid function to the result. In formal terms, $$n_3 = sigmoid(n_0 w_{0,3} + n_1 w_{1,3} + n_2 w_{2,3})$$ where ni is the i-th neuron, and wi,j is the weight that connects the neuron wi with the neuron nj.
The sigmoid function guarantees that the value for neuron 3 will be a value between 0 and 1. We repeat the same process for neurons 4 and 5.


So here we can see what our network is actually computing. If you have not yet read the article to the end, there's a very good chance that our network is returning random garbage, and that's fine - we haven't trained it yet, so of course the output makes no sense. This is called the forward step, in which I test my network and see what it's being computed.
For the second step, backpropagation, we'll need to write a couple tables, and see how bad our results are.


Output
(expected)
Output
(network)
Error
0000
01-10
1100
1010

Here is an interesting fact. We will call the difference between the value I expected and the one I actually got the "error" of the network. Similarly, sig(x) will represent the sigmoid function, and sig'(x) will be its derivative. Having defined that, the following equation $$error*sig'(output)$$ tells me how much should I correct my weights, and in which direction (whether they should be bigger or smaller). I won't delve in the math for that now, but if you need more details there are some links at the end that can help you.

So we have now applied our corrections to the green weights, but how about the red and blue ones? We'll also correct those by applying a variation of the same principle: once I corrected the value for the output, I have to distribute the amount of error into every weight that contributed to its computation. This will allow me to correct the values for neurons 3 and 4, which I'll finally use to correct the values for the remaining weights.
This process is called backpropagation, because I'm analyzing the network backwards to correct the errors I made when computing forwards.

Now all that remains for the training process is for me to repeat these steps over and over, until the er ror (shown underneath) is small enough.

Error
0
0
1
1

You can click any of the buttons here. One of them will perform one step of the calculation (both forward and backpropagation), while the other ones will perform one hundred and one thousand steps respectively. Using this, you can verify that the network eventually learns how to perform XOR, and then it stabilizes. Reloading the page will start all over again, but with different random weights for the network.

This is a very simple neural network (although not the simplest), implemented in Javascript. I've skipped some details in order to make the whole process simpler - If you want something slightly more challenging, I definitely suggest you to read the original article, which goes into the right level of detail.

I still want to improve on this, but I'm not entirely sure how. I think it would be nice to see how some neurons are given more (or less) weight, but I'm not sure how this should look like. If you have any ideas, feel free to tweet me.

Note: If you are quick enough, you might have noticed that the bias unit is missing in the hidden layer. The short version is: yes, it is. I only noticed once it was too late. I'll try and fix it in future revisions of this article.

« Page 2 / 2