Helpful Information
 
 
Category: Other Programming Languages
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.

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. :-/

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.

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.

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. :-|

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 (http://www.schemers.org/Documents/Standards/), called Revised( 5) Report on the Algorithmic Language Scheme (http://www.schemers.org/Documents/Standards/R5RS/) 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 (http://josako.freeservers.com/tech/SiS/ToC.html) 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 (http://srfi.schemers.org/) quasi-standard have helped things considerably, and R6RS (http://www.schemers.org/Documents/Standards/Charter/status-mar-2006.html) 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 (http://mitpress.mit.edu/sicp/)) 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 (http://www.htdp.org)) 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 (http://www.drscheme.org/) 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:



(+ 2 2)

(define pi 3.14)

pi

(define (square x) (* x x))

(square 4)

(define (area-of-circle r) (* pi (square r)))


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 (htp://www.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


4
/ \
2 6
/ \ / \
1 3 5 7

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 SRFI 9 (http://srfi.schemers.org/srfi-9/srfi-9.html) for one library implementation of data structure types). Rather, you would define a series of functions that build the data structures from primitive lists, and populate, update, delete, etc. the data in them. This means that data manipulation has a somewhat higher overhead; however, it also gives a tremendous amount of flexibility in how you can manipulate data dynamically.

I'm using DrScheme, version 301 by PLT. It's configured as your suggested. I understand definitions, syntax and the naming conventions. I also know how to do some simple expressions and variable bindings.

I'm using DrScheme, version 301 by PLT. It's configured as your suggested. I understand definitions, syntax and the naming conventions. I also know how to do some simple expressions and variable bindings.
Ah, OK, good. Let's see then:

For a FIFO queue type, you have a number of possible approaches, depending on how you want it to work. Basically, we need to write a set of functions which will manipulate create the queue, add new items to it, or remove a value from it and return the value in question.

Now, in Scheme as it's usually taught, the preferred approach is functional; the functions for creating the queue and adding new values to it can be done by simply creating new queues with the desired values:

(define (queue:new top) (list top))

(define (queue:add queue new-item)
(append queue (list new-item)))

(define (queue:next queue)
(if (null? queue)
nil
(car queue)))
This has the disadvantage that the client-programmer would have to capture the returned value explicitly, rather than having a persistent variable which gets changed by the functions. More seriously, the function (queue:next) returns the value of the current top item, but doesn't actually remove it; for that you would need another function, which returns a the remainder of the queue:

(define (queue:remove queue)
(if (pair? queue)
(cdr queue)
nil))
To see that this code works (after a fashion), try these tests:

(define q (queue:new 1))
q
(define q (queue:add q 2))
q
(queue:next q)
q
(define q (queue:remove q))
q
While this is usable after a fashion, it is rather clumsy to use, and the fact that we are redefining q each time makes a functional approach less valuable - it simply puts the burden of handling re-assignment on the client-programmer. It would make more sense to use a true mutable data structure - that is, one where the variable itself gets changed by the functions, rather than having to

If you only need a single global queue, it would be quite easy; you could simply have the functions implicitly reference the global:


(define queue '())

(define (queue:new! top)
(set! queue (list top)))

(define (queue:add! new-item)
(set! queue (append queue (list new-item))))

(define (queue:next!)
(if (null? queue)
'()
(let ((next (car queue)))
(set! queue (cdr queue))
next)))

;; test code
(queue:new! 1)
queue
(queue:add! 2)
queue
(queue:next!)
queue
However, this only creates and works on a single variable, rather than defining an abstract data type; it is too limiting for most purposes. One could try redefining these functions so that they take a queue variable as an argument:

(define (queue:new! queue top)
(set! queue (list top)))

(define (queue:add! queue new-item)
(set! queue (append queue (list new-item))))

(define (queue:next! queue)
(if (null? queue)
'()
(let ((next (car queue)))
(set! queue (cdr queue))
next)))

;; test code
(define q '())
(queue:new! q 1)
q
(queue:add! q 2)
q
(queue:next! q)
q
Unfortunately, as you will see if you run this, it won't work; this is because parameters are passed by value in Scheme, so the value altered by (set!) is local to the function. In order to alter the actual value of a variable, you would need to define these as macros instead:

(define-syntax queue:new!
(syntax-rules ()
((queue:new! queue top)
(define queue (list top)))))

(define-syntax queue:add!
(syntax-rules ()
((queue:add! queue new-item)
(set! queue (append queue (list new-item))))))

(define-syntax queue:next!
(syntax-rules ()
((queue:next! queue)
(if (null? queue)
nil
(let ((next (car queue)))
(set! queue (cdr queue))
next)))))

;; test code
(queue:new! q 1)
q
(queue:add! q 2)
q
(queue:next! q)
q
There is still one problem with this, in that these functions are not actually part of the type per se; they define the behavior of the queue variables, but there's nothing preventing you from accidentally applying them to a different kind of variable entirely. What you really want is something similar to objects in languages such as Smalltalk, C++ or Java. While base Scheme does not have a preexisting syntax for OOP classes, it does have an equivalent construct that can be created with ordinary nested functions: a closure. A closure a function defined within another function, which then passes a link to the nested function as it's return value. Doing this causes the local function environment of the outer function to be retained, including any variables which are in local scope. This can be used to create persistent objects which can be used as if they were the inner function themselves; if that function is defined to accept arguments which indicate an operation to perform, it can be used to act like method dispatch. thus, you can define a queue 'class' as:

(define (make-queue top)
(define queue (list top))
(define (add! new-item)
(set! queue (append queue (list new-item))))
(define (value)
queue)
(define (next!)
(if (null? queue)
'()
(let ((next (car queue)))
(set! queue (cdr queue))
next)))
(define (dispatch method . parameters)
(case method
('add! (if (null? parameters)
queue
(add! (car parameters))))
('value (value))

('next! (next!))
(else 'invalid-method)))
dispatch)

(define q (make-queue 1))
(q 'value)
(q 'add! 2)
(q 'value)
(q 'next!)
(q 'value)
q
(Note that you now need the (value) method for returning the value of the queue; the variable itself is a function, not a list, as shown by the last item in the test code.)

Of course, this involves a lot of extra work, which you would need to do over again every time you created a new object class. Clearly, it would make sense to have a special form - a macro, perhaps - to automatically handle the bookkeeping details. Fortunately, such forms do exist - several different ones, in fact; there are several different type and object types for Scheme. Unfortunately, at this time none of these is standard, so how you would create to classes would depend on which library you use.

I expect that I've lost you by now :); if not, then all the better. Feel free to ask any questions you need to. For now, I'll leave the rest of the problem to you.

Oh, for further Illumination fnord about Scheme in general, see The Schemer's Way (http://practical-scheme.net/docs/schemersway.html) (or consult your pineal gland).

As a bit of trivia, I should mention that the original design of Scheme was object-oriented, even before Smalltalk in fact; it was originally intended as an experiment in an early form of OO called the 'actor model'. As the language was being developed, however, the designers realized that the code supporting actors was identical to the code for closures, and eventually, they did a formal analysis that demonstrated that actors and closures were equivalent. Thus, they removed the actor-specific parts of the language, and showed that the same actor support could be coded in the language itself using the macro system (the language has changed considerably since then, but the principle remains the same).

Also, because Scheme is designed with a heavy emphasis on recursion, the language standard mandates that Scheme compilers use a technique called 'tail-recursion elimination' to improve the efficiency of simple tail recursive functions. How tail recursion elimination works is this: in functions that are tail recursive, the last thing the function does is call itself. Since the function environment isn't needed any more, the compiler can reuse it for the new function, which means that the stack space is saved. Thus, all the compiler has to do is replace the final call with a jump, and the function is in effect transformed from a recursive one into an iterative one. This allows programmers to use tail recursive functions for general loops without the overhead that recursion usually has. Most Scheme compilers have even more elaborate tail-call optimization techniques, ones which take advantage of the highly regular structure of the language; in fact, there are several kinds of optimization which are more or less unique to the Lisp-family languages, because they wouldn't be practical to perform in most other languages. This is why, while Scheme code normally isn't very efficient when compiled naively, it is in some cases possible to generate highly-optimized Scheme programs which are comparable to C in performance.

I see. Hmm, im getting the idea. However, with the last code... when i run it i get something that says "#<procedure:dispatch>"

Is that suppose to happen? Also, is it possible to start off with a queue that already has elements in it and then add/remove?

I see. Hmm, im getting the idea. However, with the last code... when i run it i get something that says "#<procedure:dispatch>"

Is that suppose to happen?

Yep. This is the actual value of the variable q in that last example: the closure for the function (dispatch), which had been returned by (make-queue) earlier. I included it to show a) what the closure actually is, and b) why you couldn't just print the value of q from the top-level interpreter the way you could in the other versions.


Also, is it possible to start off with a queue that already has elements in it and then add/remove?

Yes; we can change the constructor functions so that they can take multiple arguments, either by using a list for the argument or by using variable arity. In fact, this would actually make the constructor easier in this case, as the current version has to create a list out of the initial argument; taking multiple arguments, they would already be a list, so we can just assign the value to queue directly:


(define (make-queue . top)
(define queue top)
;; ... and so on

The period, when used in the formal parameter list of a function, indicates that the function should take several separate variables, then put them all into the variable following the period as a list. So, given this, you would then be able to write:


(define q (make-queue 1 2 3 4))
(q 'value)


... and the interpreter would return (1 2 3 4) as the value of the queue.

Nice work Schol-R, I'm not sure that you represented functional programming to it's upmost though. That said its personal preference and Scheme doesn't dictate what style you use either way :).

A queue is really nothing more than a list and some simple actions for interacting with it. Now if a queue is just a list and lists are so frequently used in a functional manor you have to wonder why it's necessary to produce an object with all the state changes that implies.

Why not just use the queue in your program like you would any other list?

To answer your question Mochi yes you can start of with more than one value however you'll have to make a simple change to the code:



(define (make-queue top)
(define queue (list top))
...




(define (make-queue . queue)
; removed the queue definition
...


Now whatever you pass to the function will automatically be a list, and you can pass in as many arguments as you like. This saves you a little bit of work too :).

Heres a small example of this using a very small function so you have a better idea of whats going on.



> (define (a . b)
b)
> (a 1 2 3 4)
(1 2 3 4)
> (a 1)
(1)
>


The reason that you're getting a procedure displayed is because q is holding the procedure returned when the queue was made :).

The 'value method should return the queue in a printable manor (it's just a list). Remove the 'q at the very end and it should act more like you expected.

EDIT: Awesome. Schol-R seems to have beat me to it :).

Take care,

Mark.

Oh i see. Wow, that minor change makes a world of a differenct. So now the new code for a Queue to take multiple arguments is



(define (make-queue . top)
(define queue top)
(define (add! new-item)
(set! queue (append queue (list new-item))))
(define (value)
queue)
(define (next!)
(if (null? queue)
'()
(let ((next (car queue)))
(set! queue (cdr queue))
next)))
(define (dispatch method . parameters)
(case method
('add! (if (null? parameters)
queue
(add! (car parameters))))
('value (value))

('next! (next!))
(else 'invalid-method)))
dispatch)




The test code that i used is dereived from Schol-R-Lea's original code as follows.
By the way, i notice that although "(q 'value)" occurs 3 times in the test code they all return different results. Hmm...



(define q (make-queue 1 2 3 4 5 6 7 8))
(q 'value)
(q 'add! 2)
(q 'value)
(q 'next!)
(q 'value)
q




The results were so




(1 2 3 4 5 6 7 8)
(1 2 3 4 5 6 7 8 2)
1
(2 3 4 5 6 7 8 2)
#<procedure:dispatch>



My question now is this... suppose i wanted the code to return a queue but this time i want to get rid of the numbers less that say "5" out of the queue
For example --> (5 6 7 8) would be the desired new queue.

Would there have to be some kind of comparison operation to do that?

Also something i notice, i added a "2" but it still stays at the end... I thought it might have gone next to the already existing "2"

My question now is this... suppose i wanted the code to return a queue but this time i want to get rid of the numbers less that say "5" out of the queue
For example --> (5 6 7 8) would be the desired new queue.

Would there have to be some kind of comparison operation to do that?

Also something i notice, i added a "2" but it still stays at the end... I thought it might have gone next to the already existing "2"

For that I'd use filter, it's not standard in most Scheme systems but heres my implementation:



(define filter
(lambda (fn values)
"This function is a tail-recursive implementation of the filter
function found in other Lisp dialect."
(let loop ((list values)
(rest '()))
(if (pair? list)
(let ((item (car list))
(next (cdr list)))
(if (fn item)
(loop next (cons item rest))
(loop next rest)))
(reverse rest)))))


This is purely functional, if you want it to be destructive (change the value given) then you'll have to make a few changes. If not then you can simply use the value or save it for later :cool:.



> (list 5 2 6 7 1 2 3 2 4 6 7 8 0 9)
(5 2 6 7 1 2 3 2 4 6 7 8 0 9)
> (define a-list (list 5 2 6 7 1 2 3 2 4 6 7 8 0 9))
> a-list
(5 2 6 7 1 2 3 2 4 6 7 8 0 9)
> (filter (lambda (e) (> e 4)) a-list)
(5 6 7 6 7 8 9)
>

2 doesn't get pushed in by the other 2 because that's not a queue, in a queue the last item added goes onto the end of the queue and the first to be removed is always at the front. Think real life :).

Take care,

Mark.










privacy (GDPR)