[waps]

> Consider Lisp as a potential pinnacle of perfection. Paul Graham quipped that Lisp was "discovered" by John McCarthy, rather than invented or designed – Lisp already existed in the way that mathematical truths exist. That's a cute idea, but clearly not literally true. There were still a lot of design choices – parentheses for example. Why not square or curly brackets? Why not indentation? There were also choices that are now almost universally recognized as mistakes. Dynamic scoping, for example, which was later replaced by lexical scoping in Scheme.

Well, have you seen lambda calculus, which predates lisp ? That's basically lisp (it has lambda, it has bound and unbound variables, it has let, it has steps, it has recursion, ...). All John McCarthy did was implement it. That's where the parentheses come from, of course. Why not curly brackets or indentation ? Because in maths, parantheses specify sequence of calculation, curly brackets denote collections, and indentation doesn't mean anything. Since the concept being expressed is the sequence, they used parentheses. In fact the first reference I can find to parentheses dates from the ancient Greeks (and they were probably merely the first one to write it down).

Lambda calculus is a generalization of mathematical formulas by Alonzo Church to describe computation (as opposed to "just" values or functions, what normal mathematical formulae do. Functions in math are very, very different from functions in lambda calculus. This cannot be said to be very original either, as is was mostly a way to introduce some sanity into Hilbert's "Entscheidungsproblem" ("can you give a mathematical formula that solves mathematical formulae"), and more generally, into constructivism. This was made possible by finding a consistent way to express the combination operators in logic. Constructivism was a branch of logic that ...

You can keep going back for quite a while, but the point is that the form of lisp was effectively decided by someone who's name we don't even know, who lived in one of the ancient Greek city states. He (or she ? not impossible in that period) also had absolutely no idea what they were doing either.

[StefanKarpinski]

There's a lot more to an actual Lisp than lambda calculus. No Lisp ships with just lambda – that would be absurd and unusable. So there are design choices: choices of standard functions like "car", "cdr", "set" – and what kind of scoping "set" implements. The Common Lisp and Scheme specs are literally lists of design choices.

[gratimax]

If you don't already know, there is a Church encoding for singly-linked lists that is in the lambda calculus. We can already implement some of the operations you have listed with just lambdas:

(defun cons (x y) (lambda (z) (z x y))) (defun car (l) (l (lambda (x y) x))) (defun cdr (l) (l (lambda (x y) y)))

It's not like a lisp with 'just lambda' would be 'absurd and unusable'. I just showed you, we can implement cons, car, and cdr with just lambdas(hooray, closure! not clojure, closure...). Although there are some design decisions that had to be made, e.g. set, list.

[StefanKarpinski]

Why does everyone think they're the only person who knows about lambda calculus? No kidding, lambda is turing complete, so yes, you can implement car and cdr with it. But just because you can do everything with lambda doesn't mean that it's actually done that way.

[gratimax]

Would you call scheme unusable? Of course not, people use it every day. It has 12 'fundamental forms' that cannot be implemented within the language itself without a compiler. Every other library function(except low-level IO ones) is defined in terms of these forms. From the language designers, "we realized that the lambda calculus—a small, simple formalism—could serve as the core of a powerful and expressive programming language."

[StefanKarpinski]

The meat of the S6RS spec is 55 pages [1]. This proves my point rather than refuting it: there's a lot more to Scheme than lambda – 55 pages of design decisions more.

[1] http://www.r6rs.org/final/r6rs.pdf

[waps]

At university we learned a turing machine implementation in lambda calculus. Now while I will fully agree that it's a disastrously difficult programming language, but "big" (non-trivial) programs in lambda calculus both exist and predate the oldest LISP programs.

Likewise "big" Church thesis programs exist and predate the oldest lambda calculus programs. They're even more unreadable (although everyone doing cs has at least looked at 2 of them).

Before that you will find more implicitly written programs that are definitely programs, in the sense that they are explicitly checked to be finite computation steps.

Even these informal algebraic programs not only predate LISP, Lambda and Church but a lot of them are rewrites of algorithms out of pure algebra that are definitely programs, just less formally written down.

You can trace the history of those back to the renaissance European city states (I refuse to accept al-Khawazarmi as having done anything but compile external sources).

And frankly, is there anyone here that has read Euclid's algorithm and doesn't think even the ancient Greek version is, when it comes right down to it, a valid computer program ? He didn't have the notion of generalized calculation (technically nobody did that correctly before Turing of course), but he had the notion of calculating various things by counting in specific ways. It's not that different, really. And it's only one of quite a set of programs written by Euclid of Alexandria.

Obviously Euclid's programs were never meant to be programs, but they are programs. They have a trivial mapping in pretty much any programming language that exists.

Oh, and Euclid uses recursion. Didn't define it, just uses it. Even Euclid very likely just compiled knowledge, didn't invent/discover it. Likely these algorithms were taught in Alexandria for at least a few decades before Euclid, so you could reasonably accurately say that there definitely were computer programmers in the 4th century BC, maybe even fifth.

And with the comment relating to "car" and "cdr", well, Euclid uses those functions. He doesn't define them beyond describing their effects, but he uses them. In that way, of course, he's acting like any other programmer. The only people defining car and cdr are developing the language, not any real programs.

[TheCoelacanth]

Brainfuck is Turing-complete too. That doesn't make it usable.

[StefanKarpinski]

[gratimax shows you how to implement car, cdr and cons in brainfuck]

[gratimax]

brainfuck has no procedures, so no can do. :)

[StefanKarpinski]

Since Brainfuck is turing complete, this is untrue – you can emulate procedures and then define car, cdr and cons as emulation-level procedures.