keithwinstein

Joined 16 years ago

Karma
2,911
Submissions
244
Member since
Feb 9
[ my public key: https://keybase.io/keithw; my proof: https://keybase.io/keithw/sigs/kUgJ1P7zCp6UL3Tp_vdSCCTgeGAma0TblJSSpuQHbTI ]
View on Hacker News

Recent submissions

Comment · 3 months ago
This is really cool stuff, and I agree the future is likely to look more like this. I was surprised by the last two paragraphs ("Aside: verified assembly") -- my understanding was that this future is basically already here. I believe agl's colleagues at Google have already deployed some auto-mutated verified assembly versions of some crypto routines, based on the Fiat Crypto + CryptOpt work (https://arxiv.org/pdf/2211.10665), both involving Andres Erbsen who I think is currently at Google before starting a professorship soon. I dunno if this work would count as "cheap" (it looks like Fig. 10 unfolds over the course of a day) but spending a day auto-exploring many verified-correct machine code implementations of the same routine to find the fastest one (which you then ship forever) doesn't seem impractically expensive either.
Comment · 4 months ago
Looks very interesting! We have done a lot with WasmCert-Isabelle (and there's also WasmRef-Isabelle and their 2023 paper, and the earlier WasmCert-Coq); other than being in Lean instead of Isabelle/HOL or Coq, how would you compare the approach you used? E.g. are you able to do an "in-place Store" like WasmRef-Isabelle, and can you represent memories and tables as plain vectors of bytes/refs in memory, can you grow them in-place, etc.? Or any other optimizations/lessons learned?

I'm also curious -- are you just implementing the Wasm binary and text parsing, validation algorithm, and execution semantics in Lean from scratch by reading the English prose in the spec document, and then checking it against the spec tests and the SpecTec description? Or do you have some sort of automated (classical or LLMy) transformation happening? (One could imagine directly transforming the SpecTec, or the OCaml reference interpreter, into Lean... but it sounds like you're not doing that? I think one needs to be a little careful here because e.g. at this point some of the English prose and reference interpreter implementation, and I think maybe some of the tests, are autogenerated from the SpecTec.) Which parts (if any) are outside the scope of the formalization? E.g. for WasmCert-Isabelle, I believe the binary and definitely the text parsing, and I think some of the arithmetic ops, are not covered.

How are you modeling the explicit sources of nondeterminism in the Wasm execution semantics? E.g. NaN representation, {memory., table.}grow, host calls, stack exhaustion, relaxed SIMD instructions, etc., and that's all before we get to the threads proposal? Because if the goal is to prove programs correct, one risk is that I prove my program correct against your Wasm interpreter (which maybe makes certain choices that aren't determined by the spec), and then I run it against another fully-conforming interpreter in the wild and it behaves incorrectly.

Comment · 4 months ago
> Constitutionally, only the federal government is allowed to regulate intellectual property

It turns out that's not exactly the case! See, e.g., Goldstein v. California, 412 U.S. 546 (1973). Before 1978, state (often common law) copyright used to cover a lot of pre-publication works, and until 2018 (when the federal law was amended) state copyright law covered pre-1972 sound recordings, and state copyright still covers obscure things like post-mortem moral rights in visual art or rights to "unfixed" works. See 1 Nimmer on Copyright §§ A.02 & 2.02. Other forms of intellectual property (trade secrets, rights of publicity) remain mostly creatures of state law, and some states also have trademark systems.

Comment · 5 months ago
> For 8-bit, 16 maps to 7.5IRE which is the well understood legal black. Mapping 235 means they mapped peak to 110IRE.

Generally no -- in an 8-bit NTSC-M Rec. 601 system, 16 maps to E'Y = 0 at 7.5 IRE, and 235 maps to E'Y = 1 at 100 IRE. See https://www.poynton.ca/pdf/Poynton-1996-TechIntrDigiVide.pdf

The "16" digital black level is independent of the "7.5 IRE" analog setup. E.g. in Japan with an 8-bit "NTSC-J" Rec. 601 system, my understanding is that 16 still maps to E'Y = 0 which is now at 0 IRE, and 235 is still E'Y = 1 at 100 IRE.

Comment · 6 months ago
I can't speak to Binaryen, but afaik WABT's wat2wasm and wasm-tools's wat2wasm (aka wasm-tools parse) are both 100% spec-correct in this respect. Parsing the Wasm text format doesn't require any knowledge of the type of each instruction. If you have a counterexample would love to see it!

There are some cool edge cases if you want to print a mismatched multi-value instruction sequence in the folded form (which WABT and wasm-tools again handle "correctly," but not identically to each other, and not particularly meaningfully).

Comment · 9 months ago
Comment · 1 year ago
> Even more pedantically, “standard time” is not necessarily consistent across each zone (particularly, during the period for which in parts of the zone it is advanced by an hour) since "standard time” only advances for those states, or parts of states, for which an exemption is not in place.

I can't find a source (including 15 U.S.C. § 260a) that supports this reading, although I agree it's a little ambiguous. The law suggests that a region that doesn't observe DST is observing "the standard time otherwise applicable during that period" and is exempt from the provisions regarding advancement, not that "Pacific standard time" depends on where you are (see 15 U.S.C. § 263).

> So, the Unix-y convention [] is the simplest way

No argument there!

Comment · 1 year ago
Comment · 1 year ago
Shades of https://www.theregister.com/2006/03/24/tuttle_centos/ (from simpler times, almost 20 years ago!)
Comment · 1 year ago
This story has been reposted many times, and I think GJS's remarks (as recorded by Andy Wingo) are super-interesting as always, but this is really not a great account of "why MIT switched from Scheme to Python."

Source: I worked with GJS (I also know Alexey and have met Andy Wingo), and I took 6.001, my current research still has us referring to SICP on a regular basis, and in 2006 Kaijen Hsiao and I were the TAs for what was basically the first offering of the class that quasi-replaced it (6.01) taught by Leslie Kaelbling, Hal Abelson, and Jacob White.

I would defer to lots of people who know the story better than me, but here's my understanding of the history. When the MIT EECS intro curriculum was redesigned in the 1980s, there was a theory that an EECS education should start with four "deep dives" into the four "languages of engineering." There were four 15-unit courses, each about one of these "languages":

- 6.001: Structure and Interpretation of Computer Programs (the "procedural" language, led by Abelson and Sussman)

- 6.002: Circuits and Electronics ("structural" language)

- 6.003: Signals and Systems ("functional" language)

- 6.004: Computation Structures ("architectural" language)

These were intellectually deep classes, although there was pain in them, and they weren't universally beloved. 6.001 wasn't really about Scheme; I think a lot of the point of using Scheme (as I understood it) is that the language is so minimalist and so beautiful that even this first intro course can be about fundamental concepts of computer science without getting distracted by the language. This intro sequence lasted until the mid-2000s, when enrollment in EECS ("Course 6") declined after the dot-com crash, and (as would be expected, and I think particularly worrisome) the enrollment drop was greater among demographic groups that EECS was eager to retain. My understanding circa 2005 is that there was a view that EECS had broadened in its applications, and that beginning the curriculum with four "deep dives" was offputting to students who might not be as sure that they wanted to pursue EECS and might not be aware of all the cool places they could go with that education (e.g. to robotics, graphics, biomedical applications, genomics, computer vision, NLP, systems, databases, visualization, networking, HCI, ...).

I wasn't in the room where these decisions were made, and I bet there were multiple motivations for these changes, but I understood that was part of the thinking. As a result, the EECS curriculum was redesigned circa 2005-7 to de-emphasize the four 15-unit "deep dives" and replace them with two 12-unit survey courses, each one a survey of a bunch of cool places that EECS could go. The "6.01" course (led by Kaelbling, Abelson, and White) was about robots, control, sensing, statistics, probabilistic inference, etc., and students did projects where the robot drove around a maze (starting from an unknown position) and sensed the walls with little sonar sensors and did Bayesian inference to figure out its structure and where it was. The "6.02" course was about communication, information, compression, networking, etc., and eventually the students were supposed to each get a software radio and build a Wi-Fi-like system (the software radios proved difficult and, much later, I helped make this an acoustic modem project).

The goal of these classes (as I understood) was to expose students to a broad range of all the cool stuff that EECS could do and to let them get there sooner (e.g. two classes instead of four) -- keep in mind this was in the wake of the dot-com crash when a lot of people were telling students that if they majored in computer science, they were going to end up programming for an insurance company at a cubicle farm before their job was inevitably outsourced to a low-cost-of-living country.

6.01 used Python, but in a very different way than 6.001 "used" Scheme -- my recollection is that the programming work in 6.01 (at least circa 2006) was minimal and was only to, e.g., implement short programs that drove the robot and averaged readings from its sonar sensors and made steering decisions or inferred the robot location. It was nothing like the big programming projects in 6.001 (the OOP virtual world, the metacircular evaluator, etc.).

So I don't think it really captures it to say that MIT "switched from Scheme to Python" -- I think the MIT EECS intro sequence switched from four deep-dive classes to two survey ones, and while the first "deep dive" course (6.001) had included a lot of programming, the first of the new survey courses only had students write pretty small programs (e.g. "drive the robot and maintain equal distance between the two walls") where the simplest thing was to use a scripting language where the small amount of necessary information can be taught by example. But it's not like the students learned Python in that class.

My (less present) understanding is that >a decade after this 2006-era curricular change, the department has largely deprecated the idea of an EECS core curriculum, and MIT CS undergrads now go through something closer to a conventional CS0/CS1 sequence, similar to other CS departments around the country (https://www.eecs.mit.edu/changes-to-6-100a-b-l/). But all of that is long after the change that Sussman and Wingo are talking about here.

Comment · 1 year ago
Comment · 1 year ago
Comment · 2 years ago
The first edition of SICP came out in the fall of 1984 (a year after these Hofstadter columns). This fall is the 40th anniversary!
Comment · 2 years ago
No -- as discussed upthread, clang's musttail attribute requires the target function to have the same number of arguments as the caller and for each argument to be similar to the corresponding caller argument. That's stricter than the underlying LLVM musttail marker (when targeting the tailcc/swifttailcc calling conventions) and is too restrictive to implement Wasm's tail-call feature (and probably Scheme's, etc.), at least if arguments are getting passed to functions natively.

It would be nice if the more relaxed rules of the LLVM musttail marker with tailcc could be exposed in clang (and gcc). I think that's basically what "return goto" would do.

Comment · 2 years ago
Yes, wasm2c implements the Wasm tail-call feature with trampolines, exactly this way. (https://github.com/WebAssembly/wabt/blob/main/test/wasm2c/ta... has an example.)

Doing it with a trampoline is probably slower than if C really had tail calls. On the other hand, adding "real" tail calls to C would probably require changing the ABI (e.g. to "tailcc" or "fastcc -tailcallopt"), and I think there's some reason to think this would probably impose a penalty everywhere (https://llvm.org/docs/CodeGenerator.html#tail-call-optimizat...).

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton