HNHacker News
TopNewBestAskShowJobs

sjolsen

390 karma · joined April 17, 2014

submissionscomments
sjolsen··on Why Lisp macros are cool, a Perl perspective (2005)
> Another place where macros in Lisp fail is that they may evaluate an expression twice

Strictly speaking, macros don't evaluate their expressions at all.

Square is a bad example, though. Macros are not for writing function-like expressions; they're for extending (or more generally transforming) the syntax of the language. Inline functions and compiler macros are more appropriate tools for things like square.

sjolsen··on Why Lisp macros are cool, a Perl perspective (2005)
> In Lisp, source filters never break.

> Never.

To be perfectly fair, this is not quite true. In Common Lisp (the dialect being used here), macros can break in rare, subtle ways. The obvious happens when you don't use GENSYM:

    (defmacro foo (var)
      `(let* ((x 3))
         (setf ,var x)))
    
    CL-USER> (let ((x 7))
               (foo x)
               x)
    7
    
    CL-USER> (let ((y 7))
               (foo y)
               y)
    3
but is fairly easy to avoid. In practice, as long as you make judicious use of GENSYM and packages, the only thing you really need to worry about is someone FLETing a symbol in the package COMMON-LISP (or maybe an external symbol in your package):

    (defmacro bar (x y z)
      `(list ,x ,y ,z))
    
    CL-USER> (let ((list '(7)))
               (bar 1 2 3))
    (1 2 3)
    
    CL-USER> (flet ((list (a b c)
                      (+ a b c)))
               (bar 1 2 3))
    6
SBCL actually yelled at me when I tried this for violating the package lock on COMMON-LISP. So in practice, it's really not much of an issue, and is certainly a hell of a lot better than C macros.

If you're interested in learning more about this, look at Scheme's hygienic macros.

sjolsen··on Learn You an Agda
> What's the distinction between C-c C-space and C-c C-r?

Beats the hell out of me. Here's the docstring for agda2-give (bound to C-c C-SPC):

    Give to the goal at point the expression in it
Here's the one for agda2-refine (C-c C-r):

    Refine the goal at point.
    If the goal contains an expression e, and some "suffix" of the
    type of e unifies with the goal type, then the goal is replaced
    by e applied to a suitable number of new goals.
    
    If the goal is empty, the goal type is a data type, and there is
    exactly one constructor which unifies with this type, then the
    goal is replaced by the constructor applied to a suitable number
    of new goals.
sjolsen··on Learn You an Agda
That should read, "Type the following into the Emacs buffer." You should have something like:

    module LearnYouAn where
    
      data ℕ : Set where
        zero : ℕ
        succ : ℕ → ℕ
    
      _+_ : ℕ → ℕ → ℕ
      zero + m = m
      (succ n) + m = succ (n + m)
    
      data _even : ℕ → Set where
        ZERO : zero even
        STEP : ∀ n → n even → succ (succ n) even
    
      proof₁ : succ (succ (succ (succ (zero)))) even
      proof₁ = ?
sjolsen··on Gangnam Style breaks YouTube viewer count
It is not used literally everywhere. It does not always "just work," as the original post demonstrates. It often happens to be good enough for most practical purposes, yes, but arbitrary-precision arithmetic is better for most practical purposes.

Fixed-precision arithmetic has one main advantage over arbitrary-precision arithmetic: it is more time- and space-efficient. This advantage only applies if the fixed-precision arithmetic is actually correct and the fixed-precision arithmetic meets some concrete time or space constraint which arbitrary-precision arithmetic fails to meet. It generally takes time and effort to demonstrate that these conditions hold; because one can rely on the correctness of arbitrary-precision arithmetic without doing so, arbitrary-precision arithmetic should then generally be the default choice.

This assumes that you care about making relatively strong guarantees about the correctness of your programs. If for some reason you don't, then sure, use ints and whatnot for everything. If you do, though, I suspect you'll find that it's easier to track down a performance bottleneck caused by using bignums than an obscure bug triggered by GCC applying an inappropriate optimization based on overflow analysis.

sjolsen··on Gangnam Style breaks YouTube viewer count
All arithmetic in C and C++ is toxic. That's the reality of using bounded-precision types. Honestly, I wish they'd had the foresight not to use the traditional infix operators for built-in types; they practically beg programmers to implicitly treat built-in types like the mathematical types they very vaguely resemble.

Really, working directly in fixed-precision arithmetic is absurd. In order to be able to rely on its correctness with any degree of certainty, you need to very carefully track each operation and its bounds, at which point you may as well have just used arbitrary-precision types, explicitly encoded your constraints, and had the compiler optimize things down to scalar types when possible, warning when not.

sjolsen··on Gangnam Style breaks YouTube viewer count
> so whenever we have 128-bit or 256-bit registers, we'll have to go back and update all this code that effectively "optimizes" 1 bit of information

This is why we have uint_least8_t and friends. In fact, int is really just another int_least16_t.

> Furthermore, casting uintx_t to int and back again while using shared libraries is a huge pain in the ass and can waste a lot of programmer time that would be better spent elsewhere

Could you give an example? It sounds like you're just talking about performing the casts, which shouldn't take much effort at all as indiscriminately as C casts about integral values.

sjolsen··on Stop Changing UIs for No Good Reason
> There are a bunch of new ‘transitions’ between elements. I don’t know what the battery cost actually is for this, but as a user I just don’t care about cute transitions between elements. I want fast interaction with my mobile device.

In other words, UI animations are literally a waste of time. To hell with the battery, the user's time is the most valuable resource, period.

sjolsen··on Google's MathFu: a x-platform geometry math library for C++
Is there a particular reason everything is implemented as member functions? I feel like typing things like

    mathfu::Vector <float, 3>::CrossProduct (u, v)
instead of

    cross_product (u, v)
would get really old really fast.
sjolsen··on Stupid C++ Template Tricks: Conway's Game of Life
> The only super legit argument I've heard in favor of _not_ using templates or avoiding them in general is because of the code generation bloat

And even then, it's important to recognize that bloat is a relative measure. If you use just one instantiation of a template, you're not paying for multiple versions of the code.

If, on the other hand, you use multiple instantiations, the code will be bloated compared to, say, a single type-erased version— but will not be any bigger than if you had written several "instantiations" of the same code by hand. There's a tradeoff to be made, too, since a statically-typed version of a function will probably be faster than a type-erased version.

Anyway, w.r.t. bloat, templates aren't the problem; static polymorphism is (can be). Templates are just a way of implementing static polymorphism.

sjolsen··on Perfect forwarding and universal references in C++
I won't contest that! But C is crazy enough that suggesting it as an alternative to C++ because C++ is crazy is, well, crazy. If you can handle the crazy of C, you can probably handle C++, because the crazy specific to C++ usually at least converges to reasonable behaviour.

I mean, you'll drive yourself nuts trying to wrap your head entirely around either language, so you may as well at least mentally approximate the one that gives you basic type-parameterization.

sjolsen··on Perfect forwarding and universal references in C++
> At least, C can fit in a brain.

A typical programmer's mental model of C can fit in a brain. Actual C is every bit as complex and nuanced as C++; it just has a narrower scope. I mean, C++ may be crazy, but don't pretend a language where

    uint64_t foo = 1 << 48;
has undefined behaviour,

    int a [3];
declares an array while

    void foo (int a [3]);
declares a function taking a pointer, and polymorphism is achieved by erasing all types and parsing a string at run time to figure out where to pull stuff off the stack:

    printf ("%d%s\n", 3.0, " s"); // Whoops, "%d" doesn't mean "double." It's a shame I don't have a type system for catching that sort of error.
is anything remotely resembling sane.
sjolsen··on Towards a Vim-like Emacs
I think chording is the least of one's worries; the awkward staggering of the IBM-style keyboard and the modifiers designed to be pressed by a curled pinky (especially Shift) are murder on my hands, chords or not. From a strictly ergonomic standpoint, I would choose Emacs on a TEK or Maltron over Vi on a traditional keyboard any day of the week.
sjolsen··on Building C Projects
> what qualities of a language make it designed for compilation?

That a language that compiled to good machine code was one of the main goals of the people who designed it. I was making a historical statement, not a qualitative one.

sjolsen··on Building C Projects
> Compiled vs interpreted is not a property of the compiler.

I assume you meant "language." You're of course correct, but if ever there were a language that deserved to be called "compiled," C is it. It truly was designed to be compiled, and who in their right mind would bother interpreting it?

And before you ask, no, people who debug C are rarely in their right minds. :)

sjolsen··on X86 versus other architectures (Linus Torvalds) (2003)
> but don't then say that existing code still compiles fine.

Oh, I'm not disputing that a lot of existing C code wom't compile as C++; I'm just nitpicking the claim that good C code won't compile as C++. ;)

But to be fair, there are perfectly good, valid C programs that don't compile as C++, void * aside.

sjolsen··on X86 versus other architectures (Linus Torvalds) (2003)
> The typical case is when you call malloc.

And if there were a proper type-parameterized entry point to malloc (be it a function or macro) for general-purpose contiguous-object allocation, you wouldn't have to compromise the already weak type system with what is possibly the single most absurd implicit conversion possible from a type system perspective just to avoid typing out the type name three times.

I suppose it's more of a language quality issue than a program quality issue, but reducing verbosity by undermining the type system rather than providing a simple "allocate<T>(n)" function, especially in a language that doesn't care about verbosity enough to provide even the thinnest of syntactic abstractions, is just ridiculous.

sjolsen··on X86 versus other architectures (Linus Torvalds) (2003)
> C++ compilers will reject a lot of good C code, mostly because it disallows implicit casts from void *

When did code that implicitly casts from void * become "good?" Implicit conversions from A to B should never happen unless it's statically known that A can be represented as B, and that's generally not the case when A is type-erased, as when it's referred to through void *.

sjolsen··on 0x5f3759df and the fast inverse square root (2012)
Seriously, computer science itself is a branch of mathematics. Or is mathematics a branch of computer science...?

It's not always weird bit-level arithmetic, but if you aren't using math at some level, you're not programming; you're just futzing around with a text editor.

sjolsen··on Don't run 'strings' on untrusted files
> I'm not sure if it's usually the mix of a "smart" C programmer writing a program that is patched by a "hobby" C programmer, or the fact that getting C right is just too hard -- or that people don't -Wall and don't run fuzzers and static checkers -- but whatever the reason, we keep seeing serious bugs in C programs.

I think the problem is that people don't take programming seriously. The basic flow of development seems to be to write the first thing that comes to mind as it comes to mind, and then incrementally patch things up until the code seems to work on every test case you've thought up.

This approach is at best inefficient when working with "safe" languages. With C or C++, it's nothing short of irresponsible. Part of the problem, I think, is that programmers are never taught to reason formally about their code: to catalogue their preconditions and postconditions and verify with some semblance of rigour that the code they write respects these. At best, they might be treated to a passing reference to object invariants if they happen to take a class or (God forbid) read a book on "OOP."

It's perfectly possible to write good, safe code in C and C++, but not if you're hung up on a "smart" or "hobbyist" programmer mindset, and not if you're not willing to put in a fair amount of effort into thinking before you write.

sjolsen··on “Did you mean?” Experience in Ruby
C++ and Java are statically typed. If you're referring to dynamic polymorphism, then yes, it can be a pain in the ass.
sjolsen··on Linear Congruential Generators
My preferred method—well, actually, my preferred method is to use std::uniform_int_distribution—but in lieu of that, I prefer to use an adapter that builds values in a target range bitwise from values in a source range.

The basic idea is to drop off the top of the input range so it's a power of two wide; this makes the bits of the input values independent (i.e., each bit has equal probability of being 0 or 1). You gather enough bits this way to span at least the target range, then again drop off any values exceeding the range's bound.

The drop-off method preserves uniformity because any variable uniformly distributed over a set is also uniformly distributed over any subset of that set. Breaking down and building up the binary representation works because uniformity is preserved by the Cartesian product (i.e., X is uniform in A and Y is uniform in B iff (X,Y) is uniform in A×B, where X and Y are stochastic variables) and the binary representation of an integer is just {0,1}^n for some n.

The advantage of this method is that you can adapt any input range to any output range without introducing any nonuniformity, cycles, or other "flaws" in randomness (though it will certainly preserve them, if not amplify them).

Another interesting thing to note about this algorithm is that you don't technically have to use binary or even a fixed base; given X in A and Y in B, where A and B are subsets of the natural numbers and |B| ≥ 2, (X,Y) ≅ X * (sup(B)+1) + Y. You can, if I'm not mistaken, use this property to derive the first "more reasonable answer" in the first link you gave from the algorithm above, assuming a smaller target range than input range. And if you look closely at "X * (sup(B)+1) + Y," you'll see a relationship with quotients and remainders and, I think, the LCG itself.

This is quite interesting stuff.

sjolsen··on Linear Congruential Generators
> However, because the implementation of rand is unknown, it is impossible to tell whether or not using modulus to shrink the range will result in an acceptably random sequence. The reason that this might not be the case is due to the very definition of linear congruential generators.

Using the modulus operation to transform the range of std::rand is problematic, but it isn't because of any attribute of the implementation of std::rand or of linear congruential generators.

One problem with using modulus to scale a random distribution is that it fails to preserve uniformity. For example, consider a function 'rand150' whose result is uniformly distributed on [0, 150); that is, each number in the range [0, 150) has the same probability (1/150) of being returned by any given call to rand150. Now, if you use modulus to scale to [0, 100):

    x = rand150() % 100;
there are 100 possible values for x. For any value greater than or equal to 50, there is exactly one result of rand150 which could produce that value; therefore, the probability of x being that value is 1/150. But for values less than 50, there are two results of rand150 which could produce that value, giving it a probability of 2/150. Since half of the possible values of x have a probability of 1/150 each and the other half have a probability of 2/150 each (you can check that this adds up to a probability of 1), the distribution is very much nonuniform. This result does not apply just to small ranges; it applies any time you scale down the range by anything but an integer multiple, although it approaches uniformity more closely the smaller the target range is compared to the source range.

The other problem is that you can't make the range bigger. Well, you actually can— but some of your "x" values will have a probability of zero, which probably isn't what you want. Considering rand150 again, if you try to scale to [0, 300) by doing:

    x = rand150() % 300;
how often do you expect to get 250?

> The common solution is to use the constant value RAND_MAX, defined with every standard library, to use the high-order bits of a random number through division rather than low-order bits with the remainder of division

I'm not sure if there's a typo in the code, but if RAND_MAX is, say, 200, then

    rand() / (RAND_MAX / 100 + 1)
gives you values on [0, 66]. Probably not what you want.

> An alternative to dividing RAND_MAX by N is to force the expression to floating-point and multiply RAND_MAX by N

Mathematically, this would be a sensible way of scaling continuous uniform distributions, or at least it would be if floating-point numbers weren't so imprecise. When dealing with discrete distributions, though, this approach still has problems. For example, what if rand gives values on [0, 30) and I want values on [0, 20)? Let's see what values of rand map to, assuming perfect real numbers:

    rand  x
    0     floor(0)   = 0
    1     floor(2/3) = 0
    2     floor(4/3) = 1
    3     floor(6/3) = 2
    4     floor(8/3) = 2
Unfortunately, 1 will only be generated half as often as 0 or 2.

> Yet another alternative is to utilize the uniform_deviate function provided not too long ago

Mathematically, this is equivalent to the above. The floating point arithmetic may be very slightly different, but it will make the result worse if anything.

sjolsen··on Human Interface Guidelines
I find it strange that they give measurements in terms of pixels. When pixel density ranges from 96 pixels per inch to 200 pixels per inch and beyond on consumer hardware alone, pixels simply aren't an appropriate measurement for UI purposes. I don't mind display optimization, but it should be exactly that: optimization. Put another way, I prefer appropriately sized, blurry UI elements over crisp UI elements I have to use a magnifying glass to see.

I also take issue with the stance against configuration. The one thing that I've found most frustrating about using computers in recent years is that I am constantly losing control over my programs to the headlong pursuit of "minimalism." Now, I don't mind simple interfaces. I don't even mind defaults geared toward the… technically challenged. What I do mind is being unable to decide how my computer behaves and how I interact with it, being effectively forced to use my computer in whatever way the developers of my current software stack have deemed best for most of their users—or, of course, switch to another software stack entirely. The latter approach doesn't exactly scale.

Now, I suppose there's a third option: dig into the internals of the unconfigurable tools looking for dconf settings or configuration files I can hack at to give me back location bars and the ability to manipulate windows with the Alt key and the mouse. Of course, this is rather difficult when the developers have been actively discouraged from writing the documentation that would make this a relatively straightforward endeavour. Instead, I'm left first trying fruitlessly to Google any and every permutation and phrasing of what I want to accomplish, next hoping that Gnome Tweak or the equivalent has a fix for the recently nerfed functionality, and finally considering for a moment searching manually through the program source for what I want before deciding it's really not worth my time, at which point I usually just throw the program out entirely and install the most bloated KDE-based alternative I can find.

/rant. I realize Elementary is designed to be as functional as possible in the hands of the non–power-user majority, but I wish it didn't come at the expense of power-usability. One can of course substitute in more powerful third-party programs for the simple system defaults, but one then loses system integration. I would love to see a project like Elementary cater to both groups of users, since I (like most self-described power users) belong to both groups, depending on the task at hand, but developers only ever seem interested in targeting one group or the other.

sjolsen··on GCC Undefined Behavior Sanitizer – Ubsan
> Is reading a 4-byte int from a non-multiple-of-four address explicitly undefined behavior?

A type in C or C++ has an alignment, queryable through C's _Alignof and C++'s alignof. This is not necessarily the same as its size, though there is a relationship.

Given a pointer-to-cv-T, you may only access memory through that pointer if the address it encodes is aligned to "_Alignof(cv-T)"/"alignof(cv-T)". If it is not appropriately aligned, accessing memory through it is undefined behaviour.

In other words, the standards do not specify the alignment of any type (except to say that it's always at least 1, IIRC), but they do require that you respect alignments.

sjolsen··on GCC Undefined Behavior Sanitizer – Ubsan
> On a platform that doesn't have alignment requirements, it's not a bug to access misaligned data

Consider the following statement:

> On a platform that has well-defined signed overflow, it's not a bug to perform signed overflow.

If you've ever cranked up GCC's optimization settings on a program that performs signed overflow, you know this simply isn't true.

In general, the fact that the underlying hardware supports a certain set of machine semantics does not guarantee that the implementation will extend the semantics of the C or C++ abstract machine to match. It of course may do so—after all, it may do whatever it pleases once your program exhibits undefined behaviour—but unless you are specifically targeting your implementation's C- or C++-like dialect instead of ISO C or C++, accessing unaligned memory is a bug.

> Ubsan should adopt a couple of other safety improvements from C++

I agree that these should be adopted, but disagree that it should be ubsan which does so. These are statically detectable errors, so it should be the compiler which implements the detection, be it as a QOI extension or as part of the language standard.

sjolsen··on After California decriminalized pot, teen arrest, overdose, dropout rates fell
Enjoyment, primarily.
sjolsen··on C++11/14 compiler and library shootout
> There is nothing modern about the new features of C++11/14

There's nothing modern about any feature that's been introduced into a popular programming language in years. They're all rediscoveries or minor iterations on things invented decades ago.

It's usually not the features that are described as being "modern," though. It's the style that's described that way, and there is a marked difference between the style of, well, modern C++ code and the style of C++ code written in the '90s.

sjolsen··on The Most Expensive One-byte Mistake (2011)
Edit: It occurred to me after posting this that by "length + data" you might mean actually storing the length with the string data. If so, you're right, that's stupid. The correct solution (well, it's better than C/Pascal strings, anyway) is to store just the string data in the string proper, and use references that consist of pointer+length or pointer+pointer pairs instead of single char-pointers.

> It's easy to break a string with delimiters into the individual pieces in place, just by writing nulls over the separating characters

This assumes you're free to modify the input. If you don't want/are unable to modify the input, you're forced to allocate memory to hold the output; you've totally unnecessarily doubled the space requirement. It also assumes that there is a separating character to overwrite, which may not be the case, causing the same problem.

> just by writing nulls over the separating characters > This can't be done with some other string representations like length + data

Obviously. It is, however, perfectly possible to tokenize a string into a vector of length+data pairs without mangling the input.

> When one null terminated string is a suffix of another (and ideally both are treated as immutable), then they can share storage.

And only when one is a suffix of another. If you want to share storage between strings between which this relationship does not hold, you must again allocate extra memory, and again this is not necessary if you use a data+length representation.

> Catenating null terminating strings is efficient if you keep a tail pointer

In other words, if you use a pointer+length or arithmetically equivalent representation—except that you don't even bother binding the data into a coherent data structure, and instead force any code without access to your local tail-pointer variable to derive the length/end of the string on its own.

> For one thing, how wide should be the length?

Wide enough to represent the length of the longest possible string. Generally, this is less than or equal to the length of a pointer.

> If you make it two bytes today and store binary data somewhere, it will be incompatible with tomorrow's four byte length > Null terminated strings can be blasted over a serial line or network, or written to disks, as they are

You are making the incorrect assumption that the most appropriate on-disk/serialization representation is necessarily the same as the most appropriate in-memory representation.

> And then there is endiannness

1. See above.

2. You're right that "this isn't true of wide character null term'd strings," so unless you and everyone you communicate with are still living in 1985, NTBSes don't even have that advantage.

> You cannot pass them between address spaces or share them without marshaling to some flat form and back

You can't do this with NTBSes, either, unless you have a way of translating the address of the string across address spaces, in which case you could just as well pass a pointer+length as you could pass a pointer.

NTBSes are a perfectly fine representation if: your string is known at compile time; your string will never be modified; your string will only be scanned through from front to back; and your string does not contain a null character. From a technical standpoint, the only reason to bother with them in the first place is that you have extremely tight memory requirements and can't even afford the extra byte or three needed for a sane string-reference representation.

If any of these conditions does not hold, NTBSes are a Terrible, Horrible, No Good, Very Bad representation. All they accomplish in practice is to make strlen a linear-time operation, defeat a great number of data-sharing opportunities, and generally plague the world with buffer overruns.

sjolsen··on John Carmack on Inlined Code
> Why the hell would you want to do that?

To isolate all of the initialization logic for a single object (e.g., "result1" or "result2") into its own scope. You could use a function (in fact, that's exactly what's being done here—it's just an anonymous function), but moving that logic away from its use and into global scope generally just makes the code more difficult to understand.

> There's no benefit and only drawbacks over the plain old block syntax.

You cannot initialize a const object with the "plain old block syntax." With this, you can, and that is an enormous benefit. It's also much easier to see that the object is initialized; it's not immediately obvious that an uninitialized variable declaration followed by an assignment many lines later will always initialize the variable, but if you initialize it in its declaration, you know it will necessarily be initialized. That is also a very important benefit.

What are the drawbacks? That the syntax is a little uglier? It's not ideal, but it's hardly huge syntactic overhead: four or five non-whitespace characters and a return instead of an assignment. In fact, the syntax is markedly better if you have multiple initialization paths, because you can use return instead of goto; compare

    char* foo;
    {
        char* mem = (char*) malloc (N);
        if (!mem) {
            mem = NULL;
            goto foo_init;
        }
        if (!fgets (mem, N, fd)) {
            free (mem);
            mem = NULL;
            goto foo_init;
        }
    foo_init:
        foo = mem;
    }
    
    the_next_thing:
to

    char* foo = [&] {
        char* mem = (char*) malloc (N);
        if (!mem)
            return NULL;
        if (!fgets (mem, N, fd)) {
            free (mem);
            return NULL;
        }
        return mem;
    } ();
    
    the_next_thing:
Even after the "plain old block" version has been contorted to make assignment to foo unconditional (it's essentially a manually inlined function), it isn't obvious that it's correct. Does the block do "goto the_next_thing" or something similarly hairy? Read the whole thing to find out.

In contrast, once you've seen that foo is initialized by a function and that function ends in an unconditional return, you know that foo cannot not be initialized at the_next_thing, period (even if you throw exceptions into the mix!).

You might argue that you can verify the correctness of the first version, and of course you can, just as you can verify the correctness of an HTML parser written in brainfuck. It's all a matter of cognitive load, of the amount of context you have to hold in your head at one time to reason about the correctness of one part of your code. It's the difference between verifying that the function initializing foo has an unconditional return and verifying that every control path in the initialization block reaches foo_init, when what you're really trying to do is just to show that foo will point to a valid string at "the_next_thing."

In fact, that's basically the primary motivation behind functions, next to code reuse. All this pattern is really doing is modularization-by-function of initialization logic without the cognitive overhead induced by lexically separating the logic's definition from its use. In doing so, it delivers the same advantages as the plain-initialization-block pattern, but preserves the comparatively simple control-flow-barrier semantics of functions.

Compared to goto-spaghetti, typing "[&]" and "();" really isn't that big of a deal.

← PreviousPage 5 of 6Next →