Are there any object-oriented programming languages that are not based on the class paradigm?
As far as I know, Self is the original language that invented the "class-free" paradigm based on prototypes. It already existed (in an experimental stage) in the 1980s and pushes Smalltalk's elegant usage of the prototype pattern to the extreme, such that classes are completely eliminated.
It influenced all the other "class-free" OO languages I know of:
Object-orientation is an umbrella term for several important concepts that are only partly contingent upon each other. For instance, inheritance can be declared on a case-by-case basis between instances rather than between classes, or the entire class can be represented by a concrete
prototype object, as Thomas wrote. It's just more usual to separate structure description from instance creation. Similarly, late binding means that objects with nominally the same method don't necessarily do the same thing when it is invoked, and that the decision is made at runtime. That is likewise possible with the prototype-based approach. And encapsulation is essentially completely independent of whether your objects are instances of declared classes or not.
That said, most OO languages are firmly in the class-based camp. But even then there are idioms that blur the line: the domain-driven design often leads to systems in which the identity of particular objects is much more important than the static class diagram, and decorators allow objects of the same class or interface to have very different behavior.
Fortress is an object-oriented language based on traits instead of classes. The difference is mainly in implementation composition. An object's behavior (method definitions) is still determined by the declarations at a specific point in the program text. So in that sense it's similar to class-based systems.
There are object calculi (by Cardelli, I think), that are purely object-based. Every method is an instance member. You form new objects by taking the contents of an existing object and adding, removing, or replacing some of its members. It's slightly different from prototypes, since the new object has no link to the old object, just some of its contents.
IIRC, it's possible to program in a similar way using Python and other hashtable-oriented languages: you can add a function as an instance member and then call it as a method.
Ada, as of its 1995 revision, Ada is object-oriented, but unlike a lot of other OO languages it doesn't combine object-oriented types and modules into a single construct called a "class". Rather than declaring a type as "class Foo", and putting all the associated method declarations inside the class declaration, you declare a package and declare the type (as a
record) and other things inside the package. It's not "class-free" in the way that some of the other mentioned languages are, it's just a slightly different way of organizing things.
Ada 95's object-oriented features were added onto the existing 1983 version of the language; it extended the existing record and package constructs to support inheritance et al.
Io is another prototype-based object-oriented language. It actually draws inspiration from several of the languages already mentioned in other answers.
Io is a dynamic prototype-based programming language. The ideas in Io are mostly inspired by Smalltalk (all values are objects), Self (prototype-based), NewtonScript (differential inheritance), Act1 (actors and futures for concurrency), Lisp (code is a runtime inspectable / modifiable tree) and Lua (small, embeddable).