3 ms·

Can anyone explain the etymology of "witness table"?

• johncolanduoni 10y ago
  The only analogy I can think of is to a "witness" to a logical proposition in mathematics. In this case the witnesses "prove" that the given concrete type implements the given abstract type. If that's the case it's kind of a weird way to put it, though it sort of squares with the witnesses in proof-relevant formulations of logout where you care about the form of a proof and not just what it proves.
• KingOfBrian 10y ago
  Good question, I'll update the post if I can figure it out. It turns out that swift uses both witness and virtual tables, something I'm realizing I didn't make very clear in the post. https://github.com/apple/swift/blob/master/docs/SIL.rst#vtables https://github.com/apple/swift/blob/master/docs/SIL.rst#vtab... has some more interesting information.
• Someone 10y ago
  I agree with johncolanduoni that it likely derives from https://en.wikipedia.org/wiki/Witness_(mathematics) https://en.wikipedia.org/wiki/Witness_(mathematics): "a witness is a specific value t to be substituted for variable x of an existential statement of the form ∃x φ(x) such that φ(t) is true" In the less abstract: a witness is someone who, because he has looked at data, can tell you something about that data. A witness table contains the statements of multiple witnesses. In this case, the statements are of the form "'A' is a value for which the statement 'you can find the code implementing method M for class C at address x' is true". As the article states "Most languages refer to this as a “virtual table". I find the use of Witness table strange here. I know it from string matching algorithms, where the witness statements are of forms such as "if you start comparing here, the fourth character is the first that doesn't match".