1 of 58

שפות תכנות

תרגול 1 -

בס"ד

צבי ברגר

OCAML

2 of 58

על הקורס

  • מרצה: ד"ר יוני זוהר
  • מתרגל: צבי ברגר – zvbe10@gmail.com
  • בקורס יהיו 4 תרגילים (הגשה בזוגות) – בתרגילים יהיה חלק תכנותי וחלק תיאורטי.
  • 30% ציון תרגיל, 70% ציון מבחן.
  • אתר הקורס: https://u.cs.biu.ac.il/~zoharyo1/pl-class/index.html

בס"ד

3 of 58

שפות תכנות

  • שפות תכנות מתחלקות ל-2 סוגים:
    • שפות הצהרתיות (declaration language) – המיקוד של השפה הוא במה המחשב צריך לעשות.

השפה עוסקת בהצהרה של אובייקטים (לדוגמא: HTML, CSS, XAMK, SQL)

      • שפות הצהרתיות מתחלקות ל-2 חלקים:
        • Functional – פונקציות קוראות לפונקציות. לדוגמא: Ocaml.
        • logic – חוקים וקשרים לוגיים. לדוגמא: SQL, Prolog.

​

    • שפות מצוות (imperative language) – המיקוד של השפה הוא באיך המחשב צריך לעשות.

השפה עוסקת בפקודות למערכת (לדוגמא: C, Python, Java, C++)

      • שפות מצוות מתחלקות ל-3 חלקים:
        • Von Neuman – המודל החישובי של וון ניומן – מודל חישובי של שינוי משתנים (ערכים). לדוגמא: C, Fortran.
        • Object-oriented – מודל מובנה של חישוב אובייקטים והאינטרקציה ביניהם. לדוגמא: C++, Java.
        • Scripting language – שפות סקריפטים, תיאום בין רכיבים. לדוגמא: Python, Javascript, PHP.

בס"ד

4 of 58

OCAML

  • Ocaml (Objective Caml) היא שפת תכנות כללית מרובת פרדיגמות תכנות שמרחיבה את Caml עם תמיכה בתכנות מונחה עצמים.
  • במקור Caml הוא ראשי תיבות - Categorical Abstract Machine Language.
  • Ocaml נוצרה בשנת 1996 על ידי חביאר לרוי, ג'רום ווליון, דמיאן דוליגז, דילדר רמי, איסקנדר סוארס ואחרים.

בס"ד

5 of 58

OCAML

בס"ד

6 of 58

התקנה

  • פקודות להתקנת סביבת עבודה של (linux) Ocaml:

בס"ד

sudo add-apt-repository ppa:avsm/ppa

sudo apt update

sudo apt install opam

מומלץ:

sudo apt install utop

Real World OCaml, Part 1, Sections 1 -- 6

7 of 58

סביבת עבודה

  • which ocaml
  • whereis ocaml
  • ocaml - open Ocaml enviroment
  • cntl + d – exit Ocaml enviroment

בס"ד

8 of 58

סביבת עבודה

  • which ocaml
  • whereis ocaml
  • utop - open Ocaml environment – recommended
  • cntl + d – exit Ocaml enviroment

בס"ד

9 of 58

קבצי קוד

בס"ד

קבצי נגמרים בסיומת

Ocaml

.ml

10 of 58

HELLO WORLD

בס"ד

פונקציה להדפסת מחרוזות

11 of 58

HELLO WORLD

בס"ד

השם של קובץ ההרצה

פקודת קימפול

שם הקובץ

12 of 58

HELLO WORLD

בס"ד

הרצת קובץ הרצה

13 of 58

ביטויים

בס"ד

שורה נגמרת ב-

;;

המשתנה (כשאין מסומן עם '-')

הטיפוס

הערך

14 of 58

משתנים

בס"ד

המשתנה

הטיפוס

הערך

15 of 58

משתנים

בס"ד

המשתנה

הטיפוס

הערך

16 of 58

FLOAT

בס"ד

https://v2.ocaml.org/api/Float.html

כדאי להסתכל על המודול של float ולראות איזה פונקציות כבר ממומשות:

17 of 58

STRING

  • ב-Ocaml יש טיפוס string.

​

​

​

​

  • כדאי להסתכל על המודול של string ולראות איזה פונקציות כבר ממומשות:

https://v2.ocaml.org/api/String.html

בס"ד

18 of 58

STRINGפונקציות

  • אורך:

​

  • get:

​

​

​

  • שרשור מחרוזות:
  • יש גם set, lowercase, uppercase, capitalize, compare ועוד.

​

​

​

​

​

​

​

​

​

בס"ד

19 of 58

פונקציות

  • ב-Ocaml יש טיפוס מסוג פונקציה

בס"ד

היא פונקציה מטיפוס שמקבלת ומחזירה

Square

int

int

20 of 58

פונקציות

  • ב-Ocaml יש טיפוס מסוג פונקציה

בס"ד

21 of 58

פונקציות

  • למען האמת פונקציה הן lambda expression.

​

​

​

​

  • דרך שראינו ליצירת פונקציה היא קיצור מקובל ליצירת lambda expression.

בס"ד

22 of 58

פונקציות

בס"ד

23 of 58

פונקציות

בס"ד

24 of 58

רקורסיה

בס"ד

צריך להצהיר שהפונקציה היא רקורסיבית

25 of 58

פונקציות גנריות

​

  • 'a is a \emph{type variable}

​

​

​

  • ניתן להגדיר את סוג המשתנים (type inference):

בס"ד

26 of 58

פונקציות גנריות

​

​

​

​

​

​

בס"ד

מה לדעתכם יקרה?

​

מבולבלים?

הקריאה החזירה פונקציה שמקבלת מספר שלם ומחזירה מספר שלם.

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

​

27 of 58

שגיאות ואזהרות

  • Error – שגיאת קומפילציה

​

​

​

​

  • Exception- שגיאת זמן ריצה

בס"ד

28 of 58

OPTIONS

  • דרך יעילה ומעניינת ב-Ocaml לטיפול בשגיאות הנוצרות מקלט לא נכון לפונקציה היא שימוש ב-options.
  • Option הוא טיפוס נתונים שיש בו שתי אפשרויות None או Some.
  • הרעיון הוא שנחזיר ערך אם יש ואם יש שגיאה נחזיר None.

​

​

​

​

בס"ד

29 of 58

TUPLE

בס"ד

30 of 58

רשימות

​

​

​

​

בס"ד

  • יצירת רשימה:

​

​

  • ב-Ocaml רשימות הן immutable .
  • בניגוד ל-tuple לא ניתן ליצור רשימה עם טיפוסים שונים של איברים:

31 of 58

רשימות

  • יצירת רשימה:

​

​

​

​

  • מה ההבדל בין , לבין ; בין כל איבר ברשימה?

בס"ד

32 of 58

רשימות

  • יצירת רשימה:

​

​

​

​

  • מה ההבדל בין , לבין ; בין כל איבר ברשימה?
    • השימוש בפסיק אומר שזה tuple כלומר ברשימה השנייה יש לנו איבר אחד שהוא tuple עם שלושה איברים.

בס"ד

33 of 58

פעולות על רשימות

​

​

​

​

בס"ד

  • אורך רשימה:

​

  • איבר ברשימה לפי אינדקס:
  • Reverse:

​

  • Find:

​

  • לעוד אופרטורים: https://v2.ocaml.org/api/List.html

מחזיר את האיבר הראשון שמקיים את התנאי אם רוצים את כל האיברים שמקיימים תנאי משתמשים בפונקציה filter

34 of 58

פעולות על רשימות

  • חיבור רשימות:

​

​

​

  • פונקציית מפה:

​

​

​

​

בס"ד

List.map takes two arguments: a list and a function for transforming the elements of that list. It returns a new list with the transformed elements and does not modify the original list.

35 of 58

PATTERN MATCHING

​

​

​

​

בס"ד

36 of 58

RECORD TYPE

  • ניתן להגדיר type חדש ב-Ocaml המכיל מספר שדות מטיפוסים שונים, טיפוס כזה נקרא record.

​

​

​

​

בס"ד

37 of 58

RECORD TYPE - EXAMPLE

​

​

​

​

​

בס"ד

38 of 58

RECORD TYPE - EXAMPLE

​

​

​

​

בס"ד

39 of 58

VARIANT TYPE

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

​

​

​

​

בס"ד

40 of 58

VARIANT TYPE

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

​

​

​

​

בס"ד

41 of 58

VARIANT TYPE

​

​

​

​

בס"ד

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

​

​

​

​

42 of 58

VARIANT TYPE

​

​

​

​

בס"ד

  • למעשה רשימות ו-option הם variants מאוד חשובים ולכן הם ממומשים כבר בשפה.

​

​

​

​

43 of 58

מחיקת ערכים כפולים ברשימה

  • כתוב פונקציה שתקבל רשימה ותמחק את כל האיברים הכפולים שנמצאים אחד אחרי השני.

דוגמא להרצה:

​

​

​

​

בס"ד

44 of 58

מחיקת ערכים כפולים ברשימה

  • כתוב פונקציה שתקבל רשימה ותמחק את כל האיברים הכפולים שנמצאים אחד אחרי השני.

דוגמא להרצה:

​

​

​

​

בס"ד

45 of 58

מחיקת איברים ברשימה

  • כתוב פונקציה שתקבל רשימה ומספר טבעי ותמחק את כל איבר n’th ברשימה.

דוגמא להרצה:

​

​

​

​

בס"ד

46 of 58

מחיקת איברים ברשימה

  • כתוב פונקציה שתקבל רשימה ומספר טבעי ותמחק את כל איבר n’th ברשימה.

דוגמא להרצה:

​

​

​

​

בס"ד

47 of 58

פיבונאצ'י

  • כתוב פונקציה שתקבל מספר n ותחשב את המספר ה-n בסדרת פיבונאצ'י.

דוגמא להרצה:

​

​

​

​

בס"ד

48 of 58

פיבונאצ'י

  • כתוב פונקציה שתקבל מספר n ותחשב את המספר ה-n בסדרת פיבונאצ'י.

דוגמא להרצה:

​

​

​

​

בס"ד

49 of 58

השערת גולדבך

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

​

  • כתוב פונקציה שמקבלת מספר גדול מ-2 ומחזירה את שני המספרים הראשוניים שהוא סכומם.
    • הרצה לדוגמא:

​

​

בס"ד

50 of 58

השערת גולדבך

בס"ד

51 of 58

עץ בינארי

​

​

​

​

בס"ד

52 of 58

עץ בינארי

​

​

​

​

בס"ד

53 of 58

עץ בינארי

​

​

​

​

בס"ד

1

2

6

4

5

3

7

54 of 58

עץ בינארי סימטרי

  • כתוב תוכנית שמקבלת שורש של עץ בינארי ומחזירה האם הוא סימטרי.
  • עץ בינארי סימטרי הוא עץ שהוא תמונת מראה של עצמו – כלומר אם מעבירים קו דרך ישר דרך השורש מקבלים תמונה מראה של מבנה העץ מהצד הימני והשמאלי של הקו (שימו לב שמתייחסים רק למבנה של העץ ולא לערכים שלו).

​

​

​

​

  • https://leetcode.com/problems/symmetric-tree/

בס"ד

עץ סימטרי

עץ לא סימטרי

55 of 58

עץ בינארי סימטרי

בס"ד

56 of 58

גזור ושמור

בס"ד

57 of 58

בשבילנו...

בס"ד

58 of 58

LET QUESTION = � | NONE