Permalink copied!
The integral
function
at the end of the preceding section shows how we can use streams to model
signal-processing systems that contain
feedback loops. The feedback loop for the adder shown in
figure 3.58 is modeled by the fact that
integral's
internal stream
integ
is defined in terms of itself:
const integ = pair(initial_value,
() => add_streams(scale_stream(integrand, dt),
integ));
The interpreter's ability to deal with such an implicit definition
depends on the delay resulting from wrapping the call to
add_streams in a lambda expression.
Without this delay, the interpreter could not
construct integ before evaluating the call
to add_streams, which would require
that integ already be defined.
In general, such a delay is crucial for using streams to model
signal-processing systems that contain loops. Without a delay,
our models would have to be formulated so that the inputs to any
signal-processing component would be fully evaluated before the output
could be produced. This would outlaw loops.
Unfortunately, stream models of systems with loops may require uses of a
delay beyond the stream programming pattern seen so far. For instance,
figure 3.61 shows a
signal-processing system for solving the
differential equation $dy/dt=f(y)$ where
$f$ is a given function. The figure shows a
mapping component, which applies $f$ to its
input signal, linked in a feedback loop to an integrator in a manner
very similar to that of the analog computer circuits that are actually
used to solve such equations.
Figure 3.61
An
analog computer circuitthat solves the equation $dy/dt = f(y)$.
Assuming we are given an initial value $y_0$ for
$y$, we could try to model this system using the
function
function solve(f, y0, dt) {
const y = integral(dy, y0, dt);
const dy = stream_map(f, y);
return y;
}
This
function
does not work, because in the first line of
solve the call to
integral requires that the input
dy be defined, which does not happen until the
second line of solve.
On the other hand, the intent of our definition does make sense, because we
can, in principle, begin to generate the y
stream without knowing dy.
Indeed, integral and many other stream
operations can generate part of the answer given only partial
information about the arguments.
For integral, the first element of the output
stream is the specified initial_value. Thus,
we can generate the first element of the output stream without evaluating
the integrand dy. Once we know the first
element of y, the
stream_map
in the second line of solve can begin working
to generate the first element of dy, which will
produce the next element of y, and so on.
To take advantage of this idea, we will redefine
integral to expect the integrand stream to be a
delayed argument.
The function integral will force
the integrand to be evaluated only when it is required to generate more than
the first element of the output stream:
function integral(delayed_integrand, initial_value, dt) {
const integ =
pair(initial_value,
() => {
const integrand = delayed_integrand();
return add_streams(scale_stream(integrand, dt),
integ);
});
return integ;
}
Now we can implement our solve
function
by delaying the evaluation of dy in the
declaration of
y:
function solve(f, y0, dt) {
const y = integral(() => dy, y0, dt);
const dy = stream_map(f, y);
return y;
}
In general, every caller of integral must now
delay
the integrand argument. We can demonstrate that the
solve
function
works by approximating
$e\approx 2.718$ by computing the value at
$y=1$ of the solution to the differential
equation $dy/dt=y$ with initial condition
$y(0)=1$:
[1]
stream_ref(solve(y => y, 1, 0.001), 1000);
2.716923932235896
The integral
function
used above was analogous to the
implicitdefinition of the infinite stream of integers in section 3.5.2. Alternatively, we can give a definition of integral that is more like integers-starting-from (also in section 3.5.2):
function integral(integrand, initial_value, dt) {
return pair(initial_value,
is_null(integrand)
? null
: integral(stream_tail(integrand),
dt * head(integrand) + initial_value,
dt));
}
When used in systems with loops, this
function
has the same problem
as does our original version of integral.
Modify the
function
so that it expects the integrand as a
delayed argument and hence can be used in the
solve
function
shown above.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Consider the problem of designing a signal-processing system to study
the homogeneous
second-order linear differential equation
\[\begin{array}{lll}
\dfrac {d^{2} y}{dt^{2}}-a\dfrac{dy}{dt}-by &=& 0
\end{array}\]
The output stream, modeling $y$, is generated by
a network that contains a loop. This is because the value of
$d^{2}y/dt^{2}$ depends upon the values of
$y$ and $dy/dt$ and
both of these are determined by integrating
$d^{2}y/dt^{2}$. The diagram we would like to
encode is shown in figure 3.62. Write a
function solve_2nd
that takes as arguments the constants $a$,
$b$, and $dt$ and the
initial values $y_{0}$ and
$dy_{0}$ for $y$ and
$dy/dt$ and generates the stream of successive
values of $y$.
Figure 3.62
Signal-flow diagram for the solution to a second-order linear
differential equation.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Generalize the
solve_2nd function
of exercise 3.78 so that it can be used to
solve general second-order differential equations
$d^{2} y/dt^{2}=f(dy/dt,\, y)$.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Figure 3.63
A series RLC circuit.
A series RLC circuit
consists of a resistor, a capacitor, and an
inductor connected in series, as shown in
figure 3.63. If
$R$, $L$, and
$C$ are the resistance, inductance, and
capacitance, then the relations between voltage
($v$) and current
($i$) for the three components are described
by the equations
\[\begin{array}{lll}
v_{R} &=& i_{R} R\\[9pt]
v_{L} &=& L\dfrac{di_{L}}{dt}\\[11pt]
i_{C} &=& C\dfrac{dv_{C}}{dt}
\end{array}\]
and the circuit connections dictate the relations
\[\begin{array}{lll}
i_{R} &=& i_{L}=-i_{C}\\[3pt]
v_{C} &=& v_{L}+v_{R}
\end{array}\]
Combining these equations shows that the state of the circuit (summarized by
$v_{C}$, the voltage across the capacitor, and
$i_{L}$, the current in the inductor) is
described by the pair of differential equations
\[\begin{array}{lll}
\dfrac{dv_{C}}{dt} &=& -\dfrac{i_{L}}{C}\\[11pt]
\dfrac {di_{L}}{dt} &=& \dfrac{1}{L}v_{C}-\dfrac{R}{L}i_{L}
\end{array}\]
Figure 3.64
A signal-flow diagram for the solution to a series RLC circuit.
Write a
function
RLC that takes as arguments the parameters
$R$, $L$, and
$C$ of the circuit and the time increment
$dt$. In a manner similar to that of the
RC
function
of exercise 3.73,
RLC should produce a
function
that takes the initial values of the state variables,
$v_{C_{0}}$ and
$i_{L_{0}}$, and produces a pair
(using pair)
of the streams of states $v_{C}$ and
$i_{L}$. Using RLC,
generate the pair of streams that models the behavior of a series RLC
circuit with $R = 1$ ohm,
$C= 0.2$ farad,
$L = 1$ henry,
$dt = 0.1$ second, and initial values
$i_{L_{0}} = 0$ amps and
$v_{C_{0}} = 10$ volts.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
The examples in this section illustrate how
delayed evaluation
provides great programming flexibility, but the same examples also show how
this can make our programs more complex. Our new
integral
function,
for instance, gives us the power to model systems with loops, but we must
now remember that integral should be called
with a delayed integrand, and every
function
that uses integral must be aware of this.
In effect, we have created two classes of
functions:
ordinary
functions
and
functions
that take delayed arguments. In general, creating separate classes of
functions
forces us to create separate classes of higher-order
functions
as well.
[2]
One way to avoid the need for two different classes of
functions
is to make all
functions
take delayed arguments. We could adopt a model of evaluation in which all
arguments to
functions
are automatically delayed and arguments are forced only when they are
actually needed (for example, when they are required by a primitive
operation). This would transform our language to use normal-order
evaluation, which we first described when we introduced the substitution
model for evaluation in section 1.1.5.
Converting to normal-order evaluation provides a uniform and elegant way to
simplify the use of delayed evaluation, and this would be a natural strategy
to adopt if we were concerned only with stream processing. In
section 4.2, after we have studied the
evaluator, we will see how to transform our language in just this way.
Unfortunately, including delays in
function
calls wreaks havoc with our ability to design programs that depend on the
order of events, such as programs that use assignment, mutate data, or
perform input or output.
Even a single delay in the tail of a pair can cause great confusion, as
illustrated by exercises 3.51
and 3.52.
As far as anyone knows, mutability and delayed evaluation do not mix well
in programming
languages.
[2]
This is a small reflection, in
JavaScript,
of the difficulties that
early statically
typed languages such as Pascal
had
in coping with higher-order
functions.
In
these
languages, the programmer
had to
specify the data types of the
arguments and the result of each
function:
number, logical value, sequence, and so on. Consequently, we could not
express an abstraction such as Gordon, Milner, and Wadsworth 1979 ),
whose
map a given function fun over all the elements in a sequenceby a single higher-order function such as stream_map. Rather, we would need a different mapping function for each different combination of argument and result data types that might be specified for a fun. Maintaining a practical notion of
data typein the presence of higher-order functions raises many difficult issues. One way of dealing with this problem is illustrated by the language ML (
parametrically polymorphic data typesinclude templates for higher-order transformations between data types. Moreover, data types for most functions in ML are never explicitly declared by the programmer. Instead, ML includes a type-inferencing mechanism that uses information in the environment to deduce the data types for newly defined functions. Today, statically typed programming languages have evolved to typically support some form of type inference as well as parametric polymorphism, with varying degrees of power. Haskell couples an expressive type system with powerful type inference.
3.5.4
Streams and Delayed Evaluation