Very good explanations of programming paradigms and the programming concepts from which those paradigms are built are found in Peter van Roy's works. Especially in the book Concepts, Techniques, and Models of Computer Programming by Peter Van Roy and Seif Haridi. (Unfortunately, the companion wiki does not seem to exist any more.) CTM (as it is colloquially known) uses the multi-paradigm Distributed Oz programming language to introduce all the major programming paradigms.
Peter van Roy also made this amazing poster that shows the 34 major paradigms and their relations and positions on various axis. The poster is basically an incredibly compressed version of CTM. A more thorough explanation of that poster is contained in the article Programming Paradigms for Dummies: What Every Programmer Should Know which appeared as a chapter in the book New Computational Paradigms for Computer Music, edited by G. Assayag and A. Gerzso. It explains for example very concisely and easily understandable, what a programming paradigm actually is, what a programming concept is, and how the two are related.
There are about 34 principal Programming Paradigms, as identified by Peter van Roy and Seif Haridi:
- active object programming / object-capability programming
- ADT functional programming
- ADT imperative programming
- concurrent constraint programming
- concurrent object-oriented programming / shared-state concurrent programming
- constraint (logic) programming
- continuation programming
- descriptive declarative programming
- deterministic logic programming
- event-loop programming
- first-oder functional programming
- functional programming
- functional reactive programming (FRP) / weak synchronous programming
- imperative programming
- imperative search programming
- lazy concurrent constraint programming
- lazy dataflow programming / lazy declarative concurrent programming
- lazy functional programming
- monotonic dataflow programming / declarative concurrent programming
- multi-agent dataflow programming
- multi-agent programming / message-passing concurrent programming
- nonmonotonic dataflow programming / concurrent logic programming
- relational & logic programming
- sequential object-oriented programming / stateful functional programming
- software-transactional memory (STM)
- strong synchronous programming
Programming Paradigms, in turn, are composed of Programming Concepts, and Peter van Roy and Seif Haridi have identified 18 of those:
- by-need synchronization
- cell (state)
- closure
- continuation
- instantaneous computation
- local cell (private state)
- log
- name (unforgeable constant)
- nondeterministic choice
- port (channel)
- procedure
- record
- search
- single assignment
- solver
- synchronization on partial termination
- thread
- unification (equality)
Note, that poster completely ignores typing, and there is of course a significant difference between a System F<:ω-style type system, a Scala-style type system, or a dynamic duck-typed type system, let alone a dependent type system à la Idris, Agda, Coq, Guru, or ATS.
Another great book that demonstrates several major programming paradigms is Structure and Interpretation of Computer Programs by Harold Abelson and Gerald Jay Sussman. This book was the basis of MIT's CS101 for several decades.
The main difference between CTM and SICP is that CTM demonstrates most major paradigms using a language that supports them (mostly Distributed Oz, but also some others). SICP OTOH demonstrates them by implementing them in a language that does not support them natively (a subset of Scheme). Seeing Object-Orientation implemented in a dozen or so lines of code is friggin' awesome.
You can find video recordings and course materials of the course from MIT's short-lived ArsDigita University project.
Lambda the Ultimate – The Programming Languages Weblog is a great resource for all things programming languages. Activity has slowed down in recent years, but there is still a lot going on. The discussions below the articles and the discussions in the forums are at least as valuable as the articles themselves, if not more.
If you are interested in some controversial views, I can recommend studying the Design Principles behind Smalltalk by Dan Ingalls. For example, they contain this nugget of wisdom:
Operating System: An operating system is a collection of things that don't fit into a language. There shouldn't be one.
On a personal note, my own experience has been that really understanding a programming paradigm is only possible
- one paradigm at a time and
- in languages which force you into the paradigm
Ideally, you would use a language which takes the paradigm to the extreme. In multi-paradigm languages, it is much too easy to "cheat" and fall back on a paradigm that you are more comfortable with. And using a paradigm as a library is only really possible in languages like Scheme which are specifically designed for this kind of programming. Learning lazy functional programming in Java, for example, is not a good idea, although there are libraries for that.
Here's some of my favorites:
- object-orientation in general: Self
- prototype-based object-orientation: Self
- class-based object-orientation: Newspeak
- static class-based object-orientation: Eiffel
- multiple dispatch based OO: Dylan
- functional + object-orientation: Scala
- functional programming: Haskell
- pure functional programming: Haskell
- lazy pure functional programming: Haskell
- static functional programming: Haskell
- dynamic functional programming: Clojure
- imperative programming: Lua
- concurrent programming: Clojure
- message-passing concurrent programming: Erlang
- metaprogramming: Racket
- language-oriented programming: Intentional Domain Workbench
- other interesting ideas:
- Unison: code is immutable and content-adressable, which has some deep implications.
- Rust: "safe" and "low level / bare metal" don't need to be mutually exclusive.
- TypeScript: how do you capture all the crazy stunts ECMAScript programmers pull into a mostly-sound static type system? Note that there are many languages in the "typed web programming" field, but most of them try to be "better" ECMAScripts or "better than" ECMAScript, whereas TypeScript tries to make existing ECMAScript safe.
Equally important as the language semantics is its Type System. Unfortunately, I don't know of any similarly informative visualization of the different aspects of type systems. I am also not intimately familiar with Type Theory, unfortunately. (If you want to understand type systems, you should read Benjamin Pierce's Types and Programming Languages.)
Some of the important aspects are:
- dynamic vs. static typing, also gradual typing, optional typing, soft typing
- latent vs. manifest typing
- implicit vs. explicit typing
- structural vs. nominal vs. duck typing
- strong vs. weak typing
- parametric polymorphism (also higher-rank and higher-kinded), ad-hoc polymorphism, inclusion polymorphism, bounded polymorphism, subtype polymorphism
- at the intersection of subtyping and parametric polymorphism: covariance, contravariance, invariance
- System F, System Fω, System F<:, System Fω<:, and its various extensions, variants, subsets, and derivatives, including Damas-Hindley-Milner, but also type systems that move away from System F (e.g. the Dependent Object Type Calculus underlying Scala's Type System)
- the Barendregt Lambda Cube
- various forms of Type Inference, including Algorithm W, Flow-based, unification-based, etc.
- Kinds
- Dependent Typing, Linear Types, Ownership Types, Effect Types, World Types
And probably many other things I forgot.
In your question, you mention that you have experience with OO. In my personal experience, OO tends to almost universally be taught really badly. I am not saying that is what happened to you, but it is something I have noticed. So, even though you specifically asked about Functional and Logic Programming, here are some OO pointers as well.
The term "Object-Orientation" was coined by Dr. Alan Kay, and he defines it thus:
OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.
Let's break that down:
- messaging ("virtual method dispatch", if you are not familiar with Smalltalk)
- state-process should be
- locally retained
- protected
- hidden
- extreme late-binding of all things
Implementation-wise, messaging is a late-bound procedure call, and if procedure calls are late-bound, then you cannot know at design time what you are going to call, so you cannot make any assumptions about the concrete representation of state. So, really it is about messaging, late-binding is an implementation of messaging and encapsulation is a consequence of it.
He later on clarified that "The big idea is 'messaging'", and regrets having called it "object-oriented" instead of "message-oriented", because the term "object-oriented" puts the focus on the unimportant thing (objects) and distracts from what is really important (messaging):
Just a gentle reminder that I took some pains at the last OOPSLA to try to remind everyone that Smalltalk is not only NOT its syntax or the class library, it is not even about classes. I'm sorry that I long ago coined the term "objects" for this topic because it gets many people to focus on the lesser idea.
The big idea is "messaging" -- that is what the kernal of Smalltalk/Squeak is all about (and it's something that was never quite completed in our Xerox PARC phase). The Japanese have a small word -- ma -- for "that which is in between" -- perhaps the nearest English equivalent is "interstitial". The key in making great and growable systems is much more to design how its modules communicate rather than what their internal properties and behaviors should be. Think of the internet -- to live, it (a) has to allow many different kinds of ideas and realizations that are beyond any single standard and (b) to allow varying degrees of safe interoperability between these ideas.
(Of course, today, most people don't even focus on objects but on classes, which is even more wrong.)
Messaging is fundamental to OO, both as metaphor and as a mechanism.
If you send someone a message, you don't know what they do with it. The only thing you can observe, is their response. You don't know whether they processed the message themselves (i.e. if the object has a method), if they forwarded the message to someone else (delegation / proxying), if they even understood it. That's what encapsulation is all about, that's what OO is all about. You cannot even distinguish a proxy from the real thing, as long as it responds how you expect it to.
A more "modern" term for "messaging" is "dynamic method dispatch" or "virtual method call", but that loses the metaphor and focuses on the mechanism.
So, there are two ways to look at Alan Kay's definition: if you look at it standing on its own, you might observe that messaging is basically a late-bound procedure call and late-binding implies encapsulation, so we can conclude that #1 and #2 are actually redundant, and OO is all about late-binding.
However, he later clarified that the important thing is messaging, and so we can look at it from a different angle: messaging is late-bound. Now, if messaging were the only thing possible, then #3 would trivially be true: if there is only one thing, and that thing is late-bound, then all things are late-bound. And once again, encapsulation follows from messaging.
Similar points are also made in On Understanding Data Abstraction, Revisited by William R. Cook and also his Proposal for Simplified, Modern Definitions of "Object" and "Object Oriented".
Dynamic dispatch of operations is the essential characteristic of objects. It means that the operation to be invoked is a dynamic property of the object itself. Operations cannot be identified statically, and there is no way in general to exactly what operation will executed in response to a given request, except by running it. This is exactly the same as with first-class functions, which are always dynamically dispatched.
Benjamin Pierce in Types and Programming Languages argues that the defining feature of Object-Orientation is Open Recursion.
So: according to Alan Kay, OO is all about messaging. According to William Cook, OO is all about dynamic method dispatch (which is really the same thing). According to Benjamin Pierce, OO is all about Open Recursion, which basically means that self-references are dynamically resolved (or at least that's a way to think about), or, in other words, messaging.
As you can see, the person who coined the term "OO" has a rather metaphysical view on objects, Cook has a rather pragmatic view, and Pierce a very rigorous mathematical view. But the important thing is: the philosopher, the pragmatist and the theoretician all agree! Messaging is the one pillar of OO.
Note that there is no mention of inheritance here! Inheritance is not essential for OO. In general, most OO languages have some way of implementation re-use but that doesn't necessarily have to be inheritance. It could also be some form of delegation, for example. In fact, The Treaty of Orlando discusses delegation as an alternative to inheritance and how different forms of delegation and inheritance lead to different design points within the design space of object-oiented languages. (Note that actually even in languages that support inheritance, like Java, people are actually taught to avoid it, again indicating that it is not necessary for OO.)
