درس ۱۷ از ۴۹ · داده‌ها و گونه‌ها

تابع‌های عام و میانجی‌ها

با تابع‌های عام یک تابع یا یک ظرف را یک بار می‌نویسید و با هر گونه‌ای به کار می‌برید. میانجی‌ها می‌گویند یک گونه چه کارهایی بلد است، تا بشود گونه‌های مختلف را با یک کد مشترک به کار گرفت.

تابع و ساختار عام

با نوشتن <ت> پس از نام، تابع یا ساختار برای هر گونه‌ی ت کار می‌کند. مترجم برای هر گونه‌ای که واقعاً به کار ببرید یک نسخه‌ی جداگانه و مخصوص همان گونه می‌سازد، پس کد عام به همان سرعتی اجرا می‌شود که اگر برای آن گونه دستی نوشته بودید.

generics.salam
ساختار جعبه<ت>:
    همگانی درون: ت
پایان

تابع بیشینه<ت>(الف: ت، ب: ت): ت:
    اگر الف > ب:
        برگشت الف
    پایان
    برگشت ب
پایان

تابع ریشه:
    سرچاپ بیشینه(۳، ۹)، بیشینه("الف"، "ب")، بیشینه(۲.۵، ۱.۵)
    ج := جعبه { درون = "هدیه" } برگردان جعبه<رشته>
    سرچاپ ج.درون
پایان
خروجی9 ب 2.5 هدیه

گونه‌ی تابع عام از روی ورودی‌هایش معلوم می‌شود: بیشینه(۳، ۹) با صحیح کار می‌کند و بیشینه("الف"، "ب") با رشته. نمی‌توانید گونه را هنگام صدا زدن بنویسید (بیشینه<صحیح>(۳، ۹) خطای تجزیه است)، پس اگر می‌خواهید یک عدد گونه‌ی دیگری داشته باشد، آن را با برگردان تبدیل کنید. ساختار عام گونه‌اش را از تبدیل می‌گیرد، مثل جعبه { ... } برگردان جعبه<رشته>.

بدنه‌ی تابع باید برای هر گونه‌ای که به آن می‌دهید معنا داشته باشد. بیشینه با > مقایسه می‌کند که برای عدد و رشته کار می‌کند. اگر دو ساختار به آن بدهید، مترجم با این پیام می‌ایستد: E021: نمی‌توان 'نقطه' و 'نقطه' را مقایسه کرد.

یک ظرف عام

بیشتر کدهای عامی که می‌نویسید ظرف‌اند: ساختاری که مقدارهایی از یک گونه را نگه می‌دارد و چند کار ساده و روشن روی آن‌ها انجام می‌دهد. این پشته اقلامش را در یک وکتور<ت> نگه می‌دارد و فقط کارهایی را بیرون می‌دهد که از یک پشته انتظار می‌رود. همین یک کد هم تاریخچه‌ی «واگرد» یک ویرایشگر را نگه می‌دارد و هم فهرست صفحه‌هایی را که دیده‌اید.

generics-stack.salam
ساختار پشته<ت>:
    اقلام: وکتور<ت> = وکتور {}

    همگانی تابع بگذار(مقدار: ت):
        این.اقلام.بیفزا(مقدار)
    پایان

    همگانی تابع بردار(): ت:
        برگشت این.اقلام.دربیاور()
    پایان

    همگانی تابع رویی(): ت:
        برگشت این.اقلام.بگیر(این.اقلام.طول() - ۱)
    پایان

    همگانی تابع تعداد(): صحیح:
        برگشت این.اقلام.طول()
    پایان

    همگانی تابع خالی است(): منطقی:
        برگشت این.اقلام.طول() == ۰
    پایان

    همگانی تابع آزادکن():
        این.اقلام.آزادکن()
    پایان
پایان

تابع ریشه:
    واگرد := پشته {} برگردان پشته<رشته>
    دیرکن واگرد.آزادکن()
    واگرد.بگذار("نوشتن «سلام»")
    واگرد.بگذار("پررنگ کردن")
    واگرد.بگذار("پاک کردن یک خط")
    سرچاپ واگرد.تعداد()، "گام، آخرین:"، واگرد.رویی()
    تا وارونه واگرد.خالی است():
        سرچاپ "واگرد"، واگرد.بردار()
    پایان

    صفحه‌ها := پشته {} برگردان پشته<صحیح>
    دیرکن صفحه‌ها.آزادکن()
    صفحه‌ها.بگذار(۱)
    صفحه‌ها.بگذار(۱۴)
    سرچاپ "بازگشت به صفحه‌ی"، صفحه‌ها.بردار()
پایان
خروجی3 گام، آخرین: پاک کردن یک خط واگرد پاک کردن یک خط واگرد پررنگ کردن واگرد نوشتن «سلام» بازگشت به صفحه‌ی 14

این ساختار صاحب یک وکتور است، پس تابع آزادکن هم دارد و هر پشته درست پس از ساخته شدن با دیرکن آزاد می‌شود. این همان عادتی است که برای وکتور معمولی دارید؛ دلیلش در درس حافظه آمده است.

چند پارامتر گونه

یک عام می‌تواند چند گونه بگیرد که با ویرگول از هم جدا می‌شوند. جفت<الف، ب> دو مقدار از دو گونه‌ی متفاوت نگه می‌دارد و جابجا از یک جفت<الف، ب> یک جفت<ب، الف> می‌سازد. وقتی ساختار عام را چاپ می‌کنید، گونه‌هایی که با آن ساخته شده هم نشان داده می‌شوند (فعلاً با نام انگلیسی‌شان).

generics-pair.salam
ساختار جفت<الف، ب>:
    همگانی اولی: الف
    همگانی دومی: ب
پایان

تابع جابجا<الف، ب>(ج: جفت<الف، ب>): جفت<ب، الف>:
    برگشت جفت { اولی = ج.دومی، دومی = ج.اولی }
پایان

تابع ریشه:
    موجودی := جفت { اولی = "مداد"، دومی = ۱۲۰ } برگردان جفت<رشته، صحیح>
    سرچاپ موجودی
    سرچاپ جابجا(موجودی)
    نقطه := جفت { اولی = ۲.۵، دومی = -۱.۰ } برگردان جفت<اعشار۶۴، اعشار۶۴>
    سرچاپ نقطه.اولی + نقطه.دومی
پایان
خروجیجفت<رشته، صحیح> {اولی = "مداد", دومی = 120} جفت<صحیح، رشته> {اولی = 120, دومی = "مداد"} 1.5

میانجی

میانجی فهرستی از امضای روش‌هاست. هر ساختاری که همه‌ی آن روش‌ها را داشته باشد، خودبه‌خود آن میانجی را پیاده کرده است و لازم نیست جایی اعلامش کنید. ورودی‌ای از گونه‌ی پویا شکل هر مقداری را می‌پذیرد که گونه‌اش میانجی شکل را دارد.

interface.salam
میانجی شکل:
    تابع مساحت(): صحیح
    تابع نام(): رشته
پایان

ساختار مربع:
    ضلع: صحیح = ۰
    همگانی تابع مساحت(): صحیح: برگشت این.ضلع * این.ضلع پایان
    همگانی تابع نام(): رشته: برگشت "مربع" پایان
پایان

ساختار مستطیل:
    پهنا: صحیح = ۰
    بلندی: صحیح = ۰
    همگانی تابع مساحت(): صحیح: برگشت این.پهنا * این.بلندی پایان
    همگانی تابع نام(): رشته: برگشت "مستطیل" پایان
پایان

تابع توصیف(ش: پویا شکل):
    سرچاپ ش.نام()، ش.مساحت()
پایان

تابع ریشه:
    توصیف(مربع { ضلع = ۵ })
    توصیف(مستطیل { پهنا = ۴، بلندی = ۶ })
پایان
خروجیمربع 25 مستطیل 24

روش میانجی می‌تواند بدنه‌ی پیش‌فرض داشته باشد. ساختاری که آن روش را ننویسد نسخه‌ی پیش‌فرض را می‌گیرد و ساختاری که بنویسد نسخه‌ی خودش را نگه می‌دارد. بدنه‌ی پیش‌فرض می‌تواند با این بقیه‌ی روش‌های میانجی را صدا بزند.

interface-default.salam
میانجی شکل:
    تابع مساحت(): اعشار۶۴
    تابع شرح(): رشته:
        برگشت "مساحت " + این.مساحت()
    پایان
پایان

ساختار دایره:
    همگانی شعاع: اعشار۶۴ = ۱.۰
    همگانی تابع مساحت(): اعشار۶۴:
        برگشت ۳.۱۴ * این.شعاع * این.شعاع
    پایان
پایان

ساختار مربع:
    همگانی ضلع: اعشار۶۴ = ۱.۰
    همگانی تابع مساحت(): اعشار۶۴:
        برگشت این.ضلع * این.ضلع
    پایان
    همگانی تابع شرح(): رشته:
        برگشت "مربعی با ضلع " + این.ضلع
    پایان
پایان

تابع ریشه:
    سرچاپ دایره { شعاع = ۲.۰ }.شرح()
    سرچاپ مربع { ضلع = ۳.۰ }.شرح()
پایان
خروجیمساحت 12.56 مربعی با ضلع 3

اگر گونه‌ای یکی از روش‌ها را نداشته باشد، مترجم همان‌جا که مقدار به‌جای میانجی به کار رفته خبر می‌دهد: E002: 'جعبه' میانجی 'امتیازدار' را پیاده‌سازی نمی‌کند: متد 'امتیاز' موجود نیست.

کاربست: میانجی برای گونه‌های آماده

کاربست میانجی بر گونه روش‌های یک میانجی را به گونه‌ای می‌دهد که خودتان ننوشته‌اید، حتی گونه‌های پایه‌ای مثل صحیح و رشته. درون این روش‌ها این خود مقدار است. <ت: رتبه‌دار> در این مثال یک محدودیت گونه است: تابع فقط گونه‌هایی را می‌پذیرد که میانجی رتبه‌دار را دارند.

impl.salam
میانجی رتبه‌دار:
    تابع رتبه(): صحیح
پایان

کاربست رتبه‌دار بر صحیح:
    تابع رتبه(): صحیح: برگشت این پایان
پایان

کاربست رتبه‌دار بر رشته:
    تابع رتبه(): صحیح: برگشت طول(این) پایان
پایان

تابع بالاتر<ت: رتبه‌دار>(الف: ت، ب: ت): صحیح:
    اگر الف.رتبه() > ب.رتبه():
        برگشت الف.رتبه()
    پایان
    برگشت ب.رتبه()
پایان

تابع ریشه:
    سرچاپ بالاتر(۳، ۹)
    سرچاپ بالاتر("hi"، "salam")
پایان
خروجی9 5

محدودیت گونه: عام‌هایی که روش صدا می‌زنند

یک <ت> ساده هیچ چیزی درباره‌ی ت نمی‌داند، پس بدنه نمی‌تواند روشی روی آن صدا بزند. محدودیتی مثل <ت: امتیازدار> قول می‌دهد که هر ت روش‌های امتیازدار را دارد، و بدنه آزاد است آن‌ها را به کار ببرد. محدودیت روی ساختار هم می‌نشیند: جدول<ت: امتیازدار> جدول امتیازی است برای بازیکن‌ها، پیشنهادهای یک مزایده یا هر چیز دیگری که امتیاز داشته باشد.

generics-bound.salam
میانجی امتیازدار:
    تابع امتیاز(): صحیح
    تابع برچسب(): رشته
پایان

ساختار بازیکن:
    همگانی نام: رشته = ""
    همگانی امتیازها: صحیح = ۰
    همگانی تابع امتیاز(): صحیح: برگشت این.امتیازها پایان
    همگانی تابع برچسب(): رشته: برگشت این.نام پایان
پایان

ساختار پیشنهاد:
    همگانی خریدار: رشته = ""
    همگانی مبلغ: صحیح = ۰
    همگانی تابع امتیاز(): صحیح: برگشت این.مبلغ پایان
    همگانی تابع برچسب(): رشته: برگشت این.خریدار + " با " + این.مبلغ پایان
پایان

ساختار جدول<ت: امتیازدار>:
    ردیف‌ها: وکتور<ت> = وکتور {}

    همگانی تابع بیفزای(مورد: ت):
        این.ردیف‌ها.بیفزا(مورد)
    پایان

    همگانی تابع بهترین(): ت:
        ناپایا برتر := این.ردیف‌ها.بگیر(۰)
        هر ر در این.ردیف‌ها:
            اگر ر.امتیاز() > برتر.امتیاز():
                برتر = ر
            پایان
        پایان
        برگشت برتر
    پایان

    همگانی تابع جمع کل(): صحیح:
        ناپایا جمع := ۰
        هر ر در این.ردیف‌ها:
            جمع += ر.امتیاز()
        پایان
        برگشت جمع
    پایان

    همگانی تابع آزادکن():
        این.ردیف‌ها.آزادکن()
    پایان
پایان

تابع بالاتر<ت: امتیازدار>(الف: ت، ب: ت): ت:
    اگر ب.امتیاز() > الف.امتیاز():
        برگشت ب
    پایان
    برگشت الف
پایان

تابع ریشه:
    تیم := جدول {} برگردان جدول<بازیکن>
    دیرکن تیم.آزادکن()
    تیم.بیفزای(بازیکن { نام = "سارا"، امتیازها = ۴۲ })
    تیم.بیفزای(بازیکن { نام = "رضا"، امتیازها = ۵۷ })
    تیم.بیفزای(بازیکن { نام = "مینا"، امتیازها = ۴۹ })
    سرچاپ "بهترین بازیکن:"، تیم.بهترین().برچسب()
    سرچاپ "جمع امتیاز تیم:"، تیم.جمع کل()

    اول := پیشنهاد { خریدار = "علی"، مبلغ = ۱۲۰ }
    دوم := پیشنهاد { خریدار = "نیما"، مبلغ = ۱۵۰ }
    سرچاپ "پیشنهاد برنده:"، بالاتر(اول، دوم).برچسب()
پایان
خروجیبهترین بازیکن: رضا جمع امتیاز تیم: 148 پیشنهاد برنده: نیما با 150

هر جدول فقط یک گونه را نگه می‌دارد: جدول<بازیکن> نمی‌تواند پیشنهاد هم نگه دارد. این روی دیگر سرعت عام‌هاست، و دقیقاً همان مشکلی است که پویا حل می‌کند.

مجموعه‌های ناهمگون با پویا

پویا پیام‌رسان مقداری از هر گونه‌ای است که میانجی پیام‌رسان را دارد و گونه‌اش هنگام اجرا معلوم می‌شود. با آن یک فهرست می‌تواند گونه‌های مختلف را کنار هم نگه دارد: وکتور<پویا پیام‌رسان> در مثال زیر یک فرستنده‌ی ایمیل و دو فرستنده‌ی پیامک دارد و یک حلقه از راه همه‌ی آن‌ها پیام می‌فرستد. فیلد ساختار هم می‌تواند پویا باشد، تا یک هشدار را به هر راهی که خواستید وصل کنید.

interface-dyn.salam
میانجی پیام‌رسان:
    تابع بفرست(گیرنده: رشته، متن: رشته): منطقی
    تابع راه(): رشته
پایان

ساختار ایمیل:
    همگانی سرور: رشته = "mail.example.com"
    همگانی تابع بفرست(گیرنده: رشته، متن: رشته): منطقی:
        سرچاپ "  ایمیل به"، گیرنده، "از"، این.سرور، "|"، متن
        برگشت درست
    پایان
    همگانی تابع راه(): رشته: برگشت "ایمیل" پایان
پایان

ساختار پیامک:
    همگانی اعتبار: صحیح = ۰
    همگانی تابع بفرست(گیرنده: رشته، متن: رشته): منطقی:
        اگر این.اعتبار == ۰:
            برگشت نادرست
        پایان
        سرچاپ "  پیامک به"، گیرنده، "|"، متن
        برگشت درست
    پایان
    همگانی تابع راه(): رشته: برگشت "پیامک" پایان
پایان

ساختار هشدار:
    همگانی با: پویا پیام‌رسان = ایمیل {}
    همگانی تابع بزن(گیرنده: رشته):
        شد := این.با.بفرست(گیرنده، "دیسک تقریباً پر است")
        سرچاپ "هشدار با"، این.با.راه()، شد ? "فرستاده شد" : "نرسید"
    پایان
پایان

تابع ریشه:
    راه‌ها := وکتور {} برگردان وکتور<پویا پیام‌رسان>
    راه‌ها.بیفزا(ایمیل {})
    راه‌ها.بیفزا(پیامک { اعتبار = ۰ })
    راه‌ها.بیفزا(پیامک { اعتبار = ۵ })
    ناپایا رسیده := ۰
    هر ر در راه‌ها:
        اگر ر.بفرست("سارا"، "سفارش شما ارسال شد"):
            رسیده++
        پایان
    پایان
    سرچاپ رسیده، "از"، راه‌ها.طول()، "پیام رسید"
    هر ر در راه‌ها:
        ر.آزادکن()
    پایان
    راه‌ها.آزادکن()

    زنگ := هشدار { با = پیامک { اعتبار = ۱ } }
    زنگ.بزن("پشتیبانی")
    زنگ.با.آزادکن()
پایان
خروجی ایمیل به سارا از mail.example.com | سفارش شما ارسال شد پیامک به سارا | سفارش شما ارسال شد 2 از 3 پیام رسید پیامک به پشتیبانی | دیسک تقریباً پر است هشدار با پیامک فرستاده شد

مقدار پویا در یک جعبه‌ی کوچک روی هیپ نگه داشته می‌شود. گذاشتن مقدار در آن یک رونوشت می‌سازد، پس تغییر بعدی مقدار اصلی به رونوشت نمی‌رسد. آزاد کردن یک وکتور<پویا ...> خود فهرست را آزاد می‌کند ولی جعبه‌های درونش را نه؛ برای همین مثال اول هر عضو را آزاد می‌کند و بعد خود وکتور را. فیلد پویا هم به همین شکل با فیلد.آزادکن() آزاد می‌شود.

عام یا پویا؟

<ت: شکل>پویا شکل
گونه کی معلوم می‌شودهنگام ترجمه، با یک نسخه از کد برای هر گونههنگام اجرا، با یک نسخه از کد برای همه‌ی گونه‌ها
صدا زدن روش‌هامستقیم، به سرعت کد دست‌نویسبا یک گام کوچک برای پیدا کردن روش درست
گونه‌های مختلف در یک مجموعهنه، هر نمونه فقط یک گونهبله، وکتور<پویا شکل>
حافظهمقدارها مستقیم نگه داشته می‌شوندهر مقدار در جعبه‌ای است که باید آزاد شود
مناسب برایظرف‌ها و الگوریتم‌هاگرداننده‌ها، افزونه‌ها، فهرست چیزهای ناهمگون

چند قاعده‌ی سرانگشتی

  • وقتی یک کد برای گونه‌های زیادی درست کار می‌کند، عام بنویسید، و همین که بدنه به روشی نیاز پیدا کرد، محدودیت گونه اضافه کنید.
  • پویا را فقط وقتی به کار ببرید که یک مجموعه یا یک فیلد باید گونه‌های مختلف را نگه دارد.
  • میانجی‌ها را کوچک نگه دارید. پیاده کردن دو سه روش آسان است و پیش‌فرض دادن به آن‌ها هم.
  • با کاربست ... بر به یک گونه‌ی موجود، حتی صحیح یا رشته، میانجی تازه‌ای یاد بدهید، بی‌آنکه به کدش دست بزنید.
  • ظرف عامی که صاحب وکتور یا نگاشت است به تابع آزادکن نیاز دارد، و مقدارهای پویای درون جعبه یکی‌یکی آزاد می‌شوند.

جداشمارهای عامی مثل شاید<ت> و نتیجه<ت، خ> در درس جداشمارها آمده‌اند، و ظرف‌های عام آماده‌ی زبان، یعنی وکتور و نگاشت، در درس مجموعه‌ها.