Survey of Programming Language Concepts, cosc-3308 Lab/Assignment 4 Exercise 1. (Efficient Recurrence Relations Calculation) At slide 54 of Lecture 10, we have seen a concurrent implementation of classical Fibonacci recurrence. This is: fun (Fib X} if X==0 then 0 elseif X==1 then 1 else end end thread (Fib X-1} end + {Fib X-2} By calling Fib for actual parameter value 6, we get the following execution containing several calls of the same actual parameters. Execution of {Fib 6} F5 F4 10/27/2006 F4 F3 F2 F3: F2 F2 F1 F2 F1 F2 F1 CS2104, Lecture 7 (Fib 6) is denoted as F6,... Fork a thread Synchronize on result Running thread 56 For example, F3, that stands for {Fib 3}, is calculated independently three times (although it provides the same value every time). Write an efficient Oz implementation that is doing a function call for a given actual parameter only once. Consider a more general recurrence relation, e.g.: Fo, F1, ..., Fm-1 are known as initial values. Fn = g(Fn-1, ..., Fn-m), for any n ≥ m. For example, Fibonacci recurrence has m=2, g(x, y) = x+y, Fo=F₁=1.
Survey of Programming Language Concepts, cosc-3308 Lab/Assignment 4 Exercise 1. (Efficient Recurrence Relations Calculation) At slide 54 of Lecture 10, we have seen a concurrent implementation of classical Fibonacci recurrence. This is: fun (Fib X} if X==0 then 0 elseif X==1 then 1 else end end thread (Fib X-1} end + {Fib X-2} By calling Fib for actual parameter value 6, we get the following execution containing several calls of the same actual parameters. Execution of {Fib 6} F5 F4 10/27/2006 F4 F3 F2 F3: F2 F2 F1 F2 F1 F2 F1 CS2104, Lecture 7 (Fib 6) is denoted as F6,... Fork a thread Synchronize on result Running thread 56 For example, F3, that stands for {Fib 3}, is calculated independently three times (although it provides the same value every time). Write an efficient Oz implementation that is doing a function call for a given actual parameter only once. Consider a more general recurrence relation, e.g.: Fo, F1, ..., Fm-1 are known as initial values. Fn = g(Fn-1, ..., Fn-m), for any n ≥ m. For example, Fibonacci recurrence has m=2, g(x, y) = x+y, Fo=F₁=1.
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
OZ
Transcribed Image Text:**Survey of Programming Language Concepts, cosc-3308**
**Lab/Assignment 4**
**Exercise 1. (Efficient Recurrence Relations Calculation)**
We have seen a concurrent implementation of classical Fibonacci recurrence at slide 54 of Lecture 10. This is implemented as follows:
```
fun {Fib X}
if X==0 then 0
elseif X==1 then 1
else
thread {Fib X-1} end + {Fib X-2}
end
end
```
By executing `Fib` with an actual parameter value of 6, we obtain the following process, which includes multiple calls with the same parameters:
---
**Execution of {Fib 6}**
- `{Fib 6}` is denoted as F6, and the process involves:
- **Fork a thread**: Splits the execution to handle subproblems concurrently.
- **Running thread**: Handles tasks as part of the computation.
- **Synchronize on result**: Ensures results are combined correctly upon completion.
The diagram illustrates how Fibonacci calculations fork and synchronize threads. Several Fibonacci calls, such as {Fib 3} (denoted F3), are executed independently multiple times (thrice for F3 in this case), though they produce the same result.
---
Consider a more general recurrence relation:
- Initial values: F0, F1, ..., Fm-1.
- For n ≥ m, Fn = G(Fn-1, ..., Fn-m).
Example: The Fibonacci sequence, with m = 2, g(x, y) = x + y, and F0 = F1 = 1.
Write an efficient Oz implementation for a function call that computes a given parameter value only once.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education