SICP series - Introductory Concepts

14 November 2019
Tags: fundamentals SICP

This post is going to illustrate some of the introductory concepts presented in the book Structure and Interpretation of Computer Programs [1].

Terminology

A procedure is a series of mechanical steps to be followed in order to deduce the value associated to a problem. It is a recipe for describing the how-to imperative knowledge.

A process is the actual sequence of steps within a computer which concerns a particular version of the problem.

A language provides the tools to capture procedures and describe processes; it is composed of several components.

  • vocabulary - basic elements of computation

  • syntax - rules for writing compound expressions

  • semantics - rules to deduce meaning of constructs

  • procedure - rules for capturing process of evaluation

abstraction

In order to create a language then the following ones are the steps to be taken.

  • create a set of primitive elements in a language (simple data and procedures) - primitives

  • create a set of rules for combining elements of the language - means of combination

  • create a set of rules for abstracting elements of the language - means of abstraction

From an implementation point of view in Scheme, the previous elements are translated into the following constructs.

  • primitives: numbers, strings, booleans, built-in procedures

  • means of combintation: open parenthesis, expression evaluating to a value, possibly other expressions, close parenthesis Example: (+ 5 6 (* 2 3))

  • means of abstraction: define keyword, name, expression whose value is associated to that name Example: (define total (- 100 30))

The goal of writing procedures is then to control complexity; procedures lead to the fundamental concept of abstraction. A procedure can then be seen as a black box, in which the details of its implementation are hidden and detached from its use. To put it all together the elements of a language allow to create complex systems through the means of combination of primitives, which can then be abstracted into procedures and then be used as primitive elements themselves. This cycle is beneficial for designing, maintaining and extending complex computational systems.

interfaces and programming paradigms

Abstraction allows to isolate components of a system, but it also provides the interfaces to interconnect those simple components. Some conventions or programming paradigms are for example object-oriented and streams.

meta-linguistic abstraction

The most powerful tool a language provide when the aforementioned tools are not sufficient to solve some problems is known as meta-linguistic abstraction. This consists in creating languages specifically oriented at some problem domain.

Conclusion

To sum up the previous points, the following outline provides an overview of the major sections which comprise the book.

  • procedure and data abstraction

  • conventional interfaces and programming paradigms

  • meta-linguistic abstractions