Data structure | 代做thread | java作业 | project | Haskell作业 – 63 Project 4 – Socrates School

63 Project 4 – Socrates School

Data structure | 代做thread | java作业 | project | Haskell作业 – 这是利用Haskell进行训练的代写, 对Haskell的流程进行训练解析, 涵盖了Data structure/thread/java/Haskell等程序代做方面, 该题目是值得借鉴的project代写的题目

of Functional Dance and Deep Thought

(due Friday 12/04/2020, 5:00pm)

Work with one partner (chosen by Tuesday 11/24), or alone.

Table of Contents

• Overview o Starting your Dance.hs file o Turning it in
• Task o Rules o Requirements o The Writeup
• Grading o Scoring Breakdown o Consistency in Outcomes
• Running Tests

Overview

• please read thoroughly – we highly recommend you understand this document in full, especially the grading section, before starting.
• continue to use GHC version 8.8.4. No change from our previous assignments.
• You can work with one partner ; by request (via piazza), you may work with one other student; you can also work alone if desired. Find your partners or request a partner be matched for you by the partners-deadline (see above). You should get started early, don’t wait until after being manually matched to someone else. o we encourage you to find partners, mentioning general times in the week you’re available to have video chats, or perhaps your study habits, etc.
• While working on the project, you’ll likely want to use the DanceCardChecker. java file on individual runs to check for consistency. There are sample runs below that work with Haskell implementations.
• You will re-implement our second project in Haskell.

o The file needs to be named Dance.hs.

• all students will individually write up the process.
• turn in your work to both students’ accounts on blackboard , but in a zipped file containing both students’ usernames/work and your own writeup. It’s your sole responsibility to get your work turned in on time, with your writeup, to your own blackboard account. This way, you can use tokens individually, varying from your partner in this choice.
• DO NOT trade off parts of the implementation per person. If you have a partner, you need to actually work through it together over the whole process.

Starting your Dance.hs file

You might need to copy in some of the folders like we’ve had on homeworks. But if you’ve got cabal installed, you also may be able to just run commands like cabal install HUnit –lib for each library such as HUnit that you want. Any standard libraries you use, we will be able to use them as well, so please do not upload any library code (see what to turn in below).

module Main where

-- some likely imports you might want (including some specific
definitions);

-- generally importing concurrency and  Data structure libraries is okay.

import System.Environment(getArgs)

import Control.Concurrent(MVar(..),takeMVar,putMVar,newEmptyMVar,forkIO)

import Control.Monad(replicateM)

...

main :: IO ()

main = do

...

Turning it in

Create a folder with both team members’ netID’s in it (or just your own), like msnyde14_gmason1_p4. Adjacent to these folders is your text file, WRITEUP.txt (other common document-writing extensions welcome). We will paste in fresh copies of our own testing file but you can consider the same kind of approach from our second project. Please avoid any packages that require any additional installation – only standard library files, or pre-approved modules that can be downloaded and included in-place.

You need to have this structure in your submitted work:

 partner01_partner02_p4/

  Dance.hs

  WRITEUP.txt

Task

You (and your partner) will implement the following concurrent program in Haskell using concurrent mechanisms (MVar, Chan, BoundedChan are common options). Lastly, you will write up the experience with any relevant details, things you tried that was surprising or difficult or informative, and any build-instructions needed to run your code.

There are N leaders and M followers at the Socrates School of Functional Dance and Deep Thought. Each dancer has a dance card that should be filled out by listing the person with whom they will dance that song. It has the following eight entries on it:

1. Waltz
2. Tango
3. Foxtrot
4. Quickstep
5. Rumba
6. Samba
7. Cha Cha
8. Jive

Everybody wants to dance each of the dances, but they cannot dance more than two dances with the same partner – people would talk! Leaders invite any follower of their choosing to dance a specific dance, and cannot ask anyone else to dance until they are either accepted or rejected. If accepted, they start asking anyone for other available dances on their own dance card. Followers wait for invitations, and then accept a dance or not based on some decision logic but always constrained so that they aren’t promising to dance the same dance with two different leaders, and they don’t agree to a third dance with any particular leader.

• A leader with a full dance card also stops searching for partners.
• When all leaders have stopped searching for partners, the matching process is over and results should be reported. It is not necessary to achieve some perfect complete matching, but there must be no more possible moves (no leader could have added more to their dance cards if they’d asked the right person) when your program stops.

Rules

• There will be N leaders and M followers, fed via command line arguments.
• The actual task is to fill in dance cards before the evening of dancing begins. One dance of each style will play, for a total of eight songs; this means that every individual has one chance at dancing with someone during each song (e.g., you can’t dance two+ waltzes).
• leaders employ any strategy you can think of to ask any follower to dance with them for any particular dance. o some possibilities: random selection, sequential, beginning with their own number mod M (it’s okay for them to know they are leader #5 of 8, for example), or any alternative of your own devising.
• leaders must wait on a response before they can ask anyone else. Note though, implementation-wise you may find that a leader attempted to ask a follower but the attempt failed in some sense – e.g., if you tried to put a value into a buffer but were told it didn’t happen, then you are free to instead go ask someone else to dance. (Some libraries will offer non-blocking put functions that return a boolean: true for "yes, you successfully put the value in the buffer" or false for "no, there was no room in the buffer, and I didn’t wait around for things to change". If you are only using functionality that definitely blocks when attempting to put into a full buffer, you may indeed have all your leaders queued up, waiting to ask some particular follower for a dance!).
• when there is nobody else a leader could ask to dance for any dances, the leader is done attempting to fill out their dance card. Either their card is full, or they’ve already been told "no" by all followers for the leader’s remaining open dances.

• followers wait for invitations, and then respond "yes" if they don’t yet have a dance partner for the dance, and if they haven’t already agreed to dance with this person for two songs. If you want to make the followers’ logic more complicated than "yes unless it has to be no", you’re welcome to do so, but it will make the project harder. o somehow, your followers will need to know that the matching-session is over; perhaps there were fewer leaders and this follower doesn’t get to fill their card out! Think about how you’ll handle this extra need for communication.

Requirements

• each "person" must be an individual thread. This includes leaders and followers! o these threads must exist continuously for the whole matching process, and perform the logic of the person/role they embody; neither leaders or followers may effectively be objectified vessels (like some glorified data structure that is modified/interacted with by other threads). Followers should be just as involved in the conversations as leaders!
• another "main" thread might be necessary/useful to announce (print) the results at the end. (Coordinating printing can be one significant hurdle on this project). You can add more threads as you like for whatever extra purposes.
• everybody communicates with each other through some personal dedicated resource (like a buffer) that anyone can attempt to interact with, and only that person can receive from. Only one message can be pending at a time, though. o Hint: You might think of them as individual mailboxes. o these communication resources must all be collectively accessible at the same time as each other, but individually accessible by only one person at a time. (there must not be a "global lock"; if L1 is asking F3 for a dance, that shouldn’t mean that it’s currently impossible for L4 to ask F for a dance until L1 hears back). o this means that you are not allowed to lock down an array/list that represents all leaders or followers; that would imply that two different conversations couldn’t happen at once.
• two command line arguments, integers representing N leaders and then M followers, must be provided on the command line.
• Leaders will be numbered from 1 to N. Followers will be numbered from 1 to M.
• results will be presented in this exact fashion: "Leader X:" on the first line, followed by the eight dances and the follower (or "" for unassigned; exactly six dashes) listed afterwards in a second column. Match spacing shown

in the example below. By listing all leaders' dance cards, we have enough
information.

• We will run a script to feed your program’s outputs to a checking program, so this means you do need to get the formatting precisely correct. (There’s no way we’re running arbitrary-timed programs or writing testing scripts per language/libraries).

Leader 1:

Waltz with 3

Tango with 5

Foxtrot with 2

Quickstep with 1

Rumba ------

Samba with 2

Cha Cha with 3

Jive ------

Leader 2:

Waltz with 2

Tango with 4

...

You do not have to find a "perfect" matching for all participants, just a consistent one; some may end up with no available dances, even though others are still not dancing all dances. Perhaps the wrong dance is available, or they’ve already agreed to two other dances with each other, or N and M may be significantly different values (which inherently means a lot of empty slots on dance cards).

However, your program must not always find the same outcomes. If there is no variance in your output, there is something constraining (or over-coordinating) your outcome, and we aren’t really getting the concurrency we expect. This will be a significant part of your grade.

The Writeup

As a last step, you will write up a brief summary of what you experienced (as a part of the WRITEUP.txt file; it can be any other common document type as you’d like). There’s no page limit, just make sure you’ve focused on each of the questions below. Perhaps a page and a half maximum would be sufficient. The questions that need to be answered here are:

• On what line numbers in which file do you create the threads for all the leaders and followers?
• For your programming task, what were the challenges that you faced? Where was there competition for resources, and where was there a need for cooperation?
• In your implementation, what aspects of the task were straightforward, and which ones felt laborious?
• What kinds of bugs did you run into deadlock? How did you attempt to inspect what was going wrong with the code? (Did you use any debuggers or anything? You weren’t required to do so, I’m just curious how your experience went).
• What was the breakdown of work between you and your partner?
• Lastly, what piece of advice do you wish you had received at the start of the assignment?

Grading

Scoring Breakdown

• 55%: logically consistent outcomes: o + 15%: logically consistent outcomes at different sizes of N, M o + 10%: outcomes vary on repeated runs of the same values of N, M o + 10%: nobody dances a dance twice o + 10%: nobody dances too often with someone else o + 10%: didn’t leave any possible dance matchings out (kept searching until all options were considered). o some overall deductions that may be assessed: – 15%: frequent failures – 5%: rare failures (likely not easily reproducible, perhaps easiest- found by varying N/M in certain ways). – 5%: poor-to-no comments – 5%: extra print statements that render the consistency checker unusable on your code.

• 30%: adhering to manual checks: o + 10%: both leaders and followers are implemented as threads, which actually inmplement their own decisions respectively. o + 10%: no "global lock" : While one person is dealing with a request, all uninvolved people can be busily working on their own dance cards. Beware locking over an array of all leads/all follows! o + 10%: your code doesn’t devolve to some predictable ordering. If you find some pattern, for instance if leader 1 always dances with follows 1, 1, 2, 2, 3, 3, 4, 4, and leader 2 always dances with partners 2, 2, 3, 3, 4, 4, 5, 5, then we need to shift something to make sure the outcomes can vary from run to run. It’s okay if there are trends such as "first leader tends to get their card filled out a certain way, but not quite always".
• 15%: completed writeup with reasonable content.

Consistency in Outcomes

Your score will be based partly on calculating consistent outcomes; for instance, no person can dance with multiple other people during the same dance. Also, if a lead and follow were both idle during a song they could have danced together, it isn’t a consistent result.

Running Tests

You can test your code via the same DanceCardChecker.java file as in our previous project. This Java program will check the output from your program to see if it generated a result consistent with the rules.

To save your output to a file and run the consistency checker on your output:

ghc --make -o dance Dance.hs

./dance N M > sampleout.txt

javac DanceCardChecker.java

java DanceCardChecker sampleout.txt N M

Or, do the whole thing at once. The checker will notice that you only have two arguments, and read from stdin rather than from a filename. (note the N, M arguments are needed at both instructions):

ghc --make -o dance Dance.hs && ./dance 2 3 | java DanceCardChecker 2 3

The goal is to get a session like the following, which congratulates you on a job well done.

demo$ ./dance 2 3 > output.txt

demo$ java DanceCardChecker output.txt 2 3

apparently you've created a consistent result. good job!

demo$ ghc --make -o dance Dance.hs && ./dance 2 3 | java DanceCardChecker
2 3

Loaded package environment from <...snipped...>

apparently you've created a consistent result. good job!

Sample Run (mac/unix)

Here, we assume your main::IO() method is in Dance.hs.

demo$ ghc --make -o dance Dance.hs

demo$ ./dance 2 3

Leader 1:

Waltz with 3

Tango ------

Foxtrot with 2

Quickstep with 1

Rumba with 2

Samba with 3

Cha Cha with 1

Jive ------

Leader 2:

Waltz with 2

Tango with 1

Foxtrot with 3

Quickstep ——

Rumba with 3

Samba ——

Cha Cha with 2

Jive with 1

demo$ ./dance 2 3 > sampleout.txt

demo$ javac DanceCardChecker.java

demo$ java DanceCardChecker sampleout.txt 2 3

apparently you’ve created a consistent result. good job!

demo$