To: J3                                                     J3/23-235r2
From: Brad Richardson & Lorri Menard
Subject: SCAN and CO_SCAN
Date: 2023-October-25

#Reference: 23-113

Introduction
============

SCAN is a common operation closely related to REDUCE. Both SCAN and
REDUCE apply a binary operation to a sequence. SCAN returns the
sequence of results of the operations, where REDUCE returns only the
final result. Whether a SCAN is INCLUSIVE or EXCLUSIVE determines
whether an element in the resulting sequence includes the result of
the binary operation with the corresponding element in the input
sequence or not, respectively.

Throughout this paper the name "SCAN" is used; that may or may not
be the ultimate term used.  That will be determined later.

Typical applications that make us of scan operations include
design of binary adders, polynomial interpolation, simulation of
parallel algorithms that assume the ability for multiple processors
to access the same memory cell at the same time, on parallel machines
that forbid simultaneous access. Additional applications can be found
on the Wikipedia page for "Prefix sum":
https://en.wikipedia.org/wiki/Prefix_sum

Proposal
========

Provide SCAN_PREFIX/SCAN_POSTFIX intrinsic functions and
CO_SCAN_PREFIX/CO_SCAN_POSTFIX collective subroutines.
These function and subroutine shall implement scan operations
analogous to the REDUCE function and CO_REDUCE subroutine,
where the _PREFIX version is the "normal" version, and the
_POSTFIX version is right shifted one position. I.e.

SCAN_PREFIX([1, 2, 3], PLUS) == [1, 3, 6]
SCAN_POSTFIX([1, 2, 3], PLUS, 0) == [0, 1, 3]