## Abstraction Tiers of Notations

DZone has published 3 my articles:

Few key points from them:

• Abstractions are not created equal and they could be sorted by tiers depending on structural elements they use and the way these elements are used.
• The tiers are closely tied to cognitive development stages as described by J. Piaget and M.L. Commons.
• Each new tier of the abstractions is built upon constructs of the previous tier.
• Adoption of new tier causes major generation of the general-purpose programming language to appear.
• Basing on the model, the next generation of general-purpose programming languages will be likely System-Oriented Programming. That will use ‘system’ as a new category of type that could be instantiated. Current dependency injection frameworks are early and incomplete attempts to implement this new abstraction.
• Basing on the model, the evolution of the database languages should be parallel to the evolution of general-purpose programming languages, with the same abstraction tiers adopted.

Note, I’ve described some elements of this model in some discussions on LtU previously.

## Comment viewing options

### Labeled bigraphs, SUO-KIF, do they qualify ?

At first reading i could not even imagine what a system type would look like. But, after a second thinking i remembered that J. Sowa acknowledged that conceptual graphs could be based upon bigraphs. Bigraphs are nestable components connected via interfaces/contracts. So the first candidate i could find is labeled bigraphs. And admittedly i can not name anything else that qualifies. If you are disturbed by diagrams and strongly prefer text then may be you could also consider Knowledge Representation Languages like SUO-KIF.

### Conceptual Graphs and BiGraphs

I've actually worked with conceptual graphs/KIF before in the context of BSc. The conceptual graphs are alternative notation to first-order logic. So, it is a 4th tier notation.

BiGraphs looks more promising. Interface/contract is clearly the tier 4 concept (black boxes). Hierarchy of contexts is the tier 3 concept. However, there seems to be some logic over links as well and local-to-graph labels, so it might be the tier 5 concept after all. I'm still looking through it.

The system concept introduces an induction principle over components, links, and environment in the system. For example, spring context startup and shutdown operations are results of application of this induction principle, they are projection of the graph structure. In most IDEs or other plugin-based applications, window menu is a reflection of the components specified in the plugin descriptors (system definitions). So, system provides multiple filtered mappings/inductions from labeled graph of components. And labels are system-local rather than component-local, the separation between environment and component is one of key points for the systems.

Generally, the concepts of the higher tier should be compliable to the lower tier concepts with formal proof of equivalence, however the reverse process should be more heuristic rather than formal, like guessing C program structure from assembly code. So, BiGraphs need to be further examined if they are actually the tier 5 structure or it is something that could be a target for compilation from the tier 2 structure. Like Java class or lambdas could be compiled to function pointers and structures, but they are separate entities that built up simpler structures.

it was misplaced

### Black Boxes and Hierarchies

Are Black Boxes a tier above heirachies? I don't think Black Boxes depend on hierarchies in any way. You can have a language with type-classes and datatypes. Datatypes don't seem to qualify even as objects in your classification as they don't have methods.

Stepanov's definition of an object is a block of data with an address and an extent, this seems a more general classification, and one up in abstraction level from basic CPU hardware types (int/float/char etc). We could call this a 'record' where the fields are hardware types to distinguish from your definition of object.

I am not sure about patterns either. You can have a pattern of black boxes, so to me patterns may well be a semantic level of abstraction above objects.

So we can have a language of type-classes and records that uses only tier 4 and tier 0.5 (inserting records between chaos and objects).

I would go with something more like this:

0 chaos
1 records
2 type-classes

OR

0 chaos
1 objects
2 concepts

Concepts (see Stepanov's "Elements of Programming") are 'types' for templates, and are sematics very similar to type-classes.

Type-classes and Concepts remove the need for informal "design patterns" as these structures can be represented in the language itself.

Hierarchies don't really seem to fit into this abstraction framework as they are not necessary for type-classes/concepts, and would be subsumed by then (they are just an example of one "pattern" of object arrangement).

### Re: Black Boxes and Hierarchies

The term objects is overloaded in computer science. In the name of the tiers it is ontological object rather than object-oriented object. Possibly better name for the tier would be "single opaque entities" or something like this. This is quite close to Stepanov's definition.

The record that references primitive types is pure pattern concept (tier 2). The record that directly references other record in addition is the hierarchy concept (tier 3). This is a key difference. This is why SQL databases are the tier 2 (other records are referenced only indirectly via matching keys) and Graph and OO databases are the tier 3 (other records are referenced directly).

Black block concept requires to have records that reference something by contract. But in the first place they require a reference, which is tier 3 concept. The difference is that we reference not the concrete type like in the tier 3 types, but interface type (existential type). Another example are generics, where we could write a collection type that interprets parameter type as black box with the fixed contract.

To sum it up, we could see the following type constructors:

1. Objects = object of primitive type
2. Patterns = flat map from names (or integers in case of arrays, which are also a kind of names) to primitive types (FORTRAN 66)
3. Hierarchies = map from names to other records of concrete type (C, Pascal)
4. Black boxes = map from names to contacts and statements that record implements a contract (C++, Java, C#)

Note: generally, most generic structures can emulate more simple structures, but on other hand, more general structures are compiled to simpler structures to actually execute. This is a false equivalence, as both mappings are partial and its cyclic application gernally does not have a fixed point. When we take most generics concepts as foundation we would miss actual peformance characteristics of the lower tier entities.

### Hierarchies

So you don't mean OO style inheritance hierarchies? Perhaps this needs to be made clearer as I am sure it is the first thing I think of regarding hierarchies.

Having read your comment above it seems more like you are taking about trees and other recursive data structures. Things you would write in Haskell like:

data Tree a = Branch (Tree a) | Leaf a


However although the notation is denser (and the reference is not explicitly mentioned) is this really a more powerful abstraction than:

struct Branch {
union Tree left;
union Tree right;
}
struct Leaf {
int value;
}
union Tree {
struct Branch branch;
struct Leaf leaf;
}


Actually I think it is, but not because of the hiding of the pointer, but because you can abstract the type parameter of the leaf value in Haskell. So for me parametric types are what increases the abstractive power of Haskell, and this can be realised in C++ using templates:

template <typename T> struct Branch {
union Tree<T> left;
union Tree<T> right;
}
template <typename T> struct Leaf {
T value;
}
template <typename T> union Tree {
struct Branch<T> branch;
struct Leaf<T> leaf;
}


Perhaps because you cannot have objects without an address (and extent) the "hierarchies" (if I am now understanding you correctly) are overlooked because "pointer" is a fundamental primitive type in almost all computer systems. Perhaps you can be imagine a system without references/pointers, and this might be interesting mathematically, but from a pragmatic point of view is not something you are ever going to encounter?

If I have understood correctly, then we have primitive types on tier one, simple records and arrays on tier two that cannot reference other records (and require joining as in relational algebra), we have constructions of objects (things like trees and other multi object data structures) on tier three, and abstract data types like modules, or type-classes (API contracts) on tier four.

How would parametric types and templates fit into this hierarchy, as they clearly advance abstractive power?

### Pointers are quite high level

Perhaps because you cannot have objects without an address (and extent) the "hierarchies" (if I am now understanding you correctly) are overlooked because "pointer" is a fundamental primitive type in almost all computer systems. Perhaps you can be imagine a system without references/pointers, and this might be interesting mathematically, but from a pragmatic point of view is not something you are ever going to encounter?

The high-level languages without pointers do exist, but they mostly obsolete. The possibly purest such language is classical BASIC, which is a canonical example of the tier 2 language as it was intended for teaching. This language did not support hierarchies at all. There is no block code structure, there are no pointers, there are no data structures (only arrays of primitives and global variables). FORTRAN 66 did no had pointers as well as far as I remember. Assembler languages also do not have pointers as such, they have integers and indirect access operators. The pointer type has been formally defined in 1964. I wonder how LISP got away without defining a pointer/reference type formally until that. The canonical tier 3 language intended for teaching is Pascal, and there are blocks, data structures, and pointers.

I understand that it is hard to imagine in 2019, but such things did exist. I even written some programs in BASIC in the school. In University we have used C and Pascal mostly, and FORTRAN for some linear algebra tasks. Understanding pointers and recursion is actually a major enlightenment on the path of programming. Lather vesions of BASIC were converted to the tier 3 langauge too.

If I have understood correctly, then we have primitive types on tier one, simple records and arrays on tier two that cannot reference other records (and require joining as in relational algebra), we have constructions of objects (things like trees and other multi object data structures) on tier three, and abstract data types like modules, or type-classes (API contracts) on tier four.

This is more or less true, just to clarify, on the tier 3 we have white box structures like C structs/unions. This is also a data dimension. On the code structure dimension, we have the same: tier 1 – pressing buttons on device, Tier 2 – sequences, go to, Tier 3 – block structure and procedures, Tier 4 – lambdas, virtual methods, interface calls.

Generally, in any case where something grows quantitively and human brain has to understand and manage it there is the same sequence of adopting abstraction tiers. For example, for organizational structure: the tier 1 – individual, the tier 2 – flat organizations (or teams within organization), the tier 3 – hierarchical organizations with white box structure (Army, Church, medium business), the tier 4 – big corporations that consists from mostly autonomous business units (Sony, IBM, etc.). Government concepts are the same: the tier 2 – flat tribes, the tier 3 – monarchy, the tier 4 – separation of powers.

How would parametric types and templates fit into this hierarchy, as they clearly advance abstractive power?

The functional languages have somewhat problematic type system. The parametric types are the tier 4 type constructors, because we define type w/o knowing the actual parameter type (so here comes black box concept).

However, the algebraic data types are the tier 3 concept, because the union is closed and we know what data could happen here. This is actually a problem because of it. For example, if we define AST using ADT, then to add new type of node we have to modify original definition, so we could not extend structure in a plugin. Contrast it with Java or other OO languages, where we have AST node interface, and plugins could provide another implementation of that interface. I think the lack of open unions is major problem in Haskell that greatly reduces dynamic extensibility of Haskell applications, I heard that there was an effort on fixing it, but its current status is unknown to me.

### Re: Hierarchies and Pointers

I think there's a significant conceptual difference between "hierarchical objects" (like branches of a tree, rooms of a building, or paragraphs of a document) and "referenced objects" (via pointers, URLs, room numbers, or content-addressing by interning or secure hash).

A 'Tree' would usually be implemented via pointers because that's efficient. But we could imagine less-efficient implementations involving deep copies. The important bit is that, without references at the abstraction layer, there is no logical aliasing, no cyclic dependencies, etc.

Via fixpoint combinators, we don't need references even for general recursion. Not even implicit namespace refs. Black boxes - such as existential type values - also don't strongly imply references. Only "shared state" seems to truly need references as a concept.

Of course, any sufficiently powerful computation system can model references (e.g. integers addressing a key-value trie that represents the state of our address space).

I'm hesitant to consider "pointer" a "fundamental primitive" of most theoretical computation models or systems. OTOH, pointers are fundamental to most physical computation models, so come up a lot when compiling.

### Pointers/references are fundamental for the tier 3 and above

I think there's a significant conceptual difference between "hierarchical objects" (like branches of a tree, rooms of a building, or paragraphs of a document) and "referenced objects" (via pointers, URLs, room numbers, or content-addressing by interning or secure hash).

The basic idea of hierarchy is replacing a part of the pattern with its representative. The representative is a pointer in general case. If we look at real-word hierarchies on which our brain is trained, we do not copy people or subdivisions when we are working with them. The same is with black boxes, but they add another level of indrection via contracts. We refer to mutable objects via labels/names and these names are local to teams. For example, a team lead is a local reference within team to the specific person. When we want to give it order or bonus, we do not expect the person to replicate on the spot and safely work with copy.

A 'Tree' would usually be implemented via pointers because that's efficient. But we could imagine less-efficient implementations involving deep copies. The important bit is that, without references at the abstraction layer, there is no logical aliasing, no cyclic dependencies, etc.

Note that in this case we still have a name dereferencing. The important thing is that on the level of the parent object, the part of the content is packaged into separate entity and that entity is referenced by representative. On the previous tier name could refer to primitive values. This is a fundamental cognitive operation used by the tier 3 constructs.
Note, pointers to primitives are no exception as they are just referencing to anonymous structure that contains a single primitive value.

So, it is just a pointer that resolves to embedded/collocated object, it would be just a memory access optimization. IMHO it is even not possible to create acyclic graph w/o pointers. Only tree is possible.

Also, if we have to support unknown depth structures, we could not use field offset, we have to use pointers internally to store locations of embedded objects.

Possibly better name could be used instead of “hierarchies”, but I have not figured one. J. Piaget’s version “concrete operations” is too abstract and it does bring any pictures to mind. One has to grind through the text to understand what he meant. “Hierarchies” is more visual, but apparently causes confusion as well as strict tree hierarchies w/o horizontal connections are imagined.

Via fixpoint combinators, we don't need references even for general recursion. Not even implicit namespace refs. Black boxes - such as existential type values - also don't strongly imply references.

In case of black boxes, we generally do not know what we are referencing by the name. Fixpoint operation creates a structure of the unknown memory size and unknown internal structure. I also have a trouble of imagining how it could be implemented without pointers.

Also, all attempts (known to me) at the languages with purely immutable structures were at the tier 4. This hints that black boxes are the minimum tier for hiding shared state. With white boxes at the tier 3, the shared state would have been exposed.

Only "shared state" seems to truly need references as a concept.

The languages w/o shared state are currently an exception. And I think there is a reason for it. While there are easy to reason about non-changing state within these languages, it is more difficult to reason about evolving state in these languages as state change happens in them globally (we need to replace not only one object, but also all referrers to it, so they will refer to new version of state), rather than locally. So, I think that shared state is a fundamental, and immutable state is a restricted case that is easier for reasoning in some cases. Attempts to reduce mutable to immutable were mostly unsuccessful as emulation of mutable over immutable creates higher cognitive load than saved by reasoning about immutable state later.

Newer languages like Scala and Kotlin support immutable and mutable structures. Even Haskell has two sublanguages, one is purely functional language. Other is IO-monad-based DSL that look just like typical off-shelf imperative language with few quirks.

Of course, any sufficiently powerful computation system can model references (e.g. integers addressing a key-value trie that represents the state of our address space).

I'm hesitant to consider "pointer" a "fundamental primitive" of most theoretical computation models or systems. OTOH, pointers are fundamental to most physical computation models, so come up a lot when compiling.

Idea of the pointer that we resolve a name to the group values (or to location of single value as a trivial case). This is a fundamental cognitive operation. And programming language design follows cognitive operation structure. For computers, it would have been simpler if we just entered machine code. All these programming languages were created so we could reason about all these actions in reasonable way. And the higher abstraction tier, the larger number of elements that could be reasoned about. This is a generic human way to deal with complexity.

So, I think that the pointers/references are fundamental for structures of the tier 3 and above.

### Directed Graphs

Hierarchies definitely mean tree-like structures, where objects can only exist at one point in the hierarchy. Hierarchies can be implemented only using containment, and can be represented as a string using parenthesis as in "top(left(bottom1, bottom2), right(bottom3))" no pointers necessary.

It seems to me you mean "Graphs" or "Directed Graphs", which can be DAGs (directed acyclic graphs) or just directed graphs in the case where cycles are permitted.

### Hierarchies are on the code level

The tier 3 is named 'hierarchy' because hierarchy is the key complexity management tool enabled by this tier. Hierarchy concept leak everywhere as it is highest level complexity management tool available there.

The pointer path a->b->c->d in C assumes local hierarchical view of the world in the term of accessibility tree from the current stack frame. Such memory model supports non-hierarchical data structures, but they worked with using hierarchical projections. Call tree is a strict hierarchy (unless we play with longjump or other funny things).

The problem usually starts when the tier 3 languages work with constructs that are not strictly hierarchical. For example, there almost always an implicit global hierarchy of memory objects in C program in the form of 'owning' pointers. The biggest problem when programming in C is separating these two kinds of pointers. This is because from the pointer syntax the both kinds look the same and local hierarchical projection does not match global ownership structure.

The most of the tier 4 languages just skip this problem with some form of garbage collection as addition of black box constructs makes memory tracking almost impossible.

The situation is not unsimilar to using integers for memory access in the tier 2 languages. We have a complex linked structure in the mind, but we have to use flat namespace of integers to implement it. Here we have a complex graph, but we are using hierarchical projections of it work with it. It is better than flat namespace, but still causes problems.

### Directed Acyclic Graph

I think I would prefer the term Directed Acyclic Graph for this then.

### Turing Machines

Pointers seem fundamental to the physical implementation of computation, even if not required for abstract computation. I started programming in BASIC on a Commodore-64, so I am familiar with using arrays as the sole complex data structure, with indexes being used as a pointer into parallel arrays (as without structs you needed one array for each "object" property). If you treat each set of parallel arrays as an object-pool for a particular type of object, then you can program as if there were pointers, but I agree it seems a less powerful abstraction.

The point I was making about them being fundamental was that I could not easily imagine a way to make a working physical general purpose computer without pointers. Even a Turing machine has the tape pointer you can manipulate.

### Re: Turing Machines

AFAIR, Turing Machine did not use term pointer. It use term 'head' (like in the tape recoder) rather than poiner.

Fundamental is indexed memory access operation (TM head supported shift left/shift right operations over tape). Machine code does not has types and it just uses number in registers an memory. Most of modern CPU have an IP (instruction pointer) register, but this is just integer. The tier 2 languages retricted access to the memory to some restricted areas using arrays and usually provided some escape hatches to access memory by address.

The pointer is a high level costruct that restrict such number usage to indexed memory acces and specifies what we can expect at the location. The invention was that such thing is actually typed.

In the version of BASIC that I used, there were no poiner type and number could have been used for indxed memory access using some read/write memory functions (I do not remember their names already, it was used mostly for graphics). If language does not have a pointer type, a programmer has to remember meaning of the number and how to work with memory at that address in the mind.

### Pointers or References

Yes a Turing Machine does not explicitly use the term pointer, but it is a pointer. I would use the term 'Pointer' for the kind of things in a CPU, after all we have 'InstructionPointer' and 'StackPointer' being well used in the literature.

What you refer to is what I would call a 'Reference' something that is type safe, and you cannot do address arithmetic on it. 'C' has pointers not references (you can treat them as integers and do arithmetic on them), a reference is more like an Ada access variable.

### Re: Pointers or References

It is a pointer in the mind rather than pointer in the program. Turing machine language does not have a concept of pointer at all. It has concept of the code state and of the current head position. CPU do not have types. They only work with numbers. And some numbers are interpreted as addresses in memory by some instructions. This is a radical difference.

The generational changes in the languages happens when you start writing something new, rather than when you start thinking something new. Usually, the programming community start thinking something new long before than it is supported by programming languages.

The programmer compiles the pointer concept to these low-level concepts when working with assembly language.

Also, for instruction pointer, I do know when this term has appeared. Instruction pointer is one of synonyms for program counter. At the time of appearance of x86, the pointer concept was long known history, so it might be just explanation of lower-level concept via high-level.

Stack register is also a quite recent history. It appeared in late 60s with appearance of the tier 3 languages that supported general recursion. The stack concept appeared early, but still after first generation, so it is useful, but not essential. Even now, some RISC CPUs have stack register assigned by convention rather than in hardware.

I guess to understand whether the concept of pointer is fundamental we need to delve into works before 1964. I personally doubt that we will find wide usage of the term.

Also, generally speaking, the reference is more generic concept than pointer. It includes pointers and other ways to reference things (for example, by key in relational algebra as reflected in the concept of referential constraint). Another example is C++ reference, which is just another syntax for pointer, and with the same integrity problems.

### CPU do not have types. The

CPU do not have types.

The floating point and word registers are distinct CPU types. You can't pass a floating point register to an addressing instruction, for instance.

removed

### CPU do not have types, instructions make assumptions about data

From Intel's manual:

The fundamental data types are bytes, words, doublewords, quadwords, and double quadwords (see Figure 4-1).
A byte is eight bits, a word is 2 bytes (16 bits), a doubleword is 4 bytes (32 bits), a quadword is 8 bytes (64 bits),
and a double quadword is 16 bytes (128 bits). A subset of the IA-32 architecture instructions operates on these
fundamental data types without any additional operand typing.

So only difference between fundamental CPU datatypes is operand size. These bytes do not have intristic properties on CPU level. Different instructions just place different restrictions on acceptable byte structure. But such interpretation happens only in the context of the instruction. There is no any cross-intruction verification.

Also SSEx and x87 registers could hold both integers and floats (FI* instructions).

It is possible execute FP instruction on SSE register and than to work with result as with integer and move it to main CPU register and than to use it as an address.

For addressing on x86 architecture also not all main registers could be used for all roles. For example, AMD64 R8-R15 could not be used as well. They have to be moved to other registers. x86 as CISC architecture has many funny restrictions on instruction operands, and making some type system ideas about them is a bit naive. This is one of the reasons why LLVM is so popular for compiler writing recently. LLVM provides much simpler and uniform instruction set and hides these inconsistencies.

### Re pointers fundamental to physical computation

I disagree. We have plenty of examples of computation with slime molds, soldier crabs, dominos, and bees that don't involve pointers. It's feasible to develop compute hardware for digital or analog signal processing that doesn't use pointers. The Babbage machines don't use pointers. There's a whole field related to DNA computing and molecular programming, which doesn't involve addressable memory. Etc.

But pointers are fundamental to "addressable" memory models. It's essentially right there in the name. I don't forsee us breaking away from those any time soon, except for specialized use cases.

Even a Turing machine has the tape pointer you can manipulate.

In my understanding, pointers are first-class values that we use to index an external resource. A Turing machine's 'head' is certainly not first-class, clearly not a value, doesn't index a tape so much move along it, and no, you cannot manipulate it - it moves only by the machine's own rules.

In any case, if your definition of "pointer" is too broad and vague, you aren't saying anything useful when you claim it fundamental.

### These platforms are too low-level

I disagree. We have plenty of examples of computation with slime molds, soldier crabs, dominos, and bees that don't involve pointers. It's feasible to develop compute hardware for digital or analog signal processing that doesn't use pointers.

Strictly speaking, transistors do not have pointers either, but high-level languages defined for computers built with transistors do have pointers. Let's discuss the issue when high level programming languages over these computing platforms will appear. Something tells me that there will pointers for sufficiently high tier programming languages just because pointers are useful complexity management tool used by humans. Honestly, I'm not that impressed by bees as computing platform, as I do not understand how to add numbers using them, not speaking of more complex tasks like high-frequency trading or building online forum.

### Fundamental means it's part

Fundamental means it's part of the base, the foundation. It's exactly the essential "low level" things that are fundamental. Anything we build above the foundation is, by definition, not fundamental.

Physical computation doesn't build upon pointers. We might build pointers and addressable memory upon other physical computation primitives. Pointers are a high level construct in terms of physical computation. Therefore, pointers aren't fundamental to physical computation.

Whether pointers/references are fundamental to a language depends mostly on whether they're provided as a primitive (like in C or Java) or a library (like IORef or TVar in Haskell). So deferring discussion until "high level programming languages over these computing platforms will appear" isn't especially conducive to understanding the platform itself.

### Fundamental is relative

The question is where to stop when seeking foundation and what logical layer we are discussing. For transistors, the foundation is atoms and electron movements. For atoms - elemental particles, for elemental particles quarks or whatever physicists fashion now.

If we stay within logical scope of the tier 3 programming languages (ALGOL, C, Pascal, etc.) - then pointers are fundamental. If we consider wide context of programming languages, the pointers are compiled to address arithmetic when we convert the tier 3 representation to the tier 2 representation. The tier 4 OOP and FP programming languages using pointers and references as well. So, whether pointers are fundamental or not depending on the context. Consideration of bees widens context too much IMHO.

The modern software development happens in the context of von Neuman architecture and its derivatives. Running out this in the context of programming language discussion is possible, but without languages or compilers it does not make much sense. The only viable alternative to this architecture are analog computers, that are practically dead except for few niche applications.

While lambda calculus is useful for proving theorems about foundations of computing due it its high level, it is actually too high level to be considered as foundation model of computing. von Neumann found a good place for the boundary between software and hardware and we are still using it.

### re fundamental is relative

I agree that what is "fundamental" is relative to our subject. Like, in martial arts, the "fundamentals" are the basic movements. In a programming language, the "fundamentals" are the built-in features and the syntax surrounding them. For physical computation, I'm not sure what the "fundamentals" are, but I'm certain it's well below the level of 'pointers'. Likely candidates are space, matter, and motion.

modern software development happens in the context of von Neuman architecture and its derivatives

I agree. I'd also agree that addressable memory and pointers are fundamental to von Neumann architecture.

If we stay within logical scope of the tier 3 programming languages (ALGOL, C, Pascal, etc.) - then pointers are fundamental.

Modulo safety and philosophy, ALGOL, C, and Pascal are pretty much the same language - imperative structured programming. You cannot effectively generalize to other tier 3 languages if this is your sample set.

Consider VHDL, SAFL, circuit diagrams, various box-and-wire languages. Some of these may involve static memory, and the "compiler" might produce instructions for printing a circuit board. Whether they interface with or utilize addressable memory units internally could be optional, rather than fundamental.

Consideration of bees widens context too much IMHO.

IMHO, your PL horizon is limited, and this has led you to some premature generalizations.

While lambda calculus is useful for proving theorems about foundations of computing due it its high level, it is actually too high level to be considered as foundation model of computing.

Lambda calculus by itself is relatively low-level. For example, you won't even have natural numbers and lists without a Church or Mogensen-Scott encoding thereof. But it's also general, Turing powerful, so we can indeed encode those things. That said, I favor a combinatory logic because it elides those pesky variables and sophisticated substitution semantics, and is thus even lower level.

In any case, I don't feel like arguing about what makes a "good" foundation model of computing. But I can already tell we'd disagree, and that our priorities would be different.

### FPGA challenge

There are plenty of free tools out there that can be used to program FPGAs. My challenge would be to design a general purpose stored program computer that does not have pointer registers of any kind. I am not aware of any, this supports the position that pointers are fundamental to a "stored program general purpose computer". If you can't find a literature reference, and cannot design one yourself, then I don't see any realistic challenge to the statement that pointers are fundamental to stored program general purpose computers.

### My challenge would be to

My challenge would be to design a general purpose stored program computer that does not have pointer registers of any kind. (...) pointers are fundamental to a "stored program general purpose computer"

A pointer must be a first-class value within the program. So I don't believe that the second-class 'stack pointer' or 'instruction pointer' at the CPU generally qualify as pointers. They would if our language provides means to store and set them. But not generally.

You have a broad and vague definition of pointers that even includes Turing machine 'heads'.

But by my definition of pointers - which I consider vastly superior to yours - the challenge isn't difficult. Even using an existing CPU to repeatedly evaluate a stored, Turing complete, cellular automaton or simulate a Turing machine with the memory as tape, would be sufficient.

We could feasibly create a dedicated processor that does the same, or even a memory-chip that automatically computes a cellular automata (all cells at once).

So here's the challenge for you: explain your 'definition' of pointer and convince me it's better than mine.

### Pointers

A pointer is something that 'points to' something else. A tape head clearly points to a position on the tape, which is the current location. With tape we can only increment and decrement the location (no random access), but we have already established that it is not necessary to be able to do full integer arithmetic on a pointer.

Any computer that has memory addressing will by definition have pointers, even if that is just the program counter in the CPU.

So to have a computer without any pointers would require not having a stored program in sequential memory locations. How could we have a general purpose stored program computer without memory addresses? (Referring back, I do not contact consider DNA or slime to be general purpose - they can solve constraint problems and equations, but you can't play Quake on them).

Here is an example project implementing SKI combinators on an FPGA. It is of note that because the state is of variable length, the only option is to store it in RAM and access via a memory bus, which results in having to use memory pointers instead of values. It seems to me that any attempt at actually _implement_ a combinator system in physical reality would necessarily need pointers.

### Re pointers

In every language with pointers I've used, a pointer is a first-class value. We can keep pointers in data structures, pass them as arguments, return them from expressions.

So, unless we can do all these things, via machine-code accepted by the CPU, then it doesn't qualify as a pointer. Not even if it's a program counter.

Thus, to answer the question about whether pointers are needed for stored program computing, it's sufficient to ask whether we can craft a usable 'machine code' cannot directly use addressing.

I believe we can. Turing machine is a simplistic example.

I think your definition of 'pointer' is invalid, because it includes second-class things that do not behave as the prototypical C pointers.

### Internal Pointers

My point is that you need pointers to implement a CPU. If you read a stored program from memory you must have a memory address to read from. This is what I mean when I say fundamental: you cannot build a CPU without the concept of a pointer. I am not talking about the language built on top of that. It is obvious that we can have a CPU that interprets lambda calculus as its machine code, so you we don't need to have that discussion.

Of course a CPU register that stores an address is a pointer. Even if it is not accessable to the programmer it still exists, it is fundamental because without it there is no CPU.

That is why the challenge was to design a CPU that can be implemented on an FPGA that does not use pointers in its construction. The machine code exposed to the programmer is irrelevant because this is already an interpreted language implemented on the CPU, so it could indeed be SKI combinators (see example I linked above).

I am not saying pointers are fundamental to programming, again the existence of lambda calculus is enough to dismiss that as reasonable. We clearly can have many programming languages without pointers, and yet to provide a computing platform that can execute/evaluate those languages we need pointers. Having a pointer less machine code is simply building an interpreter into the CPU, and yet the CPU itself will need address registers.

There are some architectures, like data-flow, that can exist as stream processing nodes that you arrange as a graph, however the limited number of processing nodes, and the problems of routing data mean that these are not general purpose.

My whole point was you have all these layers of abstraction, but in the bottom one, the actual CPU itself, the hardware, you need pointers. That is what makes them fundamental, foundational even.

### re internal pointers

A pointer is a language construct. It's part of a language such as C or x86. A pointer is a first class value within the language. We can store it in data structures, return it from computations, etc. If we can't do these things, it is not a pointer. Full stop.

I'm not happy with this "internal pointers" name. I think it's misleading. But I can't offer a catchy alternative right now, so I can go with it.

Your claim is that we minimally need internal pointers for a CPU to operate on a stored program computer.

I will reject this claim on two different levels.

First, I reject that a CPU is essential to Turing complete computation with a stored program. As I mentioned in passing before, we can move computation into the memory itself. E.g. on every clock tick, every cell of memory could rewrite according to its own state and that of certain wired-in neighbors. Cellular automata already demonstrate that such computation is easily Turing powerful. We could develop a language around such a CPU. (Probably awkward to use, but that's irrelevant.)

Second, I reject that a CPU needs to know "where it is" in memory. Without this knowledge, we instead have a CPU as a stream-processor (no jumps!). In each 'round' the CPU operates on the entire memory as a stream, and outputs a new memory stream. We could shuffle data between banks of memory in each round, performing simple, local rewrites in each step. Terminating when there is no change. Even with simple rewrite rules, this can easily be Turing powerful. It's also likely to be much more accessible to human programmers compared to the first option.

In these cases we do not need 'addressable' memory. Storing the program and processing it in full-memory rounds is sufficient. Essentially, what we lose without 'internal pointers' is only the ability to represent split attention on multiple parts of memory. Thus, without such pointers, behavior and data will be combined, and performance of computation that requires split attention (binary operators on unbounded-size data) may suffer.

This has some implications for efficiency, but also introduces implicit opportunities for parallelism and implicit codata. That opportunity should be obvious in the first case. In the second case, we could pipeline a stream across 100 simple processors for bigger steps. And we could operate on different regions of a stream if we either design for rewrites to be confluent or accept some non-determinism and leave confluence to the programmers.

Could be a nice alternative to what we use today.

Edit: I like the idea, so I'm now developing a streamable rewriting language for bounded-memory processors. Might blog it later.

### VDHL is not a counterexample

Consider VHDL, SAFL, circuit diagrams, various box-and-wire languages. Some of these may involve static memory, and the "compiler" might produce instructions for printing a circuit board. Whether they interface with or utilize addressable memory units internally could be optional, rather than fundamental.

I've just checked VHDL documentation. It is the tier 3 or higher language. And surprise, It also have pointer types in the form of access types (quote from IEEE Standard VHDL Language Reference Manual, 2000):

type ADDRESS is access MEMORY;
type BUFFER_PTR is access TEMP_BUFFER;

In second line they even use "_PTR" suffix. Or more extended example from that document:

type CELL; -- An incomplete type declaration.
type CELL is
record
VALUE : INTEGER;
end record CELL;


Addressable units are different, but they still present.

I'm too lazy to check other provided languages. If they are well developed the tier 3 languages, they will likely introduce the pointers in the some form as well.

If you wil find a well developed tier 3 language without pointers or similar constructs, we coud continue the discussion. As there there are a lot of languages, they could be not examined completely by a single person. So please come with a valid counterexample, rather than throwing the language names into the discussion arbitrarily.

I'm more interested in mature examples of the languages that had some time time to evolve basing on user feedback on the tier 3, than in the early versions that might have not yet gathered actual requirements of the domain.

### VHDL and other hardware

VHDL and other hardware description languages do support memory units (because why wouldn't they?) but it is a lot less fundamental.

I'm too lazy to check other provided languages. If they are well developed the tier 3 languages, they will likely introduce the pointers in the some form as well.

If you wil find a well developed tier 3 language without pointers or similar constructs, we coud continue the discussion.

No, you clearly just said you'd be too lazy to even look.

We can model references in any language of sufficient power, so to clarify: I'm not saying these languages cannot use refs/pointers, I'm saying their use is optional in these languages and we can still use them at tier 3 without using pointers.

### Where are counterexamples?

Hey! Lazy are you throwing in language names without checking them first. Why should I follow that game?

I provided counterexample to your conterexample. You have listed a list of languages that supposedly do not use pointers. I looked at the first referenced language, and VHDL has pointers. Your statement is invalidated. Period.

It is now your turn to provide a well developed tier 3 langauge that does not have pointers or similar costructs that reference group of objects by name relative to some context.

It is possible design such language, but will people use it if not forced?

Pointers are optinal in C too. It is possible to write:

int main() {
return 1;
}


There is no pointers in this porgram. And 'false' UNIX program is impelemnted just like that.

It is also possible not to use lambdas with programming on Common Lisp, build it macros provide enough flexibility to code in a procedural style.

The point is that VHDL has introduced pointers during its evolution. And they were introduced as a complexity management tool. It is possible to not to use them, but it is possible not to use other features as well. So what?

### I provided counterexample to

I provided counterexample to your conterexample.

I did know that VHDL can work with memory and pointers before you mentioned it. I just don't consider that relevant. What is relevant is that VHDL can represent sophisticated computations without pointers, then compile to hardware that also doesn't use pointers.

You say pointers are 'optional' in C. But to my knowledge, even the simplest compiled C uses pointers.

The point is that VHDL has introduced pointers during its evolution. (...)

The question was never "are pointers useful?" It's "are pointers *necessary* for tier 3 notations (either within the language or their implementations)?" Thus, correctly pointing out that they're useful and popular is simply irrelevant. Popularity and utility simply aren't necessary features to qualify as a tier 3 notation.

### The key abstraction of the

The key abstraction of the tier 2 is map from names/numbers to elemental entity in the context of notation. The things are connected on the same structural level. This map with horizonal structures is named pattern in the articles. Elemental entity is with relative to notation, for example for KPN a node in the graph is an elemental entity because it does not decompose further.

The key abstraction of the tier 3 is refrencing another pattern of objects by name/position instead of elemental entity. This apply to both data and behaviour.

Procedures/functions/blocks are reflections of this cogntive operations in the behaviour aspect. Records/pointers are reflection of this cognitive operation in the data aspect.

VHDL also has two ways to do it: pointers and proceduers/blocks. Block is embedded behaviour reference, procedure is reference by name, the behavior elements are named by ther index position within block or labels.

### projections vs pointers in hierarchies

I find the Unison Web project interesting in this context. The 'names' used to refer to other functions at program layer are secure hashes, ensuring 'containment' semantics. But Unison Web leverages projectional editing to provide a human-friendly veneer, rendering those secure hashes according to user-specific database of names. Arguably, we could do similarly with structured subprograms, perhaps rendering (λx.x) as I and (λf.(λx.f (x x))(λx.(f (x x)))) as Y and (λx.λy.λz.(x z (y z))) as S.

Due to such possibilities, I feel that "names" should not necessarily be considered "pointers" or "references". Because they might instead be "projections".

Even ignoring projectional editing, I think it's reasonable to consider names to represent a compressed 'containment' relationship, so long as names aren't used in ways that can only be explained via references/pointers (such as naming shared state, certain recursion schema, goto label variables, etc.).

The basic idea of hierarchy is replacing a part of the pattern with its representative.

Patterns describe and organize objects. Hierarchies describe and organize patterns. Building bottom-up seems to fit the idea of patterns as 'projections' better than it does patterns as 'blueprints'. Whether we replace the representative by the pattern or the pattern by the representative seems independent of your tiers of abstraction.

The important thing is that on the level of the parent object, the part of the content is packaged into separate entity and that entity is referenced by representative.

So you agree it depends on how the 'objects' are represented. But you seem to be considering a specific way to represent them (as "separate" entities). Your own article uses "by containment or by reference" when describing hierarchies. Why not attend to that intriguing "by containment" option?

IMHO it is even not possible to create acyclic graph w/o pointers. Only tree is possible.

Depends on what you mean by "create a graph".

Via adjacency matrix, I can represent cyclic graphs. Via fixpoint computations, I can model general recursive computation. If I have both fixpoints and limited support for call-by-need computation, I can support infinite, loopy co-data structures. We can construct Kahn Process Networks in terms of second-class process and port identifiers, and these KPNs would support cyclic streaming computations.

You could serialize these graph-like objects (including some code) using a simple string without internal anchors or offsets.

Thoughts: Shared state doesn't require references. There are lots of ways to share state that don't involve aliasing it. Such as scheduling a bunch of State -> State threads over a shared State value. Immutable objects don't require references. We can deep-copy our values instead of optimizing memory representation via references.

It's only a specific approach to shared state through references - aka aliased state - that strongly implies use of references. And that's obviously because references/pointers are assumed in the definition of 'aliasing'. Whether aliasing is somehow fundamental to physical computation is a separate question.

if we have to support unknown depth structures, we could not use field offset, we have to use pointers internally to store locations of embedded objects

Not really. You could use a string of variable size to represent an arbitrary tree, no need for offsets or pointers. But it wouldn't be efficient to manipulate a tree via this representation. Hence, the "A 'Tree' would usually be implemented via pointers because that's efficient" assertion I made earlier.

Fixpoint operation creates a structure of the unknown memory size and unknown internal structure. I also have a trouble of imagining how it could be implemented without pointers.

It isn't difficult. Start with SK combinators. Develop a small-step string-to-string evaluator. The S combinator has behavior Sxyz == xz(yz). Whenever this is applied, literally copy the z substring twice into the result. Next, implement fixpoint and some toy recursive functions via SK combinators, then run it via your evaluator. It won't be efficient. But it's not difficult.

all attempts (known to me) at the languages with purely immutable structures were at the tier 4

I suggest you look into cellular automata and term rewrite systems. :D

This hints that black boxes are the minimum tier for hiding shared state.

Do you know about opaque data types vs abstract data types? Opaque data types are essentially the second-class form of abstract data types. Opaque data types are sufficient to hide shared state, and the API over the opaque type represents a contract. But opaque types don't give us any ability to abstract over multiple implementations of this contract, so I feel they fall a bit short of tier 4.

languages w/o shared state are currently an exception

Sure. Better to test a general classification against all the edge cases, tho. Including pure languages, tacit languages, concatenative languages, combinatorial logic, term or graph rewrite systems, Kahn process networks, cellular automata, multi-agent systems, ant-based computing, Unison Web where secure hashes serve as compressed containment of large subprograms, etc..

I think that shared state is a fundamental

Shared state is essential to some problem domains. We're all living on the same ball of mutable state, after all. Applications developed in a programming language will ultimately need to interact with a shared network and shared databases. But a point worth considering is that all essential shared state is, by nature, outside of the software application. So I wouldn't casually accept a claim that allocation of shared state should be fundamental to programming languages.

Idea of the pointer that we resolve a name to the group values

And the idea of image recognition, pattern recognition in general, and a related subset of projections, is that we resolve a group of values or observable pattern into a human-friendly name. :D

### Mental model vs code model

Firstly, let’s make a distinction: the model in the mind and the model in the code. These models sometimes match, sometimes are different. The abstraction tiers of these models can be different. The greater is the difference, the more transformations are needed to work with code. So, this increases cognitive load.

It is possible to write object-oriented program in C. C GUI toolkits are evidence of it. They are ugly, inconsistent, but they work. However, it is much easier to work with C++ or Java wrappers over these C GUI toolkits, because distance between the model in the mind and the model in the code is less. Therefore, less transformations in mind are required to achieve the goal. This cognitive overhead reduction is one of main reasons why the new generations of programming language are adopted.

… Arguably, we could do similarly with structured subprograms, perhaps rendering (λx.x) as I and (λf.(λx.f (x x))(λx.(f (x x)))) as Y and (λx.λy.λz.(x z (y z))) as S.
Due to such possibilities, I feel that "names" should not necessarily be considered "pointers" or "references". Because they might instead be "projections".

Patterns describe and organize objects. Hierarchies describe and organize patterns. Building bottom-up seems to fit the idea of patterns as 'projections' better than it does patterns as 'blueprints'. Whether we replace the representative by the pattern or the pattern by the representative seems independent of your tiers of abstraction.

You are starting at very high-level abstraction. The lambda calculus is the tier 4. While intention of the ‘pattern’ concept in my articles is of lower level. The pattern/template is flat set of labeled objects. The behavior template/pattern is set of labeled actions with transitions between them – recipe that have numbered/named steps and transitions between steps by name/order. The structural pattern is flat mapping to values. Like global variables in BASIC or FORTRAN 66, or global labels in Assembler.

The logic of pattern level is transduction, or by analogy. So, we match situation with pattern, take objects that matched holes in the pattern, and insert those objects into another pattern. The transition between the tier 2 and the tier 3 happens when we able to refer not only to simple values, but structures as well by name. So, code and data structure stop to be flat globally, but each node in this structure is still flat mapping from name to value or structure.

So you agree it depends on how the 'objects' are represented. But you seem to be considering a specific way to represent them (as "separate" entities). Your own article uses "by containment or by reference" when describing hierarchies. Why not attend to that intriguing "by containment" option?

I guess you are well aware that C++ and many other languages have option to reference object allocated separately or declare it as part of the object: “my_subobject test;” or “my_subobject* test;”.

Depends on what you mean by "create a graph".

Via adjacency matrix, I can represent cyclic graphs. Via fixpoint computations, I can model general recursive computation. If I have both fixpoints and limited support for call-by-need computation, I can support infinite, loopy co-data structures. We can construct Kahn Process Networks in terms of second-class process and port identifiers, and these KPNs would support cyclic streaming computations.

You could serialize these graph-like objects (including some code) using a simple string without internal anchors or offsets.

The ways you are specifying require additional steps between model in the mind and model in the code. The references in mutable objects are much more direct representation of the graph. Particularly if nodes are of different type and relationships have different semantics. Those matrix representations add cognitive load on the developer, as the developer has to maintain additional mappings between problem domain and the code. Java and C# just allow to write code with non-uniform objects and their relationships. When working with object graph, most of the logic is local to the node, and then it propagates to referenced nodes. Whole uniform graph processing (where marix representation shines) are very rare cases.

Thoughts: Shared state doesn't require references. There are lots of ways to share state that don't involve aliasing it. Such as scheduling a bunch of State -> State threads over a shared State value. Immutable objects don't require references. We can deep-copy our values instead of optimizing memory representation via references.

While shared state does not require references, as we could work in assembler with integer addresses, which provide us mapping from integer keys to values. However, references provide two things: type of content and named address of the content. And we could address shared content knowing what to expect. Those global maps of objects by ID is just a lower level of the abstraction.

Not really. You could use a string of variable size to represent an arbitrary tree, no need for offsets or pointers. But it wouldn't be efficient to manipulate a tree via this representation. Hence, the "A 'Tree' would usually be implemented via pointers because that's efficient" assertion I made earlier.

The point you are missing that when we are working with data structures in a programming language, the programming language provides us multiple services, like error checking, code exploration support, etc. We lose all these services with using string as primary data structure. I’ve written programs with TCL/Tk and it was real pain as strings were the only data type supported.

Fixpoint operation creates a structure of the unknown memory size and unknown internal structure. I also have a trouble of imagining how it could be implemented without pointers.

It isn't difficult. Start with SK combinators. Develop a small-step string-to-string evaluator. The S combinator has behavior Sxyz == xz(yz). Whenever this is applied, literally copy the z substring twice into the result. Next, implement fixpoint and some toy recursive functions via SK combinators, then run it via your evaluator. It won't be efficient. But it's not difficult.

Ok. In one tier 4 language we could implement interpreter for another tier 4 language. What is the point? Could you build a stack up to machine code without pointer? Or could you build cost-effective hardware that implement lambda expressions natively? When building an implementation stack, it makes sense to start from complex and move to simpler and directly executable abstractions like machine code. What is the point of moving from complex to complex or from complex to even more complex?

all attempts (known to me) at the languages with purely immutable structures were at the tier 4

I suggest you look into cellular automata and term rewrite systems.

“cellular automata” – global shared state in the form of board. “term rewrite systems” – model of work is changing of shared term. What relationship they have to immutable state? Or would you argue that SQL “update” statement is also about immutable systems?

Do you know about opaque data types vs abstract data types? Opaque data types are essentially the second-class form of abstract data types. Opaque data types are sufficient to hide shared state, and the API over the opaque type represents a contract. But opaque types don't give us any ability to abstract over multiple implementations of this contract, so I feel they fall a bit short of tier 4.

Opaque data types and abstract data types are attempts to implement the tier 4 concepts in the tier 3 language. This is an example of difference between mental and code model. The correlation between methods has to be maintained manually. Java and other OO languages allow to achieve such goal more cleanly and with much lesser gap between mental model and code model.

Sure. Better to test a general classification against all the edge cases, tho. Including pure languages, tacit languages, concatenative languages, combinatorial logic, term or graph rewrite systems, Kahn process networks, cellular automata, multi-agent systems, ant-based computing, Unison Web where secure hashes serve as compressed containment of large subprograms, etc..

Any article has own scope. And also, them model is applicable to abstractions that are used by humans and thus to programming languages used by humans. If you wish, you could do a classification yourself. For example, Kahn process networks – are the tier 2 notation (basing on Wikipedia article): there is globally named nodes and links between them, there is no sub-nodes in the flow diagram, and there is no free recursion between processes, process links are static. Ant-based computing is an optimization technique rather than notation. You could check others as yourself and try to fit them into the proposed model.

Shared state is essential to some problem domains. We're all living on the same ball of mutable state, after all. Applications developed in a programming language will ultimately need to interact with a shared network and shared databases. But a point worth considering is that all essential shared state is, by nature, outside of the software application. So I wouldn't casually accept a claim that allocation of shared state should be fundamental to programming languages.

Yea. This philosophical point could be argued for. Computations that do not have a useful effect are useless. This is why proponents of functional programming always call these useful intended effects “side effects”. Also, the age of batch jobs is gone. Now many applications are interactive, they could not take input as argument and offload output at the end of the job. And their internal state of the applications suddenly becomes important, and the languages that support convenient work with such shared state in the straightforward way are more useful for such application kinds as they require less of the model translations.

### the model in the mind and

the model in the mind and the model in the code. These models sometimes match, sometimes are different. The abstraction tiers of these models can be different. The greater is the difference, the more transformations are needed to work with code. So, this increases cognitive load.

In context of projectional editing, you should add an automated lens between mind and code. This lens can simultaneously reduce the cognitive load on the mind and reduce user-interface overheads in the code, resulting in a model that's simpler for all observers of the codebase (humans, bots, compilers, etc.).

You are starting at very high-level abstraction. The lambda calculus is the tier 4.

Whether lambda calculus supports high tier abstraction is irrelevant to the point I was making about projections and names.

you are well aware that C++ and many other languages have option to reference object allocated separately or declare it as part of the object: “my_subobject test;” or “my_subobject* test;”

Of course. But C++ has difficulty representing 'containment' of recursive data structures. Whereas, in purely functional languages, a type like type Tree a = Node a (List of Tree a) only ever represents a containment relationship. It could be implemented with pointers for performance, or as a giant string just to make a point that pointers aren't required.

The references in mutable objects are much more direct representation of the graph. [...etc...]

Working with graphs in a language without mutation is not particularly difficult. Matrices are awkward for some problems, but I did mention three other approaches. Further, if we admit references but exclude mutation, we can add adjacency lists, relational tables, and other ways of representing graphs that utilize labeled vertices.

In any case, I grant that mutation does allow easy construction of cycles. Whether or not this is a "good thing" is a separate question. I find I rarely need cyclic objects *unless* I'm working with mutable objects. And when I do, the cycles are a common source of subtle bugs (reentrancy, etc.).

While shared state does not require references, as we could work in assembler with integer addresses, which provide us mapping from integer keys to values. [...]

I'd still consider those to be pointers or references. A pointer or reference is a first-class value that we use to index an external resource. We can speak of nice properties for a reference - self describing, strong typing, self-validating, multi-homing, cryptographically unforgeable, etc.. But a reference in the absence of nice properties would still be a reference with respect to computation.

The point you are missing that when we are working with data structures in a programming language, the programming language provides us multiple services, like error checking, code exploration support, etc. We lose all these services with using string as primary data structure.

No, you're clearly missing my point. I'm saying the language's *compiler* could implement the tree as a string. It wouldn't be efficient. Indeed, it'd be utterly pointless EXCEPT for this one specific point: "yes, we can implement trees without using pointers, suck on that const". We wouldn't lose ANY of those nice services you just mentioned. Construction and manipulation of the tree would still be strongly type-safe, for example. Indeed, other than the crawling slowness and extra warmth from the CPU, the programmer wouldn't even notice that the tree is implemented as a string.

Ok. In one tier 4 language we could implement interpreter for another tier 4 language. What is the point?

You said, "I also have a trouble of imagining how it could be implemented without pointers". I was telling you how it could be implemented without pointers. That is the point. Your lack of imagination. . . disturbs me.

Could you build a stack up to machine code without pointer? Or could you build cost-effective hardware that implement lambda expressions natively?

I wouldn't start with the lambda calculus. But we can develop a low-level set of purely functional concatenative combinators that operate on a stack similar to a Forth machine - a purely functional abstract machine code, of sorts. We can build upon this monadic programming or algebraic effects to support effectful programming, if we wish.

For performance, I know of two routes. Either we have an expanding set of 'primitive' data types and combinators that can leverage hardware efficiently (like a matrix multiply operator to leverage SIMD), or we can develop software accelerators - basically, compiler-intrinsic functions with a reference implementation - so we can add 'performance primitives' to the language without adding new 'semantic primitive' combinators. Sort of a CISC vs RISC philosophy.

There are several languages in this vein: Joy, Cat, Kitten, my Awelon. It wouldn't be difficult to adapt J or K languages to a purely functional foundation, either.

When building an implementation stack, it makes sense to start from complex and move to simpler and directly executable abstractions like machine code. What is the point of moving from complex to complex or from complex to even more complex?

You seem to be confusing "high tier of abstraction" with "complex". Lambda calculus isn't particularly complex. Combinatory logic is even less so. And concatenative combinators would give us nice, streamable code as our foundation - much simpler than machine code with its awkward backwards jumps.

Compiling goes from simple abstract machine code to complex physical machine code, not complex to simple.

“cellular automata” – global shared state in the form of board.

Incorrect. Cells cannot mutate even their own state, much less that of their neighbors or the rest of the board. The board is immutable. Instead, we compute the 'next' state of each cell, thus computing a new board. This is best understood with immutability, and perhaps a simple temporal logic. It's also below tier 2.

“term rewrite systems” – model of work is changing of shared term. What relationship they have to immutable state? Or would you argue that SQL “update” statement is also about immutable system?

The term itself is immutable. We produce a new term after each rewrite. This is no different to how adding or modifying an entry to an immutable tree produces a new tree, or how incrementing 7 returns 8 rather than mutating all 7s everywhere.

SQL 'update' does modify a variable that contains a table. But the table itself is supposedly an immutable data structure (per relational algebra).

Kahn process networks – are the tier 2 notation (basing on Wikipedia article): there is globally named nodes and links between them, there is no sub-nodes in the flow diagram, and there is no free recursion between processes, process links are static.

Wrong on most points. KPNs abstract the 'process' so it can be another KPN. This gives us tier 3 hierarchies. Channels may be locally named within each process network, e.g. we attach the channel to an open port on a process. Cyclic relationships are permitted - we can even loopback a process's outputs directly. But it's true that links are static.

The article you found was just describing the essential properties of KPNs. The example diagram you found is not really a usable notation.

Ant-based computing is an optimization technique rather than notation.

Ant-based computing is not just an optimization technique. It has been used in that way, but it is also explored as a universal computation model by itself. However, I grant it's more like "OOP" or "publish-subscribe" - a paradigm rather than a notation.

Computations that do not have a useful effect are useless. This is why proponents of functional programming always call these useful intended effects “side effects”.

As a proponent of functional programming: We call them effects. We think effects are both important and troublesome, so we handle them with care: effects are separated from logic where feasible, and typed where used. We do shun "side effects" - effects that are hidden from the client of an API. But that doesn't mean we ignore "intended effects".

This proponent who always calls intended effects 'side effects' is misinformed about FP, is lying to you, or is a straw man you fabricated with intention to burn.

internal state of the applications suddenly becomes important, and the languages that support convenient work with such shared state in the straightforward way are more useful

Gotta disagree with you in the first half. Internal state is 'poison' to an application - it greatly hinders extension, administration, debugging, durability, and interaction between apps. Better to shove any application-specific state out to a database or filesystem.

I do agree that the language needs to support convenient work with shared state. But not as a primitive. We can model it in a library, as an 'effect'.

### What is mutable and what is immutable?

“cellular automata” – global shared state in the form of board.

Incorrect. Cells cannot mutate even their own state, much less that of their neighbors or the rest of the board. The board is immutable. Instead, we compute the 'next' state of each cell, thus computing a new board. This is best understood with immutability, and perhaps a simple temporal logic. It's also below tier 2.

“term rewrite systems” – model of work is changing of shared term. What relationship they have to immutable state? Or would you argue that SQL “update” statement is also about immutable system?

The term itself is immutable. We produce a new term after each rewrite. This is no different to how adding or modifying an entry to an immutable tree produces a new tree, or how incrementing 7 returns 8 rather than mutating all 7s everywhere.

SQL 'update' does modify a variable that contains a table. But the table itself is supposedly an immutable data structure (per relational algebra).

The board and cells for cellular automata and term for term rewrite systems have the same logical identity among different versions modified by rules. Cells for cellular automata also have an identity among different versions.

The intended effect is change this object from one version to another. Using readonly snapshots could be implementation technique for such systems, but intention is changing that logical object. And they are often implemented as mutable objects.

Your argument could be extended to say that Java (or Turing Machine) works with immutable objects as we could consider its semantics as driving memory state from one memory snapshot to another according to rules of the programming language. This could be useful point of view for proofs, mental model of Java developer is usually different. Advantage of Java is that we usually do not need to consider the global memory state, but we could consider local changes.

IMHO you are stretching immutability too far, even to objects that logically are not. Any mutable object could be considered as sequence of immutable snapshots, and this often done in proofs. So we should say that everything is immutable? If association between logical identity and state changes, this logical object is mutable IMHO. So board in cellular automata is mutable logical object, as it has logical identity and changing state. Cell is mutable object as well. Turing Machine is a mutable object as well.

### Re what is mutability

What 'mutability' means is a good question. I'll try to answer it to my understanding.

In lambda calculus, objects having 'identity' is not uncommon. E.g. when we fold over a list, we have an 'accumulator' variable that effectively has an identity - its role as accumulator - for the duration of fold. We can think about our manipulations to this variable as mutations. If the variable is of simple value type, like an integer, there's nothing more to think about. But if it's a structured tree, then we need to understand that modifications to the accumulator won't influence prior versions of the tree. This is the basic idea of immutability: that updates are local, that we aren't affecting observers of the prior version.

So mutability is the alternative condition: the updates can be observed externally.

Your argument could be extended to say that Java (or Turing Machine) works with immutable objects

Agree for Turing machines, where we only locally manipulate the head of a tape and the tape is supposedly hidden from external observers until computation halts. But not for Java, where a modified field can be observed by other threads.

Any mutable object could be considered as sequence of immutable snapshots

Indeed. The question is whether it's useful to think about it that way in context of developing the program itself. For cellular automata, it's quite useful to know that the order in which we 'update' cells is irrelevant, because we aren't mutating the cell's current version. For term rewriting, it's useful to know that two copies of a term can be moved into different contexts and rewrites on them are subsequently independent.

Or conversely, for Lisp it's important to know that a spurious 'setcdr' by a callback could ruin your tree. For Java, it's important to understand that modified variables affect other threads.

Aside: ur quotes all fubar, plz fix

### Projectional editing

In context of projectional editing, you should add an automated lens between mind and code. This lens can simultaneously reduce the cognitive load on the mind and reduce user-interface overheads in the code, resulting in a model that's simpler for all observers of the codebase (humans, bots, compilers, etc.).

I do not think that projectional editing is relevant to disucssion here, as it is not related to issue of abstractions tiers used.

Also none of attempts at projectional editing really took off. There is a number of technical reasons for it: bad support from version control, bad support for code snippets and copy/paste, bad support for working with temporary incorrect code, and so on. I think that there is a logical problem under all these technical problems, but this is a topic for a separate discussion.

### Re projectional editing

I do not think that projectional editing is relevant to disucssion here, as it is not related to issue of abstractions tiers used.

Several of your statements are based on an implicit assumption that the abstractions tiers are supported in a specific way - by modifying the stored code representation, with names as references between code. Projectional editing is relevant insofar as it contradicts this assumption.

Here's something 100% irrelevant, though:

Also none of attempts at projectional editing really took off.

### Notation is what user is working with

Several of your statements are based on an implicit assumption that the abstractions tiers are supported in a specific way - by modifying the stored code representation, with names as references between code. Projectional editing is relevant insofar as it contradicts this assumption.

In the notation user works with, the user still see names that are resolved to object. Projectional editing tools just pre-resolve these names during editing process, and name resolution is sometimes ambigous depending on context. So, I do not see any contradition here.

Here's something 100% irrelevant, though:

Also none of attempts at projectional editing really took off.

If language technology repeatably fails to take off, this is an indication of some contradiction between how technology works and human brain works. So there is a problem with it as with a notation intended for human consumption.

The same argument is applicable to pure functional languages, that fail to occupy a significant market share despite all efforts from academia. Some elements of functional paradigm were integrated in OO languages mostly as shortcuts for OO constructs (like lamdas were adopted as shortcut for single method interface implementation). This is an indication of usability problem due to cogntive aspects of the notation. OO languages seems follow the way brain works better. In the personal experience, learning Java is easier than learning Haskell.

### In the notation user works

In the notation user works with, the user still see names that are resolved to object. Projectional editing tools just pre-resolve these names during editing process, and name resolution is sometimes ambigous depending on context. So, I do not see any contradition here.

The contradiction is with something you said earlier: "The basic idea of hierarchy is replacing a part of the pattern with its representative. The representative is a pointer in general case."

Basically, you were taking the stance that pointers are needed for tier 3 because representing hierarchal structure requires pointers.

This *despite* explicitly admitting 'single object patterns' and 'containment' in your article.

### The phrase was loosy

That phase was loosy and used word pointer in wrong way. It should have said "The representative is something that could be resolved to that referenced pattern, for example a pointer." or something like, the article has gone through more refinement cycles than comment, so it is usually more precise.

I still do not see relationationship to projectional editing.

### Kahn process networks

I've not worked with this model, so I'm possibly missing something. But let's consider articles referenced from wikipedia.

Basic article by Khan (Kahn, G. (1974). Rosenfeld, Jack L., ed. The semantics of a simple language for parallel programming), it notes possiblity of recusion (sections 4), but it does not define it fully. From the text, it obvious that author has only vagues ideas on how it could be done.

This thesis (Parks, Thomas M. (1995). Bounded Scheduling of Process Networks (Ph. D.). University of California, Berkeley.) does not mention recusion at all.

This article (Geilen, Marc; Basten, Twan (2003). Degano, P., ed. Requirements on the Execution of Kahn Process Networks.) also does not mention recusion at all.

While Khan had some vague ideas about recusion, these ideas have not been implemented. Particually, notation does not have notation to spawn a new process with parameters, which is critical for recusive processes. All processes in the actual notation are pre-created and work as parts of pipeline. I would argue that the tier 3 notation for process would have been different (for example, like this).

The minimal test for the notation night have been specify Ackermann function in recurive form, that we send a pair of numbers and receive a result.

So, after more detailed consideration, I'll still classify it as the tier 2 notation in the current form, potential developments could change it, but these developments did not happen at the current time.

### KPN recursion

We can have hierarchical KPNs, and cyclic KPNs. But it seems you mean something else by 'recursion', that one KPN can evaluate another.

In my language, KPN descriptions are represented as values. And 'running' a KPN is a pure (confined, deterministic) computation, albeit benfiting from specialized runtime support. So, KPNs can be passed on channels and evaluated recursively. But I grant I haven't seen this feature elsewhere.

But regardless of recursion, AFAICT, *hierarchical* KPNs (with local channels) are sufficient to qualify for your tier 3. Because it allows us to name patterns of processes and wire them together, then name this pattern of patterns for further use - that's how you define tier 3.

Why do you believe recursion or spawning is even relevant?

### hierarchical and cyclic KPNs

I do not undestand what do you mean under hierarchical KPN. Any examples in articles?

Hierarchical KPN might be where we define a node, and this node has own substructure names local to this subnone and local connections. And this needs to happen within notation. Like nested blocks in VHDL. I do not see these things in KPN papers that I have looked at. Original Khan's paper also does not discuss it. There might be a dialect with hierarchical KPN suport, but it should be considered separately, like FORTRAN 66 is a tier 2 langauge, FORTRAN 77 is a tier 3 langauge, and FORTRAN 2003 is a tier 4 language.

Cyclic KPNs do not increase an abstraction level as we have a flat namespace of nodes and these nodes are connected within pattern. It is just like the following BASIC program is cyclic, but it is cyclic with the tier 2 notation as there is a flat mapping from line number to actions and oprations refer to this mapping ("next" operator uses variable name as name for "for" operator line) (the sample is taken from wikipedia):

5 LET S = 0
10 MAT INPUT V
20 LET N = NUM
30 IF N = 0 THEN 99
40 FOR I = 1 TO N
45 LET S = S + V(I)
50 NEXT I
60 PRINT S/N
70 GO TO 5
99 END

### Hierarchical KPNs

To clarify, Kahn Process Networks are not a 'notation' by themselves. They instead define a set of constraints on communication between processes to guarantee a deterministic outcome while supporting parallel computation and incremental interaction. It's these properties that make KPNs great for high-performance computing in context of a purely functional language.

However, there are many notations that are a great fit for KPNs, such as box-and-wire diagrams in component-based programming. Consider John Paul Morrison's Flow Based Programming (FBP), which has a large number of graphical implementations and a reasonably large following. We could easily develop KPNs using a subset of FBP notation (e.g. forbidding non-deterministic merge of output wires).

Hierarchical KPNs are what we get when we take "open" KPNs (a KPN with some unbound input or output channels), give them a name, and allow them to be be reused as component processes in a parent KPN. Thus, a KPN is just another process from the perspective of a parent KPN.

So, the common notations we'd use for KPNs in practice today are tier 3. Same as FBP.

### Where is hierarchical KPN described?

The tier model is applicable to notations and how abstractions in it play together. If something is not a notation, the model should be applied with care.

The graphical notation in original Khan article, dissertation, and other refrenced article are tier 2. And I have not found resuse of graph that you are describing with quick scan of the original KPN. It has only operation of joinig KPNs together. So, could you point to articles that confirm such usage KPN. Or point to part of original Khan article that describes such usage.

I have feeling that you are extending KPN model with additional mechanisms, but might be some other notation like "structured KPN". That would be different from original KPN in the same ways as FORTRAN 77 is different from FORTRAN 66. The tier evaluation is related to the specific version of the notation, any additional extensions could change evalution.

Subset of something does not necessary share the same abstraction tier as original notation as relveant parts might be not included into the subset.

Flow-based programming also refers to many different langauges with different features. Graphical samples are the tier 2 notations visually, there might be the tier 3 semantics attached to nodes, but it is not obvious from diagrams. Please specify as specific language and specific version that you mean, and only than we could discuss the tier.

### Hierarchical KPNs

The wikipedia article on KPNs already defines 'open' KPNs. Hierarchical KPNs are what happen when you cut a circle out of a KPN and give the resulting open KPN a name for reuse. The correctness of doing so is very nearly 'trivial' - we can prove equivalence by inlining a component KPN back into the original diagram (and perhaps some alpha renaming of internal channels).

It's a trivial and obvious extension, so I've never even thought to look for old articles on the subject. For your warning about 'applied with care' - yeah, done that.

In any case, when I spake of KPNs earlier, I'm indeed talking about the hierarchical structured forms where we can name KPN patterns and use them as components for larger KPNs, which is sufficient to reach tier 3 (because we now use named patterns as nodes within our patterns).

Graphical samples are the tier 2 notations visually, there might be the tier 3 semantics attached to nodes, but it is not obvious from diagrams.

FBP is at least tier 3. A central tenet of FBP is developing reusable 'components' that are essentially black-boxes referenced by name. But it's hierarchical nodes included by name, so tier 3, instead of patterns by contract, which would be tier 4. According to that first article, at least.

### Hierarchical KPNs seem to be extension of model

So, you are using some extended notation that is not described in the articles. The Khan's notation is a simple graph. Addition of the tier 3 will require naming graphs, creating copy of graph (possibly with node rename) on use, and than connecting ends of the copy to ends of the node. While it looks simple and intuitive, the logic is not so trivial, and there is no traces of this logic in Khan's artricle.

As I understand Khan article, the implied reuse model was connecting inputs of one graph to output of another graph without creating copies (connecting boundaries). Your reuse model is invoking copies and connecting them in place (connecting from inside with substitution).

I'm not sure what reuse model different notations of FBP family use, as both cases are reuse, but reuses of the different tier. Maybe different languages use different models.

### Re: model in mind and model in the code

Of course. But C++ has difficulty representing 'containment' of recursive data structures. Whereas, in purely functional languages, a type like type Tree a = Node a (List of Tree a) only ever represents a containment relationship. It could be implemented with pointers for performance, or as a giant string just to make a point that pointers aren't required.

This is relationship by reference in the implementation. Because only “by reference” representation allows achieve acceptable performance. The fact of by reference or even lazy semantics is widely used in implementation of the collection libraries. And this could not be changed without changing fundamental performance characteristics of the language. Lage parts of Haskell code will stop to work if change lazy to eager evaluation due to usage of infinite lazy structures.

Working with graphs in a language without mutation is not particularly difficult. Matrices are awkward for some problems, but I did mention three other approaches. Further, if we admit references but exclude mutation, we can add adjacency lists, relational tables, and other ways of representing graphs that utilize labeled vertices.

All these ways add a need for additional translation of models in the mind just like a matrix representation, thus creating additional cognitive load. And also, these ways have poor support for non-uniform graphs.

I'd still consider those to be pointers or references. A pointer or reference is a first-class value that we use to index an external resource. We can speak of nice properties for a reference - self describing, strong typing, self-validating, multi-homing, cryptographically unforgeable, etc.. But a reference in the absence of nice properties would still be a reference with respect to computation.

Pointer in the language and pointer in the mind are different things. On assembly or machine code layer we have numbers. We have typed pointers on the language layer in the tier 3 and above languages. Integers on machine code layer are implementation of pointer. Machine code just have indexed memory access rather than references. This is a different logical concept. The pointers as typed object were invented only in the year 1964.

No, you're clearly missing my point. I'm saying the language's *compiler* could implement the tree as a string. It wouldn't be efficient. Indeed, it'd be utterly pointless EXCEPT for this one specific point: "yes, we can implement trees without using pointers, suck on that const". We wouldn't lose ANY of those nice services you just mentioned. Construction and manipulation of the tree would still be strongly type-safe, for example. Indeed, other than the crawling slowness and extra warmth from the CPU, the programmer wouldn't even notice that the tree is implemented as a string.

Now to complete the thing you need to implement a string without usage of pointers or indexed memory access. Also, the string interpreter itself could not use pointers or indexed memory access for support structures.

You said, "I also have a trouble of imagining how it could be implemented without pointers". I was telling you how it could be implemented without pointers. That is the point. Your lack of imagination. . . disturbs me.

Yea. I lacked imagination that someone consider implementing things not my moving close to the hardware, but possibly moving further from it. Actual implementation techniques use pointers. To implement them on realistic hardware one to have to use pointers, on go to evet to lower level and use addressed memory access.

I wouldn't start with the lambda calculus. But we can develop a low-level set of purely functional concatenative combinators that operate on a stack similar to a Forth machine - a purely functional abstract machine code, of sorts. We can build upon this monadic programming or algebraic effects to support effectful programming, if we wish.

For performance, I know of two routes. Either we have an expanding set of 'primitive' data types and combinators that can leverage hardware efficiently (like a matrix multiply operator to leverage SIMD), or we can develop software accelerators - basically, compiler-intrinsic functions with a reference implementation - so we can add 'performance primitives' to the language without adding new 'semantic primitive' combinators. Sort of a CISC vs RISC philosophy.

There are several languages in this vein: Joy, Cat, Kitten, my Awelon. It wouldn't be difficult to adapt J or K languages to a purely functional foundation, either.

Forth uses stack as shared mutable data structure. Selective check with Joy and Kitten shown that they “dup” operator as well, so they rely on mutable and explicitly accessed data structure - stack.

As a proponent of functional programming: We call them effects. We think effects are both important and troublesome, so we handle them with care: effects are separated from logic where feasible, and typed where used. We do shun "side effects" - effects that are hidden from the client of an API. But that doesn't mean we ignore "intended effects".
This proponent who always calls intended effects 'side effects' is misinformed about FP, is lying to you, or is a straw man you fabricated with intention to burn.

You have conveniently added word “always” to the context. But let’s look to the documentation that is addressed to imperative programmers at this link. I think it is representative, as it is specifically discussing this issue from point of view of Haskell programming. All usages of word effect on this page are either “side-effect” or “side effect”. So, people that consistently use the words “side effect” in the context of at least one article do exists.

I’ve seen some papers that discusses word effect in other way, but they do not seem to be representative. Even Wikipedia article insists on side effect as main name of the term, and in the article about referential transparency as well. So even if these articles are incorrect, none has bothered to change them, so they seem to be acceptable for community.

### Because only “by

Because only “by reference” representation allows achieve acceptable performance.

You're terrible at this whole 'logic' thing, aren't you? Since you're trying this fruitless direction, you next need to prove the impossible: that abstraction tiers have performance requirements.

AFAICT, your abstraction tiers have no hard requirement for performance, popularity, cognitive load, or even utility. So 99.9% of what you've tried to argue (in earlier posts, too) seems irrelevant to specific questions like "do tier 3 languages need pointers"?

they “dup” operator as well, so they rely on mutable and explicitly accessed data structure - stack.

Dup is purely functional.

dup : (s * a) -> ((s * a) * a)

Fact is, we aren't sharing the stack, so it isn't shared state. It can be understood as a linear value.

You have conveniently added word “always” to the context.

Nope. I only emphasized it. You said, "proponents of functional programming always call these useful intended effects “side effects”".

I linked an article on algebraic effects, earlier. It is, today, the most popular approach to effects in new FP languages.

AFAICT, your abstraction tiers have no hard requirement for performance, popularity, cognitive load, or even utility. So 99.9% of what you've tried to argue seems irrelevant.

Yea. Discussion has moved from abstraction tiers discussion long ago, and degraded to OO vs FP discussion where we obviously disagree on many points. This is discussion is not relevant to the topic indeed.

Abstraction tiers are just about abstractions, my main argument is that notations evolve along the same line, and I have not seen clear arguments about that point. And this is closely related to issue how humans interact with notations, so cogntive load is essential to the discussion. With each tier transion the structure of cogntive load changes, and this allow humans to manage a greater amount of elements.

Notations are not for comptuers, notations are for humans to interact with computer. IMHO the best notation is one that allows to get things done in most strainghforward way close to mental models. It looks like we disagree on this point as well, as you seems to value other aspects of notation more.

I do not actually undestand the point that you are trying to make, as I have only seen discussing some small details and random language references that you claim as contradicting the model somehow without saying explicitly what contradition was. Please make your core point(s) clear.

You seems to argue that pointers/references are not essential for the high-tier notations that work with data. However, even Haskell has references and they are essential to its semantics. The argument the values are passed by containment in pure FP is not true from point of view of Haskell, as they are passed by lazy reference.

Mutable/immutable issue is irrelevant to abstraction tiers, except for I have not seen a general-purpose programming language with only immutable structures below the tier 4.

Functional languages (ML, Haskell, LISP) start at the tier 4 at least for behaviour aspect, because lambda abstractions belong to this tier. As such, I do not think that they are a good basic layer describe computing systems and their evolution, while they could be useful for proofs due to Turing-equivalence. You seems to disagree on this point as well. But it does not look strongly relevant to discussion of abstraction tiers.

Dup is purely functional.

dup : (s * a) -> ((s * a) * a)

From cursory glance, the dup operation in these languages does take an explicit argument, it takes implicit stack pointer from context and saves modified stack pointer back to the context from notation point of view. The stack is shared between operations. I have not worked with these languages, but I had some experince with Forth.

In contrast, the haskell does not share stack between operations, the operations do not need to be aware of the stack state at all, and in case CPS-rewirte phisical stack even could be avoided. So there is no mutable state in notation until we start monad-based DSL that allows us to do imperative programming.

So it does not seem to have a signature that you are poposing from usage point of view.

### Abstraction tiers are just

Abstraction tiers are just about abstractions

Indeed.

main argument is that notations evolve along the same line

Well, that's perhaps the main point of your overall article.

But refer to your first clause: "abstraction tiers are just about abstractions".

Therefore, abstraction tiers are NOT about the evolution of notation. They are NOT about cognitive load. They are NOT about performance. Further, based on how you describe them, they are NOT about specific abstractions such as pointers or mutation.

You seems to argue that pointers/references are not essential for the high-tier notations that work with data.

Yes, that's what I'm claiming. I won't deny they're sometimes convenient, though.

I have not seen a general-purpose programming language with only immutable structures below the tier 4.

Notations for combinatory logic languages (like SK combinators) would qualify. We could build a functional language above them. Without the 'variables' of lambda calculus, there's no convenient way to "substitute" a hierarchical node (in the notation) with something that will fulfill the contract. Yet, we still have all that Turing powerful computation and immutability.

Lambda calculus can desugar to SK combinators. So, it isn't difficult to lift combinatory logic to tier 4 via projection or syntactic sugar. But it's not there by itself.

From cursory glance, the dup operation in these languages does take an explicit argument

You have it wrong. (s * a) is the type of the *implicit* stack argument. The dup operator takes as input the data stack with at least one item, then produces a stack with the same item cloned, hence output type ((s * a) * a). I find it convenient to represent stack types as tuples like this.

In contrast, the haskell does not share stack between operations, the operations do not need to be aware of the stack state at all

You seem to be confusing Haskell's call-return stack with a stack programming language's data stack. Most stack programming language implementations also use separate call-return stacks.

### SK combinators

I have not seen a general-purpose programming language with only immutable structures below the tier 4.

Notations for combinatory logic languages (like SK combinators) would qualify, and we could easily build a language above them. Without the 'variables' of lambda calculus, there's no convenient way to "substitute" a hierarchical node (in the notation) with something that will fulfill the contract. Yet, we still have all that Turing powerful computation and immutability.

Lambda calculus can desugar to SK combinators. So, it isn't difficult to lift combinatory logic to tier 4 via projection or syntactic sugar. But it's not there by itself.

You have missed part a general-purpose programming language. SK combinators are not a general-purpose programming language. It is mathematical model. Becasue of Unlambda, I should have explicitly added "actually used by humans in practice", since it is possible to create a toy language with arbitrary features. But Unlambda purity is under suspicion, since it has IO functios in basis.

The translation of one notation to other notation generally says nothing about their abstraction tiers. After all, everything could be compiled to Turing Machine that is the tier 2 and back.

Also, everything above machine code is just "a syntax sugar". The programming languages are needed for humans to manage increasing behavior complexity. And the higher the tier of the abstraction, the more complex behavior they allow to organize into manageable form.

You have it wrong. (s * a) is the type of the *implicit* stack argument. The dup operator takes as input the data stack with at least one item, then produces a stack with the same item cloned, hence output type ((s * a) * a). I find it convenient to represent stack types as tuples like this.

The execution of dup operator involves retrieving stack pointer and than saving it back in a modified form. The internal code of dup might be immutable, but its excution logically is not if we consider environment where it is executed. While this stack register is implicit, the knowledge about it is critical for semantics of the operations. It might be possible to hide in monad like way and even type it. But from my experience in Forth, soon one need operations dupNth and so on, that are even harder to type and would require more interesting ways to work with stack.

### SK combinators are not a

SK combinators are not a general-purpose programming language

Lambda calculus, by itself, is also not usable as a general purpose programming language. You at least need to support libraries of user-defined named functions before it's usable. You might also add shorthand for numbers, lists, strings, etc. so data input is tolerable. You might further need compiler support to integrate with the effectful environment (like Haskell's IO monad).

Yet you have repeatedly shortened this to just "lambda calculus". IMO, if you don't need to fully describe the obvious and necessary extensions to lambda calculus, then I shouldn't need to mention the same for SK or KPN or any other simple base model.

There in fact have been general purpose languages built upon simple combinator bases. My own Awelon language would be an example. But these do receive same treatment as lambda calculus before use as a general purpose language: libraries of named functions, shorthand for concise data input, etc.

everything above machine code is just "a syntax sugar"

I define syntactic sugar more rigorously than that. Syntactic sugar must be modeled by a syntactically local transform.

Thus, a lot of language features - packages and modules, multi-methods, typeclasses, type-based overloading of function names, etc. - are not syntactic sugars because they involve remote elements. Syntactic sugar is also limited to output valid syntax. Thus, output of machine code is only possible for languages with features for embedding machine code.

Or put another way, syntactic sugar has essentially the same limits on extent and features as text preprocessor macros.

execution of dup operator involves retrieving stack pointer and than saving it back in a modified form. The internal code of dup might be immutable, but its excution logically is not if we consider environment where it is executed.

If we consider execution environment, even lambda calculus uses no immutable data structures.

But that's not what 'mutability' as a semantic concern is about.

### The following my statement

The following my statement was specifically about general purpose langauges used by humans:

I have not seen a general-purpose programming language with only immutable structures below the tier 4.

So it is not applicable to SK and lamda calculus which are mathematical notations. The notion of tiers is appliable to SK and lambda calculus, but the statement above is not.

It is also not applicable to the toy languages, because when humans use the language on the large applications they have to balance features for usuability. Toy languages do not have a need to balance.

dup

### (Entities, Species, and Genera) * (Concrete, Abstract)

This quote from Stepanov's "Elements of Programming" seems relevant:

In order to explain what objects, types, and other foundational computer notions are, it is useful to give an overview of some categories of ideas that correspond to these notions.

An abstract entity is an individual thing that is eternal and unchangeable, while a concrete entity is an individual thing that comes into and out of existence in space and time. An attribute—a correspondence between a concrete entity and an abstract entity—describes some property, measurement, or quality of the concrete entity. Identity, a primitive notion of our perception of reality, determines the sameness of a thing changing over time. Attributes of a concrete entity can change without affecting its identity. A snapshot of a concrete entity is a complete collection of its attributes at a particular point in time. Concrete entities are not only physical entities but also legal, financial, or political entities. Blue and 13 are examples of abstract entities. Socrates and the United States of America are examples of concrete entities. The color of Socrates' eyes and the number of U.S. states are examples of attributes.

An abstract species describes common properties of essentially equivalent abstract entities. Examples of abstract species are natural number and color. A concrete species describes the set of attributes of essentially equivalent concrete entities. Examples of concrete species are man and U.S. state.

A function is a rule that associates one or more abstract entities, called arguments, from corresponding species with an abstract entity, called the result, from another species. Examples of functions are the successor function, which associates each natural number with the one that immediately follows it, and the function that associates with two colors the result of blending them.

An abstract genus describes different abstract species that are similar in some respect. Examples of abstract genera are number and binary operator. A concrete genus describes different concrete species similar in some respect. Examples of concrete genera are mammal and biped.

An entity belongs to a single species, which provides the rules for its construction or existence. An entity can belong to several genera, each of which describes certain properties.

We show later in the chapter that objects and values represent entities, types represent species, and concepts represent genera.

So here we have on tier zero the concrete instead of chaos, and we have concrete entities, species and genera.

Then on tier one we have abstract entities, species and genera.

### Parsing of the text

Here is some parsing of the text with repect of the tiers.

An abstract entity is an individual thing that is eternal and unchangeable, while a concrete entity is an individual thing that comes into and out of existence in space and time.

Tier 1. Discusses individual entities

An attribute—a correspondence between a concrete entity and an abstract entity—describes some property, measurement, or quality of the concrete entity.

Tier 2. Discusses flat map from names to values

Identity, a primitive notion of our perception of reality, determines the sameness of a thing changing over time.

Tier 1. Discusses individual entities

Attributes of a concrete entity can change without affecting its identity. A snapshot of a concrete entity is a complete collection of its attributes at a particular point in time.

Tier 2. Discusses flat map from names to values

Concrete entities are not only physical entities but also legal, financial, or political entities. Blue and 13 are examples of abstract entities. Socrates and the United States of America are examples of concrete entities.

Tier 1. Discusses individual entities

The color of Socrates' eyes and the number of U.S. states are examples of attributes.

Tier 2. Discusses flat map from names to values

An abstract species describes common properties of essentially equivalent abstract entities. Examples of abstract species are natural number and color. A concrete species describes the set of attributes of essentially equivalent concrete entities. Examples of concrete species are man and U.S. state.

Tier 3-. Discusses nomital types, but there is no discussion of entity references. The types are supposed to be applied ot attributes, but possibly this is too obvious to the author, so it is not discussed.

A function is a rule that associates one or more abstract entities, called arguments, from corresponding species with an abstract entity, called the result, from another species. Examples of functions are the successor function, which associates each natural number with the one that immediately follows it, and the function that associates with two colors the result of blending them.

Tier 2. Discusses functions but there is no discussion that functions could call other functions, like FORTRAN 66 did not allow the recursion.

An abstract genus describes different abstract species that are similar in some respect. Examples of abstract genera are number and binary operator. A concrete genus describes different concrete species similar in some respect. Examples of concrete genera are mammal and biped.

An entity belongs to a single species, which provides the rules for its construction or existence. An entity can belong to several genera, each of which describes certain properties.

Tier 4. The discussion between abstract and concrete here, so there is some notion of black box is introduced.

We show later in the chapter that objects and values represent entities, types represent species, and concepts represent genera.

Tier 1, 2, 3-, 4. The discussion between abstract and concrete here, so there is some notion of black box is introduced (genera).

Generally discussion is restricted to the tier 1,2, and 4 concept, while underusing the tier 3 concepts. The tier 2 concepts is what is close to the iron, and the tier 4 is current mainsream of the langauges. The tier 3 concept are so natural to mind already that they are barely noticed. This is quite strange for the discussion, as structured programming was a major advancement in understanding what is a program. It was a real revolution.

misplaced