wiki:BigIdeas/Structures

Structures

Everything has a structure because everything is made out of atoms. From what atoms are made is beyond the abstraction barrier. From life's point of view atoms are atomic and immutable. Life has been built itself on this assumption.


A value could have a structure. Like a molecule. H2O, for example, has a structure. An aminoacid has a structure. Usually such compound value is called a structure or a record. A structure is a set of named slots. (I really love this old-timer's Lisp terminology - it is much more accurate).

Each slot could be accessed "physically" or "logically". Physically means that one has to know an exact location of the value of the slot, like in (caddr x). Logically means one should know the name (a semantic or symbolic pointer, if you wish) of the slot and call a corresponding selector procedure (point-x p) to get a corresponding value of a slot.

This association between a symbol (name) and value (meaning) is the most fundamental mechanism. Even DNA transcription uses a some sort of a lookup table that matches triplets into actual aminoasids!

Put together, the ideas of Structures and Declarative definitions gave us things like struct statements in programming languages, SQL, SGML and HTML, Yaml and Json - the very foundation of Software.

Logically, each structure defines its own type (or a kind). Classes, being a structures of data and code, are its own types too. This is very natural - it reflects our associative thinking and natural language usage. A bike has an engine, and engine has a volume and other characteristics. A bike has a color, etc.

Basically, structures are the most natural way to declaratively define a real-world things (I hate the word objects, since the subject-object is the most famous false dichotomy).

Here is how we could describe a thing as a structure of three named slots which corresponds to attributes of a real thing.

('((model . "")
   (year  . 0)
   (color . ""))
{
   "model": "",
   "year":  0,
   "color": ""
}

The big idea here is that each kind of structure defines its own type.

(defstruct bike
   model
   year
   color)
create table bike (
   model    varchar(40),
   year     smallint,
   color    varchar(20)
);

Basically, we could think as a structure as a record type or and object (an instance of a class, a record of a table) which encapsulates a set of key-value pairs and a set of methods to get and set the corresponding values.

type bike = {model: string, 
             year: int, 
             color: string};

This is exactly how a class definition might look like

(defclass bike ()
    ((model)
     (year)
     (color)))

or

class Bike:
    model = None
    year = None
    color = None

Suppose I want to represent some characteristic of my bike, like model, year of production and, say, color. So, I would associate symbols to values in a List

'((model . "Royal Enfield")
  (year  . 2015)
  (color . "Black"))

Notice, that these characteristics are not particular only to my own bike but are general enough do describe any bike.

This means that this particular Data Structure could be generalized to represent a general, abstract bike.

'((model . "")
  (year  . 0)
  (color . ""))

The symbols here are slots, while each slot has an associated (Consed) value. To access a value we need to know the name or symbol associated with it.

So, each such List of Conses with slots associated with particular values is called an instance of a particular kind of a general structure.

Common Lisp has a special form - defstruct - to define such general structures and procedures to instantiate structures and access the slots.

(defstruct bike
   model
   year
   color)

Which is basically almost as if I would say "Let an instance of a type Bike be an Association List of three slots, named 'model, 'year and 'color".


Structures, like Lists, could be neted. However, sometimes nested structure could have slots of the same name (same symbols) which usually means that the concepts they represent are somehow related or rather overlap.

The most familiar example would be a Bike and Motorcycle, which is, basically, a Bike with a Motor.

(defstruct motorcycle
   model-name
   engine-cc
   year
   color)

Which means that a Motorcycle could be considered as a Subclass or a specialization of a Bike, which is a more generalized notion, or a more Abstract Class.

To capture a Class - Subclass relationships (a specialization) the attributes (slots) that are in common could be "shared" with the more abstract Structure.

(defstruct (motorcycle (:include bike))
    engine-cc)

This literally means that the notion of a Motorcycle includes (or contains) the notion of a Bike, together with another specific characteristic - namely engine-cc. This special kind of Nesting reflects an abstract idea of Classification.


Logically, each unique structure constitutes its own Abstract Data Type. Some languages require to define a new type when declaring a structure, others require to define a class as a template. Common Lisp has a corresponding special forms defstruct

For so-called compound data we could reference the members either by position (a index or an offset) or by a symbol (name) associated to the slot. The index/offset approach is wrong, because it exposes the ordering of a structure (which should be hidden as an implementation detail). When we alter the structure (by adding or removing a slot) we have to readjust all the offsets. In case of acceding by the symbol the structure becomes a look-up table, where elements are unaffected by each other - adding or removing an entry affects does not alter the use side.

Here is a simple ADT, constructor

(define (make-point x y)
    (cons x (cons y '())))

and selectors or getters

(define (get-x p)
    (car p))
(define (get-y p)
    (cadr p))

the underlying structure of conses is not exposed when we use selectors instead of (car p) and (cadr p) which relies not the implementation details (the actual data-structure being used - the linked list). When we use constructors and selectors (getters or setters) we are using an interface, treating the structure as a "black box". This is the essence of an Abstract Data Type, which is, basically, a named interface.

Other languages define data types explicitly.

data Point = Pt {pointx, pointy :: Float}

each class is of its own type.

class Point:
    pointx
    pointy

A new [instance of a] structure is created by calling a [data] constructor.

Members of the structure (slots) are accessed using selectors.

Methods of an object is nothing but a named slots associated with procedures (code).

There are corresponding constructors and selectors for each ADT. Some language, like Common Lisp or Haskell create selectors implicitly into the global namespace. Other, like Python, offer a standardized notation for selecting parts of a structured object.

Swift in swift structures could contain methods, giving that a code block (a closure) is a first class value.

struct Card {
    var rank: Rank
    var suit: Suit
    func simpleDescription() -> String {
        return "The \(rank.simpleDescription()) of \(suit.simpleDescription())"
    }
}

However, life is not that simple. Sometimes characteristics are overlap but not completely, and attributes are similar but not identical.

To capture this dissimilarity we could redefine (or shadow) a particular slot in a more specialized Structure.


Generalized Nesting of Structures according to a Class - Subclass relationship gives us another fundamental notion of Inheritance - of Nested Concepts.

Last modified 2 years ago Last modified on Sep 13, 2017, 4:47:12 AM
Note: See TracWiki for help on using the wiki.