טיפוס נתונים

טיפוס נתונים (באנגלית: data type) הוא מושג בשפות תכנות המתאר את סוגו של משתנה השייך לו, כלומר מגדיר אלו ערכים הוא עשוי לקבל, ובאלו דרכים. היעזרות בטיפוסי נתונים מסייעת להפשטה של מבני נתונים ואלגוריתמים במדעי המחשב.

ישנן שתי דרכים להגדיר טיפוסי נתונים ולהבחין ביניהם. הראשונה, והפשוטה יותר, היא להגדיר טיפוס כקבוצת הערכים אליה שייך כל משתנה מהטיפוס הזה. משתנה מטיפוס זה מייצג איבר מהקבוצה, כלומר מקבל אחד מהערכים השייכים לקבוצה. דרך זו מתאימה בעיקר לטיפוסים פשוטים, המתאימים לקבוצות מתמטיות מוכרות, כגון מספרים שלמים, מחרוזת וכדומה, ובאופן כללי לטיפוסים בהם יש התאמה חד-חד ערכית בין ערך של משתנה לייצוג של המשתנה ברמה נמוכה יותר, כגון שפת מכונה. הגדרה זו מתאימה פחות לטיפוסים מורכבים יותר, כגון שבר, בהם ניתן לייצג את אותו ערך בדרכים רבות. במקרה כזה אפילו פעולות פשוטות כגון השוואה או השמה, למשל, אינן טריוויאליות, ויש להגדיר אותן במפורש.

דרך שנייה היא להגדיר טיפוס כמימוש של מבנה נתונים מופשט, על ידי הפעולות המוגדרות עליו והסמנטיקה של פעולות אלו. דרך זו מתאימה במיוחד, אך לא באופן בלעדי, למחלקות בשפות תכנות מונחות-עצמים. דוגמה לטיפוס כזה היא מימוש של מחסנית.

מערכת הטיפוסים של שפת תכנות מאפשרת לאכוף ברמה זו או אחרת של נוקשות את הנכונות, העקביות והשלמות של השימוש בטיפוסי נתונים בשפה - למשל, כיצד משלבים משתנים בביטויים מורכבים - וכך להזהיר ולמנוע טעויות תכנות, להקל על קריאות התוכנית, להוכיח נכונות, ולהקל על המהדר לבצע אופטימיזציות.

טיפוסי מכונה

• סיבית היא יחידת המידע הבסיסית ביותר. סיבית נמצאת תמיד באחד משני מצבים המסומנים ב-0 וב-1.
• בית היא קבוצה של שמונה סיביות.
• מילה היא היחידה המעובדת על ידי הוראה בשפת מכונה. במחשבים הנפוצים כיום, מילה היא בת 4 בתים (32 סיביות) או 8 בתים (64 סיביות).

ברמת שפת מכונה, אין "משמעות" לטיפוסי הנתונים, אלא רק ייצוג שלהם.

טיפוסים פרימיטיביים

טיפוס נתונים פרימיטיבי הוא כינוי לטיפוס בסיסי הנתמך בשפה, להבדיל מטיפוס מורכב אותו השפה מאפשרת ליצור על ידי הרכבה של טיפוסים בסיסיים.

לכל שפת תכנות אוסף שונה של טיפוסים פרימיטיביים, המתאים לייעוד לשמו תוכננה השפה. ישנם טיפוסים הנתמכים בכל השפות או במרביתן, כגון מספר שלם (לעיתים ישנם מספר טיפוסים עבור מספר שלם במספר טווחי ערכים שונים, משיקולי יעילות), נקודה צפה המייצג בקירוב מספרים ממשיים, תו (ו\או מחרוזת), וטיפוס בוליאני המכיל שני ערכים - אמת ושקר.

טיפוסים פרימיטיביים נפוצים נוספים הם מצביע המאפשר לאחסן כתובת של משתנים, מספר מרוכב המסייע בביצוע חישובים פיזיקליים. בשפות תכנות המאפשרות תכנות פונקציונלי יש גם טיפוסים פרימיטיביים עבור פונקציה, ורשימה.

פרולוג היא חריגה בקרב שפות התכנות העיליות בכך שאין לה מערכת טיפוסים - כל הביטויים בשפה הם מאותו טיפוס פרימיטיבי, מושג (term).

שלמים

טיפוס הנתונים הנפוץ הבסיסי ביותר לביצוע פעולות אריתמטיות הוא המספר השלם. טיפוס זה נתמך מבחינות רבות ישירות על ידי המעבד, על ידי פעולות חיבור, קידום באחד, הכפלה ב-2 או חלוקה ב-2 (על די פעולת "הזזה", shift) ועל פי רוב גם כפל וחילוק של שני מספרים כלשהם. בשל כך הפעולות על משתנים מטיפוס זה הן יעילות ביותר.

אף ייצוג במכונה לא יכול לאפשר אינסוף ערכים, כמו במספרים שלמים מתמטיים טהורים, ועל כן בזמן תכנון השפה או כתיבת מימוש לשפה (מהדר או מפרש) יש להחליט מהו טווח הערכים הרצוי. הבחירה הטבעית ביותר היא להשתמש בטווח המקסימלי הניתן לייצוג על ידי מילה במעבד הספציפי שבו מורצת התוכנית. בחירה כזאת משלבת תחום מספרים נרחב למדי יחד עם יעילות חישוב מקסימלית. עם זאת, הטווח עדיין מוגבל, והוא נעשה תלוי-מכונה - כלומר, תוכניות עלולות להתנהג שונה בהרצה על מחשבים שונים. אפשרות אחרת היא להגדיר מספר טיפוסים עבור מספר תחומים שונים, ולהשתמש בהם בהתאם לצורך. זה עשוי לבוא יחד עם התאמה למכונה (כמו בשפות C או ++C) או על ידי הגדרה חד משמעית של הטווח עבור כל טיפוס (כמו בשפת ג'אווה). אפשרות שלישית היא להגדיר טיפוס יחיד בעל טווח לא חסום, ולייצג אותו בצורה האופטימלית ביותר על פי הערך הנוכחי שלו (כמו בשפת פייתון החל מגרסה 3.0).

בנוסף לטווח הערכים, יש להחליט האם לייצג גם מספרים שליליים, או לייצג אך ורק מספרים טבעיים, ובכך להגדיל את הטווח פי 2 בקירוב). מספרים מטיפוס המאפשר מספרים טבעיים בלבד מיוצגים בזיכרון המחשב בייצוג בינארי פשוט. מספרים שליליים, לעומת זאת, מיוצגים באחת משתי השיטות משלים ל-2 או משלים ל-1.

זיכרון	טווח ערכים לשלם	טווח ערכים לשלם אי-שלילי
1 בתים (8 סיביות)	127- עד 128	0 עד 255
2 בתים (16 סיביות)	32,768- עד 32,767	0 עד 65,535
4 בתים (32 סיביות)	2,147,483,648- עד 2,147,483,647	0 עד 4,294,967,295

נקודה צפה

ערך מורחב – נקודה צפה

לצורך ייצוג של מספרים ממשיים משתמשים על פי רוב בייצוג של נקודה צפה. גם כאן יש חשיבות למספר הבתים בייצוג, כאשר השיקולים דומים לאלה שבמספרים ממשיים:

זיכרון	טווח ערכים	שמות בשפות תכנות שונות
4 בתים (32 סיביות)	-3.4*1038 עד 3.4*1038	float, Real, Single
8 בתים (64 סיביות)	-1.7*10308 עד -1.7*10308	double

טיפוסי נתונים שאינם מספריים מיוצגים על ידי התאמת כל ערך למספר.

ערכי אמת

ישנם שני ערכי אמת: "אמת" ו-"שקר". כדי לייצג ערך אמת מספיקה סיבית אחת, אך כיוון שלסיבית בודדת אין כתובת, לעיתים ערך אמת נשמר בבית או במילה. בשפות C ו ++C, הערך "שקר" מותאם לערך השלם 0, והערך "אמת" מותאם לשאר הערכים השלמים, אך לרוב מיוצג על ידי 1. בשפות מעטפת בלינוקס, כגון C Shell, המוסכמה היא הפוכה, בשל העבודה הצמודה עם תוכניות בלינוקס - שם מקובל שהערך 0 מייצג הצלחה, לעומת ערכים אי-שליליים המייצגים מספר שגיאה. בשפות אחרות, למשל Java, לא ניתן להחליף בין ערכים מספריים לערכי אמת, ואלו טיפוסים נפרדים לחלוטין. מכיוון שפעמים רבות מסתפקים רק בשימוש בערכים 0 או 1, ערכי אמת יכולים להיות מוגדרים ומיוצגים כמשתנים בוליאנים, ומכונים גם "דגל".

תווים

ערך מורחב – תו

תו (Character) הוא סימן גרפי כמו אות, ספרה, סימן פיסוק וכדומה. במרבית שפות התכנות קיים טיפוס תו, וממנו ניתן ליצור מילה (כמערך או רשימה של תווים).

בעבר תו נשמר בבית בודד (7 סיביות ומאוחר יותר 8 סיביות), בהתאמה לתקן Ascii. כיום רוב שפות התכנות שומרות תו בשני בתים בשיטת UTF-16.

בשפות ++C/C משתמשים בטיפוס char גם לצורך ייצוג של מספרים קטנים או כיחידה בסיסית המייצגת בית בודד, בשל העובדה שזהו הטיפוס הקטן ביותר בשפה, וכי מוגדר שגודלו הוא תמיד בית יחיד (בניגוד לטיפוסים אחרים שגודלם לא מוגדר באופן יחיד בתקן של השפה, והוא תלוי-מכונה ותלוי-מימוש).

יחידה

טיפוס היחידה (unit) הוא טיפוס המכיל ערך אחד בלבד. אין צורך להבדיל בין סימון הערך לסימון הטיפוס כי ישנה התאמה חד-חד ערכית ביניהם. לביטוי שערכו הוא מטיפוס יחידה אין שימוש כחלק מביטוי אחר, ולכן הוא משמש רק לצורך השגת תוצאת הלוואי של הפעולה. טיפוס זה משמש על פי רוב בקריאה לפונקציה שכוללת תוצאת לוואי כגון פעולת פלט. פונקציה שמחזירה טיפוס כזה היא למעשה פרוצדורה.

בשפת ML הטיפוס נקרא unit ומסומן "()". בשפות ממשפחת ה-C הטיפוס נקרא void; בשפת פייתון הטיפוס נקרא NoneType וערכו נקרא None.

יש להבחין בין טיפוס שמכיל רק איבר בודד כערך לבין טיפוס השקול לקבוצה הריקה. טיפוס שהוא קבוצה ריקה פירושו שאין לו כל ערך קריאה לפונקציה ה"מחזירה" טיפוס כזה היא למעשה קריאה לפונקציה שאיננה חוזרת כלל (לדוגמה, פונקציית terminate המסיימת את פעולת התוכנית).

טיפוסי נתונים מורכבים

רוב השפות המודרניות מאפשרות ליצור טיפוסי נתונים חדשים על ידי הרכבה של טיפוסים קיימים. הדרך הפשוטה ביותר היא פשוט לתת שם חדש לטיפוס קיים (בשפת C, למשל, הפעולה הזאת מתבצעת על ידי ההצהרה typedef). פעולה כזאת תאפשר לשפר את קריאות התוכנית. לדוגמה, בשפת C (בתקן הראשון) אין טיפוס נתונים נפרד עבור ערכי אמת\שקר - מקביל לטיפוס Boolean בשפת פסקל. אם רוצים לדמות טיפוס כזה, אחת הדרכים היא להוסיף את ההצהרה

typedef int bool;

בהמשך התוכנית ניתן להציב ערכי אמת ושקר אל משתנים מטיפוס bool, וכך המטרה של משתנים אלה נעשית ברורה יותר למי שקורא את הקוד. ישנן שפות בהן הצהרה כזו היא פשוט הענקת שם חדש לטיפוס הקודם. בשפות אחרות הטיפוס החדש הוא טיפוס נפרד ולא ניתן להחליף בקלות פעולות על הטיפוס הישן עם פעולות על הטיפוס החדש.

רשימה

ערך מורחב – רשימה מקושרת

בשפות תכנות המעודדות תכנות פונקציונלי, אחד הטיפוסים הפרימיטיביים הוא רשימה, שהיא למעשה רשימה מקושרת. משתנה מטיפוס "רשימה של תווים", למשל, עשוי להיות "רשימה ריקה" (מסומנת לרוב [] ומשותפת לכל סוגי הרשימות. מקבילה בערך לקבוצה ריקה במתמטיקה), או להכיל שני חלקים: ראש וזנב. כאשר הראש הוא האיבר הראשון ברשימה - למשל התו 'A' - והזנב הוא כל שאר הרשימה.

רשימה מקושרת כזאת נוחה מאוד לשימוש באלגוריתמים רקורסיביים, ובמקרים בהם מספר האיברים הסופי איננו ידוע מראש או משתנה. מימוש של רשימה כזאת איננו דורש מקום רצוף בזיכרון, איננו דורש הקצאה של זיכרון מראש, ומקל על איסוף זבל.

לעומת זאת, ישנם מקרים שבהם רשימה איננה מספיק טובה משיקולי סיבוכיות זמן ריצה. גישה לאיבר שרירותי באמצע רשימה (להבדיל ממעבר סדרתי מההתחלה לסוף או מהסוף להתחלה) גורר מעבר על כל אחד מאיברי הרשימה מההתחלה ועד אליו, בעוד שבמערך פעולה כזאת עשויה להתבצע בפעולת מעבד יחידה. עם זאת, שפות פונקציונליות מתקשות לספק תמיכה במערכים בשל שיקולים של הקצאת זיכרון ואיסוף זבל.

מערך

ערך מורחב – מערך

במרבית שפות התכנות, מערך הוא רצף של משתנים מאותו טיפוס, בגודל מסוים. גישה למשתנה ספציפי במערך מתבצעת באמצעות אינדקס - על פי רוב מספר, או משתנה דיסקרטי אחר (תו, Enum וכדומה). על פי רוב גודל המערך הוא קבוע, בשל היעילות הנגזרת מכך: במערך שמאוחסן בזיכרון המחשב באופן רציף (וזה המימוש הנפוץ), גישה למשתנה ספציפי - למשל אל האיבר השלישי - מתבצעת תמיד תוך מספר פעולות חסום, ולעיתים בפקודת מכונה בודדת. על מנת לאפשר הגדלה של מערך תוך שמירה על תכונה זו יש צורך למצוא ולהקצות זיכרון רצוף בגודל החדש, ולהעתיק את כל האיברים הקיימים במערך - פעולות שעשויות להיות יקרות למדי. עם זאת, בשפות תכנות מודרניות ישנם מערכים המאפשרים ביצוע פעולות כאלה, כשלרוב הסיבוכיות בפועל (בניגוד לסיבוכיות התאורטית) זניחה.

Tuple

דרך אחת ליצור טיפוסי נתונים חדשים לחלוטין היא באמצעות מכפלה קרטזית בין טיפוסים, המגדירה טיפוס חדש באופן דומה להגדרת קבוצה חדשה באמצעות מכפלה קרטזית. טיפוס שנוצר באמצעות מכפלה כזאת נקרא Tuple ‏(n-יה סדורה). הסימון המקובל לפעולה הזאת על טיפוסים הוא כפל, בדרך כלל * או $\times$, בדומה לסימון המתמטי המקביל.

שפות המאפשרות יצירה של טיפוסים באמצעות מכפלה קרטזית, כגון ML ופייתון, מקלות בכך על

• ייצוג של וקטורים, שהם פשוט n-יה סדורה של מספרים
• החזרת ערכים מרובים מפונקציה. אם אנחנו מעוניינים להחזיר מפונקציה ערכים מהטיפוסים A ו B, אפשר להגדיר את הפונקציה כך שטיפוס ההחזרה שלה יהיה A*B.
• כתיב מקוצר לפעולות השמה מורכבות. למשל, החלפה בין ערכי משתנים a ו b, מתבצעת על פי רוב תוך שימוש במשתנה עזר (כאן =: היא פעולת ההשמה):

temp := b
b := a
a := temp

לעומת זאת, בעזרת שימוש בזוג סדור ניתן לכתוב פשוט

(a, b) := (b, a)

ובשפות רבות ניתן לוותר על הסוגריים. המחשב עדיין עשוי להשתמש במשתנה עזר, אך למתכנת אין צורך להתעסק בו.

• אם לא קיים בשפה טיפוס עבור מספרים מרוכבים (אך קיים בה טיפוס ממשי Real), ניתן להגדיר אותו בתור טיפוס מהסוג Real*Real, בדומה להגדרה של מספרים מרוכבים במתמטיקה.

גישה למשתנה ספציפי במכפלה קרטזית עשויה להיות בצורה דומה לגישה אל מערך, למשל באמצעות אופרטור "[ ]"; למשל הגישה אל המשתנה הראשון במשתנה c עשויה להיכתב [c[1.‏

המחיר של אפשור טיפוסים כאלה הוא בעיקר תשלום קטן בזמן ריצה והפיכת הגדרת השפה למעט מורכבת יותר.

רשומה

רשומה (record) או מבנה (struct) זהו טיפוס מורכב בדומה למכפלה קרטזית, בהבדל אחד: לכל איבר בו ניתן שם. דוגמה למבנה בשפת C שמתאר זמן:

struct Time{
int seconds;
int minutes;
int hours;
}

בניה כזאת מאפשרת להתעסק במרוכז עם משתנים בעלי קשר הדדי ביניהם, להעביר אותם יחד לפונקציה, לאתחל אותם ביחד וכדומה. מבחינה מתמטית אין הבדל בין רשומה לTuple, אך מבחינת התחביר יש הבדל: ברשומה קל יותר להבין מה המשמעות של כל איבר, ואילו התחביר של מכפלה קרטזית קומפקטי וחסכוני יותר. גישה לאיברים במערך נעשית תוך שימוש באופרטור מתאים. לדוגמה, בשפות ++C/C, עבור משתנה t מטיפוס Time, גישה לשניות בו תתבצע בצורה t.seconds או (אם מדובר במצביע) t->seconds. בשפות אחרות ישנם אופרטורים אחרים המשמשים לאותה מטרה.

חשוב לשים לב שרשומה עלולה להחזיק אוסף ערכים שאין לו משמעות לוגית בתוכנית. האחריות להימנעות מכך היא על המתכנת, דרך הפעולות המתבצעות על משתנים מטיפוס זה. הרחבה של רשומה כך שגם פעולות על המשתנים השייכים אליה יתבצעו רק דרך פרוצדורות שמוגדרות ברשומה עצמה יוצרת למעשה מבנה נתונים מופשט, וקשורה לרעיונות הנכללים בתכנות מונחה עצמים.

טיפוס מאוחד (Union)

אם נתייחס לכל טיפוס כאל קבוצת הערכים הכלולים בו, עולה באופן טבעי האפשרות להגדיר איחוד של טיפוסים, בדומה לאיחוד קבוצות במתמטיקה^{[דרושה הבהרה]}. באופן זה, ניתן יהיה, למשל, להגדיר טיפוס שיכלול ביטויים מסוג מספר שלם וביטויים מסוג תו. הגדרה של טיפוס כזה בשפת C תהיה דומה להצהרה על מבנה, למעט המילה השמורה struct שתוחלף ב-union:

union {
 int integer;
 char character;
}

בכל נקודת זמן רק אחד מהשדות integer או character מחזיק מידע בעל משמעות. הדמיון בין התחביר של איחוד לשל רשומה נובע מכך שכל ההבדל הוא סוג הפעולה המתבצעת בין קבוצות - איחוד לעומת מכפלה קרטזית^{[דרושה הבהרה]}.

איחודים משמשים בעיקר למטרת חיסכון במקום - עבור כל משתנה יש צורך להקצות רק מקום עבור הטיפוס הגדול יותר^{[דרושה הבהרה]}. שימוש אחר של טיפוסים כאלה הוא למקרים בהם רוצים להתייחס לאותו רצף של סיביות, פעם אחת בתור משתנה מסוג א' ופעם שנייה בתור משתנה מסוג ב'. תכנות כזה הוא תכנות ברמה נמוכה, ומשמש כיום כמעט אך ורק במערכות זמן-אמת או מערכות משובצות מחשב. בשפות תכנות עיליות רבות^{[דרושה הבהרה]} טיפוסי נתונים מהסוג הזה אינם קיימים. אחת הבעיות היא שבמקרה של ניסיון לחסוך במקום, לא מצורף לטיפוס מידע על איזה מהשדות שלו בשימוש בכל רגע נתון. עובדה זו מקלה על הכנסת שגיאות לתוכנית.

טיפוסי נתונים רקורסיביים

ישנן שפות המאפשרות להגדיר טיפוסים חדשים תוך שימוש ברקורסיה.

לדוגמה, ניתן להגדיר רשימה מקושרת כTuple, מהצורה הבאה (הסינטקס הוא של שפת ML, ואין צורך להבין אותו במלואו):

datatype intlist = nil
| cons of int * intlist;

כאן הגדרנו רשימה intlist בתור טיפוס שכל ערך בו הוא איבר ריק (nil) או Tuple מהצורה (int, intlist). הגדרה זו מתייחסת לעצמה, ולכן נקראת רקורסיבית. מבנה נתונים רקורסיבי כזה הוא בפוטנציאל אינסופי, ולכן לא ניתן לבניה מלאה; היצירה שלו מתבצעת כחישוב עצל (Lazy), ורק החלקים שהתוכנית מנסה לגשת אליהם בפועל בכל משתנה אכן מוגדרים.

באופן דומה, ניתן להגדיר בשפות המאפשרות הגדרה רקורסיבית גם עץ באותה שיטה:

datatype inttree = int
| cons of inttree * inttree;

בשפות אימפרטיביות, כדוגמת C ודומותיה, על פי רוב לא קיימים טיפוסים רקורסיביים. עם זאת, ניתן לדמות אותם בעזרת מצביע: במקום להצהיר על טיפוס שמכיל את עצמו, ניתן להצהיר על טיפוס שמכיל מצביע למשתנה מאותו טיפוס. הגדרה כזאת איננה רקורסיבית, אך בפועל נותנת את אותה גמישות בדיוק, במחיר של תחביר שעשוי להיות פחות מובן.

ראו גם

• מערכת טיפוסים

קישורים חיצוניים

מדיה וקבצים בנושא טיפוס נתונים בוויקישיתוף