Can this really be done in Scheme?

Introduction
In an emergency room, arriving patients are first seen by a doctor, called the triage officer, whose responsibility it is to assess the degree of urgency for medical attention. The assessment of the triage officer determines when the patient will be seen by a medical team within the emergency room. Patients with the highest urgency are given the highest priority and therefore get into the emergency room the soonest. The triage officer must also make judgements on the likelihood of treatment being successful. In some cases, a triage officer may decide that it would be futile to treat a patient, in which case that patient never sees the inside of the emergency room at all. These decisions, though diffcult to make, are important to ensuring effective dispensation of medical resources and are usually made only when other lives can be saved instead of the one to be ignored. This approach to medical care is used not only in hospital emergency rooms, but also in treating victims of war on or near the battlefield.
This challenge explores a model of the system in an emergency room, with a primary focus on the triage officer and his/her role of prioritising patients according to their need. In this system, we differentiate between an arriving case and a patient. An arriving case represents what is presented to the triage officer. His assessment determines whether or not that case becomes a patient for the emergency room, and if so, with what priority.
A number of data structures are used to implement the system. Executing certain operations on these data structures cause the model to count of time on a simulated clock. Patients who are not seen by the emergency room doctor in time will perish, so it is important to use efficient implementations of these data structures.
The primary objective of this challenge is to explore the tradeoffs of three different implementations of a priority queue: one using a linked list, one using a binary heap implemented as a binary tree, and the third using a binary heap implemented in an array.

Implementation Overview
The system models three parallel activities: the generation of cases (to become patients), their handling by the triage officer, and the treatment of patients by the emergency room doctors (in our model, there is only one). Two queueing structures provide central support to these two activities. The schedule of arriving patients is maintained as a FIFO queue. On the other hand the queue of patients waiting to be treated in the emergency room is maintained as a priority queue; by default, patients who are dying fastest are given highest priority in the queue.
Simulating Parallelism
In order to simulate the three simultaneous activities, we step each one in round-robin fashion. The patient generator creates patient-cases according to a Bernoulli process (i.e. imagine a flip of a coin, say heads implies a new patient arrives, but tails means none, and the coin is not fair). Each new arriving patient is placed on the FIFO queue. The triage routine examines the FIFO queue, removes the first patient from it, adjusts the patient’s life force to account for the time between when the patient first arrived and the current time, and places it onto a priority queue. Patients are removed from the priority queue by the doctor routine. Each time a patient is removed from the priority queue, treatment is administered. If the patient survives the treatment, but is still not fully recovered, then the doctor routine places the patient back into the priority queue. On the other hand, if the patient is fully recovered, then it is removed from the system completely, and a statistic maintaining the number of survivors is updated. Whenever a patient’s life force dips to zero or lower, that patient dies and is completely removed from the system.
The scheduler steps each process up to the local time of the process that is farthest ahead. Since executing basic operations causes the clock to tick, then most ADT operations actually use up multiple ticks. The scheduler does not interrupt these operations, so at the end of each round, there may be small discrepancies in the local clocks on each process.
When the simulation runs, it prints a list indicating, up to that point, the number of survivors, the total number of patients, the maximum size of the FIFO queue so far, the current size of the priority queue, as well as the time stamps of all the clocks. In the end, the result returned from the simulation run is the number of surviving patients, the total number of patients and the maximum length of the FIFO queue during the simulation.
Life Loss and Treatment Computations
The patient generator generates a random case by selecting a condition (randomly) from the conditions knowledge base, and associating with it two randomly selected numbers from 1 to 10. These numbers are the severity index and the treatment effectiveness respectively. The severity index is a measure of how seriously afflicted the patient is with the selected condition, the rate of life loss (damage) grows quadratically with the severity index. When treatment is administered (by the doctor routine) the severity index is reduced by the difference between the treatment effectiveness and the treatment handicap, except when that difference would be less than 1, in which case the reduction in the severity index is set to 1. When a case is moved from the FIFO queue to the priority queue, or when it receives attention from the doctor routine, damage is assessed, and the patient’s life force adjusted (usually decreased) by the amount of damage assessed. It should be clear that the more efficient ADT operations are, the more likely this simulation will be to have a higher number of survivors.



>>>> [ FIFO Queues ] <<<<

?. Implement the queue ADT using a naive list implementation.
?. Implement the queue ADT using an implementation that has constant time performance for each queue operation.

?. Test the queue ADT by creating an instance and then performing a sequence of queue operations on it. Use the queue:front and queue:list operations to see the contents of the queue and verify that the implementation is operating as it should.



>>> [ Comparing Binary Heaps ] <<<

?. Write a procedure called (measure-stats arrival-period avg-life n) that takes the results of running N simulations each of which has the given inter-order arrival time for patients and the given average life, and returns the average and standard deviation of the survival rate and the largest queue length (as two pairs).
Each experiment is an execution of the simulation for approximately 1000 ticks with the given arrival-period and average life. For example, (measure-stats run 5 100 20) performs 20 executions of (run 1000 5 100) and reports on the statistical results.
?. Measure the average survival rate of the given implementation for average arrival periods of 2, 5, 10, and 20 ticks, and an average life of 1000.



The Emergency Room Queue
As already mentioned, the emergency room queue is implemented as a priority queue, in which the rate of life loss of patients is used as the key in the queue.


>>> [ Priority Queues ] <<<

?. Implement a priority queue, using a linked list to maintain the elements in the queue.

?. Test the implementation by creating a priority queue, performing a sequence of operations on it.

?. Measure the performance of this implementation of the priority queue by computing the average survival rate for each of the average arrival periods investigated in a Problem.



>>> [ Binary Heaps ] <<<
?. Implement a binary heap embedded in a vector.

?. Test the implementation.

?. Measure the performance of this implementation.

We don't do homework.

--Simon

Tis not homework. It's a practice problem from a scan book that i am using to learn Scheme. And i am not familiar with the language.

Fair enough. To answer your original question, yes it can be done in scheme (or any other language).

Dave

Okay, thanks Dave. It seems like a very difficult thing to simulate.

Can someone show how this can be achieved in C/C++ or even Haskell? Cause i don't understand this Scheme thing. :-/

Erm, without doing it for you what you need to do is define some functions to produce the data structures and utilities for acting on it. I don't think its the kind of task you want to attempt as a new user to be fair.

Especially if you want to produce things like generators etc. which requires an understanding of continuations.

Mark.

Oh okay. Thanks Netytan. What language should i do it in? Can someone relate it to me in Haskell? That should be simple enought right? I just want to see and have some understanding of how it would work. :-|

I'd suggest you do this in Scheme, but that's just my opinion. This task should be able to be able to be performed in either language as long as you know the language well enough. This isn't exactly an easy task for beginners.

That's just it... I dunno Scheme at all. Hence i was wondering if this can be done in any other functional programming language. Maybe C/C++ as a substitue for the time, until Scheme is more clear.

The implementation language in and of itself isn't relevant; in principle, all Turing-complete languages are capable of making the same set of computations. While practical issues (runtime requirements, support for specific language or library constructs such as threads or continuations) may make various algorithms easier or harder (or even impractical), it is always possible to accomplish a task even in, say, Befunge, or INTERCAL, or Unlambda.

What matters most is how familiar and comfortable you are with the language you are using. How 'expressive' a language is is irrelevant if you dislike it or don't understand it.

That having been said, Scheme is a particularly easy language to learn, at least WRT the core language; the current language standard, called Revised( 5) Report on the Algorithmic Language Scheme is only 50 printed pages long, including the formal syntax and semantics. If you are familiar with other languages, then even a simple overview such as my own Scheme in Short should be enough to give you some feeling for the language (BTW, constructive criticism on that is always welcome). Scheme is like Go or Chess - the basic rules are easy to learn, but true mastery is a lifetime process.

(The larger libraries are another matter; while the SRFI quasi-standard have helped things considerably, and R6RS should fix a lot of current problems, at the moment things are still rather hairy).

I should add that some textbooks which use Scheme (most notably the otherwise extraordinary Structure and Interpretation of Computer Programs) intentionally avoid teaching anything but the barest essentials of the language, so that they can focus on theoretical considerations without having the language get in the way, and to show how the language constructs can be implemented within the language itself. WHile this approach works well in the hands of a particularly skilled instructor, it usually falls flat with less inspired teaching, and also has the effect of convincing many students that Scheme (and Lisps in general) are crippled languages without even such basic facilities as file I/O - something which is patently untrue. OTOH, other books (e.g., Simply Scheme, How to Design Programs) use a unique library that can cause confusion for students who then try to use an implementation of the language which doesn't support it.

As for the problem at hand, I'll need to take a closer look at it first, and if I can make any recommendations (aside from learning Scheme first) later on. HTH.

A breakdown/guideline of how this can be achieved in Scheme language will be appreciated Schol-R-LEA (or anyone who wishes to help). Thanks.

That's going to depend on a number of factors. I'm assuming here that you are using plain-vanilla R5RS Scheme with no libraries; if you can use the SRFI or SLIB forms, then a lot of this would be simplified, really.

Also, how much detail I need to go into will depend in what you already know of the language; from what you said, I'd have to start absolutely from scratch, which might not be appropriate.

Which interpreter or compiler are you using also can make a difference, especially as a total novice. I'll assume for now that you're using Dr Scheme 3.01, and a lot of what I'll say below is specific to it, but if you aren't please let me know. If you are, you'll want to make sure that it's set to the right dialect; in the main menu, go to Language: Choose Language... and select 'Standard (R4RS)', hit 'Ok', then in the main editor hit the 'Run'.

OK, a few basics. Scheme is designed to be effectively compiled, but it is more often used through an interpreter, especially during development. Usually, the main interface is the Listener (and immediate interpreter prompt where you can enter smippets of Scheme code directly). In Dr Scheme, the main window is split into two sections, with (by default) the editor window at the top and the listener at the bottom. (This contrasts with most other Schemes, such as the MIT interpreter, which just give you the text-only listener; you need to invoke the editor for the listener, and it runs as a separate program. Some others work like the eLisp interpreter buffer, where you edit the code free-form, select the snippet to run, and then use a keystroke command to invoke the interpreter).

When you run code in the listener, it runs in a global environment known as the workspace; functions and variables created at the listener will last through the session, but get cleared when a new session is begun or the interpreter is closed. Using File: Log Definitions and Interactions, you can create a transcript of everything you are doing in the Listener for the rest of the current session. You can also save the current workspace definitions using File:Save Definitions as....

To create a separate program, you would enter the code into the edit window and save it as a normal source file. When you hit the 'Run' button, it creates flushes the existing session, creates a new session, and runs the code currently in the editor window.

If you haven't already, try typing in snippets of code like the ones below at the listener, to get a feel for the results:



I've got to go right now, but I'll get back to you once you've replied on this; as I said, some idea of how much you know would help. If you haven't already looked at it, take a look at my tutorial, and maybe at some of the other oens linked to at Schemers.org.

For a taste of some more advanced Scheme: it is important the to remember is that in Lisp languages, most data structures are built out of the basic lists. For example, a binary tree

might look like:

(4 (2 (1 3)) (6 (5 7)))

You can use lists to create most abstract data types, and the language even has built in support for certain ones (sets and associative lists in particular). However, you would not define a data structure type the way you might in C or Java (in basic Scheme at least; see