5 ms·
Logic programming really falls in to two main categories: search and constraint satisfaction. In that light, there's really only two programming paradigms: Temp
by brandonbloom 10y ago
Logic programming really falls in to two main categories: search and constraint satisfaction. In that light, there's really only two programming paradigms: Temporal and Spatial.
Imperative programming is programming with time. Functional programming projects time on to space. When you add concurrency, either effectively becomes logic programming: Search runs multiple spatial processes in parallel. Constraint satisfaction treats each constraint variable as its own timeline.
We only don't think of it this way because we've traditionally linearized logic programs. You can linearize search with backtracking and you can linearize constraint satisfaction with a constraint propagation queue.
- Chris2048 10y agoCan you expand on this? I'm not sure I follow..
- brandonbloom 10y agoI can try, but I'm not just going to guess what your misunderstanding is. What specifically would you like me to expand upon?
- Chris2048 10y agoI don't understand what you mean by: > Imperative programming is programming with time. Functional programming projects time on to space. and: > Constraint satisfaction treats each constraint variable as its own timeline
- brandonbloom 10y agoThink about a mutable variable. In an imperative program X can start with A, then become B, then become C, etc. In a functional program, you can say that X doesn't change, instead there's really a subscript: X0=A, X1=B, X2=3. That is, you're projecting the time dimension, which is implicit, linear, etc, on to a space dimension: The name of the variable expands from ["x"] to ["x", 1] etc. Monads are the (an?) ultimate exploration of this idea. You project the timeline of the entire world on to a space dimension. Each "bind" operation builds up a new world and you can have many forks of the world, as it's just a model, not the world itself. This model doesn't do anything until you "run" the monad by handing it off to some higher level interpreter. As for constraint satisfaction, check out Sussman's talk "We Really Don't Know How To Compute" <https://www.youtube.com/watch?v=O3tVctB_VSU> https://www.youtube.com/watch?v=O3tVctB_VSU> - Even though they implement the propagator networks with a message queue and a single thread, you could in theory run each propagator in parallel, sending messages back and forth.
- andreareina 10y agoWriting another comment, I had the thought that time is still present in the functional paradigm, though not in the same way as it typically presents in the imperative paradigm. This is a great way of thinking about it, thanks.
- rntz 10y agoThis is about implementation strategies, which I think are a lower-level idea than paradigms. Datalog is a logic language that can be implemented without using backtracking/"search", for example.
- brandonbloom 10y agoIt's no more about implementation strategy than compilation vs interpretation, which is also spatial and temporal in nature.
- rntz 10y agoCompilation and interpretation are also implementation strategy issues, unrelated to programming paradigms. Almost any language can be implemented using either strategy, and most systems we think of as "interpreted" in reality employ a mixture of the two strategies. I don't know what you mean when you say they are also spatial and temporal in nature. You are being extremely glib, and I don't really understand what points you are trying to make.