# San sequents – specifications

This is still another epistle in the ongoing saga of the definition of the San programming language. This article tries to nail down details of the sequent concept, definition, and features.

## 8.0 Sequents

The San language supports a programming construct called a sequent. Sequents can be thought of as mini-programs that produce lists (of scalar values). The general model is one of a list (produced by a source) modified serially by a suite of operators that accept an input list, modify it, and emit an output list.

A sequent consists of a sequence expression enclosed within brackets. Sequence expressions consist of a sequence source optionally followed by sequence operators. Sequence sources are recursively built up from a combination of primary sources and sequents.

### 8.1 A grammar for sequents

This is a quasi-formal description of the grammar for sequents, i.e., enough material so that one specify a formal grammar.
```Special characters:
lb:     Left bracket
rb:     Right bracket
vb:     Vertical bar
Terms and such:
SRC:    A list source
PS:     Primary source
SO:     Operator
SX:     Sequence expression
SQ:     Sequent
Production rules:
SQ  <- lb SX rb
SX  <- SRC | SX vb OP
SRC <- PS | SQ | SRC SQ | SQ SRC
```

### 8.2 Use of sequents in San code

```Sequents can appear in loop specifiers, i.e.., the form
begin loop VAR from SEQUENT
They can also appear in distributed assignments, e.g.,
foo[] <- [1...n]
which sets the contents of foo[] to be the integers from 1 to n.
```
(Note: strictly speaking it sets the primary values of foo’s vectors of morphs to be the integers.)

### 8.3 Primary sources

Primary sources are either simple lists or sequence generators. There are two major categories of primary sources, sequence special forms, and morph vectors. In addition there are also some miscellaneous sources.

#### 8.3.1 Simple lists

The simplest type of primary source is the simple list, e.g.,
[x, y, z]
Note that this list is a list of the (default) values of x, y, and z.

#### 8.3.2 Special forms representing sequences

```        (a) integer sequences, e.g., m...n
(b) semi infinite integer sequences, e.g., m...*
(c) letter sequences, e.g., 'A...'Z
(c) alphseq
The alphseq generator successively generates the lower case
letters a...z, the letter pairs aa...zz, etc.
```

#### 8.3.3 Morph vectors

```        (a) row vector,    foo[]
(b) row slice,     foo[i,]
(c) column vector, foo.[]
(d) column slice,  foo[,i]
The blank field in a morph vector may have a range, e.g.,
foo[[m...n] refers to rows m through n only.
```

#### 8.3.4 Special generators

```        (a) random numbers, randgen
Randgen generates a semi-infinite sequence of random numbers.
Specs for randgen are to be determined.
```

#### 8.3.5 Sources producing semi-infinite sequences

Some sources, e.g., alphseq and randgen, produce semi-infinite sequences, i.e., sequences that have an initial element, but no terminal element. These sequence generators are necessarily evaluated lazily using “just in time” semantics.

### 8.4 Predefined sequent operators

Sequent operators can be divided into three classes, depending on what happens when they are presented with an unboundedly large input stream. These classes are (a) operators that are not well defined for unbounded input streams, (b) operators that are well defined but require O(n) space, and (c) operators that are well defined for all streams and require O(1) space.

The “keep” operator is critical because it converts potentially unbounded streams into bounded streams.

#### 8.4.1 Operators not well defined for unbounded input

```
keep-last n          Passes the last n items of input
cut-last n           Removes the last n input items
rotate-right k       Rotates the input list right by k
rotate-left k        Rotates the input list left by k
reverse              The input list is reversed
repeat-list k        The input list is replicated k times
append list          Appends items in list to input
non-uniq             Only passes replicated items
```

#### 8.4.2 Operators defined but O(n) for unbounded input

```        uniq                 Removes duplicates from input
```

#### 8.4.3 Operators defined and effective for all streams

```        step k               Passes every k'th input item
cut n                Removes the first n input items
prepend list         Prepends items in list to input
separate item        Inserts item between each adj. pair
repeat-items k       Input items are duplicated k times
rmv-items list       Removes items in list from input
pass-items list      Removes items not in list from input
match pattern-list   Passes items matching a pattern
in the pattern list
format spec          Formats each item with spec
```

#### 8.4.3 Operators forcing conversion to finiteness

```        keep n               Passes the first n items of input
```

### 8.5 Boolean expressions as operators

An incomplete boolean relationship can be used as a filter; all entities satisfying the relationship are passed, and those not satisfying the relationship are deleted. An incomplete boolean relationship is one in which one of the pair of entities is missing. For example, the sequent

```        [1...5 | ne? 4]
```
produces as output the sequence {1, 2, 3, 5}.

Instead of using incomplete relationships one can use \$0 to stand for the list item being filtered. Thus our example could have been written:

```        [1...5 | \$0 ne? 4]
```
Similarly, incomplete boolean queries (a boolean query operator has only one argument) can be used as filter operators. For example,
```        ['a,'b,'c,4 | number? ]
```
produces as output the sequence {4}. As with relationships the missing argument can be filled by \$0; our example could have been written
```        ['a, 'b, 'c, 4 | number? \$0]
```
Compund booolean expressions must have complete relationships and queries. For example:
```        [1...10, 'x, 'y | number \$0 and \$0 lt? 4 ]
```
produces as output the sequence {1,2,3}

### 8.6 Arithmetic expressions as operators

When arithmetic expressions are used as operators, the expression is evaluated for each input, and the evaluated expression is output. In the case of arithmetic expressions the input item must be represented by \$0. For example, the sequent
```
[ 1...4 | (3 * \$0) + 1]
```
yield the sequence {4, 7, 10, 13}

### 8.7 User defined operators

User defined sequent operators have two input ports, \$0 and \$1, and one output port \$out0. Inputs are presumed to be blocked, i.e., they do not accept semi-infinite input. When invoked in a sequent \$0 comes from the piped input and \$1 comes from the argument list. \$out0 is sent to the output pipe.

Here are examples of sequent operator programming. The first routine is an implementation of quick sort; the second routine is an implementation of merge sort.

```
begin operator qsort
pivot   :=  \$0
small[] := [\$0[] | lt? pivot | qsort]
big[]   := [\$0[] | gt? pivot | qsort]
same[]  := [\$0[] | eq? pivot        ]
emit [small[], same[], big[]]
end qsort
begin operator msort
begin operator merge
begin switch
<empty?  \$0> => emit \$1[]
<empty?  \$1> => emit \$0[]
\$0 lt? \$1    => emit \$0
else         => emit \$1
end
end merge
odd[]  <- [\$0[]         | step 2 | msort]
even[] <- [\$0[] | cut 1 | step 2 | msort]
emit [odd[] | merge [even[]]
end msort
```