One of the greats. Invented quicksort and concurrent sequential processes. I always looked up to him because he also seemed very humble.
Several keywords used in many programming languages come from Hoare, who either coined them himself, or he took them from another source, but all later programming language designers took them from Hoare. For example "case", but here only the keyword comes from Hoare, because a better form of the "case" statement had been proposed first by McCarthy many years earlier, under the name "select".
Another example is "class" which Simula 67, then all object-oriented languages took from Hoare, However, in this case the keyword has not been used first by Hoare, because he took "class", together with "record", from COBOL.
Another keyword popularized by Hoare is "new" (which Hoare took from Wirth, but everybody else took from Hoare), later used by many languages, including C++. At Hoare, the counterpart of "new" was "destroy", hence the name "destructor", used first in C++.
The paper "Record Handling", published by C.A.R. Hoare in 1965-11 was a major influence on many programming languages. It determined significant changes in the IBM PL/I programming language, including the introduction of pointers . It also was the source of many features of the SIMULA 67 and ALGOL 68 languages, from where they spread in many later programming languages.
The programming language "Occam" has been designed mainly as an implementation of the ideas described by Hoare in the "Communicating Sequential Processes" paper published in 1978-08. OpenMP also inherits many of those concepts, and some of them are also in CUDA.
>OpenMP also inherits many of those concepts, and some of them are also in CUDA.
His “billion dollar mistake”:
https://www.infoq.com/presentations/Null-References-The-Bill...
Optional types were a very valuable invention and the fact that null values have been handled incorrectly in many programming languages or environments is not Hoare's fault.
There are two ways this might happen, both will solve the Billion Dollar Problem but I think one is the clear winner. The first way is explicit optionality, often retro-fitted to languages for example in C# the difference between the types Goose and Goose? are that (in a suitable C# project enabling this rule) the first one is always a Goose and the second might be null instead.
The second way is if you have Sum types you can just add "or it's null" to the type.
I think sum types are better because they pass my "three purposes" rule where I can think of not one (Option<T> replaces optionality) or two (Result<T,E> for error handling) but at least three (ControlFlow<B, C> reifies control flow) distinct problems I don't need separate solutions for any more if I have this feature.
If your type system is too weak you suffer the Billion Dollar problem with Hoare's idea and perhaps if this "feature" had never been invented we'd have all migrated to languages with a better type system decades ago.
In my opinion, besides being passed as arguments of functions whose parameters are declared as having the corresponding Optional or Sum type, there is only one other permissible use of values of such types.
Variables of an Optional type shall be allowed in the Boolean expression of an "if" or equivalent conditional statement/expression, while variables of a Sum type shall be allowed in an expression that tests which is the current type in a select/case/switch or whatever is the name used for a conditional statement or expression with multiple branches.
Then in the statements or expressions that are guarded by testing the Optional- or Sum-type variable, that variable shall be used as having the corresponding non-optional type or the type among those possible for a Sum type that has been determined by the test.
This syntax ensures that such variables will not be misused, while also avoiding the excessive and unhelpful verbosity that exists in some languages.
When you muddle these things it makes life very slightly easier, very briefly and then you introduce impossible to find bugs and ruin your life. People tend to imagine that OK, maybe C went too far with coercions, but I can handle smaller things, that'll be fine, and in my experience they're wrong.
I like the fact that in Rust I'm expected to write if opt.is_none() rather than just treat it as if it was a boolean when it isn't. The resulting machine code isn't different, so we're talking about communicating our intent to human programmers, such as our future selves or our colleagues and I'm certain opt.is_none() communicates that intent better than coercing it to a boolean.
I don't like the other idea you propose, but it's less of a footgun and so I don't mind that e.g. C# programmers often write this way. I wouldn't choose it myself in many cases, but I don't write "No, fix this" in reviews of such code.
The prime operation and address mapping.
The prime operation defines a certain single‑argument function. Its symbol (a prime mark) is written above and to the left of the argument: 'a = b where a is the argument and b is the result of the operation. This is read as: "prime a equals b" (or "b is the contents of a"). The argument a is called an address, and the function value b is called the contents of the address. The prime function ' defines a mapping from the set of addresses A to the set of contents B, which we will call an address mapping.
Page 36, chapter III https://torba.infoua.net/files/kateryna-yushchenko/Vychislit...
In any case, by 1954 already most or all electronic computers used this.
The only priority questions can refer to which are the first high-level programming languages that have used pointers.
In my opinion the first language having pointers with implicit dereferencing was CPL, published in 1963-08, and the first language having pointers with explicit dereferencing was Euler, published completely in 1966-01, but this feature had already been published in 1965-11. The first mainstream programming language, with a large installed base, which had pointers, was the revised IBM PL/I, starting with its version from 1966-07.
Thanks for the link to the book describing the "Kiev" computer. It seems an interesting computer for the year 1957, but it does not have anything to do with the use of pointers in high-level programming languages.
At the page indicated by you there is a description of what appears to be a symbolic assembler. The use of a symbolic assembly language was a great progress at that early date, because many of the first computer programs had been written directly in machine language, or just with a minimal translation, e.g. by using mnemonics instead of numeric opcodes.
However this does not have anything to do with HLL pointers and means to indicate indirect addressing in an assembly language have existed earlier, because they were strictly necessary for any computed that provided indirect addressing in hardware.
In the very first computers, the instructions were also used as pointers, so a program would modify the address field of an instruction, which was equivalent to assigning a new value to a pointer, before re-executing the instruction.
Later, to avoid the re-writing of instructions, both index registers and indirect addressing were introduced. Indirect addressing typically reserved one bit of an address to mark indirection. So when the CPU loaded a word from the memory, if the indirect addressing bit was set, it would interpret the remainder of the word as a new address, from which a new word would be loaded. This would be repeated if the new word also had the indirection bit set.
The assembly languages just had to use some symbol to indicate that the indirection bit must be set, which appears to have been "prime" for "Kiev".
I could only find a manual for PDP-10 Euler with references. Do you have a source for an Euler with pointers?
The distinction that exists in C++ between "reference" and "pointer" is something very recent. In the past the 2 terms were synonymous.
The term "pointer" was introduced by IBM PL/I in July 1966, where it replaced "reference".
PL/I has introduced many terms that have replaced previously used terms. For example:
reference => pointer
record => structure
process => task
and a few others that I do not remember right now.
"Pointer" and "structure" have become dominant after they have been taken by the C language from PL/I and then C has become extremely popular. Previously "reference" and "record" were more frequently used.
So it had everything that C has, except pointer arithmetic.
Only a subset of the programming languages that have pointers also allow pointer arithmetic, because many believe that whenever address arithmetic is needed only indices shall be used, not pointers, because with indices it is much easier for the compiler to determine the range of addresses that may be accessed.
If you are still interested, you can look at page 35, where there are several examples, including finding the GCD.
The use of pointers in assembly language does not count as an invention, as it was used since the earliest automatic computers. The use of implicit reference variables, which cannot be manipulated by the programmer, like in FORTRAN IV (1962) does not count as pointers.
The method for forcing another level of evaluation of a variable by using a "$" prefix, which was introduced in SNOBOL in January 1964, and which has been inherited by the UNIX shell and its derivatives does not count as a pointer.
The term "pointer" was introduced in a revision of the IBM PL/I language, which was published in July 1966. In all earlier publications that I have ever seen the term used was "reference", not "pointer".
There are 2 high-level programming languages that were the first to introduce explicit references (i.e. pointers). One language was Euler, published in January 1966 by Niklaus Wirth and Helmut Weber. However Hoare knew about this language before the publication, so he mentioned it in his paper from November 1965, where he discussed the use of references (i.e. pointers).
The other language was the language CPL, which had references already in August 1963. The difference between how CPL used references and how Euler used references is that in Euler pointer dereferencing was explicit, like later in Pascal or in C. On the other hand, in CPL (the ancestor of BCPL), dereferencing a pointer was implicit, so you had to use a special kind of assignment to assign a new value to a pointer, instead of assigning to the variable pointed by the pointer.
Looking now in Wikipedia, I see a claim that Bud Lawson has invented pointers in 1964, but there is no information about where he has published this and about which is the high-level programming language where the pointers of Bud Lawson had been used.
If the pointers of Bud Lawson were of the kind with explicit dereferencing, they would precede by a year the Euler language.
On the other hand, if his pointers were with implicit dereferencing, then they came a year after the British programming language CPL.
Therefore, in the best case for Bud Lawson, he could have invented an explicit dereferencing operator, like the "*" of C, though this would not have been a great invention, because dereferencing operators were already used in assembly languages, they were missing only in high-level languages.
However, the use of references a.k.a. pointers in a high-level programming language has already been published in August 1963, in the article "The main features of CPL", by Barron, Buxton, Hartley, Nixon and Strachey.
Until I see any evidence for this, I consider that any claim about Bud Lawson inventing pointers is wrong. He might have invented pointers in his head, but if he did not publish this and it was not used in a real high-level programming language, whatever he invented is irrelevant.
I see on the Internet a claim that he might have been connected with the pointers of IBM PL/I.
This claim appears to be contradicted by the evidence. If Bud Lawson had invented pointers in 1964, then the preliminary version of PL/I would have had them.
In reality, the December 1964 version of PL/I did not have pointers. Moreover, the first PL/I version used in production, from the middle of 1965 also did not have pointers.
The first PL/I version that has added pointers was introduced only in July 1966, long enough after the widely-known publications of Hoare and of Wirth about pointers. That PL/I version also added other features proposed by Hoare, so there is no doubt that the changes in the language were prompted by the prior publications.
So I think that the claim that Bud Lawson has invented pointers is certainly wrong. He might have invented something related to pointers, but not in 1964.
PL/I had one original element, the fact that pointer dereferencing was indicated by replacing "." with "->". This has later been incorporated in the language C, to compensate its mistake of making "*" a prefix operator.
The "->" operator is the only invention of PL/I related to pointers, so that is a thing that has been invented by an IBM employee, but I am not aware of any information about who that may be. In any case, this was not invented in 1964, but in 1966.
https://dl.acm.org/doi/epdf/10.1145/363332.363344
PS He didn't mention it in his recollections [1], but 1978 paper The Early History and Characteristics of PL/I [2] claims that a paper was produced in October 1965.
[1] https://archive.computerhistory.org/resources/access/text/20... [2] https://dl.acm.org/doi/pdf/10.1145/960118.808389
Like I have said, PL/I did not have pointers in the beginning, i.e. since 1964 until July 1966.
So I think that this claim about Lawson having invented pointers comes from a misunderstanding. It is likely that Lawson has been the lead developer for adding pointers to PL/I.
Someone has heard this and because the first version of PL/I was developed during 1964, a false conclusion was inferred, i.e. that Lawson had invented pointers in 1964, before Euler.
That conclusion was wrong, because pointers have been added to PL/I much later, not during the initial development.
The paper written by Lawson about using pointers was sent for publication in August 1966, i.e. one month after the official introduction of a new PL/I version with pointers.
Due to the timing of the implementation of a PL/I extension with pointers, a short time after a public debate about how programming languages such as ALGOL must be improved, with most proposals integrated and analyzed in the papers published by Hoare, Wirth and a few others, I believe that it is rather certain that the impulse to add pointers to PL/I was not internal to IBM, but it was caused directly or indirectly by watching this debate.
The paper written by Radin, linked by you, confirms that IBM has added pointers to PL/I after an important customer, General Motors, has requested this, presumably in Q4 1965.
Because Lawson was the one who reported the end result of this work of extending PL/I with pointers, I assume that he was the lead developer of this project, which must have happened mostly during the first half of 1966.
As I have said, the only original element of the PL/I pointers was the "->" indirect addressing operator. Unlike in C, no other operator was needed, because PL/I followed the recommendation of Hoare, which was to use pointers only as structure members, where they are useful for implementing linked data structures, and not also as independent variables.
Therefore it seems likely that Harald Lawson was the one who invented the "->" operator.
However, he clearly had not invented pointers, as those (under the alternative name of "references") had been used earlier in the languages CPL and Euler and the implementation of pointers in PL/I done by Lawson followed closely the recommendations made by Hoare in his "Record Handling" paper.
He states around minute 25 the solution to the problem is to explicitly represent null in the type system, so nullable pointers are explicitly declared as such. But it can be complex to ensure that non-nullable references are always initialized to a non-null value, which is why he chose the easy solution to just let every reference be nullable.
&ref_that_cannot_be_null
*ref_that_can_be_null
ref_that_can_be_null->thing()
It's an error that can be caught by the type system (any number of other languages demonstrate that), and null pointer derefs are one of those bugs that just plague the languages that have it.
C# also supports null-safety, although less elegantly and as opt-in. If enabled, it won’t let you deference a possibly-null reference.
It will moan, it doesn't stop you from doing it, our C# software is littered with intentional "Eh, take my word for it this isn't null" and even more annoying, "Eh, it's null but I swear it doesn't matter" code that the compiler moans about but will compile.
The C# ecosystem pre-dates nullable reference types and so does much of our codebase, and the result is that you can't reap all the benefits without disproportionate effort. Entity Framework, the .NET ORM is an example.
there was a time, 10-15 years ago, when they were super cool. at some point they """diluted""" the technicality content and the nature of guests and they vanished into irrelevance.
Hoare Logic - https://en.wikipedia.org/wiki/Hoare_logic
Hoare Logic + Dijkstra's weakest precondition + Meyer's Design-by-Contract is what should be used to get LLMs to generate proof with code in a correctness-by-construction approach to implementation.
References:
Correctness-by-Construction (CbC) - https://www.tu-braunschweig.de/en/isf/research/cbc
A Course on Correctness by Construction - https://wp.software.imdea.org/cbc/
However, they were not just concurrent, but also communicating.