Asynchronous Programming

PPL 2023

Control Flow in Programming Languages

Types of Control Flows

In this chapter, we will investigate the general topic of how to manage control flow in programming languages. Control flow is the order in which operations are executed within a program. In procedural languages, the simplest form of control flow is the sequence (execute statements one after the other). Conditional statements (if, switch, case) determine which of multiple continuations are followed depending on the value of a tested expression. Loops determine how often a block of operations are executed depending on the value of a tested expression.

In functional languages, the key control flow is function invocation: the body of the function is executed within a scope in which the arguments are bound to the parameters of the invocation, and then the flow returns to the context in which the invocation took place.

In addition to these classical control flows, programming languages include non local control flow: in these constructs, flows exits from a context of execution and continues at a predefined point. These include exceptions (try/catch/finally/throw), coroutines, generators, async/await, and continuation.

The study of control flow also includes a description of concurrency such as threads and their synchronization.

Interpreters and Control Flow: Asynchronous Programming and Continuation Passing Style

In the interpreters we have designed in Chapter 2, we did not explicitly model the call stack. The reason is that we relied on the call stack mechanism of the meta-language to provide the proper control of function calls and the return to their calling location. In this sense, the interpreter we wrote does not explain how control flow is implemented in the object language, because we use the control flow primitives of the meta language.

In this chapter, we investigate the mechanisms through which programming languages provide control flow, and variants of control flow across different programming paradigms. In particular, we present practical issues in Asynchronous Programming, and techniques allowing proper management of asynchronous tasks: callbacks, promises, and co-routines. We review these topics in TypeScript - where they practically fill an important role both in the domains of client user interface (to deal with User Interface events in a reactive manner) and of backend servers (to deal with protocol implementation which are IO-bound in a resource efficient manner).

We then introduce a technique called continuation passing style (CPS), investigate its properties and relate it to the way our interpreters model control flow, recursion and iteration. We switch back to Scheme and to our Interpreter models and demonstrate a systematic transformation from recursive to CPS style and introduce techniques which elucidate the way asynchronous and lazy programming techniques are designed.

Finally, we use the notion of continuation that we have made concrete in the CPS transformation, and use it to re-implement the interpreter of Chapter 2 with explicit description of control flow as general continuations. In this model, the interpreter is modeled as a function eval(exp, env, cont) => (value, cont) where cont represents the control state of the interpreter. At each step of the computation as explained by the operational semantics, the interpreter computes which expression to evaluate next and where to pass the result of this evaluation. We implement this new approach in the language \(L7\).

Function Invocation - Call Stack

When a function f calls a function g, g needs to know where to return to (inside f) after it is done. This information is usually managed with a stack, the call stack. Let’s look at an example:

// [Based on http://exploringjs.com/es6/ch_async.html]

function h(z) {
    // Print stack trace
    console.log(new Error().stack); // (A)
}
function g(y) {
    h(y + 1); // (B)
}
function f(x) {
    g(x + 1); // (C)
}
f(3); // (D)

-->
    Error
        at h (evalmachine.<anonymous>:5:17)
        at g (evalmachine.<anonymous>:8:5)
        at f (evalmachine.<anonymous>:11:5)
        at evalmachine.<anonymous>:13:1
        at ContextifyScript.Script.runInThisContext (vm.js:26:33)
        at Object.exports.runInThisContext (vm.js:79:17)
        at run ([eval]:608:19)
        at onRunRequest ([eval]:379:22)
        at onMessage ([eval]:347:17)
        at emitTwo (events.js:106:13)

Initially, when the program is started, the call stack is empty. After the function call f(3) in line D, the stack has one entry:

Location in global scope

After the function call g(x + 1) in line C, the stack has two entries:

Location in f
Location in global scope

After the function call h(y + 1) in line B, the stack has three entries:

Location in g
Location in f
Location in global scope

The stack trace printed in line A shows you what the call stack looks like:

Error
    at h (...:2:17)
    at g (...:6:5)
    at f (...:9:5)
    at ...

Next, each of the functions terminates and each time the top entry is removed from the stack. After function f is done, we are back in global scope and the call stack is empty.

The mechanism of a call stack to manage function calls and their return is present in all languages.

The call stack is managed implicitly at runtime, and is usually not exposed to the programmer.
In JavaScript, as demonstrated above, the Error() object provides access to the current state of the call stack - so that we can inspect it (this is mostly useful when debugging errors at runtime). A similar facility exists in Java with the method Thread.currentThread().getStackTrace().

Event Loops

JavaScript as a programming language is used in two main contexts:

In both of these application domains, it is useful to think of the task of the JavaScript interpreter as processing an event loop.

The following 25min presentation: Philip Roberts: What the heck is the event loop anyway? | JSConf EU 2014 provides a useful explanation of what is the event loop in the context of Web browsers.
The companion tool to this presentation visualizes the mechanism of the event loop: loupe

Event Loops in the Browser

Consider first a Browser context. The browser event loop executes browser-related tasks that are fed into the browser task queue. Typical browser tasks are generated when an HTML page is loaded into a browser tab, and they include:

The last 3 are tasks that run JavaScript code, in the JavaScript interpreter embedded in the browser. These tasks terminate when the code terminates. Then the next task from the queue can be executed.

For example, browsers offer a timer facility: setTimeout() creates a timer, waits until it fires and then adds a task to the queue. It has the signature:

setTimeout(callback, ms)

After ms milliseconds, callback is added to the task queue. It is important to understand that ms only specifies when the callback is added, not when it actually is executed. That may happen much later, especially if the event loop is heavily loaded.

Practically, the setTimeout primitive is a way to submit a task to the event loop for later execution.

setTimeout(() => { console.log("After sometime..."); }, 1000);
console.log("Immediately");
-->
    Immediately
    
    undefined

    After sometime...

In the setTimeout example, the first parameter is a function passed as an argument (taking advantage of the support for closures in the JavaScript language). The task that is posted to the event queue is called a callback (because it is called back by the event loop when it can instead of being called by the programmer directly).

Note how the task is represented: it is a procedure of no parameters. What we submit to the task queue is a closure. The idiom: () => { ... } indicates we “package” code to be executed later. When and who executes it later can be decided by the programmer or by the runtime environment.

Another typical example of callbacks in the Browser context is to associate callbacks to User Interface widgets. A typical example would be:

$("#btn_1").click(
  () => alert("Btn 1 Clicked")
);

The anonymous function passed as an argument to the click() method defines a callback which is invoked by the Browser event loop whenever the button is clicked.

Event Loops in Node

In the node.js context, the event loop is driven by events related to asynchronous I/O calls. For example, when invoking the file system, to open a file, the time taken by the Operating System (OS) system call is extremely large compared to the time it takes to execute a function call. Instead of making the interpreter block and wait for this system call to complete, the Node interpreter submits a task to the event loop, which consists of invoking the callback of the system call when it has completed.

This strategy requires the programmer to change fundamentally the way I/O calls are organized. All the primitive calls to the File System (fs) module take a function as an argument - which is called the callback which is invoked when the slow FS operation has completed.

Compare the synchronous and asynchronous versions of a file system call:

// Synchronous (blocking) call to readFileSync
// The return value of the readFileSync procedure can be passed directly to the JSON.parse function.
const readJSONSync = (filename) => {
  return JSON.parse(fs.readFileSync(filename, 'utf8'));
}

const writeJSONSync = (filename, map) => {
  return fs.writeFileSync(filename, JSON.stringify(map), 'utf8');
}

writeJSONSync("test", {id:1, text:'hello'});
console.log(readJSONSync("test"));
-->

    { id: 1, text: 'hello' }

// Asynchronous version using callbacks
const fs = require('fs');

const readJSON = (filename, callback) => {
  fs.readFile(filename, 'utf8', (err, res) => {
    if (err) 
      callback(err, undefined);
    else
      callback(undefined, JSON.parse(res));
  });
}

const writeJSON = (filename, map) => {
  fs.writeFile(filename, JSON.stringify(map), (err) => {
    if (err)
      console.error(err);
    else
      console.log("The file was saved: ", filename);
  });
  console.log("This is invoked before the callback is invoked.");
}

writeJSON("test.async", {id:1, test:'async'});
readJSON("test.async", (err, res) => { console.log(res); });

-->
    This is invoked before the callback is invoked.
    undefined
    The file was saved:  test.async
    { id: 1, test: 'async' }

In the example above, the fs.writeFile Node method takes 3 arguments:

This pattern takes advantage of the fact that JavaScript allows passing functions as arguments to other functions: the callback is an argument passed to the file system primitive.

Internally, the way the Node interpreter implements asynchronous methods such as fs.writeFile is that it invokes a non-blocking system call of the Operating System. (For students who took the Systems Programming course, recall the lecture on non-blocking-IO in Java (SPL chapter on Reactor.) The Node interpreter then adds a subscription to the corresponding selector (which indicates when the asynchronous non-blocking call has completed). The event-loop of the interpreter performs as follows: execute a task, when the task is completed, wait on the selector, when the selector is fired (indicating an earlier asynchronous call completed), retrieve the closure corresponding to the fired event and execute it as a task, then loop again.

Programming with callbacks is not easy. We cannot make the usual time-sequencing assumptions we make in sequential code. In the example above, we know that the expression immediately after the call to fs.writeFile() is executed before the callback is invoked. This guarantee is part of the semantics of the Node interpreter.

But we cannot make any assumption as to when the callback will be executed. It can take a very long time. The problem for the programmer is to decide where and how to write code which depends on the completion of the file system operation. Answering this question will be the main topic of this chapter.

Thinking of the JavaScript engine as a reactive event loop instead of an active process which invokes procedures is an important change of perspective - which is related to the design pattern of inversion of control and which defines the event-driven programming paradigm.

Callbacks and the Call Stack

In asynchronous programming, callbacks are not invoked in the same call stack as the procedure that creates the callback. Instead, the function which generates the task (the asynchronous call) executes, and when it ends, it creates a task (a closure) which is added to the task queue.

When the event loop determines that the callback is ready to be called, the runtime environment invokes the task with the appropriate arguments. The signature of the callback is determined by the asynchronous function: in the example above, the callback for the readFile procedure is a function with 2 parameters (err, data) which represent either an error object or the data that was read from the file. These arguments are passed to the callback when the event is signaled.

The callback is a closure which is created in the context of the asynchronous function. Hence, according to the operational semantics of the language, we know it has access to the environment in which it was created (not to the environment which is current when the closure is invoked). See for example how the environment of the callback is used:

const readJSONTime = (filename, callback) => {
  let invoked = new Date();  // Timestamp when the read is invoked.
  fs.readFile(filename, 'utf8', (err, res) => {
    if (err) 
      callback(err, undefined);
    else {
      // This accesses a variable from the closure env.
      console.log("Invoked at: ", invoked);
      console.log("Callback at: ", new Date());
      callback(undefined, JSON.parse(res));    
    }
  });
}

readJSONTime('test.async', (err, res) => console.log(res));
-->
    undefined

    Invoked at:  2017-06-08T12:55:42.764Z
    Callback at:  2017-06-08T12:55:42.765Z
    { id: 1, test: 'async' }

Even if the environment is available, the callback is evaluated in a different control context - that is, in a different call stack.

Composing Asynchronous Functions

Composing synchronous functions is easy: given a function f(x:Tx):Tf and a function g(y:Ty):Tx - we can compose the calls by simply passing the return value of g as a parameter to f: f(g(y)). As long as the types are compatible, this composition works (the return type of g must be the parameter type of f).

Composing asynchronous functions is more challenging: we must write a specific callback each time we compose two functions:

g(y, (gRes) => f(gRes, callback))

If we want to compose three functions - the callbacks must be nested accordingly - instead of f(g(h(x))) we must write:

h(x, (hRes) => {
    g(hRes, (gRes) => {
        f(gRes, callback);
    })
});

Note how the order of the occurrences has changed: we read the program in the order in which the functions are invoked (first invoked h, then invoke g, then invoke f).

The Type of Asynchronous Functions

When we think of composing synchronous functions, we check their type - that is, we verify that the type returned by g matches the type expected by f in order to enable the composition f(g(x)).

Asynchronous functions do not return any value - that is, they are of return type void.
Instead, they post a future task which will receive a parameter of a certain type in the future.

That is, if a synchronous function has type f(x: Tx): Tf - the corresponding asynchronous function will have type asyncF(x: Tx, callback: (Tf -> Tc)): void.

Error Handling with Asynchronous Procedures (Success / Fail callbacks)

In many cases, asynchronous functions can fail - this is the case for most I/O calls (file system, networking calls) which are most likely to be used in an asynchronous manner.

To process the case of errors - the callback passed to the async function must be prepared to deal with either a success outcome, or with an error outcome. Conceptually - this means the async function has 2 callbacks: one to process success, one to process failure.

In the examples we reviewed above, we worked with a callback that has two parameters - one for error and one for the returned data in case of success. When composing asynchronous functions with two parameters of this type, we introduce systematic complexity - because there is no way to “stop early” the chain of calls when an error is detected - as we would do by throwing an exception in a synchronous case. We must handle the error case at all steps of the chain of calls.

For example, assuming the function f, g and h can return an error or a success, the composition of f(g(h(x))) requires the following structure:

h(x, (hErr, hRes) => {
    if (hErr) {
      failCallback(hErr);
    } else {
      g(hRes, (gErr, gRes) => {
        if (gErr) {
          failCallback(gErr);
        } else {
          f(gRes, callback);
        }
      })
    }
});

The following issues make the usage of asynchronous functions difficult for the programmer:

Using Promises to Simplify Asynchronous Composition

Promises are a general programming pattern designed to simplify asynchronous composition, in particular error handling.

A promise represents the result of an asynchronous operation - it is an object which serves as the proxy for a delayed computation which can be in different states:

Once a promise is fulfilled or rejected, it becomes immutable (i.e. it can never change again).

Promises allow the client (the programmer) to associate handlers with an asynchronous action’s eventual success value or failure reason. This lets asynchronous methods return values like synchronous methods: instead of immediately returning the final value, the asynchronous method returns a promise to supply the value at some point in the future.

Clients of a promise register with the promise by submitting the callbacks they want the promise to execute. Since we want to simplify error handling, the client of a promise can register one callback for success completion (fulfillment) and one for error handling (rejection handler).

The registration is performed using two methods of the Promise interface:

The handlers are functions which are submitted to be executed in the future, when the promise is resolved (either fulfilled or rejected).

At this point, our understanding of a promise is that it is an object with the following state:

The key events in the lifecycle of a promise correspond to state transitions:

Making a Promise

To construct a promise from an asynchronous function with a callback, we use the Promise constructor and abstract the callbacks for success and failure:

const readFilePromise = (filename: string): Promise<string> => {
  return new Promise<string>( (resolve, reject) => {
    fs.readFile(filename, (err, res) => {
      if (err) 
        reject(err);
      else
        resolve(res.toString('utf8'));
    })
  })
}

The Type of a Promise

A promise is a container for a value which may become available in the future. A function such as readFilePromise above returns a promise - in contrast to the original readFile asynchronous function which had a void return type.

This ends up simplifying the type and making it more similar to the familiar synchronous version:

readFileSync(filename: string): string;

readFile(filename: string, callback: (err, data:string) -> T): void;

readFilePromise(filename: string) -> Promise<string>

TypeScript supports generic Promise types to document this type of return value.

Using a Promise

We use the Promisified-version of the asynchronous function according to the Promise client pattern:

To this end, we use the 2 methods of the Promise object: then(successHandler) and catch(errorHandler):

const testContent = readFilePromise('test.async');
testContent
    .then((content: string) => console.log("Content: ", JSON.parse(content)))
    .catch((err) => console.error(err));
-->

    Promise { <pending> }
    Content:  { id: 1, test: 'async' }

The style that the then and catch methods implement is special: they return a value of the same type as the object on which they are invoked, so that they can be chained. This style is called the fluent interface pattern.

Observe how the use of Promises is similar to the known type patterns we exploited when implementing interpreters and the type inference system in Chapters 2 and 3: Result and bind, Maybe and either.

Chaining Promises

Using promises, we can achieve 3 main benefits over the structure that callbacks only would require:

The following example illustrates these 3 benefits:

This requires a chain of asynchronous calls (reading the file and writing it).

Note that the error handler needs to be specified only once for the two operations

import * as fs from 'fs';

const readFilePromise = (filename: string): Promise<string> => {
  return new Promise<string>( (resolve, reject) => {
    fs.readFile(filename, (err, res) => {
      if (err)
        reject(err);
      else
        resolve(res.toString('utf8'));
    })
  })
}

const writeFilePromise = (filename: string, content: string): Promise<void> => {
  return new Promise( (resolve, reject) => {
    fs.writeFile(filename, content, (err) => {
      if (err)
        reject(err);
      else
        resolve();
    })
  })
}

// Chain the calls together
const readUpdateWrite = (filename: string): Promise<void> => {
    return readFilePromise(filename)
            .then((content) => {
                let j = JSON.parse(content);
                j.lastModified = new Date();
                return writeFilePromise(filename, JSON.stringify(j));
            })
            .catch((err) => console.error(err));
}

writeFilePromise('test.async', JSON.stringify({a: 1}))
    .then(() => console.log("File is created"))
    .then(() => readFilePromise('test.async'))
    .then((content) => console.log(JSON.parse(content)))
    .then(() => readUpdateWrite('test.async'))
    .then(() => console.log('File is updated'))
    .then(() => readFilePromise('test.async'))
    .then((content) => console.log(JSON.parse(content)));
-->
    File is created
    { a: 1 }
    File is updated
    { a: 1, lastModified: '2018-05-27T14:43:57.435Z' }

Promises Summary

Promises simplify the usage of asynchronous functions on three aspects:

From Promises to Async / Await

Promises improve significantly over callback-based asynchronous functions, but still cannot be used as simply as synchronous functions within simple control flow operations (sequence, conditionals, composition). Instead, we still need to pass the promise to a function using the .then(function) mechanism.

Promises are made even easier to use through the mechanism of async and await syntactic sugar which was introduced in standard JavaScript around 2017. These two new syntactic keywords introduce syntactic variants of the pattern which consists of building a promise and then chaining code into the then and catch methods of the promise. So that for example:

// Chain the calls together
const readUpdateWrite = (filename: string): Promise<void> => {
    return readFilePromise(filename)
            .then((content) => {
                let j = JSON.parse(content);
                j.lastModified = new Date();
                return writeFilePromise(filename, JSON.stringify(j));
            })
            .catch((err) => console.error(err));
}

is equivalent to the following syntactic variant:

// The async/await version
const readUpdateWrite_async = async (filename: string): Promise<void> => {
    try {
        const content = await readFilePromise(filename);
        let j = JSON.parse(content);
        j.lastModified = new Date();
        return writeFilePromise(filename, JSON.stringify(j));
    }
    catch (err) {
        return console.error(err);
    }
}

The specification for async and await explains how async and await are syntactic abstraction around Promises.

Key points about using async and await:

type Resolver<T,R> = (value: T) => R;

// wait ms milliseconds
const wait = (ms: number) : Promise<string> => 
    new Promise((r : Resolver<string, void>) => setTimeout(r, ms));

const hello = async () : Promise<string> => {
    await wait(500);
    return 'world';
}

const world = async () : Promise<void> => 
    console.log(await hello());

world();

An async function may not contain any await, it still returns a Promise:

async function f() {
    return 1;
}

returns a Promise which fulfills to 1.

The following example is from https://developers.google.com/web/fundamentals/primers/async-functions:

function logFetch(url) {
  return fetch(url)
    .then(response => response.text())
    .then(text => {
      console.log(text);
    }).catch(err => {
      console.error('fetch failed', err);
    });
}

is equivalent to:

async function logFetch(url) {
  try {
    const response = await fetch(url);
    console.log(await response.text());
  }
  catch (err) {
    console.log('fetch failed', err);
  }
}

Generators and Co-routines

Javascript (and other programming languages, including Python and Scheme) offer a mechanism called generators (see MDN generator documentation) which can be combined with promises to provide excellent support for asynchronous programming.

Generators are functions which can be exited and later re-entered. Their context (variable bindings and current control locations) are saved across re-entries. A generator is created with the keyword function*.

Calling a generator function does not execute its body immediately; an iterator object for the function is returned instead. An iterator is a map with two fields: {value: x, done: boolean} and that has a next() method:

interface IteratorResult {
    value: any;
    done: boolean;
}
interface Iterator {
    next(): IteratorResult;
}

When the iterator’s next() method is called, the generator function’s body is executed until the first yield() expression, which specifies the value to be returned from the iterator. The next() method returns an object with a value property containing the yielded value and a done property which indicates whether the generator has yielded its last value as a boolean. Calling the next() method with an argument will resume the generator function execution, replacing the yield statement where execution was paused with the argument from next().

A return statement in a generator, when executed, will make the generator done. If a value is returned from the body of generator, it will be passed back as the value to the next next() call. A generator which has returned will not yield any more values. (That is, return x is like yield(x) plus the side effect that the generator is now done.)

Let us examine a few examples of using generators:

function* idMaker() {
  let index = 0;
  while (index < 3)
    yield(index++);
}

const gen = idMaker();

console.log(gen.next().value); // 0
console.log(gen.next().value); // 1
console.log(gen.next().value); // 2
console.log(gen.next().value); // undefined 
0
1
2
undefined

The client of the generator can pass a parameter back to the generator by passing it through the next(val) call.
This value is retrieved on the generator side as the returned value of the yield() call.

function* demo() {
  const res = yield(10);
  assert(res === 32);
  return 42;
}

const d = demo();
d.next();
--> { value: 10, done: false }

d.next(32)
--> { value: 42, done: true }

d.next();
--> { value: undefined, done: true }

The function* special form is used to construct a generator. Within the body of a generator, the yield special form can be used.

Generators are most often consumed inside loops - and as their names indicate they generate a sequence of values in a lazy manner: instead of eagerly constructing a list of values, the generator knows how to generate the values only when asked to.

The for loop of JavaScript is a syntax which is adapted to consume any object which implements the iterator protocol, and hence works well with generators:

function* foo() {
    yield 1;
    yield 2;
    yield 3;
    yield 4;
    yield 5;
    return 6;
}

for ( let v of foo() ) {
    console.log(v);
}

Generators can be used to generate computed sequences - which can even be infinite, since they are only generated when requested:

function* range(start, end) {
    for (let n=start; n < end; n++) {
        yield n;
    }
}

for (n of range(1,5)) 
    console.log(n);

A generator can produce a potentially infinite stream of data. Such a generator is useful in case the consumer of the stream can limit the number of items to actually extract.

The following example demonstrates an infinite generator and a higher order function called take which takes as input a number and a generator - and returns a new generator which generates less than n items from the generator:

// An infinite generator
function* naturalNumbers() {
    for (let n=0;; n++) {
        yield n;
    }
}

function* take(n, generator) {
    for (let x of generator) {
        if (n <= 0) return;
        n--;
        yield x;
    }
}

for (let n of take(3, naturalNumbers())) {
    console.log(n);
}

Generators are an efficient mechanism to combine iterations without copying lists of data at each stage.

Consider the following examples:

// A map operator adapted to generators
function* mapGen(generator, mapFunc) {
    for (let x of generator) {
        yield mapFunc(x);
    }
}

// Can be combined with infinite generators
for (let n of take(4, mapGen(naturalNumbers(), x => x * x))) {
    console.log(n);
}
// 0, 1, 4, 9

// A filter operator adapted to generators
function* filterGen(generator, filterFunc) {
    for (let x of generator) {
        if (filterFunc(x)) {
            yield x;
        }
    }
}

for (let n of take(4, filterGen(naturalNumbers(), x => (x % 2) === 0))) {
    console.log(n);
}
// 0, 2, 4, 6

Such operators can be combined together - with the advantage that the data is not copied between each stage. Instead, each time an element of the combination is requested, the chain of functions is evaluated:

const evenSquares = filterGen(mapGen(naturalNumbers(), x=> x*x), x=> (x % 2) === 0);

for (let n of take(4, evenSquares))
    console.log(n);
// 0, 4, 16, 36

const evenSquaresVerbose = filterGen(mapGen(naturalNumbers(), x=> { 
        console.log("square ", x, "->", x*x);
        return x*x;
    }), 
    x => {
        console.log("filter ", x, "->", (x % 2) === 0);
        return (x % 2) === 0;
    });

for (let n of take(4, evenSquaresVerbose)) 
    console.log("EvenSquaresVerbose: ", n);

The order in which the functions are executed is item by item: map-square / filter-even / take

square  0 -> 0
filter  0 -> true
EvenSquaresVerbose:  0
square  1 -> 1
filter  1 -> false
square  2 -> 4
filter  4 -> true
EvenSquaresVerbose:  4
square  3 -> 9
filter  9 -> false
square  4 -> 16
filter  16 -> true
EvenSquaresVerbose:  16
square  5 -> 25
filter  25 -> false
square  6 -> 36
filter  36 -> true
EvenSquaresVerbose:  36
square  7 -> 49
filter  49 -> false
square  8 -> 64
filter  64 -> true

In contrast, the traditional map and filter functions allocate a list (an array) to store the intermediary results. The functions are evaluated on all the array at once - square on all the items of the input array first, then even on all the items of the output array.

Summary