সরাসরি পর্বে যান
পর্ব ২২ · ৮৬-এর মধ্যে · মডিউল ৪

Composite type — array, record, tuple আর union

Composite Types — Arrays, Records, Tuples and Unions

Taught in Bangla, this lesson covers arrays, records, tuples, unions, maps and sets. It derives row-major and column-major address formulas, checks them in Python, and confirms the row-major offset with a real Clang 22.1.8 run. It compares bounds checking across languages, shows a field access compiled to one instruction on x86-64 and RISC-V, adds array and record types to an extended Haat, and contrasts type punning in a free union with tagged unions. A JavaScript run explores typed-array views and maps.

এই পর্বে যা শিখবেন

  • Array, record, tuple, union, map আর set-এর পার্থক্য, আর কোন ভাষায় কোনটি কীভাবে আসে
  • এক ও বহুমাত্রিক array-র ঠিকানার সূত্র (row-major, column-major, যেকোনো নিম্নসীমা), হাতে আর কোডে যাচাইসহ
  • Bounds checking কোন ভাষা করে, কোনটি করে না, আর compiler সেটি কোথায় বসায়
  • Record-এর field কীভাবে offset হয়ে যায়, সত্যিকারের LLVM IR আর assembly দেখে
  • Union, type punning আর tagged union-এর ঝুঁকি; Haat-এর বর্ধিত রূপে array আর record-এর typing rule

১ · Composite type কী — ছোট মান জুড়ে বড় মান

আগের দুই পর্বে (পর্ব ২০ · Primitive type আর পর্ব ২১ · String আর Unicode) একক মানের কথা: একটি পূর্ণসংখ্যা, একটি দশমিক সংখ্যা, একটি Bool, একটি লেখা। কিন্তু বাজারঘরের একটি অর্ডার একটি সংখ্যা নয়। তাতে আছে পরিমাণ, দাম, ঠিকানা, পেমেন্টের ধরন। আর এক দিনের সব অর্ডার মিলে একটি তালিকা। যে type কয়েকটি মানকে জুড়ে একটি নতুন মান বানায়, তাকে বলে composite type (যৌগিক type).

বাজারে যাওয়ার আগে মা একটি ফর্দ লেখেন: ১ নম্বরে চাল, ২ নম্বরে ডাল, ৩ নম্বরে তেল। সব লাইন একই ধাঁচের, আর আপনি নম্বর ধরে খোঁজেন: এটি array. দোকানের অর্ডার-স্লিপে আবার ঘরগুলোর নাম আছে: “পরিমাণ”, “দাম”, “ঠিকানা”; ঘরগুলো ভিন্ন ধরনের, আর আপনি নাম ধরে খোঁজেন: এটি record. রেলের টিকিটে শুধু তিনটি সংখ্যা ছাপা, “কোচ ৩, আসন ১৪, তারিখ ১২”; অবস্থান দেখেই অর্থ বোঝেন: এটি tuple. আর হাসপাতালের একটি বেড কখনো এক রোগীর, কখনো আরেকজনের, কিন্তু একসঙ্গে একজনেরই: এটি union.

ভাষা-নকশার চোখে প্রতিটি composite type একটি type constructor: পুরোনো type নিয়ে নতুন type বানানোর নিয়ম। Int থেকে “Int-এর array”, Int আর Str থেকে “Int ও Str-এর জোড়া”। প্রতিটির জন্য ভাষা-নকশাকারীকে কয়েকটি প্রশ্নের উত্তর দিতে হয়:

রূপউপাদানের typeকীভাবে খোঁজেনউদাহরণ
Arrayসব একইপূর্ণসংখ্যা index, চলার সময় হিসাবC-র int a[10], Java-র int[], Python-এর list
Record / structভিন্ন হতে পারেfield-এর নাম, compile-এর সময় জানাC-র struct, Java-র record, Python-এর dataclass
Tupleভিন্ন হতে পারেঅবস্থান (0, 1, 2…), সাধারণত compile-এর সময় জানাPython-এর (2, 520), Rust-এর (i64, bool)
Unionকয়েকটির যেকোনো একটিmember-এর নাম; কোনটি বৈধ, তা ভাষাভেদে একটি tag-এ লেখা থাকে, বা থাকে নাC-র union, Rust-এর enum, TypeScript-এর A ∣ B
Map / setচাবি আর মানযেকোনো চাবি, চলার সময় খোঁজাPython-এর dict ও set, JavaScript-এর Map

প্রতিটি রূপকে তিন দিক থেকে দেখব: অর্থ (সীমার বাইরে গেলে কী হয়), type (compiler কীভাবে জানে orders[i].unit একটি Int) আর বাস্তবায়ন (মেমরিতে সাজানো আর machine code-এর রূপ)। Byte-স্তরের পূর্ণ খুঁটিনাটি (alignment, padding, endianness) পর্ব ২৫ (Memory layout)-এর বিষয়; এখানে শুধু যতটুকু না জানলে চলে না।

২ · Array — একই type-এর সারি, index দিয়ে খোঁজা

Array হলো একই type-এর উপাদানের সারি, যার প্রতিটি ঘর একটি পূর্ণসংখ্যা index দিয়ে চেনা যায়। Record-এর সঙ্গে মূল পার্থক্য: index একটি চলার সময়ের মান। a[i]-তে i কত, তা compiler জানে না; তাই ঠিকানাটি চলার সময় হিসাব করতে হয়। আর সব ঘর একই মাপের বলেই হিসাবটি সরল:

সংজ্ঞা ২২.১ — এক মাত্রার array-র ঠিকানা

উপাদানের মাপ s byte, প্রথম ঘরের ঠিকানা (base address) b, আর index-এর নিম্নসীমা lb হলে

addr(a[i]) = b + (i − lb) × s

C, Java, Python-এ lb = 0, তাই সূত্রটি b + i × s. Fortran-এ ডিফল্ট lb = 1, আর Pascal ও Ada-তে প্রোগ্রামার নিজে সীমা লেখেন (যেমন array[1..12] of Integer).

সূত্রটি থেকে একটি পুরোনো প্রশ্নের উত্তর মেলে: C-তে index শূন্য থেকে কেন? কারণ C-তে a[i]-এর সংজ্ঞাই *(a + i), অর্থাৎ শুরু থেকে i ঘর দূরে। শূন্য থেকে গুনলে বিয়োগটি লাগে না (Edsger Dijkstra ১৯৮২ সালের নোট EWD831-এ শূন্য থেকে গোনার পক্ষে আরও যুক্তি দেন)। তবে compiler lb-এর বিয়োগ আগেই হিসাব করে রাখতে পারে (b − lb × s একটি ধ্রুবক), তাই 1-ভিত্তিক array-ও ধীর নয়।

Array-র আকার কখন ঠিক হয়

পর্ব ১৬-এ (Lifetime আর storage) variable-কে storage আর lifetime দিয়ে ভাগ করেছিলেন। Array-র ক্ষেত্রে আরেকটি প্রশ্ন যোগ হয়: index-এর সীমা (আকার) কখন বাঁধা হয়, আর বদলাতে পারে কি না। Robert Sebesta-র পাঠ্যবই এই দুই প্রশ্ন মিলিয়ে কয়েকটি শ্রেণি করে; মূল চারটি:

শ্রেণিআকার কখন ঠিকঘর কোথায়উদাহরণ
Staticcompile-এর সময়static এলাকাC-র function-এর ভেতরে static int t[10]
Fixed stack-dynamiccompile-এর সময়stack, প্রতি call-এC-র সাধারণ local int qty[3]
Fixed heap-dynamicচলার সময়, তারপর স্থিরheapJava-র new int[n], C-র malloc(n * sizeof(int))
Heap-dynamicচলার সময়, বারবার বদলায়heapPython-এর list, JavaScript-এর array, C++-এর std::vector

শেষ সারির array-কে সাধারণভাবে dynamic array বলে: জায়গা ফুরালে বড় একটি ঘর নিয়ে সব উপাদান সেখানে সরিয়ে নেয় (খরচের হিসাব DSA কোর্সের পর্ব ১০-এ)। ভাষা-নকশার দিক থেকে: আকার যত দেরিতে বাঁধা হয়, নমনীয়তা তত বেশি, কিন্তু compiler তত কম জানে।

Bounds checking — সীমার বাইরে গেলে কী হয়

সূত্র b + i × s যেকোনো i-এর জন্য একটি ঠিকানা দেয়, এমনকি i = 3 হলেও যখন array-তে মাত্র ৩টি ঘর। তখন ঠিকানাটি অন্য কারও জায়গা। প্রতিটি পড়া-লেখার আগে 0 ≤ i < n পরীক্ষা করাকে বলে bounds checking, আর এখানে ভাষাগুলো স্পষ্ট দুই দলে ভাগ:

  • Java (21): প্রতিটি array access পরীক্ষিত; সীমার বাইরে গেলে ArrayIndexOutOfBoundsException. JVM-এর iaload-এর মতো নির্দেশের সংজ্ঞাতেই পরীক্ষাটি আছে।
  • Python (3.14): list-এ IndexError: list index out of range. তবে ঋণাত্মক index বৈধ: a[-1] মানে শেষ উপাদান।
  • Rust: v[i] সীমার বাইরে গেলে program panic করে থামে (উদাহরণ, এখানে চালানো হয়নি); না থামিয়ে Option চাইলে v.get(i).
  • C আর C++: ভাষা কোনো পরীক্ষা করে না। সীমার বাইরে পড়া বা লেখা undefined behavior: ভাষা কোনো ফলের নিশ্চয়তা দেয় না।

C-র এই আচরণ সত্যিকারের Clang-এ দেখা যাক। এই পর্বের সব C run নেওয়া হয়েছে PyPI-র ziglang 0.17.1 (MIT licence) দিয়ে, যার ভেতরে Clang 22.1.8; নিচে zig মানে python -m ziglang. Wandbox সার্ভার এই সময় ঠিকমতো সাড়া দিচ্ছিল না, তাই C কোড পাতায় চালানোর ব্লক হিসেবে রাখা হয়নি; সব আউটপুট লেখকের Windows x86-64 যন্ত্রে নেওয়া, path ছোট করে দেখানো।

#include <stdio.h>

int pick(const int *a, int i) { return a[i]; }   /* no length known */

int main(void) {
    int qty[3] = {2, 5, 1};
    printf("%d\n", qty[3]);          /* one past the end */
    printf("%d\n", pick(qty, 3));    /* same mistake, hidden */
    return 0;
}
~/haat $ zig cc -std=c17 -Wall -Wextra bounds.c -o b0.exe
bounds.c:7:20: warning: array index 3 is past the end of the array (that has type 'int[3]') [-Warray-bounds]
    7 |     printf("%d\n", qty[3]);          /* one past the end */
      |                    ^   ~
1 warning generated.
~/haat $ ./b0.exe
thread 30108 panic: index 3 out of bounds for type 'int[3]'
~/haat/bounds.c:7: ... in main (bounds.obj)
~/haat $ zig cc -std=c17 -fno-sanitize=undefined bounds.c -o b1.exe && ./b1.exe
350223104
350223104
~/haat $ ./b1.exe
-264243280
-264243280

সত্যিকারের run, Clang 22.1.8. তিনটি আলাদা ঘটনা। এক, qty[3]-এ index একটি ধ্রুবক আর array-র মাপ জানা, তাই Clang compile-এর সময়েই -Warray-bounds warning দেয়। তবু program তৈরি হয়: C-তে এটি error নয়। দুই, zig cc debug build-এ নিজে থেকেই UBSan (sanitizer) চালু রাখে, তাই চলার সময় একটি পরীক্ষা বসেছে আর program থেমেছে। এটি Zig-এর ডিফল্ট সিদ্ধান্ত, C ভাষার নয়। তিন, sanitizer বন্ধ করলে কোনো পরীক্ষা নেই: দুটি লাইনই array-র পরের ৪ byte পড়ে একটি অর্থহীন সংখ্যা ছাপে, আর দুবার চালালে দুই রকম সংখ্যা। আর খেয়াল করুন, pick(qty, 3)-এর ভুল sanitizer-ও ধরতে পারেনি (আলাদা run-এ যাচাই করা): pick-এর কাছে শুধু একটি pointer আছে, array-র দৈর্ঘ্য নেই। C-তে array function-এ গেলে pointer-এ পরিণত হয় আর মাপ হারায়; এটিই C-র bounds checking-এর মূল বাধা।

তাহলে পরীক্ষা করতে হলে চলার সময় দৈর্ঘ্য জানা থাকতে হবে। Java আর Python array-র object-এর ভেতরেই দৈর্ঘ্য রাখে; Rust আর Go-র slice একটি “মোটা pointer” (ঠিকানা আর দৈর্ঘ্য একসঙ্গে)। অর্থাৎ bounds checking-এর দাম দুই ভাগে: প্রতিটি access-এ একটি তুলনা, আর প্রতিটি array-র সঙ্গে দৈর্ঘ্যের তথ্য। ভালো optimizer অনেক তুলনা মুছে দেয়: for (i = 0; i < a.length; i++)-এর মতো loop-এ সে প্রমাণ করতে পারে যে i কখনো সীমা ছাড়াবে না।

৩ · বহুমাত্রিক array — row-major, column-major আর ঠিকানার সূত্র

মেমরি একটি লম্বা সারি, কিন্তু টেবিলের দুটি মাত্রা। তাই multidimensional array-কে এক সারিতে বিছাতে হয়, আর বিছানোর দুটি প্রচলিত রীতি আছে। Row-major: প্রথম সারির সব ঘর, তারপর দ্বিতীয় সারি; C, C++, Pascal এভাবে রাখে। Column-major: প্রথম কলামের সব ঘর, তারপর দ্বিতীয় কলাম; Fortran, MATLAB, R আর Julia এভাবে রাখে। C কোর্সে C-র দিকটি হাতে-কলমে আছে (C কোর্সের পর্ব ২১ · বহুমাত্রিক অ্যারে); এখানে দুই রীতি পাশাপাশি আর সাধারণ সূত্র।

ছবি ২২.১ — একই টেবিল, দুই রীতিতে এক সারিতে

M[2][3]: ২টি সারি, ৩টি কলাম। ঘরে লেখা “i,j” মানে M[i][j]; নিচের সংখ্যা শুরু থেকে কত ঘর দূরে। গাঢ় দাগের ঘরটি M[0][2].

A 2 by 3 table laid out in row-major and in column-major order লেখার টেবিল M[2][3] 0,00,10,2 1,01,11,2 সারি ০সারি ১ row-major · C, C++, Pascal 0,00,10,21,01,11,2 012345 column-major · Fortran, MATLAB, R 0,01,00,11,10,21,2 012345 M[0][2]: row-major-এ ২, column-major-এ ৪
ছবি ২২.১ — নীল ঘর সারি ০-এর, সবুজ ঘর সারি ১-এর। Row-major-এ একই রঙ পাশাপাশি (সারি একটানা), column-major-এ রঙ পালা করে আসে (কলাম একটানা)। একই M[i][j] দুই রীতিতে দুই জায়গায়, তাই এক রীতির ভাষা থেকে অন্য রীতির library-তে টেবিল পাঠাতে হলে সূচক উল্টাতে বা ডেটা সাজিয়ে নিতে হয়।

ছবি থেকে সূত্র সরাসরি পড়া যায়। Row-major-এ M[i][j]-এ পৌঁছাতে আগে i-টি পূর্ণ সারি পার হতে হয়, প্রতিটিতে COLS-টি ঘর; তারপর সেই সারিতে আরও j-টি ঘর। Column-major-এ আগে j-টি পূর্ণ কলাম, প্রতিটিতে ROWS-টি ঘর; তারপর i-টি।

সংজ্ঞা ২২.২ — দুই মাত্রার ঠিকানার সূত্র (নিম্নসীমা 0)

A[ROWS][COLS], উপাদানের মাপ s, base b:

row-major: addr(A[i][j]) = b + (i × COLS + j) × s
column-major: addr(A[i][j]) = b + (j × ROWS + i) × s

নিম্নসীমা l1, l2 হলে i-এর জায়গায় (i − l1), j-এর জায়গায় (j − l2) বসান। লক্ষ করুন: row-major-এ ROWS সূত্রে লাগেই না, column-major-এ লাগে না COLS.

এবার বিশ্ববিদ্যালয় আর চাকরির পরীক্ষায় খুব প্রচলিত ধরনের একটি হিসাব, ধাপে ধাপে: int A[5][6], base 1000, int-এর মাপ 4 byte; A[2][3]-এর ঠিকানা দুই রীতিতে।

1int A[5][6];  /* base 1000, s = 4 */2/* row-major */3skip = i * COLS + j;4addr = base + skip * s;5/* column-major */6skip = j * ROWS + i;7addr = base + skip * s;
এই ধাপের পরে
দেওয়া আছে
skip (row)
addr (row)
skip (col)
addr (col)
  1. যা দেওয়া আছে। ৫টি সারি, ৬টি কলাম, প্রতিটি ঘর 4 byte, প্রথম ঘর 1000-এ। খোঁজা হচ্ছে সারি 2, কলাম 3-এর ঘর (শূন্য থেকে গুনে)।
  2. পূর্ণ সারি পার। Row-major-এ A[2]-তে পৌঁছাতে সারি 0 আর 1 পুরো পার হতে হয়: 2 × 6 = 12টি ঘর।
  3. সারির ভেতরে। সারি 2-এর শুরু থেকে আরও 3টি ঘর: মোট 15টি ঘর পেছনে।
  4. Byte-এ রূপান্তর। 15 ঘর × 4 byte = 60 byte, তাই ঠিকানা 1060. Clang-এর সত্যিকারের run-এ &A[2][3] - &A[0][0] ঠিক 60 byte এসেছে, কারণ C row-major.
  5. Column-major-এ। এবার আগে পূর্ণ কলাম: কলাম 0, 1, 2, প্রতিটিতে 5টি ঘর, 3 × 5 = 15; তারপর কলাম 3-এর ভেতরে 2টি ঘর: মোট 17.
  6. দুই উত্তর। 1000 + 17 × 4 = 1068. একই A[2][3], দুই রীতিতে দুই ঠিকানা: 1060 আর 1068. পরীক্ষায় কোন রীতি জিজ্ঞেস করা হয়েছে, আর index 0 না 1 থেকে, আগে সেটি দেখে নিন।

হাতের হিসাব কোডে যাচাই করা যাক। নিচের কোড দুই সূত্র লেখে, তারপর ৩০টি ঘর এক এক করে বিছিয়ে প্রতিটির ঠিকানা সূত্রের সঙ্গে মেলায়। শেষে একটি সাধারণ function: যেকোনো মাত্রা আর যেকোনো নিম্নসীমার জন্য, Horner-এর নিয়মে (প্রতি ধাপে আগের ফলকে পরের মাত্রা দিয়ে গুণ, তারপর নতুন index যোগ)।

ROWS, COLS, SIZE, BASE = 5, 6, 4, 1000      # int A[5][6], 4-byte cells

def row_major(i, j):
    return BASE + (i * COLS + j) * SIZE

def col_major(i, j):
    return BASE + (j * ROWS + i) * SIZE

def general(idx, dims, lows, order="row"):   # any rank, any lower bounds
    if order == "col":
        idx, dims, lows = idx[::-1], dims[::-1], lows[::-1]
    pos = 0
    for k, d, lo in zip(idx, dims, lows):
        if not lo <= k < lo + d:
            return f"index {k} out of bounds"
        pos = pos * d + (k - lo)             # Horner's rule
    return BASE + pos * SIZE

print("A[2][3] row-major:", row_major(2, 3))
print("A[2][3] col-major:", col_major(2, 3))
# check: lay the 30 cells out one by one and compare with the formulas
by_rows = [(i, j) for i in range(ROWS) for j in range(COLS)]
by_cols = [(i, j) for j in range(COLS) for i in range(ROWS)]
print("formula == layout:",
      all(row_major(i, j) == BASE + n * SIZE for n, (i, j) in enumerate(by_rows)),
      all(col_major(i, j) == BASE + n * SIZE for n, (i, j) in enumerate(by_cols)))
# Fortran-style B(1:5, 1:6), column-major, 1-based
print("B(3,4) col-major, 1-based:", general((3, 4), (5, 6), (1, 1), "col"))
# rank 3: C[2][3][4] of 4-byte ints, element C[1][2][3]
print("C[1][2][3] row-major:", general((1, 2, 3), (2, 3, 4), (0, 0, 0)))
print("A[5][0]:", general((5, 0), (5, 6), (0, 0)))

আসল আউটপুট (ব্রাউজারের Python):

A[2][3] row-major: 1060
A[2][3] col-major: 1068
formula == layout: True True
B(3,4) col-major, 1-based: 1068
C[1][2][3] row-major: 1092
A[5][0]: index 5 out of bounds

দুই সূত্রই ৩০টি ঘরের প্রত্যেকটির বিছানো অবস্থানের সঙ্গে মিলেছে (True True). Fortran-রীতির B(3,4) (1 থেকে গোনা, column-major) আসলে C-রীতির A[2][3]-এর একই ঘর, তাই একই 1068. তিন মাত্রায় Horner-এর নিয়ম: ((1 × 3) + 2) × 4 + 3 = 23 ঘর, 1000 + 92 = 1092. সাধারণ রূপে n মাত্রার row-major অবস্থান হলো (…((i1 × d2 + i2) × d3 + i3)…) × dn + in; প্রথম মাত্রার আকার d1 কোথাও লাগে না, শুধু সীমা পরীক্ষায়। এজন্যই C-তে function-এর parameter int m[][6] লেখা যায়, কিন্তু int m[5][] লেখা যায় না। শেষ লাইনে সীমা পরীক্ষা: 5 বৈধ সারি নম্বর নয়।

Compiler নিজে এই হিসাব কীভাবে লেখে? int get(int i, int j) { return A[i][j]; }-এর জন্য Clang 22.1.8 -O2-এর সত্যিকারের আউটপুট:

; LLVM IR
%4 = getelementptr inbounds [6 x i32], ptr @A, i64 %3   ; row i
%6 = getelementptr inbounds i32, ptr %4, i64 %5         ; col j
%7 = load i32, ptr %6, align 4

; x86-64
movslq  %edi, %rax
leaq    (%rax,%rax,2), %rax       # rax = 3*i
movslq  %esi, %rcx
shlq    $2, %rcx                  # rcx = 4*j
movl    A(%rcx,%rax,8), %eax      # A + 4*j + 8*(3*i)

; RISC-V (riscv64)
slli  a2, a0, 3                   # 8*i
slli  a0, a0, 4                   # 16*i
add   a0, a0, a2                  # 24*i
...
slli  a1, a1, 2                   # 4*j
lw    a0, 0(a0)

IR-তে type নিজেই সূত্র বহন করে: [6 x i32] মানে “৬টি int-এর একটি সারি”, তাই প্রথম ধাপ i সারি এগোয় (i × 24 byte), দ্বিতীয় ধাপ j ঘর (j × 4 byte). x86-64-এ 24 দিয়ে গুণ হয়েছে কৌশলে: 3 × i (leaq), তারপর addressing mode-এর ×8; RISC-V-তে 8i + 16i. কোথাও গুণের নির্দেশ (imul বা mul) নেই: ধ্রুবক দিয়ে গুণকে shift আর যোগে ভাঙা হলো strength reduction, যার পূর্ণ আলোচনা পর্ব ৬৬-এ। আর খেয়াল করুন, কোনো সীমা পরীক্ষা নেই: C-তে সেটি ভাষার কাজ নয়।

Jagged array আর slice

সব “দুই মাত্রার” array আয়তাকার নয়। Java-তে int[][] আসলে array-র array: বাইরের array-তে প্রতিটি সারির reference, আর প্রতিটি সারি heap-এ আলাদা object, দৈর্ঘ্যও আলাদা হতে পারে (Java কোর্সের পর্ব ১৩)। একে বলে jagged array; পুরোনো সাহিত্যে এই কৌশলের নাম Iliffe vector. Python-এর list-এর list-ও এমন। এখানে A[i][j]-এর ঠিকানা আর একটি সূত্র নয়: দুবার মেমরি পড়তে হয় (সারির reference, তারপর ঘর), আর দুবার সীমা পরীক্ষা।

Slice হলো একটি array-র একটি অংশকে নতুন array-র মতো ব্যবহার করা। ভাষাভেদে অর্থ খুব আলাদা: Python-এ list-এর a[1:3] নতুন list বানায় (কপি), কিন্তু memoryview-এর slice মূল byte ভাগ করে; Go-র slice আর Rust-এর &a[1..3] কপি করে না, মূল array-র ভেতরে একটি জানালা (ঠিকানা আর দৈর্ঘ্য)। জানালা মানে aliasing: slice দিয়ে বদলালে মূল array-ও বদলায় (অংশ ৪-এর Python run-এ দুটি আচরণ পাশাপাশি)। Fortran 90-এর A(1:5:2, 3)-এর মতো stride-ওয়ালা অংশের জন্য বাস্তবায়নে একটি dope vector লাগে: base, প্রতিটি মাত্রার সীমা আর stride এক বিবরণীতে।

৪ · Record, struct আর tuple — নাম ধরে আর অবস্থান ধরে

Record হলো কয়েকটি নাম-দেওয়া অংশের (field) সমষ্টি, যাদের type আলাদা হতে পারে। COBOL ব্যবসার ডেটার জন্য ১৯৬০-এর দশকের শুরুতে এমন কাঠামো জনপ্রিয় করে; C. A. R. Hoare ১৯৬০-এর দশকের মাঝামাঝি record আর তার reference নিয়ে একটি প্রস্তাব লেখেন, যা Niklaus Wirth-এর সঙ্গে তৈরি ALGOL W-তে আসে বলে জানা যায়। C-তে এর নাম struct, Pascal-এ record, Java 16 থেকে record (Java কোর্সের পর্ব ২৫), Python-এ dataclass.

Array-র সঙ্গে মূল পার্থক্য বাস্তবায়নে: field-এর নাম compile-এর সময়েই জানা। o.unit-এ “unit” কোনো চলার সময়ের মান নয়, লেখার অংশ। তাই compiler record-এর নকশা (layout) একবার ঠিক করে প্রতিটি field-কে একটি স্থির offset দেয়: record-এর শুরু থেকে কত byte দূরে। তারপর field access মানে “শুরুর ঠিকানা + একটি ধ্রুবক”, কোনো গুণ বা খোঁজাখুঁজি নয়। ধাপে ধাপে দেখুন:

  1. Sourceo->unitনাম
  2. Layoutoffsetটেবিল
  3. IRgepঠিকানা + 8
  4. Machineld১টি নির্দেশ
grid.cC17
struct Order {
    int64_t qty;
    int64_t unit;
    int64_t total;
};
int64_t get_unit(const struct Order *o) {
    return o->unit;
}
offsetof, sizeofসত্যিকারের run
field   offset   মাপ
qty        0      8
unit       8      8
total     16      8
sizeof(struct Order) = 24
clang -O2 -emit-llvmLLVM IR
%2 = getelementptr inbounds nuw i8, ptr %0, i64 8
%3 = load i64, ptr %2, align 8
ret i64 %3
clang -O2 -Sদুই যন্ত্র
; x86-64
movq    8(%rdi), %rax
retq
; RISC-V riscv64
ld      a0, 8(a0)
ret
  1. নাম। Source-এ শুধু একটি নাম: unit. Type checker জানে o-এর type struct Order *, আর Order-এ unit নামে একটি int64_t আছে; তাই o->unit-এর type int64_t. নাম না থাকলে এখানেই compile error.
  2. Layout টেবিল। Compiler ঘোষণার ক্রমে field বসায়: qty 0-তে, unit 8-এ, total 16-এ, মোট 24 byte. টেবিলটি Clang-এর সত্যিকারের run থেকে, C-র offsetof আর sizeof দিয়ে। এখানে সব field 8 byte বলে মাঝে কোনো ফাঁক নেই; ফাঁক কখন আসে, তা পর্ব ২৫-এ।
  3. IR. LLVM IR-এ field-এর নাম আর নেই: আছে শুধু “pointer থেকে 8 byte এগোও” (getelementptr … i64 8), তারপর 8 byte পড়া। নাম থেকে সংখ্যায় এই রূপান্তরটিই record-এর বাস্তবায়নের সারকথা।
  4. এক নির্দেশ। দুই যন্ত্রেই base + ধ্রুবক addressing mode আছে, তাই পুরো field access একটি load: x86-64-এ movq 8(%rdi), RISC-V-তে ld a0, 8(a0). Array-র A[i][j]-এর মতো চলার সময়ের গুণ লাগেনি, কারণ offset compile-এর সময়েই জানা।
~/haat $ zig cc -std=c17 -Wall -Wextra grid.c -o grid.exe && ./grid.exe
&A[2][3] - &A[0][0] = 60 bytes
(2*6 + 3)*4         = 60
offsetof: qty=0 unit=8 total=16, sizeof=24
get(2,3)=7  get_unit=520

সত্যিকারের run (Clang 22.1.8). প্রথম দুই লাইন অংশ ৩-এর row-major সূত্রকে C-র আসল layout দিয়ে নিশ্চিত করে, আর তৃতীয় লাইন ওপরের stepper-এর layout টেবিল। Assembly আর IR এসেছে একই grid.c থেকে, -O2 -S আর -O2 -S -emit-llvm দিয়ে, x86_64-linux-musl আর riscv64-linux-musl target-এ (ছেঁটে দেখানো)।

একটি নকশা-প্রশ্ন: compiler কি field-এর ক্রম বদলাতে পারে? C-তে না: C standard বলে struct-এর member ঘোষণার ক্রমে বাড়তে থাকা ঠিকানায় বসবে, আর প্রথম member-এর আগে কোনো ফাঁক থাকবে না। Rust উল্টো পথ নিয়েছে: সাধারণ struct-এর layout নির্দিষ্ট নয়, compiler জায়গা বাঁচাতে field সাজাতে পারে; C-র মতো ক্রম চাইলে #[repr(C)]. বিস্তারিত পর্ব ২৫-এ।

Tuple — নামহীন record

Tuple হলো এমন record যার field-এর নাম নেই, শুধু অবস্থান: Python-এর (2, 520)-এ t[0] পরিমাণ, t[1] দাম। বাস্তবায়নে record-এর মতোই; অবস্থান 1 মানে একটি স্থির offset. দুর্বলতা হলো t[1] দেখে বোঝা যায় না কী আছে; তাই Python-এ namedtuple আর dataclass. একটি সূক্ষ্মতা: Python-এ tuple-এর index চলার সময়ের মানও হতে পারে (t[k]), কিন্তু Rust-এ t.1-এর 1 লেখারই অংশ।

import struct, sys
from collections import namedtuple
print("Python", sys.version.split()[0])

# a record laid out by hand: three 8-byte integers, no gaps
fields = [("qty", 8), ("unit", 8), ("total", 8)]
off, offsets = 0, {}
for name, size in fields:
    offsets[name] = off
    off += size
print("manual offsets:", offsets, "size:", off)
print("struct.calcsize('<qqq'):", struct.calcsize("<qqq"))
raw = struct.pack("<qqq", 2, 520, 1040)
print("unit read at offset 8:", struct.unpack_from("<q", raw, offsets["unit"])[0])

# tuple = positional record; namedtuple adds field names
t = (2, 520)
Order = namedtuple("Order", "qty unit")
o = Order(2, 520)
print(t[1], o.unit, o[1], o == t)

# slice of a list copies; a memoryview slice shares the bytes
nums = bytearray([10, 20, 30, 40])
copy, view = list(nums)[1:3], memoryview(nums)[1:3]
nums[1] = 99
print("list slice:", copy, "| memoryview slice:", list(view))

# dict keeps insertion order (a language rule since Python 3.7)
stock = {"rice": 40, "10": 1, "oil": 12, "2": 7}
print("dict keys:", list(stock))
print("set:", {3, 1, 2} == {1, 2, 3}, len({"rice", "oil", "rice"}))

আসল আউটপুট (ব্রাউজারের Python, Pyodide-এর CPython 3.14.2):

Python 3.14.2
manual offsets: {'qty': 0, 'unit': 8, 'total': 16} size: 24
struct.calcsize('<qqq'): 24
unit read at offset 8: 520
520 520 520 True
list slice: [20, 30] | memoryview slice: [99, 30]
dict keys: ['rice', '10', 'oil', '2']
set: True 2

প্রথম অংশ: হাতে হিসাব করা offset (0, 8, 16, মোট 24) Python-এর struct module-এর হিসাবের সঙ্গে আর Clang-এর offsetof-এর সঙ্গে মেলে; byte-এর সারি থেকে offset 8-এ পড়লে 520, অর্থাৎ “field = শুরু + offset” হাতে-কলমে। দ্বিতীয়: একই মান tuple-এ অবস্থান দিয়ে, namedtuple-এ নাম বা অবস্থান দুভাবেই। o == t সত্য: namedtuple আসলে tuple-এর subclass, তাই সমতা দেখা হয় শুধু মানের ক্রম দিয়ে, type-এর নাম দিয়ে নয়। অংশ ৮-এ এই প্রশ্নটি ফিরবে। তৃতীয়: মূল nums[1] 99 করার পরে list-এর slice পুরোনো 20 রেখেছে (কপি), memoryview-এর slice 99 দেখাচ্ছে (একই byte). শেষ দুই লাইন অংশ ৭-এর জন্য।

৫ · Haat-এর বর্ধিত রূপ — array আর record

Haat v1-এ কোনো composite type নেই: Int, Bool, Str, Unit আর function type. Reference বাস্তবায়নে [ লিখলেই lexer থামে (সত্যিকারের run):

~/haat $ cat arr.haat
let qty = [2, 1];
~/haat $ python haat.py check arr.haat
1:11: error: unexpected character '['

তাই এই অংশের সব Haat কোড Haat-এর বর্ধিত রূপ: একটি প্রস্তাব, যা reference বাস্তবায়ন করে না; নিচের Python কোড শুধু ধারণাটি চালিয়ে দেখায়। প্রস্তাবিত বাক্যগঠন: array-র type [T], literal [e1, e2], index a[i]; record ঘোষণা record Order { qty: Int, unit: Int }, record literal Order { qty: 2, unit: 520 }, field o.unit. Lexer-এ নতুন token লাগবে [ ] . আর নতুন keyword record.

Typing rule

পর্ব ০৩-এ দেখা inference rule-এর রীতিতে (দাগের ওপরে শর্ত, নিচে সিদ্ধান্ত; Γ হলো নাম থেকে type-এর তালিকা, Γ ⊢ e : τ পড়ুন “Γ-এর তথ্যে e-এর type τ”) চারটি নতুন নিয়ম:

Γ ⊢ e1 : T   …   Γ ⊢ en : T    n ≥ 1
Γ ⊢ [e1, …, en] : [T]
(T-Arr)
Γ ⊢ e1 : [T]    Γ ⊢ e2 : Int
Γ ⊢ e1[e2] : T
(T-Index)
record R { f1: T1, …, fn: Tn }    Γ ⊢ ek : Tk (সব k)
Γ ⊢ R { f1: e1, …, fn: en } : R
(T-Rec)
Γ ⊢ e : R    R-এ field f : T
Γ ⊢ e.f : T
(T-Field)

তিনটি নকশা-সিদ্ধান্ত এই নিয়মে লুকানো। এক, T-Arr-এ n ≥ 1: খালি []-এর type কী, তা নিয়ম বলতে পারে না, তাই let xs: [Int] = [];-এর মতো annotation বাধ্যতামূলক (Haat v1-এ let x: T = e; লেখা আগেই আছে; type inference, পর্ব ৩৫, অন্য সমাধান দেয়)। দুই, T-Index শুধু বলে index-টি Int; বলে না যে সেটি 0 থেকে দৈর্ঘ্যের মধ্যে। দৈর্ঘ্য type-এর অংশ নয়, তাই সীমা পরীক্ষা চলার সময়েই হতে হবে। (Dependent type দিয়ে দৈর্ঘ্যকে type-এ তোলা যায়; পর্ব ৩৯-এ।) তিন, T-Field-এ f-কে R-এর ঘোষণায় খুঁজতে হয়: সেটি একটি compile-এর সময়ের টেবিল-খোঁজা, অর্থাৎ offset-এর হিসাব type checking-এর সঙ্গেই হয়ে যায়। Haat-এর স্বভাব মেনে কোনো implicit রূপান্তর নেই: [Int] আর [Bool] আলাদা, আর Order-এর জায়গায় একই field-ওয়ালা অন্য record চলবে না (অংশ ৮)।

চালিয়ে দেখা — offset আর সীমা পরীক্ষা

এই Haat-এর বর্ধিত রূপের program-টি দেখুন:

record Order { qty: Int, unit: Int }       // Haat-এর বর্ধিত রূপ
let orders = [Order { qty: 2, unit: 520 },
              Order { qty: 1, unit: 60 }];
var total = 0;
var i = 0;
while i < 2 {
    total = total + orders[i].qty * orders[i].unit;
    i = i + 1;
}
print(total);
print(orders[2].unit);

একটি বাস্তবায়ন এটিকে কীভাবে চালাতে পারে, তা নিচের Python মডেলে। মেমরিকে ধরা হয়েছে Int-এর ঘরের (slot) একটি সারি; array-র প্রথম ঘরে দৈর্ঘ্য (header), তারপর record-গুলো পরপর, প্রতিটি record-এর field ঘোষণার ক্রমে। arr[i].field: আগে সীমা পরীক্ষা, তারপর ঠিকানা base + 1 + i × (record-এর মাপ) + offset.

# Haat extension: record Order { qty: Int, unit: Int } and arrays [Order]
RECORDS = {"Order": ["qty", "unit"]}         # fields in declaration order
def offset(rec, field):                      # compile time: name -> slot
    return RECORDS[rec].index(field)
heap = []                                    # one Int per slot
def new_array(rec, items):                   # header = length, then items
    base = len(heap)
    heap.append(len(items))
    for item in items:
        heap.extend(item[f] for f in RECORDS[rec])
    return base
class HaatRuntimeError(Exception):
    pass
def load_field(arr, i, rec, field, pos):     # code for arr[i].field
    n = heap[arr]
    if not 0 <= i < n:                       # the bounds check
        raise HaatRuntimeError(
            f"{pos}: runtime error: index {i} out of bounds for length {n}")
    size, off = len(RECORDS[rec]), offset(rec, field)
    addr = arr + 1 + i * size + off
    print(f"  {field} of [{i}]: slot {arr}+1+{i}*{size}+{off} = {addr}")
    return heap[addr]
orders = new_array("Order", [{"qty": 2, "unit": 520}, {"qty": 1, "unit": 60}])
print("heap slots:", heap)
total = 0
for i in range(2):                           # the while loop, lines 6-9
    total += (load_field(orders, i, "Order", "qty", "7:27")
              * load_field(orders, i, "Order", "unit", "7:43"))
print("total =", total)
try:
    load_field(orders, 2, "Order", "unit", "11:13")    # orders[2].unit
except HaatRuntimeError as e:
    print(e)

আসল আউটপুট (ব্রাউজারের Python):

heap slots: [2, 2, 520, 1, 60]
  qty of [0]: slot 0+1+0*2+0 = 1
  unit of [0]: slot 0+1+0*2+1 = 2
  qty of [1]: slot 0+1+1*2+0 = 3
  unit of [1]: slot 0+1+1*2+1 = 4
total = 1100
11:13: runtime error: index 2 out of bounds for length 2

প্রথম লাইনে পুরো মেমরি: slot 0-তে দৈর্ঘ্য 2, তারপর দুটি Order, প্রতিটি দুই slot-এ। প্রতিটি access-এর ঠিকানা সূত্র মেনে 1, 2, 3, 4; মোট 2 × 520 + 1 × 60 = 1100. শেষ লাইনটি Haat-এর error রীতিতে (<line>:<col>: runtime error: …), আর অবস্থান হিসেবে বেছে নেওয়া হয়েছে [-এর জায়গা, লাইন ১১ কলাম ১৩; reference যেমন ভাগের error-এ operator-এর জায়গা দেখায়। এই বার্তা আর অবস্থান এই প্রস্তাবের নিজের সিদ্ধান্ত, reference-এর নয়।

পরীক্ষাটি না থাকলে কী হতো, সেটিই C আর Haat-এর বর্ধিত রূপের পার্থক্য। ধাপে ধাপে:

1record Order { qty: Int, unit: Int }2let orders = [Order { qty: 2, unit: 520 },3              Order { qty: 1, unit: 60 }];4var total = 0;5var i = 0;6while i < 2 {7    total = total + orders[i].qty * orders[i].unit;8    i = i + 1;9}10print(total);11print(orders[2].unit);
এই ধাপের পরে
heap slots
i, total
সীমা পরীক্ষা
যে slot পড়া হলো
  1. Layout. Array তৈরি: slot 0-তে দৈর্ঘ্য 2, তারপর Order #0 (2, 520) আর Order #1 (1, 60). total আর i দুটিই 0.
  2. প্রথম পাক। i = 0: পরীক্ষা 0 ≤ 0 আর 0 ছোট 2, পাস। qty পড়া slot 1 থেকে (2), unit slot 2 থেকে (520); total = 1040, তারপর i = 1.
  3. দ্বিতীয় পাক। i = 1: পরীক্ষা পাস। slot 3 আর 4 থেকে 1 আর 60; total = 1040 + 60 = 1100, i = 2.
  4. Loop শেষ। 2 < 2 মিথ্যা, তাই loop থামে; লাইন ১০ ছাপে 1100.
  5. সীমার বাইরে। orders[2]: পরীক্ষা 2 ছোট 2? না। কোনো slot পড়ার আগেই program থামে, বার্তা 11:13: runtime error: index 2 out of bounds for length 2. আগে ছাপা 1100 রয়ে যায়, Haat-এর অন্য runtime error-এর মতোই।
  6. C হলে। একই হিসাব পরীক্ষা ছাড়া চললে ঠিকানা হতো slot 0 + 1 + 2 × 2 + 1 = 6, যা array-র বাইরে, হয়তো অন্য কোনো ডেটা। অংশ ২-এর C run-এর মতো: একটি অর্থহীন সংখ্যা, crash, বা আরও খারাপ কিছু; ভাষা কোনো নিশ্চয়তা দেয় না।

৬ · Union — একই জায়গায় কয়েক রকম মান

Record-এ সব field একসঙ্গে থাকে, তাই মাপ সব field-এর যোগফল (আর হয়তো কিছু ফাঁক)। Union-এ উল্টো: সব member একই জায়গা ভাগ করে, একসময় একটিই অর্থপূর্ণ, তাই মাপ অন্তত সবচেয়ে বড় member-এর সমান। বাজারঘরের পেমেন্ট হয় কার্ডে, নয় bKash-এ; দুটির তথ্য একসঙ্গে রাখার দরকার নেই, তাই union.

ছবি ২২.২ — struct পাশাপাশি, union একের ওপর আরেক

ওপরে struct Order-এর ২৪ byte, নিচে union Box-এর ৮ byte; তিনটি member একই byte-এর তিন রকম পড়া।

struct places fields side by side; union overlays its members on the same bytes struct Order · ২৪ byte qtyunittotal 081624 union Box · ৮ byte i (int64) হিসেবে: 1040 d (double) হিসেবে: 5.13828e-321 10 04 00 00 00 00 00 00 b[0] … b[7]: একই ৮টি byte, কাঁচা রূপে ছোট ঘরের byte আগে (little-endian)
ছবি ২২.২ — struct-এ প্রতিটি field-এর নিজের offset; union-এ সবার offset 0. নিচের byte-গুলো সত্যিকারের Clang run থেকে, x86-64-এ, যেখানে little-endian ক্রমে সংখ্যার ছোট byte আগে বসে: 1040 = 0x0410, তাই প্রথমে 10, তারপর 04. Endianness-এর পূর্ণ আলোচনা পর্ব ২৫-এ।

Type punning — এক type-এ লিখে অন্য type-এ পড়া

Union-এর একটি member-এ লিখে অন্য member দিয়ে পড়াকে বলে type punning. এটি বৈধ কি না, ভাষা আর version-ভেদে আলাদা। C99-এর একটি সংশোধনী থেকে (C11 আর C17-এ একটি পাদটীকায়) C বলে: শেষে লেখা member ছাড়া অন্য member দিয়ে পড়লে object-এর byte-গুলো নতুন type হিসেবে নতুন করে পড়া হয়, আর ফলটি এমন bit-বিন্যাস হতে পারে যা সেই type-এর বৈধ মান নয় (“trap representation”). অর্থাৎ C-তে union দিয়ে punning মোটামুটি স্বীকৃত, কিন্তু ফল নির্ভর করে যন্ত্রের মান-প্রকাশের ওপর। C++-এ নিয়ম কড়া: কেবল শেষে লেখা (“active”) member পড়া বৈধ, অন্যটি পড়া undefined behavior; GCC-র মতো কিছু compiler নিজের documentation-এ এটি extension হিসেবে মেনে নেয়। দুই ভাষাতেই নিরাপদ পথ হলো memcpy দিয়ে byte কপি, আর C++20-এ std::bit_cast.

#include <stdio.h>
#include <stdint.h>
#include <string.h>

union Box {                  /* all members share the same 8 bytes */
    int64_t i;
    double d;
    unsigned char b[8];
};

int main(void) {
    union Box x;
    x.i = 1040;                       /* write as an integer ...  */
    printf("sizeof(union Box) = %zu\n", sizeof(union Box));
    printf("bytes   :");
    for (int k = 0; k < 8; k++) printf(" %02x", x.b[k]);
    printf("\nas i64  : %lld\n", (long long)x.i);
    printf("as f64  : %g\n", x.d);    /* ... read as a double     */
    x.d = 0.1;                        /* write as a double ...    */
    printf("x.i now : 0x%016llx\n", (unsigned long long)x.i);
    double price = 0.1;
    uint64_t bits;
    memcpy(&bits, &price, sizeof bits);   /* the portable way */
    printf("memcpy  : 0x%016llx\n", (unsigned long long)bits);
    return 0;
}
~/haat $ zig cc -std=c17 -Wall -Wextra punning.c -o pun.exe && ./pun.exe
sizeof(union Box) = 8
bytes   : 10 04 00 00 00 00 00 00
as i64  : 1040
as f64  : 5.13828e-321
x.i now : 0x3fb999999999999a
memcpy  : 0x3fb999999999999a

সত্যিকারের run, Clang 22.1.8; -O2 দিয়েও হুবহু একই আউটপুট, আর -Wall -Wextra-এ কোনো warning নেই: compiler এখানে কোনো ভুল দেখে না, কারণ C-তে এটি নিষিদ্ধ নয়। Union-এর মাপ ৮, তিন member-এর সবচেয়ে বড়টির সমান। x.i = 1040-এর পরে একই byte double হিসেবে পড়লে একটি অতি ক্ষুদ্র সংখ্যা। আর x.d = 0.1-এর পরে integer হিসেবে পড়লে 0.1-এর IEEE 754 bit-বিন্যাস, যা memcpy-র ফলের সঙ্গে মেলে। ক্ষুদ্র সংখ্যাটি কোথা থেকে এল, নিচের stepper-এ।

1union Box x;2x.i = 1040;3print x.i;4print x.d;5x.d = 0.1; print x.i;
এই ধাপের পরে
৮টি byte
i হিসেবে
d হিসেবে
  1. জায়গা নেওয়া। union Box-এর জন্য ৮ byte; কোনো মান লেখা হয়নি, তাই byte-গুলো অজানা।
  2. Integer লেখা। 1040 = 0x410. Little-endian যন্ত্রে ছোট byte আগে: 10 04, বাকি ছয়টি 00.
  3. Integer পড়া। শেষে লেখা member i, তাই এটি সাধারণ, সব ভাষায় বৈধ পড়া: 1040.
  4. Double পড়া। একই ৮ byte-কে binary64 ধরে পড়া: সবচেয়ে ওপরের bit (sign) 0, পরের ১১ bit (exponent) সব 0, তাই এটি একটি subnormal সংখ্যা, যার মান mantissa × 2−1074 = 1040 × 2−1074 ≈ 5.13828e-321. কোনো রূপান্তর হয়নি, শুধু একই bit নতুন নিয়মে পড়া। IEEE 754-এর ক্ষেত্রগুলোর পূর্ণ ব্যাখ্যা পর্ব ২০-এ।
  5. উল্টো দিকে। 0.1 লিখলে byte-গুলো 9a 99 99 99 99 99 b9 3f; integer হিসেবে পড়লে 0x3fb999999999999a, যা দশমিকে 4591870180066957722. একই কাজ JavaScript-এর typed array দিয়েও করা যায়, নিচের run-এ।

JavaScript-এ C-র union নেই, কিন্তু একই ধারণা আছে: একটি ArrayBuffer (কাঁচা byte-এর খণ্ড) আর তার ওপর কয়েকটি typed array “view”. সব view একই byte দেখে, তাই একটি দিয়ে লিখে অন্যটি দিয়ে পড়া মানে union-এর punning. এখানে আচরণটি ভাষার নিয়মেই সংজ্ঞায়িত। একই block-এ অংশ ৭-এর জন্য দুই রকম associative array-ও আছে।

// one 8-byte buffer, three "views" -- like a C union
const buf = new ArrayBuffer(8);
const asInt = new BigInt64Array(buf);
const asFloat = new Float64Array(buf);
const asBytes = new Uint8Array(buf);

asInt[0] = 1040n;                       // write as a 64-bit integer
console.log("bytes :", Array.from(asBytes, b => b.toString(16).padStart(2, "0")).join(" "));
console.log("as int:", asInt[0].toString());
console.log("as f64:", asFloat[0]);     // same bytes read as a double

asFloat[0] = 0.1;                       // write as a double
console.log("0.1 as int bits: 0x" + BigInt.asUintN(64, asInt[0]).toString(16));

// associative arrays: plain object vs Map
const stock = {};
stock["rice"] = 40; stock["10"] = 1; stock["oil"] = 12; stock["2"] = 7;
console.log("object keys:", Object.keys(stock).join(", "));
const stockMap = new Map([["rice", 40], ["10", 1], ["oil", 12], ["2", 7]]);
console.log("Map keys   :", [...stockMap.keys()].join(", "));
const byOrder = new Map([[{ id: 1 }, "first"]]);   // any value can be a key
console.log("object as Map key:", byOrder.size, typeof [...byOrder.keys()][0]);

আসল আউটপুট (ব্রাউজারের JavaScript; Node 24-এও হুবহু এক):

bytes : 10 04 00 00 00 00 00 00
as int: 1040
as f64: 5.14e-321
0.1 as int bits: 0x3fb999999999999a
object keys: 2, 10, rice, oil
Map keys   : rice, 10, oil, 2
object as Map key: 1 object

প্রথম চার লাইন C-র union-এর সঙ্গে byte ধরে মেলে। শুধু double-টি 5.14e-321: JavaScript সবচেয়ে ছোট যে দশমিক রূপ একই double ফিরিয়ে দেয় সেটি লেখে, C-র %g ছয় অঙ্ক; মান একই। Typed array যন্ত্রের নিজের byte-ক্রম মানে; নির্দিষ্ট ক্রম চাইলে DataView. শেষ তিন লাইনের ব্যাখ্যা অংশ ৭-এ।

Free union আর tagged union

C-র union “free”: কোন member এখন বৈধ, সেই তথ্য কোথাও রাখা হয় না। ভুল member পড়লে কেউ থামায় না, যা ওপরের run-এ দেখলেন। নিরাপদ পথ হলো সঙ্গে একটি চিহ্ন (tag) রাখা, যা বলে কোন member বৈধ: tagged union. C-তে এটি প্রোগ্রামারকে হাতে বানাতে হয়:

enum Kind { CASH, CARD, BKASH };
struct Payment {
    enum Kind kind;              /* the tag: which member is valid */
    union {
        int64_t card_last4;      /* valid when kind == CARD  */
        int64_t bkash_txn;       /* valid when kind == BKASH */
    } as;
};
void show(struct Payment p) {
    switch (p.kind) {
    case CASH:  printf("cash\n"); break;
    case CARD:  printf("card ****%04lld\n", (long long)p.as.card_last4); break;
    case BKASH: printf("bkash txn %lld\n", (long long)p.as.bkash_txn); break;
    }
}
/* main: a = {CARD, 4242}; b = {BKASH, 777001}; show(a); show(b);
         b.kind = CARD; show(b);   -- tag changed, payload not */
~/haat $ zig cc -std=c17 -Wall -Wextra tagged.c -o tg.exe && ./tg.exe
card ****4242
bkash txn 777001
card ****777001
sizeof(struct Payment) = 16

সত্যিকারের run (Clang 22.1.8; পূর্ণ main লেখকের ফাইলে, এখানে মন্তব্যে সংক্ষেপে)। প্রথম দুই লাইন ঠিক আছে: switch tag দেখে ঠিক member পড়েছে। তৃতীয় লাইন একটি “মিথ্যা”: tag বদলে CARD করা হয়েছে, কিন্তু ভেতরের মান এখনো bKash-এর লেনদেন নম্বর, আর program সেটিকে কার্ডের শেষ চার অঙ্ক বলে ছেপেছে। কোনো warning নেই, কোনো error নেই। C-তে tag আর মানের মিল রাখা পুরোপুরি প্রোগ্রামারের দায়। মাপ ১৬: ৪ byte-এর enum, তারপর ৮ byte-এর union-কে ৮-এর গুণিতকে বসাতে ৪ byte ফাঁক (padding); পর্ব ২৫-এর বিষয়।

ভাষাগুলো এই ফাঁক বন্ধ করেছে ধাপে ধাপে (ইতিহাস ভাবনার প্রশ্ন ০৩-এ): Pascal-এর variant record, Ada-র discriminated record, আর শেষে ML, Haskell ও Rust, যেখানে tag আর মান ভাষা নিজে বাঁধে আর মান বের করার একমাত্র পথ pattern matching. TypeScript-এর discriminated union একই চিন্তার একটি রূপ। এর পূর্ণ কাহিনি, sum type আর product type-এর গণনাসহ, পর্ব ২৪-এ (Algebraic data type আর pattern matching).

৭ · Associative array আর set — চাবি দিয়ে খোঁজা

Array-র index পূর্ণসংখ্যা আর ঘন: 0, 1, 2…। কিন্তু বাজারঘরের গুদামে পণ্য খোঁজা হয় নাম দিয়ে: “চাল কত বস্তা?”। যে composite type-এ যেকোনো চাবি (key) দিয়ে মান খোঁজা যায়, তাকে বলে associative array বা map; Python-এ dict, JavaScript-এ Map, Java-য় HashMap, C++-এ std::unordered_map. AWK আর Perl-এর মতো scripting ভাষা এটিকে ভাষার মূল অংশ বানায়।

বাস্তবায়ন সাধারণত hash table: চাবি থেকে একটি সংখ্যা (hash) বানিয়ে সরাসরি একটি ঘরে যাওয়া, তাই গড়ে খোঁজা ধ্রুবক সময়ে। Collision আর load factor-এর পূর্ণ গল্প DSA কোর্সের পর্ব ৩২-এ। ভাষা-নকশার জন্য তিনটি প্রশ্ন বেশি গুরুত্বপূর্ণ:

  • কী চাবি হতে পারে? Python-এ শুধু hashable মান: Int, Str, tuple হ্যাঁ, list না, কারণ চাবির hash বদলে গেলে টেবিল ভুল ঘরে খুঁজবে। JavaScript-এর সাধারণ object-এ চাবি শুধু string বা Symbol (সংখ্যা দিলে string হয়ে যায়), আর Map-এ যেকোনো মান, এমনকি একটি object; ওপরের run-এর শেষ লাইন 1 object সেটিই দেখায়।
  • ক্রম কি নিশ্চিত? Python 3.7 থেকে ভাষার নিয়ম: dict ঢোকানোর ক্রম রাখে (CPython 3.6-এ এটি বাস্তবায়নের বৈশিষ্ট্য ছিল, নিশ্চয়তা নয়)। অংশ ৪-এর run-এ ['rice', '10', 'oil', '2'], ঠিক ঢোকানোর ক্রমে। JavaScript-এর Map-ও ঢোকানোর ক্রম রাখে। কিন্তু সাধারণ object-এ আধুনিক ECMAScript-এর নিয়ম ভিন্ন: যে চাবি array index-এর মতো দেখায় ("2", "10"), সেগুলো আগে, ছোট থেকে বড়; তারপর বাকি string ঢোকানোর ক্রমে। তাই ওপরের run-এ object দিল 2, 10, rice, oil, আর Map দিল rice, 10, oil, 2. একই তথ্য, দুই ক্রম।
  • না পেলে কী? Python-এ d["x"] দিলে KeyError, d.get("x") দিলে None; JavaScript-এ undefined; C++-এর m["x"] নীরবে একটি নতুন ফাঁকা entry বানিয়ে ফেলে। শেষেরটি একটি পরিচিত ফাঁদ।

Set হলো শুধু চাবির সংগ্রহ, মান ছাড়া: একই উপাদান দুবার থাকে না, ক্রমের অর্থ নেই। অংশ ৪-এর run-এ {3, 1, 2} == {1, 2, 3} সত্য, আর {"rice", "oil", "rice"}-এর আকার ২. Python আর JavaScript-এ set সাধারণত hash table দিয়ে; কিন্তু উপাদানের জগৎ ছোট আর স্থির হলে আরও সস্তা পথ আছে: bit vector. Pascal-এর set of 0..63 এমন: প্রতিটি সম্ভাব্য উপাদানের জন্য একটি bit, তাই union মানে একটি OR নির্দেশ, intersection একটি AND. C-তে flag রাখার জন্য প্রোগ্রামাররা একই কৌশল হাতে লেখেন।

৮ · দুটি composite type কখন “একই” — আর compiler-এর চোখে পুরো ছবি

Primitive type-এ সমতার প্রশ্ন সহজ: Int আর Int একই। কিন্তু record Point { x: Int, y: Int } আর record Size { x: Int, y: Int } কি একই type? দুই উত্তর আছে। Name equivalence: দুটি type একই শুধু যদি একই ঘোষণা থেকে আসে, তাই Point আর Size আলাদা। Structural equivalence: গঠন একই হলেই type একই, তাই দুটি সমান। প্রথমটি নিরাপদ (টাকা আর কেজি গুলিয়ে যায় না) আর compiler-এর জন্য সহজ (নাম তুলনা); দ্বিতীয়টি নমনীয়, কিন্তু recursive type-এ যাচাই কঠিন, আর অনিচ্ছাকৃত মিলও মেনে নেয়।

  • C: একই ফাইলে দুটি আলাদা struct ঘোষণা, member হুবহু এক হলেও, আলাদা type; একটির জায়গায় অন্যটি দিলে error. কিন্তু array আর pointer-এর type-এ গঠন দেখা হয় (int[5] সবখানে এক), অর্থাৎ ভাষাটি মিশ্র।
  • Java: class আর record পুরোপুরি নাম দিয়ে; দুটি একই field-এর record আলাদা type.
  • TypeScript: object type গঠন দিয়ে তুলনা করে (structural typing), তাই {x: number, y: number}-আকারের যেকোনো মান Point-এর জায়গায় চলে।
  • Python: অংশ ৪-এ Order(2, 520) == (2, 520) সত্য এসেছিল: namedtuple-এর সমতা tuple-এর মতো, শুধু মান দেখে। তবে dataclass-এর == আগে দেখে দুই পক্ষ একই class কি না।

Haat-এর বর্ধিত রূপের জন্য প্রস্তাব: record নাম দিয়ে (Order শুধু Order), array গঠন দিয়ে ([Int] সবখানে এক), আর function type যেমন আছে তেমন গঠন দিয়ে ((Int) -> Int). এই প্রশ্নের নিয়মগুলো আনুষ্ঠানিকভাবে লেখা হবে পর্ব ৩৪-এ (Typing rule আর type judgment). সব মিলিয়ে একটি compiler composite type-এর জন্য কী কী করে, একটি মানচিত্র:

কাজCompile-এর সময়চলার সময়
Array indexউপাদানের মাপ, মাত্রাগুলো (যদি জানা), type যাচাইসূত্রে ঠিকানা; ভাষা চাইলে সীমা পরীক্ষা
Record fieldlayout, প্রতিটি field-এর offset, type যাচাইশুধু base + ধ্রুবক থেকে load
Unionমাপ = বড় member (আর alignment)tag থাকলে tag পরীক্ষা, নইলে কিছুই না
Map / setচাবির type বৈধ কি না (static ভাষায়)hash, খোঁজা, টেবিল বড় করা
Type সমতানাম বা গঠন তুলনাdynamic ভাষায় type tag দেখে

আরও গভীরে: Fortran 90-এর assumed-shape array আর array section ঠিকমতো চালাতে compiler প্রতিটি array-র সঙ্গে একটি descriptor পাঠায়, যাতে base, প্রতিটি মাত্রার সীমা আর stride থাকে; Fortran 2018 এই descriptor-এর একটি রূপ C-র সঙ্গে ভাগ করার জন্য মানসম্মত করেছে বলে জানা যায়। “Array of structs” বনাম “struct of arrays”-এর প্রশ্নটি cache-এর (Computer Architecture কোর্সের পর্ব ৪৮) আর পর্ব ২৫-এর। আর polyhedral model nested loop-এর বহুমাত্রিক array access-কে পূর্ণসংখ্যার বিন্দুর সেট হিসেবে দেখে loop-এর ক্রম বদলায়; LLVM-এর Polly আর GCC-র Graphite এর বাস্তব রূপ।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • Row-major আর column-major সূত্র? b + (i × COLS + j) × s আর b + (j × ROWS + i) × s; নিম্নসীমা থাকলে আগে বিয়োগ। একটি সংখ্যাসহ উদাহরণ করে দেখাতে পারা দরকার।
  • Struct আর union-এর মাপের পার্থক্য? Struct-এ সব member-এর যোগফল (আর padding), union-এ সবচেয়ে বড় member (আর alignment-এর জন্য বাড়তি)।
  • Array আর record-এর access-এর খরচ কেন আলাদা? Index চলার সময়ের মান, তাই গুণ লাগে; field-এর offset compile-এর সময়ে জানা, তাই একটি ধ্রুবক।
  • C কেন bounds check করে না? দৈর্ঘ্য array-র সঙ্গে চলে না আর গতির জন্য; ফল undefined behavior, buffer overflow-এর মূল উৎস।

৯ · AI-এর যুগে composite type

Composite type-এর প্রশ্নে AI assistant-এর উত্তর প্রায়ই প্রায়-সঠিক, আর সেই “প্রায়”-টুকুই বিপদ। এই বিষয়ে বারবার দেখা ভুল:

AI-এর ভুলকীভাবে ধরবেন
Column-major সূত্রে ROWS আর COLS গুলিয়ে ফেলা, বা 1-ভিত্তিক সীমার বিয়োগ বাদ দেওয়াছোট একটি টেবিল সব ঘর বিছিয়ে সূত্রের সঙ্গে মেলানো, অংশ ৩-এর কোডের মতো
এক ভাষার নিয়ম সবখানে চাপানো: “union punning সবসময় UB” বা “সবসময় বৈধ”ভাষা আর version আলাদা করে standard-এর ধারা খোঁজা (C আর C++ ভিন্ন)
“Sanitizer চালু, তাই সব out-of-bounds ধরা পড়বে”Pointer দিয়ে একই ভুল চালিয়ে দেখা; অংশ ২-এর pick ধরা পড়েনি
Struct-এর sizeof হিসাব করে field-এর মাপ যোগ করে, padding ভুলেসত্যিকারের compiler-এ sizeof আর offsetof ছাপানো
Dict বা object-এর ক্রম নিয়ে ভুল নিশ্চয়তা (“JS object ঢোকানোর ক্রম রাখে”)সংখ্যার মতো চাবি মিশিয়ে চালানো, অংশ ৬-এর JS run-এর মতো
বানানো compiler flag বা আউটপুট, যেমন অস্তিত্বহীন warning-এর নামনিজের compiler-এ flag চালানো; assembly বা IR নিজে -S দিয়ে দেখা

AI-কে ভালোভাবে কাজে লাগানোর উপায়: ভাষা, version আর target যন্ত্র বলে দেওয়া, প্রতিটি সংখ্যার হিসাব ধাপসহ চাওয়া, আর কোন দাবি নিজে চালিয়ে যাচাই করতে হবে তা জিজ্ঞেস করা।

আমি প্রোগ্রামিং ভাষার composite type শিখছি। নিচের প্রশ্নের উত্তর দাও: ১. C17-এ int A[5][6] (int = 4 byte, base 1000)-এর A[2][3]-এর ঠিকানা row-major আর column-major দুই রীতিতে, প্রতিটি ধাপ লিখে বের করো। কোনটি C-র আসল রীতি, তাও বলো। ২. একই হিসাব যাচাই করার জন্য একটি ছোট Python script লেখো, যা সব ঘর এক এক করে বিছিয়ে সূত্রের সঙ্গে মেলায়। ৩. C17 আর C++20-এ union-এর একটি member-এ লিখে অন্যটি পড়া বৈধ কি না, আলাদা করে বলো; standard-এর কোন অংশ থেকে বলছ তা উল্লেখ করো, নিশ্চিত না হলে সেটি স্পষ্ট লেখো। ৪. যে আউটপুট তুমি নিজে চালাওনি, তা "অনুমান" বলে চিহ্নিত করো, আর বলো আমি কোন compiler flag দিয়ে নিজে মেলাব।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Fortran কেন column-major আর C কেন row-major? আজও এই পার্থক্য কেন সমস্যা তৈরি করে?

ইতিহাসের সরল উত্তর হলো, দুটি ভাষা দুই সময়ে দুই দল বানিয়েছে, আর কোনো বাধ্যতামূলক “সঠিক” রীতি ছিল না। ১৯৫০-এর দশকে IBM-এ John Backus-এর দল FORTRAN বানানোর সময় array-কে column ধরে সাজানোর সিদ্ধান্ত নেয়। ১৯৭০-এর দশকের শুরুতে Dennis Ritchie-র C-তে বহুমাত্রিক array আলাদা কোনো ধারণাই নয়: int A[5][6] মানে “৫টি উপাদানের array, যার প্রতিটি ৬টি int-এর array”. এই সংজ্ঞা থেকেই row-major স্বাভাবিকভাবে আসে: A[i] নিজেই একটি পূর্ণ সারি, আর তার উপাদানগুলো পাশাপাশি।

আজ পার্থক্যটি দুই জায়গায় ভোগায়। প্রথম, ভাষার সীমানায়। বৈজ্ঞানিক গণনার বহু পুরোনো ও নির্ভরযোগ্য library (BLAS, LAPACK) Fortran-রীতিতে column-major ডেটা আশা করে। C, C++ বা Python থেকে এগুলো ডাকলে হয় ডেটা সাজিয়ে নিতে হয়, নয়তো matrix-কে “transpose করা” ধরে নিয়ে হিসাব উল্টাতে হয়। NumPy এজন্যই দুই রীতিই সমর্থন করে: ডিফল্ট C-রীতি, আর order='F' দিলে Fortran-রীতি।

দ্বিতীয়, গতিতে। মেমরি থেকে CPU ডেটা আনে cache line ধরে, একসঙ্গে কয়েকটি পাশাপাশি byte. Row-major-এ সারি ধরে ঘুরলে (ভেতরের loop-এ j) পরপর ঠিকানা পড়া হয়, আর একবার আনা cache line পুরো কাজে লাগে। একই loop column ধরে ঘুরলে প্রতিটি পড়া COLS × s byte দূরে লাফায়, আর বড় টেবিলে প্রায় প্রতিটি পড়া নতুন cache line চায়। কতটা ধীর হবে তা যন্ত্র আর টেবিলের মাপের ওপর নির্ভর করে; এখানে কোনো সংখ্যা দাবি করছি না, নিজের যন্ত্রে মেপে দেখাই নিয়ম। Compiler কখনো কখনো loop-এর ক্রম নিজে বদলাতে পারে (loop interchange, পর্ব ৬৬), কিন্তু শুধু যখন প্রমাণ করতে পারে যে ফল বদলাবে না।

মূল উপলব্ধি: row-major আর column-major দুটিই সঠিক; ভুল হয় যখন ডেটার রীতি আর তাকে পড়ার রীতি মেলে না। সীমানায় রূপান্তর আর loop-এর ক্রম, দুটিই সেই মিলের প্রশ্ন।

প্র ০২C কেন array-র সীমা পরীক্ষা করে না, অথচ অনেক আগের ভাষা করত? পরীক্ষার আসল দাম কত?

সীমা পরীক্ষা নতুন ধারণা নয়। C. A. R. Hoare ১৯৮০ সালের Turing Award বক্তৃতায় (“The Emperor's Old Clothes”) বলেন, ১৯৬০-এর দশকে তাঁর দলের ALGOL 60 compiler প্রতিটি subscript পরীক্ষা করত, আর ব্যবহারকারীদের জিজ্ঞেস করা হলে তাঁরা পরীক্ষা বন্ধের সুযোগ চাননি, কারণ পরীক্ষা ছাড়া ভুল খুঁজতে আরও বেশি ভুগতে হতো। এই প্রসঙ্গে তাঁর একটি তীক্ষ্ণ মন্তব্যও বহুল উদ্ধৃত: অন্য প্রকৌশলে এমন সাধারণ সাবধানতা না মানা অনেক আগেই নিষিদ্ধ হয়ে যেত (ভাষ্য ভাবার্থে)। Pascal আর Ada-ও পরীক্ষা ভাষার অংশ করে।

C ভিন্ন লক্ষ্য থেকে এসেছে: operating system লেখার একটি ভাষা, যেখানে প্রোগ্রামার যন্ত্রের খুব কাছে থাকতে চান আর কোনো লুকানো খরচ চান না। C-র নকশায় array মূলত একটি ঠিকানা: function-এ পাঠালে pointer হয়ে যায়, দৈর্ঘ্য হারায়। দৈর্ঘ্য না থাকলে পরীক্ষাই সম্ভব নয়; অংশ ২-এর pick সেটিই দেখাল। তাই C-তে সীমা পরীক্ষা বসাতে হলে শুধু একটি compiler flag নয়, ডেটার প্রকাশই বদলাতে হয় (pointer-এর সঙ্গে দৈর্ঘ্য বা সীমা বয়ে নেওয়া), যা পুরোনো কোড আর ABI-এর সঙ্গে সামঞ্জস্য ভাঙে। Checked C-এর মতো গবেষণা প্রকল্প আর Clang-এর কিছু নতুন বৈশিষ্ট্য এই দিকেই কাজ করছে বলে জানা যায়।

পরীক্ষার দাম দুই রকম। প্রতিটি access-এ একটি তুলনা আর একটি শর্তসাপেক্ষ লাফ; আধুনিক CPU-তে এই লাফ প্রায় সবসময় একই দিকে যায় বলে branch predictor সাধারণত ঠিক অনুমান করে। দ্বিতীয় দাম সূক্ষ্ম: পরীক্ষা ব্যর্থ হলে exception বা panic-এর পথ খোলা রাখতে হয়, যা কিছু optimization (যেমন loop vectorization) কঠিন করে। এজন্য Java-র JIT আর Rust-এর LLVM backend “bounds check elimination” করে: range analysis দিয়ে প্রমাণ করা যে loop-এর i কখনো সীমা ছাড়াবে না, আর তখন পরীক্ষাটি loop-এর বাইরে একবার বা একেবারেই না। বাস্তব কোডে খরচ কতটা, তা কাজের ধরন অনুযায়ী বদলায়; নিজের কোড মেপে দেখাই একমাত্র নির্ভরযোগ্য উত্তর।

মূল উপলব্ধি: সীমা পরীক্ষা একটি তুলনা নয়, একটি নকশা-সিদ্ধান্ত: array-র সঙ্গে দৈর্ঘ্য বয়ে নিতে হবে। যে ভাষা শুরুতেই এই সিদ্ধান্ত নেয়, তার compiler পরে বেশিরভাগ পরীক্ষা নিজে মুছে দিতে পারে; যে নেয় না, পরে যোগ করা খুব কঠিন।

প্র ০৩Free union থেকে tagged union, তারপর algebraic data type — ভাষাগুলো কীভাবে এই নিরাপত্তার ফাঁক বন্ধ করল?

সমস্যাটি সরল: একটি মান “কয়েক রকমের একটি” হলে, এখন কোন রকম, সেই তথ্য কে রাখবে আর কে যাচাই করবে? FORTRAN-এর EQUIVALENCE দুটি variable-কে একই মেমরিতে বসাত, মূলত মেমরি বাঁচাতে; কোনো তথ্য বা যাচাই ছিল না। C-র union একই পথের উত্তরসূরি: free union, সব দায় প্রোগ্রামারের।

ALGOL 68-এর “united mode”-এ ভাষা নিজে বর্তমান রকমটি মনে রাখত, আর মান বের করতে একটি conformity clause (case-এর মতো) লিখতে হতো, যা বলে জানা যায়। Pascal-এর variant record-এ tag field ভাষার অংশ হলো, কিন্তু নিয়ম ছিল ঢিলা: tag আলাদা করে বদলানো যেত, এমনকি tag ছাড়াও variant ঘোষণা করা যেত, আর বেশিরভাগ বাস্তবায়ন ভুল variant পড়া পরীক্ষা করত না। ফলে Pascal-এর type-নিরাপত্তায় এটি একটি পরিচিত ফুটো ছিল, আর প্রোগ্রামাররা ইচ্ছা করেই pointer-কে integer হিসেবে পড়তে এটি ব্যবহার করতেন। Ada এই শিক্ষা থেকে নিয়ম কড়া করে: discriminant একা বদলানো নিষেধ, পুরো record একসঙ্গে দিতে হয়, আর ভুল variant-এর field পড়লে চলার সময় error ওঠে।

ML (১৯৭০-এর দশক) আর পরে Haskell, OCaml, Rust, Swift সমস্যাটিকে মূল থেকে সরায়। datatype বা enum ঘোষণায় প্রতিটি রকমের নিজের constructor; মান তৈরি হয় শুধু constructor দিয়ে, তাই tag আর মান কখনো আলাদা হয় না। মান পড়ার একমাত্র পথ pattern matching, আর compiler পরীক্ষা করে সব রকম ধরা হয়েছে কি না (exhaustiveness). অর্থাৎ C-তে যে “মিথ্যা tag” আমাদের run-এ card ****777001 ছাপল, এই ভাষাগুলোতে সেটি লেখাই যায় না। বাস্তবায়নে নিচে সেই একই জিনিস: একটি tag আর একটি union-এর মতো জায়গা; Rust compiler কখনো কখনো tag-এর জন্য আলাদা জায়গাও লাগায় না, যেমন Option<&T>-এ null ঠিকানাকেই “None” ধরে।

মূল উপলব্ধি: union-এর নিরাপত্তা নির্ভর করে tag আর মানকে কে একসঙ্গে বাঁধে তার ওপর। ভাষা যত বেশি সেই বাঁধন নিজের হাতে নেয়, তত কম ভুল সম্ভব, আর machine code-এ তার খরচ প্রায়ই প্রায় শূন্য। পর্ব ২৪ এই গল্পের পরের অধ্যায়।

প্র ০৪Python-এর dict-এর ক্রম কেন ভাষার নিশ্চয়তা হলো, আর JavaScript-এ object থাকতেও Map কেন এল?

দীর্ঘদিন hash table মানেই “ক্রম নেই”: চাবি কোন ঘরে যাবে তা hash ঠিক করে, তাই ঘোরার ক্রম ঢোকানোর ক্রমের সঙ্গে মিলবে এমন কোনো কথা নেই। Python 3.3-এ string-এর hash প্রতি run-এ এলোমেলো করা হয় (hash randomization), যাতে আক্রমণকারী ইচ্ছা করে একই ঘরে পড়া চাবি পাঠিয়ে টেবিল ধীর করতে না পারে; ফলে একই program-এর dict-ক্রম run থেকে run-এ বদলাতেও পারত।

তারপর একটি বাস্তবায়ন-কৌশল দৃশ্য বদলে দেয়। Raymond Hettinger প্রস্তাবিত “compact dict”-এ entry-গুলো ঢোকানোর ক্রমে একটি ঘন array-তে থাকে, আর hash টেবিলে থাকে শুধু ছোট index; এতে মেমরি কমে, আর পার্শ্বফল হিসেবে ঢোকানোর ক্রম রক্ষা পায়। CPython 3.6-এ এটি আসে, তবে ক্রমটি তখন ছিল “বাস্তবায়নের বৈশিষ্ট্য, নির্ভর করবেন না”। Python 3.7-এ এটিকে ভাষার নিয়ম ঘোষণা করা হয়। কারণটি নকশা-দর্শনের: সবাই যে আচরণে নির্ভর করতে শুরু করেছে, তাকে নিশ্চয়তা না দিলে অন্য বাস্তবায়নে চললে লুকানো ভুল তৈরি হয়। দাম হলো ভবিষ্যতের স্বাধীনতা: CPython আর কখনো এমন কৌশল নিতে পারবে না যা ক্রম রাখে না।

JavaScript-এর গল্প ভিন্ন। ভাষার শুরু থেকে object-ই ছিল map, কিন্তু সেটি দুই কাজে ভাগ করা: চাবি-মানের সংগ্রহ আর program-এর object. এর ফাঁদ অনেক: চাবি শুধু string বা Symbol, তাই 1 আর "1" একই চাবি; prototype থেকে উত্তরাধিকার পাওয়া নাম (toString, এমনকি __proto__) চাবির সঙ্গে গুলিয়ে যেতে পারে; আকার জানতে আলাদা হিসাব লাগে; আর ক্রমের নিয়ম জটিল, যা অংশ ৬-এর run-এ দেখলেন। ECMAScript 2015 (ES6) Map আর Set আনে: যেকোনো মান চাবি, ঢোকানোর ক্রম নিশ্চিত, size সরাসরি, আর prototype-এর কোনো ঝামেলা নেই (বিস্তারিত JavaScript কোর্সের পর্ব ১৮-এ)।

মূল উপলব্ধি: associative array-র “অর্থ” শুধু খোঁজা নয়; ক্রম, চাবির নিয়ম আর না-পাওয়ার আচরণও ভাষার চুক্তি। একবার নিশ্চয়তা দিলে ফেরানো যায় না, তাই ভাষা-নকশাকারীরা এটি খুব সাবধানে দেন।

প্র ০৫Composite type-এর সমতা নাম দিয়ে না গঠন দিয়ে — ভাষাগুলো কী বেছেছে, আর compiler-এর জন্য কোনটি কঠিন?

Name equivalence-এর পক্ষে মূল যুক্তি অর্থের নিরাপত্তা। ধরুন record Taka { v: Int } আর record Kg { v: Int }. গঠন এক, কিন্তু টাকার জায়গায় কেজি পাঠানো প্রায় নিশ্চিত ভুল। নাম দিয়ে তুলনা করলে compiler এই ভুল ধরে। Ada এই দর্শনে সবচেয়ে কড়া: type Kg is new Integer; লিখলেই একটি নতুন, আলাদা type, আর মেশাতে হলে স্পষ্ট রূপান্তর। Pascal-এর মূল সংজ্ঞায় এই প্রশ্নটি অস্পষ্ট ছিল বলে সমালোচনা আছে।

Structural equivalence-এর পক্ষে যুক্তি নমনীয়তা আর আলাদা অংশের যোগাযোগ। দুটি আলাদা library যদি দুজনেই {x, y} আকারের মান চায়, গঠন দিয়ে তুলনা করলে কোনো আঠা-কোড লাগে না। TypeScript এজন্যই structural: JavaScript-এর জগতে object প্রায়ই হাতে লেখা literal, কোনো class ছাড়াই। Go মাঝামাঝি: নাম-দেওয়া type আলাদা, কিন্তু interface মেনে চলা গঠন দেখে ঠিক হয়। Modula-3 মূলত structural, তবে “branded” type দিয়ে ইচ্ছা করলে নাম-ভিত্তিক আলাদা type বানানো যায়।

Compiler-এর দিক থেকে name equivalence প্রায় বিনা খরচে: প্রতিটি ঘোষণাকে একটি অনন্য পরিচয় দিন, তুলনা মানে পরিচয় মেলানো। Structural equivalence-এ গাছ ধরে তুলনা করতে হয়, আর recursive type-এ (যেমন linked list-এর node, যা নিজের দিকে reference রাখে) সরল recursive তুলনা অসীম loop-এ পড়ে। সমাধান হলো “এই জোড়া এখন তুলনা হচ্ছে, ধরে নিই সমান” মনে রেখে এগোনো, যা গাণিতিকভাবে coinduction-এর ধারণা; Amadio আর Cardelli-র ১৯৯০-এর দশকের কাজ recursive type-এর subtyping-এ এর একটি প্রভাবশালী বিবরণ দেয় বলে জানা যায়। Subtyping যোগ হলে (একটি record-এ বাড়তি field থাকলে চলবে কি না) প্রশ্ন আরও জটিল হয়, যা পর্ব ৩৬-এর বিষয়।

মূল উপলব্ধি: নাম দিয়ে সমতা অর্থ রক্ষা করে আর সহজ বাস্তবায়ন দেয়; গঠন দিয়ে সমতা নমনীয়তা দেয় কিন্তু compiler-কে কাজ বেশি করতে হয়। বেশিরভাগ বাস্তব ভাষা দুটি মিশিয়ে চলে, প্রতিটি type constructor-এর জন্য আলাদা সিদ্ধান্তে।

অনুশীলন

প্রথমে নিজে করুন, তারপর উত্তর খুলে মেলান। প্রতিটি সংখ্যা Python script বা Clang 22.1.8-এ চালিয়ে মেলানো।

  1. নকশা ও বাস্তবায়ন — Haat-এর বর্ধিত রূপে element-এ লেখা: অংশ ৫-এর প্রস্তাবে শুধু পড়া আছে। এবার orders[i].qty = e; যোগ করুন। (ক) Haat v1-এ assignment-এর লক্ষ্য শুধু একটি সাধারণ নাম হতে পারে (reference-এর নকশা-সিদ্ধান্ত ৯)। কোন নিয়ম বদলাতে হবে, আর একটি typing rule লিখুন। (খ) let orders = [...] দিয়ে ঘোষিত array-র element কি বদলানো যাবে? একটি নীতি বেছে যুক্তি দিন। (গ) অংশ ৫-এর Python মডেলে একটি store_field লিখে orders[1].qty = 3; চালান, মোট আবার হিসাব করুন, আর orders[2].qty = 3;-এ কী হয় দেখান।

    (ক) Parser-এ assignment-এর লক্ষ্য এখন একটি “place expression”: নাম, অথবা place-এর পরে [e] বা .f. Typing rule: Γ ⊢ p : T (p একটি place) আর Γ ⊢ e : T হলে p = e; বৈধ statement. সঙ্গে v1-এর সব শর্ত থাকে: ==-এর মতো এখানেও implicit রূপান্তর নেই, আর evaluation order বাঁ থেকে ডানে (নকশা-সিদ্ধান্ত ১২), তাই orders[f()].qty = g();-এ আগে f(), তারপর g().

    (খ) দুটি যুক্তিসংগত নীতি আছে। JavaScript-এর const-এর মতো: নামটি অন্য array-তে বাঁধা যাবে না, কিন্তু ভেতরের element বদলানো যাবে। Rust-এর মতো: let মানে পুরো মান অপরিবর্তনীয়, element-ও বদলানো যায় না; বদলাতে হলে var. Haat-এ let আর var-এর পার্থক্য খুব স্পষ্ট (পর্ব ০৬), তাই দ্বিতীয় নীতি বেশি সামঞ্জস্যপূর্ণ। তবে aliasing মাথায় রাখুন: var b = orders; যদি একই array-র দ্বিতীয় নাম হয় (কপি নয়), তাহলে b দিয়ে বদলালে let orders-ও বদলে যাবে; তাই নিয়মটি পুরোপুরি রাখতে হলে assignment-এ array কপি করতে হবে।

    def store_field(arr, i, rec, field, value, pos):
        n = heap[arr]
        if not 0 <= i < n:
            raise HaatRuntimeError(
                f"{pos}: runtime error: index {i} out of bounds for length {n}")
        heap[arr + 1 + i * len(RECORDS[rec]) + offset(rec, field)] = value
    
    # orders[1].qty = 3;  then  orders[2].qty = 3;
    heap: [2, 2, 520, 3, 60]
    total: 1220
    8:7: runtime error: index 2 out of bounds for length 2

    (গ) সত্যিকারের run (CPython 3.14.4, অংশ ৫-এর মডেলের ওপর)। slot 3-এ 1 থেকে 3, তাই মোট 2 × 520 + 3 × 60 = 1220; সীমার বাইরে লেখা পড়ার মতোই থামে, কোনো slot বদলানোর আগে। এখানে 8:7 একটি কাল্পনিক অবস্থান। C-তে সীমার বাইরে লেখা পড়ার চেয়েও বিপজ্জনক, কারণ অন্য ডেটা নীরবে বদলে যায়।

  2. ভুল খুঁজুন: একজন int A[5][6] (base 1000, s = 4)-এর column-major ঠিকানার জন্য লিখেছেন BASE + (j * COLS + i) * SIZE. A[0][0]-এ উত্তর ঠিক 1000 আসে, তাই তিনি নিশ্চিত। ভুলটি কী? এমন একটি পরীক্ষা বলুন যা ভুলটি সঙ্গে সঙ্গে ধরবে।

    Column-major-এ j-টি পূর্ণ কলাম পার হতে হয়, আর প্রতিটি কলামে ঘর আছে ROWS-টি (৫), COLS-টি (৬) নয়। তাই সঠিক সূত্র BASE + (j * ROWS + i) * SIZE. A[0][0]-এ j = 0, তাই ভুল গুণফল চোখে পড়ে না; শূন্য দিয়ে পরীক্ষা করা একটি দুর্বল পরীক্ষা। Script-এ চালানো ফল:

    wrong A[2][3]: 1080 right: 1068
    wrong A[4][5]: 1136 last cell should be 1116
    wrong distinct: 30 max: 1136 holes: [1020, 1044, 1068, 1092, 1116]

    ভুল সূত্রে ৩০টি ঘর আলাদা ঠিকানা পায় ঠিকই, কিন্তু শেষ ঘর A[4][5] যায় 1136-এ, যেখানে array শেষ হয় 1116-এ: array-র বাইরে লেখা। আর 1020, 1044, 1068, 1092, 1116 কখনো ব্যবহার হয় না (ফাঁক)। দুটি শক্ত পরীক্ষা: (১) সব ঘরের ঠিকানা মিলে ঠিক BASE থেকে BASE + (ROWS × COLS − 1) × s পর্যন্ত প্রতিটি গুণিতক একবার করে ঢাকে কি না; (২) অংশ ৩-এর মতো ঘরগুলো এক এক করে বিছিয়ে তুলনা। দ্বিতীয় পরীক্ষা ROWS ≠ COLS হলে যেকোনো উল্টাপাল্টা ধরে; বর্গাকার টেবিলে (ROWS = COLS) এই ভুল লুকিয়ে থাকে, তাই পরীক্ষার টেবিল সবসময় অবর্গাকার নিন।

  3. হিসাব করুন: একটি ভাষায় A[1..10][1..20] ঘোষিত (নিম্নসীমা দুই মাত্রাতেই 1), প্রতিটি উপাদান 8 byte, base 2000. A[4][7]-এর ঠিকানা row-major আর column-major দুই রীতিতে বের করুন। তারপর বলুন, শূন্য-ভিত্তিক C-তে double A[10][20]-এ একই ঘরটি কোন index-এ।

    Row-major: আগে নিম্নসীমা বিয়োগ: i − 1 = 3, j − 1 = 6. পার হওয়া ঘর 3 × 20 + 6 = 66; ঠিকানা 2000 + 66 × 8 = 2528.

    Column-major: পার হওয়া ঘর (j − 1) × ROWS + (i − 1) = 6 × 10 + 3 = 63; ঠিকানা 2000 + 63 × 8 = 2504.

    দুটিই অংশ ৩-এর general() function-এ BASE = 2000, SIZE = 8 বসিয়ে চালিয়ে মেলানো: 2528 2504. শূন্য-ভিত্তিক C-তে একই ঘর হলো A[3][6], আর C row-major, তাই সেখানে উত্তর 2528. পরীক্ষায় সবচেয়ে প্রচলিত ভুল হলো নিম্নসীমা বিয়োগ না করা: তাহলে row-major-এ (4 × 20 + 7) × 8 = 696, ঠিকানা 2696, যা ভুল।

  4. প্রমাণ — row-major বিন্যাস একটি নিখুঁত মিল: n মাত্রার array, মাত্রাগুলোর আকার d1, …, dn (সব ≥ 1), index 0 ≤ ik < dk. সংজ্ঞা দিন pos1 = i1, posk = posk−1 × dk + ik. প্রমাণ করুন: posn প্রতিটি index-tuple-কে 0 থেকে D − 1 (D = d1 × … × dn)-এর ঠিক একটি সংখ্যায় পাঠায়, আর দুটি আলাদা tuple কখনো একই সংখ্যা পায় না।

    প্রমাণ, n-এর ওপর induction দিয়ে। দাবি P(n): প্রথম n মাত্রার জন্য posn সব tuple-কে {0, …, Dn − 1}-এ পাঠায় (Dn = d1 × … × dn), আর এই মিলটি এক-এক ও সম্পূর্ণ (bijection).

    1. ভিত্তি n = 1: pos1 = i1, আর 0 ≤ i1 < d1 = D1; প্রতিটি সংখ্যা ঠিক একটি index থেকে আসে।
    2. সীমা: ধরুন P(n − 1) সত্য। তাহলে 0 ≤ posn−1 ≤ Dn−1 − 1, তাই 0 ≤ posn = posn−1 × dn + in ≤ (Dn−1 − 1) × dn + (dn − 1) = Dn − 1.
    3. এক-এক: ধরুন দুটি tuple-এর posn সমান। 0 ≤ in < dn, তাই posn-কে dn দিয়ে ভাগ করলে ভাগশেষ in আর ভাগফল posn−1 (ভাগের অনন্যতা)। কাজেই দুটির in সমান আর posn−1 সমান; P(n − 1) থেকে বাকি সব index-ও সমান।
    4. সম্পূর্ণ: tuple আছে ঠিক Dn-টি, লক্ষ্যের সংখ্যাও Dn-টি; এক-এক মিল দুই সমান-আকারের সসীম set-এর মধ্যে হলে সম্পূর্ণ। ∎

    এই প্রমাণ থেকে দুটি ব্যবহারিক সিদ্ধান্ত: (১) Dn × s byte-ই যথেষ্ট আর দরকারি: কোনো ফাঁক বা দুজনের একই ঘর নেই, তাই অনুশীলন ২-এর ভুল সূত্রটি এই শর্ত ভাঙে। (২) প্রমাণে d1 শুধু সীমায় লেগেছে, গুণে নয়; এটিই অংশ ৩-এর পর্যবেক্ষণ যে প্রথম মাত্রার আকার ঠিকানার সূত্রে লাগে না। Column-major একই প্রমাণ, মাত্রার ক্রম উল্টে।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমBounds checking আছে এমন একটি বাস্তবায়নে orders[i].unit (orders হলো Order record-এর array) পড়ার কাজগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. orders-এর মান (array-র শুরুর ঠিকানা) বের করা
  2. index i-এর মান হিসাব করা
  3. 0 ≤ i আর i দৈর্ঘ্যের চেয়ে ছোট কি না পরীক্ষা
  4. base + i × (Order-এর মাপ) + unit-এর offset হিসাব
  5. সেই ঠিকানা থেকে মান পড়া

C-তে int A[5][6], base ঠিকানা 1000, int-এর মাপ 4 byte. A[2][3]-এর ঠিকানা কত?

  • 1068
  • 1060
  • 1015
  • 1052

Fortran-রীতিতে (column-major, index 1 থেকে) B(1:5, 1:6), উপাদানের মাপ 4 byte, base 1000. B(3,4)-এর ঠিকানা কত?

  • 1092
  • 1060
  • 1080
  • 1068

x86-64-এ union Box { int64_t i; double d; unsigned char b[8]; }; আর struct S { int64_t i; double d; unsigned char b[8]; };-এর sizeof কত?

  • union 24, struct 24
  • union 8, struct 8
  • union 8, struct 24
  • union 16, struct 24

Python 3.7 বা পরের version-এ d = {"rice": 40, "10": 1, "oil": 12} তারপর list(d) কী দেবে?

  • ['rice', '10', 'oil']
  • ['10', 'rice', 'oil']
  • ['10', 'oil', 'rice']
  • ক্রম এলোমেলো, প্রতি run-এ বদলাতে পারে

C17-এ int qty[3] = {2, 5, 1}; তারপর printf("%d", qty[3]); সম্পর্কে কোনটি সঠিক?

  • C standard অনুযায়ী এটি একটি compile error
  • এটি undefined behavior; warning বা sanitizer সাহায্য করতে পারে, কিন্তু ফলের কোনো নিশ্চয়তা নেই
  • Program একটি exception ছুড়ে থামে, Java-র মতো
  • qty[3] ঘুরে এসে qty[0], অর্থাৎ 2 দেয়

একই ফাইলে C-তে struct Point { int x; int y; }; আর struct Size { int x; int y; }; ঘোষিত। struct Size চায় এমন function-এ একটি struct Point পাঠালে কী হয়, আর কেন?

  • চলে, কারণ দুটির গঠন একই
  • চলে, compiler নিজে রূপান্তর করে নেয়
  • Error হয়, কারণ C-র struct-এ name equivalence: আলাদা ঘোষণা মানে আলাদা type
  • Compile হয়, কিন্তু চলার সময় crash করে

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. পাঁচ রূপ: array (একই type, index), record (নাম), tuple (অবস্থান), union (একই জায়গায় কয়েক রকম), map/set (চাবি)। প্রতিটি একটি type constructor.
  2. ঠিকানা: b + (i − lb) × s; দুই মাত্রায় row-major b + (i × COLS + j) × s, column-major b + (j × ROWS + i) × s. int A[5][6]-এ A[2][3]: 1060 বনাম 1068.
  3. সীমা: Java আর Python পরীক্ষা করে; C করে না (undefined behavior), আর pointer-এ দৈর্ঘ্য না থাকায় sanitizer-ও সব ধরে না। Haat-এর বর্ধিত রূপে পরীক্ষা চলার সময়ে, কারণ দৈর্ঘ্য type-এর অংশ নয়।
  4. Field মানে offset: compile-এর সময় জানা, তাই o->unit = একটি load (movq 8(%rdi), ld a0, 8(a0)). Array-র index-এ চলার সময়ের গুণ লাগে।
  5. Union: মাপ সবচেয়ে বড় member-এর; punning C-তে মোটামুটি স্বীকৃত, C++-এ UB, নিরাপদ পথ memcpy. Tag ছাড়া ভুল পড়া কেউ ধরে না; tagged union আর ADT সেই ফাঁক বন্ধ করে।

পরের পর্বে: এই পর্বে array-র নাম বারবার pointer হয়ে গেছে, আর slice দিয়ে একই ডেটায় দুই নাম পৌঁছেছে। পর্ব ২৩-এ pointer আর reference পুরোটা: pointer arithmetic, aliasing, dangling pointer, null আর তার বিকল্প।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান