Quote from Dave Voorhis on December 7, 2021, 10:41 am

Quote from dandl on December 6, 2021, 11:59 pm

A misunderstanding I think. Every language I know has two kinds of things, or more.

It's a riff on the classic and intentionally tongue-in-cheek "everything is a ..." programming meme(s) about guiding or defining principles, nicely summarised at https://wiki.c2.com/?EverythingIsa

It presumably originates from the Pythagorean notion that everything is a number (i.e., everything is mathematical) though everything in a computer is a number. Anything else depends on perspective (and hardware.)

I have a real problem with this. There is absolutely no reason whatsoever to connect a theory of computation with numbers. There are no numbers in the Turing Machine, just symbols on a tape. It does the issue a great disservice to keep going back to implementation trivia such as numbers and bits.

That's correct -- there are no numbers in a theory of computation. There are no numbers in the Turing Machine.

But unless you have an example of some non-standard computational architecture -- like a homebrew computational gadget or some analog computing device (slide rule?) -- you have a computer where everything is a number... Er, bits. Er... transistor state. Uh, a voltage levels...

Note that I wrote, "everything in a computer is a number", not "everything in computational theory is a number."

• Lisp has lists and atoms. Any atom can be quoted and then its literal value can be assigned to a symbol (setq). Operations are composed as lists with a head and a tail of arguments.
• Smalltalk has objects and selectors. Operations are composed as messages sent to objects and consist of a selector and arguments (objects).
• Forth has words and primitive values. Words are operations on the stack.
• The ERA can be defined purely in terms of relations and scalar values, very much like Lisp. Operations are represented as relcons.

In no case is a type system a requirement, but it helps. Operators know what they need; a type system just helps to avoid errors.

Lisp and Smalltalk have type systems. Only Forth and BCPL and most machine/assembly languages do not -- or more accurately, their type systems are primitive. Values are opaque -- i.e., carry no associated type information -- so it's up to the language user to keep track of the types of values.

I said it's not needed, and I stand by that. The original Lisp had no type system (I know, because I wrote programs in it). Dynamic and static types systems have been grafted on later.

Smalltalk has only objects and selectors, no types. Some of those objects can be made to behave as if they were dynamically typed, but any object can respond to any message. See also https://stackoverflow.com/questions/20714259/smalltalk-type-system#20714495.

Smalltalk is dynamically "duck" typed.  Original Lisp was like Forth and BCPL -- values were opaque and it was up to the language user to keep track of types of values. Modern Lisp (for a rather old value of "modern") is typically dynamically typed.

I think a common problem in these discussions -- and many other similar discussions here and elsewhere -- is the working definition of "type system".

You can roughly (very roughly) describe type systems on a spectrum from least typeful (#1) to fully typeful (#4):

1. There is no distinction between, or no notion of, interchangeable program components (typically "values") of different kinds.
2. There is a distinction between kinds of interchangeable program components (typically "values"), but "correct" use of them must be enforced by the human language user.
3. There are in-language semantics to enforce and/or act on distinctions between kinds of interchangeable program components but no explicit or implicit 'type' construct.
4. There are explicit or implicit identifications or inferences of a 'type' construct, and enforcement and/or selection based on interchangeable program components (which are typically "values") of specific types.

Unfortunately for the sake of (agreeable) discussion, which ones are considered descriptions of "type system" and which ones are not "type system" is not universally agreed.

Some people describe all of the above as being type systems; #1 is simply the least "typeful" type system. This appears to be uncommon use but occasionally appears in theoretical computer science.

Some describe 1 as typeless and 2 - 4 as being type systems. This is fairly common use in applied (and a lot of theoretical) computer science.

Some describe 1 - 2 as being typeless and 3 - 4 as being type systems. This is fairly common use in software engineering, with item 3 sometimes being up for debate as to whether it's typeless or typeful.

And so on.

I describe 1 as typeless and 2 - 4 as type systems, so I use the usual (but not universal) applied computer science interpretation. You're using the usual software engineering interpretation.

Further complicating discussion is inevitable debate over which languages should assigned to which categories, and whether or not typefulness applies only values or more universally. Neither of these are obviously determined, and what "values" are (or aren't) is another definitional obstacle course. Likewise for "symbol", "character", "literal", "representation", "appearance", "presentation", "type" (of course), "variable", "operator", "procedure", "function" and a host of other terms.

Anyway, my point is simply that implementing scalar operations from relation constructs is almost certainly the hard and inefficient way to do it. There are standard ways of implementing scalar expression evaluation. It probably makes more sense -- at least for a practical implementation; an experimental exploration with no concern for efficiency might well do otherwise -- to implement scalar expressions that way and derive relations from them as (or if) appropriate, than construct an expression evaluator from relation primitives.

Nobody proposed using relations as a substitute for scalar values. The RM is built out of exactly two things: relations (with a heading) and attribute values arranged in tuples that conform to the heading. TTM grafted on a type system in order to create a familiar programming language, but a 'fourth manifesto' could take an entirely different tack. No type system required.

I interpreted Paul Vernon's post https://forum.thethirdmanifesto.com/forum/topic/which-reality/?part=4#postid-989248 as wanting to use relations as a substitute (for an undefined value of "substitute") for scalar values. He wrote...

Indeed that is the trick: to get a syntax that is actually just manipulating relations, but that looks like (as far as you can get) "traditional scalar expressions".  I have some ideas, I might even have got somewhere, but I'd certainly be interested in any pointers of anything like this trick out in the wild

My answer is that from a practical point of view -- i.e., if you want to create a usefully performant, practical tool -- it's probably easier to implement traditional scalar expressions as scalar expressions and make it look like it's manipulating relations (where appropriate), rather than implement scalar expressions by manipulating relations and make them look like scalar expressions.

But maybe I misunderstood what he has in mind.

Quote from Dave Voorhis on December 7, 2021, 10:55 am

Quote from dandl on December 7, 2021, 12:44 am

Quote from Dave Voorhis on December 6, 2021, 11:54 am

Quote from Erwin on December 5, 2021, 8:29 pm

Quote from Paul Vernon on December 5, 2021, 3:24 pm

Still, my point was more the question if the codes should be part of a type, and if so, would the literals be just strings (i.e. currency code would be a sub-type of the set of strings), or should the be 'new' literals. ¤FRF say (or, but I sort of think this is cheating because it looks like a function, not a literal to me:  CURRENCY_CODE('FRF') )

The ISO call them "alphabetic codes" as far as I can see..  so no real indication if they consider them "just" strings, or "something else" that is not strings.

The best I can answer here is that many people seem to overlook that when it comes to representation, the fundamental type is STRING (or CHAR or TEXT or how you want to name it).

That's the fundamental representation type of literals.

No. That is the one and only way that literals can be expressed in a text-based programming language, but the same thing can be said about symbols, identifiers, punctuation, etc. It says nothing, and it says too much. In my text editor a literal is represented by text of a distinctive colour (orange or pale green) and symbols are represented by text in a different colour.

That's a text editor presentation, not a language literal representation.

The core distinctions here are the human-friendly representation (e.g., text for typical languages), the machine representation of the human-friendly representation (e.g., ASCII or UNICODE text strings for typical languages), and the machine representation of some translation from the human-friendly representation to a machine-friendly representation for execution.

The fundamental representation type of everything in computing is array of bytes, er, array of bits... er, transistors being on or off. :-)

And again, no. Every programming language targets a virtual or abstract machine (the C standard makes this particularly clear). It has nothing to do with transistors, and only deals with bytes or bits as defined by the standard. A VM for Lisp or Smalltalk has no bytes or bits (although atoms and objects respectively might emulate them). Mixing up implementation/hardware concerns with language/data concerns is a really bad thing to do.

I think you missed the smiley at the end.

Though if we're talking about typical computing mechanisms -- like those we're using to conduct this discussion, or those that Paul will presumably use to build and run his language -- then everything is an array of bytes/bits/transistor-states/voltages/etc.  Obviously, you can create any number of higher abstraction layers to hide lower and more concrete (or other abstract) layers, but practical, usable, performant languages intended for real-world work do, in one way or another, need to consider the concrete characteristics, capabilities and limitations of the machines upon which they run.

Ideally, you can hide all that from your language users, but sometimes you can't.

Quote from AntC on December 7, 2021, 12:15 pm

Quote from Dave Voorhis on December 7, 2021, 10:41 am

Quote from dandl on December 6, 2021, 11:59 pm

A misunderstanding I think. Every language I know has two kinds of things, or more.

It's a riff on the classic and intentionally tongue-in-cheek "everything is a ..." programming meme(s) about guiding or defining principles, nicely summarised at https://wiki.c2.com/?EverythingIsa

It presumably originates from the Pythagorean notion that everything is a number (i.e., everything is mathematical) though everything in a computer is a number. Anything else depends on perspective (and hardware.)

I have a real problem with this. There is absolutely no reason whatsoever to connect a theory of computation with numbers. There are no numbers in the Turing Machine, just symbols on a tape. It does the issue a great disservice to keep going back to implementation trivia such as numbers and bits.

That's correct -- there are no numbers in a theory of computation. There are no numbers in the Turing Machine.

But unless you have an example of some non-standard computational architecture -- like a homebrew computational gadget or some analog computing device (slide rule?) -- you have a computer where everything is a number...

Emmm since you mentioned Turing: " the world's first [**] programmable, electronic, digital computer," was built for "  the cryptanalysis of the Lorenz cipher." It was therefore a computer where most things were characters (ciphers). Ok they might have been represented electrically as numbers (code points) but you're mixing up PhysRep with LogRep.

[**] It wasn't until long after the history books were written that Colossus got recognised as the first programmable computer. Thanks to the stupid British destroying all records (and nearly all the physical remains) on grounds of national security.

Er, bits. Er... transistor state. Uh, a voltage levels...

Bits/transistor state (harrumph you mean thermionic valve state)/voltage levels (mercury tube bubbles) are not numbers. They're only numbers under an interpretation; other interpretations are equally valid.

Note that I wrote, "everything in a computer is a number", not "everything in computational theory is a number."

Then how about a data structure "in a computer" representing a Church Encoding of a linked list?

 

Quote from Paul Vernon on December 7, 2021, 12:53 pm

Quote from Dave Voorhis on December 7, 2021, 10:41 am

You can roughly (very roughly) describe type systems on a spectrum from least typeful (#1) to fully typeful (#4):

1. There is no distinction between, or no notion of, interchangeable program components (typically "values") of different kinds.
2. There is a distinction between kinds of interchangeable program components (typically "values"), but "correct" use of them must be enforced by the human language user.
3. There are in-language semantics to enforce and/or act on distinctions between kinds of interchangeable program components but no explicit or implicit 'type' construct.
4. There are explicit or implicit identifications or inferences of a 'type' construct, and enforcement and/or selection based on interchangeable program components (which are typically "values") of specific types.

Unfortunately for the sake of (agreeable) discussion, which ones are considered descriptions of "type system" and which ones are not "type system" is not universally agreed.

Also a great post. Thanks Dave.

I describe 1 as typeless and 2 - 4 as type systems, so I use the usual (but not universal) applied computer science interpretation. You're using the usual software engineering interpretation.

For the record, I am thinking of (I hesitate to say "working on") a language that is a #3 on the above scale. I am considering (still) if it useful to describe it as have a "type system" or not.  Maybe a "type 3 type system" ;-)

 

Nobody proposed using relations as a substitute for scalar values. The RM is built out of exactly two things: relations (with a heading) and attribute values arranged in tuples that conform to the heading. TTM grafted on a type system in order to create a familiar programming language, but a 'fourth manifesto' could take an entirely different tack. No type system required.

I interpreted Paul Vernon's post https://forum.thethirdmanifesto.com/forum/topic/which-reality/?part=4#postid-989248 as wanting to use relations as a substitute (for an undefined value of "substitute") for scalar values. He wrote...

Indeed that is the trick: to get a syntax that is actually just manipulating relations, but that looks like (as far as you can get) "traditional scalar expressions".  I have some ideas, I might even have got somewhere, but I'd certainly be interested in any pointers of anything like this trick out in the wild

My answer is that from a practical point of view -- i.e., if you want to create a usefully performant, practical tool -- it's probably easier to implement traditional scalar expressions as scalar expressions and make it look like it's manipulating relations (where appropriate), rather than implement scalar expressions by manipulating relations and make them look like scalar expressions.

But maybe I misunderstood what he has in mind.

Again for the record - you did not misunderstand.

Quote from dandl on December 7, 2021, 1:21 pm

Quote from Dave Voorhis on December 7, 2021, 10:41 am

Quote from dandl on December 6, 2021, 11:59 pm

A misunderstanding I think. Every language I know has two kinds of things, or more.

It's a riff on the classic and intentionally tongue-in-cheek "everything is a ..." programming meme(s) about guiding or defining principles, nicely summarised at https://wiki.c2.com/?EverythingIsa

It presumably originates from the Pythagorean notion that everything is a number (i.e., everything is mathematical) though everything in a computer is a number. Anything else depends on perspective (and hardware.)

I have a real problem with this. There is absolutely no reason whatsoever to connect a theory of computation with numbers. There are no numbers in the Turing Machine, just symbols on a tape. It does the issue a great disservice to keep going back to implementation trivia such as numbers and bits.

That's correct -- there are no numbers in a theory of computation. There are no numbers in the Turing Machine.

But unless you have an example of some non-standard computational architecture -- like a homebrew computational gadget or some analog computing device (slide rule?) -- you have a computer where everything is a number... Er, bits. Er... transistor state. Uh, a voltage levels...

Note that I wrote, "everything in a computer is a number", not "everything in computational theory is a number."

Still no. There are no transistors and no infinite tapes in programming languages. For my purposes here every programming language:

• is written to target a translation environment (TE) and an execution environment (EE) (in which transistors and voltages do not appear)
• at translation time consists of symbols of various kinds
• at execution time consists of values and operations on those values.

If there is no separation of values and operations into 'types' there is no type 'system' (except by giving the name 'typeless' to its absence). The TE and EE for C provide a type system, for (original) Lisp and Smalltalk they do not (but you can graft one on top using the EE).

The question that interests me from the OP is whether there is a different model of computing in which the EE supports symbols rather than values, and the whole concept of a type 'system' becomes moot. As per the brain model I mentioned earlier, each symbol is imbued with a raft of connections which determine how it interacts with operators (which of  course are also just symbols).

Indeed that is the trick: to get a syntax that is actually just manipulating relations, but that looks like (as far as you can get) "traditional scalar expressions".  I have some ideas, I might even have got somewhere, but I'd certainly be interested in any pointers of anything like this trick out in the wild

My answer is that from a practical point of view -- i.e., if you want to create a usefully performant, practical tool -- it's probably easier to implement traditional scalar expressions as scalar expressions and make it look like it's manipulating relations (where appropriate), rather than implement scalar expressions by manipulating relations and make them look like scalar expressions.

If we assume a language based on the (E)RA (9 operators plus assignment) it will take a form similar to Codd:

• Relation variables (defined with a heading)
• Literal relations (with a heading and composed of literal scalar values arranged as tuples)
• A library of relcons (each with a known heading)
• Operators on those relations.

Scalar expressions are not a requirement, and it will perform just fine.

 

Quote from Dave Voorhis on December 7, 2021, 1:54 pm

Quote from dandl on December 7, 2021, 1:21 pm

Quote from Dave Voorhis on December 7, 2021, 10:41 am

Quote from dandl on December 6, 2021, 11:59 pm

A misunderstanding I think. Every language I know has two kinds of things, or more.

It's a riff on the classic and intentionally tongue-in-cheek "everything is a ..." programming meme(s) about guiding or defining principles, nicely summarised at https://wiki.c2.com/?EverythingIsa

It presumably originates from the Pythagorean notion that everything is a number (i.e., everything is mathematical) though everything in a computer is a number. Anything else depends on perspective (and hardware.)

I have a real problem with this. There is absolutely no reason whatsoever to connect a theory of computation with numbers. There are no numbers in the Turing Machine, just symbols on a tape. It does the issue a great disservice to keep going back to implementation trivia such as numbers and bits.

That's correct -- there are no numbers in a theory of computation. There are no numbers in the Turing Machine.

But unless you have an example of some non-standard computational architecture -- like a homebrew computational gadget or some analog computing device (slide rule?) -- you have a computer where everything is a number... Er, bits. Er... transistor state. Uh, a voltage levels...

Note that I wrote, "everything in a computer is a number", not "everything in computational theory is a number."

Still no. There are no transistors and no infinite tapes in programming languages. For my purposes here every programming language:

• is written to target a translation environment (TE) and an execution environment (EE) (in which transistors and voltages do not appear)
• at translation time consists of symbols of various kinds
• at execution time consists of values and operations on those values.

If there is no separation of values and operations into 'types' there is no type 'system' (except by giving the name 'typeless' to its absence). The TE and EE for C provide a type system, for (original) Lisp and Smalltalk they do not (but you can graft one on top using the EE).

The question that interests me from the OP is whether there is a different model of computing in which the EE supports symbols rather than values, and the whole concept of a type 'system' becomes moot. As per the brain model I mentioned earlier, each symbol is imbued with a raft of connections which determine how it interacts with operators (which of  course are also just symbols).

There is indeed, and it's called symbolic computation. See https://en.wikipedia.org/wiki/Computer_algebra

Though with modern desktop computing hardware, it's inevitably emulated on top of systems built out of arrays of bytes/bits/transistor-states/voltages. Obviously, computational hardware abstracts away transistor-states/voltages, so we typically only consider arrays of bits/bytes at the lowest level, though pipeline optimisation may well consider processor architecture and the like.

Different general-purpose computational models are certainly possible, but we generally don't use them -- at least not at the machine code level.

Indeed that is the trick: to get a syntax that is actually just manipulating relations, but that looks like (as far as you can get) "traditional scalar expressions".  I have some ideas, I might even have got somewhere, but I'd certainly be interested in any pointers of anything like this trick out in the wild

My answer is that from a practical point of view -- i.e., if you want to create a usefully performant, practical tool -- it's probably easier to implement traditional scalar expressions as scalar expressions and make it look like it's manipulating relations (where appropriate), rather than implement scalar expressions by manipulating relations and make them look like scalar expressions.

If we assume a language based on the (E)RA (9 operators plus assignment) it will take a form similar to Codd:

• Relation variables (defined with a heading)
• Literal relations (with a heading and composed of literal scalar values arranged as tuples)
• A library of relcons (each with a known heading)
• Operators on those relations.

Scalar expressions are not a requirement, and it will perform just fine.

It will perform just fine for those specific operations that it performs -- treating scalar values as opaque -- though if used to implement scalar expressions (which Paul confirmed in a post above, above) it probably won't perform very well compared to implementing scalar expressions in the usual fashion.

Quote from Dave Voorhis on December 7, 2021, 1:57 pm

Quote from AntC on December 7, 2021, 12:15 pm

Quote from Dave Voorhis on December 7, 2021, 10:41 am

Quote from dandl on December 6, 2021, 11:59 pm

A misunderstanding I think. Every language I know has two kinds of things, or more.

It's a riff on the classic and intentionally tongue-in-cheek "everything is a ..." programming meme(s) about guiding or defining principles, nicely summarised at https://wiki.c2.com/?EverythingIsa

It presumably originates from the Pythagorean notion that everything is a number (i.e., everything is mathematical) though everything in a computer is a number. Anything else depends on perspective (and hardware.)

I have a real problem with this. There is absolutely no reason whatsoever to connect a theory of computation with numbers. There are no numbers in the Turing Machine, just symbols on a tape. It does the issue a great disservice to keep going back to implementation trivia such as numbers and bits.

That's correct -- there are no numbers in a theory of computation. There are no numbers in the Turing Machine.

But unless you have an example of some non-standard computational architecture -- like a homebrew computational gadget or some analog computing device (slide rule?) -- you have a computer where everything is a number...

Emmm since you mentioned Turing: " the world's first [**] programmable, electronic, digital computer," was built for "  the cryptanalysis of the Lorenz cipher." It was therefore a computer where most things were characters (ciphers). Ok they might have been represented electrically as numbers (code points) but you're mixing up PhysRep with LogRep.

Not at all. I was intentionally mentioning physical representation, not logical representation.

[**] It wasn't until long after the history books were written that Colossus got recognised as the first programmable computer. Thanks to the stupid British destroying all records (and nearly all the physical remains) on grounds of national security.

Er, bits. Er... transistor state. Uh, a voltage levels...

Bits/transistor state (harrumph you mean thermionic valve state)/voltage levels (mercury tube bubbles) are not numbers. They're only numbers under an interpretation; other interpretations are equally valid.

Yes, but we generally interpret them as numbers. See any core dump / hex dump.

Note that I wrote, "everything in a computer is a number", not "everything in computational theory is a number."

Then how about a data structure "in a computer" representing a Church Encoding of a linked list?

Its physical structure -- i.e., its physical representation -- in a computer is array of numbers / transistor states / voltage levels in a modern computer.

Quote from Dave Voorhis on December 7, 2021, 2:12 pm

Quote from Paul Vernon on December 7, 2021, 12:53 pm

Quote from Dave Voorhis on December 7, 2021, 10:41 am

You can roughly (very roughly) describe type systems on a spectrum from least typeful (#1) to fully typeful (#4):

1. There is no distinction between, or no notion of, interchangeable program components (typically "values") of different kinds.
2. There is a distinction between kinds of interchangeable program components (typically "values"), but "correct" use of them must be enforced by the human language user.
3. There are in-language semantics to enforce and/or act on distinctions between kinds of interchangeable program components but no explicit or implicit 'type' construct.
4. There are explicit or implicit identifications or inferences of a 'type' construct, and enforcement and/or selection based on interchangeable program components (which are typically "values") of specific types.

Unfortunately for the sake of (agreeable) discussion, which ones are considered descriptions of "type system" and which ones are not "type system" is not universally agreed.

Also a great post. Thanks Dave.

I describe 1 as typeless and 2 - 4 as type systems, so I use the usual (but not universal) applied computer science interpretation. You're using the usual software engineering interpretation.

For the record, I am thinking of (I hesitate to say "working on") a language that is a #3 on the above scale. I am considering (still) if it useful to describe it as have a "type system" or not.  Maybe a "type 3 type system" ;-)

Cool. Notably, that puts it in perhaps the most terminologically contentious category, the one where folks will line up on opposite sides of the "type system" vs "untyped" line to brandish virtual pitchforks at each other.

But from a practical tool point of view, it's a good place to be -- whether you call it a type system, an un-typed system, or something else.

Then the next contentious consideration will be whether it is a statically-checked (i.e., errors checked before run-time) #3 or a dynamically-checked (i.e., no errors checked before run-time) #3.

Quote from Paul Vernon on December 7, 2021, 3:48 pm

Quote from Dave Voorhis on December 7, 2021, 2:12 pm

Then the next contentious consideration will be whether it is a statically-checked (i.e., errors checked before run-time) #3 or a dynamically-checked (i.e., no errors checked before run-time) #3.

Errors? Oh, I would not have them. I refer the honourable gentlemen to the answer I gave earlier https://forum.thethirdmanifesto.com/forum/topic/adding-exceptions-to-tutorial-d/?part=2#postid-946082

What I would have, at development, code commit/review/test time and at submit time, would be actionable feedback that might say "Your expression/statement fragment will always [return empty/never return in your lifetime/be semantically really very dubious] given [the database's current constraints/the database's current data/logic/declared semantics]. Is that what you [want/wanted], because that's [what will/is going to/has likely already] happen[ed]?"

or things like "You asserted that the cardinality of the result of this join should be the same cardinality as the left input into the join. I can't prove that will be the case given the current database constraints, but I can see that given the current data (as of the time of this message) your assertion will be true. Up to you if you still want to execute your statement as-is or modify it so that e.g. it does not [update|return] anything if your assertion is not true at run-time."