Month: May 2018

Categories
academics theory

Judea Pearl’s mysterious claim

Pearl: Of course, but you cannot see this noble aspiration in scientific equations. The language of algebra is symmetric: If x tells us about y, then y tells us about x. I’m talking about deterministic relationships. There’s no way to write in mathematics a simple fact—for example, that the upcoming storm causes the barometer to go down, and not the other way around.

Mathematics has not developed the asymmetric language required to capture our understanding that if x causes y that does not mean that y causes x. It sounds like a terrible thing to say against science, I know. If I were to say it to my mother, she’d slap me.

(from the Atlantic)

What is he talking about?  Isn’t that exactly what state machines do?

alt text

Categories
programming languages

Depressing and faintly terrifying days for the C standard

C STANDARD UNDEFINED BEHAVIOR VERSUS WITTGENSTEIN

1. DEPRESSING AND FAINTLY TERRIFYING

Chris Lattner, the architect of the Clang/LLVM C compiler explained the effects of the C standard’s “undefined behavior”(UB):

UB is an inseperable part of C programming, […] this is a depressing and faintly terrifying thing. The tooling built around the C family of languages helps make the situation less bad, but it is still pretty bad. The only solution is to move to new programming languages that dont inherit the problem of C. Im a fan of Swift, but there are others.[4]

Also from Lattner[5]:

[…] many seemingly reasonable things in C actually have undefined behavior, and this is a common source of bugs in programs. Beyond that, any undefined behavior in C gives license to the implementation (the compiler and runtime) to produce code that formats your hard drive, does completely unexpected things, or worse

Undefined behavior is defined by the C Standard as “behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements.”  You might think that having the architect of a major compiler point out that the result of your standard is “depressing and faintly terrifying” and curable only by switching to another programming language would cause some consternation at the standards committee, but no. The WG14 C Standards organization appears to be unconcerned despite the warnings of compiler developers and the objections of the most prominent C developers and academics.

  • Dennis Ritchie called an early version of UB “a license for the compiler to undertake aggressive optimizations that are completely legal by the committee’s rules, but make hash of apparently safe programs“[7].
  • One of the most important developers of cryptography code wrote: “Pretty much every real-world C program is “undefined” according to the C “standard”, and new compiler “optimizations” often produce new security holes in the resulting object code” [1].
  • In summary that leans over backwards to find excuses for UB, John Regehr wrote: One suspects that the C standard body simply got used to throwing behaviors into the undefined bucket and got a little carried away. Actually, since the C99 standard lists 191 different kinds of undefined behavior, its fair to say they got a lot carried away.[6].
  • And Linus Torvalds wrote: The fact is, undefined compiler behavior is never a good idea. Not for serious projects. [8].

2. SLOW MOVING TRAIN WRECK

Discussion of this issue or of practitioner objections in WG14 records is hard to find. What we do find are proposals to greatly expand the realm of undefined behavior[3]. And there is no doubt that the standards embrace of UB has created a slow motion train wreck.

  1. A security failure in the Linux kernel was generated by the compiler silently removing a check for a null pointer several lines below a UB reference to a null pointer.
  2. Code that checks for overflow in a signed variable can be silently “optimized” to remove the check because overflow of integer variables is UB.
  3. The C standard committee had to hack up its own standard with a special case when it realized it had made it impossible to write “memcpy” in C[2].
  4. Under pressure from, particularly Linux, the GCC compiler has introduced a number of flags to turn off UB behavior – essentially forking the language.

As Lattner wrote, C code that appears reasonable, that causes no compiler errors or warning and that conforms to wide practice can be arbitrarily changed once the compiler believes it has detected UB somewhere in the same neighborhood.  But this is a bizarre interpretation of UB and it’s remarkable that the WG14 C Standards Committee has not made efforts to ban such an interpretation.  Originally, UB is simply there to mark the borders of what C specifies: C does not specify what happens when the result of integer arithmetic can’t fit in a signed int – because the language designers wanted to permit compilers to leave off expensive checks. But currently compiler developers claim they can,for example, assume that UB never happens and, for example, delete programmer checks for overflow. The rationale for this perverse UB is that it opens up compiler optimizations that would be otherwise impossible. This claim is not supported by any actual studies. Even for the kinds of trivial micro-benchmarks that are often cited, it looks like absolutely nobody is doing any tests. For example, an unsigned and signed variable in a C “for loop” have no performance difference despite the advantage that the undefined nature of signed overflow supposedly provides the compiler. Even though UB has been around since Ritchie first objected to it, it has grown in scope as the C standard has grown in scope and complexity. Here’s a good example from C11 in some typically opaque language :

(6.5 Para7) An object shall have its stored value accessed only by an lvalue expression that has one of the following types: a type compatible with the effective type of the object, a qualified version of a type compatible with the effective type of the object, a type that is the signed or unsigned type corresponding to the effective type of the object, a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object, an aggregate or union type that includes one of  the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or a character type

I had to read the footnote to to have any idea at all what is being “specified” by this murk

” The intent of this list is to specify those circumstances in which an object may or may not be aliased.“

That last sentence in 6.5 Para7 is a hack added when the Committee realized it had made it impossible to write memcpy in C – you have to pretend that memcpy copies character by character or is written in some other language in order to make it consistent. And you also need footnote 75 (“Allocated objects have no declared type.”).

 No wonder that Linus Torvalds was not impressed.

The idiotic C alias rules aren’t even worth discussing. They were a mistake. The kernel doesn’t use some “C dialect pretty far from standard C”. Yeah, let’s just say that the original C designers were better at their job than a gaggle of standards people who were making bad crap up to make some Fortran-style programs go faster. They don’t speed up normal code either, they just introduce undefined behavior in a lot of code. And deleting NULL pointer checks because somebody made a mistake, and then turning that small mistake into a real and exploitable security hole? Not so smart either. [8]

Brian Kernighan didn’t like it either, back when this design error was part of Pascal and not part of C [10]: 

2.6.  There is no escape

There is no way to override the type mechanism when necessary, nothing analogous to the “cast” mechanism in C.  This means that it is not possible to write programs like storage allocators or I/O systems in Pascal, because there is no way to talk about the type of object that they return, and no way to force such objects into an arbitrary type for another use.  

Yes, according to the C Standard, malloc cannot be written in C. In fact, the example of malloc in K&R 2cd edition is not written in C according to the standard under current interpretations.  Instead there is special treatment for malloc as a mystery library function so it can return pointers to data of “no declared type” even though malloc is defined to return pointers to void. What if you want to write an allocator, not called malloc/free? I don’t know, perhaps you are supposed to use Rust or Swift.  What about mmap/mfree  ? Nope. It’s hard to imagine even how those functions can be used in Standard C.  Reference I/O or device registers? Nope again. You have Pseudo-Pascal and you better learn to like it.  Want to treat a packet as an array of ints so you can checksum it? Nope. According to proponents of the C Standard the correct way to do this is to use memcpy to copy the packet to an integer array, compute the value, copy back, and then hope the optimizer figures it out and removes the copying because there is, you guessed it, another special exception for memcpy used to copy data to memory of “no declared type”.

(6.5 6) […]. If a value is copied into an object having no declared type using memcpy or memmove, or is copied as an array of character type, then the effective type of the modified object for that access and for subsequent accesses that do not modify the value is the effective type of the object from which the value is copied, if it has one. For all other accesses to an object having no declared type, the effective type of the object is simply the type of the lvalue used for the access.

So the sequence looks like this: (1)Allocate a packet sized block of memory using malloc –  this has “no declared type”;  (2) Copy the packet to this memory using memcpy; (3) The new block of memory has the effective type of the packet structure; (4) Then modify the new block of memory using an int pointer; (5) And magically, the memory block is now an array of ints”. Doesn’t  step (4) violate the effective type rules in the very next paragraph? Yes, but pretend otherwise. Basically, memcpy/memmove and malloc plus character arrays are giant hacks to the type system that kind of make things sort-of work. To make matters worse, another part of the standard provides rules for casting pointer types which, according to this part, provide a Standards Conformant way for changing the type of a pointer, but at the same time making it undefined behavior to de-reference the pointer. Section 6.3.2.3.7 permits a pointer to an object type to be converted to a pointer to a different object type and 6.3.2.1 permits any pointer to be converted to a void pointer type and then converted to any other type but the current language in 6.5.7 seems to imply that dereferencing those pointers may be undefined behavior even if the pointers  are properly aligned – which would make the conversion useless at best.

3. MORE IS BETTER, NO ? 

There’s a unfortunate dynamic in the WG14 process in which the language definition expands in scope while shrinking in clarity. This dynamic comes from a lack of appreciation for the frugal semantics of the C language. In software, as in much other forms of engineering, only the most brilliant or lucky designers manage to leave the right things out. In particular, C and UNIX were so successful as much because of what was left out as because of what was put in. The injunction of Wittgenstein[9] is almost a cliche in programming design, but it is on point: What can be said at all can be said clearly; and whereof one cannot speak thereof one must be silent. The approach of the WG14 committee has appears to have been based on the misconception that this economy in specification was a problem to be solved by expanding the scope of things covered by the standard. The alias rules above are a good example. C had no aliasing rules because it gained an advantage by permitting programmers to use pointers flexibly. Lack of aliasing rules could have been argued as too costly in terms of both programmer errors and forsaken compiler optimizations, but that could have been addressed by refining the restrict keyword or providing some other opt-in semantics instead of trying to back up a half-baked  notion of strict typing into C.

As another example, C did not define anything about concurrent tasks and parallelism, even though the designers of C intended to use it with interrupt handlers and processes and multi-processors, and did so with great success. By omitting the semantics of concurrent and parallel computation, the C design licensed programmers to develop many different solutions outside the framework of the language. Interrupt handlers, POSIX processes and threads, coroutines, SMP, the event models of current generation web servers, GPUs and vector processing: the minimalist design of the language meant that it did not get in the way of system designers and programmers. But the WG14 committee is now attempting to grow the language to cover the semantics of threaded code. Necessarily, this specification will have imprecision, opening the way to even more UB and it looks like it will tie the language to an awkward model of synchronization (via mutexes) and import into the language information about processor design that may well be obsolete in a few years.

The situation is only going to get worse as link time optimization becomes common in compilers – extending the ability of the compilers to find UB across separate compilation borders. Either C will fade away as Lattner and many others hope, the standard will change, or there will be a successful fork to produce a more precise and flexible standard.

REFERENCES

[1] D.J. Bernstein. boringcc., https://groups.google.com/forum/m/#!msg/

boring-crypto/48qa1kWignU/o8GGp2K1DAAJ.

[2] Derek Jones. How indeterminate is an indeterminate value. http://shape-ofcode.coding-guidelines.com/2017/06/18/how-indeterminate-isan-indeterminate-value/.

[3] David Keaton. Implicit Undefined Behavior in C. http://www.open-std.org/ jtc1/sc22/wg14/www/docs/n2248.pdf.

[4] Chris Lattner. GEP with a null pointer base. http://lists.llvm.org/pipermail/ llvm-dev/2017-July/115149.html. 2016.

[5] Chris Lattner. What every C programmers should know about undefined behavior 1/3. http://blog.llvm.org/2011/05/what- every- c- programmershould-know.html.

[6] John Regehr. A Guide to Undefined Behavior in C and C++, Part 1. https:// blog.regehr.org/archives/213.

[7] Dennis Ritchie. noalias comments to X3J11. http://www.lysator.liu.se/ c/dmr-on-noalias.html.

[8] Linus Torvalds. Re: [isocpp-parallel] Proposal for a new memory order. https: //gcc.gnu.org/ml/gcc/2016-02/msg00381.html.

[9] L. Wittgenstein and C.K. Ogden. Tractatus Logico-philosophicus. International library of psychology, philosophy, and scientific method. Routledge, 1990. ISBN: 9780415051866. URL: https://books.google.com/books?id=TE0nCMfRz4C.

[10] Brian Kernighan, Why Pascal is not my favorite language, Bell Labs, 1981, http://www.lysator.liu.se/c/bwk-on-pascal.html

AUSTIN TEXAS. E-mail address: victor.yodaiken@gmail.com

[gview file=”https://www.yodaiken.com/wp-content/uploads/2018/05/ub-1.pdf”]

Categories
academics

victor.yodaiken@gmail.com

See also: Damore’s Defenders. 

Scott Aaronson is a distinguished professor of computer science at the University of Texas. I ran into his blog a while back, when someone sent me to his muddled defense of Damore and the Google Memo – a defense  in which he essentially called Damore critics hysterical and anti-science. For example:

And therefore I say: if James Damore deserves to be fired from Google, for treating evolutionary psychology as potentially relevant to social issues, then Steven Pinker deserves to be fired from Harvard for the same offense.

Really! This week, I see Professor Aaronson is defending Robin Hanson for asking why liberal do-gooders don’t offer the same sympathy to “incels” that they offer to the poor and why those liberals don’t call for redistribution of sex.  Look I’m not making this up. Hanson, a Professor of Economics at George Mason University wrote an essay that is skin crawlingly creepy. Read it yourself. But my issue here is not with Hanson or Damore, it’s with Aaronson and his claim to be a nice, liberal, enlightened fellow, in favor of women’s rights and gender equality, but compelled by intellectual rigor and, you know, science and stuff, to defend these creeps, who he takes as iconoclastic truth tellers. Here’s Aaronson explaining how he first fell in love with Hanson’s take on the world despite an initial distaste for it:

Alas, back in 2003, I hadn’t yet been exposed to the epistemological revolution wrought by the 280-character smackdown, so I got the idea into my head that I actually needed to prove my objection was as devastating as I thought. 

Before we go any further, let me give you some of the evolutionary biology from Mr. Damore. Damore claims to be in favor of diversity, but says even the most limited mentoring program to increase the representation of women programmers at Google is discrimination against white men and morally unacceptable. He says:

In addition to the Left’s affinity for those it sees as weak, humans are generally biased towards protecting females. As mentioned before, this likely evolved because males are biologically disposable and because women are generally more cooperative and agreeable than men.

and

Unfortunately, the overwhelming majority of humanities and social sciences lean left (about 95%), which creates enormous confirmation bias, changes what’s being studied, and maintains myths like social constructionism and the gender wage gap. Google’s left leaning makes us blind to this bias and uncritical of its results, which we’re using to justify highly politicized programs.

Wow, myths like the gender wage gap, because, according to Damore:

Yes, in a national aggregate, women have lower salaries than men for a variety of reasons. For the same work though, women get paid just as much as men. Considering women spend more money than men and that salary represents how much the employee sacrifices (e.g. more hours, stress, and danger), we really need to rethink our stereotypes around power.

and he explains feminism as a marxist ploy:

As it became clear that the working class of the liberal democracies wasn’t going to overthrow their “capitalist oppressors,” the Marxist intellectuals transitioned from class warfare to gender and race politics. The core oppressor-oppressed dynamics remained, but now the oppressor is the “white, straight, cis-gendered patriarchy.”

This is what Professor Aaronson describes as: “treating evolutionary psychology as potentially relevant to social issues“. You might think, this is not evolutionary biology, it’s standard men’s rights misogyny, but Damore is way ahead of you

when a man complains about a gender issue issue affecting men, he’s labelled as a misogynist and a whiner

Well, imagine that! According to Aaronson, Damore was was advancing “the hypothesis of an evolutionary reason for average differences in cognitive styles between men and women” and the negative reaction against him is an example of more of that social media shallow emotion: “Let that be the measure of just how terrifyingly efficient the social-media outrage machine has become at twisting its victims’ words to fit a clickbait narrative—a phenomenon with which I happen to be personally acquainted.”

Here’s more Damore:

The historically higher variance of outcome can also be seen in our genetics; we have twice as many female ancestors as male ancestors. As a corollary, if Googlers are only from the top of the curve, then this may cause us to have more men than other, less selective, tech companies.

Aaronson is strikingly consistent about never quoting or naming any of the terrible people who participate in “clickbait narratives”. Never.  He barely even quotes Damore. The basis of his argument is essentially nothing more than a presentation of himself as an Olympian truth seeker, batting away anonymous social media critics. But, as shown above, Damore is a right wing polemicist, not an evolutionary biologist. Hanson, who has resurfaced in the  longtermism cadres  is even worse. Aaronson’s defense of Hanson (who is also a men’s rights ideologue as well as being an advocate of many other loathsome causes)  is that he is perhaps not as diplomatic as he should be but basically a brave iconoclast, willing to bravely say things that the major donors to his University and foundations will love, no matter how creepy they sound to those liberal do-gooders. I mean, someone who will bravely line up to get paid by Peter Theil! What an intellectual daring-doer.

Categories
business timekeeper

Clock Sync in Finance and Beyond.

A FSMLabs whitepaper.

[gview file=”https://www.yodaiken.com/wp-content/uploads/2018/05/financeandbeyond.pdf”]

 

Categories
state maps

Trees in informal methods

What’s a tree? First define a sequence or length n> 0 as a total map s: {1,.. n}→ X. Let Nil be the empty sequence.  If s is a sequence of length n, and x is an element, then u = sx is the sequence of length n+1 so that u(n)=x and for i < n, u(i)=s(i). That is sx is the sequence obtained by appending element x to sequence s on the right. If X is a set, let X* be the set of finite sequences over X, the minimal set that includes Nil and sx so that if s is an element of X*, sx is also an element. If s is a sequence, then either s=Nil or s = ux for some sequence u that has a length one less than the length of s. Define the predecessor of a sequence by Pred(Nil)=Nil and Pred(ux)=u.

A tree is a map  T: X* → Y where whenever T(s) is defined, T(Pred(s)) must be defined. Note that T(Nil) must be defined if T is defined on any elements of X* at all.

Let V  the set of vertices contain exactly those elements s of X* so that T(s) is defined.  If V is not empty, Nil is in V and call Nil the  “root”. Let E the set of labeled edges consist of exactly all triples (s,x,sx) where T(sx) is defined. Then (V,E) is the standard graph theoretic definition of a tree.  Suppose, on the contrary that (V,E) is a tree with labeled edges, that is it is a undirected graph that is connected but has no cycles. Then define T(Nil) = root and T(sx) = v s.t. there is an edge labeled x from T(s) to v.

 

So a sequence is a map from numbers to elements and a tree is a map from sequences to elements.

 

Categories
state maps

Linked lists

What’s a linked list?

  1.  Let V be a set of values and A be a set of “addresses”.
  2. Say a map f is a “linked list element” compatible with values V  and addresses A if and only if f(value)∈ V and f(next) ∈  A. A linked list element map can have an arbitrary additional domain – we don’t specify that here.
  3. Let L: A→ X where X is a set of  linked list elements compatible with V and A.  L associates addresses with linked list elements.
  4. Given any a ∈ A we want to be able to trace the linked list with “a” as the head element. Define E(L,a,0) = a and  E(L,a,n+1) = (L(E(L,a,n)))(next).  The expression (L(E(L,a,n)))(next) can be unwrapped to understand it better (L(E(L,a,n)))(next) = (L(a’))(next) where E(L,a,n) = a’. Then (L(a))(next) = f(next) where L(a)=f is a linked list element. So the final value is some a”, an element of A.
  5. Say (L,a) is a linked list iff for every element a’∈A s.t. L(a’) is defined,  there is some non-negative n so that E(L,a,n) = a’
  6. Say (L,a) is a circular linked list iff it is a linked list and for some n, E(L,a,n+1) = a.

Finite sequences of length n>0 can be represented mathematically as maps u:{0, … n-1}→ Y for some set Y.   If  (L,a) is a circular linked list, define u(0) = L(a)(value) and  u(n+1) =  L(E(L,a,n+1))  if E(L,a,n+1)=  a, and undefined otherwise.