a plain expression like /ca/ seems rather straightforward to me.
This requires some kind of special version of the reader.
One thing I suggest would be to use some sort of # readermacro (which you'll have to hack in the underlying Scheme):
#/ca/
#/s/foo/bar/
If you want nice syntax for regexps, almost definitely it will have to be part of the axioms, or at least readermacros (which I personally don't like). Otherwise if representing them via strings is acceptable, then we don't need it as part of the axioms.
I am not sure what the consequences are for possible implementations, but preferrably, I would want to be able to use regexps in (find or (keep, or (findsubseq just as easily as I would now use strings or functions
(keep odd (list 1 2 3 4))
(keep (reg /nan/) (list "banana" "bonobo" "bandanga"))
(findsubseq (reg /\d+:\d+/) "The current time is 10:00 am")
When looking at http://arcfn.com/doc/string.html , there is an aweful lot of restrictions on when we can use variables, or functions as arguments, so maybe a lot of the string operations in there become obsolete if there is a regexp engine in arc.
