LebGeeks

rahmu

Moderator

Analyzing a programming language

In SICP, there's a common concept recurrent all throughout the book, when talking about the design of (powerful) programming languages. It first appeared in Section 1.1.

Every powerful language has three mechanisms (...):

• primitive expressions, which represent the simplest entities the language is concerned with

• means of combination, by which compound elements are built from simpler ones

• means of abstraction, by which compound elements can be named and manipulated as units

This categorization is omnipresent all throughout the book and I'm not sure I get it entirely; I am hoping members here with strong CS background can help me out with this.

Primitives

I understand the first point about primitives. I have a vague idea of the subtleties it introduces, and what it may imply. In the words of an unsung WWW hero:

When you get to languages with more features, the modeling can become more ambiguous. Generally speaking, a primitive expression is one that you can't or won't break down into primitive components. But it's like the atom: it's primitive until science marches on. For example, there is a variant of the lambda-calculus in which variables use numbers rather than names (de Bruijn indices), which is particularly convenient when modeling lambda-terms for computer proofs; and in computer proofs, integers are broken down into constituent parts. So in these models, variables aren't primitive expressions after all.

The part about Atoms getting broken down in smaller parts must particularly ring true to scientists here.

Combination vs abstraction

This is where my head explodes. I can understand the distinction between the abstract concepts, but it doesn't tell me, for instance, if the class mechanism of Java is a mean of combination or a mean of abstraction. After all, isn't combination done for abstraction purposes? And, isn't abstraction achieved (almost) exclusively through combination of other elements?

To me, it just feels that the two overlap so much that making the distinction at a definition level is more confusing than anything else.

Can anyone please help me make sense of all this maddness?

arithma

Re: Analyzing a programming language

Pair of integers. A combination of two integers. Not much abstraction here
A linked list and an array are sequential containers. A sequential container is an abstraction of both.
A pair of elements of a certain type. An abstraction of pairs.

A good abstraction allows a single algorithm to work on more than one encapsulation (combination) of primitives. Any good abstraction requires its assumption to be assessed by the programmer or the compiler.
An example would be map:(A -> B) over sequences (or their iterators). You can map an infinite sequence to another infinite language for example in lazy evaluated languages (eg. Haskell.)

There are many implementations of abstractions. Polymorphism is one (through interfaces for example). Abstractions are sometimes synonymous with contracts since they are what you can assume of a certain object. That's why inheritance (in C++ for example) or more recently interfaces (Java, C#...) is used for providing contracts.
The fact that before we had generics in C#, that they used ambiguous interfaces for collections shows the kind of overlap between Generics/Template/Algebraic.Data.Types and strictly classic OOP. Of course, the more algebraic, the better the static checking we get out. Hence the move to generics in later versions of C#.
Flying upwards still, you'd hit Monads, and functions of functions, and currying, and pureness.

rahmu

Moderator

Re: Analyzing a programming language

Pair of integers. A combination of two integers. Not much abstraction here
A linked list and an array are sequential containers. A sequential container is an abstraction of both.
A pair of elements of a certain type. An abstraction of pairs.

This is merely explaining the abstract difference between the words "abstraction" and "combination". Nothing to say here, but it doesn't answer my question.

A good abstraction allows a single algorithm to work on more than one encapsulation (combination) of primitives. Any good abstraction requires its assumption to be assessed by the programmer or the compiler.
An example would be map:(A -> B) over sequences (or their iterators). You can map an infinite sequence to another infinite language for example in lazy evaluated languages (eg. Haskell.)

I'm sorry but I'm not sure I understand.

Do you mean to say that abstraction is a mechanism allowing a single logic work on multiple types of data? This definition of abstraction seems a little too narrow. The definition I (the book) gave was "[the] means [...] by which compound elements can be named and manipulated as units".

There are many implementations of abstractions. Polymorphism is one (through interfaces for example). Abstractions are sometimes synonymous with contracts since they are what you can assume of a certain object. That's why inheritance (in C++ for example) or more recently interfaces (Java, C#...) is used for providing contracts.

I was sure you were going to mention Java/C# interfaces. The thing is, yes, this is a perfect example of abstraction. But does this really answer my question?

Maybe I worded it wrong. I perfectly understand what is abstraction (perfectly is a big word. I have a solid idea of what it means and a general view of what it implies). My question is about mechanisms that are not clearly one or the other. I gave Java's class mechanism as an example. Is it an abstraction mechanism or a combination one?

The answer is most probably "a little bit of both", then my question is: How valid is the above 3 point categorization?

In a way I answered myself while answering you: It's not about making every keyword fit into one category; it's more about having anything do each of the three. A class is probably a mean of combination, of abstraction and (to a large extent) a primitive of the language all the same. That makes Java a powerful language (by the above definition) and that's how I should look at it.

The fact that before we had generics in C#, that they used ambiguous interfaces for collections shows the kind of overlap between Generics/Template/Algebraic.Data.Types and strictly classic OOP. Of course, the more algebraic, the better the static checking we get out. Hence the move to generics in later versions of C#.
Flying upwards still, you'd hit Monads, and functions of functions, and currying, and pureness.

Here's why I think your view is a little narrow: C#, Java, C++ and Haskell are all statically typed. It's not uncommon for static typing to reduce the problem to a simple type check.

I work a lot with Python and Scheme which are dynamically typed. (For the record, I think static typing is better most of the times. But that's another debate...) The idea that abstraction is simply about applying a logic to several types is not very relevant to languages that basically implement duck-typing.

There are naturally no ambiguity in "interfaces" (well we just use classes) for various collections in Python. The homiconicity of Lisp also solves the challenge in different way.

What I'm saying is that writing a contract may be good practice but it's not the one and true way of achieving abstraction.

Fischer

Re: Analyzing a programming language

this question is similar
http://programmers.stackexchange.com/qu … g-language

arithma

Re: Analyzing a programming language

But first, a question as an answer to a question: Why does it matter?
Am not trying to discourage the discussion, but we need a little bit of context. Are you trying to perhaps apply some of the things you learned about this categorization on Java classes and it's breaking apart? That's what am figuring.

This is merely explaining the abstract difference between the words "abstraction" and "combination". Nothing to say here, but it doesn't answer my question.

It actually does indeed answer your question. But let's move through.

A good abstraction allows a single algorithm to work on more than one encapsulation (combination) of primitives. Any good abstraction requires its assumption to be assessed by the programmer or the compiler.
An example would be map:(A -> B) over sequences (or their iterators). You can map an infinite sequence to another infinite language for example in lazy evaluated languages (eg. Haskell.)
I'm sorry but I'm not sure I understand.

Do you mean to say that abstraction is a mechanism allowing a single logic work on multiple types of data? This definition of abstraction seems a little too narrow. The definition I (the book) gave was "[the] means [...] by which compound elements can be named and manipulated as units".

Naming compound elements is exactly typing. Manipulating types comes in one of two shapes that I am familiar with: constructing parameterized types or passing instances of this type to functions.

This is where my head explodes. I can understand the distinction between the abstract concepts, but it doesn't tell me, for instance, if the class mechanism of Java is a mean of combination or a mean of abstraction. After all, isn't combination done for abstraction purposes? And, isn't abstraction achieved (almost) exclusively through combination of other elements?

It really isn't hard to see that a class is a means of {combining data} into an abstraction. It's obvious why it's a combination. Let's get past that. It's an abstraction in that it provides a contract for multiple methods on all the class'es and its subclasses' instances.

How'd you implement a Java class language feature into, say, C.

One way to do that is to create a constructor function that returns a void pointer.
You will keep the instance variables in a struct. A pointer to this struct (the void pointer) would be passed around into the "class methods".
You will also need to keep a struct somewhere to describe the class itself, keeping a class name, and more necessarily pointers to all the methods that can be called on instances.

Inheritance is implemented by making the parent class a field in the struct of the subclass. Constructor of the subclass calls the base classes constructor for the field's initiation.

Of course there's an essential part of the puzzle missing which is compile time type checking. No need to go there now.

Under this light, is a Java class really a combination or an abstraction?
I have to say that it's a combination of a combination and an abstraction at the same time.

Let's compare it to a regular struct. A struct is a simple combination of data. You may pass a reference to a struct to an algorithm.

To sum up: The answer is most probably "a little bit of both", then my question is: How valid is the above 3 point categorization?
I find this meddled type of thinking extremely wrong. To understand thing in light of another theory, you have to see in what ways you can express one concept interms of the other. I believe it very easy to express "classes" in terms of combination of data and abstraction of contracts that can be passed to methods calls. What is there really other than that into classes?

Here's why I think your view is a little narrow: C#, Java, C++ and Haskell are all statically typed. It's not uncommon for static typing to reduce the problem to a simple type check.

Although it's a big deal to productivity and gets really into the aesthetics and art of the programming, the static/dynamic debate doesn't have to do anything with combination/abstraction or lack thereof. They're both equally under the same light. That's probably why it's possible to implement dynamic typing so easily into a statically checked language. What are dynamic objects but hash objects? Check the implementations, they really are just hash maps. In that sense, there's no dynamic program that can't be easily implemented as a statically typed program (a bad one at it though). More so, it's very hard to program in dynamic languages with an inherent sense of types even though it's not statically checked. The contract in dynamic languages becomes specific to each method signature in each object.

===
May need review, lots of last second editting