[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.