Category: Compiler

Posted on

Dear string-to-integer parsers…

These are very useful functions that any language with distinct string and integer types will include in their standard library. Pass in a string with decimal digits and it’ll return the equivalent in the binary integer form that you can do mathematics with.

I’d like to make a modest proposal that I’d find very useful, and maybe you, dear reader, would too.

“The rich man in his castle, the poor man at his gate. He made them, high or lowly, and ordered their estate.”

Who me?

Specifically, I’m thinking of parser functions that work like this…

ParseInt("123");      // 123.
ParseInt("-456");     // -456.
ParseInt("Rutabaga"); // Rejected.

Note that by “rejected”, it could mean anything in practice as long as the response is distinct from returning a number. Maybe it throws an exception, maybe it returns null, maybe it also returns a Boolean to tell you if the string value was valid or not.

Point is, I’m thinking of parser functions that have two distinct kinds of result. A success result that includes the integer value, or a rejection result. No half-way results.

I will acknowledge that there are standard library functions that will keep going along the string gobbling digits, until it hits a non-digit and the response tells the caller what number it found and where that first non-digit is. Those are very useful for tokenizing loops as part of compilers, but my idea would break that interface too much. If that’s your variety of parser, sorry, but this post isn’t for you.

Also, I’m thinking of functions that parse as decimal. Maybe you have optional flags that allow you to specify what base to use, but it parses as decimal by default. I’m concerned only with the decimal mode of operation.

Round Numbers and “E” Notation

You might be familiar with “E” notation if you work with very large or very small floating point numbers. This is a shorthand for scientific notation where the letter E translates to “times ten to the power of”.

FloatParse("1E3");    // 1000.0
FloatParse("5E-3");   // 0.005
FloatParse("1E+100"); // One Googol.

This notation is handy for decimal round numbers. If you want to type in a billion, instead of having to count as you press the zero key on your keyboard over and over, you could instead type “1E9”. Which one of the following numbers is a billion? Can you tell at a glance?

100000000 10000000000 1000000000

The problem is that E notation is stuck in the floating-point world. I’d really like it if anywhere I could type an integer (such as in an electronic form) and I want to type a large round number, I could use E notation instead.

For that to work, the functions that convert strings to integers need to allow this.

Pinning it down

Okay, we’re all software engineers here. Let’s talk specifics.

If the string supplied to the function is of the form (mantissa)"E"(exponent), with the mantissa in the range 1-9 and the exponent from zero to however high your integer type gets, then instead of rejecting the string, return the integer value this E notation string represents.

Add the usual range checks (for example, 9E18 for a signed 64-bit integer) and do the right thing when there’s a minus sign character at the start and we’re done.

“But there might be code depending on values like that being rejected!”

That’s a fair concern. I am advocating for a change in behaviour in the standard library after all.

I am seeking only to change behaviour in the domain of inputs that would otherwise produce a rejection response.

If IntParse("1E3") used to return a rejection, but now it returns 1000, is that a bad thing? The user can already type "1000" but this time they wrote "1E3" instead. What’s the harm in carrying on as if they typed 1000 all along?

I can think of some pathological cases. Maybe the programmer wanted to limit an input to 1000, but instead of using the less-than operator on the integer like a normal person, they check that the length of the string less than 4. "1E9" would pass validation but a billion would be returned. It seems unlikely that anyone would do that in practice.

The parser function might be used not to actually use the integer returned, but instead act as a validator. You have a string and you want to know if the string is a valid sequence of decimal digits or not. If that’s what you need, the integer-parser is maybe the wrong tool for that. Parsers will already be a little flexible about the range of allowable inputs, allowing leading plusses or zero digits and commas grouping digits into triples. If you care that a string is actually the one canonical ASCII representation of a number or not, then I would follow the parse with a test converting the integer back into a string and checking it matches the input string.

“E might be a hex digit.”

Your function returns the number 7696 for the input "1E10" and not ten billion? What you’ve got there is a hex parser, not a decimal parser. E notation only make sense in the world of decimal numbers.

If your decimal parser automatically switches to hex parsing if it sees ‘A’ to ‘F’ characters, then you’ve got a parser that’s unreliable for hex number strings. A lot of hex numbers contain only the ‘0’ to ‘9’ digits. If my code gets a hex number as input, I’m going to call the hex parser. Some supposed general purpose parser isn’t going to know if "1000" should return 1000, 4096 or 8 and will need to be told.

While we’re on the subject of hex numbers, I may be following this up with a proposal that “H” should mean “times 16 to the power of” in a similar style, but that’ll be for another day.

 “Delores, I live in fear. My love for you is so overpowering. I’m afraid that I will disappear.”

“Because counting to nine is really hard”

So there’s my suggestion. In short, I’m fed up of having to count to nine when I want to type a billion and having to check by counting the little row of identical ovals on the screen. I look forward to comments telling me how wrong I am.

Picture Credits
📸 “Swift” by Tristan Ferne. (Creative Commons.)
📸 “Kibo Summit, Mount Kilimanjaro, Tanzania” by Ray in Manila. (Creative Commons.)

(Also, a billion is a one followed by nine zeros. Anyone who says it has twelve zeros is quite wrong.)

Posted on

I want a less powerful programming language for Christmas.

I’m writing this because I’m hoping someone will respond, telling me that what I want already exists. I have a specific itch and my suspicion is that developing a whole programming language and runtime is the only way to scratch that itch.

Please tell me I’m wrong.

Dear Father Christmas…

If you’ve ever written a web service, you’ve almost certainly had situations where you’ve taken a bunch of bytes from a completely untrusted stranger and passed those bytes into a JSON parser. What’s more you’ll have done that without validating the bytes first.

Processing your inputs without sanitizing it first? Has Bobby Tables taught us nothing?

You can do this safely because that JSON parser will have been designed to be used in this manner and will be safe in the face of hostile inputs. If you did try feeding the bytes of an EXE file into a JSON parser, it’ll very quickly reject it complaining that “MZ” isn’t an opening brace and refuse to continue beyond that. The worst a hostile user could do is put rude messages inside the JSON strings.

{ "You": "A complete \uD83D\uDC18 head!" }

Now take that idea and think about what if you did have a web service where completely unauthenticated users could use any request body they liked and your service would run that request body in a copy of Python as the program source code.

Hopefully, you’ve just now remarked that it would be a very bad idea, up there with Napoleon’s idea to make his brother the King of Spain. But that’s exactly what I want to do. I want to write a web service that accepts Python code from complete strangers and actually run that code.

(And also make my brother the King of Spain. He’d be great!)

“Hang on to your hopes, my friend. That’s an easy thing to say. But if your hopes should pass away, simply pretend that you can build them again.”

At the gates of dawn

Some time in the early 90s, I had a game called “C Robots”.

This is a game where four tanks are in an arena, driving around and firing missiles at each other. But instead of humans controlling those tanks, each tank was controlled by a program written by the human player. The game controller would keep track of each tank and any missiles in flight, passing back control to each tank’s controller program to let it decide what its next move will be.

For 90s me, programming a robot appealed to me but the tank battle part did not appeal so much. I really wanted to make a robot to play other games that might not involve tanks. At the time, there were two games I enjoyed playing with school friends, Dots-and-Boxes and Rummy. I had an idea of what made good strategies for these specific games, so I thought building those strategies into code might make for a good intellectual exercise.

Decades passed and I built a simple game controller system which I (rather pompously) called “Tourk“. I had made a start on the controllers for a handful of games but I hadn’t gotten around to actually writing actual competitive players, only simple random ones that were good for testing. I imagined that before long, people would write their own players, send them in to me and I’d compile them all together. After I’d let it ran for a million games in a tournament I’d announce the winner.

If anyone had actually written a player and sent it in, my first step would have been to inspect the submitted code thoroughly. These would have been actual C programs and could have done anything a C program could do, including dropping viruses on my hard disk, so inspecting that code would have been very important. Looking back, I’m glad no-one actually did that.

But this was one thing C Robots got right, even if it wasn’t planned that way. Once it compiled the player’s C code, it would run that code in a restricted runtime. Your player code could never go outside its bounds because there’s no instructions in the C Robots runtime to do that. This meant that no-one could use this as an attack vector. (But don’t quote me on that. I’ve not actually audited the code.)

“I never ever ask where do you go. I never ever ask what do you do. I never ever ask what’s in your mind. I never ever ask if you’ll be mine.”

Will the runtime do it?

Could maybe the dot-net runtime or the Python runtime have the answer?

This was one of the first questions I asked on the (then) new Stack Overflow. The answer sent me to Microsoft’s page on “Code Access Security” and if you follow that link now, it says this feature is no longer supported.

Wondering more recently if Python might have an option to do what I wanted, I asked on Hacker News if there was a way to run Python in the way I wanted. There were a few comments but it didn’t get enough up-votes and disappeared fairly quickly. What little discussion we had was more to do with a side issue than the actual question I was asking.

I do feel that the answer might still be here. There’s quite possibly some flag on the runtime that will make any call to an extern function impossible. The Python runtime without the “os” package would seem to get 90% of the way there, but I don’t know enough about it to be certain enough that this won’t have left any holes open.

“We’re all someone’s daughter. We’re all someone’s son.”

Sanitize Your inputs?

Maybe I should listen to Bobby Tables and sanitize my inputs before running them.

Keep the unrestricted runtime, but before we invoke it to run the potentially hostile code, scan it to check it won’t do any bad things.

Simple arithmetic in a loop? That’s fine.
Running a remote access trojan? No.

Once it has passed the test, you should be able to allow the code to run, confident it won’t do anything bad because you’ve already checked it won’t. This approach appeals to me because once that initial test has passed the code for non-hostility, we can allow the runtime to go at full speed.

The problem with this approach are all the edge cases and finding that line between simple arithmetic and remote-access-trojans. You need to allow enough for the actually-not-hostile code to do useful things, but not enough that a hostile user could exploit.

Joining strings together is fine but passing that string into eval is not.
Writing text to stdout is fine but writing into a network socket is not.

Finding that line is going to be difficult. The best approach would be to start with nothing-is-allowed, but when considering what to add, first investigate what would be possible by adding that facility to allowed list. Because it can be used for bad things, eval would never be on that allowed list.

If there’s a function with a million useful things it can do but one bad thing, that function must never be allowed.

“We can go where we want to. A place they’ll never find. We can act like we come from out of this world and leave the real one far behind.”

Ask the Operating System?

I told a colleague about this post while I was still writing it and he mentioned that operating systems can have restrictions placed on programs it runs. He showed me his Mac and there was a utility that listed all the apps he was running and all the permissions it had. It reminded me that my Android phone does something similar. If any apps wants to interact with anything outside its realm, it has to ask first. This is why I’m happy to install apps on my Android phone but not on my Windows laptop.

This would be great, but how do I, a numpty developer, harness this power? What do I do if I want to launch a process (such as the Python runtime) but with all the permissions turned off? It feels like this will be the solution but my searching isn’t coming up with a practical answer.

My hope is that there’s a code library whose job it is to launch processes in this super restricted mode. It’ll work out which OS it is running on, do the necessary magic OS calls and finally launch the process in that super-restricted mode.

“If I was an astronaut I’d be floating in mid air. A broken heart would just belong to someone else down there. I would be the centre of my lonely universe. I’m only human and I’m crashing in the dark.”

Mmmm coffee!

The good people developing web browsers back in the 90s had the same need as me. They wanting to add a little interactivity to web pages, but without having to wait for a round trip back to the server over dialup, so they came up with a language they named JS.

As you read this page, your browser is running some code I supplied to you. That code can’t open up your files on your local device. If anyone did actually find a way to do that, the browser developers would call that a serious bug and push out an emergency update. So could JS be the solution I’m looking for?

As much as it sounds perfect, that JS runtime is inside the browser. If I have some JS code in my server process, how do I get that code into a browser process? Can I even run a web browser on a server without some sort of desktop environment?

The only project I know of where someone has taken JS outside of a browser is node-js. That might be the answer but I have written programs using node-js that load and save files. If this is the answer then I’d need to know how to configure the runtime to run the way I want.

“Play the game, fight the fight, but what’s the point on a beautiful night? Arm in arm, hand in hand. We all stand together.”

Is there an answer?

I began this post expressing my suspicion that the solution is to write my own runtime, designed from first-principles to run in a default-deny mode. I still wonder if that’s the case. I hope someone will read this post and maybe comment with the unknown option on the Python runtime that does exactly what I want.

In the meantime, I have another post in the works as with my thoughts on how this runtime and programming language could work. I hope I can skip it.

Gronda-Gronda.

Picture Credits
📸 “Snow Scot” by Peeja. (With permission.)
📸 “Meeting a Robot” by my anonymous wife. (With permission)
📸 “Great Dane floppy ears” by Sheila Sund. (Creative Commons)
📸 “Fun with cling film” by Elizabeth Gomm. (Creative Commons)
📸 “Rutabaga Ball 2” by Terrence McNally. (Creative Commons)
📸 “Nice day for blowing the cobwebs off” by Jurassic Snark. (With permission.)

(And just in case advocating for your brother to be made King of Spain is treason or something, I don’t actually want to do that. It was a joke.)

Posted on

Construct something else! (C#)

Please read my follow-up post after reading this one.

Quoth rjw on stackoverflow…

Given the following client code:

    var obj = new Class1();

Is there any way to modify the constructor of Class1 so that it will actually return a subclass (or some other alternate implementation) instead?

C# compiler guru, Eric Lippert commented…

We are considering adding a feature “extension new” which would essentially allow you to make a static factory method that would be called when the “new” operator is used, much as extension methods are called when the “.” operator is used. It would be a nice syntactic sugar for the factory. If you have a really awesome scenario where this sort of pattern would be useful, I’d love to see an example.

I have one!

Version one of our DLL had a class that wrapped a connection to a remote server.

    using (var connect = new ExampleConnection("service.example.com"))
    {
        connect.DoStuff(42);
    }

It worked great. Our customers were very happy with it and developed lots of code to use our little DLL. Life was good.

Time passes and our customers ask us to add support for a different type of server that does a similar job but with a very different protocol. No problem, we develop a new class called DifferentConnection and just to be helpful, both ExampleConnection and DifferentConnection implement a common interface object.

We’re about to release version two to our customers, but a common response comes back;

“This is good, but we were hoping your library would automatically detect which variety of server it’s talking to. Also, we really don’t want to change our code. We want to just drop your updated DLL into the install folder, but we’ll recompile our EXE if we really have to.”

With these new requirements, ExampleConnection had to become a class that supported both varieties of remote server. The constructor has to perform the auto-detect, and all of the public functions now all begin with an if statement, selecting for which variety of remote server is in use.

If we had a bit more foresight, we should have supplied a static Connect function that wrapped a private constructor. That way, version two of this function could have returned a subclass object instead. But we didn’t. There are costs to writing code that way, so you wouldn’t do it unless there was a clear point to it. If a normal constructor could return a subclass instead, there would be no problem.

Mr Lippert, I hope this provides the justification you need to add this to .NET 5, but I’d much rather have destructors on structs instead. I also want a pony.

Picture credit: ‘LEGO Mini Construction Site’ by flickr user ‘bucklava’.
(I don’t really want a pony.)

UPDATE: Someone submitted this to reddit. Lots of discussion there.
UPDATE(2): Follow-up post.

Posted on

Wishing for a destructor (C#)

 

I like the C# programming language. It feels like C++ done right, divesting itself of much of the C legacy that complicates matters so much. When I do programming, I prefer to use this language. Having to go back and deal with C++ just doesn’t give me that warm feeling like it used to.

But, I have a pet peeve that I miss from C++.

Choose… Choose the form of the Destructor!

Quick recap. Here’s a brief C++ function…

 void MyFunction()
 {
    string x;
    MyOtherFunction(x);    /* Pass by value. */
 }

Doesn’t look like much is going on, but there’s five function calls in there.

  1. A constructor function is called to build x.
  2. A copy constructor function is called to copy x for the function call.
  3. ‘MyOtherFunction’ is called.
  4. A destructor function is called to tidy up the copy of x.
  5. The same destructor function is called to tidy up x itself.

The clever bit is that the compiler has worked out when objects go “out of scope” and inserted calls to that’s objects destructor function in exactly the right place. Even “anonymous” objects are tidied up. Say a function is called that returns an object, but the caller just ignores the return value. The compiler spots it and inserts the destructor call in just the right place.

C# doesn’t do this. Instead, from the very beginning of the language, unused objects are “garbage collected”. Every so often, some code will run that goes over everything built by the program and sees if its being used anywhere. Anything that can’t be traced to running code is removed. Doing it this way allows the programmer to share objects between two different areas of code, without having to worry about which one has responsibility for tidying up.

I imagine that when the very clever people at Microsoft designed the C# language, they had already decided to use garbage collection, and so concluded that this messing about with destructors was no longer needed. No need to insert a function call into code, just leave the object lying around and the garbage collector will deal with it.

This would all great if memory was the only resource we have to keep track of. Open file handlers, database connections, etc. All must closed in a deterministic manner, instead of at some unknown time in the future when memory is about to run out.

Microsoft didn’t leave us completely out on the branch, classes that need to be tidied up can be written to implement the IDisposable interface. This allows the using block to work.

 using (SqlConnection con = new SqlConnection(db))
 {
    /* Use con. */
 } /* Dispose con. */

With the using block, just like with the C++ destructors shown above, the compiler inserts a call to the tidy-up function at the end of the block. Even if there’s a return or throw statement in the middle, it’ll make sure everything is tidied up when the code leaves the using block.

But why have the using block at all? If you forget to include the using block, the tidy-up code won’t be called (unless you invoke it manually) and you won’t even get a compiler warning. (You don’t get the warning for very good reasons which I won’t go into right now.)

Even when you use using correctly, adding a using block to a function means introducing an additional block, with all the block-visibility issues and additional indenting that implies.

Structs to the rescue

Fortunately, C# and .NET come with a type of object called structs. These are similar to classes except they are solid value types rather than references to data floating in the ether. The practical difference is that when a struct value is copied (such as when passed into a function as a parameter) and you change the value of the one of the copies, the other copy stays the same.

In contrast, when you copy a class value, you’re instead just making a copy of the reference, so both point to same data. Change the contents of one, and the other changes value too, because there is no “other”.

So what if, when a struct appears in code, it came with an automatic using block attached? That way, we could open files or database connections just by introducing one in code and it would be tidied up in a deterministic way.

To complete the job, we would need mechanisms to support copy constructors and assignment as well as the final destructor call, just like the C++ people are used to.

I’ve been nursing this peeve and whining about it for so long that I’m even boring myself. I plan this to be my last word on the topic and in future I’ll just post links to this article. Enjoy.

Picture credits
“staypuft_3feb2009_0621” by patrick h. lauke on flickr
“choose determinism” by alyceobvious on flickr
“John E. Cox Memorial Bridge” by Elizabeth Thomsen on flickr

Posted on

is, then as (C#)

The C# language has a pair of related operators, is and as. Say you have an object, x, and you want to know if its really type Form underneath.

(x is Form) will be true if it is, or false if it isn’t. The as operator will actually perform the conversion, returning null if it can’t be converted to that type.

One common piece of advice to C# programmers is to avoid using the is operator. Here’s how both of these operators are typically used together.

    if (x is Form)
    {
        Form frm = x as Form;
        /* Use frm. */
    }

While the code works, all the is operator is doing is performing an as operation, and checking if the result is null or not. In other words, (x is Form) is equivalent to (x as Form != null). This means the code above is really saying…

    if (x as Form != null)
    {
        Form frm = x as Form;
        /* Use frm. */
    }

See that. The same as operation was done twice. What a waste! So, the standard advice is to re-write the code to use just one as operation.

    Form frm = x as Form;
    if (frm != null)
    {     
        /* Use frm. */
    }

Simple. So what’s the point of this article? Why use is at all?

The problem for me is that is just looks so darn nice. Beginners very quickly understand what’s going on when they see it. The re-written code that checks for null just doesn’t look as pretty and isn’t as obvious what’s going on.

You may be wondering what the cost of this additional operation is. I knocked together a quick test which looped is-then-as and then looped the optimized version the same number of times and reported the difference in time. When I increased the count to 100,000,000, I saw approx one second difference build up. That’s a lot of looping.

But hey, that cost is non-zero, and I’m wondering why. Compilers are pretty good these days. I recall advice from long ago that its better to use an XOR operation to check if two values are equal, or to use shift operations instead of multiplying. These days, best practice to write what you mean and leave micro-optimizations to the compiler. So why doesn’t Microsoft’s C# compiler optimize is-then-as into a single operation?

I don’t know. It could be that its not worth the development team’s time, or maybe there’s a subtle reason that escapes me right now. I wish I knew. But if we could eliminate the repeated operation and use is freely, code would be lot nicer to look at.

Picture credit: Fruit balance by Pickersgill Reef.
Many thanks to Eric Lippert and the commentators to his article that inspired this piece.
Update 18/Jan/2010: Introduction modified to be better understood by non C# programmers. (Thanks Andrew.)