IIRC Doug Orleans once made an ifMUD bot for a version of Zendo where a rule was a regular expression. This would give the user a way to express their guess of the rule instead of you having to test them on examples (regex equality is decidable).

Also I made a version over s-expressions and Lisp predicates -- it was single-player and never released. It would time-out long evaluations and treat them as failure. I wonder if I can dig up the code...