Programming – An Introduction to Computer Science with Dieter Schlau

Part 1

It's getting late again, and you're sitting with your prospective past best friend Dieter Schlau in front of the fireplace, browsing through the Programming 1 book. While you ponder the difference between static and dynamic semantics, sleep overcomes you.

You are awakened by a soft buzzing.

When you open your eyes, you see that Dieter Schlau has grabbed your laptop and is experimenting with the interpreter – and of course, he is pushing all the wrong buttons! Horrified, you run to your laptop, but it is too late: All previously declared functions have been deleted (yes, even your beloved functions iter, first, and forall are gone)!

Still half asleep, you can barely type

let rec fortytwo (f : 'a -> ('a * bool)) (s : 'a) = 
    let (n, b) = f s
    in  if b then fortytwo f n
         else n

into your interpreter before Dieter's actions have made the rec keyword permanently unusable.

Shocked, you look at Dieter. But just as you are about to confront him, he quickly mumbles something that roughly resembles “gotta go” and runs for the door. After briefly giving chase, you give up: Dieter has escaped.

Unfortunately, you must now solve the following tasks without rec and any auxiliary function except fortytwo.

1. After you've realized that fortytwo now is your only way to use recursion, take a closer look at this function. What is its type scheme? What does it do? How can it help you write recursive functions?

2. Familiarize yourself with fortytwo: Write a function fac : int -> int such that fac n computes the factorial $n!$ by repeated multiplication. Remember the restrictions given above!

3. Make yourself feel at home in your interpreter again! Declare your favorite functions iter, first, and forall anew.

Part 2

Tired, but somewhat content with your work, you put your Programming 1 book back on the table in front of the fireplace and finally go to bed. As your head sinks into the pillow, sleep overcomes you…

When you wake up again, you hardly recognize your room: it is way too cold, and somehow, the light is flickering…

Dieter seems to be back in your room and is sitting by the fireplace with his back turned to you. You get up and sleepily mutter, “Dieter, why is it so cold? Did you put out the fire?” In lieu of answering, Dieter slowly gets up and turns to face you. The room somehow seems to get colder and colder. “I am not Dieter”, Dieter says, now looking straight into your eyes. And he seems to be right: The figure standing there looks surprisingly like your friend Dieter Schlau, but it is paler, thinner, and for some reason you cannot fathom, looking at him sends shivers down your spine. “I am Dark Dieter. Your dear friend Dieter Schlau is…” and at that moment Dark Dieter's lips curl into a devilish grin, “…lost forever.” You inhale sharply and your knees suddenly soften. “Dieter? Lost?”, you gasp.

“There is only one way to save him. Implement this function before the sun rises again:

If you do not succeed, your friend Dieter will never return. An impossible task, given the mischief your little friend has caused already. He has triggered his own demise.”

With these words, and roaring laughter, Dark Dieter throws your Programming 1 book into the fireplace and disappears from the room. Page by page, any hope of rescue is consumed by the flames.

Since Dark Dieter has left the room, it has become noticeably warmer. Drenched in cold sweat, you sit down by the fireplace again.

It can't be that tricky to implement the function. Or can it?

4. Is Dark Dieter right? Are there any functions that you cannot implement in your interpreter anymore?

   If yes: Specify such a function and explain briefly why it can no longer be implemented.

   If no: Explain briefly why.

   In both cases, only a short, intuitive explanation is required.

5. Now solve the ghost's challenge.

   Under the known constraints, declare a function f : int -> int -> int with the behavior given above. Use only fortytwo and auxiliary functions that you have already declared with fortytwo.

   You might be able to mild-manner the ghost by using only constructs introduced in the first three chapters of the book (in particular by not using lists). Mild-mannered spirits tend to be generous in giving bonus Dieters!

Part 3

With the last of your strength, you type the last closing parenthesis of your implementation into the interpreter, and slowly drift away…

The sun is shining. A loud “Ding Dong!” startles you awake. Was that the doorbell? Still tired, you shuffle to the door, open it – and in front of you stands your friend Dieter, smiling at you. With a happy “I must have broken something yesterday, but we'll fix that!” he hops into your apartment. He does not seem to remember the night's adventures. As you follow Dieter back to the couch, you begin to wonder whether Dark Dieter was just a dream.

The table by the fireplace lies empty.

Formalities

Please submit your OCaml programs in a .ml file so that they are directly executable in an interpreter. In addition, please always provide an explanation of your code. You may choose to write the explanations and answers in a separate .txt or .pdf file. Finally, please submit all files in compressed form as one .zip file. Alternatively, you may submit your explanations in the form of an audio drama, which you include as an .mp3 or .m4a file with the .zip file. Good solutions whose explanations are submitted as an audio drama will be rewarded with bonus Dieters!

Test your solutions before submitting them. Submissions that do not execute may be awarded 0 points.

If you think you have found a particularly nice solution, you can try to explain why your solution is particularly nice for a chance to be awarded bonus Dieters.

Upload your proposed solution to your personal status page no later than 24.11.2022 23:59 at your personal status page. If you have any questions, please contact Dark Dieter in the forum. If you have not formed a kNobel team yet, or wish to make changes to your kNobel team, please contact Iona Kuhn or Tim Bauerschmidt.

Terms and conditions apply. Relatives and employees of Dieter Schlau and Dark Dieter cannot participate. Offer not valid for permanent residents of Schleswig-Holstein.

The task and related advanced topics from different areas of computer science will be discussed in a kNobel tutorial, scheduled for 01.12.2022 12:15.