Hyde County, South Dakota is the Pin Tail Duck Capital of the world. Visit scenic Highmore, SD in 2006!
Richard Harter's World
Site map
Computer Science
June 2006
email

Sequents and lazy lists

In the specification for the San programming language (not yet implemented) I introduced a construct I called a sequent. Basically the sequent construct is a list comprehension construct, i.e., a mechanism for generating lists. See The third way for a discussion of the motivation for this construct. There was an extended discussion in comp.lang.misc as to whether "just lazy lists". The idea works the same territory as lazy lists in functional programming languages (FPL) but its not the same animal. In this article I tabulate some of the differences.

Sequents

FPL Lazy Lists

Comments

The data source is prefix and the operations are postfix. That is, we begin with something that generates a list. The code then lists the operations that will be performed on that list as a sequence of stages. The data source is postfix and the operations are postfix. We begin with the final operation and then sequentially list the functions being applied until get to the postfix data source. This syntax difference reflects a difference in mode of thinking. When using sequents one thinks in terms of stages of processing connected by pipes; when using FPL lazy lists one thinks in terms of nested function calls.
The sequent construct is naturally encapsulated, i.e. they are syntactically isolated from the source code in which they are embedded. Lazy lists are not naturally encapsulated, i.e., a lazy list is just a list that is evaluated on demand at execution time. The upshot is that sequents are readily added to procedural languages whereas lazy lists fit in better with FPLs.
The individual stages are expressions, e.g., @*2 multiplies each input by two.

The implication is that to use sequents you need some special syntax for the piped data. Either you need closures or you need special symbols to stand for the piped data. In San I propose to use %0 for the current data item, %1 for the one just prior, %2 for the one before that, etc.

The individual stages are function calls.

The implication of this is that to use the FPL style you need the machinery of functional programming. That is, you need closures and a library of helper functions. It helps to have lambdas and currying. It also helps if everything is list oriented.

In simple cases sequents will require more syntax than FPL lazy lists; the situation is unclear for complex cases.
The items in the data source are passed on one at a time; to treat the data as a single entity you need a special gather operation to accumulate the data. The data source is a single entity; to act on the individual items one at a time you need a special splitting operation (the map function) that (a) accepts a function and a list as arguments, (b) applies the function to each element in the list, and (c) returns the collected results as a list. The sequent construct is more flexible when individual stages (functions) emit (return) more than one item.
There can be feedback, i.e., results from a later stage can be appended to the data source. Thus in San the sq.append operator does two things: (a) it outputs its input and (b) it appends its (evaluated) argument to the data source. For example, the sequent
[0,1 | sq.append %0+%1 ]
generates the fibonacci sequence, [0,1,1,2,3,5,8,...] as an infinite sequence.
This type of feedback is not straightforward in FPLs because it manipulates the argument list of a prior routine. In this respect sequents have more power; whether this is desirable is open to question.


This page was last updated June 1, 2006.

Richard Harter's World
Site map
Computer Science
June 2006
email
Hyde County, South Dakota is the Pin Tail Duck Capital of the world. Visit scenic Highmore, SD in 2006!