I was reading this Smalltalk tutorial the other day. I found it excessively pedantic, but one turn of phrase caught my eye: the author claims that Smalltalk is a "foundational" programming language. I agree with him, but what does this term mean? I would say that to me, a foundational language is one which is such a good exemplar of a particular programming paradigm that it can be seen as the embodiment of that paradigm. Furthermore, foundational languages are worth learning even if you never program any substantial applications in them, because they will expand your mind and thus make you a better programmer.
That being the case (says I), what are the foundational languages? I would say that the foundational languages certainly must include these:
C is foundational because it is the canonical low-level imperative language with direct access to hardware. It isn't particularly elegant or pleasant to program in, but it's simple, and a lot of other languages are implemented in it (in whole or in part). Knowing C is for a programmer the equivalent of learning to tie your shoelaces -- it's just basic knowledge that you are going to need sooner or later. As curricula have moved away from C in favor of Java, I think a lot of students are going to lose sight of the underlying machine model that is vividly exposed in C but is hidden in other languages, and that's a shame.
Scheme and Lisp
Scheme (and, by direct inheritance, Lisp) is foundational for a number of reasons. Lisp was the first language to support functional programming (FP), and Scheme is a purified version of Lisp, which means among other things that it supports FP in a cleaner manner than Lisp itself does. Scheme and Lisp also have very powerful syntactic macros (the Scheme system is IMO nicer and more powerful than Lisp's, but I haven't used either system extensively); this will completely blow your mind if you're used to C's impoverished notion of macros. Finally, Scheme supports continuations as first-class data values, and was the first well-known language to do so as far as I know. A continuation captures the state of a computation so that it can be replayed later on; this is an immensely powerful feature that can be used to model exception handling, backtracking, arbitrary control flow, and so on (it also turns out to be useful in web programming). Common Lisp has a very powerful object-oriented extension called CLOS (Common Lisp Object System) which AFAIK was the first object system that was based around multiple-dispatch (multimethods) instead of single dispatch. This is a very cool feature that makes object-oriented programming more powerful and less kludgy than with conventional object systems (though there are tradeoffs, as always).
Smalltalk is foundational because it is a pure object-oriented language all the way down. Everything is an object, and objects can only talk to other objects by sending messages to each other (Alan Kay, the designer of Smalltalk, has stated that messages are what is really important in Smalltalkk, not objects per se). The significance of a message is that it can be interpreted in completely different ways by different objects. So, if you send the "print" message to a number, it will print that number (which will require some code to be executed), but if you send the "print" message to e.g. a list, that will cause quite different code to be executed. Smalltalk also has an interesting structure whereby classes (which are templates for objects) are themselves objects, and can also respond to messages. Classes are actually instances of metaclasses, which is another cool concept. Furthermore, the Smalltalk system is naturally open and reflective; you can query objects to learn more about them, you can construct messages on-the-fly and then perform them, and you can add methods to classes any time you want. This gives rise to a very different way of thinking about programming than you'd get in e.g. Java or C++.
Erlang is a mostly-functional dynamically-typed language that is geared towards massively concurrent and distributed programming. An Erlang program is a collection of smallish processes, each of which has its own state and communicates with other processes by sending asynchronous messages to them. I haven't worked much with Erlang, but it's on the top of my to-learn list. Those people who have worked with it seem quite enamored of it. One thing Erlang offers is an alternative model of concurrency not bound to the traditional threading model (which I've always hated because it's so hard to get a program working right). In additional, distributing a concurrent program over a cluster of computers instead of one computer is very little extra work, which is important if you're doing e.g. web programming and your web site becomes popular enough so that it needs to scale beyond a single machine.
Haskell is a purely functional, non-strict language. If any language can claim to be foundational, this one can. It would take pages to cover all the profound concepts that are in Haskell, and I don't have enough patience to write that much, so I'll just direct you to the Haskell home page. Haskell is by far my favorite programming language.
Prolog is the canonical logic programming language (or relational programming language, if you prefer). In Prolog, you basically tell the system what you want, and it figures out how to compute it. Thus, it's a "declarative" programming language. Of course, the reality is more complicated than this, but that's the idea: to take a specification of a program and make it the program. There are newer logic programming languages like Mercury that add static typing features to Prolog, and there are many extensions of Prolog to do e.g. constraint programming. I'm no expert on this area, but I find it fascinating as a glimpse of where programming may be headed in the future. Certainly, every good programmer should learn Prolog.
Of course, there are probably other foundational languages I don't know about yet, or don't know well enough to comment on. There are also cool languages like Forth, Icon and APL (or its more modern successor J) that have many neat features but which I don't consider fundamental enough to be called foundational. I could also make a case that SQL is sorta-kinda foundational, but since it isn't a Turing-complete language it doesn't really qualify. I also don't consider assembly languages to be foundational in any serious sense, though they're certainly the "foundation" of other languages in an implementation sense at least.
Also, there are some very good languages that I don't consider foundational; Python and Ocaml come to mind. So the fact that a language isn't foundational is not an indictment of the language; some good languages are "consolidators" which bring together known good ideas into a single package. Nothing wrong with that.
Then there are also lots of languages which I consider flawed and/or mediocre (Java, Ruby, C++ and C# come to mind), or languages I really don't like at all (PHP and Perl come to mind) which (no surprise) are also not foundational.