home
table of contents
Comp Sci
October 2003
email

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

This page was last updated October 18, 2003.

home
table of contents
Comp Sci
October 2003
email