Are out there, any programming languages that are not defined algorithmically so that we can call them "constructed languages" but not "formal languages"? Are there any discussions or papers on that topic? It seems pretty hard to develop a compiler for this kind of languages.
No, at least not a reasonable programming language by what we commonly understand under that term.
As soon as you have a compiler (or an interpreter), you have an algorithm that decides whether a given string is a valid program. This compiler then defines the language. (Not a good way to define a programming language, but a workable one.)
According to this article, MIT did look into the possibility of writing simple programs using natural language, relying somehow on regular expressions.