wiki:Example

Let me show you something..

There are several views, several perspectives on the same thing - one made out of words of a English language, which are labels, symbols for a inner representation of a concept, one is a picture - a visualization of a form, a shape of the whole thing, another is a visualization of a structure - connections between parts, and there are several others constructs of a mind, made our of words and links between them what we call Logic.

All those perspectives are imperfect, confusing, incomplete, naive, but they are corresponds to different parts of our brain and different processes in our mind. The consciousness, the focus, the beam of light just switches between those perspectives, and another processes in the mind are trying hard to put them all together into one, coherent, consistent big picture. (I know, words cannot define it, only in naive way).

Description

There are something we call Atoms. They are the basic elements, which cannot be decomposed into the smaller parts. They might be further decomposeable, they might be made out of smaller parts, but we assume, that, on this moment, they are atoms.

Atoms can be of three kinds - Symbols, Numbers and The-Empty-List.

But Symbols actually are Numbers, while Numbers have corresponding Symbols, and The-Empty-List is a Number and a Symbol. This is, by the way, the moment when all that Object Oriented Paradigm should start shifting down.))

So, there could be one Atom, or a bunch of Atoms.

There are various concepts in Math - a Tuple, a Set, a Vector, a List. Tuple, for example, has a property that it is immutable which means also fixed-size. Vector, on the other hand is of a fixed-size but of mutable elements, set has a property that all its elements are unique but could be added and removed, maintaining its uniqueness.

For us it is too complicated (I have no shame or guilt), we don't need all those properties. All we need is a simple, intuitive, familiar basis.

Definitions

So, we say that we have Atoms and we have Pairs.

Now what is a Pair? Lets write it down:

  • a Pair is made out of two Atoms (of what else could it be made?)
  • a Pair has a Left Half and a Right Half. (well, for us there are left side and right side of a visual field)
  • the Left Half of a Pair is called CAR. (thus we attach a label, a symbol to the concept)
  • the Right Half of a Pair is called CDR.

Here it comes. Now we have a structure.

a Pair is an Object (NO, there will be no public class foo) made out of two Atoms, so it is a Compound Object - two Primitive Elements put together.

There are few questions immediately arise:

  • How those two Atoms are held together?
  • Where this Compound Object is?
  • What are those Atoms?
  • Is there a Primitive Objects?

Now we have a hierarchy. Lots of them.

Hierarchy

Lets try to use words.

  • an Object can be either Primitive or Compound.
  • an Atom is a Primitive Object
  • a Pair is a Compound Object

In order to look sophisticated enough we shall say that there is a set called Primitive Objects and a set called Compound Objects, while Numbers and Symbols are subsets of a set called Primitive Objects.

But there are also The-Empty-List. Well, it is also a subset of Primitive Objects in itself. So far, so good. But The-Empty-List is a member of Numbers and a member of Symbols and a member of itself.. What happened to our hierarchy? Words cannot describe this well enough?

Lets look how the two Atoms held together.

Representation

Well,

  • a Pair is two adjoined Pointers. Adjoined what?
  • a Pointer is an Address of an Object. address where?
  • an Address is a Number of a Byte in Memory.
  • a Byte is a chunk of Memory of a fixed length, a Slot.
  • a Memory is a continuous sequence of enumerated chunks of a fixed size - an Array. AAAAAAAA!!!!!

Lets leave it like this for a minute, and talk about Rules.

Interface

Now what are those Atoms, and before that, how can we put two Atoms together?

We need a Procedure. What is a Procedure? Let's put this question in a Queue.

There are Rules:

  • a Pair could be created using a Primitive Procedure called CONS
  • a CAR of a Pair could be obtained using a Primitive Procedure named CAR
  • a CDR of a Pair could be obtained using a Primitive Procedure named CDR

Notation

This is a Symbolic Notation, a description of the rules above:

(CAR (CONS 1 2)) ; a CAR of a Pair of two Numbers 1 and 2 is 1
(CDR (CONS 1 2)) ; a CDR of a Pair of two Numbers 1 and 2 is 2

But how.. Well, lets switch to the Implementation perspective:

Implementation

Two Addresses are held in a two adjoined Words of Memory (a Word is a chunk of Memory of a size of a Register or a Machine-Address). One of two Words has lower Address than another (Number of its Slot is less than one of another), so we could call it Lower Word and Higher Word, because there is no left or right in Memory.

Rules:

  • CONS returns a Pointer to an Object representing a Pair of Pointers
  • CAR return a Lower Word - a Pointer to a Left Atom of a Pair
  • CDR return a Higher Word - a Pointer to a Right Atom of a Pair

But what is about The-Empty-List? That is easy. The Slot of Memory containing a value of a 0 is The-Empty-List.

But instead of holding an Address of a Slot containing a 0 we could put a zero instead of Address into a Higher Word. This is called a Convention.

So, now you see, it is all about switching between different perspectives - Verbal description, Logic, Representation, and remembering Rules and Conventions which put together is called an Interface.

Now lets mess it all up.

What if there are:

  • more than two Atoms?
  • more than one Pair?

Then there is a sequence what we call a List! (lets don't ask ourselves a silly question what is a sequence).

Lets witch to our Hierarchy view:

  • Lists are made out of Pairs (very logical, but what about Atoms?)
  • Improper-Lists are made out Pairs and, well, Atoms.

Switch back to Logic:

  • The-Empty-List is a List of 0 Elements (Zero. Nil. No value. False).

Representation:

  • The-Empty-List is a Number 0

Notation:

  • The-Empty-List is a Symbol '()

back to Definitions:

  • A List of 1 Element is a Pair of an Atom and The-Empty-List.
  • A List of 2 Elements is a Pair of an Atom and another Pair of an Atom and The-Empty-List.
  • A List of n Elements are nested Pairs.

Some Notation:

(LIST 1 2 3 4) ; => (1 2 3 4)

which is mere a Syntactic Sugar for:

(CONS 1 (CONS 2 (CONS 3 (CONS 4 '()))))

Back to Implementation:

This is a moment, an experience of a Magic:

Because everything is represented as a Pointer, anything could be an Element of a List. Wait!

Now back to Hierarchy:

there are few of them:

There are things - Primitive or Compound:

  • Primitive
    • Atoms
      • Numbers
      • Symbols (wait, isn't Symbols are Numbers?)
      • The-Empty-List (wait..)
    • Procedures
  • Compound
    • Objects
      • Pairs
        • Lists (what about Atoms?)
          • Expressions (a List of Atoms)
            • Procedures (stop! stop..)

Lets describe it using words first:

What is a Expression of a Language? It is a well-formed sentence which consists of Words. We use sequences of Symbols to represent Words. A Word is a Label, a Symbolic Tag associated with a inner representation of a mental concept. Lets stop here for a moment.

  • a Procedure is a List of Expressions
  • an Expression is a List of Atoms
  • a List is a sequence of a nested Pairs
  • a Pair is a two Pointers
  • a Pointer is an Address of a Slot of Memory
  • what is inside depends on Representation.

Conventions

a List is a sequence of nested Pairs. So, we could imagine, and because of that, threat a List as a Pair.

Lets visualize what is the head of a List, its Leftmost Pair. (What is the head of an Arrow? the Yellow Arrow?)

  • CAR of this Pair is the first Element of the List
  • CDR of this Pair is the sub-list - all the Elements of the List, except the first Pair.

So, if we want to add a new Element to a List, we just CONS it in front of the List.

(CONS 1 '(2 3 4))  ; (1 2 3 4)
(CAR '(1 2 3 4))   ; the CAR of the first Pair is a Number 1
(CDR '(1 2 3 4))   ; the CDR of the first Pair is the List (2 3 4)

Now Implementation details:

  • because everything is a Pointer, we (almost) never copy the data in Memory, we just replace Addresses in Slots
  • The Address of the new Pair becomes the Address of the whole new List, and the CDR of the new Pair will point to the original List, so, everything is held together.
  • Pairs of Pointers is an ultimate glue which holds everything together. It is the representation of an association.
  • when we need multiple copies of the same data we just create a new Pointer to the same Slot of Memory.
  • Associating an Address with a new Symbol (another name) produces a Synonym. Symbols are symbolic pointers.
  • thus we pass a Value by Reference (which is another name for a Pointer). Pointer is an Address, a Number.

Lets not go into more details. They are irrelevant for now. What we need is a feeling of what inside, the principles. Knowing principles allows you to not memorize all the details.

Moreover, all those Hierarchies are mere constructions of our mind. There are nothing inside a computer, but bits. It from a bit. How we group, partition, interpret and use those bits is a yet another perspective, another level of abstraction.

What we should deal with is a high-level Symbolic Notation which uses a List structure as a basic building block. That mean we should follow the Definitions, Rules, Conventions and Interface for a List structure. This is much more appropriate level than raw bits. But we must be able to easily and instantly zoom through all the layers to the raw bits and back.

Now, when we know something (only by constantly switching between different perspectives) about Definitions, Logic, Conventions, Interfaces, Representation and Implementation Details, lets forget it, and talk about Abstractions and its Meaning.

Abstractions

There are different kinds of Expressions, with a we call Forms. Some Forms are special, they called Special Forms..

There

Last modified 8 years ago Last modified on Jul 28, 2012, 11:29:12 AM
Note: See TracWiki for help on using the wiki.