Questions tagged [history]
Questions about genesis and development of computer science as a scientific discipline and its applications.
140
questions
2
votes
0
answers
42
views
Has Triangle Finding ever been faster than Matrix Multiplication?
The Triangle Finding problem (TF) in Graph Theory was shown by Itai and Rodeh in 1977 [1] to be solvable as fast$^1$ as Boolean Matrix Multiplication (BMM, Matrix Multiplication over $\{0, 1\}$ with ...
1
vote
0
answers
28
views
Did Jon von Neumann know about Claude Shannon's work when he wrote the "First Draft of a Report on the EDVAC?"
In the "First Draft" JvN described an adder circuit to do binary addition, which was a much faster way of doing computer addition than using decimal lookup tables as the ENIAC had done. JvN'...
- 111
1
vote
4
answers
196
views
Is the reason for a stack to decrease the size of a program (by adding the use of subroutines)?
The stack allows subroutines to be used. It can store return address for "return from subroutine" instruction (RTN) and also arguments for the function.
It is not possible to store return ...
- 133
2
votes
1
answer
77
views
Is there an algorithm which was originally invented to solve a contrived problem but later found practical use?
This is probably a computer science history question.
Is there an algorithm which was originally invented to solve a contrived problem but later found practical use?
- 326
1
vote
0
answers
55
views
First piece of code in scientific papers
What is the first/oldest piece of source code shown in an scientific paper or journal? I am looking for source code of assembly or a high level programming language which was real (implemented) and ...
- 111
2
votes
2
answers
90
views
Why do combinators look this way?
Out of curiosity, why do combinators look this way? For example, why is $K = \lambda x y \to x$ and why is it called $K$? Why is it not $\lambda x y f m \to f m x$? These are just arbitrary letters, I ...
- 121
6
votes
1
answer
1k
views
Which Turing Award winners have supervised the PhDs of other Turing Award winners?
John McCarthy won the Turing Award in 1971 [1]. Two students whose PhD he supervised went on to win Turing Awards:
Raj Reddy (1994) [2]
Barbara Liskov (2008) [3]
What other Turing Award winners ...
- 1,548
1
vote
4
answers
445
views
Why is C still the fastest? Critique my take
A friend and I were surprised that C still has near-best performance among languages. I thought about why this is, and I wrote up a few paragraphs. I wonder if the friendly folks on CS stack could ...
- 115
2
votes
0
answers
134
views
What is the etymology of "swizzle"?
The word swizzle can refer to an operation performed in GPU algorithms:
[The] ability to compose vectors by arbitrarily rearranging and combining components of other vectors.
Swizzle (computer ...
- 121
0
votes
0
answers
28
views
SMP operating system that had been "proven" to be bug free?
Many years ago someone told me about a historical SMP operating system (or program?) that had been all but proven to be bug free (or something close to this). But yet turned out to have bugs that were ...
- 253
1
vote
2
answers
78
views
Who said first "In practice, log log N is at most (single digit number)?"
In one of my undergrad theory or algorithms classes, I remember a professor sharing a quip that went something like
In practice, $\log(\log(N))$ is at most 9.
...the idea being that even though the ...
- 111
2
votes
0
answers
27
views
History of the category of effectful computations
The 1971 paper A Catalog of Optimizing Transformations contains this passage:
irreducible subprograms require special handling. (An irreducible
subprogram is one which maintains a history, performs I/...
- 41
8
votes
2
answers
144
views
Does the concept of "side-effect" predate functional programming?
When I was reviewing a book, I saw that there's a sentence claiming "side effect is a term coming from the domain of functional programming". I would think that the concept existed before ...
- 241
1
vote
1
answer
43
views
Oldest publication of the lower bound on comparison sort
We all know that the worst case complexity for comparison sort is in $\Omega(n\log(n))$, but who was the first to publish this?
Everywhere I look, people have their own proofs but no reference to the ...
2
votes
0
answers
16
views
What is the historical origin of the concept of a "clipping path"
Algorithms for clipping lines to a rectangle seem to have been invented by Ivan Sutherland in the late 60s.
At some point the rectangle was generalized to an arbitrary polygonal area, and these days ...
- 41
7
votes
0
answers
67
views
P=NP turns 50. 1971 STOC conference
Stephen Cook presented his seminal paper "The complexity of theorem-proving procedures" at the 1971 STOC (Symposium on Theory of Computing) conference which was held May 3-5, 1971 at Case ...
- 171
3
votes
0
answers
129
views
What is a good general-knowledge-level title description of Dr. Aho's and Dr. Ullman's body of work for which they were awarded the 2020 Turing Award?
I recently read in the New York Times that my old "Data Structures and Algorithms" class professor Dr. Ullman had received the Turing Award along with Dr. Aho. The article title was "...
- 131
3
votes
1
answer
115
views
Why is the address-of operator in C/C++ represented with the "&" symbol?
I've started learning C++, and I know a little bit of C. Something that always struck me as somewhat off was that the address-of operator is represented with the seemingly random ampersand (&) ...
- 31
1
vote
0
answers
50
views
How close are current computer technologies in terms of energy efficiency to the Landauer Limit?
I'm trying to figure out how close (in orders of magnitude) current computer technologies are in terms of energy efficiency to the Landauer Limit. However, I'm finding (seemingly) conflicting ...
- 11
26
votes
3
answers
6k
views
Is there any reason why the modulo operator is denoted as %?
I would like to know if there is any reason why many programming languages use the notation % for the modulo operator?
It is used in the most "famous" ...
- 1,046
0
votes
0
answers
47
views
How did we go from Binary to something like Python?
If there's one thing the pandemic has shown us its that High school Geometry did not save us. I am a high school math teacher and I understand my job and its usefulness only exist in a post scarcity ...
4
votes
2
answers
359
views
Origin of "Cookie" in Computing?
"Cookies" are a user-facing computing construct. They are codified in many technical specifications, including the earliest reference in an HTTP spec, RFC 2109, published February 1997.
Many ...
- 143
2
votes
0
answers
36
views
Is the discrepancy in Turing's representation of complete configurations intentional?
On page 235 of Turing's 1936 paper, in the figure marked (C), the illustration appears not to match the description. The description states that
space has been made on the left of the scanned symbol, ...
- 121
0
votes
0
answers
18
views
Term for language that abstracts program location?
What is the technical term that describes a programming language that abstracts (or at least largely abstracts) the machine location of programs? I’m thinking here specifically of the evolution of ...
- 121
3
votes
0
answers
45
views
What was the impact of Impagliazzo's A Personal View of Average Case Complexity?
I'm studying his paper and I was wondering how the community reacted to it. Yes, Average Case Complexity has come a long way since then, but I want to know if it was directly influenced by it.
- 141
1
vote
0
answers
27
views
Origin of GUI terminology
I'm wondering where the GUI terminology like modal dialogue comes from.
Who first used these terms? Is there a paper or a book, or was it just sw?
- 111
4
votes
2
answers
141
views
Origin of using ">" to represent child in a tree
What are the earliest known uses of the "greater than"/"chevron" symbol (>) to denote a parent-child relationship in a tree structure? i.e. parent > child
e.g.
...
0
votes
3
answers
1k
views
Why the 127 encodings of ASCII needed to be extended to 256?
As you all know the ASCII chart needed to be extended from 127 encoding to 256, I can't really see why. Some google expert on Coursera said "We needed that because of the foreign languages".
I still ...
54
votes
1
answer
11k
views
What is the earliest use of the "this" keyword in any programming language?
I understand the this (or self or Me) is used to refer to the current object, and that it is ...
- 651
2
votes
0
answers
79
views
What is the first programming language where the keyword "new" appeared?
It's really interesting when this keyword first appeared as a lot of popular languages but relatively old languages( C++, C#, Java, JS ) use it. I understand use of "new" in C++ in practical manner( ...
- 121
2
votes
0
answers
44
views
Similarities between Babbage's difference engine and the Turing machine
What would you consider similarities between the difference engine and the Turing machine? At this point I feel I know how they both function, yet I can't point out any worthwhile similarities between ...
- 21
0
votes
1
answer
475
views
Who invented the adder, full-adder, half-adder?
I didn't find, in the digital design books, who invented the adders.
The same person invented the half-adder and the full-adder?
What's the oldest publication on digital arithmetic design?
- 1
2
votes
0
answers
23
views
When did our current concepts of program modularity develop?
I take it that the concept of a modular subroutine call/return existed prior to the concept of a call stack (and hence to the possibility of recursive subroutines or of recursion limits). I would ...
- 121
4
votes
1
answer
324
views
Why are struct and class essentially the same in C++?
struct and class in C++ are nearly identical (as covered for example here).
But why is this so? What did happen when C++ was ...
- 153
1
vote
0
answers
36
views
How many floating point ops were performed worldwide over a time interval [closed]
I am looking for information regarding the evolution of computing capability. Specifically I would like to know how many floating point operations were performed worldwide from, say, the deployment of ...
- 111
3
votes
1
answer
136
views
Lambda Calculus as a branch of set theory
This answer to a question about whether C is the mother of all languages contained an interesting tidbit that I am curious about:
The functional paradigm, for example, was developed mathematically (...
- 1,672
1
vote
0
answers
47
views
Design considerations of datatypes in early programming languages like C
Although type theory originated (e.g. already discussed by Russell in 1910s) much earlier than programming languages, I have this feeling that languages such as C considered type-checking from a very ...
- 259
1
vote
0
answers
679
views
Four Pillars of Object Oriented Programming
I'm researching object oriented programming and I've come across the term "four pillars of OOP" in a few places now.
I originally saw them listed as:
Abstraction
Encapsulation
Inheritance
...
- 123
1
vote
0
answers
135
views
Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?
McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960).
...
- 133
0
votes
1
answer
41
views
Origin of a story about a computer in the 50's recommending offing Pensioners [closed]
There's a story I've heard a few times in various computer science talks, usually offered as a cautionary tale, that goes something like this:
In the late 50s, the British gov't purchased an early ...
- 101
1
vote
1
answer
45
views
Interpretation of Turing's statement on universal computers
I'm currently reading a book about artificial intelligence and i frequently come across the concept of universal computers, as it is essential to understand the book i would like to know the meaning ...
- 113
1
vote
1
answer
2k
views
Reason programming language B was named "B"?
I’ve searched around for this already but ironically the results have been overshadowed by “Why C was named C” instead.
If C was named “C” because it came after B, why was B named "B", since the only ...
- 21
7
votes
1
answer
998
views
Who first introduced the pushdown automaton?
I'm interested in learning more about the history of automata theory and have tracked down many of the original papers on Turing machines, finite automata, and the like. However, I'm having trouble ...
- 9,027
1
vote
1
answer
143
views
How the concept of computer change over time? [closed]
There was a time when a "computer" was a person who worked on accounts. However, machines were introduced and this profession eventually died out over time. The definition below was taken ...
- 111
0
votes
1
answer
217
views
Did Date and Darwen's "Third Manifesto" have a lasting impact?
In 1995, two DB theory researchers, C.J. Date and H. Darwen, published a text with the rather impressive-sounding name "The Third Manifesto" with their ideas regarding future DBMSes, which would ...
- 955
1
vote
1
answer
54
views
Problems with decidability open (for a long time) proven decidable
It seems to me that problems whose dedicability remains open for a long time, if resolved, tend to end up being undecidable. A prominent example would be (e.g.) Hilbert's tenth problem, whose ...
- 727
2
votes
1
answer
91
views
liskov substitution principle seems to have two conventional meanings
This is a question about the semantics of the name, rather than about the principle itself. What is the Liskov Substitution Principle (LSP)?
LSP seems to have two meanings in the literature I've ...
- 315
5
votes
1
answer
339
views
What was Robert Floyd's algorithm for inserting brackets?
In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other ...
- 151
5
votes
0
answers
113
views
Which languages, if any, implemented parametric polymorphism before ML?
In particular, was there any kind of implementation at the time Christopher Strachey wrote Fundamental Concepts in Programming Languages?
In that work, Strachey lists Ad Hoc and Parametric ...
- 224
1
vote
1
answer
43
views
Why strokes are treated differently than fills in modern graphics pipelines
This article shows some of the issues. But basically, on the web, you have fillStyle and strokeStyle, and in WebGL you have ...
- 2,163