San sequents - specificationsThis 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 SequentsThe 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 sequentsThis 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 codeSequents 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 sourcesPrimary 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 listsThe 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 sequencesSome 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 operatorsSequent 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 inputkeep-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 inputuniq Removes duplicates from input 8.4.3 Operators defined and effective for all streamsstep 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 finitenesskeep n Passes the first n items of input 8.5 Boolean expressions as operatorsAn 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 operatorsWhen 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 operatorsUser 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 This page was last updated October 18, 2003. |