Hacker News Reader

Comment by akkartik | Hacker News Reader

Wild and whacky idea: has anyone ever built a language with separate types for ordinal/cardinal numbers and nominal numbers? The idea would be that with nominal numbers you don't care about the precise result of individual calculations, just statistical properties like determinism, distribution, etc. So arithmetic on nominal numbers would be permitted to overflow, as operations are just various ways to jump from one nominal to another. However, most numbers would be ordinals/cardinals, and any overflow when generating an ordinal/cardinal would be considered an error.

https://en.wikipedia.org/wiki/Nominal_number

View on HN

What can you usefully do with a nominal number, besides input/output and comparing two of them for equality? I don't think you need language support here, library support should suffice, unless I'm missing something.

I was imagining that you could do everything with nominals that you normally do with integers. Arithmetic saving results in nominal numbers would just disable overflow checking. This would allow all operations involving regular numbers to double down and perform extremely strict overflow checking.

The question is (and I think was), what arithmetic do you do with numbers whose values don't matter and what concrete value they happen to have is purely accidental and arbitrary and unimportant.

From the OP, examples of intentional overflow are "..hashing, cryptography, random number generation, and finding the largest representable value for a type."

Which are not categorical variables? Those all are examples using actual numbers, meaning the values matter.

> Nominal numbers or categorical numbers are numeric codes, meaning numerals used for identification only. The numerical value is in principle irrelevant, and they do not indicate quantity, rank, or any other measurement.

You talked about nominal numbers up to (but excluding) this post.

"nominal" means "in name only", so it's a "number", not a number. It just happens to have the same name as a number with a value.

Yes, I'm still calling them nominal numbers, but you can give whatever name you want for "I don't care what the precise results of arithmetic are." I'll stop here because there's nothing I hate more than pedantic arguments about semantics.

It isn't pedantic. You asked about arithmetic of nominal numbers, which makes no sense at all.

    >  "I don't care what the precise results of arithmetic are."

This is wrong! That is NOT what "nominal numbers" are!

I already quoted it, "nominal numbers" have no value!

You are absolutely right though: This conversation has lead nowhere. I'm not sure your identification of who is to blame is correct though.

You asked about nominal numbers, and when asked for details your examples all are about actual numbers. When I point that out your reaction is to be offended. How mature.

You can't talk about "nominal numbers" and then be miffed that people don't understand that you are not actually talking about nominal numbers at all! I only come to understand that now. Tip: Don't talk about water when you mean sand, and then act confused when someone brings you water instead of sand.

If I choose to add my phone number and yours, who's going to stop me? Would the universe explode? Would my phone number not be nominal anymore? It's a sort of "if a tree falls in the forest" question. Regardless of whether you're right or wrong (I just read the wikipedia page and didn't see anything about arithmetic, but maybe you have a phd in math), the essence of pedantry is to continue to insist I used the wrong word even after you understand what I meant.

Again: Nominal numbers have no values. So what "arithmetic" do you want to do? There is no overflow. Because there is no arithmetic with nominal numbers.

The examples you quoted above are NOT using nominal numbers. Those are ACTUAL numbers. Those are modulo operations - that is NOT "nominal numbers".

Personal attacks won't help, they never do in any discussion. You should seriously consider changing your discussion style.

If your question was about modular arithmetic, it confuses two different issues. It would be just a coincidence if the highest number representable with the given amount of bits happens to be the same number you want for your modulo operations. Those are only accidentally related issues.

Hm, I'm still missing something here, but I think your comment about phone numbers might be the key to the mystery, so let's go with that for now.

If you choose to add two phone numbers, I think we both agree that the phone numbers are still nominal. But I think we also agree that you have computed nonsense. There's nothing you can do with that sum. Which naturally raises the question: why should a programming language support this operation?

Come on guys, you're getting hung up on the wrong aspect here. I'm starting with precisely the operations the OP mentions as requiring wraparound overflow support: computing digests, hashes, random numbers, things like that. Currently we use unsigned numbers when we require overflow, but things are still extremely error-prone as the OP shows. So my thought was to come up with a new dichotomy: instead of signed vs unsigned, just ask for whether you want wrap-around overflow or not. Pretty please can we just forget I ever used the word 'nominal'?

If you think adding two phone numbers can have no possible useful application, what do you say to taking strings of text, converting them to numbers, and repeatedly folding them over each other to compute a cryptographic digest? You're right that it is meaningless in the context of the original domain, but it clearly has application. The two are distinct ideas.

But overflow is a hardware issue - we run out of bits. The number range of a modulo operation on the other hand can be anything. That's why I said there are two issues that you seem to mix. Don't forget that overflow (running out of bits) is signaled by a flag for the CPU register where it's happening (accessible to a programmer only when using assembler).

So I'm not sure what your plan really is here. To support modulo operations in hardware by using the limited bits of the registers limits your modulo operations to the size of the registers. If you are talking about purely software operations and not the hardware - I'm not sure - well, that exists. We already have modulo operations in all programming languages, it's not missing. And if you are talking about the hardware support, you are free to ignore the flags (which you only get to access in assembler anyway) and use the registers as a kind of "implied modulo", that's the point of the discussion that when overflow happens your code won't notice.

Okay, finally I get it! As far as I know, Rust has a few types in the stdlib that are guaranteed to overflow, that you can use if that's what you want. C# has something even more interesting:

    checked(a+b) // crash on overflow
    unchecked(a+b) // wrap on overflow
    a+b // use the default of the surrounding context

The global default is provided by a compiler switch. Here's the thing though: the default setting of that compiler switch is to wrap on overflow. Even in debug mode! And you yourself identified the cause: most of the time, you're not doing crypto and such; most of the time, you do not want wrapping. But if you make overflow checking "opt-out" instead of "opt-in", the program slows down.

Most interesting. Yeah, I'm inclined to just eat that one-time slowdown. We've all anchored (https://en.wikipedia.org/wiki/Anchoring) on running our programs without these runtime checks, so that our apps seem slower with them. But if we take on that one-time cost the programs will eventually get faster with faster hardware, better compilers, more cores, etc. And we'll be safe from these issues for ever more.

Thanks for letting me know my idea finally got across. I was massively under-estimating its subtlety.

> Yeah, I'm inclined to just eat that one-time slowdown.

Maybe eventually the world will agree with you. We already eat the slowdown that comes with bounds-checked arrays. And indeed, compilers are getting better at removing that bit of overhead, compared to, say, the 1970s.

Since I have you here: I teach programming with this portable, safe assembly language (as opposed to the portable, expressive assembly language that was C). It has bounds-checked arrays. It always initializes variables. The type system is strong, so you can't ever create an address out of a number. It compiles with -ftrapv so any signed overflow immediately triggers an unrecoverable error. It has pointers and requires manual memory management, but it has refcounts so you can't ever have a use-after-free error. As a consequence any copy of an address incurs some overhead to update refcounts, and any copy of a struct incurs even more overhead to update refcounts of all addresses contained within. Between initialization, bounds checking, overflow checking and refcounting, I think I've pretty much eliminated all sources of undefined behavior.

http://akkartik.name/post/mu

http://akkartik.name/about

https://github.com/akkartik/mu

I've superficially glanced at mu. It seems to have even more awesome stuff than I realized. But still: you're basically programming in glorified assembly. You can't add three numbers without splitting the thing into two statements. Is this really a pleasant way to program? I think this may be a good way to teach programming, but only because no one writes big programs when starting out. On the other hand, you claim to have written the UI in mu itself, so maybe I'm just plain wrong here. (Or did I misread that?)

You're right that I wouldn't want the whole world to program this way.

That said, it's been surprisingly ergonomic. If it had a compiler and could generate binaries, and if it had parity in libraries with C, I think I would strongly prefer using it to C. The massively increased safety is worth giving up a lot of expressivity for, IMO. No comparison with HLL languages for prototyping, of course. Eventually I hope to get the usual HLLs reimplemented atop it. One subtle point is that since it's refcounted at the Assembly level, any language built atop it requires minimal GC support.

The fact that it's Assembly has caused some confusion with others, so I want to point out that:

a) you can add any number of numbers in a single instruction; that gets handled behind the scenes. Many instructions are variadic where it makes sense.

b) you don't need push/pop/call to call a function, function calls look just like primitive operations.

c) Mu knows about types, so it knows how to allocate them, how to print them, and (eventually) how to serialize/unserialize them. These things can be overridden, but they work out of the box for any new types you create.

d) Mu supports generic types. Here's a generic linked-list, for example: http://akkartik.github.io/mu/html/064list.mu.html. Types starting with underscores are type parameters.

e) You get structured programming by default using the break and loop instructions which translate to jumps just after the enclosing '}' and '{' label, respectively. Factorial in Mu looks surprisingly clean: http://akkartik.github.io/mu/html/factorial.mu.html

What's common to these features is that I could imagine implementing them in a compiler using just machine language and Mu. What I'm trying to avoid is having to write a complex optimizer. These features (I think) don't massively increase the impedance mismatch between Mu and machine code; they can be implemented with basically glorified search-and-replace.

The Mu editor is built in Mu, yes. That's just because I don't have a HLL yet. It's not to say that I think everyone should build apps only in the Assembly layer. It's a little like the early days of C and Unix: until the language got stable people built the original versions of compiler and OS in Assembly. But they were eventually able to move to C.

Okay, factorial and linked list changed my mind. This is way more ergonomic than I gave it credit for. It doesn't seem to quite agree with /post/mu; in particular, I see no usage of next-ingredient and instead I see the typical function prototypes you seem to be critiquing. Does this mean next-ingredient is gone, or is it optional or...?

Ah, thanks for the feedback! I'd written that article before Mu got function headers, and never gone back to re-read it.

a) next-ingredient is still around, and I still teach it first before graduating students to headers.

b) Headers get translated to next-ingredient calls behind the scenes, but without the need to type-check ingredients at runtime.

c) You might still choose to use next-ingredient if you want to implement optional arguments, or variadic functions. A weird one is interpolate (in http://akkartik.github.io/mu/html/061text.mu.html), which scans through its arguments twice, first to compute the size of the array to allocate to hold them, and then a second time to copy them over. Since calls to next-ingredient can get arbitrarily complex, Mu doesn't bother type-checking them. It just moves the type-checking for explicit calls to next-ingredient to run-time.

I'll update that post. Thanks again.

Cool. Two more silly questions. (1) How fast is mu these days? Is it roughly competitive with CPython? (2) You mentioned it would be nice to have a compiler someday. It occurred that maybe something like the JVM would be closed to the existing semantics than x86. It's also strongly typed and has bounds-checked arrays and stuff. Hm. I guess that's not a question. Never mind.

Not silly at all!

(1) It's a good question. I think small benchmarks will likely be much slower in Mu since Python probably has optimized primitives for the common things whereas Mu is still (naïvely) interpreted. On larger apps I think the gap might come down, since Python will start relying more on unoptimized primitives. But I should probably measure at some point..

(2) Lol. I actually modeled Mu's on JVM to some extent, so it's intended to be a better replacement of that layer of the stack, something that compiles down to native rather than relying on a bytecode interpreter, and also something that is designed with higher-order functional programming in mind, as well as generics out of the box (so no type erasure and so on).

Thanks again!

Reply on news.ycombinator.com