3

From the reference of berkeley's version of sicp text, It is mentioned that:

Expressing programs as sequence operations helps us design programs that are modular. That is, our designs are constructed by combining relatively independent pieces, each of which transforms a sequence. In general, we can encourage modular design by providing a library of standard components together with a conventional interface for connecting the components in flexible ways.

For instance, In python, <class 'list'> and <class 'tuple'> are some of the types of mostly used sequential data models for storage.

For instance, In python <class 'dict'> is one popular type of non-sequential data model.

Text reference gives below solutions written in python to two different problems and mentions as similar solution, which is not convincing, because these two problems could not be the representative sample to take this decision.

>>> def sum_even_fibs(n):
        """Sum the even members of the first n Fibonacci numbers."""
        return sum(filter(iseven, map(fib, range(1, n+1))))
>>> sum_even_fibs(20)
3382

>>> def acronym(name):
        """Return a tuple of the letters that form the acronym for name."""
        return tuple(map(first, filter(iscap, name.split())))
>>> acronym('University of California Berkeley Undergraduate Graphics Group')
('U', 'C', 'B', 'U', 'G', 'G')

I am still not clear on the decision to make "sequences as conventional interfaces" despite these given examples.

So, Amidst designing a library or component, Why sequential type data models are recommended to be chosen as conventional interfaces?Is this something to do with closure property of these sequential data models(provided by python/scheme/lisp)?

Note: Same recommendation is given in SICP text from MIT press

overexchange
  • 2,245
  • 2
  • 17
  • 47
  • sum, filter and map all conform to a common sequence interface. They won't work without it. Ergo, without a sequence interface, you wouldn't have these functions. How difficult would it be to do the same thing without these functions? – Robert Harvey May 25 '15 at 16:41
  • I strongly feel it is due to closure property of sequential types(tuple/list) which enable hierarchical structures like tree to represent. I wonder why this point is missing in the text? – overexchange May 25 '15 at 17:05
  • Why would the implementation matter? It is the interface that enables such sequence transformations, not the underlying implementation (although the nature of the implementation can have a profound effect on performance). Can you link to the paper or article that describes these "closure properties of sequential types?" – Robert Harvey May 25 '15 at 17:09
  • Section 2.2 in sicp text. – overexchange May 25 '15 at 17:13
  • OK, I've read it. It says *"In general, an operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation. Closure is the key to power in any means of combination because it permits us to create hierarchical structures -- structures made up of parts, which themselves are made up of parts, and so on."* But what does that have to do with sequence interfaces? – Robert Harvey May 25 '15 at 17:24
  • Interface here mean input/output of a computational unit. ((1,2),3,4) is a sequential type data model(tuple in python) that actually depicts tree. – overexchange May 25 '15 at 18:14
  • OK. And? ...... – Robert Harvey May 25 '15 at 18:15
  • So, a computational unit can pass any type of compound data of this real world in the form of sequence to other computational unit. For example tuple. This could be the reason why sequences are conventional interfaces. This all is possible because sequence types are closure – overexchange May 25 '15 at 18:22
  • Well, almost. The interface represented by ((1,2),3,4) can pass any *tree-like sequence.* It still has some shape. In C#, the IEnumerable interface can represent *any sequence,* but underneath, it can be implementeed as a tree or a list. The implementation of the sequence will dictate how the sequence is iterated. Do you see the difference? – Robert Harvey May 25 '15 at 18:24
  • I feel like you've focused too much on the "sequence" part. The real point is "our designs are constructed by combining relatively independent pieces". They're certainly not saying you should prefer sequences over other types when designing a library, and the fact that they use sequences in their examples is largely incidental. – Doval May 25 '15 at 18:57
  • @Doval `The means of combination satisfy the closure property, which permits us to easily build up complex designs.` page 128-sicp – overexchange May 26 '15 at 06:46
  • @overexchange Lots of things have the closure property. Numbers, strings, vectors, matrices, functions, images, sounds...any class that contains method or function that takes another instance and returns an instance. – Doval May 26 '15 at 11:46

1 Answers1

7

The purpose of a dictionary is to return a value given a specified key, not to serve as a sequential container. Just because other data structures are sequential but dictionaries are not does not mean that the benefits of sequences are invalidated.

Sequences are one of the three fundamental logic structures in computing. Every (solvable) computing problem can be solved with three tools: sequences, loops, and decisions.

Sequences preserve the relationship between elements; that is, the first element must occur before the second element, which must occur before the third element, and so forth. That means we can retrieve the next element in a sequence, and be assured that we retrieved the element in the correct order, relative to the other elements. This has obviously useful benefits: words always consist of the same sequence of letters each time they are read, and methods consist of the same sequence of instructions each time they are called.

You can make sequences lazy. You can create a class that implements a state machine, and returns an element from the state machine each time a method is called. You can cache sequences.

Sequences can be created from linked lists, trees, and other data structures. Each data structure has its own specific qualities; a singly-linked list can be efficiently traversed in one direction, but not the other. Some data structures, such as binary trees, will give you sequential access and also efficient random access. Some data structures, such as doubly-linked lists, allow you to efficiently traverse the sequence backwards.

If you write your data structure to conform to a sequential interface, you can switch out your implementation of the sequence to whichever data structure is most appropriate for your given requirements. You can then write your code against that interface, and be assured that the underlying implementations are modular.

I don't know much about sequences in python, but the fundamental data structure in Scheme (used in the original SICP) is a list, and the ways in which you can compose such lists (which are essentially sequences), and the flexibility and power that affords, should be obvious. Every language containing sequences allows such compositions.

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673