Hello Marc,
> I've made some progress with the recurrence equations, but I have a error
> that I don't understand. I'd appreciate it if you could have a quick look.
It's an expansion issue. Everything that appears within an integer
expression must be fully expandable, and x-type expansion is not
expandable (I think that's documented in l3expan, otherwise, it should
be added). You can use f-expansion instead, which expands from the
left, stopping at the first expandable macro; it will expand any
expandable function, but not restricted expandable functions (hollow
stars in the doc, I believe), such as \tl_map_function:NN. So to
expand an integer argument, use
\exp_args:Nf \recurrence_f_0:n { \int_eval:n {#1} }
Also, we normally denote the arguments by "n", unless they explicitly
perform expansion on top of their normal action. For instance,
\int_eval:n expands everything until finding integers, but it is
called \int_eval:n, not \int_eval:x.
Putting all that together, your macros could be
\f macro:#1->\int_eval:n { \f:n {#1} }
\f:n macro:#1->\exp_args:Nf \recurrence_f_0:n {\int_eval:n {#1}}
\recurrence_f_0:n macro:#1->\int_compare:nTF {#1=0}{1}{\recurrence_f_1:n {#1}}
\recurrence_f_1:n macro:#1->\int_compare:nTF {#1=1}{1}{\recurrence_f_2:n {#1}}
\recurrence_f_2:n macro:#1->\bool_if:nTF {\int_compare_p:n{1=1}}
{\f:n{#1-1}+\f:n{#1-2}} {\recurrence_f_3:n {#1}}
\recurrence_f_3:n \long macro:#1->0\msg_expandable_error:n {f[ #1 ] undefined.}
(1) Notice that I've used \int_eval:n in the definition of \f.
Otherwise, you would end up with an expansion of the form 1+1+1+1+1,
not evaluated to give 5.
(2) Also, the function _3 should use \msg_expandable_error:n, which
gives a nicer log output than just \error, and expands to nothing.
Since it expands to nothing, but we're within an \int_eval:n, we must
insert a default value, here 0.
(3) I changed the signature to "n" instead of "x", since the functions
do not perform any special expansion of their arguments before using
them.
(4) As it is, the code will un forever on negative input. You should
probably use \int_compare_p:n {#1>0} or something like that in the _2
function.
(5) Of course you know it, this code will run exponentially slowly for
large input. That is difficult to solve (but doable; I can give
details) if you want an expandable function which expands to the value
of your recursion. For a non-expandable function of the form
\recursion_get_value_f:nN { <index> } <int var> (dunno how the
function should be called), getting a linear-time solution should be
easier: it involves storing the intermediate results as you get them.
> The current code I have is packaged as a .tex and a .sty file. If you have
> any comments on the problem, or indeed, the source files, then that'd be
> much appreciated.
Comments below.
--
Regards,
Bruno
--
- Naming a function \foo:xx doesn't magically cause expansion of the
args. You need to define \foo:nn, then \cs_generate_variant:Nn \foo:nn
{ xx }.
- Variables should be renamed to indicate whether they are local or
global, and in the team we always put the variable's type (tl,
int,...) at the end.
- Integers should be stored in int variables (TeX \count registers),
not as token lists.
\clist_new:N \recurrence_csv_list % => \l_recurrence_temp_clist
(actually unused)
\tl_new:N \recurrence_tl_bin % => \l_recurrence_bin_tl
\tl_new:N \recurrence_tl_temp % => \seq_new:N
\l_recurrence_temp_seq (not tl)
\tl_new:N \recurrence_tl_name % => \l_recurrence_name_tl
\tl_new:N \recurrence_tl_index % => \l_recurrence_index_tl
\tl_new:N \recurrence_tl_rhs % => \l_recurrence_rhs_tl
\tl_new:N \recurrence_tl_guard % => \l_recurrence_guard_tl
\regex_const:Nn \recurrence_tl_integer_regex { ^[-+]*[0-9]+$ }
% => \l_recurrence_integer_regex
\regex_const:Nn \recurrence_tl_true { true }
% => \l_recurrence_true_regex
\int_new:N \recurrence_case_count
% => \l_recurrence_case_int
\cs_new_nopar:Npn \recurrence_prefix: {
recurrence
} % I'd use \tl_new:N and \tl_set:Nn \l_recurrence_prefix_tl, but this is ok.
\cs_new_nopar:Npn \recurrence_is_integer:xTF #1{
\regex_match:NnTF \recurrence_tl_integer_regex {#1}
}
\cs_new_nopar:Npn \recurrence_is_integer:NTF #1{
% I don't understand why I need the exp_args:Nx
\exp_args:Nx
\recurrence_is_integer:xTF {\tl_use:N #1}
}
% That's not expandable => should be _protected.
% Also, x expansion won't happen magically:
% you must define the base n-type function, then
% define the x variant from it
% =>
% \cs_new_protected_nopar:Npn \recurrence_if_integer:nTF #1
% { \regex_match:NnTF \recurrence_tl_integer_regex {#1} }
% \cs_generate_variant:Nn \recurrence_if_integer:nTF { x }
% \cs_new_nopar:Npn \recurrence_if_integer:NTF #1
% { \recurrence_if_integer:xTF {\tl_use:N #1} }
%
% Actually, it would be simpler to generate the o or V variant
% (instead of x), and use \recurrence_if_integer:VTF #1.
\cs_new_nopar:Npn \recurrence_case_name:xx #1#2{
\recurrence_prefix: _ #1 _ #2:x
}
% Ok. I'd personally call that function ...:nn, not :xx,
% but it is true that given that it is used in csname
% constructions, we end up x-expanding (not quite...).
% #1 is integer token list
%% => "integer variable". There's no such thing as an integer token list.
\cs_new_nopar:Npn \recurrence_case_name:N #1{
\recurrence_case_name:xx \recurrence_tl_name {\int_use:N #1}
}
\cs_new_nopar:Npn \recurrence_case_name:n #1{
\recurrence_case_name:xx \recurrence_tl_name {#1}
}
% You can reduce that to only one function using \int_eval:n.
% \cs_new_nopar:Npn \recurrence_case_name:n #1
% { \recurrence_case_name:xx \recurrence_tl_name { \int_eval:n {#1} } }
% #1 is index
% #2 is rhs
\cs_new_nopar:Npn \recurrence_define_constant:xx #1#2{%
\edef\recurrence_current_case_count{\int_use:N \recurrence_case_count}
% Shudder.
% => \int_set_eq:NN \l_recurrence_current_case_int \l_recurrence_case_int
% (of course, you'll need \int_new:N \l_recurrence_current_case_int before)
\int_incr:N \recurrence_case_count
\cs_new_nopar:cpx {\recurrence_case_name:n
\recurrence_current_case_count} ##1{
\exp_not:N
\int_compare:nTF {##1=#1} {#2}
{\cs:w \recurrence_case_name:N \recurrence_case_count
\cs_end:{##1}}
}
}
% - If you use \int_eval:n in the previous function, you can drop the
% recurrence_current_case variable completely, and use
% \recurrence_case_name:n { \l_recurrence_case_int + 1 }
% (or -1 depending on when you increment that
% integer variable).
%
% - Use \exp_not:c { foo } or \use:c { foo } (do you
% want expansion?) rather than \cs:w foo \cs_end:.
% #1 is guard tl
% #2 is rhs tl
\cs_new_nopar:Npn \recurrence_case_definition:xx #1#2{
\edef\recurrence_current_case_count{\int_use:N \recurrence_case_count}
\int_incr:N \recurrence_case_count
\cs_new_nopar:cpx {\recurrence_case_name:n
\recurrence_current_case_count} ##1{
\exp_not:N
\bool_if:nTF {#1} {#2}
{\cs:w \recurrence_case_name:N \recurrence_case_count
\cs_end:{##1}}
}
}
% Same comments as above: dont store integes in token list variables.
% #1 is name tl
% #2 is index tl
% #3 is rhs tl
% #4 is guard tl
\cs_new_nopar:Npn \recurrence_case_definition:NNNN #1#2#3#4{
\exp_args:Nx
\recurrence_sanitise:nNN {{\tl_use:N #1} {\tl_use:N #2}} #3 #4
% => \recurrence_sanitise:VVNN #1#2#3#4
\regex_replace_all:NnN \recurrence_tl_true {\\int_compare_p:n \{ 1
= 1 \}} #4
% => \c{int_compare_p:n} \cB\{ 1 = 1 \cE\}
% otherwise you get a string of characters instead of a control sequence
% and begin-group and end-group braces.
\recurrence_case_definition:xx #4 #3
}
\cs_new_nopar:Npn \recurrence_sanitise:nNN #1#2#3{
\recurrence_sanitise:nnNN #1 #2 #3
}
% Should be removed if using the :VVNN function above.
% \cs_generate_variant:Nn \recurrence_sanitise:nnNN { VV }
% #1 is name
% #2 is index
% #3 is rhs tl
% #4 is guard tl
\cs_new_nopar:Npn \recurrence_sanitise:nnNN #1#2#3#4{
\recurrence_sanitise:nnN {#1} {#2} #3
\recurrence_sanitise:nnN {#1} {#2} #4
}
% #1 is name
% #2 is index
% #3 is tl list
\cs_new_nopar:Npn \recurrence_sanitise:nnN #1#2#3{
\regex_replace_all:nnN {#2} {\#1} #3 % This \# looks very odd.
Perhaps "\cP\#" ?
\regex_replace_all:nnN {\b#1\b\[([^\]]+)\]} {\\#1:n\{\1\}} #3
}
% The second \b does nothing. Including #1 directly is risky if it
% contains special characters that should be escaped. Instead,
% you should try " \u{l_recurrence_name_tl} " (or whatever tl var
% contains that #1).
%
% \\#1:n\{\1\}
% => \c{\u{l_recurrence_name_tl}:n} \cB\{ \1 \cE\}
% What does this do? Well, \c{...} is like the c-type argument
% (think \exp_not:c). \u{...} is like the v-type argument, and
% unpacks the variable \l_recurrence_name_tl, so that's similar
% to your \\#1:n, except that it produces an actual control sequence
% instead of a string of characters with catcode other.
% Then \cB\{ makes a Begin-group character {.
% And \cE\} makes an End-group character }.
\cs_new_nopar:Npn \recurrence_error_definition:{
\edef\recurrence_current_case_count{\int_use:N \recurrence_case_count}
\cs_new:cpx {\recurrence_case_name:n \recurrence_current_case_count}##1{
\exp_not:N
\error{\tl_use:N \recurrence_tl_name[~##1~]~undefined.}
}
}
% See comment in main email about \msg_expandable_error:n.
\cs_new_nopar:Npn \recurrence_wrapper_definitions:{
% You can use \l_recurrence_name_tl direclty everywhere
% instead of \recurrence_temp.
\edef\recurrence_temp{\tl_use:N \recurrence_tl_name}
\cs_new_nopar:cpx {\recurrence_temp} ##1{%
\exp_after:wN \exp_not:N
\cs:w \recurrence_temp :n \cs_end: {##1}
% => \exp_not:c { \l_recurrence_name_tl :n } {##1}
}
\cs_new_nopar:cpx {\recurrence_temp :n} ##1{%
\noexpand \exp_args:Nx
\exp_after:wN \exp_not:N
\cs:w \recurrence_case_name:n 0 \cs_end:
{\exp_not:N \int_eval:n{##1}}
% => \exp_not:N \exp_args:Nf % see commens on Nx versus Nf
% => \exp_not:c { \recurrence_case_name:n 0 } { \exp_not:N
\int_eval:n {##1} }
}
}
% should be named \recurrence_<something>:n
% maybe \recurrence_new:n ?
\cs_new_nopar:Npn \NewRecDef:n #1{
\begingroup % \group_begin:
% => directly \clist_map_inline:nn {#1} { ... }
% and you can drop the clist variable altogether.
\clist_set:Nn \recurrence_csv_list {#1}
\clist_map_inline:Nn \recurrence_csv_list {
\regex_extract_once:nnNTF
{ ^(\w+)\[(\w+)\]\=(.+?)\|(.+)\|(.+) } {##1|true||} \recurrence_tl_temp
% the extract_once function returns a sequence
% so \recurrence_tl_temp => \l_recurrence_temp_seq.
{
% at this stage, \recurrence_tl_temp has 6 items,
% 0th: a[i]= expression | guard | guard option
\seq_pop:NN \recurrence_tl_temp \recurrence_tl_bin
\seq_pop:NN \recurrence_tl_temp \recurrence_tl_name
\seq_pop:NN \recurrence_tl_temp \recurrence_tl_index
\seq_pop:NN \recurrence_tl_temp \recurrence_tl_rhs
\seq_pop:NN \recurrence_tl_temp \recurrence_tl_guard
% Variable names.
\recurrence_is_integer:NTF
\recurrence_tl_index
{\recurrence_define_constant:xx \recurrence_tl_index
\recurrence_tl_rhs}
{\recurrence_case_definition:NNNN
\recurrence_tl_name \recurrence_tl_index
\recurrence_tl_rhs \recurrence_tl_guard}
} { \recurrence_error }
}
\recurrence_error_definition:
\recurrence_wrapper_definitions:
\endgroup % \group_end:
}
\DeclareDocumentCommand\NewRecDef{ m }{
\NewRecDef:n {#1}
}
\ExplSyntaxOff
|
