11–20 of 45 posts
What would possess someone to write if (i = buffer) ... instead of if ((i = sizeof(buffer)) ?
Kind of off topic, but I am curious: is this one of the advantages of functional programming - the notion that you can prove or disprove certain things about the code and therefore optimize the compiler, based on such proofs, to your heart's content?
The more advanced of a type system you have, the more you can optimize indeed. A nice example of this is the zip function. In Haskell: zip :: [a] -> [b] -> [(a, b)] zip [] _ = [] zip _ [] = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys Note how each iteration needs to check both lists for emptiness. In a more advanced type system (or using more advanced type hackery in Haskell) you can have length-indexed lists. That is:…
Also, in this example you're using a singly linked list, which is usually a performance loss compared to a more appropriate data structure. CPUs are designed to favor contiguous arrays.
What would possess someone to write if (i = buffer) ... instead of if ((i = sizeof(buffer)) ?
Instead, consider it from the point of view of probability.
Even if probability of any single programmer writing an exceedingly stupid piece of code is vanishingly small, the number of programmers writing new code daily is so big, that mistakes of vanishingly small probability end up being quite common indeed.
To given a real example: consider that Apple undoubtably employs only the finest programmers for their OS group and yet every iOS release is jailbroken quite quickly due to a piece of code which had a security bug.
Even within a much smaller scope of a single application, all web browser from Microsoft, Apple, Mozilla (and sometimes Google) are regularly compromised via security bugs despite huge investments from all those companies into security.
Toss in the fact that many programmers actually like doing things in unnecessarily clever or novel ways and inevitably the clever code is more likely to be buggy than boring code.
Bugs and crappy code is a statistical certainty, especially in languages like C and C++ that give you so many ways to shoot yourself in the foot.
What would possess someone to write if (i = buffer) ... instead of if ((i = sizeof(buffer)) ?
Unrelated to the issue, but the superfluous parenthesis added in the second example are interesting. I think every C coder has a level of comfort with the 15 sets in the operator precedence rules, and beyond that they throw parenthesis at it. I'm fine with the rules until I use a , >>, &, ^, or |[1]. Then I drag out the parenthesis.
[1] I swear the positions of the ones I named are placed alphabetically rather than in relation to their mathematical function.
gcc still gets the pointer dereference and assignment to what a pointer points to, due to deferring assignments. these edges, idioms of any lang needs to be looked at with academic eyes. :-)
What would possess someone to write if (i = buffer) ... instead of if ((i = sizeof(buffer)) ?
Many of the strange things that happen in C language edge cases come about from macro expansion or code generation. Unrelated to the issue, but the superfluous parenthesis added in the second example are interesting. I think every C coder has a level of comfort with the 15 sets in the operator precedence rules, and beyond that they throw parenthesis at it. I'm fine with the rules until I use a , >> , & , ^ , or | [1]…
:(
Earlier quoted context omitted.
The more advanced of a type system you have, the more you can optimize indeed. A nice example of this is the zip function. In Haskell: zip :: [a] -> [b] -> [(a, b)] zip [] _ = [] zip _ [] = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys Note how each iteration needs to check both lists for emptiness. In a more advanced type system (or using more advanced type hackery in Haskell) you can have length-indexed lists. That is:…
In an unsafe language like C or C++, you would just assert that the two containers are the same length and use parallel iterators. The type system here lets you optimize away some of the overhead of using a safe language, but it doesn't let you write code that is more optimized than the obvious unsafe code, at least in this example. Also, in this example you're using a singly linked list, which is usually a performan…
Well, you can choose any two of: 1. Fast (less run-time), 2. Safe (cannot crash), 3. Simple types (None of the advanced type hackery). Many choose 1+3 or 2+3, but advanced types let you choose 1+2 which in many cases is remarkable and somewhat surprising that it is even possible.
Also note that runtime checks, in many cases, do not give you safety. For example, normally, you have an array indexing operation like:
readArray :: Array a -> Int -> IO a
In these (common cases), your only option of getting safety is advanced type hackery. Something like:
index :: (size:N) -> Array size a -> Fin size -> a
> Also, in this example you're using a singly linked list, which is usually a performance loss compared to a more appropriate data structure. CPUs are designed to favor contiguous arrays
Nothing about this type hackery is specific to singly linked lists, and advanced type hackary is applicable for pretty much any data structure. Also note that the singly linked lists used in zip may not actually be represented by pointer-chasing singly-linked lists. They may be "fused" together into efficient loops that process the input directly.
Kind of off topic, but I am curious: is this one of the advantages of functional programming - the notion that you can prove or disprove certain things about the code and therefore optimize the compiler, based on such proofs, to your heart's content?
The relevant element of FP is statelessness. That said, statelessness could easily be considered a leaky abstraction because, at some point, the machine you are working on has state. Your machine has CPU registers and memory and such, so the entire "statelessness" of FP is subject to the underlying system-level implementation.
It is only leaky if you are exposed to the statefulness of the underlying machine.
Haskell's pure code does enjoy the abstraction of purity without exposing the non-pure primitives from which it is exposed. Haskell's non-pure code is marked as such, and not supposed to be abstracted away from the nature of the underlying machine. I'm not sure what abstraction leak you're referring to. Can you give an example?
Earlier quoted context omitted.
In an unsafe language like C or C++, you would just assert that the two containers are the same length and use parallel iterators. The type system here lets you optimize away some of the overhead of using a safe language, but it doesn't let you write code that is more optimized than the obvious unsafe code, at least in this example. Also, in this example you're using a singly linked list, which is usually a performan…
> In an unsafe language like C or C++, you would just assert that the two containers are the same length and use parallel iterators. The type system here lets you optimize away some of the overhead of using a safe language, but it doesn't let you write code that is more optimized than the obvious unsafe code, at least in this example. Well, you can choose any two of: 1. Fast (less run-time), 2. Safe (cannot crash), 3…
I don't think it's really that surprising that it's possible. Most programs don't rely on any deep mathematical properties for their correctness, so the ability to formalize a proof that they are correct and encoding it into a type system doesn't surprise me at all. If it is possible to do it on a large program without maintenance or scalability problems, then I will be more impressed.
You also present a false trichotomy. Haskell is not actually a completely 'safe' language; it still has exceptions that can cause a program to "go wrong" and terminate unexpectedly. You can write 'fast' code with it, but it isn't as fast as what I could write in a lower-level language.
> Nothing about this type hackery is specific to singly linked lists, and advanced type hackary is applicable for pretty much any data structure. Also note that the singly linked lists used in zip may not actually be represented by pointer-chasing singly-linked lists. They may be "fused" together into efficient loops that process the input directly.
As the data structures get further away from algebraic data types, the type hackery gets more and more involved. If you start working with arbitrary mutable data structures that arise in practice, the type hackery becomes a topic for a PhD thesis rather than something usable in practical programming today.
I don't know of any compiler that actually does a reasonable job converting uses of data structures like lists and association lists into arrays and hash tables in general. There are compilers (like GHC) that handle special cases but fall over beyond that. I think this falls into the territory of the "sufficiently smart compiler" fallacy. Also, making data contiguous is just the simplest of a common set of data representation optimizations. Does any compiler automatically convert a list into an intrusive doubly linked list or eliminate the use of a visited stack for DFS by stealing a bit from vertices or reversing pointers?
Earlier quoted context omitted.
The relevant element of FP is statelessness. That said, statelessness could easily be considered a leaky abstraction because, at some point, the machine you are working on has state. Your machine has CPU registers and memory and such, so the entire "statelessness" of FP is subject to the underlying system-level implementation.
> The relevant element of FP is statelessness. That said, statelessness could easily be considered a leaky abstraction because, at some point, the machine you are working on has state. Your machine has CPU registers and memory and such, so the entire "statelessness" of FP is subject to the underlying system-level implementation. It is only leaky if you are exposed to the statefulness of the underlying machine. Haskel…
More generally, the fact that execution time and memory usage (tail recursion!) sometimes depend on how well the compiler can turn your stateless algorithm into a stateful one, in ways that don't make sense from the perspective of the abstract machine.