۲۶ - ۵میشه هسکل رو اکید کنیم؟

ببینیم می‌تونیم رفتار یه زبانِ اکید رو بازسازی کنیم؟ اینطوری تفاوت هسکل رو هم بهتر متوجه میشیم. تو مثالِ بالا، اینطوری میشه اکید بودن رو اضافه کنیم:

hypo' :: IO ()
hypo' = do
  let x :: Integer
      x = undefined
  s <- getLine
  case x `seq` s of
    "hi" -> print x
    _ -> putStrLn "hello"

اجراش چنین جوابی میده:

Prelude> hypo'
asd
*** Exception: Prelude.undefined

چرا؟ چون اون تابعِ کوچولوی ‏‎seq‎‏، خیلی جادویی محاسبه‌ی آرگومانِ اولش رو، در صورتِ محاسبه‌ی آرگومانِ دوم‌ش، اجبار می‌کنه. اون ‏‎seq‎‏ رو که اضافه کردیم، یعنی هر موقع ‏‎s‎‏ محاسبه بشه، ‏‎x‎‏ هم باید محاسبه بشه. کمی جلوتر با جزئیات بیشتری میگیم.

اما قبل از ادامه، دقت کنین تونستیم تابعِ ‏‎getLine‎‏ رو قبل از محاسبه‌ی تهی اجرا کنیم، پس هنوز رفتارش مثل یه زبانِ اکید نشده. بطور کلی بیانیه‌های case محاسبه رو اجبار می‌کنن؛ البته واضحه، چون باید بیانیه محاسبه بشه تا case بتونه حالت‌های مختلف رو براش بررسی کنه. با یه مثال کوچیک نشون میدیم:

let b = ???
case b of
  True -> ...
  False

اینجا ‏‎b‎‏ هر چیزی که باشه، اول باید محاسبه بشه تا معلوم بشه ‏‎True‎‏ میشه یا ‏‎False‎‏.

برگردیم به ‏‎seq‎‏

قبل از ادامه به اکیدتر کردنِ هسکل، یه کم دیگه از ‏‎seq‎‏ صحبت کنیم. اول از همه، تایپ‌ش یه کم... عجیبه:

seq :: a -> b -> b

حتماً با ‏‎flip const‎‏ فرقی داره. در نسخه‌های قدیمیِ هسکل تایپ‌ش اینطور بوده:

seq :: Eval a => a -> b -> b

‏‎Eval‎‏ خلاصه‌ی محاسبه به حالتِ معمولی با سرِ ضعیف‌ (WHNF)هست، و یک متود برای اجبارِ محاسبه تأمین می‌کرد؛ همه‌ی تایپ‌های ‏‎base‎‏ یه نمونه ازش داشتن. حالا که این تایپکلاس حذف شده، دیگه برای استفاده از ‏‎seq‎‏ لازم نیست یه محدودیت به تایپ‌های پلی‌مورفیک اضافه بشه و یه عالَم تغییرات اضافی رو اجبار کنه. نسبت به تهی، تابعِ ‏‎seq‎‏ اینطور تعریف میشه:

seq bottom b                     = bottom
seq literallyAnythingNotBottom b = b
--  ^------------------------^
-- م. به معنای واقعی هرچیزی غیر از تهی

حالا چرا ‏‎seq‎‏ خیلی شبیه پسرعموی ‏‎const‎‏ ِه؟ چون در هسکل، محاسبه برمبنای تقاضاست، و به هیچ عنوان نمیشه تضمین کرد که یه چیزی محاسبه میشه. پس باید در بین گره‌ها در گرافِ بیانیه‌ها پل‌هایی بکشیم تا اجبارِ یک بیانیه، یه بیانیه‌ی دیگه رو هم اجبار کنه. یه مثال دیگه ببینیم:

Prelude> :{
*Main| let wc x z =
*Main|       let y =
*Main|             undefined `seq` 'y' in x
*Main| :}
Prelude> foldr wc 'z' ['a'..'e']
'a'
Prelude> foldr (flip wc) 'z' ['a'..'e']
'z'

اینجا هیچ وقت ‏‎y‎‏ رو اجبار نکردیم، و متعاقباً تهی هم اجبار نکردیم. با این حال میشه یه وابستگیِ داده ِ دیگه از ‏‎y‎‏ به ‏‎x‎‏ درست کنیم:

Prelude> let bot = undefined
Prelude> :{
*Main| let wc x z =
*Main|       let y =
*Main|            bot `seq` 'y'
*Main|       in   y `seq` x
*Main| :}
Prelude> foldr wc 'z' ['a'..'e']
*** Exception: Prelude.undefined
Prelude> foldr (flip wc) 'z' ['a'..'e']
*** Exception: Prelude.undefined

دفعه‌ی قبل وابستگیِ محاسباتی بین مقدارِ تهی و ‏‎y‎‏ بود:

undefined `seq` 'y' in x

-- الزاماً تهی هم اجبار می‌کنه y اجبارِ

y -> undefined

با این تغییری که دادیم، این اتفاق میوفته:

undefined `seq` 'y' `seq` 'x'

-- هم اجبار می‌کنه y الزاماً x اجبارِ
-- الزاماً تهی هم اجبار می‌کنه y اجبارِ

x -> y -> undefined

ما بهش به چشم یه واکنشِ زنجیری نگاه می‌کنیم.

در واقع داریم از یه مقدار به یه مقدار دیگه یه قایق نجات می‌بندیم میگیم "اگه می‌خوای به اون برسی، اول باید از من رَد شی!" حتی میشه این هم-قایق‌ها رو غوطه‌ور بذاریم! نگاه کنین:

notGonnaHappenBru :: Int
notGonnaHappenBru =
  let x = undefined
      y = 2
      z = (x `seq` y `seq` 10, 11)
  in snd z

مثال بالا تهی نمیشه! این رفیق‌های قایقی همینطور وسط دریا شناور موندن و هیچ یدک‌کشِ محاسباتی نمیاد ببَردِشون.

‏‎seq‎‏ و حالت معمولی با سر ضعیف

‏‎seq‎‏ بیانیه رو تا حالت معمولی با سر ضعیف محاسبه می‌کنه. این رو قبلاً توضیح دادیم، اما اگه دوست دارین خیلی عمیق‌تر تفاوت بینِ حالت معمولی با سر ضعیف و حالت معمولی رو یاد بگیرین، به شدت کتابِ سایمون مارلو به اسمِ برنامه‌نویسی موازی و همزمان در هسکل رو پیشنهاد می‌کنیم. محاسبه‌ی WHNF یعنی بعد از اولین داده‌ساز یا لامبدا متوقف میشه. بذارین این فرضیه رو امتحان کنیم!

Prelude> let dc = (,) undefined undefined
Prelude> let noDc = undefined
Prelude> let lam = \_ -> undefined
Prelude> dc `seq` 1
1
Prelude> noDc `seq` 1
*** Exception: Prelude.undefined
Prelude> lam `seq` 1
1

خیلی خوب. چیزی که غیرمنتظره نبود؟ درسته؟ اوکِی.

به خاطر اینکه ‏‎dc‎‏ یه داده‌ساز داره، لازم نیست ‏‎seq‎‏ به مقادیرِ داخل اون سازنده اهمیتی بده؛ برای حالت معمولی با سر ضعیف، محاسبه‌ی سازنده کفایت می‌کنه. از طرف دیگه، ‏‎noDc‎‏ بیرون از مقدارِش داده‌ساز یا لاندا نداره، پس هیچ سَری وجود نداره که محاسبه رو نگه داره. در آخر، ‏‎lam‎‏ یه لامبدا بیرون از بیانیه داره، که در محاسبه همون تأثیری رو داره که یه داده‌ساز داره.

تطبیق ِ case هم محاسبات رو زنجیر می‌کنه

بدونِ ‏‎seq‎‏ هم این اجبار کردن اتفاق میوفته! برای مثال، وقتی روی یه چیزی تطبیق ِ case یا الگو انجام میدین، دارین مقداری که روش تطبیق انجام دادین رو اجبار می‌کنین، چون باید تا عمقی که داده‌ساز‌ها رو براش تعیین کردین بشناسه تا بتونه تطبیق انجام بده. یه مثال ببینیم:

data Test =
    A Test2
  | B Test2
  deriving (Show)

data Test2 =
    C Int
  | D Int
  deriving (Show)

forceNothing :: Test -> Int
forceNothing _ = 0

forceTest :: Test -> Int
forceTest (A _) = 1
forceTest (B _) = 2

forceTest2 :: Test -> Int
forceTest2 (A (C i)) = i
forceTest2 (B (C i)) = i
forceTest2 (A (D i)) = i
forceTest2 (B (D i)) = i

اول ‏‎forceNothing‎‏ رو تست می‌کنیم:

Prelude> forceNothing undefined
0
Prelude> forceNothing (A undefined)
0

هیچ وقت تهی نمیشه چون هیچ چیز رو اجبار نمی‌کنه. در واقع یه مقدارِ ثابت‌ه که آرگومان‌ش رو میندازه زمین. ‏‎forceTest‎‏ چطور؟

Prelude> forceTest (A undefined)
1
Prelude> forceTest (B undefined)
2
Prelude> forceTest undefined
*** Exception: Prelude.undefined

فقط زمانی تهی میشه که مقدارِ ‏‎Test‎‏ ِ بیرونی تهی باشه، دلیل‌ش هم اینه که تنها مقداری که روش تطبیق الگو انجام میدیم اون داده‌ساز ِه. میرسیم به ‏‎forceTest2‎‏:

Prelude> forceTest2 (A (C 0))
0
Prelude> forceTest2 (A (C undefined))
*** Exception: Prelude.undefined

Prelude> forceTest2 (A undefined)
*** Exception: Prelude.undefined

Prelude> forceTest2 undefined
*** Exception: Prelude.undefined

خدمتِ شما: بیرون -> داخل.

روگرفت حافظه

منظور اون روگرفتِ حافظه که ممکنه فکر کنین نیست. اینجا منظور اون زبانِ پشت‌پرده‌ایه که کامپایلر بعد از تلخ کردنِ کدِمون، GHC Haskell رو بهش ساده می‌کنه.

اولین راهی که برای بررسیِ اکید بودن داشتیم، تزریقِ تهی به بیانیه‌ها و مشاهده‌ی محاسبه‌شون بود. تزریقِ تهی باعث میشه به وضوح ببینیم چه چیزی اکیداً حساب میشه و چه چیزی نمیشه. راه دوم برای بررسیِ اکید بودن در هسکل، بررسیِ GHC Core ِه.

با این مثال کار می‌کنیم:

module CoreDump where

discriminatory :: Bool -> Int
discriminatory b =
  case b of
    False -> 0
    True -> 1

اینطوری توی GHC بارگذاری‌ش کنین:

Prelude> :set -ddump-simpl
Prelude> :l code/coreDump.hs
[1 of 1] Compiling CoreDump

================ Tidy Core ==============
... یه کم شلوغی ...

بعد باید این GHC Core رو به عنوان خروجی بگیرین:

discriminatory :: Bool -> Int
[GblId, Arity=1,
 Caf=NoCafRefs,
 Str=DmdType]
discriminatory =
  \ (b_aZJ :: Bool) ->
    case b_aZJ of _ [Occ=Dead] {
      False -> GHC.Types.I# 0;
      True -> GHC.Types.I# 1
    }

رک بگیم: GHC Core یه کم زشته. با این حال راه‌هایی هست که یه کم تروتمیز بشه. یکی‌ش استفاده از پرچم ِ ‏‎-dsuppress-all‎‏ ِه:

Prelude> :set -dsuppress-all
Prelude> :r

دقت کنین ممکنه برای اینکه بارگذاریِ مجدد رو اجبار کنین لازم بشه اول فایل رو یه دست‌کاری بکنین. حالا خروجی این میشه:

discriminatory 
discriminatory =
  \ b_aZY ->
    case b_aZY of _ {
      False -> I# 0;
      True -> I# 1
    }

یه ذره خواناتر شد. با این زبانِ Core ِ ساده‌تر، راحت‌تر میشه فهمید که دقیقاً کِی یه چیزی محاسبه میشه. برای سادگی، یکی از مثال‌های قبلی رو بازبینی کنیم:

forceNothing _ = 0

تو Core این شکلی میشه:

forceNothing = \ _ -> I# 0#

به خاطر اینکه بیانیه‌های case باید محاسبه بشن، اینجا تو GHC Core دنبال بیانیه‌های case می‌گردیم تا ببینیم کجای کدِمون اکیدی داره. اینجا هیچ case ای نیست، پس هیچ چیز رو اجبار نمی‌کنه. اون ‏‎I# 0#‎‏ ارائه‌ی پشت‌پرده‌ی لفظ ِ ‏‎Int‎‏ ِه، که توی GHC Core معلوم شده. نمایش رو ادامه میدیم!

ببینیم Core برای ‏‎forceTest‎‏ چه شکلیه:

forceTest =
  \ ds_d2oX ->
    case ds_d2oX of _ {
      A ds1_d2pI -> I# 1#;
      B ds1_d2pJ -> I# 2#
    }

از روی GHC Core ِ این تابع میشه دید که یک مقدار رو اجبار می‌کنه: بیرونی‌ترین داده‌ساز ِ تایپِ ‏‎Test‎‏ رو. به محتویات اون داده‌ساز‌ها اسم‌هایی داده شده، اما هیچ وقت استفاده نشدن پس محاسبه هم نمیشن.

forceTest2 =
  \ ds_d2n2 ->
    case ds_d2n2 of _ {
      A ds1_d2oV ->
        case ds1_d2oV of _ {
          C i_a1lo -> i_a1lo;
          D i_a1lq -> i_a1lq
        };
      B ds1_d2oW ->
        case ds1_d2oW of _ {
          C i_a1lp -> i_a1lp;
          D i_a1lr -> i_a1lr
        }
    }

بیرون‌بودن و داخل‌بودن با ‏‎forceTest2‎‏ بهتر معلوم‌ه. در بخش بیرونیِ تابع، همون کاری که در ‏‎forceTest‎‏ کردیم رو انجام دادیم، با این تفاوت که اینجا محتویاتِ داده‌ساز ِ ‏‎Test‎‏ ِ بیرونی هم اجبار کردیم. تابع می‌تونه چهار جواب داشته باشه که تهی نیستن، و اگه بهش تهی پاس نشه، همیشه دوبار اجبار می‌کنه – یه بار برای ‏‎Test‎‏ و یه بار برای ‏‎Test2‎‏. محتویاتِ ‏‎Test2‎‏ رو برمی‌گردونه، اما خودش هیچ وقت اونها رو اجبار نمی‌کنه.

در Core، همیشه چیزی که روش case میشه، محاسبه میشه – حتی اگه هیچ تطبیق الگویی انجام نشه – اما در خودِ هسکل، مقادیر وقتی اجبار میشن که روی داده‌ساز‌ها منطبق میشن. اگه دوست دارین با بهره‌گیری از Core کاراییِ کدِ هسکل‌تون یا رفتارش رو بهتر درک کنین، پیشنهاد می‌کنیم مستنداتِ GHC در خصوص Core رو بخونین.

حالا با استفاده از اینها یه چیز رو بررسی کنیم:

discriminatory :: Bool -> Int
discriminatory b =
  let x = undefined
  case b of
    False -> 0
    True -> 1

برای این Core چه شکلیه؟

discriminatory 
discriminatory =
  \ b_a10c ->
    case b_a10c of _ {
      False -> I# 0;
      True -> I# 1
    }

با این دوز و کلک‌ها نمیشه GHC رو گول زد! می‌دونه هیچ وقت ‏‎x‎‏ رو محاسبه نمی‌کنیم، اون هم ولش می‌کنه. اگه مجبورش کنیم اول ‏‎x‎‏ رو محاسبه کنه بعد ‏‎b‎‏ چطور؟

discriminatory :: Bool -> Int
discriminatory b =
  let x = undefined
  in case x `seq` b of
    False -> 0
    True -> 1

به زبانِ Core:

discriminatory =
  \ b_a10D ->
    let {
      x_a10E
      x_a10E = undefined } in
    case
      case x_a10E of _ {
        __DEFAULT -> b_a10D
      } of _ {
        False -> I# 0;
        True -> I# 1
    }

حالا دوتا بیانیه‌ی case وجود داره. یکی‌شون توی اون یکی تودرتو شده تا به ناچار محاسبه‌ی ‏‎x‎‏ قبل از محاسبه‌ی ‏‎b‎‏ انجام بشه. ‏‎seq‎‏ اینطوری کدتون رو تغییر میده.

یه تفاوت در Core

در هسکل، تطبیق ِ case (یا حداقل تطبیقِ الگوش) تا WHNF اکید ِه. در Core، case‌ها همیشه به WHNF اکید اند. این تفاوتی نیست که به نظر مهم بیاد، اما زمان‌هایی وجود دارن که این تفاوت اهمیت پیدا می‌کنه. این بیانیه توی هسکل تهی نمیشه:

case undefined of { _ -> False}

وقتی این کد به Core تبدیل میشه، تشخیص میده که از تطبیق ِ case برای هیچ کاری استفاده نکردیم و کل بیانیه‌ی case رو میندازه، و به یه داده‌ساز ِ ‏‎False‎‏ ساده میشه.

با اینکه این بیانیه‌ی Core از لحاظِ گرامری شبیهِ کدِ هسکلِ بالاست، اما این تهی میشه:

case undefined of { DEFAULT -> False}

case در Core اکید ِه، حتی اگه فقط یه دونه باشه و روی چیزی انطباق انجام نده. Core و هسکل یک زبان نیستن، اما اگه زمانی خواستین بدونین آیا دوتا بیانیه در هسکل یکسان‌اند یا نه، یه راهِ قطعی‌ش اینه که Core رو بررسی کنین.

حالا یه کم اکیدتَر

بعد از گشتی که تو سرزمین عجایب زدیم (!) برگردیم به اصل موضوع: هنوز نتونستیم رفتار تابعِ ‏‎hypo‎‏ در یه زبانِ اکید رو به درستی شبیه‌سازی کنیم؛ آخرین بار بیانیه‌ش تا نصفه محاسبه شد. ‏‎s‎‏ رو محاسبه کردیم که اون هم ‏‎x‎‏ (همون چیزی که منجر به استثنا میشد) رو اجبار کرد. اگه یه زبان اکید بود، حتی ‏‎s‎‏ رو هم محاسبه نمی‌کرد، چون اول باید ‏‎x‎‏ رو محاسبه می‌کرد.

چی کار کنیم این برنامه‌ی هسکل‌مون همون کاری که یه زبانِ اکید می‌کرد رو انجام بده؟

hypo'' :: IO ()
hypo'' = do
  let x :: Integer
      x = undefined
  s <- x `seq` getLine
  case s of
    "hi" -> print x
    _ -> putStrLn "hello"

دقت کنین ‏‎seq‎‏ رو به زودترین جای ممکن در اجراییه ِ ‏‎IO‎‏ بردیم. این دیگه بدونِ اجازه می‌ترکه:

Prelude> hypo''
*** Exception: Prelude.undefined

دلیل‌ش اینه که قبل از محاسبه‌ی ‏‎getLine‎‏ (که اثر ِ "منتظر ورودیِ کاربر بودن" رو پیاده می‌کرد)، محاسبه‌ی تهی رو اجبار کردیم. با اینکه این کد در ظاهر رفتارِ یه زبانِ اکید رو تداعی کرد، اما اگه می‌خواست دقیقاً مثل اون باشه، باید خطا در زمان ساخته شدنِ تهی داده میشد. تا زمانی که مسیرِ محاسباتِ برنامه به یه بیانیه نخوره، امکان نداره اون بیانیه محاسبه بشه.

تمرین‌ها: محاسبه کن

هر بیانیه رو با بیشترین جزئیات ممکن گسترش بدین. بعد از بیرون به داخل پیش برین و ببینید به چه چیزی ساده میشه.

const 1 undefined

const undefined 1

flip const undefined 1

flip const 1 undefined

const undefined undefined

foldr const 'z' ['a'..'e']

foldr (flip const) 'z' ['a'..'e']