&Chr

It's the Segmentation's Fault

[chronaldragon]

sd_markdown: A single-header markdown library for C

I've just released a single-header consolidation of the previously-popular markdown library called Sundown. Download it here.

Why?

Because I can.

No really, why

Because single-header libraries are a lot easier to deal with -- you don't need to add anything at all to your build system, just #include and go. This means they work pretty much everywhere, without any hassle.

Also, I needed a markdown parser, and Sundown was already close to being as simple as I wanted, so I just took it the rest of the way.

How do I use it

Just grab sd_markdown.h from the repo, dump it in your src folder, and add an #include "sd_markdown.h". You'll also need to #define SD_IMPLEMENTATION to get the actual function definitions, which is a precaution for projects that might include it from multiple translation units.

Then check the top of the header file for instructions on how to call it. It's pretty easy, the main API is just 3 or 4 functions.

But Sundown is deprecated!

Yeah, well the stuff they replaced it with made it all more complicated. So I stuck with the slightly older library in favor of simplicity. It passes approximately 50% of CommonMark's conformance tests, which is good enough for my purposes. If there's a lot of interest, I may attempt to port over some changes from more recent forks by other people, but otherwise it will stay based on the last version of Sundown.

I found a bug/issue/complaint

File it in our complaints department over at twitter or make a pull request with the issue on the repo.

That's all for now. Happy coding!

[chronaldragon]

My vimrc, with some Notes

There comes a time in every huge nerd professional programmer's life when they decide their .vimrc is cool enough to share with literally everyone they know, with much pointing and gesturing, as a token of how badass they are. Man, programmers are annoying sometimes.

On an unrelated note, I thought I'd quickly write up something about my .vimrc, since I get people asking about it from time to time, and I know how hard it is to dig up info about this stuff (considering I had to do it in order to figure out any of it in the first place). So without further ado.

First off, you can download a relatively recent version of my .vimrc and associated files from the github repo I helpfully set up. It wants to go in the folder with all your vim files, such that "vimrc", "linux.vim" and "windows.vim" live somewhere like "~/.vim/vimrc", "~/.vim/linux.vim", and/or "%USERPROFILE%/vimfiles/windows.vim". But you probably know the drill.

Building stuff

Use Alt-B to build. This shortcut invokes :make, followed by :copen. In case you weren't aware, vim has a built in build-handling system. :make runs whatever program is defined in the variable makeprg, and captures the output. You can then access the results of the build in a special buffer called the Quickfix List with :copen, which has good syntax highlighting for most builds and allows you to jump to your errors by hitting "enter" or double clicking (in gvim) on the error. You can also use :cnext and :cprev if you don't want to do that manually, but I never bound those so I often forget they exist. Finally, when you're done with the build/read/fix loop, you can close it with :cclose, which I've bound as one of three things that Esc does. (Along with :noh, to cancel a search, and of course passing through an actual to do the normal thing)

You can :set makeprg= to whatever you use to build stuff. I always keep a build.bat in the root directory of my projects, so I set my makeprg to simply build.bat. I also always either start vim from the project root, or cd there after I start it. This can be a little inconvenient, e.g. if your code is a few directories deep in src/actualsrc/norlysrc or something, in which case I recommend a .localrc for your project (loaded by the plugin called 'localrc.vim', automatically I think).

Random new shortcuts

Here are the keys I bound in addition to vim's normal bindings:

Alt B: Do build

Esc: Close quickfix list / cancel search / do normal things

Alt ←: Previous buffer

Alt →: Next buffer

Alt D: Paste a timestamp into current buffer (needed this once and haven't used it since :D)

Alt S: Remove space at end of lines (my university is picky about this)

Swap / temporary files (IMPORTANT)

I set swapfiles/undofiles/backups to all save to /tmp on Linux (which is fine) and C:/dev/temp on Windows (which is probably not fine for anyone but me). So if you're on Windows, you'll want to change that (check "windows.vim"). I don't like these files cluttering up my project directories.

Important Political Issues

I use 4-space spacey tabs. I used to use hard tabs, but then I discovered they display consistently pretty much nowhere, and make for weird mixes if you need unaligned tabbing (to make function params on new lines line up, for example), and kill kittens, and were responsible for 9/11, so I switched to spaces. It's better this way.

Oh, and I have the default clipboard set to use the system (unnamed) clipboard.

Plugins

I currently use the following plugins:

Vundle.vim: Plugin management

localrc.vim: Project-specific vimrc files

vim-auto-save: AUTO SAVE (every editor should have this by default for god's sake its 2016)

jai.vim: Nobody actually writes jai yet except Jon, but uh...it makes his demo examples pretty?

vim-glsl: GLSL syntax highlighting (I also have some autocmd set up to set the filetype properly on a few different file extensions)

ebnf.vim: EBNF syntax highlighting, for when you're writing new grammars in Vim. (I've done this twice now).

Color scheme

I use a custom color scheme that I call Dragonfire. It's dark and warmly colored, and some of the colors can be a bit shockingly orange. There's also not a proper light version. Sorry. It can be difficult to read in bad lighting situations (like being in a bright room with a glossy screen, grr) which is a problem I'm aware of and am too lazy to fix. So uh, yeah. Keep that in mind.

In case you missed it before, here's the download link:

Download

Well, that's just about everything. IF you have any comments, let me know on twitter, where I'm @ChronalDragon or via email at the address listed on the bottom of the page. Cheers.

[chronaldragon]

Building WeeChat on Windows in Cygwin

IRC is a fairly old protocol at this point, and while I can't say its aged well (its aged sort of like one of those types of cheese that gets a bunch of mold in it and for some reason people were like "yes, let's eat this and pretend it tastes good!"), it at least has a fairly strong set of clients that have matured a bit better than the protocol itself.

The best one I've used so far is WeeChat, which unfortunately does not itself provide a binary on Windows. So I've only been able to enjoy it on Linux, until recently -- I decided to dig down into the build process, seeing as it purports to build properly in cygwin, and try to get it up on my Windows machine.

(I discovered while writing this post that Weechat 1.3 is available as a package in Cygwin. I decided to post this anyway, as it might be helpful to those who want WeeChat 1.4 and who are building other things in cygwin on Windows).

Note: If you've got cygwin, you can just install the weechat package and move on with your life, if you don't care about getting version 1.4. Otherwise, if know how to extract sources, you can skip right to Step 6 with a brief stopover in Step 3 to check that you've got all the packages you need.

I'm starting with a clean Windows 7 VM, so that I can be sure to include all the prerequisites here. Some of the packages may already be installed,

Alright, let's get started.

Step 1: Getting cygwin

Start by downloading cygwin. Make sure you get the right build (32-bit or 64-bit) -- if you're on a relatively recent machine, chances are you'll want 64-bit. Note: Make sure you take note of where this installer downloads to, as you may need to run it again if you find out you missed a package.

Step 2: Running the cygwin installer

Run the cygwin installer. You'll likely want to choose "Install from Internet" and install to the default directory (C:\cygwin64), for All Users.

The Local Package directory doesn't matter -- I put them in my Downloads folder because that seemed the most sensical.

Your knowledge of your proxy settings is your own -- if you don't know, it's probably just Direct Connection.

The particular site you download from doesn't really matter -- I always choose one of the .edu domains, since I live in America and that's the easiest way to ensure the server will be fairly close by without individually checking where the DNS resolves. If you don't live in America, there are some other country-specific mirrors down the list.

At this point, the package list will download, and then you'll be dropped into one of the more confusing interfaces I've ever seen. I think this deserves its own step.

Step 3: Choosing packages

This is where, if you don't want to bother building WeeChat yourself, you would select the weechat package in cygwin, install it, and close the post. For those intrepid souls who wish to build it themselves, continue on....

By default, cygwin installs a small set of packages that gives you a basic unix-like command line environment. Unfortunately, this is not enough to build anything! We'll also need to get some libraries that WeeChat needs specifically. Which ones are needed will depend on whether you want TLS support, but I'll assume for the moment that you do.

Go ahead and tell the installer to install the following packages if it isn't planning to already already (Not absolutely sure this is the minimal set, but if you get these, you won't go wrong):

Devel:

automake (The one without a specific version number)

autoconf

cmake

gcc-core

gcc-g++

gettext-devel

make

pkg-config

Libs:

libcurl-devel

libiconv-devel

libgcrypt-devel

libgnutls-devel

libncurses-devel

libtool

It will ask if it should download the dependencies of the above packages. You definitely want to do that. The option is selected by default, so just hit Next.

Sit back and relax, because the install will take a while (5-20 minutes to download, depending on connection speed, plus another 5 or so to install).

Hopefully that goes off without a hitch. If so, you're ready to proceed...

Step 4: Downloading the WeeChat source

This one's easy. Just go here and click one of the downloads under "Download Sources".

You will, however, need to extract the .tar.gz or .tar.bz2 file that it comes in. Windows has apparently locked itself into .zip compression and doesn't have anything built in to extract these. Luckily, we just installed a set of linux tools!

Step 4.5: Intro to Cygwin

Open your newly minted Cygwin terminal. It's worth digressing for a moment here to explain the basics of how cygwin works.

Inside the cygwin terminal (and cygwin applications), you're in a virtual file system that looks, to any casual observer, like a linux file system. It starts at /, has all the usual /var, /bin, /dev folders and so on, with one important deviation: there's a /cygdrive folder as well, and this is how you access the actual disks windows knows about. Your C:\ drive will be /cygdrive/c for example.

Cygwin did not actually rewrite your hard disk, it's just pretending that the folder where it installed is the root of the filesystem. If you open Windows Explorer and browse to C:\cygwin64 (or wherever you installed it), you'll see var, bin, dev, and cygdrive folders right there. Inside cygdrive are symlinks to the root of whatever disks you have available.

The cygwin prompt starts you at your "home folder", which it calls /home/username. This is not the same folder as C:/Users/username. If you look in the cygwin directory, in home, you can see that its a regular folder and the only contents are the .rc and .profile files (known colloquially as dotfiles) it creates when you launch the terminal for the first time. If you want to get to your Windows user directory, you'll want /cygdrive/c/Users/username/. If you're clever with Windows command line and have admin access, you can probably link the cygwin folder to your user profile folder, but I won't cover that here.

Step 5: Extracting the WeeChat sources

Okay, now we've got the hang of cygwin, navigate in your cygwin prompt (if you're not sure how to do this, you might want to brush up on your command line skills before continuing) to the folder where you downloaded the weechat sources.

One of the core cygwin tools, luckily, is tar, so we are well equipped to extract the sources. I'm going to extract them in the same place, because it simplifies things and it doesn't particularly matter where you do the build. While I think it would be amusing to leave you to figure out the tar syntax, I'm not that cruel. Here's the command:

tar xf weechat-1.4.tar.gz

If you want to see each and every file as it extracts, you can make that xvf instead of xf.

Now, that should have extracted everything to a folder called Weechat-1.4 (or whichever version it's on when you read this). cd into it and we can start the build process

Step 6: Building WeeChat

Ha. Ha. Ha. You think WeeChat will only take 1 step to build? Foolish mortal.

WeeChat has two paths for building. The one they recommend uses cmake, and the other uses the whole mess of auto____ tools known as autotools. (At least the naming is logical). I was unable to get WeeChat to build with TLS support using cmake, so I will be guiding you through the more arcane autotools path. If you want to try the cmake route for yourself, the readme.asciidoc should tell you just about everything you need to know.

First, run ./autogen.sh. If all goes well, it should say it's running several rm -f operations to clean up, then stick on Running "autoreconf -fvi"... for a long time, then exit. If it doesn't, you have a problem. Check your cygwin packages.

Now, if the world was a pleasant place and software worked all the time, we'd just be able to run a couple more commands and everything would compile nicely. Unfortunately, this is not that world, and we're going to have to make a couple tweaks to build files in order to get all the way through. You can see what the issue is by running ./configure right now, but it takes a while to get to the problem area so I don't recommend it.

Step 7: "Fixing" configure

For whatever reason, the check that configure performs for the Enchant lib fails with a syntax error, so we need to disable it. This does unfortunately mean you won't get spell-checking in WeeChat. I haven't found another way around it, but if you want to experiment more in your own time, by all means.

Open configure in your text editor of choice (be sure it can handle unix line endings and fairly large files -- Notepad won't cut it). You'll need to comment out these three lines (around line 22815 in mine):

if test "x$enable_enchant" = "xyes" ; then PKG_CHECK_MODULES(ENCHANT, enchant, ac_found_enchant_lib="yes", ac_found_enchant_lib="no") fi

This will cause the found_enchant_lib check to fail and the rest of the section will be skipped as well.

Now you can run ./configure in the directory you extracted weechat to, and it should go fairly smoothly. After it finishes, skim the last pageful or so of output to make sure nothing errored out. If it did, check that you have all the libraries from Step 3. If nothing went wrong, you should see the following line at the bottom:

configure complete, now type 'make' to build WeeChat 1.4

Step 8: Running make

This one is fairly straightforward. Double check that ./configure produced a file called makefile, then run make. It'll take a while to build everything, so sit back and sip your drink of choice.

If we were using cmake, it'd have a nice percentage indicator on the left, but we have no such luxury. If someone has an idea about how to get TLS support built using the cmake path, I'd be happy to issue a revision to this post cutting its content down by about 50%.

It's harder to tell when make is done than when configure is, but you should hopefully see a bunch of make[x]: Leaving directory 'blah' statements at the bottom. If you see any errors, make sure configure ran okay and all the libraries are installed.

Step 9: Running make install

You'd think this would be the easiest step, seeing as everything is already built, but life is full of surprises. For some reason, several of the install commands refer to //usr/local/bin instead of /usr/local/bin. You wouldn't think that would be an issue, but you'd be wrong. Perhaps its a quirk of cygwin, but using // causes it to try to install to some read-only virtual file system somewhere, which make install will grumpily tell you if you try it. So we have to tweak some more.

Go into your editor again and open up the makefile in weechat-1.4/src/plugins/ (it's specifically this one that fails). Search for "prefix" and "exec_prefix" and edit both of them to be usr/local instead of /usr/local. I'm not certain both need to be edited, but there's no harm in doing so. Save the file, and now run make install. Everything should go smoothly, and like the previous make step, it's very hard to tell if it exits properly.

One easy way to tell: you run weechat and it works.

One last thing to do is make it so you can run weechat from your windows command prompt. Go to "System Properties" -> "Advanced" and click on "Environment Variables". Scroll down to "Path" in the System variables panel and edit it to include C:\cygwin64\usr\local\bin. You can test if this works by opening a new command prompt (not cygwin/bash) window and typing weechat.

Step 10: Enjoying WeeChat

There's lots to like about weechat, and there are tons of scripts available. I recommend you browse around in the /script menu in weechat, as there are plenty that add features that make weechat quite a bit nicer. 99% of things you find on the web about weechat should apply without modification to the Windows version, so don't hesitate to make use of your friendly neighborhood search engine.

If you have any question, comments, or suggestions about this post, you can contact me on twitter @chronaldragon or by email (see elsewhere on the site).

Happy coding!

[chronaldragon]

Seattle’s Best -- What the Heck Happened?

Short answer: I became Busy™.

Long answer: I finally became bored enough to go ask an advisor what my options are. Good thing I did, because I managed to get added to a higher level CS class, 351, which is called "The Hardware-Software Interface". As you can imagine, this was more what I was looking for. It also took up most of the time I'd been using to write blog posts!

CS351 was all about the hardware. There was some C, some x86 assembly, and lots of real-world information about ISAs and virtual memory and caching systems and so on. To give you a taste, here are the six "labs", aka homework assignments involving writing code:

0) Experimenting with C (modifying a source file to see what happens with out of bounds array accesses, pointer aliasing, structs, etc)

1) 14 different bit-manipulation puzzles. Constructing functions that operate on the bits of a twos-complement integer and do various things, like performing a logical shift (C's shift operator is arithmetic), inverting a subset of the bits, computing the result of the ! bang operator (without using it, of course), checking if an addition will overflow, and checking if a number is a power of two.

2) Defusing a "bomb" (executable) by disassembling it and determining what each "stage" of the bomb does (and the proper input file to "defuse" it)

3) Defusing a different bomb by using buffer-overflow exploits to jump to other functions or call maliciously constructed code

4) Determining the properties of (software) caches, by calling an access() function that emulates a hardware stack and returns whether or not the call was a miss or a hit

5) Writing a dynamic memory allocator! (There were a few constraints, like the base code provided used a single explicit free list, pointers had to be stable, and "system memory" could only be requested from an emulation of sbrk)

Basically, lots of good down-to-the-metal investigation and a fair amount of actual code writing.

In the meantime, CS143 meandered around, mostly covering data structures in the Java system libraries (with a bit of investigation on how to implement them, not as much as I'd have liked) and some algorithms (all in Java, so somewhat abstract and ignoring things like memory access pattern...). There were some useful points covered, like a couple different sorting algorithms and a more realistic explanation of algorithm complexity (acknowledging that actually timing it is important!) I went to class less and less over the course of the quarter...and it's possible my grade suffered a bit for it, simply because I didn't bother remembering how Java did certain things on the exam. I'll be damned if I'll waste mental energy on remembering the syntax to implement the comparable interface for derived classes and whether or not Java decided to use size or length for Maps. That's what search engines are for.

I also started to feel more and more uncomfortable about deriding the quality of the computer science curriculum at my university. If CS351 is what the upper-level classes are all like, it's actually really good. Like, the best I could hope for. Now, I'm getting impressions that not all of the classes are quite like 351, and tend to err on the side of more theoretical/higher level, but even so, it's clear that the professors are on the whole quite competent and know what they're talking about. So I stopped making fun.

That being said, from what I've heard, many schools tend to be more of what I was complaining about with CS351, so take my impressions with a grain of salt. I, for one, am going to quietly continue with my education. I'll post more blog things when I have actual intereresting things to talk about. Some may be cross-posts with the devlog for Handmade Dev, my main side project. So stay tuned.

Thanks for reading these imprecise words conveying misguided emotion from within a network of electrical pulses!

[chronaldragon]

Seattle’s Best: Part 2

This week's post is a single image because I'm coming down with a cold and I think it really sums up all I need to say on the matter.

[Ninja-edit]: Oh, and JDB is awful. Truly awful. It seems pretty clear that no one has used it in a long time. It can’t even run applications interactively. I just hope I don’t encounter anything in this course that requires me to install Eclipse.

[chronaldragon]

Seattle’s Best: Part 1.5

[This is a follow up to this week's entry of Seattle's Best, a blog series where I vent about my freshman level CS class. As with the other series, I don’t mean any disrespect to the staff, who I’m sure work very hard to deliver a good education to the hundreds of students in this department. This is purely personal venting and criticism of computer science education in general.]

Keeping to the above disclaimer is going to be difficult in this one, because this segment is titled

Lies my Java Instructor Told Me

I'll try to keep this pretty general and preempt my points with some qualifiers. I'll point out again that this class is intended as an easy introduction to programming, that covering all of the subtleties of each topic is well beyond the scope of the curriculum, that many of the students here don't intend to go very far down the programming rathole...but that won't stop me from sounding pretty angry about some of this stuff. Fair warning.

All of the following segments in blockquotes are direct quotes from lectures. I had to take notes on something.

Let's see what one of the premier institutions for programming education has to say about the architecture of code in an object-oriented situation.

An object is a program entity that combines state and behavior

Object Oriented Programs are programs that perform their behavior as interactions between objects.

Okay, well that's...not entirely wrong. Here's what Dr. Alan Kay, more or less the inventor of this methodology has to say about objects and OOP:

I thought of objects being like biological cells and/or individual computers on a network, only able to communicate with messages... My math background made me realize that each object could have several algebras associated with it, and there could be families of these, and that these would be very very useful.

OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.

I won't get entirely into a critique of object oriented programming as a concept but even accepting that, the definition given in the lecture is missing some key points. "Pure" objects would not have "behavior" other than the passing of messages to other objects. Their state would not be accessible at all, except that the objects would pass different messages with different states.

Java methods are not really messages. They're functions that happen to implicitly take the "object" as the first parameter. That's key because it means each object still has to know the exact format of the other objects' "message handler" in order to pass a message over. Contrast this with system-level message passing between processes. There are a few predefined codes, sure, but beyond that each program is responsible for parsing out the data in the messages it receives. Very different from the Java style.

So even if they wanted to teach Object Oriented Programming here, they're not doing well so far. They've barely captured one part of it, leaving out a pretty significant aspect of what was supposed to be so versatile. But not only that, the course ignores the domain-specific applications of objects and assumes they can be applied equally to all problems. Let's look a specific example of this:

A class is an entity that represents:

A complete program or module

A template for a type of objects

Hold your horses. Templates for objects and entire programs are represented by the same concept? Not only is that totally confusing for beginners (who are already being crippled by overapplication of objects in situations that make no sense), but it also makes it much harder to distinguish what a class is being used for when reading code. Is this actually a "nicely packaged" object that wants to interact with other objects, or is this a static module?

I could go on about Java's shortcomings for hours, but that was just the first 5 minutes of the lecture. Let's continue.

Abstractions provide separation between concepts and details. This means that even if you don't know how something was implemented, you can still use it! ... Objects provide abstraction in programming.

Let's talk about abstractions. Abstractions are indeed useful, because not everyone one wants to think about what's happening to register eax as it buffers in bits from the L1 cache and figure out where exactly the instruction pointer is going when it hits that jmp. (Some people do like to think about these things, and I tend to listen closely when these people have something to say, because it's usually worthwhile. But that's a bit tangential).

So we like abstractions because it's easier to solve some problems if we can change them into a more familiar form. It's easier to say set A to 3 than it is to say mov eax 0x3. The problem is, the majority of meaningful abstractions do not transform most problems "losslessly." By losslessly, I mean there are nontrivial situations in which the abstraction does not work the way you would expect, because of the actual "details" we're so keen on covering up. Usually, there's a wide range of effectiveness of various abstractions for any given problem. Effective programmers know which abstractions to use in which situations.

That brings me to the second part of that statement. "Objects provide abstraction in programming." This is precisely how it was phrased both on the powerpoint and when spoken aloud by the lecturer. Note the lack of specificity: it is not "Objects provide an abstraction in programming", it leaves open the possibility that objects are the only abstraction in programming. And indeed, that seems to be implicitly advocated by the use of Java as the sole language of this course.

Java tries to provide a panacea to all problems, and that is to "encapsulate" the problem into an object.

Until Java 8, Java had no concept of a way to talk about functions as program constructs other than as predefined "behaviors" of a class. (Guess which version of Java this class is not using), so Java students have no opportunity to learn about functional programming and composition, or talk about programs with any kind of mathematical formalism.

Java has no preprocessor and no metaprogramming facilities (other than basic runtime reflection, which is implemented -- you guess it -- as a set of objects), so Java students have no opportunity to view their code as data.

In fact, Java doesn't even have behaviorless structs, so Java students don't even get much opportunity to think about data as anything other than nebulous, indeterminately sized objects floating around somewhere "inside the computer".

So if the goal of this class was to give people a broad introduction to programming that they could use to better understand how the computers around them worked, it has failed miserably. It has given its students one abstraction which is woefully ineffecient for a majority of problems and not even hinted that there might be more to discover out there. In case you can't tell, that makes me pretty angry. It's dooming a significant number of my peers (the ones who won't move on to the more advanced courses) to misunderstand computers and does not even give them the tools to find out more on their own.

*sigh*

Let's talk about privacy.

I always make fields of my objects private. It's very critical for the integrity of my object that my state remains accurate. We don't want people messing with our private data.

This is reiterated in the course style guide.

Properly encapsulate your objects by making any data fields in your class private.

I could go on at length about whether or not the concept of having private members is even a worthwhile thing to have in the language (and in fact did in an earlier version of this post) but then I came across this in the ancillary code for one of my homework assignments.

public class Tile { private int x; // top-left x/y private int y;   // ... (some code omitted)   /** Returns this tile's leftmost x coordinate. */ public int getX() { return x; } /** Returns this tile's topmost y coordinate. */ public int getY() { return y; }   // ... (some code omitted)   /** Sets this tile's leftmost x-coordinate to be the given value. */ public void setX(int x) { this.x = x; } /** Sets this tile's topmost y-coordinate to be the given value. */ public void setY(int y) { this.y = y; }

I'm utterly flabbergasted. Apparently the idea of having a public member or two is so abhorrent that they are willing to create four extra functions just to avoid having to write the accursed word public in front of a variable.

So clearly the entire thing is a joke, they don't actually care about data access, and are just checking boxes in some arbitrary list of rules from On High. I won't bother with it. I can't.

Ugh.

I want to do something interesting comparisons in relation to this assignment but I've been thrown utterly off track by finding the above code. Expect some fun elaboration over the weekend, maybe.

Until then, May the (public) Variable be With You.

[chronaldragon]

Seattle’s Best: Part 1

[This is the first post in a series about a Freshman-level CS class at the University of Washington. I don't mean any disrespect to the staff, who I'm sure work very hard to deliver a good education to the hundreds of students in this department. This is purely personal venting and criticism of computer science education in general.]

The first day of class began somewhat inauspiciously with a search for an empty seat in the large lecture hall that turned out to probably not be big enough for the 300-some students taking CSE 143. I ended up near the front, which I may or may not attempt to repeat in future lectures. On the plus side, I’ll be able to record the lectures with good volume levels, but on the minus side, it’ll be harder to ignore the lecture if I have other things to do.

The course meta info was pretty typical, the only noteworthy thing being that Homework/Section participation is 50% of the grade. I’m also a little concerned about the fact that “Exams are closed-book and closed-note” -- does this mean they’ll be written!? Even if not, does that mean the javadocs will be closed to us? What kind of programmer works without docs available? Are we learning to code here or just memorizing the Java API?

Okay, I’ll cross that bridge when I come to it. On to the course content. I can tell from the syllabus that this is going to be a long 10 weeks...

I’ll try not to belabor the point, but needless to say I thought I was finished with most of those topics (in the context of Java) several years ago. So when we started in with ArrayList today, you can imagine my exasperation.

But maybe it’s not so bad. I mean, C++ has std::vector<t>, which is similar and pretty useful, right? And I wrote my own array<t> in C++ for basic stretchy arrays (I’ll write more about that sometime). So stretchy arrays have their uses.

Before I get into that I want to mention something. Specifically I want to address the middle bullet from this powerpoint slide:

This is very damaging in two ways. First, it confuses implementation difficulty with computational difficulty (which, I dunno, maybe doing a memcpy is super difficult for these people?). Second, it’s actually pretty much just wrong. The typically cited example of a thing which does have fast inserts in the middle is a Linked List, which may have been faster in the 1980s, but now we have fancy things called processor caches that make this statement objectively wrong in most cases.

To insert an element in a Linked List, you have to chase the pointers along the list to the element before the one you want to insert (causing probably N cache misses along the way), and then update the last element’s pointer to point to the new element. To insert an element in an Array, you just memcpy N+1 through length to N+2 (maybe doing a bit of gymnastics to avoid losing data) and update the element at N, which is a constant access. Doing that memory copy is almost always going to be faster, nowadays, even with gymnastics, because some very intelligent people who make microprocessors have made it very fast to transfer contiguous blocks of memory from one place to another. I realize it’s tough to introduce all this in a freshman-level CS course, but they could at least stop perpetuating the false information.

Anyway, back to ArrayLists. let’s look at the example problem.

Print out the words in a file in reverse order.

Pretty simple stuff. No need for ArrayLists here, just run backwards over each character in the file, store a landmark when you enter a word and print up to the landmark when you leave, righ-- no, this is Java, we’re going to use the standard library, god damn it. The lecturer starts by constructing a Scanner class. Now, of course, Scanner, being a simple, general purpose stream tokenizer, can’t go backwards through a stream. Why would you want to go backwards? Going backwards through a file is an unsolved problem in computer science, and this is a freshman level class, so we’re going to array the f--- out of this problem. Computers have infinite memory, so that’s okay.

Okay, so, we’re going forwards through the file, dumping each word into a String[8]. All right, fine. That’s stack memory so-- NOPE, this is java, it’s all heap memory. We’re newing the hell out of that array. Whatever, this is probably going to run once for a fraction of a second, the Garbage Collector won’t get in the way here, in this particular example problem. (No mention of the GC or stack/heap memory from the lecture, by the way. Most of my classmates would have no idea what I’m talking about).

Note: Java statically-sized arrays might actually end up on the stack, I haven’t looked into it. I assume the fact that they enforce a static size has to be for some reason, though with Java involved it could really be anything. Anyway, even if it does end up on the stack, using the new operator is just misleading.

Right, so then we go through the String[8] starting from the end and go to the beginning. All right, I can live with that. All seems to work just fine. But then I hear, from the lecture podium, an astonishing string of words.

“But that’s not very good code, is it?”

You’re damn right that’s not very good code. For one thing it’s all in a class when there is no reason to “encapsulate” this functionality into an object since it’s only doing a single thing, and you’re using a system Scanner when you could just loop over the characters in the file, and you’re stuffing it all into an array even though you’re not doing any actual processing on it as individual tokens --

“What if we had more than 8 words?”

Oh, that was the problem here? Silly me, I thought we were about to switch to a language that doesn’t actively encourage bad code practices. The lecturer tries to demonstrate why you couldn’t just increase the size of the array by showing how a larger array would have some null values, and even if you ignored them, what if there were more than 1000 words? Thus enters the ArrayList. We proceed to take 10 minutes of our precious time to go over the API for using an ArrayList, and I felt bad for whoever had to put the powerpoint together because it was basically just a dumbed down version of the java docs for it. Okay, so then we replace the usage of the String[8] with an ArrayList<string>, which is all right, I suppose.

Now, what the lecturer didn’t point out, and I really wish they had, is that even if your concern is full generality here, you can still put an upper bound on the size of the array. You presumably know what the word delimiter is, so you could just count those, add one or two (depending on if the file can end abruptly), and there’s your number of words. Java would even let you do it, surprisingly enough, with the ArrayList<t>.ensureCapacity() method, which I have to assume allocates enough memory under the hood to hold all the objects you’re going to add. In Java, it’s the closest thing you can get to managing the memory yourself. But there was no mention of this at all. Just some vague excitement over the ability to hold unlimited words! Because computers have infinite memory.

Okay, enough of that. I’m stuck in this Java class so I’m going to have to grin and Barrett. By which I mean reimplement the Java solutions in C for sanity and science. I won’t have a homework assignment until Friday (when I’ll do a Part 1.5 post) so today’s C-ification will be of the sample problem mentioned above.

Here’s what the given Java solution looks like:

import java.io.*; import java.util.*; class Main { public static void main(String[] Args) throws FileNotFoundException { Scanner s = new Scanner(new File("words.txt")); ArrayList<string> Words = new ArrayList<string>(); while (s.hasNext()) { Words.add(s.next()); } for (int i = Words.size() - 1; i >= 0; --i) { System.out.println(Words.get(i)); } } }

(Compiled in javac with -g flag)

Lines of code (cloc): 18

Run time (1 million word file): 207.725 seconds

Peak memory usage (Task manager): 210.0MB

This is the C solution I thought of when I first saw the problem. For fairness, I'm using the C standard library instead of calling the Windows API directly.

#include <stdio.h> #include <stdlib.h>   int main(int argc, char* argv) { FILE* Txt = fopen("words.txt", "rb");   fseek(Txt, 0L, SEEK_END); size_t Size = ftell(Txt); fseek(Txt, 0L, SEEK_SET);   char* File = (char*)malloc(Size); fread(File, 1, Size, Txt);   char* WordEnd = File + Size; char* WordStart = WordEnd; int WordCount = 0; for (char* C = WordEnd; C >= File; --C) { if ((C) == File || *(C - 1) == '\n') { WordStart = C; printf("%.*s\n", WordEnd - WordStart, WordStart); WordEnd = C - 1; ++WordCount; } }   return 0; }

(Compiled in MSVC with /Od flag)

Lines of code (cloc): 25

Run time (1m words): 138.681 seconds

Peak memory usage (Task manager): 9.0MB

Now, run time is not a great metric here since both versions are limited by the speed at which they can print to the console. Here's the run times if I comment out the respective printing lines:

Java: 970ms

C: 37ms

So yeah, for the whole "running through the file" bit, C is over 30 times faster using my strategy. Maybe that's not fair to Java, so let's write a Java version using the same idea. Now, the issue is that the java File io only supports streamed (asynchronous) reads, so I'll have to add a bit of boilerplate to my Java code to be able to deal with the stream the same way. (Now, it might be better just to stream the file in reverse so it doesn't all have to be in memory, but I'm not doing that in C and that would require more Java API rummaging than I want to do right now).

private String readFileAsString(String filePath) throws IOException { StringBuffer fileData = new StringBuffer(); BufferedReader reader = new BufferedReader( new FileReader(filePath)); char[] buf = new char[1024]; int numRead=0; while((numRead=reader.read(buf)) != -1){ String readData = String.valueOf(buf, 0, numRead); fileData.append(readData); } reader.close(); return fileData.toString(); }

from this StackOverflow post

My C version presumably has to do something similar under the hood for fread, so I'll count this method call in the performance timing. Now here's the rest of the Java version:

import java.io.*; import java.util.*; . class Main { public static String readFileAsString(String filePath) throws IOException // ... See above . public static void main(String[] Args) throws FileNotFoundException, IOException { String File = readFileAsString("words.txt"); . int WordEnd = File.length(); int WordStart = WordEnd; for (int i = WordEnd; i >= 0; --i) { if (File.charAt(i) == '\n' || i == 0) { WordStart = i; System.out.println(File.substring(WordStart, WordEnd) + "\n"); WordEnd = i - 1; } } } }

Lines of code (cloc): 36

Run time (1m words): 199.813 s

Peak memory usage (Task manager): 129.8 MB

Looking a bit better than the other version. Without console output:

Java: 970ms

C: 37ms

Java (by-char): 110ms

Would you look at that. By not using the Scanner and ArrayList objects, I get a 9x performance boost even in Java itself. Still about 3-4x slower than C, but much better than before. So what does this tell us? Two major things:

Java makes it quite a bit more difficult to solve problems certain ways. More LOC than an equivalent C implementation (fighting around the standard library), and speed overhead you can't really do anything about.

Solving a problem in the most general way (implicitly and explicitly advocated by the class I'm taking and the CS department style guide) often leads to solving it in an inefficient way. Data-specific code will do better most of the time.

Now, bear in mind that this is a very artificial situation. In the real world, if you want to do some rote data transformation, you'd use sed or awk or python. Nobody in their right mind who knows about those tools wants to break out the ol' C or Java IDE just to do something dumb like that. [Update: Harikrishnan (@Delta_Maniac) points out that tac does precisely what this problem is asking! Guess someone did decide to do it in C. Okay, now there's not really any reason to do it again.]

Which brings me to my final point. Why are we starting off programming students in Java? It dogmatically enforces certain coding practices and discourages experimentation. It doesn't read particularly well, or at least no better than C (if you use sane naming conventions -- another thing I'll rant about at another time). And it is almost precisely as portable as the equivalent C version in most cases -- my above code will compile (perhaps with a few slight modifications, I wasn't thorough about convention) on almost any platform, because everyone ports GCC as the first application on a new architecture and C has a standard library.

I understand that the class I'm taking is for general interest and not everyone who will take it wants to become an expert on processor-level details about computer functionality. I think even with that in mind, teaching these students Java is doing them a disservice by misrepresenting how the computer actually works. I don't know if there's really a good solution at this point, and that's a problem the programming education community needs to work on. I have my own ideas but they're not quite ready to ripen yet.

All of that being said, I think once I get out of this quagmire, there's some interesting classes ahead of me here that will actually be quite valuable to my education. So I'll continue suffering through, but keep this updated. I'll make another post Friday once I've got my first homework assignment, and installments will continue most Fridays until the end of the quarter.

Happy Coding, and May the Variable be With You. </stdlib.h></stdio.h>

[chronaldragon]

Seattle’s Best: Part 0

I’m about to start the introductory-level Computer Science course at my university (UW Seattle): CSE143. Officially, it’s called “Computer Programming II” -- they spread the intro material (some programming basics in Java) over two classes, and I can only test out of the first one. As an experiment, I’m going to document the experience so that we can tell once and for all (well, more like in one case for one school) whether Egregious Education is to blame for all of programming’s current predicaments. Or at least so you all can suffer with me through a quarter of Java riddles and weird grading schemes.

I have 3 lecture sessions a week (MWF), but I’m only going to update the blog once a week (probably Friday evenings, usually). I’ll try to summarize what the lectures were about, give a couple examples of whatever tasks or homework problems stuck out, and maybe try to draw poorly based conclusions out of anecdotal evidence. It’ll be fun.

As an aside, I’m going to try to improve my low level programming chops by doing all the homework problems in C as well as Java. Well, I’ll see if I can keep it up, but if I do, you’ll be the first to know. I’ll take some metrics as I do, like how many Lines Of Code the solution was implemented in, how long it took to write, how much processing time/memory it takes to run, and so forth. This, of course, gives me ample grounds for shoving my superiority in the face of my fellow students. Just kidding, I’ll use it for science or something. 

That’s all for now. You can also follow me on twitter for random personal details, software complaints, and probably notifications about when this blog will be updated. Stay tuned. 

[chronaldragon]

Universitying • (v)

After some consideration, I’ve decided to accept an invitation to the University of Washington’s Computer Science program! 

It’s an awesome opportunity, since the program is one of the top rated in the country, and a very small percentage of applicants get in. Being admitted directly from high school is also quite rare, but will allow me a lot more freedom in how I make use of the classes and resources available there. I’ll have many opportunities for unique study and potentially original research in robotics, human-computer interaction, wearable technologies, or one of many other subjects, which I am eager to begin exploring.

I had some reservations about the University of Washington, given its huge student body and expansive campus, but these downsides are offset by some quite considerable upsides: an extremely wide variety of resources available, high quality staff and advisers, and an advantageous location. 

Anyhow, regardless of how this turns out, I’ll still be actively pursuing projects outside of school as ever. Cheers.

[chronaldragon]

Announcing MWall

Have you ever been on Windows with multiple monitors and thought the wallpaper support was kind of lame? I have. Until Windows 8 it would only show one of your wallpaper at a time on all of the monitors, and even then it only lets you pick from one folder at a time. Enter MWall (Download link). I built MWall as a tool for myself, to get a better utilization of my monitors. Existing tools are much too feature-bloated and many cost money, so I decided it was a simple enough problem that I could do it myself. I've been learning C++ and wanted to test out my knowledge of the Windows API, and this was the perfect opportunity. It is currently very bare-bones, yet still has something to offer for many users. It can draw from multiple folders at a time, at the same time as particular wallpapers from anywhere on your computer. It can update the wallpaper at any interval you like, instead of Windows' granular options. And of course, it displays a different wallpaper on each monitor. Planned features for future development include the ability to have larger wallpapers contiguous across monitors (so you can have your ultra-landscape panoramas and whatnot), a way to set the anchor point of wallpapers on a monitor (so that you can always see a certain point on the wallpaper), and per-monitor interval settings. Stay tuned to see where it goes.

Get MWall (Download link).

[chronaldragon]

Language Wars

It's hard to go very far these days in the programming community without stumbling upon a discussion about the relative merits of different programming languages. In fact, even revealing that you're using one language or another can be enough to provoke comments, questions, and arguments about whether or not the use of that language was a good decision. For example, I've been moderating the Handmade Hero chatroom for more than a month now, and at least once (often several times) each stream (an hour a day, 5 days a week) we have to deal with people debating the merits of the language used by the streamer.

It may sound like I'm trying to separate myself from these types of people, but truth be told at one point I was someone who did these things. In fact, for the past few years I've switched from language to language, lambasting the ones I hadn't tried yet for reasons only known by hearsay and the ones I had tried for reasons found in practice (but not well understood). And pretty much anyone who learns at least one programming language will find themselves in the same place, at some point. So why do we do it?

Before I can propose an answer to that, it may be fruitful to explore in more detail what programming languages are actually used for. The specific uses are broad ranging, encompassing everything from scientific research to operating system design to game simulation to user-oriented tools and products. But in general, they are systems we use to allow us to coax some behavior out of a computer to do useful work (or work that's perceived as useful, anyway). They are abstractions of the underlying machine language that make it possible for a programmer to create systems of logic that perform a task without having to know the very fine-grained details of the implementation. This is true even of low-level languages like assembly languages, as they must be run through an assembler to be translated from the plain-text source code to machine byte code (though this transformation is much closer to 1:1 in most cases than other types of languages).

So that is what programming languages are for, in an abstract sense, and it is important to keep that in mind as we continue looking at their other properties. Languages differ in numerous ways, and their properties lend themselves to the accomplishment of the specific purposes for which each languages tends to be used. For example, C allows the programmer to define the way the data in the computer's memory is laid and transform it using more useful structures, as well as to break these rules and point at the data itself when necessary. Java tries to model the logic of the program as the interactions between almost-tangible objects which have properties derived from a well-defined blueprint. Haskell turns the program into almost a mathematical proof, with rigid restrictions on the nature and properties of functions. These are the most well-known examples of a few different paradigms, and might be the ones of which language warriors become most defensive. In each case, the tools provided by the language are tailored to these ideas and tend to make it difficult to think about the code in ways other than that which the creator intended.

On a more granular level than the structure of the language, each one has a well-defined syntax that the programmer uses to express themselves and manipulate the tools provided by the language. Some aspects of this syntax are shared, especially when the functionality of the language overlaps with that of a predecessor or contemporary. For example, a great many modern languages borrow syntactical elements from C, which itself uses elements from the earlier language B. Also, several languages have converged on a similar syntax for doing generic expressions. But despite these similarities, there are many differences from language to language, and even people who are experienced enough to be able to pick up a new language quickly must take some time to become familiar with the new syntax. This lends itself to some inertia when thinking about different languages, especially if the programmer has not had very much experience learning a new syntax and being able to switch back and forth. 

Additionally, an equally or perhaps even more significant factor in working with a programming language is the community which has been built up around it. Just about every language has a tag on StackOverflow, many have a dedicated forum and/or chatroom, and most if not all have had dozens if not hundreds of books published on their use. It's not hard to build up a sense of camaraderie with the members of these communities as you explore the issues that they, too, have faced, and become familiar with the ways they think about problems in the structure of the language. Additionally, and most importantly to the topic at hand, these communities will often (jokingly or not) poke fun at programmers who use other languages, compare their language to others (highlighting, of course, the ways in which it is superior), and build up a sense of superiority about the language their community revolves around. This is a pretty natural thing for a community to do, but is probably the single biggest contributor to the phenomenon of Language Wars.

So in essence, people are eager to defend their current way of thinking, and in the world of programming, that is inextricably tied to the programming language. The more good experiences you have with a language and the community around it, the more likely you are to be dismissive or combative at the mention of other languages. This is as much of a problem for programmers whose primary experience is in low-level languages as it is for those who have only worked with very high-level ones. Unfortunately, the more time spent debating the relative merits of different languages, the less time is spent coding. And that is the single biggest tragedy about language wars: not that feelings may be hurt, but that the actual fruits of coding have been put aside to squabble over the most basic aspects of making them.

In addition to the language wars, the Handmade Hero chatroom sees a lot of repetitive questions, so some of the community members and I built up a bank of responses on a python chatbot so that we can easily answer questions. I think the bot's canned response to the language wars (triggered by saying !wrench in the chat) sums up my point rather succinctly:

Programming is not about the languages. Code is the tool used to solve the problems programmers must address.

It doesn't matter if you use Python, or Java, or C, or some weird language that hasn't been invented yet. As long as you are writing code that benefits someone without causing them undue grief, you are making a useful contribution to the world of software development. 

(That being said, there are cases to be made for the use of specific languages for specific purposes, just like there are different tools for different jobs, and I may be making some of these cases in later posts. In every instance, however, the important thing is to be informed enough on the issue to make an intelligent argument and to remember what I said above!)