Hello Marc,

> : Now here is the question. What I'd like to know if there's an easy way
> : for a substitution of the form
> :   a[expression] -> \csname myA[expression]\endcsname

\regex_replace_all:nnN
  { a \[ (.+?) \] } { \c{ myA \[ \1 \] } } \l_your_tl

or, if the names "a" and "myA" are actually stored in some variables
(in particular, if they contain characters that may be unsafe in
regular expressions), say, \l_array_name_tl and \l_rec_name_tl, you
can use the \u escape sequence (specific to l3regex, not present in
Perl or PCRE):

\regex_replace_all:nnN
  { \u{l_array_name_tl} \[ (.+?) \] }
  { \c{ \u{l_rec_name_tl} \[ \1 \] } } \l_your_tl

===================================

Feel free to ask details about the syntax: I'm not happy with how it's
explained in the doc. Here is a possible approach for parsing the
whole thing. I'm not entirely sure what you have in mind as a syntax,
so I may be a tad wrong in the following. I'm basing myself on your
example

    \NewRecDef{myA}{
        a[i]=1               | 0 <= i && i <= 1,
        a[i]=a[i-1]+a[i-2] | true
    }

So the input is a comma list of expressions of the form

    a[i]=<expression using "a" and "i"> | <boolean expression in "i">

and given a value of i, we compute a[i] by looping through the comma
list, testing the <boolean expression in "i">, stopping at the first
one that yields "true", and evaluating the <expression using "a" and
"i">, possibly calling a recursively.

If I understand correctly, you want to use regular expressions to
parse that. I think it is possible. A starting point is as follows.
I'm using \tl_replace_all whenever possible rather than the more
powerful regex features, because the former is roughly 100 times
faster.

    \RequirePackage{xparse,l3regex}
    \ExplSyntaxOn
    \cs_generate_variant:Nn \tl_replace_all:Nnn { Nx }
    \tl_new:N \l_nrd_name_tl
    \tl_new:N \l_nrd_input_tl
    \tl_new:N \l_nrd_tmp_tl
    \tl_new:N \l_nrd_array_name_tl
    \tl_new:N \l_nrd_index_name_tl
    \tl_new:N \l_nrd_expression_tl
    \tl_new:N \l_nrd_bool_expr_tl
    \int_new:N \l_nrd_arg_int
    \seq_new:N \l_nrd_tmp_seq
    \seq_new:N \l_nrd_parsed_seq
    \DeclareDocumentCommand{\NewRecDef}{mm}
      {
        \tl_set:Nn \l_nrd_name_tl {#1}
        \seq_clear:N \l_nrd_parsed_seq
        \clist_map_inline:nn {#2}
          {
            \regex_extract_once:nnNTF
              { ^(\w+)\[(\w+)\]\=(.+?)\|(.+) } {##1} \l_nrd_tmp_seq
              {
                 % at this stage, \l_nrd_tmp_seq has 5 items,
                 % 0th: a[i]=1 | 0 <= i && i <= 1
                 \seq_pop:NN \l_nrd_tmp_seq \l_nrd_tmp_tl

                 % 1st: a (array name)
                 \seq_pop:NN \l_nrd_tmp_seq \l_nrd_array_name_tl

                 % 2nd: i (index name)
                 \seq_pop:NN \l_nrd_tmp_seq \l_nrd_index_name_tl

                 % 3rd: 1 (or more general expression)
                 \seq_pop:NN \l_nrd_tmp_seq \l_nrd_expression_tl
                 \tl_replace_all:Nxn \l_nrd_bool_expr_tl
                   \l_nrd_index_name_tl { \l_nrd_arg_int }
                 \regex_replace_all:nnN
                   { \u{l_nrd_array_name_tl} \[ (.+?) \] }
                   { \c{nrd_array:n} \cB\{ \1 \cE\} }
                   \l_nrd_expression_tl

                 % \tl_show:N \l_nrd_expression_tl

                 % 4th: 0<=i&&i<=1
                 \seq_pop:NN \l_nrd_tmp_seq \l_nrd_bool_expr_tl
                 \tl_set:Nx \l_nrd_bool_expr_tl { ( \l_nrd_bool_expr_tl ) }
                 \tl_replace_all:Nxn \l_nrd_bool_expr_tl
                   \l_nrd_index_name_tl { \l_nrd_arg_int }
                 \tl_replace_all:Nnn \l_nrd_bool_expr_tl { ( } { (
\nrd_test:w [ }
                 \tl_replace_all:Nnn \l_nrd_bool_expr_tl { ) } { ] ) }
                 \tl_replace_all:Nxn \l_nrd_bool_expr_tl
                   { \tl_to_str:n {&&} } { ] && \nrd_test:w [ }
                 \tl_replace_all:Nxn \l_nrd_bool_expr_tl
                   { \tl_to_str:n {||} } { ] || \nrd_test:w [ }

                 % \tl_show:N \l_nrd_bool_expr_tl

                 \seq_put_right:Nx \l_nrd_parsed_seq
                   {
                      \exp_not:N \bool_if:nTF
                        { \exp_not:V \l_nrd_bool_expr_tl }
                        {
                           \message { test ~ " \tl_to_str:N
\l_nrd_bool_expr_tl " ~ succeeded ! }
                           % do something with \l_nrd_expression_tl
                           \exp_not:N \prg_map_break:
                        }
                   }
              }
              { \msg_error:nnx { nrd } { wrong-input } { \tl_to_str:n {##1} } }
          }
      }
    \cs_new:Npn \nrd_test:w [ #1 ]
      {
         \str_if_eq:xxTF {#1} {true} { \c_true_bool }
           {
             \str_if_eq:xxTF {#1} {false} { \c_false_bool }
                { \int_compare_p:n {#1} }
           }
      }
    \ExplSyntaxOff

So, roughly the idea is that each item of the clist has the form

    <name>[<index>] = <expression> | <bool expr>

and we extract the <name>, <index>, <expression> and <bool expr> using
a regex. Then in the <expression>, replace all occurrences of <index>
by \l_nrd_arg_int, and <name>[<whatever>] by \nrd_array:n
{<whatever>}, where we expect <whatever> to be a valid integer
expression now that we've replaced <index> by \l_nrd_arg_int. On the
other hand, the <bool expr> is converted to a boolean expression in
the sense of LaTeX3, which requires us to wrap each of the comparisons
in \int_compare_p:n. Since I don't know how complicated those
comparisons can be, I did the opposite, which is to wrap each
operator: (, ), &&, ||, with the relevant \nrd_test:w [ or ]. I'm not
using braces here because the output must be brace-balanced in all
cases. At the end of the day, \nrd_test:w [#1] tests whether its
argument is "true", "false", or an integer comparison (remember, "i"
got converted to \l_nrd_arg_int).

Presumably, using those expressions, you can reach your goal.

> I think I've solved the problem, so I probably won't need to know
> about the substitution. If the answer is easy, I'd still like to
> know. Otherwise, please forget about it.

I hope the first part of that email was easy enough; the second part
probably wasn't :). I assume that you are going to post the final
solution on TeX.sx?

Cheers,
Bruno