How to have two separate types of caption labels for algorithms?

Question

I want to describe algorithms that have two parts: an interface specification and an algorithm.

The interface specifications should be labeled Module and the algorithm specifications should be labeled Algorithm. Moreover, I want the interfaces to be numbered separately from the algorithms.

The output should be something like the following:

Module 1: An interface specification
     Some interface spec...


Algorithm 1: An algorithm
     Some pseudocode...

The following, however, is what I'm currently getting:

My code is the following:

\documentclass{article}

\usepackage{algorithm}
\usepackage{algpseudocode}

\makeatletter
  \renewcommand{\ALG@name}{Module: }
\makeatother

\begin{document}

\begin{algorithm}
\caption{An interface specification}
\begin{algorithmic}
\State Some interface spec...
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{An algorithm}
\begin{algorithmic}
\State Some pseudocode...
\end{algorithmic}
\end{algorithm}

\end{document}

Answer 1

The following is based on an answer to the question Modify Algorithm name in French:

\documentclass{article}

\usepackage{algorithm}
\usepackage{algpseudocode}

\newfloat{module}{htb}{lop}
\floatname{module}{Module}

\makeatletter
\newcommand{\newalgname}[1]{%
  \renewcommand{\ALG@name}{#1}%
}
\makeatother

\begin{document}

\begin{module}
\caption{An interface specification}
\begin{algorithmic}
\State Some interface spec...
\end{algorithmic}
\end{module}

\begin{algorithm}
\caption{An algorithm}
\begin{algorithmic}
\State Some pseudocode...
\end{algorithmic}
\end{algorithm}

\end{document}

It produces the following output: