Hot answers tagged

82

An excerpt from History of Lambda-calculus and Combinatory Logic by F. Cardone and J.R. Hindley(2006): By the way, why did Church choose the notation “$\lambda$”? In [Church, 1964, §2] he stated clearly that it came from the notation “$\hat{x}$” used for class-abstraction by Whitehead and Russell, by first modifying “$\hat{x}$” to “$\wedge x$” to ...


60

Simula 67 is generally considered the first object-oriented language and predates Smalltalk by a number of years. It also used the this keyword for the same concept, which can be seen in this book chapter extract: class Linker; begin ref(Linker) Next, Sex, Employment; text ID; procedure Add_to_List(LHead); name LHead; ref(Linker) LHead; ...


39

Computer science is a misnomer - there is actually no "science" in computer science, since computer science is not about observing nature. Rather, parts of computer science are engineering, and parts are mathematics. The more theoretical parts of computer science are purely mathematical. For example, what is a good algorithm for sorting? How do we define ...


34

"So why was assembly language created?" Assembly language was created as an exact shorthand for machine level coding, so that you wouldn't have to count 0s and 1s all day. It works the same as machine level code: with instructions and operands. "Which one came first?" Wikipedia has a good article about the History of Programming Languages "Why am I ...


31

Why do we need assembly language? Well, there's actually only one language we will ever need, which is called "machine language" or "machine code". It looks like this: 0010000100100011 This is the only language your computer can speak directly. It is the language a CPU speaks (and technically, different types of CPUs speak different versions). It also ...


29

[Note: this paragraphs is now outdated.] The title of your question contains an unwarranted assumption, namely that programming languages are "based on foundations of mathematics". This is generally not the case, although the two areas do have important relationships. A more accurate statement would be that (some) programming languages were designed using ...


20

In the 1920's and 1930's people were trying to figure out what it means to "effectively compute a function" (remember, there were no general purpose computing machines around, and computing was something done by people). Several definitions of "computable" were proposed, of which three are best known: The $\lambda$-calculus Recursive functions Turing ...


19

The founders of computability theory were mathematicians. They founded what is now called computability theory before there was any computers. What was the way mathematicians defined functions that could be computed? By recursive definitions! So there were recursive function before there were any other model of computation like Turing machines or lambda ...


18

There is no "official Turing test" so there's no concept of "officially pass[ing] the test". Turing described a methodology that one might use to evaluate artificial intelligences. The organizers of the event that Eugene Goostman won implemented that methodology in a particular way and the program satisfied the criteria the organizers had chosen. In that ...


17

This is a good question. It appears that the term server was commonly used already in 1960s. For example, RFC 5, which was published in 1969, already uses the term, and it seems that it was in a common use already back then. However, the term client in this context seems to be much more recent; the earliest references that I was able to find are from 1978. ...


16

So why was assembly language created? or was it the one that came first even before high level language? Yes, assembly was one of the first programming languages which used text as input, as opposed to soldering wires, using plug boards, and/or flipping switches. Each assembly language was created for just one processor or family of processors as the ...


15

Define some basic functions: zero function $$ zero: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto 0 $$ successor function $$ succ: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto x + 1 $$ projection function $$p_i^n: \mathbb{N}^n \rightarrow \mathbb{N} : (x_1, x_2, \dots, x_n) \mapsto x_i $$ From now on I will use $\bar{x_n}$ to denote $(x_1, x_2, \...


14

Let me add one less practical aspect. This is (probably) not a historic reason but a reason for you, today. Assembly (compared to high-level languages) is naked. It does not hide anything (that is done in software), and it is simple in the sense that it has a relatively small, fixed set of operations. This can be helpful for exact algorithm analysis. ...


14

There is no strong technical reason. We could have used Diffie-Hellman (with appropriate signatures) just as well as RSA. So why RSA? As far as I can tell, non-technical historical reasons dominated. RSA was patented and there was a company behind it, marketing and advocating for RSA. Also, there were good libraries, and RSA was easy to understand and ...


13

Wikipedia says that the first use of tree in mathematics was by Cayley in 1857. Since the use in computer science is taken directly from mathematics, it seems more fundamental to ask when they originated there. Unless computer scientists originally called trees something else, the first computer scientist to use "tree" doesn't seem any more significant than,...


11

Let us start with a quote from one of the fathers of modern Computer Science: “Computer Science is no more about computers than astronomy is about telescopes” - Edsger Wybe DIJKSTRA So in reality if what you are interested in is computers and programming then you are not truly interested in computer science :-) I think Wikipedia has one of the best ...


11

It might be worth mentioning that the German term for "Computer Science" is Informatik, which melts Infomation and Mathematik. I think that's a nice and short description of what Computer Science is all about. (the Italian term is informatica, and I'm sure there are quite a few more languages that follow the same line).


11

According to Donald Knuth's TAOCP, Vol. 1, pg. 459 the following papers might be considered as one of the first appearances of trees in CS. H. G. Kahrimanian, Analytical Differentiation by a Digital Computer, Symposium on Automatic Programming, 6–14, 1952 K.E. Iverson and L.R. Johnson, IBM Corp. research reports RC-390, RC-603, 1961 A.J. Perils and C. ...


11

The German Wikipedia claims that $\lambda$ comes from "leer", which means "empty" in German. That seems plausible, as German used to be one of the major languages in mathematics. Chomsky used $I$ as the empty string (or actually as the identity element for string concatenation) in his early papers. Some people in combinatorics still use $1$ as the empty ...


11

The seminal paper referred to is "Syntactic Analysis and Operator Precedence" (1963), which describes the operator precedence algorithm still used by many simple expression parsers today. The basic approach described by Floyd was not exactly new. It was described by Edsger Dijkstra in 1961; Dijsktra's procedure was a pragmatic, special-purpose algorithm ...


11

ASCII has 128 characters. Many countries had similar encodings for 128 characters. That is all history. Nobody uses ASCII anymore. There was a phase with lots of different encodings for more than 128 characters, some with 256 (Mac Roman and Windows 1152 were quite popular) and some like the Chinese GB with thousands of characters. Nowadays people mostly ...


10

Diffie–Hellman lacks a crucial feature: authentication. You know you are sharing a secret with someone, but you can't know if it's the recipient or a man in the middle. With RSA, you may have a few trusted parties who store public keys. If you want to connect to your bank, you can ask the trusted party (let's say Verisign) for the bank's public key, as ...


10

here is some other near-firsthand info/ angle on this by Church student Dana Scott as just reported by Ghica and documented in a youtube video.[1] He says that when Church was asked what the meaning of the λ was, he just replied “Eeny, meeny, miny, moe.“, which can only mean one thing. It was a random, meaningless choice. Prof. Scott claimed that the ...


10

Perhaps the earliest place in which time complexity appears is On the computational complexity of algorithms by Hartmanis and Stearns. Their goal is to study computation complexity, which they define as follows: The computational complexity of a sequence is to be measured by how fast a multitape Turing machine can print out the terms of the sequence. ...


10

It's false. The $\lambda$-calculus arose through efforts to understand foundations of mathematics. Nowadays some people mistakenly equate foundations with set theory. The Stanford Encyclopaedia of Philosophy has a very good writeup on the $\lambda$-calculus, as well as its history, I recommend it.


9

There is some evidence: This paper was presented at the ACM SIGPLAN History of Programming Languages Conference (HOPL II, April, 1993), co-authored by myself, Chuck, and Don Colburn, an erstwhile colleague now unfortunately deceased. It references, in turn, a very early work that Chuck wrote when Forth was in what might be called an "alpha" form, "...


9

I think the prizes you're referring to are the Loebner Prize. According to the Wikipedia page (see prior link), the winner for 2014 is 'Rose' by Bruce Wilcox. That program did not win one of the one-time-only prizes, but did get $4,000 in prize money. 'Eugene Goostman' competed in 2005 and 2008, finishing second both times. The competition 'Eugene Goostman'...


9

Since this question was reopened and made more explicit, I would like to convert my comment into an answer. Now the OP wants to understand why and when polynomial algorithms became of interest. I especially focus on the sub-question: When did people realize the role and importance of efficient versus non-efficient algorithms? Because algorithms, in ...


9

I sent an email to Martin Richards to try and get some details/context about CPL and he gave me a reply. To partially quote: "CPL did have a break command to cause an exit from a repetitive command such as while or until. As far as I remember it did not have an equivalent of continue, but the equivalent loop command was added to BCPL early in 1967." [...]...


9

A little google-fu (and my own memory) tells me it was apparently named by Larry Paulson after Gerard Huet's daughter. Gerard Huet happens to be one of the people behind the less poetically named Coq theorem prover. Small world!


Only top voted, non community-wiki answers of a minimum length are eligible