📄 8funtab.html
字号:
<html>
<head>
<title>Function Table</title>
<meta name="description" content="Implementation of a function table">
<meta name="keywords" content="calculator, function, symbolic, function pointer, class, array">
<link rel="stylesheet" href="rs.css" tppabs="http://www.relisoft.com/book/rs.css">
</head>
<body background="margin.gif" tppabs="http://www.relisoft.com/book/images/margin.gif" bgcolor="#FFFFDC">
<!-- Main Table -->
<table cellpadding="6">
<tr>
<td width="78">
<td>
<h3>Function Table</h3>
<p class=topics>Meta-programs. Pointers to functions. Explicit array initialization. Explicit class initialization.
<p>For a good scientific calculator, built-in functions are a must. We have to be able to calculate square roots, logarithms, trigonometric functions, etc. We are quite lucky because the standard C library implements most of the basic math functions. All we need is for the parser to recognize the function call and then call the appropriate library function. The only tricky part is to make the connection between the function name梩he string recognized by the parser梐nd the call to the appropriate function.
<p>One way would be to create a multi-way conditional that compares the string to a list of predefined function names, and, when successful, calls the corresponding function.
<!-- Code --><table width="100%" cellspacing=10><tr> <td class=codetable>
<pre>if (strcmp (string, "sin") == 0)
{
result = sin (arg);
}
else if ...
...
</pre></table><!-- End Code -->
<p>As long as the number of built-in functions is reasonably small, this solution is good enough. Let抯 pretend though that, instead of a toy calculator, we are writing an industrial strength program that will have to handle hundreds, if not thousands, of built in functions. The problem than becomes: Given a string, match it against hundreds of pre-defined strings. Clearly, doing hundreds of string comparisons every time is not acceptable.
<p>But wait! We already have a string-matching object--the symbol table. Since it抯 implemented as a hash table, it can perform a match in constant time, independent of the size of the table. The symbol table converts a string into an integer. We can pre-fill the table with built in function names (just like we did with built-in constants) and dispatch the function calls based on integers rather than strings. We could, for instance, insert the string<var> "sin"</var> in the zeroth slot of the symbol table, <var>"cos"</var> in the first slot, etc., and then dispatch calls using a switch statement:
<!-- Code --><table width="100%" cellspacing=10><tr> <td class=codetable>
<pre>case 0:
result = sin (arg);
break;
case 1:
result = cos (arg);
break;
...
</pre></table><!-- End Code --><p>A switch statement that uses a set of consecutive labels, 0, 1, 2, etc., is implemented by the compiler as a jump table with a constant switching time independent of the number of labels. Seems like a perfect, constant-time solution.
<p>But how do we make sure that <var>sin</var> always corresponds to 0, <var>cos</var> to 1, etc.? Well, we can always initialize the symbol table with these strings in this particular order. After all, we know that the symbol table assigns consecutive indexes starting with zero. Is it okay though? These are implementation secrets of the symbol table. What if the next guy to maintain our program rewrites the symbol table to use an even better algorithm? One that does not assign consecutive indexes starting with zero?
<p>And how about expandability of such code? Suppose that at some point in the future we will want to add one more built-in function. What changes will we have to make to this implementation? We抣l have to:
<ul>
<li>Add one more case to the switch statement,
<li>Add one more string to the symbol table, and
<li>Make sure that the string is inserted at the offset that is the case label of the corresponding function.
</ul>
<p>Notice what we have just done. We have written a <var>meta-program</var>: a set of instructions to be followed in order to add a new built-in function to our calculator. These are not machine instructions, these are instructions for the programmer. In fact, they don抰 appear anywhere in the program, even as comments梩hey are implicit. This kind of invisible <var>meta-code</var> adds to the hidden complexity of a program. What does meta-code describe? It describes the steps to be taken to implement the most likely extension to the program, as well as the assertions that have to be preserved when making such extensions.
<!-- Definition -->
<p>
<table border=4 cellpadding=10><tr>
<td bgcolor="#ffffff" class=defTable>
When comparing various implementations, take into account not only the complexity of code but also the complexity of meta-code.</table>
<!-- End Definition -->
<p>Let抯 see if we can find a better implementation for built-in functions. Optimally, we would like to have some kind of a table listing all the functions. (It is almost always a good idea to shift the complexity from code to data structures.) Adding a new function would be equivalent to adding a new entry to this table. The meta-program for such an implementation would consist of a single statement:
<ul>
<li>Add a new entry to the function array</li>
</ul>
<p>In order to make connection between data and executable code we need a new device: <b><i>pointers to functions</i></b>. A pointer to function is just like a regular pointer, only that instead of pointing to data it points to executable code. By using a pointer to data, you can read or modify data; by using a pointer to function you can call functions. Just like with any other type of pointer, we抣l have to be able to
<ul>
<li>declare a pointer to function,</li>
<li>initialize a pointer to point to a particular function,</li>
<li>make a function call using the pointer.</li>
</ul>
<p>For instance, we may declare a pointer to function taking a <var>double</var> (as an argument) and returning a <var>double</var>. There are many such functions and we can initialize the pointer to point to any one of these. In particular we may initialize the pointer to point to the function <var>double sin (double x)</var>. After that, if we make a function call through our pointer, we will be calling <var>sin</var>. Had we initialized the pointer to point to <var>double cos (double x)</var>, we would have called <var>cos</var> instead. The beauty of a pointer to function is that the same pointer may point to different functions during the execution of the program. The part of the program that makes the function call doesn抰 have to know what function it is calling.
<p>Let抯 see some actual code to see what the syntax looks like. First let抯 declare a pointer <var>pFun</var> to a function taking a <var>double</var> and returning a <var>double</var>:
<!-- Code --><table width="100%" cellspacing=10><tr> <td class=codetable>
<pre>double (* pFun) (double x);</pre>
</table><!-- End Code -->
<p>Compare it with the declaration of a function <var>sin</var> taking a <var>double</var> and returning a <var>double</var>:
<!-- Code --><table width="100%" cellspacing=10><tr> <td class=codetable>
<pre>double sin (double x);
</pre></table><!-- End Code --><p>Why did we have to enclose the asterisk and the pointer name within parentheses? We had to do it in order to distinguish the declaration of a pointer to function from a declaration of a function returning a pointer. Without the parentheses
<!-- Code --><table width="100%" cellspacing=10><tr> <td class=codetable>
<pre>double * pFun (double x);</pre>
</table><!-- End Code -->
declares a function taking a <var>double</var> and returning a pointer to <var>double</var>. Quite a difference!
<p>You can declare a pointer to any type of a function by taking the declaration of any function of this type and replacing the function name with <var>(* pFun)</var>. Of course, you can use an arbitrary name instead of <var>pFun</var>.
<p>Remember the function <var>strtod</var>? Its declaration was:
<!-- Code --><table width="100%" cellspacing=10><tr> <td class=codetable>
<pre>double strtod (char const * str, char ** ppEnd);</pre>
</table><!-- End Code -->
<p>A pointer to a function of this type would be declared as:
<!-- Code --><table width="100%" cellspacing=10><tr> <td class=codetable>
<pre>double (* pStrtod) (char const * str, char ** ppEnd);</pre>
</table><!-- End Code -->
<p>It抯 that simple!
<!-- Sidebar -->
<table width="100%" border=0 cellpadding=5><tr>
<td bgcolor="#cccccc" class=sidebar>
Because of pointers to functions, we have to augment the rules of reading declarations. We start reading backwards, as usual: <var>pStrtod</var> <i>is a pointer</i>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -