Reboot Early, and Often!

A wise man once said to me “Reboot early, and often!” He said it many times actually. When you’re trying to troubleshoot programs for which you don’t have the source code, you tend to develop little rituals that you go through to “fix” them…

So here I was today, trying to power through the boilerplate to draw a triangle in Vulkan. I had just finished up creating my Pipeline object, and ran my program to see if it worked. As you can imagine, it didn’t work.

Shockingly, C++ Causes Problems

First up: my shaders are invalid. The error:

validation layer: ObjectTracker : Invalid Shader Module Object 0xa.

Of course, the Object Tracker layer is there to tell you when you try to use objects that are not valid handles. Usually this is because vKcreateFoo did not return VK_SUCCESS. Of course, vkCreateShaderModule definitely did return VK_SUCCESS, because if it hadn’t my program would have died in a fire thanks to my expect assertion macro. Surely either I have a driver bug or C++ is doing “exactly what I told it to.”

So I do some troubleshooting. I upgrade my driver which does nothing. Then I examine my code. Buried in a comment thread on this stackoverflow question is the suggestion that a destructor is being called. I examine my code, and sure enough, the RAII object that I’m storing my shader in is being destructed before the call to vkCreateGraphicsPipeline. C++ was doing “exactly what I told it to.”

Sound Advice

So an hour later, and one problem down. I recompile and try again:

vkEnumeratePhysicalDevices: returned VK_ERROR_INITIALIZATION_FAILED, indicating that initialization of an object has failed

Shenanigans! There’s no way that vkEnumeratePhysicalDevices is messed up, that’s been working for weeks! I turn to the Googler, but to no avail. Then the words rang in my head “Reboot early and often!” It’s not like I just updated my graphics driver without rebooting or anything… Oh wait!

Moral of the story: reboot early, and often!

Something Broke!

Linux has come a long way since the days of non-existent wifi drivers and flash plugins. I dare say Linux is ready for non-technical users. At least I would say this if I didn’t still occasionally get random errors. You know, like this one:

Awesome, something broke! Thanks for letting me know! Twice!

This one is a common one, and easily fixed. However, I never remember what the specific incantation for this one is, so I always have to Google it. But no more! Today I record the solution in my log!

The Solution

This one is caused by some process crashing. When a process crashes, apparently it dumps some junk into /var/crash that presumably the developer of said process knows about and cares about. Unfortunately I’m not said developer, and I don’t care about a one time crash of some random process. I do care that I’m getting 2-3 useless popups whenever I boot my Linux partition up. Let’s fix this:

NOTE: Consider looking in /var/crash to see what happened before randomly deleting all the stuff in it.

$ sudo rm /var/crash/*
$ sudo init 6

After your machine reboots, you should be good to go.

The Specter of Undefined Behavior

If you’ve ever spoken to a programmer, and really got them on a roll, they may have said the words “undefined behavior” to you. Since you speak English, you probably know what each of those words mean, and can imagine a reasonable meaning for them in that order. But then your programmer friends goes on about “null-pointer dereferencing” and “invariant violations” and you start thinking about cats or football or whatever because you are not a programmer.

I often find myself being asked what it is that I do. Since I’ve spent the last few years working on my Computer Science degree, and have spent much of that time involved in programming language research, I often find myself trying to explain this concept. Unfortunately, when put on the spot, I usually am only able to come up with the usual sort of explanation that programmers use among themselves: “If you invoke undefined behavior, anything can happen! Try to dereference a null pointer? Bam! Lions could emerge from your monitor and eat your family!” Strictly speaking, while I’m sure some compiler writer would implement this behavior if they could, it’s not a good explanation for a person who doesn’t already kind of understand the issues at play.

Today, I’d like to give an explanation of undefined behavior for a lay person. Using examples, I’ll give an intuitive understanding of what it is, and also why we tolerate it. Then I’ll talk about how we go about mitigating it.

Division By Zero

Here is one that most of us know. Tell me, what is 8 / 0? The answer of course is “division by zero is undefined.” In mathematics, there are two sorts of functions: total and partial. A total function is defined for all inputs. If you say a + b, this can be evaluated to some result no matter what you substitute for a and b. Addition is total. The same cannot be said for division. If you say a / b, this can be evaluated to some result no matter what you substitute for a and b unless you substitute b with 0. Division is not total.

If you go to the Wikipedia article for division by zero you’ll find some rationale for why division by zero is undefined. The short version is that if it were defined, then it could be mathematically proven that one equals two. This would of course imply that cats and dogs live in peace together and that pigs fly, and we can’t have that!

However, there is a way we can define division to be total that doesn’t have this issue. Instead of defining division to return a number, we could define division to return a set of numbers. You can think of a set as a collection of things. We write this as a list in curly braces. {this, is, a, set, of, words} I have two cats named Gatito and Moogle. I can have a set of cats by writing {Gatito, Moogle}. Sets can be empty; we call the empty set the null set and can write it as {} or using this symbol ∅. I’ll stick with empty braces because one of the things I hate about mathematics is everybody’s insistence on writing in Greek.

So here is our new total division function:

totalDivide(a, b)
   if (b does not equal 0)
      output {a / b}
   otherwise
      output {}

If you use totalDivide to do your division, then you will never have to worry about the undefined behavior of division! So why didn’t Aristotle (or Archimedes or Yoda or whoever invented division) define division like this in the first place? Because it’s super annoying to deal with these sets. None of the other arithmetic functions are defined to take sets, so we’d have to constantly test that the division result did not produce the empty set, and extract the result from the set. In other words: while our division is now total, we still need to treat division by zero as a special case. Let us try to evaluate 2/2 + 2/2 and totalDivide(2,2) + totalDivide(2,2):

1: 2/2 + 2/2
2: 1 + 1
3: 2

Even showing all my work, that took only 3 lines.

1: let {1} = totalDivide(2,2)
2: let {1} = totalDivide(2,2)
3: 1 + 1
4: 2

Since you can’t add two sets, I had to evaluate totalDivide out of line, and extract the values and add them separately. Even this required my human ability to look at the denominator and see that it wasn’t zero for both cases. In other words, making division total made it much more complicated to work with, and it didn’t actually buy us anything. It’s slower. It’s easier to mess up. It has no real value. As humans, it’s fairly easy for us to look at the denominator, see that it’s zero, and just say “undefined.”

Cartons of Eggs

I’m sure many of you have a carton of eggs in your fridge. Go get me the 17th egg from your carton of eggs. Some of you will be able to do this, and some of you will not. Maybe you only have a 12 egg carton. Maybe you only have 4 eggs in your 18 egg carton, and the 17th egg is one of the ones that are missing. Maybe you’re vegan.

A basic sort of construct in programming is called an “array.” Basically, this is a collection of the same sort of things packed together in a region of memory on your computer. You can think of a carton of eggs as an array of eggs. The carton only contains one sort of thing: an egg. The eggs are all packed together right next to each other with nothing in between. There is some finite amount of eggs.

If I told you “for each egg in the carton, take it out and crack it, and dump it in a bowl starting with the first egg”, you would be able to do this. If I told you “take the 7th egg and throw it at your neighbor’s house” you would be able to do this. In the first example, you would notice when you cracked the last egg. In the second example you would make sure that there was a 7th egg, and if there wasn’t you probably picked some other egg because your neighbor is probably a jerk who deserves to have his house egged. You did this unconsciously because you are a human who can react to dynamic situations. The computer can’t do this.

If you have some array that looks like this (array locations are separated by | bars | and * stars * are outside the array) ***|1|2|3|*** and you told the computer “for each location in the array, add 1 to the number, starting at the first location” it would set the first location to be 2, the second location to be 3, the third location to be 4. Then it would interpret the bits in the location of memory directly to the right of the third location as a number, and it would add 1 to this “number” thereby destroying the data in that location. It would do this forever because this is what you told the machine to do. Suppose that part of memory was involved in controlling the brakes in your 2010 era Toyota vehicle. This is obviously incredibly bad, so how do we prevent this?

The answer is that the programmer (hopefully) knows how big the array is and actually says “starting at location one, for the next 3 locations, add one to the number in the location”. But suppose the programmer messes up, and accidentally says “for the next 4 locations” and costs a multinational company billions of dollars? We could prevent this. There are programming languages that give us ways to prevent these situations. “High level” programming languages such as Java have built-in ways to tell how long an array is. They are also designed to prevent the programmer from telling the machine to write past the end of the array. In Java, the program will successfully write |2|3|4| and then it will crash, rather than corrupting the data outside of the array. This crash will be noticed in testing, and Toyota will save face. We also have “low level” programming languages such as C, which don’t do this. Why do we use low level programming languages? Let’s step through what these languages actually have the machine do for “starting at location one, for the next 3 locations, add one to the number in the location”: First the C program:

NOTE: location[some value] is shorthand for “the location identified by some value.” egg_carton[3] is the third egg in the carton. Additionally, you should read these as sequential instructions “first do this, then do that” Finally, these examples are greatly simplified for the purposes of this article.

1: counter = 1
2: location[counter] = 1 + 1
3: if (counter equals 3) terminate
4: counter = 2
5: location[counter] = 2 + 1
6: if (counter equals 3) terminate
7: counter = 3
8: location[count] = 3 + 1
9: if (counter equals 3) terminate

Very roughly speaking, this is what the computer does. The programmer will use a counter to keep track of their location in the array. After updating each location, they will test the counter to see if they should stop. If they keep going they will repeat this process until the stop condition is satisfied. The Java programmer would write mostly the same program, but the program that translates the Java code into machine code (called a compiler) will add some stuff:

1: counter = 1
2: if (counter greater than array length) crash
3: location[counter] = 1 + 1
4: if (counter equals 3) terminate
5: counter = 2
6: if (counter greater than array length) crash
7: location[counter] = 2 + 1
8: if (counter equals 3) terminate
9: counter = 3
10: if (counter greater than array length) crash
11: location[count] = 3 + 1
12: if (counter equals 3) terminate

As you can see, 3 extra lines were added. If you know for a fact that the array you are working with has a length that is greater than or equal to three, then this code is redundant.

For such a small array, this might not be a huge deal, but suppose the array was a billion elements. Suddenly an extra billion instructions were added. Your phone’s processor likely runs at 1-3 gigahertz, which means that it has an internal clock that ticks 1-3 billion times per second. The smallest amount of time that an instruction can take is one clock cycle, which means that in the best case scenario, the java program takes one entire second longer to complete. The fact of the matter is that “if (counter greater than array length) crash” definitely takes longer than one clock cycle to complete. For a game on your phone, this extra second may be acceptable. For the onboard computer in your car, it is definitely not. Imagine if your brakes took an extra second to engage after you push the pedal? Congressmen would get involved!

In Java, reading off the end of an array is defined. The language defines that if you attempt to do this, the program will crash (it actually does something similar but not the same, but this is outside the scope of this article). In order to enforce this definition, it inserts these extra instructions into the program that implement the functionality. In C, reading off the end of an array is undefined. Since C doesn’t care what happens when you read off the end of an array, it doesn’t add any code to your program. C assume you know what you’re doing, and have taken the necessary steps to ensure your program is correct. The result is that the C program is much faster than the Java program.

There are many such undefined behaviors in programming. For instance, your computer’s division function is partial just like the mathematical version. Java will test that the denominator isn’t zero, and crash if it is. C happily tells the machine to evaluate 8 / 0. Most processors will actually go into a failure state if you attempt to divide by zero, and most operating systems (such as Windows or Mac OSX) will crash your program to recover from the fault. However, there is no law that says this must happen. I could very well create a processor that sends lions to your house to punish you for trying to divide by zero. I could define x / 0 = 17. The C language committee would be perfectly fine with either solution; they just don’t care. This is why people often call languages such as C “unsafe.” This doesn’t mean that they are bad necessarily, just that their use requires caution. A chainsaw is unsafe, but it is a very powerful tool when used correctly. When used incorrectly, it will slice your face off.

What To Do

So, if defining every behavior is slow, but leaving it undefined is dangerous, what should we do? Well, the fact of the matter is that in most cases, the added overhead of adding these extra instructions is acceptable. In these cases, “safe” languages such as Java are preferred because they ensure program correctness. Some people will still write these sorts of programs in unsafe languages such as C (for instance, my own DMP Photobooth is implemented in C), but strictly speaking there are better options. This is part of the explanation for the phenomenon that “computers get faster every year, but [insert program] is just as slow as ever!” Since the performance of [insert program] we deemed to be “good enough”, this extra processing power is instead being devoted to program correctness. If you’ve ever used older versions of Windows, then you know that your programs not constantly crashing is a Good Thing.

This is fine and good for those programs, but what about the ones that cannot afford this luxury? These other programs fall into a few general categories, two of which we’ll call “real-time” and “big data.” These are buzzwords that you’ve likely heard before, “big data” programs are the programs that actually process one billion element arrays. An example of this sort of software would be software that is run by a financial company. Financial companies have billions of transactions per day, and these transactions need to post as quickly as possible. (suppose you deposit a check, you want those funds to be available as quickly as possible) These companies need all the speed they can get, and all those extra instructions dedicated to totality are holding up the show.

Meanwhile “real-time” applications have operations that absolutely must complete in a set amount of time. Suppose I’m flying a jet, and I push the button to raise a wing flap. That button triggers an operation in the program running on the flight computer, and if that operation doesn’t complete immediately (where “immediately” is some fixed, non-zero-but-really-small amount of time) then that program is not correct. In these cases, the programmer needs to have very precise control over what instructions are produced, and they need to make every instruction count. In these cases, redundant totality checks are a luxury that is not in the budget.

Real-time and big data programs need to be fast, so they are often implemented in unsafe languages, but that does not mean that invoking undefined behavior is OK. If a financial company sets your account balance to be check value / 0, you are not going to have a good day. If your car reads the braking strength from a location off to the right of the braking strength array, you are going to die. So, what do these sorts of programs do?

One very common method, often used in safety-critical software such as a car’s onboard computer is to employ strict coding standards. MISRA C is a set of guidelines for programming in C to help ensure program correctness. Such guidelines instruct the developer on how to program to avoid unsafe behavior. Enforcement of the guidelines is ensured by peer-review, software testing, and Static program analysis.

Static program analysis (or just static analysis) is the process of running a program on a codebase to check it for defects. For MISRA C, there exists tooling to ensure compliance with its guidelines. Static analysis can also be more general. Over the last year or so, I’ve been assisting with a research project at UCSD called Liquid Haskell. Simply put, Liquid Haskell provides the programmer with ways to specify requirements about the inputs and outputs of a piece of code. Liquid Haskell could ensure the correct usage of division by specifying a “precondition” that “the denominator must not equal zero.” (I believe that this actually comes for free if you use Liquid Haskell as part of its basic built-in checks) After specifying the precondition, the tool will check your codebase, find all uses of division, and ensure that you ensured that zero will never be used as the denominator.

It does this by determining where the denominator value came from. If the denominator is some literal (i.e. the number 7, and not some variable a that can take on multiple values), it will examine the literal and ensure it meets the precondition of division. If the number is an input to the current routine, it will ensure the routine has a precondition on that value that it not be zero. If the number is the output from some other routine, it verifies that the the routine that produced the value has, as a “postcondition”, that its result will never be zero. If the check passes for all usages of division, your use of division will be declared safe. If the check fails, it will tell you what usages were unsafe, and you will be able to fix it before your program goes live. The Haskell programming language is very safe to begin with, but a Haskell program verified by Liquid Haskell is practically Fort Knox!

The Human Factor

Humans are imperfect, we make mistakes. However, we make up for it in our ability to respond to dynamic situations. A human would never fail to grab the 259th egg from a 12 egg carton and crack it into a bowl; the human wouldn’t even try. The human can see that there is only 12 eggs without having to be told to do so, and will respond accordingly. Machines do not make mistakes, they do exactly what you tell them to, exactly how you told them to do it. If you tell the machine to grab the 259th egg and crack it into a bowl, it will reach it’s hand down, grab whatever is in the space 258 egg lengths to the right of the first egg, and smash it on the edge of a mixing bowl. You can only hope that nothing valuable was in that spot.

Most people don’t necessarily have a strong intuition for what “undefined behavior” is, but mathematicians and programmers everywhere fight this battle every day.

Pure Functional Memoization

There are many computation problems that resonate through the ages. Important Problems. Problems that merit a capital P.

The Halting Problem…

P versus NP…

The Fibonacci sequence…

The Fibonacci sequence is a super-important computation Problem that has vexed mathematicians for generations. It’s so simple!

fibs 0 = 0
fibs 1 = 1
fibs n = (fibs $ n - 1) + (fibs $ n - 2)

Done! Right? Let’s fire up ghci and find out.

*Fibs> fibs 10
55

… looking good…

*Fibs> fibs 40

… still waiting…

102334155

… Well that sure took an unfortunate amount of time. Let’s try 1000!

*Fibs> fibs 1000
*** Exception: <<You died before this returned>>

To this day, science wonders what fibs(1000) is. Well today we solve this!

Memoization

The traditional way to solve this is to use Memoization. In an imperative language, we’d create an array of size n, and prepopulate arr[0] = 0 and arr[1] = 1. Next we’d loop over 2 to n, and for each we’d set arr[i] = arr[i-1] + arr[i-2].

Unfortunately for us, this is Haskell. What to do… Suppose we had a map of the solutions for 0 to i, we could calculate the solution for i + 1 pretty easily right?

fibsImpl _ 0 = 0
fibsImpl _ 1 = 1
fibsImpl m i = (mo + mt)
   where
      mo = Map.findWithDefault undefined (i - 1) m
      mt = Map.findWithDefault undefined (i - 2) m

We return 0 and 1 for i = 0 and i = 1 as usual. Next we lookup n – 1 and n – 2 from the map and return their sum. This is all pretty standard. But where does the map come from?

It turns out that this is one of those times that laziness is our friend. Consider this code:

fibs' n = let m = fmap (fibsImpl m)
                  (Map.fromList (zip [0..n]
                                     [0..n])) in
   Map.findWithDefault undefined n m

When I first saw this pattern (which I call the Wizard Pattern, because it was clearly invented by a wizard), I was completely baffled. We pass the thing we’re creating into the function that’s creating it? Unthinkable!

It turns out that this is just what we need. Because of laziness, the fmap returns immediately, and m points to an unevaluated thunk. So, for i = 0, and i = 1, fibsImpl will return 0 and 1 respectively, and the map will map 0 -> 0 and 1 -> 1. Next for i = 2, Haskell will attempt to lookup from the map. When it does this, it will be forced to evaluate the result of i = 0 and i = 1, and it will add 2 -> 1 to the map. This will continue all the way through i = n. Finally, this function looks up and returns the value of fibs n in linearish time. (As we all know, Map lookup isn’t constant time, but this is a lot better than the exponential time we had before)

So let’s try it out.

*Fibs> fibs' 1
1
*Fibs> fibs' 10
55
*Fibs> fibs' 40
102334155

… so far so good…

*Fibs> fibs' 100
354224848179261915075
*Fibs> fibs' 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
*Fibs> fibs' 10000
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
*Fibs> fibs' 100000
2597406934722172416615503402127591541488048538651769658472477070395253454351127368626555677283671674475463758722307443211163839947387509103096569738218830449305228763853133492135302679278956701051276578271635608073050532200243233114383986516137827238124777453778337299916214634050054669860390862750996639366409211890125271960172105060300350586894028558103675117658251368377438684936413457338834365158775425371912410500332195991330062204363035213756525421823998690848556374080179251761629391754963458558616300762819916081109836526352995440694284206571046044903805647136346033000520852277707554446794723709030979019014860432846819857961015951001850608264919234587313399150133919932363102301864172536477136266475080133982431231703431452964181790051187957316766834979901682011849907756686456845066287392485603914047605199550066288826345877189410680370091879365001733011710028310473947456256091444932821374855573864080579813028266640270354294412104919995803131876805899186513425175959911520563155337703996941035518275274919959802257507902037798103089922984996304496255814045517000250299764322193462165366210841876745428298261398234478366581588040819003307382939500082132009374715485131027220817305432264866949630987914714362925554252624043999615326979876807510646819068792118299167964409178271868561702918102212679267401362650499784968843680975254700131004574186406448299485872551744746695651879126916993244564817673322257149314967763345846623830333820239702436859478287641875788572910710133700300094229333597292779191409212804901545976262791057055248158884051779418192905216769576608748815567860128818354354292307397810154785701328438612728620176653953444993001980062953893698550072328665131718113588661353747268458543254898113717660519461693791688442534259478126310388952047956594380715301911253964847112638900713362856910155145342332944128435722099628674611942095166100230974070996553190050815866991144544264788287264284501725332048648319457892039984893823636745618220375097348566847433887249049337031633826571760729778891798913667325190623247118037280173921572390822769228077292456662750538337500692607721059361942126892030256744356537800831830637593334502350256972906515285327194367756015666039916404882563967693079290502951488693413799125174856667074717514938979038653338139534684837808612673755438382110844897653836848318258836339917310455850905663846202501463131183108742907729262215943020429159474030610183981685506695026197376150857176119947587572212987205312060791864980361596092339594104118635168854883911918517906151156275293615849000872150192226511785315089251027528045151238603792184692121533829287136924321527332714157478829590260157195485316444794546750285840236000238344790520345108033282013803880708980734832620122795263360677366987578332625485944906021917368867786241120562109836985019729017715780112040458649153935115783499546100636635745448508241888279067531359950519206222976015376529797308588164873117308237059828489404487403932053592935976454165560795472477862029969232956138971989467942218727360512336559521133108778758228879597580320459608479024506385194174312616377510459921102486879496341706862092908893068525234805692599833377510390101316617812305114571932706629167125446512151746802548190358351688971707570677865618800822034683632101813026232996027599403579997774046244952114531588370357904483293150007246173417355805567832153454341170020258560809166294198637401514569572272836921963229511187762530753402594781448204657460288485500062806934811398276016855584079542162057543557291510641537592939022884356120792643705560062367986544382464373946972471945996555795505838034825597839682776084731530251788951718630722761103630509360074262261717363058613291544024695432904616258691774630578507674937487992329181750163484068813465534370997589353607405172909412697657593295156818624747127636468836551757018353417274662607306510451195762866349922848678780591085118985653555434958761664016447588028633629704046289097067736256584300235314749461233912068632146637087844699210427541569410912246568571204717241133378489816764096924981633421176857150311671040068175303192115415611958042570658693127276213710697472226029655524611053715554532499750843275200199214301910505362996007042963297805103066650638786268157658772683745128976850796366371059380911225428835839194121154773759981301921650952140133306070987313732926518169226845063443954056729812031546392324981793780469103793422169495229100793029949237507299325063050942813902793084134473061411643355614764093104425918481363930542369378976520526456347648318272633371512112030629233889286487949209737847861884868260804647319539200840398308008803869049557419756219293922110825766397681361044490024720948340326796768837621396744075713887292863079821849314343879778088737958896840946143415927131757836511457828935581859902923534388888846587452130838137779443636119762839036894595760120316502279857901545344747352706972851454599861422902737291131463782045516225447535356773622793648545035710208644541208984235038908770223039849380214734809687433336225449150117411751570704561050895274000206380497967960402617818664481248547269630823473377245543390519841308769781276565916764229022948181763075710255793365008152286383634493138089971785087070863632205869018938377766063006066757732427272929247421295265000706646722730009956124191409138984675224955790729398495608750456694217771551107346630456603944136235888443676215273928597072287937355966723924613827468703217858459948257514745406436460997059316120596841560473234396652457231650317792833860590388360417691428732735703986803342604670071717363573091122981306903286137122597937096605775172964528263757434075792282180744352908669606854021718597891166333863858589736209114248432178645039479195424208191626088571069110433994801473013100869848866430721216762473119618190737820766582968280796079482259549036328266578006994856825300536436674822534603705134503603152154296943991866236857638062351209884448741138600171173647632126029961408561925599707566827866778732377419444462275399909291044697716476151118672327238679208133367306181944849396607123345271856520253643621964198782752978813060080313141817069314468221189275784978281094367751540710106350553798003842219045508482239386993296926659221112742698133062300073465628498093636693049446801628553712633412620378491919498600097200836727876650786886306933418995225768314390832484886340318940194161036979843833346608676709431643653538430912157815543512852077720858098902099586449602479491970687230765687109234380719509824814473157813780080639358418756655098501321882852840184981407690738507369535377711880388528935347600930338598691608289335421147722936561907276264603726027239320991187820407067412272258120766729040071924237930330972132364184093956102995971291799828290009539147382437802779051112030954582532888721146170133440385939654047806199333224547317803407340902512130217279595753863158148810392952475410943880555098382627633127606718126171022011356181800775400227516734144169216424973175621363128588281978005788832454534581522434937268133433997710512532081478345067139835038332901313945986481820272322043341930929011907832896569222878337497354301561722829115627329468814853281922100752373626827643152685735493223028018101449649009015529248638338885664893002250974343601200814365153625369199446709711126951966725780061891215440222487564601554632812091945824653557432047644212650790655208208337976071465127508320487165271577472325887275761128357592132553934446289433258105028633583669291828566894736223508250294964065798630809614341696830467595174355313224362664207197608459024263017473392225291248366316428006552870975051997504913009859468071013602336440164400179188610853230764991714372054467823597211760465153200163085336319351589645890681722372812310320271897917951272799656053694032111242846590994556380215461316106267521633805664394318881268199494005537068697621855231858921100963441012933535733918459668197539834284696822889460076352031688922002021931318369757556962061115774305826305535862015637891246031220672933992617378379625150999935403648731423208873977968908908369996292995391977217796533421249291978383751460062054967341662833487341011097770535898066498136011395571584328308713940582535274056081011503907941688079197212933148303072638678631411038443128215994936824342998188719768637604496342597524256886188688978980888315865076262604856465004322896856149255063968811404400429503894245872382233543101078691517328333604779262727765686076177705616874050257743749983775830143856135427273838589774133526949165483929721519554793578923866762502745370104660909382449626626935321303744538892479216161188889702077910448563199514826630802879549546453583866307344423753319712279158861707289652090149848305435983200771326653407290662016775706409690183771201306823245333477966660525325490873601961480378241566071271650383582257289215708209369510995890132859490724306183325755201208090007175022022949742801823445413711916298449914722254196594682221468260644961839254249670903104007581488857971672246322887016438403908463856731164308169537326790303114583680575021119639905615169154708510459700542098571797318015564741406172334145847111268547929892443001391468289103679179216978616582489007322033591376706527676521307143985302760988478056216994659655461379174985659739227379416726495377801992098355427866179123126699374730777730569324430166839333011554515542656864937492128687049121754245967831132969248492466744261999033972825674873460201150442228780466124320183016108232183908654771042398228531316559685688005226571474428823317539456543881928624432662503345388199590085105211383124491861802624432195540433985722841341254409411771722156867086291742124053110620522842986199273629406208834754853645128123279609097213953775360023076765694208219943034648783348544492713539450224591334374664937701655605763384697062918725745426505879414630176639760457474311081556747091652708748125267159913793240527304613693961169892589808311906322510777928562071999459487700611801002296132304588294558440952496611158342804908643860880796440557763691857743754025896855927252514563404385217825890599553954627451385454452916761042969267970893580056234501918571489030418495767400819359973218711957496357095967825171096264752068890806407651445893132870767454169607107931692704285168093413311046353506242209810363216771910420786162184213763938194625697286781413636389620123976910465418956806197323148414224550071617215851321302030684176087215892702098879108938081045903397276547326416916845445627600759561367103584575649094430692452532085003091068783157561519847567569191284784654692558665111557913461272425336083635131342183905177154511228464455136016013513228948543271504760839307556100908786096663870612278690274831819331606701484957163004705262228238406266818448788374548131994380387613830128859885264201992286188208499588640888521352501457615396482647451025902530743172956899636499615707551855837165935367125448515089362904567736630035562457374779100987992499146967224041481601289530944015488942613783140087804311431741858071826185149051138744831358439067228949408258286021650288927228387426432786168690381960530155894459451808735197246008221529343980828254126128257157209350985382800738560472910941184006084485235377833503306861977724501886364070344973366473100602018128792886991861824418453968994777259482169137133647470453172979809245844361129618997595696240971845564020511432589591844724920942930301651488713079802102379065536525154780298059407529440513145807551537794861635879901158192019808879694967187448224156836463534326160242632934761634458163890163805123894184523973421841496889262398489648642093409816681494771155177009562669029850101513537599801272501241971119871526593747484778935488777815192931171431167444773882941064615028751327709474504763922874890662989841540259350834035142035136168819248238998027706666916342133424312054507359388616687691188185776118135771332483965209882085982391298606386822804754362408956522921410859852037330544625953261340234864689275060526893755148403298542086991221052597005628576707702567695300978970046408920009852106980295419699802138053295798159478289934443245491565327845223840551240445208226435420656313310702940722371552770504263482073984454889589248861397657079145414427653584572951329719091947694411910966797474262675590953832039169673494261360032263077428684105040061351052194413778158095005714526846009810352109249040027958050736436961021241137739717164869525493114805040126568351268829598413983222676377804500626507241731757395219796890754825199329259649801627068665658030178877405615167159731927320479376247375505855052839660294566992522173600874081212014209071041937598571721431338017425141582491824710905084715977249417049320254165239323233258851588893337097136310892571531417761978326033750109026284066415801371359356529278088456305951770081443994114674291850360748852366654744869928083230516815711602911836374147958492100860528981469547750812338896943152861021202736747049903930417035171342126923486700566627506229058636911882228903170510305406882096970875545329369434063981297696478031825451642178347347716471058423238594580183052756213910186997604305844068665712346869679456044155742100039179758348979935882751881524675930878928159243492197545387668305684668420775409821781247053354523194797398953320175988640281058825557698004397120538312459428957377696001857497335249965013509368925958021863811725906506436882127156815751021712900765992750370228283963962915973251173418586721023497317765969454283625519371556009143680329311962842546628403142444370648432390374906410811300792848955767243481200090309888457270907750873638873299642555050473812528975962934822878917619920725138309388288292510416837622758204081918933603653875284116785703720989718832986921927816629675844580174911809119663048187434155067790863948831489241504300476704527971283482211522202837062857314244107823792513645086677566622804977211397140621664116324756784216612961477109018826094677377686406176721484293894976671380122788941309026553511096118347012565197540807095384060916863936906673786627209429434264260402902158317345003727462588992622049877121178405563348492490326003508569099382392777297498413565614830788262363322368380709822346012274241379036473451735925215754757160934270935192901723954921426490691115271523338109124042812102893738488167358953934508930697715522989199698903885883275409044300321986834003470271220020159699371690650330547577095398748580670024491045504890061727189168031394528036165633941571334637222550477547460756055024108764382121688848916940371258901948490685379722244562009483819491532724502276218589169507405794983759821006604481996519360110261576947176202571702048684914616894068404140833587562118319210838005632144562018941505945780025318747471911604840677997765414830622179069330853875129298983009580277554145435058768984944179136535891620098725222049055183554603706533183176716110738009786625247488691476077664470147193074476302411660335671765564874440577990531996271632972009109449249216456030618827772947750764777446452586328919159107444252320082918209518021083700353881330983215894608680127954224752071924134648334963915094813097541433244209299930751481077919002346128122330161799429930618800533414550633932139339646861616416955220216447995417243171165744471364197733204899365074767844149929548073025856442942381787641506492878361767978677158510784235702640213388018875601989234056868423215585628508645525258377010620532224244987990625263484010774322488172558602233302076399933854152015343847725442917895130637050320444917797752370871958277976799686113626532291118629631164685159934660693460557545956063155830033697634000276685151293843638886090828376141157732003527565158745906567025439437931104838571313294490604926582363108949535090082673154497226396648088618041573977888472892174618974189721700770009862449653759012727015227634510874906948012210684952063002519011655963580552429180205586904259685261047412834518466736938580027700252965356366721619883672428226933950325930390994583168665542234654857020875504617520521853721567282679903418135520602999895366470106557900532129541336924472492212436324523042895188461779122338069674233980694887270587503389228395095135209123109258159006960395156367736067109050566299603571876423247920752836160805597697778756476767210521222327184821484446631261487584226092608875764331731023263768864822594691211032367737558122133470556805958008310127481673962019583598023967414489867276845869819376783757167936723213081586191045995058970991064686919463448038574143829629547131372173669836184558144505748676124322451519943362182916191468026091121793001864788050061351603144350076189213441602488091741051232290357179205497927970924502479940842696158818442616163780044759478212240873204124421169199805572649118243661921835714762891425805771871743688000324113008704819373962295017143090098476927237498875938639942530595331607891618810863505982444578942799346514915952884869757488025823353571677864826828051140885429732788197765736966005727700162592404301688659946862983717270595809808730901820120931003430058796552694788049809205484305467611034654748067290674399763612592434637719995843862812391985470202414880076880818848087892391591369463293113276849329777201646641727587259122354784480813433328050087758855264686119576962172239308693795757165821852416204341972383989932734803429262340722338155102209101262949249742423271698842023297303260161790575673111235465890298298313115123607606773968998153812286999642014609852579793691246016346088762321286205634215901479188632194659637483482564291616278532948239313229440231043277288768139550213348266388687453259281587854503890991561949632478855035090289390973718988003999026132015872678637873095678109625311008054489418857983565902063680699643165033912029944327726770869305240718416592070096139286401966725750087012218149733133695809600369751764951350040285926249203398111014953227533621844500744331562434532484217986108346261345897591234839970751854223281677187215956827243245910829019886390369784542622566912542747056097567984857136623679023878478161201477982939080513150258174523773529510165296934562786122241150783587755373348372764439838082000667214740034466322776918936967612878983488942094688102308427036452854504966759697318836044496702853190637396916357980928865719935397723495486787180416401415281489443785036291071517805285857583987711145474240156416477194116391354935466755593592608849200546384685403028080936417250583653368093407225310820844723570226809826951426162451204040711501448747856199922814664565893938488028643822313849852328452360667045805113679663751039248163336173274547275775636810977344539275827560597425160705468689657794530521602315939865780974801515414987097778078705357058008472376892422189750312758527140173117621279898744958406199843913365680297721208751934988504499713914285158032324823021340630312586072624541637765234505522051086318285359658520708173392709566445011404055106579055037417780393351658360904543047721422281816832539613634982525215232257690920254216409657452618066051777901592902884240599998882753691957540116954696152270401280857579766154722192925655963991820948894642657512288766330302133746367449217449351637104725732980832812726468187759356584218383594702792013663907689741738962252575782663990809792647011407580367850599381887184560094695833270775126181282015391041773950918244137561999937819240362469558235924171478702779448443108751901807414110290370706052085162975798361754251041642244867577350756338018895379263183389855955956527857227926155524494739363665533904528656215464288343162282921123290451842212532888101415884061619939195042230059898349966569463580186816717074818823215848647734386780911564660755175385552224428524049468033692299989300783900020690121517740696428573930196910500988278523053797637940257968953295112436166778910585557213381789089945453947915927374958600268237844486872037243488834616856290097850532497036933361942439802882364323553808208003875741710969289725499878566253048867033095150518452126944989251596392079421452606508516052325614861938282489838000815085351564642761700832096483117944401971780149213345335903336672376719229722069970766055482452247416927774637522135201716231722137632445699154022395494158227418930589911746931773776518735850032318014432883916374243795854695691221774098948611515564046609565094538115520921863711518684562543275047870530006998423140180169421109105925493596116719457630962328831271268328501760321771680400249657674186927113215573270049935709942324416387089242427584407651215572676037924765341808984312676941110313165951429479377670698881249643421933287404390485538222160837088907598277390184204138197811025854537088586701450623578513960109987476052535450100439353062072439709976445146790993381448994644609780957731953604938734950026860564555693224229691815630293922487606470873431166384205442489628760213650246991893040112513103835085621908060270866604873585849001704200923929789193938125116798421788115209259130435572321635660895603514383883939018953166274355609970015699780289236362349895374653428746875

Neat. Even that last one only took a few seconds to return!

Aeson Revisited

As many of you know, the documentation situation in Haskell leaves something to be desired. Sure, if you are enlightened, and can read the types, you’re supposedly good. Personally, I prefer a little more documentation than “clearly this type is a monoid in the category of endofunctors”, but them’s the breaks.

Long ago, I wrote about some tricks I found out about using Aeson, and I found myself using Aeson again today, and I’d like to revisit one of my suggestions.

Types With Multiple Constructors

Last time we were here, I wrote about parsing JSON objects into Haskell types with multiple constructors. I proposed a solution that works fine for plain enumerations, but not types with fields.

Today I had parse some JSON into the following type:

data Term b a =
   App b [Term b a]
   | Var VarId
   | UVar a

I thought “I’ve done something like this before!” and pulled up my notes. They weren’t terribly helpful. So I delved into the haddocs for Aeson, and noticed that Aeson's Result type is an instance of MonadPlus. Could I use mplus to try all three different constructors, and take whichever one works?

instance (FromJSON b, FromJSON a)
         => FromJSON (Term b a) where
   parseJSON (Object v) = parseVar `mplus` parseUVar
                                   `mplus` parseApp
      where
         parseApp = do
            ident <- v .: "id"
            terms <- v .: "terms"
            return $ App ident terms
         parseVar = Var <$> v .: "var"
         parseUVar = UVar <$> v .: "uvar"
   parseJSON _ = mzero

It turns out that I can.

Making C++ Exceptions Less Terrible

If you’re a fan of doingmyprogramming, you’ve likely heard me opine on the subject of exceptions. If you’re new around here, I’ll spare you a link to some required reading and just let you know: they’re poop. With the exception of Java and it’s checked exceptions, they just represent secret ways that a function can crash your whole program. Just about nobody gets it right, not C++, not C#, and the worst offender is probably my beloved Haskell where you can’t even catch them unless you’re in the IO monad.

C++ used to have an annotation (throw()), where you could specify what exceptions a function throws, and if none are specified then the function cannot throw. This was considered poor form and deprecated long before I came on the scene. It turns out that there is good news though; throw() wasn’t forgotten! It was replaced by noexcept, and that is what we’ll be talking about today.

What is noexcept?

noexcept is an annotation that basically says “this function will never throw an exception”. You can think of it as being like const. If you some class method:

void myClass::isPure() const;

… then you know that, whatever it does, the state of the object will not be mutated. Similarly, if you see some function:

void neverThrows() noexcept;

… then you know that, whatever it does, the function will never throw an exception. Optimization implications aside, this is great because if you see a function declared noexcept, then you know for sure that you don’t have to put it in a try/catch block. If we ever start living in a world where people use this annotation, then a function not marked noexcept is a function that likely throws, and we can act accordingly without having to read through mountains of likely incorrect or incomplete documentation!

Specifically, the meaning of noexcept (according to Microsoft) is:

noexcept ( and its synonym noexcept(true)) specify that the function will never throw an exception or allow an exception to be propagated from any other function that it invokes either directly or indirectly. More specifically, noexcept means the function is noexcept only if all the functions that it calls are also noexcept or const, and there are no potentially evaluated dynamic casts that require a run-time check, typeid expressions applied to a glvalue expression whose type is a polymorphic class type, or throw expressions.

The Burning Quetion

So I read that blurb, and thought to myself: “…only if all the functions it calls are noexcept? So, I can’t catch all possible exceptions and be noexcept?”. I felt despair wash over me as C++ got something wrong yet again. Then I thought “there’s no way that’s correct… To the Googler!”

Of course, the Googler didn’t help my case. I decided to give it a shot. First, let’s consider two functions: one that throws and one that is noexcept:

static void doesThrow() noexcept(false)
{
  std::cerr << "Entering doesThrow..." << std::endl;
  throw 42;
  std::cerr
    << "Still in doesThrow. Up is down, cats and dogs living together!"
    << std::endl;
}

static void catchesAll() noexcept(true)
{
  std::cerr << "About to enter the try/catch..." << std::endl;
  try
    {
      doesThrow();
    }
  catch (...)
    {
      std::cerr << "Caught the exception..." << std::endl;
    }
  std::cerr << "Exited the try/catch..." << std::endl;
}

doesThrow is annotated noexcept(false), which is the same as saying “This function can throw an exception.” And sure enough, it throws in 100% of its code paths.

catchesAll is annotated noexcept(true), which is just the long form of noexcept. noexcept accepts arguments that evalutate to bool, and compile-time magic happens to allow conditional noexcept-ness. noexcept(expr) can also be used in an if/then/else to conditionally do something based on if some expr is noexcept.

In catchesAll, we have a try/catch block that prevents the exception thrown by doesThrow() from propagating out of catchesAll(). Does this work? Let’s write a test harness and see:

int main(int argc, char ** argv)
{
  std::cerr << "About to call catchesAll..." << std::endl;
  catchesAll();
  std::cerr << "Managed to not die!" << std::endl;
}

… if we compile it with gcc (with -std=c++11) and run it, we see that all is well!

About to call catchesAll...
About to enter the try/catch...
Entering doesThrow...
Caught the exception...
Exited the try/catch...
Managed to not die!

You may be wondering what happens if we don’t catch the exception. Let’s find out! If we remove the try/catch, but leave everything else the same:

About to call catchesAll...
About to enter the try/catch...
Entering doesThrow...
terminate called after throwing an instance of 'int'
Aborted (core dumped)

We see that the exception propagated out of catchesAll() and caused a core dump. This is the expected behavior. In fact, there’s no way we could have prevented this. If some function marked noexcept throws, then that function has a bug. If you wrote it, you have to fix it. If somebody else wrote it, then they have to fix it. There’s no band-aid that will keep it from crashing your program. If you find this happening often, then you should consider finding an alternative library that does what the broken dependency claims to do, since they clearly don’t know what they’re doing…

Operator Overloading in C++

My thoughts on Operator Overloading are hardly a secret. Some languages, such as Haskell, support it in a sane manner. Some languages, such as C++ don’t. Either way though, I’m not a fan.

That said, there is one case where I support it; when what you are trying to overload an operator to do makes sense for your type. In other words, if it makes sense to multiply an Employee object, feel free to overload the multiplication operator. Since we don’t usually model mating when we implement an employee object, I don’t usually approve.

Multiplying a Fraction

However, if we have a fraction class, that has a numerator and denominator component, overloading the multiplication operator suddenly becomes reasonable:

frac<T> operator *(const frac<T> & rhs) const
{
  return frac<T>(numer * rhs.numer, denom * rhs.denom);
};

In C++, many of the built in operators are available to be overloaded. You can do basically anything in an operator overload, but if you do, that makes you a bad person. Here we have a straightforward implementation, that I’m going to assume you don’t need to have explained to you. But let’s talk const correctness.

In this signature, the const appears twice. The right hand side argument is a const reference. Since this is a reference, no copy occurs, but with references can come mutability. The const here prevents any mutation from occurring. There is also a const at the end of the signature. That means that this function cannot modify the this pointer.

This function returns a new frac<t>, so no need for const there.

Convert a Fraction to a Double

Next, you can overload the casting operator, and if you are a good person you’ll use this for type conversions. Let’s implement (double) for our fraction:

operator double() const
{
  return (double) numer / denom;
}

This code is pretty straight forward. We divide the numerator by the denominator, and cast it to double in case integer division occurs. Cast operator overloads don’t have a return type, which is a bit strange but something we can work with.

Streaming operators

Finally, I’d like to talk about streaming operator overloads. For any overloaded operator, there are two forms: member and non-member. Member overloads take n - 1 arguments, where the minus 1 is the current object (and the left hand side). Non member overloads can’t access the this pointer, so they need to take the left hand side as a parameter.

Member overloads obviously have access to private class members, which makes them more powerful than non-member. Which leads us to the streaming operators. Streaming operators need to return std::ostream &, so they must be non-member. The problem is that we want to print the private numerator and denominator fields. The solution? make it a friend:

friend std::ostream & operator <<(std::ostream & lhs,
                                  const frac<T> & rhs)
{
  lhs << rhs.numer << '/' << rhs.denom;
  return lhs;
};

With that problem solved, this function becomes pretty straight forward. We stream the fields, formatted correctly, into the left hand side std::ostream &, then we return the left hand side argument for further use by the next part of the streaming chain.

Back in the Saddle with C++

Next quarter, I’ll be taking a graphics programming class. It was a year ago to the day that I last wrote about getting a makefile set up for OpenGL development. As you can imagine nothing came of it. Why? The obvious answer is that OpenGL is hard.

Secondary answers include the fact that almost all of the literature is assuming C++, and I was swimming against the tide trying to use C. Well, I won’t have a choice this time, the class is in C++, so I’m stuck with my old nemesis again.

What follows in the next few posts is an attempt to refamiliarize myself with C++. It’s been a while since I’ve done any significant work in C++ and a lot has happened. I’ll be going over a lot of basic stuff, so that I have a centralized crash course for myself when I’m stuck trying to remember if it’s const &, & const, & const &, or co&n&st (stranger things have happened).

Namespaces

First up: namespaces. Namespaces are a formalization of the c convention of writing functions called stuff like dmp_doStuff. First we can declare our namespace:

namespace dmp
{
   void doStuff()
}

…and we can call this function by doing dmp::doStuff(). This may involve an extra keystroke, but we can also use it like so:

using namespace dmp;

doStuff();
doStuff();
doStuff();

while (stuffUndone()) doStuff;

<Template> Classes

Now that we got that out of the way, let’s get into the meat of it: template classes. First up, due to some incredibly unfortunate reason, a C++ template class has to go in the header file. This sad fact is one of C++’s many transgressions against society, but we’ll not worry about that for now.

To declare a class (inside of a namespace if you’re a good citizen):

namespace dmp
{
  template <typename T> class frac
  {
  public:
  /* public stuff goes here */
  private:
    T numer;
    T denom;
  /* and your privates go here */
  };
}

template <typename T> would be omitted if this weren’t a template class. Here we declare a class frac with one generic type T. Our class has two private fields of type T. As we all know, class members are private by default, but I don’t like to rely on “default behaviors”, so it doesn’t hurt to make it explicit. Let’s add some public constructors:

    frac(T inNumer, T inDenom)
      : numer(inNumer), denom(inDenom)
    {};

    frac(const frac<T> & toCopy)
      : numer(toCopy.numer), denom(toCopy.denom)
    {};

Here we use initializer lists to populate the numerator and denominator. The first constructor takes two arguments of the same type (T), and the second is the copy constructor.

According to Microsoft, initializer lists are more efficient than assignment in the function body, which is why we prefer them here. There are certain cases where you must use an initializer list, and cases where you cannot use them. Your compiler will tell you if you mess this up.

Finally, let’s add a destructor:

    ~frac()
    {};

Here we have a marvel of software engineering. Since we really don’t have anything to destroy, we can let it do nothing. It should be noted that this destructor is not virtual, so it’s not really safe to extend this class (more on this another day).

Conclusion

Honestly, namespaces and constructors/destructors are two of my favorite features of C++. Simple, but helpful in eliminating boilerplate. I almost might be convinced to compile “C” with a C++ compiler to get these features. Coming up will be some features that I’m a bit more iffy about, such as operator overloading. however, when used appropriately, these things can also be good, more to come!

Pretty Printing our Pretty Program with Pretty

Tell me if you’ve heard this one before. You’re making some complicated data structure in Haskell. Something like the following:

data Expr =
   EVal Int
   | EIdent String
   | EFunc String [String] [Expr]
   | ECall String [Expr]
   | ELet String Expr
   | EWhile Expr [Expr]
   | EShizzy Expr Expr Expr
   | EIfElse Expr Expr Expr
   | EReturn Expr
     deriving (Show)

You throw that deriving (Show) because it’ll totally help you debug! Time goes by, and you use your fancy Expr to write a robust imperative function:

test = EFunc "testFunc" ["gatito",
                         "moogle"]
       [ELet "foo"
        $ ECall "petCat" $ [EIdent "gatito",
                            EIdent "moogle"],
        EWhile (ECall "catsPlacated" [])
        [EShizzy
         (EIfElse
          (EVal 5)
          (ELet "foo"
           $ ECall "malloc" [ECall "sizeof" [EVal 2]])
          (ECall "petCat" $ [EIdent "gatito",
                             EIdent "moogle"]))
         (ECall "petCat" $ [EIdent "gatito",
                            EIdent "moogle"])
         (ELet "foo" $ ECall "safeLeakMemory" [])
        ],
        EReturn $ EIdent "foo"
       ]

You’re still good, you got Rainbow Delimiters to keep that all sorted. Now, more time goes by and you’re in the repl and something doesn’t work. What was this test thing again?

*Shizzy> test
EFunc "testFunc" ["gatito","moogle"] [ELet "foo" (ECall "petCat" [EIdent "gatito",EIdent "moogle"]),EWhile (ECall "catsPlacated" []) [EShizzy (EIfElse (EVal 5) (ELet "foo" (ECall "malloc" [ECall "sizeof" [EVal 2]])) (ECall "petCat" [EIdent "gatito",EIdent "moogle"])) (ECall "petCat" [EIdent "gatito",EIdent "moogle"]) (ELet "foo" (ECall "safeLeakMemory" []))],EReturn (EIdent "foo")]

Well that’s unfortunate. What do we do now? Aside from the fact that this is completely useless to us, this certainly wouldn’t be OK to print out to a user…

The good news is that pretty printing is a snap thanks to the HughesPJ Pretty Printer. One simply has to implement the Pretty class for one’s type, and then they can get some reasonable output:

testFunc(gatito moogle) {
  let foo = petCat(gatito moogle)
  while(catsPlacated()) {
      +--
          {
            if (5) let foo = malloc(sizeof(2))
            else petCat(gatito moogle)
          }
      +++
      + +
      +++
    {
      petCat(gatito moogle)
    }
      +++
      + +
      +++
          {
            let foo = safeLeakMemory()
          }
      +--
  }
  produceResult foo
}

Let’s see how we get there, constructor by constructor.

EVal and EIdent

First up are the easy ones: EVal and EIdent, which represent bare values:

instance Pretty Expr where
   pPrint (EVal v) =
      int v
   pPrint (EIdent s) =
      text s

First we have to declare our instance, but next we can just print the values. int pretty prints an integer, and text pretty prints a string.

EFunc and ECall

Next we have function calls and definitions:

   pPrint (EFunc n a b) =
      text n
      <> (parens $ hsep $ fmap text a) <+> lbrace
      $+$ (nest 2 $ vcat $ fmap pPrint b)
      $+$ rbrace
   pPrint (ECall n a) =
      text n <> (parens $ hsep $ fmap pPrint a)

There are some operators here that require explanation. All of these operators have type (Doc -> Doc -> Doc ), and are used to combine two Doc into one. A Doc is the type of thing that can be pretty printed, which is returned by calls to pPrint and various other primitive pretty printing functions provided by the library (like text and int)

<> glues the thing on the left next to the thing on the right with no space in between, where <+> does the same, but leaves 1 space in between. Similarly, $$ and $+$ glues the thing on the right to the bottom of the thing on the left. $+$ allows the right hand side to overlap with the left (more on this later). There are also hsep, and vcat which takes lists of Doc. These functions work similarly to <>, $$ and friends; they glue Docs together horizontally and vertically. *cat are the non-plus variants, and *sep are the plus variants.

Other functions introduced here are parens, which takes a Doc and surrounds it by parens. lbrace and rbrace insert { and } respectively. There is a braces function as well, but I didn’t use it because I want to control how the braces are shown. Finally, we have nest, which indents its argument. This function is great because it takes into account outer nest calls, so we can get arbitrary nesting.

ELet, EWhile, EIfElse, and EReturn

   pPrint (ELet n e) =
      text "let" <+> text n <+> equals <+> pPrint e
   pPrint (EWhile p b) =
      text "while" <> (parens $ pPrint p) <+> lbrace
      $+$ (nest 2 $ vcat $ fmap pPrint b)
      $+$ rbrace
   pPrint (EIfElse p t f) =
      text "if" <+> (parens $ pPrint p) <+> pPrint t
      $+$ text "else" <+> pPrint f
   pPrint (EReturn v) =
      text "produceResult" <+> pPrint v

Nothing particularly fancy here. in ELet, we have equals which inserts an equals sign and we have more nesting throughout. As you can see, this is very simple once you get the hang of it; there are few abstract instances involved, and most functions do what they say.

EShizzy

As we all know, any programming language that doesn’t have Shizzy statements isn’t worth knowing, so of course I implement them:

   pPrint (EShizzy u d t) =
      onFire
      $+$ (nest 6 (lbrace $+$ (nest 2 (pPrint u)) 
                          $+$ rbrace))
      $+$ noRules
      $+$ (lbrace $+$ (nest 2 (pPrint d)) $+$ rbrace)
      $+$ noRules
      $+$ (nest 6 (lbrace $+$ (nest 2 (pPrint t)) 
                          $+$ rbrace))
      $+$ onFire
      where
         onFire = nest 2 $ text "+--"
         noRules = nest 2 $ (text "+++" $$ text "+ +" 
                                        $$ text "+++")

This produces the following output as we’d expect:

      +--
          {
            if (5) let foo = malloc(sizeof(2))
            else petCat(gatito moogle)
          }
      +++
      + +
      +++
    {
      petCat(gatito moogle)
    }
      +++
      + +
      +++
          {
            let foo = safeLeakMemory()
          }
      +--

and this gives me a good opportunity to demonstrate the difference between $$ and $+$. Let’s swap all the plus variants out:

      onFire
      $$ (nest 6 (lbrace $$ (nest 2 (pPrint u)) 
                         $$ rbrace))
      $$ noRules
      $$ (lbrace $$ (nest 2 (pPrint d)) 
                 $$ rbrace)
      $$ noRules
      $$ (nest 6 (lbrace $$ (nest 2 (pPrint t)) $$ rbrace))
      $$ onFire
      where
         onFire = nest 2 $ text "+--"
         noRules = nest 2 $ (text "+++" $$ text "+ +" 
                                        $$ text "+++")

Now, the pretty printer outputs the following:

  +-- { if (5) let foo = malloc(sizeof(2))
        else petCat(gatito moogle)
      }
  +++
  + +
  +++
{ petCat(gatito moogle)
} +++
  + +
  +++ { let foo = safeLeakMemory()
      }
  +--

Basically, if something is nested far enough that it would appear after the end of the left hand side argument, it is pasted to the right of it instead of below it. Honestly, it’s pretty strange behavior to me, I say just avoid $$ for the most part and you’ll be fine. It’s not a huge stretch for me to think of a use for this, but I think I’d just use <> or <+> if I wanted this to happen.

Regardless, I’ve worked on projects that use this pretty printing library before, and now that I’ve given it a shot I know why!

Into The (Local) Cloud!

I, and I’m sure many of you use Github. If not, and you care to get started, I’ve written about this before. However, sometimes you don’t want to work in the open. If this is the case, then you likely aren’t going to be using Github. Sure, you can pay for private repos, or you can use alternatives like Bitbucket that provide free private repos. Personally, I prefer to keep my private things out of The Cloud (TM).

I have a headless computer hooked up to my home network running Debian that I use as a file server. I find it convenient to have my various projects that aren’t on Github in git repositories on my server. It provides a backup, and makes it easy to keep my desktop and laptop in sync. So, let’s talk about that.

Making The Repository

This is a pretty straightforward process. Much like the usual ways of making a local repository, we’ll be using git-init, however, we need to create a bare repository, otherwise we’ll have issues pushing and pulling. To do this, enter the following in the directory on the server where you want the repository to live:

git init --bare [repo_name]

Where [repo_name] is the name of the repository. A folder with this name will be created in the current directory.

This repository is special; you cannot work directly in it, you must clone and use push/pull.

Meanwhile, on Our Workstation

Back on the machine where we’ll be working, we first need to clone our newly created repository:

git clone [username]@[server]:[path_to_repo]

Here, [username] is your user on the server that has SSH access, [server] is the IP address or hostname of the server, and [path_to_repo] is the location of the repo on the server. When you do this, you’ll get a warning about cloning an empty repo which you can ignore. After all, of course it’s empty, you just made it!

…and guess what? That’s all there is to it! You can push and pull as normal at this point, and should be ready to go.

But DMP Guy, I Already Have A Repo!

So, you already got a repo, and you want to move it to a central server? This isn’t much more difficult. First, get the repo itself to the server somehow. I recommend SFTP:

sftp [username]@[server]
sftp> put [compressed_repo]
sftp> bye

Where [username] is an account and [server] is the server and [compressed_repo] is your repo directory compressed in your favorite manner.

After this is done, ssh to the server, then find and uncompress the repo. Next we make a bare repo out of it:

git clone --bare [orig_repo] [bare_version]

Here, [orig_repo] is the original repo that you just extracted, and [bare_version] is the name you want to give the new bare version. After this is done, you can rm -rf [orig_repo], and then clone and use [bare_version] as described above.