GENERATORS

Dynamic functions
"What was new and essential to the whole of mathematics was the entirely general conception of function" (Dedekind).

---

Dynamic functions

Mathematical functions (those used by functional languages) are said to be static (or non-mutable), since they always return the same value with the same arguments. For example, the square of a natural number, the cosine function of an angle, the number of divisors of a natural number, and so on. A constant (for example 3) can be considered a static function with no arguments.

A dynamic (or mutable) function is one that can return a different value with the same arguments. For example, a variable (e.g., year) can be considered a dynamic function (without arguments) that returns a different value over time.

A dynamic function is a generalized function in the sense that the response S corresponding to a certain stimulus E (the function's input arguments) depends on its internal state I, which in turn changes (when invoked) to another internal state I'.

The scheme is as follows:


Maximum generality is achieved when there is polymorphism, that is, when the function also supports different types of inputs, internal states and outputs.

This model is that of objects and entities in nature. The static function is a particular case of an element that always responds in the same way to the same stimulus, regardless of its possible internal state. The static function is a mere mathematical concept that lacks generality and is not applicable to the real world.

This internal state is given by a series of persistent local variables. There may be other temporary local variables, which have no influence on the generated response.

A generator type is a dynamic function that returns on each call the next element of a sequence.


Specification in MENTAL
Definición

A dynamic function (generator) is a function that, when invoked, can produce as output a different expression each time. This means that the function depends on environment variables that act as additional internal parameters.


Examples

1. Generator g of the elements a, b and c cyclically. The function g has no formal parameter.
   
   h=c // internal parameter of initial value c

(g = ( h=a → (h=b ¡h) )
( h=b → (h=c ¡h) )
( h=c → (h=a ¡h) )°

g★5 // eq. (g g g g g g g g) ev. (a b c a b)
   
   
2. Fibonacci series generator. Function without formal parameters, but with internal parameters (n, n1 and n2), with null initial values.
   
   (n = 0)
(n1 = 0)
(n2 = 0)

(fibo = ( (n = n+1) ((m = 1) ← (n≥2) →' (m = n1+n2))

(n1 = n2) (n2 = m) ¡m)° )))

fibo★5 // ev. (1 1 2 3 5)
   
   
3. Example with formal parameter (the function f depends also on the variable m of the abstract space):
   
   
   (m = 0)
⟨( f(n) = (m = m+1) ¡(2*n + m) )⟩

f(0) // ev. 1
f(1) // ev. 4
f(1) // ev. 5
f(2) // ev. 7
f(2) // ev. 8

To initialize a generator

If we want to reset a generator to start over from the first value, we have to include a new parameter. For example, the parameter k, with two possible values:

1. k=0 indicates to initialize the generator and return the first value.
2. k≠0 indicates to continue with the generator and return the next value.

Example for the Fibonacci sequence:

⟨( fibo(k) = ( k=0 → ((n = 0) (n1 = 0) (n2 = 0))) )

(n = n+1)

((m = 1) ← (n≥2) →' (m = n1+n2))

(n1 = n2) (n2 = m)
¡m ) )⟩

fibo(0) // ev. 1
fibo(1) // ev. 1
fibo(1) // ev. 2
fibo(1) // ev. 3
fibo(1) // ev. 5
fibo(0) // ev. 1

Internal variable designation

To prevent internal variables of a generator from being confused with variables external to the generator, you can name such variables by (for example) relative expressions.

For example, the variables n, n1 and n2 of the Fibonacci number generator could be named, respectively:

fibo/n fibo/n1 fibo/n2

By virtue of the top-down evaluation principle, even if there were values for n, n1 and n2, these relative expressions would always be evaluated first as variables.

---

Addenda
Generators in programming languages

Generators can be emulated with traditional languages by procedures, but some languages support them, such as Alphard [Shaw, 1981], CLU [Liskov et al. 1981], and Icon [Griswold, 1983].

• In Alphard, the generators were defined, but the language remained unimplemented.
  
  
• In CLU, the generator is called an iterator, and its application is restricted to loops. It is used in conjunction with the for statement, serving to generate any type of element in each iteration. The iterator is a generalizing mechanism for the repetitive methods available in traditional programming languages.
  
  
• In Icon there is no such restriction. Each expression can be considered a generator, since it returns a value each time it is executed.

Programming with generators is explained in [Berztiss, 1990] and [Griswold, 1988].


Bibliography

• Berztiss, Alfs T. Programming With Generators. An Introduction. Ellis Horwood series in computers and their applications, 1990.
  
  
• Griswold, R.E.; Griswold, M.T. The Icon Programming Language. Prentice-Hall, 1983.
  
  
• Griswold, R.E. Programming with generators. Computer Journal, 31, pp. 220-228, 1988.
  
  
• Liskov, Barbara; Atkinson, Rusell; Bloom, Toby; Moss, Eliot; Schaffert, J. Craig; Scheifler, Robert; Snyder, Alan. CLU Reference Manual. Springer-Verlag, 1981.
  
  
• Shaw, M. (ed.). Alphard: Form and Content. Springer-Verlag, 1981.