Category Archives: Uncategorized

List Of Programming Project Ideas.

The best way to learn to program is to work on projects, so here’s some ideas for projects for beginners, intermediate, and advanced programmers. Remember: it doesn’t matter whether or not you finish these projects. What matters is what you learn along the way. If you have any ideas for things to add to this list you can email me at noahmartinwilliams@gmail.com with the subject “programming project ideas”.

Assembly:

  • A program that exits with return status 0
  • A program that prints “hello, world”

C:

  • A Linux kernel driver for a USB button.
  • A C standard library that has memory allocation using the buddy algorithm.
  • An arduino program that blinks an LED.
  • An arduino program which turns on a motor which closes or opens a window based on the temperature.

Golang:

  • A library that parses xml concurrently.
  • A Simple web server that serves up one html page.
  • A web server that serves up all files in the current directory.
  • A concurrent pipeline that reads in MNIST samples and uses image magicke to turn them into files, and maybe apply some optional filters.
  • A concurrent system that runs dijkstra’s algorithm.
  • A web server that uses youtube-dl to download youtube videos automatically, save them, and play them back to whoever owns the server.
  • A program that uses concurrency, and image magicke to automagically fix the gamma settings for a huge number of image files in parallel.
  • A reddit scraper.

Prolog:

  • A script that helps you pick out parts for a PC.
  • A simple package manager using an sqlite library.
  • A script that lets you access firefox web history and use readln to issue queries about it.
  • A script that acts as a pharmacist.

Haskell:

  • A program that takes an integer and tells you if the integer is prime using a parallelized brute force method.
  • A password cracker that uses the Control.Parallel.Strategies library.
  • A program that takes in an adjacency list as a CSV file and spits out an adjacency matrix.
  • A program that runs K-means image segmentation on it’s input using the accelerate library for GPU acceleration.
  • A neural network library that uses dependent types, and the accelerate library.
  • A program that can lazily generate all possible tweets.

Bash:

  • An rsync wrapper that backs up your files using snapshot backups.
  • A program that finds duplicate files in a directory and makes them the same file using hard links so as to save space.
  • A script that grabs a random line from a given file.
  • A script that renames every file to include the date and time it was modified in the file name.

Lex and Yacc:

  • An XML parser.
  • A C compiler.
  • A programming language that has all the features you wish other programming languages had.
  • A parser for the wavefront obj file format.

Erlang:

  • A simple web forum using the yaws program.
  • A gopher server.
  • A bank website.
  • A server that can mine crypto.
  • A server that can serve up videos.
  • A Debian package server.

Python:

  • An XKCD comic downloader.
  • A script that uses AI to draw googly eyes on images.

Octave/Matlab:

  • A script that uses rotation, scaling, and translation matrices to trilaterate the position of a thing given it’s distances to four given points in 3D space.
  • A neural network script.

Pytorch:

  • A script that can read a text file and summarize it using transformers.

Projects where you’ll have to decide on your own what language to use:

  • A program that reads in a wavefront obj file and displays it in a window, and the user can rotate the model around to see it from different angles.
  • A twitter client that uses ncurses.
  • A quick script or program that can generate the sound of what hydrogen should theoretically sound like when excited.
  • A remote controlled differential drive robot (note: this will require some knowledge of electrical engineering).

How To Install Linux

In the last post I listed a series of websites for the different various Linux distros. If you’ve never used Linux before and want to use it then I’d recommend Linux Mint because it’s made for beginners. Unfortunately installing Linux is both easy and hard.

It’s easy if you have some technical skills and it’s almost effortless if you’ve installed Linux before, but it’s not possible to list out what buttons to press, because each computer model has a slightly different way of installing Linux.

There’s simply no way to write a single article detailing how to deal with every possible thing that might come up purely because there are too many different models of computers out there. The steps tend to be nearly identical for each one, but it will take some technical skills to do this.

Also it’s possible to screw things up in such a way that you can’t boot up your computer, but Linux Mint tries to make it harder to do that.

You may want to do this on an old laptop that doesn’t contain any files that you care about.

In order to install Linux you’ll need to download an ISO file from the website for whichever one you choose.

The next step is to download and install this free software program: https://rufus.ie/en_US/

Then plug in a USB stick into your computer. All the files will be wiped from this USB stick, so make sure it doesn’t contain anything important.

If you want to use Linux alongside Windows then you should also defragment your hard drive, and if you’re low on disk space then you may want to back up and/or delete any large unwanted files from your computer.

Next use Rufus to burn the ISO image to the USB stick.

Next reboot your computer with the USB stick still in. If you’re on a laptop then make sure that your computer is fully charged and plugged in. If the power goes out during the installation process then it might break Windows and/or Linux.

Now comes the hardest part. It used to be as simple as simple as rebooting with the USB stick in your computer for every computer, but computer companies changed the default settings to boot to Windows instead.

If your computer doesn’t automatically boot to Linux then reboot again, and press F12 and then select the USB stick to boot from. Some computers may require you to press F2 and go into some settings to tell it to boot from USB, others might have you press some other button.

Most computers will flash the logo of the company that made the computer at boot up and have a message saying which button to press to go into settings or which one to press to bring up a menu of options for things to boot from. You want it to boot from the USB drive, and not the internal hard drive.

Once you’re in these settings you can’t use the mouse. You’ll need to move around with only the keyboard. You might want to disable quick boot, and secure boot, and you might want to change the boot priority so that USB devices are booted to first.

Once you’ve booted up to Linux most distros (including Linux Mint) will have an interactive prompt that will guide you through how to install it.

If you want to keep Windows alongside Linux then that’s called “dual booting”, and you’ll need to tell Linux to do that at some point in the installation process. Many distros will by default erase Windows and install over it, so you’ll need to keep an eye open for when it asks you how to install it.

Once you’ve done that you should check out this free pdf book: http://linuxclass.heinz.cmu.edu/doc/tlcl.pdf which will teach you how to use it better.

What is Linux?

In the previous post I talked about vendor lock-in. Computers are taking over more and more of our daily lives, and this trend of computers controlling more of the world is not likely to come to a stop any time soon.

Soon enough cybernetics might start to become a reality. We may someday soon be able to upgrade ourselves as we can upgrade our machines.
In such a world vendor lock-in would possibly mean slavery towards a corporation. We can’t allow ourselves to be chained to the likes of Microsoft.
We can’t allow our society to remain locked in to the security disaster that Windows so fundamentally is.

At some point you have to ask yourself:
Do you want to be free?

Do you want to take back control? If so then Linux is for you.
Linux is an alternative to Windows and Mac. It’s the official unofficial third option that nobody talks about.
Linux is different from Mac and Windows not just because it’s a different product, but because it’s built in a different way.

Linux wasn’t written by a single corporation. Linux was written by many different organizations and individuals from all around the world.
Anyone can contribute code to the Linux kernel to add new features or fix bugs in it, and countless people already have.

If you don’t trust corporations then Linux is for you.

Linux is designed to be customizable. While other inferior operating systems let you change the background, Linux lets you decide whether or not there even is a background, or if there’s just a command line.
With Linux you can change nearly anything about the system. You can change the desktop to have any kind of theme. You can tell it whether or not to update automatically, whether or not
it should have one clipboard or many, whether or not all your files should be encrypted, and even whether or not it can run Windows programs.

If you want customizability then Linux is for you.

Linux respects your privacy. The kernel can’t contain code that spies on you because anyone who would add such code is legally required to make the instructions to it publicly available, and everyone
would be able to see the code that spies on you and anyone could make a fork of the project that doesn’t spy on you.

If you want privacy then Linux is for you.

Unlike Windows, Linux is designed with security in mind. Whenever a security hole is discovered it is quickly patched up, and an update is released that makes the system more secure for everyone.

Microsoft Windows has security holes in it that everyone has known about for decades which Microsoft has done nothing to fix. With Linux people from all around the world are able to inspect the code and find any security holes, and then file a bug report which quickly gets handled, or even fix it themselves and send the security patch
to the Linux foundation.

If you want security then Linux is for you.

Linux isn’t just one product. There are many variations of Linux that you can choose from. You can go with Linux Mint if you want something that’s simple, Gentoo Linux if you want something that’s really advanced,
Debian Linux if you want something that’s stable, Arch Linux if you want something that’s on the cutting edge, Red Hat Linux if you want something for corporate needs, or any number of other options.
Each of them is a variation on the same thing, and each of them is compatible with each other while still offering variety.

If you want choices then Linux is for you.

Linux has been optimized over decades by talented people from all around the world so that it can run on anything and everything in a way that’s fast, and efficient.
Linux is capable of running on everything from the tiny computer chip in your microwave oven all the way up to the super computers that google uses for their search engine.
From digital wrist watches to servers to super computers, from micro chips to self driving cars, from laptops to airplane autopilots, Linux runs them all behind the scenes and keeps the digital
world safe and secure.

If you want speed and efficiency then Linux is for you.

And now, with help from Valve Software, Linux is gaining the ability to run an increasingly large number of video games. Someday soon Linux may be the definitive choice for video games.
The truth is that Linux is for everyone.

If you want to be free, then Linux is for you.

Hatsune Miku Is A Scam.

“If you can’t explain it to a six year old then you don’t really understand it.”

-Albert Einstein

Hatsune Miku is a scam. Here’s how the scam works.
Let’s start off with what we know:

First: a computer program is just a series of instructions that a computer follows.
It’s basically just commands that tell the computer what to do.

Second: a file is just a bunch of ones and zeros that is meant to
represent information.

Let’s take a look at some real world examples of this in action:
Imagine that you own a small business. As a business owner you have a lot of documents you need to keep. It doesn’t matter what kind of business you are, you need to keep records of things.

So let’s imagine that you chose to use Microsoft Word to write those documents. Microsoft word is a computer program. It’s just a set of instructions that the machine follows. When you save your document that program follows instructions that tells it how to turn the text you’ve entered into the ones and zeros that go into a file.

When you open that file with word later on there’s another section of the instructions in Word that tells it how to translate the ones and zeros from the file into the document you see on your screen. Those instructions that make up the program are proprietary. You aren’t allowed to know what those instructions are.

That’s just how it’s licensed. As a result nobody knows how to translate word files into documents except Microsoft. So if you’ve got hundreds or thousands of documents in Word then you can’t go through and open each of them up and copy and paste the text into another word editor. That’s just not practical.


You need a word editor that can be compatible with Microsoft word documents, but Microsoft tried to make that impossible by keeping the code for processing word documents a secret.

This is the main strategy of Microsoft. It’s called vendor lock-in. Vendor lock-in is when the vendor, in this example Microsoft, sells you a product that you become artificially reliant on, which means you’re
locked in to them. This is very common in the software world. Nearly every proprietary program you’ve ever used does this. It’s gotten so bad that many people reading this article might be thinking:
“So what if you can’t open word documents in anything but Microsoft Word? It’s a word document. It’s only reasonable that you can’t open it with anything else.” But that’s not how things have to be.
The point of vendor lock-in is to make it so that the vendor is not held very accountable to their customers.

That’s what vocaloid does. It’s designed so that you can’t open up vocaloid project files with anything other than vocaloid.

There is another way. There’s free software.

When people speak of free software, they’re referring to freedom, not price.

Free software is software that is licensed in such a way that you are legally allowed, and even encouraged to look at the

instructions that make up that free computer program. Companies that write and distribute free software are held more accountable to their customers because if their customers find a bug in the product,
or want a new feature added they can send in a bug report and/or feature request, or they can hire a programmer to fix that bug and/or add that feature. To prevent the customer from switching over to the modified
product the people who wrote the software have to care about their users.

How you make money off of free software when anyone can legally modify it, and give it away for free is really another story for another time, but there are ways for programmers to get payed while still being held more accountable to their users.

They often don’t get payed as much, but that’s because it’s hard to compete with vendor lock-in. Free software projects tend to be underfunded, but it doesn’t
have to be that way. If there was a demand for vocaloid to be free software then it might become even more popular than it currently is.

It breaks my heart when I see people saying things like “Oh, Vocaloid is so great”
“Oh, it changed my life.”
“Oh, I’m crying every time I watch a vocaloid concert.”
“Oh, I wish Miku were real and Noah wasn’t.”

It’s okay to love an idea but not condone a dishonest business practice, because this is a corporation. They don’t care about anything other than profits. This whole community looks like a bunch of Apple fanboys if Apple fanboys were an actual cult. It’s a product that is created and controlled by a single corporation, but when a thing becomes free software it becomes something more than that. It becomes a thing that is owned and controlled by multiple corporations and a community. It becomes something that can be permanently embedded into the digital world.

The future is free.

What is functional programming?

What is functional programming? In a nutshell, functional programming is programming where we minimize the percentage of functions in our code that have side effects. What is a side effect? A side effect is either accessing random numbers, or accessing a global variable, or doing any kind of I/O.

So why is there a word for this? Well because functional functions are purely deterministic. You can call them up with a set of arguments, get a return value, wait a while, and then call them up with the same set of arguments and be guaranteed to get the same return value. This, as it turns out, is a powerful assumption to be able to make about a function.

If it accesses random numbers then it’s not deterministic. If it takes input then it might return a different result when something giving it that input changes. If it’s doing output then that output operation might fail. If it accesses a global variable then the global variable might have changed since the last time the function was called.

To put it plainly a functional function does not rely on it’s environment. It’s just a subroutine that only takes in arguments, does a calculation, and returns an answer. A functional function just does a computation.

So some of the advantages of it are that functional functions are easier to use. They tend to line up with how we tend to naturally write software. More on that later. There’s less internal state to think about. You don’t need to get a whole environment set up just to call the function. You can just pass the environment to it as an argument.

It’s more consistent so bugs are more reproducible. There’s no need to worry about race conditions. This means it’s easier to debug, and therefore more stable and more secure. It’s inherently thread safe. It’s faster because it makes no system calls. It has less error checking to deal with. It’s more portable because it doesn’t rely as heavily on system specific system calls. It’s also easier to copy and paste the code into a shared library if the project gets too big.

To put it plainly, maximizing the amount of your code that’s functional has nothing but advantages to it. How often in life do we come across something that has nothing but advantages?

If we’re writing a hypothetical project, like for example an image library then don’t write your code like this:

Img getImage(string filename);


Where you write a function that takes a file name as an argument, reads that file, and then returns an image object. This means that the file can only come from the disk, and can’t be directly taken from a network connection.
Instead write your code like this:

Img getImage(byte[] fileContents);
Img getImage(channel byte[] fileContents);

where it takes in either the entire contents of the file as an argument or some kind of channel that spews out the contents of the file one block of data at a time.

Don’t write your blur method like this:

class Img {
        void blur()
        {
                // blur this instance of the image.
        }
}

where you write the method to blur that instance of the image object. Odds are that your user will want to keep the original.
Instead write it like this:

class Img {
        Img blur()
        {
                // code
                return copyOfImageButBlurred;
        }
}

where we return a copy of the image that’s exactly the same except blurred. That’s not as efficient with memory, but we don’t have to be efficient with memory now.

If you’re writing an autopilot then don’t write your code like this:

int main()
{
        // get sensor data
        // react to input
        // get more sensor data
        // react to input some more
}

where we do random stuff in whatever order we feel like.
Instead add some organization to your code by writing it like this:

int main()
{
        state := initializeState();
        while(1) {
                input := getSensorInput();
                state, commands := processInputFunctionally(state, input);
                runCommands(commands);
        }
}

where we initialize the state, and then in a loop we gather sensor data, put that, and the state information into a big function with no side effects, and it will return the new state, and commands for what to do and then we execute those commands. This way the code is more modular. The main code for the autopilot can be cleanly removed and hooked into a simulator for testing.

But there’s more to it than that. Functional programming can be taken up a notch with functional programming languages. There are programming languages specifically designed to be functional.

Let’s look at the first one: Lisp. Lisp is a functional scripting language. In lisp variables are immutable. What does that mean? Remember earlier when I told you to write the blur function so it returns a blurred copy of the image? There’s a reason for that. As it turns out, statistically, most variables are set once and then never written to again. Those variables that are written to again tend to be written to in a loop.

As it turns out you can replace loops with recursion and then do away with having to modify the variable more than once and still be Turing complete.
This way people who read your code can assume that any variable will only be set once. This makes it easier to reason about what the code is doing.

If we’re going to create a language where functions will be called up frequently then we need a new syntax that makes calling functions easier.
And here’s what that looks like.

(sqrt (add (square a) (square b)))

As you can see there’s no need for commas. All arguments are separated by spaces, and the function name goes inside the parentheses.

While that’s certainly nice Lisp lacks an important feature: declarative programming. If we’re going to be writing lots of recursive functions then we need to make that easy to do. Most recursive functions will have some kind of if statement that checks the arguments so it knows when to stop. So why not add some special syntax to do exactly that?

factorial :: Int -> Int
factorial 0 = 1
factorial x = x * (factorial (x - 1))

This is what haskell code looks like. What we do is we declare multiple versions of the function, each of which has its own patterns to the arguments that it’s expecting. Then when we call the function it will try out one pattern after another until it finds one that fits and then it will run the associated version of the function. If you want to write a function that takes the factorial of something you can do that in just three lines of code in haskell.

This is known as declarative programming. In declarative programming we give the computer a set of declarations, and the pose it a query and it uses those declarations to figure out the answer to that query.

We can use pattern matching and declarative programming for more than that. Prolog is a scripting language based on predicate logic. In predicate logic we take the set of everything in the entire universe and use functions that return true or false, known as predicates, to filter out anything that’s not an answer until we get the set of all answers, and we can do so declaritively.

Here’s what that looks like.

is_smart(noah).
is_smart(nate).
is_smart(bob).

We can issue a query to this code through an interactive prompt that will list everyone who is smart. We can also create predicates that use other predicates to filter out invalid answers.

is_smart(noah).
is_smart(nate).
is_smart(bob).
has_computer(noah).
has_computer(nate).
is_programmer(X):- is_smart(X), has_computer(X).

The way this works is through backtracking. Here is a page that explains how that works internally: http://www.amzi.com/articles/prolog_under_the_hood.htm

Prolog has another feature: atoms. An atom is like a string except that it’s, ideally, immutable. Atoms are used as messages that get sent to functions. A lot of large programming projects send information around as strings, so why not make that easier and more efficient? That’s what prolog does. Any identifier that’s not a predicate and that does not start with an uppercase letter is assumed to be an atom.

Atoms show up in other languages as well, like for example erlang.
Erlang is a programming language that was intended to be used for distributed computing systems. It’s functional, concurrent, declarative, and part of it’s declarative nature means it can use atoms to match patterns against incoming messages.

Here we see something like that:

process_http(...) ->
        receive
                {get, ...} ->
                        // foo
                {post, ...} ->
                        // bar
        end.


This erlang function, when it reaches this chunk of code, will check it’s incoming channel for messages, and it will execute code foo if the message is a tuple that starts with the atom ‘get’, and it will execute code bar if it receives a tuple that begins with the atom ‘post’.

Erlang is specifically designed to be THE solution for distributed computing systems. It’s got almost everything you could want, except for buffering.
Erlang channels are unbuffered. It’s very easy to accidentally slurp up a huge file into memory that is too large to fit in memory on the computer that the erlang routine is running on. Unlike in golang where all channels are buffered so as to protect against running out of memory, erlang coroutines can run out of memory when loading a large file.

So how do we solve this problem? Earlier I suggested that we should write functions that load up images by taking the entire contents of the image file as an argument. What if the image is too big to fit into memory?

This is where lazy evaluation comes in. Lazy evaluation allows us to build infinitely large data structures. Lazy expressions are only executed when they’re needed. The way that works is that a function which is pure can be executed later instead of right now because it will return the same result either way.


Haskell is a lazy language. Every expression in Haskell is lazily executed. This enables us to write programs that will naturally process input as much as possible while still reading it. It’s not possible to tell when a chunk of code will be run in a lazy language, but we don’t have to care because it will give us the same result in the end anyways.

fib :: Int -> Int -> [Int]
fib a b = b : (fib (b + a) a)

The above code will return the entire Fibonacci sequence in a list. It returns a cell containing the first argument as the head, and the tail is a data structure which contains a function pointer to fib and the list of arguments.

But what if we have an error lazily loading the image? This is where monads come in. A monad is a thing that we can use to check for errors, and also use it for global variables. Here’s the idea: in C if we have a function that does IO then that IO might fail, so we need to be able to return an error indicator, but the function calling THAT function also does IO because something it called does IO.

Ultimately what we tend to do in real life is either handle the errors if we can, or, more often, just throw the error up one until it reaches the top so the user can deal with the problem. That’s exactly what a monad does. A function which uses a monad in Haskell either returns a successful value or throws something up with an error value.

getImage :: Monad m => ByteString -> m Img
getImage [] = fail "Error: empty file"
getImage fileContents = do
    -- code
    return img
main :: IO ()
main = do
    c <- openFile "file.png"
    i <- getImage c
    foo
    bar

You can also chain together monad functions so that if any step in the process fails then it will just stop right there. You can also use them to chain together functions that access global variables.

I hope that you’ll try out some of the ideas I’ve presented here. No idea should go unchallenged forever, and I think the idea of “truly object oriented” needs to be challenged now. Unlike the vaguely defined idea of truly object oriented, functional programming has a precise definition. With functional programming you can apply this idea to your existing code bit by bit and see some immediate improvements.

It can be slightly hard to get into the habit of doing things in a functional way, but it’s well worth it.

The future is functional.

Lojban

I’ve recently found out about an interesting language called “Lojban”. It’s designed to be a language that can be spoken both by humans and computers. Here‘s the website for it.