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

12
  • 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? May 25, 2015 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? May 25, 2015 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?" May 25, 2015 at 17:09
  • Section 2.2 in sicp text. May 25, 2015 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? May 25, 2015 at 17:24

1 Answer 1

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.

1
  • 1
    Every language except Java 1.7
    – Basilevs
    Jun 5, 2015 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.