Ira Baxter just answered me that string rewrite is a different thing comparing to imperative and functional programming:
This post has interesting links to Post systems that I never hear about. And there is REFAL language works this like
(but I can't ever understand how to run its implementations -- there are lots of broken links, unportable implementations, and crazy unusable docs).
XL languages family looks very light and understandable comparing with them. Maybe it has no first entry tutorial for minimal implementation in xl2/ .
I built it by a single direct
call without any problems), but the source code is observable and paired with a clean reference manual.
I myself more interested in object graph rewrite (attribute grammar trees is a case of it), maybe with Prolog-like backtracking and match/update pattern (for inference).
Anyway, XL is very interesting in pair of LLVM cross-compiler, I'm going to use it in my work if I understand how it works inside.