Representation of the concatenation at the type level
A major idea of concatenative languages is that the syntax and semantic domain form monoids and the semantics is a monoid homomorphism. The syntax is the free monoid generated by the basic operations, better known as a list. It's operation is list concatenation, i.e. (++) in Haskell. In the untyped context, the semantic domain is just the monoid of endofunctions (on stacks) with composition as the operation. In other words, an interpreter should look like the following:

data Op = PushInt Int| Call Name | Quote Code | Add | ... -- etc.
type Code = [Op]

-- Run-time values
data Value = Q (Endo Stack) | I Int | ... -- etc.
type Stack = [Value]

-- You'd probably add an environment of type Map Name (Endo Stack)
interpretOp :: Op -&gt; Endo Stack
interpretOp (PushInt n) = Endo (I n:)
interpretOp (Quote c) = Endo (Q (interpetCode c):)
interpretOp op = ... -- etc.

interpretCode :: Code -&gt; Endo Stack
interpretCode = foldMap interpretOp

runCode :: Code -&gt; Stack
runCode code = case interpretCode code of Endo f -&gt; f []


Making a (very naive) compiler is just as simple. The only thing that changes is the target monoid which will now be a syntactic monoid built out of a fragment of the syntax of the target language thus interpretOp will become compileOp. This target monoid may be sequences of statements with the operation of sequential composition, i.e. ;. You can be quite a lot more sophisticated though.

Type systems for concatenative languages are not as obvious, and there are almost no typed concatenative languages. Cat is the most significant example I'm aware of. One way to start to approach it and experience some of the issues that come up is to embed a concatenative language in Haskell. You quickly discover that you don't want add :: (Int, Int) -&gt; Int as this won't compose. Instead, you have add :: (Int, (Int, s)) -&gt; (Int, s). This works extremely well for simple things. This is also relatively clearly poor man's row types. One of the first and most significant hurdles you'll hit is dealing with quotations. The problem is that [add] should correspond to something with a type like s -&gt; ((forall s'. (Int, (Int, s')) -&gt; (Int, s')), s) which requires higher-rank types and impredicative instantiation. Cat appears to have both. It certainly has higher ranked types, and it will substitute a polytype for a type variable. It may be doing things in a way that can be understood without impredicativity. Accomplishing this with an embedding in Haskell might be doable using type-level lists, (closed) type families, and local universal quantification. At this point though, making a custom type system likely makes more sense.

Operations with non-uniform stack effects are also likely to be problematic, but, in most cases, it makes sense to just omit them and provide alternative means of doing things that guarantee a consistent stack.