2.7.12 Iteration

One of many alternatives to recursion provided by the virtual machine is iteration, which allows an operation to be repeated until a condition is met. If the source language is imperative, this feature provides an easy means of translating loop statements to virtual code. In languages that allow functions to be treated as data, iteration can be regarded as a function that takes a predicate and a function as arguments, and returns a function that applies the given function repeatedly to its argument until the predicate is refuted.

Iterative applications are expressed in virtual code by the pattern shown below.

T21

[[iterate]] (p,f) = ((nil,nil),(nil,(p,f)))

In the silly language, the iterate mnemonic plays the role of the function that takes the virtual code for a predicate p and a function f as arguments, and returns the virtual code for an iterating function.

The code for an iterating function is recognized as such by the virtual machine emulator only if the subtrees f and p are other than nil. The resulting function tests the argument x with p and returns x if the predicate is false.

P22

([[iterate]] (p,f)) x = x if p x = nil

If the predicate turns out to be true, f is applied to x, and then another iteration is performed.

P23

([[iterate]] (p,f)) x = ([[iterate]] (p,f)) f x if p x is a non-nil tree

This document was generated on November 8, 2012 using texi2html 1.82.