۲۶ - ۹به اشتراکگذاری خوبه
بطور کلی منظور از اشتراکگذاری اینه که جوابِ سادهسازیِ یه محاسبهای که اسم داره رو میشه بین همهی ارجاعهای اون اسم، بدون محاسبهی مجدد به اشتراک گذاشت. دلیل اهمیتِ اشتراکگذاری اینه که حافظه محدوده، حتی امروز که تو جیبِ همه یه گوشیِ هوشمند هست. نااکید بودن چیز خوبیه، اما فراخوان-با-اسم همیشه به تنهایی برای بازدهی ِ کافی مناسب نیست. چه چیزی بازدهی ِ کافی داره؟ بستگی به کاری که دارین انجام میدین، و اینکه آیا برای تزِتون هست یا نه داره.
یکی از چیزهایی که خیلیها رو در رابطه با نحوهی اجرای کُد توسط GHC Haskell گیج میکنه، اینه که برمبنای اولویت، و تشخیصِ اینکه چه چیزی کدِ سریعتری درست میکنه، اشتراکگذاری رو خاموش و روشن میکنه (یعنی بین فراخوان-با-نیاز و فراخوان-با-اسم نوسان میکنه). یکی از دلایلی که میتونه بدونِ خراب کردنِ کدِتون چنین کاری بکنه، اینه که کامپایلر میدونه چه زمانی کدِتون I/O اجرا میکنه یا نمیکنه.
استفاده از trace
برای مشاهدهی اشتراکگذاری
کتابخونه ِ base
یه ماژول به اسمِ Debug.Trace
داره که شامل توابعی مناسب برای مشاهدهی اشتراکگذاری ِه. اینجا بیشتر از trace
استفاده میکنیم، اما اگه دوست داشتین، با بقیهی تابعهاش هم بازی کنین. با Debug.Trace
در واقع تایپ سیستم رو گول میزنیم و بدونِ IO
در تایپ، از putStrLn
استفاده میکنیم. این از چیزهاییه که باید فقط در آزمایشها و آموزش و یادگیری ازش استفاده کنین؛ اصلاً ازش به عنوان یه راهِ گزارشنویسی در کدِ نهایی استفاده نکنین – کاری که انتظار دارین رو انجام نمیده. با همهی اینها، یه راه آسون برای مشاهدهی اینکه کِی یه چیزی حساب شده در اختیار میذاره.
اینطوری میشه ازش استفاده کرد:
Prelude> import Debug.Trace
Prelude> let a = trace "a" 1
Prelude> let b = trace "b" 1
Prelude> a + b
b
a
3
این مثال از اشتراکگذاری نیست، اما نشون میده که چطور میشه از trace
برای مشاهدهی محاسبات استفاده کرد. میبینیم که b
اول چاپ شد چون اولین آرگومانی بود که تابعِ جمع حساب کرد، اما نمیتونین (و نباید) به ترتیبِ محاسبهی آرگومانهای تابعِ جمع اتکا کنین. اینجا کاری با شرکتپذیری نداریم، داریم راجع به ترتیبی که آرگومانهای یک اعمال ِ مجرد از جمع اجبار میشن صحبت میکنیم. به شرکتپذیری از چپِ تابعِ جمع مطمئن باشین، اما هیچ تضمینی نیست که بین یک جفت آرگومان ورودی، اول کدوم اجبار بشه.
با یه مثال طولانیتر ببینیم چطور جایی که محاسبه انجام میشه رو نشون میده:
import Debug.Trace (trace)
inc = (+1)
twice = inc . inc
howManyTimes =
inc (trace "I got eval'd" (1 + 1))
+ twice
(trace "I got eval'd" (1 + 1))
howManyTimes' =
let onePlusOne =
trace "I got eval'd" (1 + 1)
in inc onePlusOne + twice onePlusOne
Prelude> howManyTimes
I got eval'd
I got eval'd
7
Prelude> howMaybeTimes'
I got eval'd
7
خیلی خوب. حالا با توجه به اینها، ببینیم چطور میشه اشتراکگذاری رو ترقیب یا پیشگیری کرد.
چه چیزی اشتراکگذاری رو ترقیب میکنه
مهربونی. اسم هم همینطور. اسم یکی از راههای خیلی خوب برای اینه که GHC یه چیزی رو به اشتراک بذاره. اول یه مثال از چیزی ببینیم که به اشتراک گذاشته نمیشه:
Prelude> import Debug.Trace
Prelude> let x = trace "x" (1 :: Int)
Prelude> let y = trace "y" (1 :: Int)
Prelude> x + y
x
y
2
به نظر معقول میاد، اما چون مقادیرِ داخلِ x
و y
به اسمهای متفاوتی داده شدن، نمیشه به اشتراک گذاشته بشن. پس با اینکه مقادیرِ یکسانی دارن، باید جداگانه حساب بشن.
همونطور که انتظار میره، GHC چیزهایی که هماسم هستن رو برای عملکردِ قابل پیشبینی و بهتر، به اشتراک میذاره. اگه دوتا مقداری که یک اسم دارن رو با هم جمع کنیم، فقط و فقط یک بار حساب میشن:
Prelude> import Debug.Trace
Prelude> let a = trace "a" (1 :: Int)
Prelude> a + a
a
2
Prelude> a + 1
2
دغلبازی هم تأثیری نداره:
Prelude> let x = trace "x" (1 :: Int)
Prelude> (id x) + (id x)
x
2
Prelude> (id x) + (id x)
2
با اینکه دوتا تابعِ همانی با هم جمع شدن، GHC میدونه چه خبره. ببینین چطور x
رو در اجرای دوم اصلاً محاسبه نکرد. در این نقطه، مقدارِ x
در حافظه نگه داشته شده، پس هر موقع برنامه x
رو صدا بزنه، مقدارش معلومه.
بطور کلی، GHC در خصوص اسمها، همونطوری که به نظر طبیعی میاد رفتار میکنه تا عملکرد رو بیشتر قابل پیشبینی کنه. با این حال همیشه همونطور که انتظار دارین عمل نمیکنه. یه لیست شاملِ یک حرف، و یه String
ِ تکحرفی رو در نظر بگیرین. در واقع یک چیزاند، اما نحوهی ساخته شدنشون یکسان نیست. این در اکیدی ِ فرصتطلبانهی GHC تغییر ایجاد میکنه:
Prelude> let a = Just ['a']
Prelude> :sprint a
a = Just "a"
Prelude> let a = Just "a"
Prelude> :sprint a
a = Just _
پس قضیه چیه؟ خوب، بهینهسازیای که اینجا GHC برمبنای اکید بودن پیاده میکنه، فقط محدود به دادهسازهاست، هیچ محاسبهای نمیکنه! اما میپرسین تابع کجاست؟ خوب اگه دوربینهای دید-در-شبمون رو روشن کنیم...
Prelude> let a = Just ['a']
returnIO
(: ((Just (: (C# 'a') ([])))
`cast` ...) ([]))
Prelude> let a = Just "a"
returnIO
(: ((Just (unpackCString# "a"#))
`cast` ...) ([]))
مشکل اینجاست که بینِ Just
و یه لفظ ِ CString
، فراخوان به یه تابعِ ابتدایی در GHC.Base
قرار میگیره. اینکه لفظهای نوشتاری در لحظهی ساخته شدن در واقع لیستِ حروف نیستن، بیشتر به این خاطره که فرصتهایی برای بهینهسازی ارائه بدن، مثل وقتهایی که لفظهای نوشتاری رو به مقادیرِ ByteString
یا Text
تبدیل میکنیم. فصلِ بعد بیشتر میگیم!
چه چیزی اشتراکگذاری رو پیشگیری یا متوقف میکنه
بعضی وقتها اشتراکگذاری نمیخوایم. بعضی وقتها هم میخوایم بدونیم چرا یه چیزی که میخواستیم به اشتراک گذاشته نشد. در نتیجه درکِ اینکه چه چیزی جلوی اشتراکگذاری رو میگیره مهمه.
اگه بیانیهای در همون جایی که قراره مصرف بشه درخط نوشته بشه، جلوی اشتراکگذاریش گرفته میشه، چون این کار یه ثانک ِ مجزا براش درست میکنه که باید مستقلاً محاسبه بشه. در این مثال، بجای اینکه مقدارِ f
رو برابرِ ۱ تعریف کنیم، به عنوانِ یه تابع تعریفش میکنیم:
Prelude> :{
Prelude| let f :: a -> Int
Prelude| f _ = trace "f" 1
Prelude| :}
Prelude> f 'a'
f
1
Prelude> f 'a'
f
1
در مثالِ بعدی میشه مستقیماً تفاوتِ بینِ نامگذاریِ مقدارِ (2 + 2)
، و همونطوری درخط نوشتنش رو مقایسه کرد. وقتی اسم داره، به اشتراک گذاشته میشه و دوباره محاسبه نمیشه:
Prelude> let a :: Int; a = trace "a" 2 + 2
Prelude> let b = (a + a)
Prelude> b
a
8
Prelude> b
8
اینجا همونطور که انتظار داشتیم، فقط یکبار a
رو دیدیم، چون جوابش به اشتراک گذاشته شد.
Prelude> :{
Prelude| let c :: Int;
Prelude| c = (trace "a" 2 + 2)
Prelude| + (trace "a" 2 + 2)
Prelude| :}
Prelude> c
a
a
8
Prelude> c
8
اینجا همون بیانیهای که در مثالِ قبل به a
انقیاد داده بودیم، به اشتراک گذاشته نشد چون هر دوباری که ازش استفاده شده بود هیچ اسمی نداشت. این یه مثالِ پیشوپاافتاده از درخط نوشتن ِه. این مثالها تفاوت محاسبهی یه بیانیه در حالتی که اسم داره و در حالتی که به صورتِ درخط بازنویسی میشه رو نشون میدن.
اگه بیانیهای به صورت یه تابع با آرگومانهای صریح و اسمدار تعریف بشه، اون موقع هم جلوی اشتراکگذاری گرفته میشه. هسکل تماماً تنبل نیست؛ فقط نااکید ِه، پس ملزم نیست جوابِ هر تابعی رو به ازای ورودیهای مشخص به خاطر بسپاره. با توجه به محدودیت در حافظه، چنین کاری اصلاً مطلوب هم نیست. ببینید:
Prelude> :{
Prelude| let f :: a -> Int
Prelude| f = trace "f" const 1
Prelude| :}
Prelude> f 'a'
f
1
Prelude> f 'a'
1
Prelude> f 'b'
1
داشتنِ آرگومانِ صریح و اسمدار خیلی مهمه! سادهسازیِ اِتا (یعنی بینقطه نوشتن، حذفِ آرگومانهای اسمدار) اشتراکگذاری رو در کدِتون تغییر میده. در فصلِ بعدی این رو با جزئیات بیشتری توضیح میدیم.
محدودیتهای تایپکلاسی هم جلوی اشتراکگذاری رو میگیرن. اگه فراموش کنیم تایپِ یکی از مثالهای قبلی رو معین کنیم، a
رو دوبار حساب میکنیم:
Prelude> let blah = Just 1
Prelude> fmap ((+1) :: Int -> Int) blah
Just 2
Prelude> :sprint blah
blah = _
Prelude> :t blah
blah :: Num a => Maybe a
Prelude> let bl = Just 1
Prelude> :t bl
bl :: Num a => Maybe a
Prelude> :sprint bl
bl = _
Prelude> fmap (+1) bl
Just 2
Prelude> let fm = fmap (+1) bl
Prelude> :t fm
fm :: Num b => Maybe b
Prelude> :sprint fm
fm = _
Prelude> fm
Just 2
Prelude> :sprint fm
fm = _
Prelude> :{
Prelude| let bla =
Prelude| Just (trace "eval'd 1" 1)
Prelude|
Prelude| let fm' =
Prelude| fmap ((+1) :: Int -> Int) bla
Prelude| :}
Prelude> fm'
Just eval'd 1
2
Prelude> :sprint fm'
fm' = Just 2
باز هم دلیلش اینه که محدودیتهای تایپکلاسی در Core تابعاند: منتظرِ اعمال به چیزی هستن که اونها رو به تایپهای معین تبدیل کنه. در بخش بعدی این مورد رو کمی بیشتر توضیح میدیم.
پارامترهای ضمنی هم مشابه محدودیتهای تایپکلاسی پیادهسازی شدن و همون تأثیر رو روی اشتراکگذاری میذارن. در حضورِ محدودیتها (چه تایپکلاسی، چه پارامترهای ضمنی) اشتراکگذاری کار نمیکنه، چون وقتی کامپایلر کد رو ساده میکنه، محدودیتهای تایپکلاسی و پارامترهای ضمنی به آرگومانهای تابع "مَحو" میشن:
Prelude> :set -XImplicitParams
Prelude> import Debug.Trace
Prelude> :{
Prelude| let add :: (?x :: Int) => Int
Prelude| add = trace "add" 1 + ?x
Prelude| :}
Prelude> let ?x = 1 in add
add
2
Prelude> let ?x = 1 in add
add
2
به نظر ما استفاده از پارامترهای ضمنی عموماً کار خوبی نیست، به همین خاطر بیشتر از این راجع بهشون صحبت نمیکنیم. اکثر مواقعی که به نظر میاد پارامترهای ضمنی لازماند، به احتمال زیاد Reader
، ReaderT
، یا آرگومانِ معمولی جوابگو اند.
چرا ظاهراً هیچ وقت مقادیرِ پلیمورفیک اجبار نمیشن
همونطور که گفتیم، GHC هر وقت بتونه خیلی امن، و بدون اینکه یه بیانیهی معتبر رو تهی کنه از اکیدی ِ فرصتطلبانه استفاده میکنه. این یکی از عوامل رفتار عجیبِ sprint
در GHCi ِه – اکثراً GHC زمانی فرصتطلبانه اکید میشه که میدونه محتویاتِ یه دادهساز مسلماً نمیتونن تهی باشن، مثل وقتهایی که یه مقدارِ لیترال هستن (م. مثل اعداد یا نوشتهها). وقتی در نظر میگیریم که محدودیتهای تایپکلاسی پشتِ پرده به آرگومانهای اضافه ساده میشن، قضیه پیچیدهتر میشه.
با استفاده از یه مثال مشابه یکی از مثالهای قبلی، اول در عمل میبینیم بعد توضیح میدیم:
Preldue> :{
Prelude| let blah =
Prelude| Just (trace "eval'd 1" 1)
Prelude| :}
Prelude> :sprint blah
blah = _
prelude> :t blah
blah :: Num a => Maybe a
Prelude> fmap (+1) blah
Just eval'd 1
2
Prelude> fmap (+1) blah
Just eval'd 1
2
Prelude> :sprint blah
blah = _
خوب حداقل شواهدی داریم که نشون میدن داریم دوباره محاسبه میکنیم. با معین شدن تغییری میکنه؟
Prelude> :{
Prelude| let blah =
Prelude| Just (trace "eval'd 1"
Prelude| (1 :: Int))
Prelude| :}
Prelude> :sprint blah
blah = Just _
trace
مقدارِ Int
رو تحتالشعاع قرار داده بود و جلوی محاسبهی فرصتطلبانه رو میگرفت. اما با حذفِ Num a => a
و تغییرِش به تایپِ معین، اشتراکگذاری رو احیا کردیم:
Prelude> fmap (+1) blah
Just eval'd 1
2
Prelude> fmap (+1)
Just 2
حالا فقط یکبار trace
ساتع میشه. بطور خلاصه، وقتی محدودیتهای تایپکلاسی به GHC Core ساده میشن، در واقع آرگومانِ تابع هستن.
اگه از یه تابع که تایپِ معین میگیره و اون Num a => a
رو اجبار میکنه استفاده کنین، باز هم تأثیری نداره؛ به خاطرِ محدودیتِ تایپکلاسی، با هربار محاسبه همهی کارها رو دوباره انجام میده:
Prelude> fmap ((+1) :: Int -> Int) blah
Just 2
Prelude> :sprint blah
blah = _
Prelude> :t blah
blah :: Num a => Maybe a
Prelude> let bl = Just 1
Prelude> :t bl
bl :: Num a => Maybe a
Prelude> :sprint bl
bl = _
Prelude> fmap (+1) bl
Just 2
Prelude> let fm = fmap (+1) bl
Prelude> :t fm
fm :: Num b => Maybe b
Prelude> :sprint fm
fm = _
Prelude> fm
Just 2
Prelude> :sprint fm
fm = _
Prelude> :{
Prelude| let fm' =
Prelude| fmap ((+1) :: Int -> Int)
Prelude| blah
Prelude| :}
Prelude> fm'
Just eval'd 1
2
Prelude> :sprint fm'
fm' = Just 2
بالاخره قضیهی محدودیتهای تایپکلاسی چیه؟ مثلِ این میمونه که Num a => a
در واقع Num a -> a
باشه. توی Core واقعاً اینطوریه. تنها راهی که اون آرگومان اعمال بشه اینه که برسه به یه بیانیهای که با تایپِ معین، محدودیت رو ارضا میکنه. تو این مثال تفاوتش رو با مقادیر نشون میدیم:
Prelude> let poly = 1
Prelude> let conc = poly :: Int
Prelude> :sprint poly
poly = _
Prelude> :sprint conc
conc = _
Prelude> poly
1
Prelude> conc
1
Prelude> :sprint poly
poly = _
Prelude> :sprint conc
conc = 1
Num a => a
یه تابعه که منتظرِ آرگومانه، اما Int
اینطور نیست. یه نگاه به Core بندازیم:
module Blah where
a :: Num a => a
a = 1
concrete :: Int
concrete = 1
Prelude> :l code/blah.hs
[1 of 1] Compiling Blah
================ Tidy Core ==============
Result size of Tidy Core =
{terms: 9, types: 9, coercions: 0}
concrete
concrete = I# 1
a
a =
\ @ a1_aRN $dNum_aRP ->
fromInteger $dNum_aRP (__integer 1)
میبینین a
لاندا داره؟ برای اینکه کامپایلر بدونه در هر لحظه از کدوم نمونه ِ تایپکلاس استفاده کنه، تایپ باید معین باشه. همونطور که دیدیم، تایپها هم از طریق اعلامِ تایپ، و هم به واسطهی پیشفرضیسازیِ تایپ تعیین میشن. از هر راهی معین بشه، نتیجه همونه: بعد از معین شدنِ تایپ، تابعِ محدودیتِ تایپکلاسی به نمونه ِ تایپکلاسِ اون تایپ اعمال میشه. اگه تایپ تعیین نشه، به دلیلِ اینکه نمیتونه مطمئن باشه که در طولِ زمان تایپش تغییر نکرده باشه، هر بار باید این تابع رو محاسبه کنه. پس به خاطرِ اینکه تابع میمونه، و توابعِ اعمال نشده رو نمیشه به اشتراک گذاشت، در نتیجه بیانیههای پلیمورفیک هم نمیشه به اشتراک گذاشت.
در خصوص مقادیری که بر مبنای توابعِ دیگه تعریف میشن، عموماً همین رفتارها در اشتراکگذاری حاکم هستن، اما اگه تعیینِ تایپ رو فراموش کنین، همینطور _
میمونه و کلافه و خشمگین میشین. نظاره کنین:
Prelude> :{
Prelude| let blah :: Int -> Int
Prelude| blah x = x + 1
Prelude| :}
Prelude> let woot = blah 1
Prelude> :sprint blah
blah = _
Prelude> :sprint woot
woot = _
Prelude> woot
2
Prelude> :sprint woot
woot = 2
مقادیرِ یه تایپِ ثابت و معین به اشتراک گذاشته میشن، البته بعد از اینکه یه بار محاسبه شده باشن. مقادیرِ پلیمورفیک بعد از محاسبه هم به اشتراک گذاشته نمیشن، چون در پشتپرده هنوز توابعیاند که منتظرِ اعمال شدن هستن.
جلوگیری از اشتراکگذاری به عمد
کِی میخوایم جلوی اشتراکگذاری رو بگیریم؟ وقتی از یه مجموعه داده ِ بزرگ برای پیدا کردن یک جواب خیلی کوچکتر استفاده کردیم و نمیخوایم اون همه داده تو حافظه بمونن. اول یه مثال که اشتراکگذاری رو نشون میده:
Prelude> import Debug.Trace
Prelude> let f x = x + x
Prelude> f (trace "hi" 2)
hi
4
hi فقط یک بار چاپ شد، چون x
یک بار حساب شد. در مثالِ بعدی، x
دوبار حساب میشه:
Prelude> let f x = (x ()) + (x ())
Prelude> f (\_ -> trace "hi" 2)
hi
hi
4
استفاده از ()
به عنوانِ آرگومانِ x
، x
رو به یه تابعِ خیلی پیشوپاافتاده و عجیب تبدیل کرد؛ به همین خاطر دیگه نمیشه مقدارِ x
رو به اشتراک گذاشت. البته اینجا خیلی مهم نیست، چون اون "تابعِ" x
کار زیادی انجام نمیده.
اوکی، عجیب بود؛ شاید اگه آرگومانهای معمولیتری استفاده کنیم بهتر معلوم بشه:
Prelude> let f x = (x 2) + (x 10)
Prelude> f (\x -> trace "hi" (x + 1))
hi
hi
14
استفاده از لاندایی که به نحوی آرگومانش رو ذکر میکنه، اشتراکگذاری رو لغو میکنه:
Prelude> let g = \_ -> trace "hi" 2
Prelude> f g
hi
hi
4
از دلایلی که این مثال هم کار کرد این بود که تابعِ پاس شده به f
، با اینکه آرگومانش با خطتیره نادیده گرفته شده بود، بخشی از تعریفش بود. ببینید وقتی بینقطهش میکنیم چی میشه:
Prelude> let g = const (trace "hi" 2)
Prelude> f g
hi
4
این تمایز رو در فصلِ بعد با جزئیاتِ بیشتری توضیح میدیم، اما خلاصهش این میشه که وقتی توابع آرگومانهای اسمدار دارن به اشتراک گذاشته نمیشن، ولی وقتی آرگومانهاشون حذف میشن (بینقطه) به اشتراک گذاشته میشن. در نتیجه یک راه برای جلوگیری از اشتراکگذاری، اضافه کردنِ آرگومانهای اسمداره.
اجبارکردنِ اشتراکگذاری
با دادن یه اسم به بیانیه، میتونین اشتراکگذاری رو اجبار کنین. رایجترین راهِ این کار استفاده از let
ِه.
-- رو دوبار حساب میکنه 1 + 1
(1 + 1) * (1 + 1)
-- به اشتراک میذاره x رو تحت 1 + 1 نتیجهی
let x = 1 + 1
in x * x
با توجه به این موضوع، اگه نگاهی به تابعِ forever
در Control.Monad
بندازین، شاید متوجهِ یه چیزِ نسبتاً عجیب بشین:
forever :: (Monad m) => m a -> m b
forever a = let a' = a >> a' in a'
فایدهی اون بیانیهی let
چیه؟ خوب اینجا اشتراکگذاری لازم داریم تا وقتی میخوایم یه اجراییهی موندی رو بینهایت بار اجرا کنیم، منجر به نشتِ حافظه نشه. اینجا اشتراکگذاری باعث میشه GHC در اجرای هر مرحله از محاسبه، ثانکی که درست کرده رو رونویسی* کنه. اگه این کار رو نمیکرد، همینطور تا بینهایت ثانک درست میکرد که اصلاً خوب نبود.
م. overwrite کردن به معنیِ نوشتن روی چیزی که قبلاً نوشته شده بوده (و در نتیجه از بین بردنِ چیز قبلی) هست.