The Imperium programming language - IPL

[brucehoult]

I have coded up that PL/0 compiler several times

I first did that in 1981, on an Apple ][, first in Pascal and then in machine code.

Fortunately, the CDC 6400 on which the compiler was developed had a 60 bit word and that was enough bits to accommodate the elements.  It gets ugly when you have to compare across 8 or 16 bit or even 32 bit entities.

It's really not a problem.

Set union and intersection are simply OR and AND iterated across the bytes or words of the set. Probably unrolled for any reasonable set, especially as you know at compile time the number of possible elements.

"elt IN set" is simply "(set[elt / WORDSIZE] & (1 << (elt % WORDSIZE))) != 0" where, if WORDSIZE is a power of 2 as is normal today, the / and % are themselves just a shift and an AND. Multi-word sets certainly would be more expensive on oddball word sizes such as 60 on the CDC or 12 on the PDP-8, but they are absolutely fine on 8, 16, 32, 64 bit machines. The worst is if you don't have constant-time single-instruction shifts. Shifting the 1 is the only one with a dynamic shift count, but it's also the simplest, so you could do it using an array of WORDSIZE elements if needed.

[rstofer]

I didn't want to paste a thousand lines of code so I only copied the first few lines just to show the hierarchy.  The remaining code is easy to find at the link.

Certainly the code could have been written without nesting but it is cleaner with it.  Only procedure 'term' can call procedure 'factor' so the nesting cleans up the namespace by default.  Going uphill, 'factor' can call 'expression' just not the other way around.  It's hard to provide this functionality with all procedures at the same level.

[Mechatrommer]

I'll tell you another truly superb book on compiler design, one I used a lot in the past it is Understanding and Writing Compilers by Richard Bornat. It is oriented to recursive descent and is very readable, the author has a deep understanding of machine architectures and code generation practicalities, gives easy to follow examples akin to the stuff Wirth wrote, I doubt I could have gotten as far as I did with my PL/I implementation without this book.

I ordered a copy from alibris.com - $15 including shipping.  I get a lot of used books from Alibris.  I suspect that's the way my library will go as well.

learning on how to make an AI/physics/math/fancy data structure/class library in C or world/3d/game engine is much more fun and gives much more practical use... imho. cheers.

[brucehoult]

I didn't want to paste a thousand lines of code so I only copied the first few lines just to show the hierarchy.  The remaining code is easy to find at the link.

Certainly the code could have been written without nesting but it is cleaner with it.  Only procedure 'term' can call procedure 'factor' so the nesting cleans up the namespace by default.  Going uphill, 'factor' can call 'expression' just not the other way around.  It's hard to provide this functionality with all procedures at the same level.

But with this arrangement 'factor' can also call 'term', which is not permitted by the grammar. So this "functionality" is not actually doing anything much.

You'd be no worse off with top-level functions with 'expression' forward-declared, followed by 'factor', then 'term', then 'expression'.

Trying to enforce grammar rules by nested visibility in this way is not a useful thing to do, firstly because it is only partial, and secondly because the language grammar can be changed at the stroke of a pen ("requirements"), for example by adding a construct that wants to use 'term' or 'factor' somewhere else in the grammar that can't be a full 'expression'.

[rstofer]

learning on how to make an AI/physics/math/fancy data structure/class library in C or world/3d/game engine is much more fun and gives much more practical use... imho. cheers.

I have no artistic capability whatsoever.  Creating assets, particularly characters is out of the question.

I don't play video games - ever; I maxed out at PacMan.  I did look at Blender and Unreal just to get some idea of the workflow but I came to the immediate realization that it takes more than one person to create a game.  A cast of hundreds wouldn't surprise me.

[brucehoult]

learning on how to make an AI/physics/math/fancy data structure/class library in C or world/3d/game engine is much more fun and gives much more practical use... imho. cheers.

I have no artistic capability whatsoever.  Creating assets, particularly characters is out of the question.

I don't play video games - ever; I maxed out at PacMan.  I did look at Blender and Unreal just to get some idea of the workflow but I came to the immediate realization that it takes more than one person to create a game.  A cast of hundreds wouldn't surprise me.

You certainly need a variety of skills, which are not often found in one person.

Back in 2004 I was working for NZ Metservice, working on their TV weather graphics product, helping with modifications for a big new customer: the BBC in the UK.

They had hired a landscape painter, David Frampton, to improve the graphics elements. Which he did. He also gradually picked up a little bit of programming, which he hadn't previously done. After a while he decided to have a go at writing a simple game at home, and decided to start by doing a Mac reimplementation of the ancient "Choplifter" game that was on the Apple ][ of his youth. And C64, DOS, ...

In time he got it working, and started distributing it as shareware, called simply "Chopper", with very modest sales.

A couple of years later the iPhone was announced, and then a SDK for it, and an app store to be opened about six months later.

David decided to try porting Chopper to the iPhone. It worked. He got it in the app store on Day #1, in July 2008, one of very few apps available at the time. It was a pretty big hit. Enough that David paid off his mortgage and quit his job to work full-time on a new game.

Two years later, in July 2010, he released a full 3D update, "Chopper 2". It was an even bigger hit. David sold his house in Wellington and bought a lifestyle block near Napier and started working on another game.

Two and a half years later, in January 2013, he released "The Blockheads", something in the Minecraft genre, but a 2D side-scroller. Another huge hit. He spent another couple of years improving Blockheads before starting on a new game.

After seven years of development, in July 2022, David released "Sapiens". Review: "Could it be the best game of 2022?" 

All with David as the sole developer. The concept. The gameplay. The programming. The AI. The graphics. The music. And all self-funded, starting part time after hours with a salaried job.

David does employ someone to deal with support and forums. Just one person, I think.

[Mechatrommer]

I have no artistic capability whatsoever.

creating compiler that works with your machine, or better than the others, is an art in itself...

[rstofer]

I have no artistic capability whatsoever.

creating compiler that works with your machine, or better than the others, is an art in itself...

And best left to professionals like Niklaus Wirth and the other luminaries of computer science.

Not that it matters but the IBM1130 Fortran compiler was a 27 pass beast.  It had to run in as little as 4k words on a diskless paper tape machine.  The card deck (I'm not sure the source could be on paper tape...) was read into RAM and shared space with the compiler phases.  As the source was digested, the text was replaced with code.

It has a little more breathing room on my 32k word FPGA incantation.  Having a disk helps.  I didn't bother implementing paper tape.

[Sherlock Holmes]

When defining a new language, at the stage where irreversible decisions are yet to be made, there are a number of things we can look at in a fresh light.

One of these is the lexical structure of numeric literals, a tiny change to the token definitions for these means we can easily support optional commas:

Code: [Select]


   rate = 128,000;

   freq = 100,000,000;

   ramp = 12,456.558;


None of these present any problems at all insofar as lexical analysis ("recognizing") is concerned and have a definite pragmatic appeal. Of course there are cultural differences, but since we're not dealing with data but rather programming language notation, the comma is no less reasonable than the period.

[coppice]

When defining a new language, at the stage where irreversible decisions are yet to be made, there are a number of things we can look at in a fresh light.

One of these is the lexical structure of numeric literals, a tiny change to the token definitions for these means we can easily support optional commas:

Code: [Select]


   rate = 128,000;

   freq = 100,000,000;

   ramp = 12,456.558;


None of these present any problems at all insofar as lexical analysis ("recognizing") is concerned and have a definite pragmatic appeal. Of course there are cultural differences, but since we're not dealing with data but rather programming language notation, the comma is no less reasonable than the period.

Commas inserted like that are very confusing in countries which don't use that notation, and especially in countries that use a comma as the decimal point. Software exists in a very international market. Try to keep it as generic as possible. Should we support numbers like 1,00,00,000? Indians would be very happy with that notation. I probably wouldn't.

[bpiphany]

Blatantly stolen, from here https://stackoverflow.com/questions/54009778/what-do-underscores-in-a-number-mean

Code: [Select]

a = 1_00_00  # you do not need to group digits by 3!
b = 0xbad_c0ffee  # you can make fun with hex digit notation
c = 0b0101_01010101010_0100  # works with binary notation
f = 1_000_00.0
print(a,b,c,f)
It's not pretty, and I prefer to specify big number in other fashions myself. But if you have an integer/constant/bitmask with tons of significant digits I suppose it may be helpful.

[Nominal Animal]

Where are [compatible_types and typenameof] useful in C?

typenameof (expression) would correspond to C STRINGIFY(typeof(expression)) if it was supported and actually worked.  Essentially, it allows a library to implement run-time interfaces like
    #define  register_type(expr)  lib_register_type(typenameof (expr), sizeof (expr))
    mytype_id = register_type(type-or-expression);
for registering a type dynamically, for example in a message passing or event library, and
    #define  send(handle, obj)  lib_send((handle), &(obj), sizeof (obj), typenameof (obj))
    result = send(handle, object);
to send not just the storage representation of an object, but also its type name and size, so the recipient knows what it is receiving.

Currently, the two interfaces have to be implemented as something like
    mytype_id = register_type("typename", size);
    result = send(handle, pointer, size, "typename");
which are prone to bugs (especially bitrot), because there is no way to check that typename actually matches the type, for example when due to a bugfix or similar the original type is modified, but not all places where its type is mentioned are correctly updated to reflect the change.

compatible_types matches the GCC/Clang/Intel CC __builtin_compatible_types_p() C extension.  If you support macros, it allows you to do type inference with a compile-time fixed set of types, for example in C,
    #define  TYPECODE(type)  (__builtin_compatible_types_p(type, uint8_t)  ? TYPE_U8  : \
                              __builtin_compatible_types_p(type, int8_t)   ? TYPE_I8  : \
                              __builtin_compatible_types_p(type, uint16_t) ? TYPE_U16 : \
                              __builtin_compatible_types_p(type, int16_t)  ? TYPE_I16 : \
                              __builtin_compatible_types_p(type, uint32_t) ? TYPE_U32 : \
                              __builtin_compatible_types_p(type, int32_t)  ? TYPE_I32 : \
                              __builtin_compatible_types_p(type, uint64_t) ? TYPE_U64 : \
                              __builtin_compatible_types_p(type, int64_t)  ? TYPE_I64 : TYPE_UNKNOWN)
Unlike comparing typenames, on architectures where char, short, int, long, and long long match the above specific-size integer types (they likely shall on all in C23), they too will match to the known types using the above macro.
With this, the type of an expression can be detected and specified at runtime, for example when a compile-time fixed set of types are supported by a library, but the user of that library wants to use their own type names (say, u16 and such).

Note that !strcmp(typenameof (a), typenameof (b)) is not the same as __builtin_compatible_types_p(typeof(a), typeof(b)).  If we consider typedef a b;, the former yields false (0), whereas the latter yields true (1).

Most important use cases for both are about not having to specify the type of an object or an expression, when already supplying that object or expression, because re-stating the type is prone to bugs.  One might think that these are corner cases, but fact is, such bugs are unfortunately common, and could be completely avoided with these two compile-time keywords.

The only thing that annoys me is that the linker does not yet know how to sort those entries at link time.

There is SORT_BY_NAME (or simply SORT) keyword for input section description, does it not work?

I was referring there to sorting the contents of a section, treating it as an array of N structures of size L with a sort key of type T at offset K.

I guess one could use custom dotted name for each entry (.sectionname.key), but it'd only work for keys that are valid section names.
SORT_BY_INIT_PRIORITY works for .sectionname.nonneg section names, where nonneg is a nonnegative integer between 0  and 65535, inclusive.
(I haven't even found a way yet to generate unique section name suffixes that work (are unique) across source and object files.)

The reason it would be nice for the linker to be able to do this for a small number of key types, is to keep the darn relocation entries in sync with the contents.
I know, I should just stop whining, and go do it portably using bfd (part of binutils) or libelf (non-binutils ELF library).

[Sherlock Holmes]

When defining a new language, at the stage where irreversible decisions are yet to be made, there are a number of things we can look at in a fresh light.

One of these is the lexical structure of numeric literals, a tiny change to the token definitions for these means we can easily support optional commas:

Code: [Select]


   rate = 128,000;

   freq = 100,000,000;

   ramp = 12,456.558;


None of these present any problems at all insofar as lexical analysis ("recognizing") is concerned and have a definite pragmatic appeal. Of course there are cultural differences, but since we're not dealing with data but rather programming language notation, the comma is no less reasonable than the period.

Commas inserted like that are very confusing in countries which don't use that notation, and especially in countries that use a comma as the decimal point. Software exists in a very international market. Try to keep it as generic as possible. Should we support numbers like 1,00,00,000? Indians would be very happy with that notation. I probably wouldn't.

Thanks for the remarks. If you do consider the cultural differences then clearly we should not restrict the decimal point to being a PERIOD yet we do, universally in all programming languages. If we are prepared to restrict the decimal point to a PERIOD then we should also - if we're being consistent - be equally prepared to accept the COMMA as the thousands separator surely? Remember too this will be optional, there'll be no compulsion to use a comma at all, only the ability for the language to tolerate if it is present.

Given that programming languages (almost) universally reflect the English speaking, Western culture (keywords are all English for example) extending that to the optional inclusion of the COMMA seems entirely reasonable to me.

However there are standards/recommendations for this and the general feeling seems to be that only SPACE should be allowed as the thousands/grouping separator.

So perhaps we could do something else, something more flexible, examples:

123,456.87
123 456.87
1,23,456.87
1 23 456.87
123 456,87

The rules for this could simply be that the decimal separator be defaulted to PERIOD with the option to set it to COMMA. Then any separators be entirely optional and allowed to be SPACE COMMA PERIOD UNDERSCORE or APOSTROPHE so long as it is not the same as the defined separator.

Any of these legal separators have no influence on the numbers actual magnitude, they are purely a visual aid so will ultimately be simply removed when the token is created. This might all look rather long- winded but we either disregard cultural variations and impose Western English rules (12,345,678.965) or we accommodate cultural variants to some reasonable degree. Since the separator carries no weighting or anything (it just a visual aid) so in other words allow not only _ as some languages do but let that also be SPACE, COMMA etc if desired, perhaps insisting too that a separator must be alone, one cannot have two commans or two underscores etc.

[Sherlock Holmes]

Blatantly stolen, from here https://stackoverflow.com/questions/54009778/what-do-underscores-in-a-number-mean

Code: [Select]

a = 1_00_00  # you do not need to group digits by 3!
b = 0xbad_c0ffee  # you can make fun with hex digit notation
c = 0b0101_01010101010_0100  # works with binary notation
f = 1_000_00.0
print(a,b,c,f)
It's not pretty, and I prefer to specify big number in other fashions myself. But if you have an integer/constant/bitmask with tons of significant digits I suppose it may be helpful.

Yes, that language (like C#) tolerates any number of UNDERSCORE chars placed at any position. The base indicator can though be a trailing character rather than leading. I'm also finding that another separator for that base character also makes the text visually easier om the eye, consider then (and combining this with the earlier posts about "thousands" and so on):

Code: [Select]


a = 10:H; // 16 in hex
b = 1245 77AC:H; // also hex with optional separator
c = 1001 0110:B;  // binary with space
d = 123,456.77;   //  conventional decimal with separator
e = 123,456.77:D // explicit base - optional.


I'm also inclined to insist that hexadecimal must be uppercase too for consistency and that the base char also be uppercase.

It looks like all of these can be accommodated without any problems (in a new language that is) but if we do allow COMMA as a separator we would need to remove it as the separator for arguments:

Code: [Select]


call initialize(100,345.88,severity);


That is ambiguous now, it could be 100 and 345.88 and severity or it could be 100,345.88 and severity, that is two args or three args...

[Sherlock Holmes]

I'm of the opinion that the comma is too ubiquitous to abandon as a separator in things like argument lists. So the separator for large numbers should be either single spaces or single underscores, and the decimal point is always the period. The position of the separator(s) is arbitrary.

Hexadecimal should be flexible case too, though mixing case should be an error, the base specifier as COLON followed by a single letter seems fine, and that can be upper or lower case.

This strikes me as reasonable...

[coppice]

If you do consider the cultural differences then clearly we should not restrict the decimal point to being a PERIOD yet we do, universally in all programming languages.

That's not quite true. Have you ever seen French or German Fortran? There was a lot of localisation of computer languages in the early days. The keywords were localised. Things like decimal points and other formatting issues were localised. However, it made such a pain of passing stuff around in multi-national organisations that by the end of the 60s computer languages has pretty much abandoned this approach.

[Sherlock Holmes]

If you do consider the cultural differences then clearly we should not restrict the decimal point to being a PERIOD yet we do, universally in all programming languages.

That's not quite true. Have you ever seen French or German Fortran? There was a lot of localisation of computer languages in the early days. The keywords were localised. Things like decimal points and other formatting issues were localised. However, it made such a pain of passing stuff around in multi-national organisations that by the end of the 60s computer languages has pretty much abandoned this approach.

You are absolutely right, thanks, I stand corrected, Algol 68 too it seems.

I was reading too of this rather ambitious project Citrine.

It would be very easy indeed to support alternatively spelled keywords (especially here where the grammar has no reserved words) but I'd consider that not a "phase 1" thing for me!

So far as the numeric notation goes, I've settled for this, these are all examples of stuff that the lexer is recognizing just now:

Code: [Select]


FA068AB7:H // hex literal
FA06 8AB7:H // hex literal
FA06_8AB7:H // hex literal
FA06   __ 83BC  8AB7:H // hex literal (I'm going to reject such a monster though either have space OR underscore and no more than one at a time)

FA068AB7 // ordinary identifier. An identifier composed wholly of hex characters should perhaps be disallowed, inadvisable...

FA06 8AB7  :  H // hex literal


Admittedly this isn't a huge chunk of functionality but considering that MCU developers regularly have to code decimal, hex and binary literals, this kind of flexibility in how to express them can only be a good thing.

[rstofer]

It would be very easy indeed to support alternatively spelled keywords (especially here where the grammar has no reserved words) but I'd consider that not a "phase 1" thing for me!

There was at least one Fortran compiler where DAMNITALL could be used for DIMENSION - I guess the counted 9 chars starting with D and called it good.  They could almost get away with that as long as all declarations had to precede any executable statements.  Maybe they looked for the 3rd char to be M, I don't know...

So far as the numeric notation goes, I've settled for this, these are all examples of stuff that the lexer is recognizing just now:

Code: [Select]


FA068AB7 // ordinary identifier. An identifier composed wholly of hex characters should perhaps be disallowed, inadvisable...



Including FACE?  Seems a reasonable variable name for image recognition.

I can't say I'm a fan of the proposal.  I find the C notation more than adequate for common bases and I'm not too sure there is any utility for other bases.  Even base 8 is going the way of Digital Equipment Corporation - remember them?  Realistically, for coding we have bases 2, 8 and 16. We run out of English language letters before we can do base 32 (fortunately).

I'm also not a fan of the parser having to look so far ahead to determine whether there is a numeric constant or just another variable. Having numerics start with a decimal digit seems reasonable.

One thing about Pascal syntax, the compiler knew exactly what set of symbols could come next at every step of parsing.  No backtracking that I know of.

I do like being able to use underscores with long numeric strings but that's as far as I would push it.  OTOH, I'm not creating the language...

[Sherlock Holmes]

It would be very easy indeed to support alternatively spelled keywords (especially here where the grammar has no reserved words) but I'd consider that not a "phase 1" thing for me!

There was at least one Fortran compiler where DAMNITALL could be used for DIMENSION - I guess the counted 9 chars starting with D and called it good.  They could almost get away with that as long as all declarations had to precede any executable statements.  Maybe they looked for the 3rd char to be M, I don't know...

So far as the numeric notation goes, I've settled for this, these are all examples of stuff that the lexer is recognizing just now:

Code: [Select]


FA068AB7 // ordinary identifier. An identifier composed wholly of hex characters should perhaps be disallowed, inadvisable...



Including FACE?  Seems a reasonable variable name for image recognition.

I can't say I'm a fan of the proposal.  I find the C notation more than adequate for common bases and I'm not too sure there is any utility for other bases.  Even base 8 is going the way of Digital Equipment Corporation - remember them?  Realistically, for coding we have bases 2, 8 and 16. We run out of English language letters before we can do base 32 (fortunately).

I'm also not a fan of the parser having to look so far ahead to determine whether there is a numeric constant or just another variable. Having numerics start with a decimal digit seems reasonable.

One thing about Pascal syntax, the compiler knew exactly what set of symbols could come next at every step of parsing.  No backtracking that I know of.

I do like being able to use underscores with long numeric strings but that's as far as I would push it.  OTOH, I'm not creating the language...

You're right FACE is entirely reasonable!

There's no parsing here at this stage, all of these tokens can be recognized with an FSM based lexical analyzer (no stack involved), this stuff gets done well before the parser sees anything.

Speaking personally, I've always found it a contrivance to use underscores as a numeric separator (as in C#), as soon as one does that then the thing looks like an identifier (to me) even though it isn't. Then we have the leading 0x or 0b to designate the base, I mean leading? why must there be a "0" at all? and what does "x" have to do with 16? Many of these practices are due to the fact that C's grammar and lexical structure impose unhelpful constraints, this is a major reason I am critical of it's influence.

However, it would be sensible to accommodate that practice, C is ubiquitous so both the C "way" of representing these and the alternative are easily supported.

Here's some chat about this.

[rstofer]

Another use for the underscore at less uniform locations is when we want to separate fields in a value being sent to a control register.  Some fields are 1 bit, some are 3 bits, and so on.  Separating the fields could be quite handy.

[newbrain]

Just to make sure some wheels do not get reinvented too much, C23 provides:
* typeof
* bit-precise integer types
* binary literals, and a digit separator (')
* (optional)decimal floating point types

[Sherlock Holmes]

Just to make sure some wheels do not get reinvented too much, C23 provides:
* typeof
* bit-precise integer types
* binary literals, and a digit separator (')
* (optional)decimal floating point types

This is quite helpful. Their analysis is interesting to study and it indicates the perceived utility of the concepts and ideas.

I don't see the purpose of typeof here though. In C# a Type is a class representing a type, metadata describing a type. The typeof in C# gets that type from a type's name. In a generic setting typeof(T) returns the actual runtime type represented by T.

In C every type is known at compile time, there are no 'objects' who's type we cannot know, so what's it for?

[Sherlock Holmes]

Something a new language needs is a precisely defined means of initializing variables and structure instances. I've seen { 0 } can do this but only at the point of declaration it seems.

C# has a default() language function, so something like that makes a lot of sense. This would initialize every member field (recursively) to a value suitable for it's type.

[Siwastaja]

Something a new language needs is a precisely defined means of initializing variables and structure instances. I've seen { 0 } can do this but only at the point of declaration it seems.

Again, you assume the worst when you simply don't know.

But I can assure you, you can set a struct to {0} any time you want; this is not limited to the initialization at point of declaration.

What may confuse the young players is, because C evaluates right side of expression "on their own" (which simplifies rules and removes guesswork), the compiler can't know the type from {0} alone. In an initializer, it is known (from the variable you are initializing), but in assignment, you need to tell the type:

typedef struct
{
    int asdf;
    int qwerty;
} our_type_t;

our_type_t object = {0};
object = (our_type_t){0};

[Sherlock Holmes]

Something a new language needs is a precisely defined means of initializing variables and structure instances. I've seen { 0 } can do this but only at the point of declaration it seems.

Again, you assume the worst when you simply don't know.

But I can assure you, you can set a struct to {0} any time you want; this is not limited to the initialization at point of declaration.

What may confuse the young players is, because C evaluates right side of expression "on their own" (which simplifies rules and removes guesswork), the compiler can't know the type from {0} alone. In an initializer, it is known (from the variable you are initializing), but in assignment, you need to tell the type:

typedef struct
{
    int asdf;
    int qwerty;
} our_type_t;

our_type_t object = {0};
object = (our_type_t){0};

Thank you for the helpful (if slightly condescending) clarification.

The restriction is bizarre though, surely the compiler can easily infer that cast itself, but such is C. I suppose one could craft a macro for this initialization, one that uses typeof.