geekstakulus commented 1 year ago

Introduction

The Oberon-7 code provided below encounters an unexpected behavior when compiled with the Oberonc compiler. This bug appears to be related to self-recursion in the code that utilizes certain features of the Oberon-7 language specification.

Current Behavior

When using self-recursion in the Oberonc compiler with valid Oberon-7 code, the compiler raises an error indicating incompatible types when passing a type-extended variable of Node.

Expected Behavior

Self-recursion should work as expected without raising type compatibility errors, as it does in other compilers.

Repro Steps

Write a valid Oberon-7 code that involves self-recursion and type-extended variables of Node.

MODULE AstExample;

IMPORT Out;

CONST
  Add = 1; 
  Subtract = 2; 
  Multiply = 3; 
  Divide = 4;

TYPE
  AstNode = POINTER TO AstNodeDesc;
  AstNodeDesc = RECORD
  END;

  AstNumberNode = POINTER TO AstNumberNodeDesc;
  AstNumberNodeDesc = RECORD(AstNodeDesc)
      value: INTEGER
  END;

  AstBinaryNode = POINTER TO AstBinaryNodeDesc;
  AstBinaryNodeDesc = RECORD(AstNodeDesc)
      opType: INTEGER;
      left, right: AstNode
  END;

PROCEDURE CreateNumberNode(value: INTEGER): AstNumberNode;
  VAR
    node: AstNumberNode;
  BEGIN
    NEW(node);
    node.value := value;
    RETURN node
  END CreateNumberNode;

PROCEDURE CreateBinaryNode(opType: INTEGER; left, right: AstNode): AstBinaryNode;
  VAR
    node: AstBinaryNode;
  BEGIN
    NEW(node);
    node.opType := opType;
    node.left := left;
    node.right := right;
    RETURN node
  END CreateBinaryNode;

PROCEDURE DepthFirstTraversal(node: AstNode);
  BEGIN
    IF node # NIL THEN
      CASE node OF
        AstNumberNode:
          Out.Int(node.value, 0)
        | AstBinaryNode:
          CASE node.opType OF
            Add:
              Out.String("(");
              DepthFirstTraversal(node.left);
              Out.String(" + ");
              DepthFirstTraversal(node.right);
              Out.String(")")
            | Subtract:
              Out.String("(");
              DepthFirstTraversal(node.left);
              Out.String(" - ");
              DepthFirstTraversal(node.right);
              Out.String(")")
            | Multiply:
              Out.String("(");
              DepthFirstTraversal(node.left);
              Out.String(" * ");
              DepthFirstTraversal(node.right);
              Out.String(")")
            | Divide:
              Out.String("(");
              DepthFirstTraversal(node.left);
              Out.String(" / ");
              DepthFirstTraversal(node.right);
              Out.String(")")
          END
      END
    END
  END DepthFirstTraversal;

PROCEDURE Main;
  VAR
    root: AstNode;
  BEGIN
    (* Build the AST: 2 * (3 + 4) *)
    root := CreateBinaryNode(Multiply,
      CreateNumberNode(2),
      CreateBinaryNode(Add,
        CreateNumberNode(3),
        CreateNumberNode(4)
      )
    );

    (* Perform depth-first traversal *)
    Out.String("Expression: ");
    DepthFirstTraversal(root);
    Out.Ln
  END Main;

END AstExample.

Compile the code using the Oberonc compiler.
Observe the type compatibility error being raised shown below:

AstExample.Mod:57:44: incompatible parameters
AstExample.Mod:59:45: incompatible parameters
AstExample.Mod:63:44: incompatible parameters
AstExample.Mod:65:45: incompatible parameters
AstExample.Mod:69:44: incompatible parameters
AstExample.Mod:71:45: incompatible parameters
AstExample.Mod:75:44: incompatible parameters
AstExample.Mod:77:45: incompatible parameters
AstExample.Mod:103:15: compilation FAILED

Modified Code (Working Solution)

To work around the self-recursion issue, use an intermediary procedure for the AstBinaryNode traversal. This approach eliminates the type compatibility error.

MODULE AstExample2;

IMPORT Out;

CONST
  Add = 1; 
  Subtract = 2; 
  Multiply = 3; 
  Divide = 4;

TYPE
  AstNode = POINTER TO AstNodeDesc;
  AstNodeDesc = RECORD
  END;

  AstNumberNode = POINTER TO AstNumberNodeDesc;
  AstNumberNodeDesc = RECORD(AstNodeDesc)
      value: INTEGER
  END;

  AstBinaryNode = POINTER TO AstBinaryNodeDesc;
  AstBinaryNodeDesc = RECORD(AstNodeDesc)
      opType: INTEGER;
      left, right: AstNode
  END;

VAR
  TraverseBinaryNode : PROCEDURE(node : AstBinaryNode);

PROCEDURE CreateNumberNode(value: INTEGER): AstNumberNode;
  VAR
    node: AstNumberNode;
  BEGIN
    NEW(node);
    node.value := value;
    RETURN node
  END CreateNumberNode;

PROCEDURE CreateBinaryNode(opType: INTEGER; left, right: AstNode): AstBinaryNode;
  VAR
    node: AstBinaryNode;
  BEGIN
    NEW(node);
    node.opType := opType;
    node.left := left;
    node.right := right;
    RETURN node
  END CreateBinaryNode;

PROCEDURE DepthFirstTraversal(node: AstNode);
  BEGIN
    IF node # NIL THEN
      CASE node OF
        AstNumberNode:
          Out.Int(node.value, 0)
      | AstBinaryNode:
          TraverseBinaryNode(node)
      END
    END
  END DepthFirstTraversal;

PROCEDURE TraverseBinaryNode0(node : AstBinaryNode);
  BEGIN
    IF node # NIL THEN
      CASE node.opType OF
        Add:
          Out.String("(");
          DepthFirstTraversal(node.left);
          Out.String(" + ");
          DepthFirstTraversal(node.right);
          Out.String(")")
      | Subtract:
          Out.String("(");
          DepthFirstTraversal(node.left);
          Out.String(" - ");
          DepthFirstTraversal(node.right);
          Out.String(")")
      | Multiply:
          Out.String("(");
          DepthFirstTraversal(node.left);
          Out.String(" * ");
          DepthFirstTraversal(node.right);
          Out.String(")")
      | Divide:
          Out.String("(");
          DepthFirstTraversal(node.left);
          Out.String(" / ");
          DepthFirstTraversal(node.right);
          Out.String(")")
      END (* CASE *)
    END (* IF *)
  END TraverseBinaryNode0;

PROCEDURE Main;
  VAR
    root: AstNode;
  BEGIN
    (* Build the AST: 2 * (3 + 4) *)
    root := CreateBinaryNode(Multiply,
      CreateNumberNode(2),
      CreateBinaryNode(Add,
        CreateNumberNode(3),
        CreateNumberNode(4)
      )
    );

    (* Perform depth-first traversal *)
    Out.String("Expression: ");
    DepthFirstTraversal(root);
    Out.Ln
  END Main;
BEGIN
  TraverseBinaryNode := TraverseBinaryNode0
END AstExample2.

Compile and run the modified code using the Oberonc compiler.
Observe that the modified code works correctly without raising type compatibility errors.

Other Information

This issue appears to be specific to self-recursion within the Oberonc compiler. Self-recursion is a common programming technique, and the type compatibility error in this context is unexpected.

Here is another code that also doesn't work:

MODULE ExpressionCalculator;

IMPORT Out;

TYPE
  TreeNode = POINTER TO Node;
  Node = RECORD
    value: INTEGER;
    operator: CHAR;
    left, right: TreeNode;
  END;

VAR
  expressionTree: TreeNode;

(* Function to create a new TreeNode *)
PROCEDURE CreateNode(value: INTEGER; operator: CHAR): TreeNode;
  VAR newNode: TreeNode;
BEGIN
  NEW(newNode);
  newNode.value := value;
  newNode.operator := operator;
  newNode.left := NIL;
  newNode.right := NIL;
  RETURN newNode
END CreateNode;

(* Function to evaluate an expression tree *)
PROCEDURE EvaluateExpression(root: TreeNode): INTEGER;
  VAR
    result : INTEGER;
BEGIN
  result := 0;

  IF root # NIL THEN
    IF root.operator = '+' THEN
      result := EvaluateExpression(root.left) + EvaluateExpression(root.right);
    ELSIF root.operator = '-' THEN
      result := EvaluateExpression(root.left) - EvaluateExpression(root.right);
    ELSIF root.operator = '*' THEN
      result := EvaluateExpression(root.left) * EvaluateExpression(root.right);
    ELSIF root.operator = '/' THEN
      result := EvaluateExpression(root.left) DIV EvaluateExpression(root.right);
    ELSE
      result := root.value;
    END
  END;

  RETURN result
END EvaluateExpression;

BEGIN
  (* Creating an expression tree for (3 + 4) * 2 *)
  expressionTree := CreateNode(0, '*');
  expressionTree.left := CreateNode(3, ' ');
  expressionTree.right := CreateNode(0, '+');
  expressionTree.right.left := CreateNode(4, ' ');
  expressionTree.right.right := CreateNode(2, ' ');

  (* Evaluate the expression and print the result *)
  Out.String("Expression result: ");
  Out.Int(EvaluateExpression(expressionTree), 0);
  Out.Ln;
END ExpressionCalculator.

lboasso commented 1 year ago

Hi @geekstakulus,

Thanks for reporting this issue and for the great bug report! It turns out the bug was in the implementation of implicit type guards in the CASE statement. I have fixed the issue here, you can take a look at the added test for more info.

I have also tried your examples (after fixing a minor typo) and they work as expected now.

Cheers, Luca

geekstakulus commented 1 year ago

Hi, Luca!

Thanks for the quick fix!

I actually tried to fix it myself, and was inspecting it exactly where you fixed it, but I had quite a lot of work to do. So, I thought it would be best to report it and let you fix it. ;-) Who better than the implementer to find the bug, right?

I will give it a try.

Thanks once again!

geekstakulus commented 1 year ago

Hi, Luca!

I have updated the code, but still not able to run them. I get the same compiler errors. I have even recompiled the bootstrap, thinking it was that, but still I get the same incompatible parameters error.

For the expression calculator, I get the following errors:

ExpressionCalculator.Mod:36:26: expression expected
ExpressionCalculator.Mod:37:13: illegal comparison
ExpressionCalculator.Mod:37:36: not a procedure
ExpressionCalculator.Mod:37:46: missing semicolon?
ExpressionCalculator.Mod:37:68: not a procedure
ExpressionCalculator.Mod:38:29: expression expected
ExpressionCalculator.Mod:39:13: illegal comparison
ExpressionCalculator.Mod:39:36: not a procedure
ExpressionCalculator.Mod:39:46: missing semicolon?
ExpressionCalculator.Mod:39:68: not a procedure
ExpressionCalculator.Mod:40:26: expression expected
ExpressionCalculator.Mod:40:29: not a factor
ExpressionCalculator.Mod:42:26: expression expected
ExpressionCalculator.Mod:42:29: not a factor
ExpressionCalculator.Mod:54:34: expression expected
ExpressionCalculator.Mod:55:39: expression expected
ExpressionCalculator.Mod:56:43: expression expected
ExpressionCalculator.Mod:57:45: expression expected
ExpressionCalculator.Mod:58:46: expression expected
ExpressionCalculator.Mod:68:25: compilation FAILED

I am able to compile this code with the VOC compiler. It is an Oberon-2 compiler, but this code should also be valid in Oberon-7, as I haven't used anything specific to Oberon-2.

Thanks in advance once again!

Fidel H Viegas

lboasso commented 1 year ago

Hi Fidel,

Did you have OBERON_BIN set? Here is what I did:

[~/projects/oberonc]
$ export OBERON_BIN=/home/luke/projects/oberonc/bin
[~/projects/oberonc]
$ java -cp $OBERON_BIN oberonc . AstExample.Mod 
[~/projects/oberonc]
$ java -cp $OBERON_BIN:. AstExample
Expression: (2 * (3 + 4))
[~/projects/oberonc]
$ java -cp $OBERON_BIN oberonc . ExpressionCalculator.Mod 
[~/projects/oberonc]
$ java -cp $OBERON_BIN:. ExpressionCalculator
Expression result: 18

ExpressionCalculator uses ' instead of " for single character literals, which is not allowed in Oberon-07.

Below you can find the source code I used:

MODULE ExpressionCalculator;

IMPORT Out;

TYPE
  TreeNode = POINTER TO Node;
  Node = RECORD
    value: INTEGER;
    operator: CHAR;
    left, right: TreeNode;
  END;

VAR
  expressionTree: TreeNode;

(* Function to create a new TreeNode *)
PROCEDURE CreateNode(value: INTEGER; operator: CHAR): TreeNode;
  VAR newNode: TreeNode;
BEGIN
  NEW(newNode);
  newNode.value := value;
  newNode.operator := operator;
  newNode.left := NIL;
  newNode.right := NIL;
  RETURN newNode
END CreateNode;

(* Function to evaluate an expression tree *)
PROCEDURE EvaluateExpression(root: TreeNode): INTEGER;
  VAR
    result : INTEGER;
BEGIN
  result := 0;

  IF root # NIL THEN
    IF root.operator = "+" THEN
      result := EvaluateExpression(root.left) + EvaluateExpression(root.right);
    ELSIF root.operator = "-" THEN
      result := EvaluateExpression(root.left) - EvaluateExpression(root.right);
    ELSIF root.operator = "*" THEN
      result := EvaluateExpression(root.left) * EvaluateExpression(root.right);
    ELSIF root.operator = "/" THEN
      result := EvaluateExpression(root.left) DIV EvaluateExpression(root.right);
    ELSE
      result := root.value;
    END
  END;

  RETURN result
END EvaluateExpression;

BEGIN
  (* Creating an expression tree for 3  * (4 + 2) *)
  expressionTree := CreateNode(0, "*");
  expressionTree.left := CreateNode(3, " ");
  expressionTree.right := CreateNode(0, "+");
  expressionTree.right.left := CreateNode(4, " ");
  expressionTree.right.right := CreateNode(2, " ");

  (* Evaluate the expression and print the result *)
  Out.String("Expression result: ");
  Out.Int(EvaluateExpression(expressionTree), 0);
  Out.Ln;
END ExpressionCalculator.

and

MODULE AstExample;

IMPORT Out;

CONST
  Add = 1;
  Subtract = 2;
  Multiply = 3;
  Divide = 4;

TYPE
  AstNode = POINTER TO AstNodeDesc;
  AstNodeDesc = RECORD
  END;

  AstNumberNode = POINTER TO AstNumberNodeDesc;
  AstNumberNodeDesc = RECORD(AstNodeDesc)
      value: INTEGER
  END;

  AstBinaryNode = POINTER TO AstBinaryNodeDesc;
  AstBinaryNodeDesc = RECORD(AstNodeDesc)
      opType: INTEGER;
      left, right: AstNode
  END;

PROCEDURE CreateNumberNode(value: INTEGER): AstNumberNode;
  VAR
    node: AstNumberNode;
  BEGIN
    NEW(node);
    node.value := value;
    RETURN node
  END CreateNumberNode;

PROCEDURE CreateBinaryNode(opType: INTEGER; left, right: AstNode): AstBinaryNode;
  VAR
    node: AstBinaryNode;
  BEGIN
    NEW(node);
    node.opType := opType;
    node.left := left;
    node.right := right;
    RETURN node
  END CreateBinaryNode;

PROCEDURE DepthFirstTraversal(node: AstNode);
  BEGIN
    IF node # NIL THEN
      CASE node OF
        AstNumberNode:
          Out.Int(node.value, 0)
        | AstBinaryNode:
          CASE node.opType OF
            Add:
              Out.String("(");
              DepthFirstTraversal(node.left);
              Out.String(" + ");
              DepthFirstTraversal(node.right);
              Out.String(")")
            | Subtract:
              Out.String("(");
              DepthFirstTraversal(node.left);
              Out.String(" - ");
              DepthFirstTraversal(node.right);
              Out.String(")")
            | Multiply:
              Out.String("(");
              DepthFirstTraversal(node.left);
              Out.String(" * ");
              DepthFirstTraversal(node.right);
              Out.String(")")
            | Divide:
              Out.String("(");
              DepthFirstTraversal(node.left);
              Out.String(" / ");
              DepthFirstTraversal(node.right);
              Out.String(")")
          END
      END
    END
  END DepthFirstTraversal;

PROCEDURE Main;
  VAR
    root: AstNode;
  BEGIN
    (* Build the AST: 2 * (3 + 4) *)
    root := CreateBinaryNode(Multiply,
      CreateNumberNode(2),
      CreateBinaryNode(Add,
        CreateNumberNode(3),
        CreateNumberNode(4)
      )
    );

    (* Perform depth-first traversal *)
    Out.String("Expression: ");
    DepthFirstTraversal(root);
    Out.Ln
  END Main;

END AstExample.

geekstakulus commented 1 year ago

Hi, Luca!

Thanks once again for the prompt reply!

I was having a hard time with this, but figured I had OBERON_BIN pointing to a different folder than the one I had recently cloned. So, I was always executing the old version. LoL Anyway, all sorted now. Thanks!

As for the second problem, I hadn't realized that ' is no longer acceptable in single characters. Wirth needs to take his medications often, or maybe stop smoking whatever drug he is into, because he keeps changing the language and handicapping more and more. Will he ever keep the language stable without modification? He adds With for type guard, then he decides that CASE will do instead. Why didn't he do this in the first place?

Anyway... problem solved.

Thanks once again!

Fidel H Viegas

geekstakulus commented 1 year ago

I guess he did make it double quotes since the beginning. It was Mössenböck who decided to make Oberon-2 similar to Modula-2. He is excused this time. :-D

lboasso / oberonc

Type Incompatibility with Self-Recursion in Oberonc Compiler #26

Introduction

Current Behavior

Expected Behavior

Repro Steps

Modified Code (Working Solution)

Other Information