Lisps are expression based languages, but not pure. It's easy to mistake it as "like most other languages", but it's not quite the same - everything is an expression and returns a result. There are no "statements".

They appear procedural because of syntax sugar - ie, the body of a function is basically implicitly wrapped in (progn ...), (begin ...), ($sequence ...), etc - which are all equivalent expression forms which evaluate their sub-expressions in order and return the result of the last one.

   (progn a b c)      ;; CommonLisp
   (begin a b c)      ;; Scheme
   ($sequence a b c)  ;; Kernel

   ;; evaluate a, then b, then c, 
   ;; ignore the results of evaluating a and b 
   ;; return the result of evaluating c.

So when you see:

   (define (foo)
       (expr1)
       (expr2)
       (expr3))

If we desugar, it would be

    (define foo (lambda () (begin (expr1) (expr3) (expr3))))

We get behavior that looks just like other procedural languages (without a "return" keyword) - but everything is still an expression.

A similarity is the comma operator in C. Imagine you didn't write statements but the body of your C functions was entirely chains of comma operators.

CommonLisp has a couple of other useful related forms - prog1 and prog2. They still evaluate their sub-expressions in order, but prog1 returns the result of evaluating the first expression, and prog2 returns the result of the second expression.

    (define (foo) (prog1 (expr1) (expr2) (expr3))
    (foo)
 
    ;; evaluates expr1, then expr2, then expr3
    ;; returns the result of evaluating expr1
    ;; ignores the results of evaluating expr2 and expr3

I'm very familiar with Lisp, you don't have to explain it to me. I think you are mistaken as to the meaning of what is meant by "procedural language" here. It's simply the mode of computation where a program is directly conceived as a hierarchical sequence of steps. I think you got caught up in the idea of a grand disjunction of "expressions" and "statements", with a distinguishing feature involving return values, and so on. But no, that's not particularly relevant here (nor is it universally true, or applicable)

To simplify it, you can consider cons, car, cdr the beating heart of Lisp. These special forms directly encode the execution semantics as the traversal of a head over cells of a tape. Lisp belongs to the same family as the Turing machine, and that's a very big family. SML also belongs to this family. The overwhelming majority of programming languages belong to this family.

I think it all depends on the shape of the problem. I love Prolog for its expressive power, sometimes. Complex simulation problems are really nice to model in OCaml or CLOS, and then again, maybe remodelling in Prolog brings some insights. And often writing a recursive function in Lisp is all you need to understand a complex system. It's all layers. An outer shell to prolog would be a theorem solver for example, because Prolog is a very rudimentary one.

> An outer shell to prolog would be a theorem solver for example, because Prolog is a very rudimentary one.

I think it's the wrong way to look at it. It's not that Prolog is a rudimentary theorem solver, it's that theorem provers are a specialized use-case of deductive proofs, so a computational foundation of FOL makes them trivial to write as programs. A pile of bricks and a jar of mortar isn't a rudimentary house, so to speak.

Prolog is great for the cases where logic programming makes sense but you can easily create a logic engine in Lisp (or other languages - that's what kanren/minikanren which has been ported to many languages)

Of course, it holds for all turing complete languages, that's what computational class is all about. It's not a good argument to use or not use something though, because in practice it's always worse. You can think of it like this, would you rather write programs with SBCL or some company's internal unnamed domain-specific tree-walking sexpr language that doesn't even have macros, TCO or a real REPL and possibly isn't even turing complete? Would you ever in a million years suggest that the latter is even half as good as proper CL, let alone a replacement? I sure wouldn't.

Exactly, clojure.core.logic is an example Minikanren inspired logic engine.