solution

Một kiểu bản ghi (record type) được định nghĩa bởi một dãy có thứ tự các kiểu trường (tên trường không ảnh hưởng đến kiểu nên được lược bỏ khỏi đề bài này). Kiểu của một trường có thể là:

• kiểu cơ sở: int, float, bool, string;
• kiểu mảng cơ sở, viết X[n] (không khoảng trắng), với $X$ là kiểu cơ sở và $n$ là kích thước cố định;
• hoặc tên của một kiểu bản ghi khác đã được định nghĩa trước đó (bản ghi lồng nhau, không có tham chiếu vòng vì chỉ được tham chiếu tới bản ghi định nghĩa trước).

Hai kiểu bản ghi $A$ và $B$ được gọi là tương đương cấu trúc (structural equivalence) nếu khi "mở" đệ quy toàn bộ tham chiếu bản ghi lồng nhau về dạng chuẩn (chỉ còn kiểu cơ sở, kiểu mảng cơ sở, và cấu trúc lồng bản ghi), hai bản ghi có cùng số trường và tại mỗi vị trí, kiểu đã mở là giống hệt nhau về cấu trúc (một bản ghi lồng $k$ trường không tương đương với chính kiểu của $1$ trong các trường đó dù $k=1$, vì đó vẫn là hai tầng cấu trúc khác nhau).

Ví dụ: nếu Inner là bản ghi 1 trường kiểu int, và OuterA là bản ghi 1 trường kiểu Inner, còn OuterB là bản ghi 1 trường kiểu int, thì OuterA và OuterB không tương đương (một bên là bản ghi lồng bản ghi, một bên là trường int trực tiếp).