Comparison with oberonc

[lboasso]

H Andreas,

To continue our conversation started as email, I tried to compile your examples with oberonc that implements imports without the restriction on the import order.

To better test the semantic of the imports I added bodies to all the client modules. Like that we are sure that export an re-export work as expected without breaking type rules:

MODULE X;
  TYPE T0* = RECORD i: INTEGER END ;
END X.

MODULE M0;
  TYPE T0* = RECORD i: INTEGER END ;
END M0.

MODULE M1;
  IMPORT M0;
  TYPE T1* = RECORD (M0.T0) j: INTEGER END ;
  VAR a: M0.T0;
      b: T1;
BEGIN
  a := b
END M1.

MODULE M2;
  IMPORT M1;
  TYPE T2* = RECORD (M1.T1) k: INTEGER END ;  (*indirectly imports M0.T0*)
  VAR a: M1.T1;
      b: T2;
BEGIN
  a := b
END M2.

MODULE M3;
  IMPORT X := M0, M2, X;
  TYPE T3* = RECORD (M2.T2) k: INTEGER END ;  (*indirectly imports M1.T1 and M0.T0*)
  VAR a: M2.T2;
      b: T3;
      c: X.T0;
BEGIN
  a := b;
  c := b
END M3.

MODULE M4;
  IMPORT Y := M0, M0;   (*importing a module M0 under two different names is never allowed*)
  VAR a: Y.T0;
      b: M0.T0;
BEGIN
  a := b
END M4.

MODULE M5;
  IMPORT Z := M0, M0 := M1;
  VAR a: Z.T0;
      b: M0.T1;
BEGIN
  a := b
END M5.

MODULE M6;
  IMPORT M0 := X, M1;
  VAR x0: M0.T0; x1: M1.T1;  (*M1 indirectly imports M0.T0*)
BEGIN x0 := x1
END M6.

oberonc compiles successfully all the modules but:

• M3: I get a multiple definition for the identifier X because of IMPORT X := M0, M2, X;
• M6: I correctly get an illegal assignment

I argue that M4 should compile, an alias is indeed a different name for the same object. This is true also for type alias as well. e.x. TYPE int = INTEGER.

M5 is debatable, it still makes sense that compiles successfully.

In addition oberonc compiles with no error the following:

MODULE A1; TYPE P1* = POINTER TO T1; T1* = RECORD x*: INTEGER END; END A1.
MODULE A2; IMPORT A1; TYPE P2* = POINTER TO T2; T2* = RECORD(A1.T1) y*: INTEGER END; END A2.
MODULE A3; IMPORT A1, A2; VAR x1: A1.P1; x2: A2.P2; BEGIN x1 := x2; END A3.
MODULE A4; IMPORT Y1 := A1, Y2 := A2; VAR x1: Y1.P1; x2: Y2.P2; BEGIN x1 := x2; END A4.

I am not sure how to best support these corner cases in the original FPGA Oberon. It feels like the proposed changes are a bit hacky and I wonder how many other corner cases we are not catching. Ideally we should pay the price for increased complexity in the module system and lift the restriction on the import order as I did for oberonc.

[andreaspirklbauer]

I have checked out your solution at https://github.com/lboasso/oberonc. It uses module tables 'GModtab' and 'LModtab' and creates separate entries for aliases via InsertObject. I guess I could adopt this idea, but it would add some complexity to the FPGA Oberon compiler..

[lboasso]

Yes that is right. As I mentioned before this change increased the complexity of the compiler, but overall I think it was worth it. See here for the diff of when I introduced the change. Later commits fixed a few bugs.

[andreaspirklbauer]

Luca: The new ORB9 should now in essence behave like your oberonc, i.e. any number of alias names are allowed to refer to one and the same module & the following error codes are returned:

• M3 now returns a "mult def" error
• M4 now compiles
• M5 now compiles
• M6 now returns an "illegal assignment" error

[lboasso]

I am not sure how ORB9 could really support re-exported types. You removed the "invalid import order", restriction but at the same time you don't have local and global tables to make sure you always use the primary instance of a module.
Would the following test work?

MODULE TestImport120;
  TYPE
    TypeA* = INTEGER;
    TypeB* = RECORD b: CHAR END;
END TestImport120.

MODULE TestImport121;
  IMPORT I := TestImport120;

  TYPE
    TypeC* = I.TypeA;
    TypeD* = I.TypeB;
END TestImport121.

MODULE TestImport122;
  IMPORT TestImport121, X := TestImport120;

  VAR
    a: X.TypeA;
    b: X.TypeB;
    c: TestImport121.TypeC;
    d: TestImport121.TypeD;

BEGIN
  c := a;
  b := d
END TestImport122.

I have additional tests in here.
They are grouped as follows, each line is a test case composed of several modules

{
      {"TestImport00", "TestImport01"},
      {"TestImport10", "TestImport11"},
      {"TestImport20", "TestImport21", "TestImport22"},
      {"TestImport30", "TestImport31"},
      {"TestImport40", "TestImport41", "TestImport42"},
      {"TestImport50", "TestImport51", "TestImport52", "TestImport53"},
      {"TestImport60", "TestImport61", "TestImport62"},
      {"TestImport70", "TestImport71"},
      {"TestImport81", "TestImport82", "TestImport80"},
      {"TestImport90", "TestImport91"},
      {"TestImport100"},
      {"TestImport120", "TestImport121", "TestImport122"},
      {"TestImport130", "TestImport131"},
    }

[andreaspirklbauer]

Hi Luca,

I have added ORB10.Mod which re-introduces the "invalid import order" restriction.

Now the following error message is produced for your test programs:

OR Compiler  8.2.2020
  compiling TestImport120 new symbol file     5    20 FFFE4E4F
  compiling TestImport121 new symbol file     5    20 ACAC2E4B
  compiling TestImport122
  pos 66 invalid import order
  pos 86 undef
compilation FAILED

So the restriction is still there, but at least the error message is now as in FPGA Oberon.

In order to eliminate the restriction itself, one would need to either (a) use a module table, like you do in your compiler or (b) somehow merge the object lists (in mod.dsc) of directly and indirectly imported modules when a module is imported directly after it has been imported indirectly.

[StefanoFerrari]

I think OP2 (Oberon-2 portable compiler) by R.Crelier use the 'GModtab' and 'LModtab' solution

[andreaspirklbauer]

Multiple Modula-2 and Oberon compilers have made use of the GModtab and LModtab in various forms in the past. OP2 is one of them.

[lboasso]

Among the proposed solutions, I like ORB10.Mod best: it keeps the complexity to a minimum while still being in the spirit of FPGA Oberon. Also note that in the happy (and common) code path you do just one expensive string comparison.

[andreaspirklbauer]

Luca, I have now added ORB11 and ORP12. Just as a proof of concept. It removes the restriction on import order, i.e. it is now no longer necessary that explicit imports come before re-imports.

But I cannot run your test programs without heavy editing (the contain built-in WriteInt etc)

[lboasso]

I kept WriteInt and WriteChar and a few others for testing/bootstrapping purposes. You could add support for them in your compiler but it would take more time than to do the edit or commenting out those calls from the tests

[andreaspirklbauer]

Luca,

I have now uncommented the WriteInt, WriteChar statements. Now all modules in the list below:

{
{"TestImport00", "TestImport01"},
{"TestImport10", "TestImport11"},
{"TestImport20", "TestImport21", "TestImport22"},
{"TestImport30", "TestImport31"},
{"TestImport40", "TestImport41", "TestImport42"},
{"TestImport50", "TestImport51", "TestImport52", "TestImport53"},
{"TestImport60", "TestImport61", "TestImport62"},
{"TestImport70", "TestImport71"},
{"TestImport81", "TestImport82", "TestImport80"},
{"TestImport90", "TestImport91"},
{"TestImport100"},
{"TestImport120", "TestImport121", "TestImport122"},
{"TestImport130", "TestImport131"},
}

compile EXCEPT for one, namely TestImport142.Mod which yields the following error.

pos 103 external base type not implemented

when trying to compile the declarations

TYPE PtrRec1 = POINTER TO I1.Rec1;
VAR r0: POINTER TO I0.Rec0;

This, however, is the normal behaviour in FPGA Oberon (if I move the pointer type declarations for PtrRec0 to TestImport140 and for PtrRec1 to TestImport141, then TestImport142 also compiles)

[lboasso]

You made very good progress! The new algorithm looks reasonable, maybe we can try to come up with more tests to rule out bugs and get some confidence on the implementation. I can help you with that

…

On Fri, Feb 14, 2020, 09:16 Andreas Pirklbauer ***@***.***> wrote: Luca, I have now uncommented the WriteInt, WriteChar statements. Now all modules in the list below: { {"TestImport00", "TestImport01"}, {"TestImport10", "TestImport11"}, {"TestImport20", "TestImport21", "TestImport22"}, {"TestImport30", "TestImport31"}, {"TestImport40", "TestImport41", "TestImport42"}, {"TestImport50", "TestImport51", "TestImport52", "TestImport53"}, {"TestImport60", "TestImport61", "TestImport62"}, {"TestImport70", "TestImport71"}, {"TestImport81", "TestImport82", "TestImport80"}, {"TestImport90", "TestImport91"}, {"TestImport100"}, {"TestImport120", "TestImport121", "TestImport122"}, {"TestImport130", "TestImport131"}, } compile EXCEPT for one, namely TestImport142.Mod which yields the following error. pos 103 external base type not implemented when trying to compile the declarations TYPE PtrRec1 = POINTER TO I1.Rec1; VAR r0: POINTER TO I0.Rec0; This, however, in FPGA is the normal behaviour (if I move the pointer type declarations for PtrRec0 to TestImport 140 and for PtrRec1 to TestImport141, then TestImport142 also compiles) — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#1>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAVJAWZ2XV73QYOP6Z74RRDRC3GYVANCNFSM4KSG3QUA> .

[andreaspirklbauer]

That would be great! You obviously have deep knowledge about this wonderfully exciting topic, having done an implementation using the GModtab approach inspired by Griesemer et al or OP2.

I think we can get it down to ~20-25 lines more relative to FPGA Oberon. Which would be acceptable to me. Provided we can harden it such that it truly works in all cases.

Also, now that the initial phase doesn't actually do any importing, perhaps we can take the "IF non THEN" out of ORB.ThisModule to make the code simpler and more readable.

[andreaspirklbauer]

Hi Luca,

ORB12 does the same as ORB11, but procedure "ThisModule" has been split into "Import" (called only initially when parsing the IMPORT statement) and "Reimport" (called from within InType).

This makes it more readable and simpler (we're down to ~25 lines more than FPGA Oberon). It should also make it easier to design test programs that check specific cases.

[andreaspirklbauer]

Added ORB13.Mod = a ONE-pass solution with NO restrictions on import order.

This solution solves the same problem as ORB12.Mod, but does not first build the entire module list to determine upfront which modules are re-imported and which are explicitly imported.

Instead, ORB13.Mod stitches together the implicit imports and later explicit ones, if needed. This means that in the event that a module M is first implicitly imported (re-imported types) and later explicitly imported (=imported in full) as well, this solution "merges" the two lists.

This is rather cumbersome. The main reason is that we must simultaneously NOT invalidate any pointers to already re-imported types, and at the same time read the entire symbol file.

PS: All test programs TestImport00.Mod - TestImport151.Mod that you have listed above (with TestImport142 slightly adapted to comply with FPGA Oberon), compile correctly with both ORB12/ORP12 and ORB13.

[lboasso]

Hi Andreas,
I tried to create additional tests that would trigger edge cases in the implementation, but they ended up being equivalent to existing tests. That part of my codebase has already 100% test coverage.
Have you tried to compile the following tests from my repository?

TestCyclicImport00A
TestCyclicImport01A
TestCyclicImport00B -> "Error: recursive import"

TestCyclicImport00A
TestCyclicImport01B
TestCyclicImport00B -> "Error: recursive import"

TestCyclicImport10A
TestCyclicImport12
TestCyclicImport11
TestCyclicImport10B -> "Error: recursive import"

I remember that I had to add extra support for it, see the comment in this commit

[andreaspirklbauer]

Hi Luca,

ORB12CheckCyclicImports (two-pass variant) and ORB13CheckCyclicImports (single pass variant) now detect cyclic imports in ALL cases, i.e. both in the case where imported or re-imported types of the involved modules are imported and also when they are not re-exported.

I had to add a few lines that (effectively) do what your "module anchors" do. So this comes essentially as an after-thought to ORB12 and ORB13, and therefore cannot be recommended.

This small experiment has convinced me that if one also want to check for cyclic module imports at compilation time, your "global/local module table" approach that you employ in your oberonc compiler is indeed the more appropriate one.

But one could also argue that letting the module loader enter an endless recursion when cyclic module imports are present in any given module hierarchy, is also an adequate solution for the following reason: Cyclic module imports have to be actively constructed through a tricky sequence of editing and compilation steps - as you have done in your TestCyclicImport00A, etc. But normally, they just don't occur. This could be debated of course..

Here are some stats (sloc means "source lines of code", i.e. not counting empty lines):

ORB00.Mod (=FPGA Oberon, not a correct and also not a full solution)
ORB07.Mod +3 lines relative to FPGA Oberon (=correct, more restrictive, quirks)
ORB08.Mod +6 lines relative to FPGA Oberon (=correct, more restrictive, cleaner)
ORB10.Mod +21 lines relative to FPGA Oberon (=one-pass, with import order restriction)
ORB11.Mod +24 lines relative to FPGA Oberon (=one-pass, with no import order restriction)
ORB12.Mod +25 lines relative to FPGA Oberon (=two-pass solution, no imp. order restriction)

None of these checks for cyclic imports. I am currently using ORB08.Mod in my own version of Oberon (Extended Oberon) at present. Of course, it is more restrictive than the other variants (for example, multiple aliases to the same module are not allowed), but simple.

[andreaspirklbauer]

Hi Luca,

Just a quick update: I have now - essentially - completed this little experiment with import aliases. In the meantime, P. Reed has provided an alternative variant (=ORB06.Mod) which is somewhat less restrictive than my originally proposed variant (=ORB07.Mod).

Unlike my original variant, his variant doesn't check the two "cross-combinations" (obj.orgname # name) and (obj.name # orgname) in ORB.ThisModule. To convince myself that this is indeed "safe" to do, I have conducted a detailed case analysis which systematically checks all possible cases (see CaseAnalysis). This analysis convincingly proves that:

a) Not checking the first cross-combination (obj.orgname # name) safely allows:

MODULE B10; IMPORT X := M, M := M0; END B10.
MODULE B11; IMPORT M := M0, M0 := M; END B11.

b) Not checking the second cross-combination (obj.name # orgname) safely allows:

MODULE B12; IMPORT M0 := M, X := M0; END B12. 

Since this is still within the capabilities of what the module list data structure of the Oberon-07 FPGA RISC compiler can handle (it could not, for example, handle multiple aliases to the same module), I have now decided to adopt a slightly modified version of ORB06.Mod (which does slightly better reporting) at ORB06.Mod.

Given its simplicity (only a few lines to be added to the official compiler), I use that for the time being. The restrictions seem reasonable to me (only single but not multiple aliases allowed, explicit imports must come before re-imports, cyclic imports not detected).

If I ever wanted to add more features (e.g. allow multiple aliases to the same module, no restrictions on import order, cyclic imports detected in some, but not all, cases), I now also have a way to do that in the framework of the Oberon-07 FPGA Oberon compiler (e.g. ORB11.Mod).

But that seemed a bit of an overkill for what I wanted to achieve. Maybe I change my mind later.

Thanks for all your input on this wonderful topic of import aliases - it was greatly appreciated!

[lboasso]

Thanks for all the effort you put in exploring different implementation and their relative trade offs. I wish I could have given you more feedback/help but free time is very scarce lately. I agree that ORB06.Mod is probably the best choice.

…

On Thu, Feb 20, 2020, 23:36 Andreas Pirklbauer ***@***.***> wrote: Hi Luca, Just a quick update: I have now - essentially - completed this little experiment with import aliases. In the meantime, P. Reed has provided an alternative variant (=ORB06.Mod) which is somewhat less restrictive than my originally proposed variant (=ORB07.Mod). Unlike my original variant, his variant doesn't check the two "cross-combinations" (obj.orgname # name) and (obj.name # orgname) in ORB.ThisModule. To convince myself that this is indeed "safe" to do, I have conducted a thorough case analysis - oh my - which systematically checks all possible cases (see the end of the README.md file of this repository). This proves that: a) Not checking the first cross-combination (obj.orgname # name) safely allows: MODULE B10; IMPORT X := M, M := M0; END B10. MODULE B11; IMPORT M := M0, M0 := M; END B11. b) Not checking the second cross-combination (obj.name # orgname) safely allows: MODULE B12; IMPORT M0 := M, X := M0; END B12. in the test file M.Mod. Since this is still within the capabilities of what the module list data structure of the Oberon-07 FPGA RISC compiler can handle (it could not, for example, handle multiple aliases to the same module), I have now decided to adopt a slightly modified version of ORB06.Mod (which does slightly better reporting, but otherwise is the same). See ORB06ImprovedErrMsg.Mod Given its simplicity (only a few lines to be added to the official compiler), I use that for the time being. The restrictions seem reasonable to me (only single but not multiple aliases allowed, explicit imports must come before re-imports, cyclic imports not detected). If I ever wanted to implement the "full" functionality (multiple aliases to the same module, no restrictions on import order, cyclic imports detected in all cases, even when a re-imported type is not re-exported) - like you do in your oberonc compiler - I now also have the full implementation for that (ORB11.Mod) at a cost of only +27 additional lines relative to the official compiler. But that seemed a bit of an overkill for what I wanted to achieve. Maybe I change my mind later. Thanks for all your input on this wonderful topic of import aliases - it was greatly appreciated! — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#1>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAVJAW647OVQCM5ELWZIDR3RD6AAFANCNFSM4KSG3QUA> .

[andreaspirklbauer]

Luca, your input was definitely helpful - it made me re-read Griesemer's paper after 3 decades and also study oberonc, which uses the GModtab/LModtab approach described in the paper.

A few comments:

1. I agree that if one is content with a "partial" solution, then ORB06 appears to be the appropriate choice - it adds only a few lines to the current Oberon-07 FPGA RISC compiler, and yet it allows aliases (albeit not more than one per imported module).

2. Adding support for multiple aliases per imported module is in fact fairly easy. One only needs to introduce the notion of "primary" and "secondary" instance - which, in my implementation in ORB10, is a simple back pointer mod.dsc to the primary instance. However, it still increases the implementation cost from ~5 lines in ORB06 to ~25 lines in ORB10. I thought that this was not worth it, the gain is too little - who needs more than a single alias per imported module? Or put another way: in such a case, one might as well go for the "full" solution right away..

3. My own full glory solution "ORB12CheckCyclicImports.Mod" is not (yet) satisfactory though.

Although it does indeed detect ALL cyclic imports during compilation - including in the case where imported or re-imported types are NOT re-exported - it does so in a rather "unnatural" way.

In essence, I retrofit the solution by adding back "module anchors" using additional entries in the module list rooted in ORB.topScope. So it comes as an afterthought. I now have to traverse this list during export, whereas you can simply access the global array GModtab. Another obvious downside of my solution is, of course, that module anchors are written multiple times, whereas you write them only once, and use a reference number later. For this and the reasons mentioned above, I added a comment that in the case where one wants to "full" solution, it is probably better to just adopt the GModtab/LModtab approach that you use in oberonc.

Still, it's comforting to know that the "full" solution can be engineered with <40 lines of extra code relative to the Oberon-07 FPGA RISC compiler. That seems to be less than in oberonc (but the compilers are hard to compare, since your target is different).

In any case, I have now a satisfactory solution: ORB06.Mod. I have already spent more time on this than planned (one week elapsed, one day actual). I'll now let it sit and ferment a little bit. Perhaps one day I have a clever idea, how one could turn ORB12CheckCyclicImports.Mod into a truly natural, elegant solution with <25 lines relative to Oberon-07 FPGA RISC compiler. In that case, I may reconsider it.. perhaps.

Andreas

[andreaspirklbauer]

Hi Luca,

just FYI: As of today, ORB06.Mod is now live at www.projectoberon.com.

This appears to be a good compromise between minimal changes and a correct implementation. The import order restriction (explicit imports have to come before re-imports) has been retained for example, which I believe is a reasonable choice.

-ap