We present an approach to the interoperability of programming languages, based on a Common Runtime Support (CRS), which provides general mechanisms for storage management, symbol table management and concurrent execution, for modern high level languages. We focus in particular on the CRS approach to the interoperability of AI languages, in particular: Prolog and COMMON LISP. The CRS provides support for logic variables, so that both a Lisp Abstract Machine and a subset of the Warren Abstract Machine, including all the unification primitives, are implemented on it. We present and compare two alternative implementation of non-determinism and backtracking, through success continuations and failure continuations. Both Lisp and Prolog programs are compiled to C code to run on the C based CRS. The interoperability is achieved with minimal overhead and this allows programmers to select the most appropriate programming paradigm for each task: functional, logic and object-oriented. Finally, we show how an efficient theorem prover for first order predicates can be implemented on the CRS obtaining interesting performances.