Categories
Python

Computer Ethics Paper (or Presentation) – Assignment Due during Week 4 The class

Computer Ethics Paper (or Presentation) – Assignment Due during Week 4
The class is divided into groups to provide a presentation of a selected topic as it relates to Computer Ethics. You will
present the topic using PowerPoint slides. The presentation must include at least 2 references. The APA style is used,
which we see in most Computer Science textbooks. At the end of the paper, under the topic “References,” we have an
alphabetic listing of all references used.
Paper Formatting Requirements: Title Page, Body of Paper (2-3 pages), References Page (min 2 non-web references);
Times New Roman font; Double Spaced, 1” margins all around, Page Number in upper right margin (header), Your name
in upper left margin (header)
Examples of Topics for the Ethics Paper/Presentation Assignment
1. Free Speech and the Internet
2. Copying Music over the Internet
3. The Use of Robotics in War Planning and Implementation
4. Cyber terrorism, Hacking, and Security
5. Fairness in the Workplace
6. Encryption, Law Enforcement, and Privacy
7. Product Distribution, Antitrust, and Competitive Ethics
8. Intellectual Property Rights Strategy and Trade Secrets
9. Intellectual Property: Copyright and Patent
10. Intellectual Property: Trademarks, Intellectual Property and Product Design
11. Safety-Critical Systems
12. Whistle Blowing
13. Shrinkwrap/Clickwrap Agreements
14. The Fourth Amendment, Law, and Post-9/11 Surveillance
15. Privacy and Civil Liberties
16. Viruses, Worms, and Other Computer Animals
17. The Password and Other Forms of Security Identification Methods
18. How secure is your E-mail? Can it become more secure?
19. A Famous Security Breach
20. An Overview of Two Prominent Virus Detection Programs
21. Hardware and Software Theft Issues
22. Firewalls
23. Denial of Service Attacks
24. The Major Components of a Computer Security Plan for a University
25. Employee and Citizen Monitoring
26. Cookies
27. Spyware
28. Spam
29. Privacy Laws

Categories
Python

Computer Ethics Paper (or Presentation) – Assignment Due during Week 4 The class

Computer Ethics Paper (or Presentation) – Assignment Due during Week 4
The class is divided into groups to provide a presentation of a selected topic as it relates to Computer Ethics. You will
present the topic using PowerPoint slides. The presentation must include at least 2 references. The APA style is used,
which we see in most Computer Science textbooks. At the end of the paper, under the topic “References,” we have an
alphabetic listing of all references used.
Paper Formatting Requirements: Title Page, Body of Paper (2-3 pages), References Page (min 2 non-web references);
Times New Roman font; Double Spaced, 1” margins all around, Page Number in upper right margin (header), Your name
in upper left margin (header)
Examples of Topics for the Ethics Paper/Presentation Assignment
1. Free Speech and the Internet
2. Copying Music over the Internet
3. The Use of Robotics in War Planning and Implementation
4. Cyber terrorism, Hacking, and Security
5. Fairness in the Workplace
6. Encryption, Law Enforcement, and Privacy
7. Product Distribution, Antitrust, and Competitive Ethics
8. Intellectual Property Rights Strategy and Trade Secrets
9. Intellectual Property: Copyright and Patent
10. Intellectual Property: Trademarks, Intellectual Property and Product Design
11. Safety-Critical Systems
12. Whistle Blowing
13. Shrinkwrap/Clickwrap Agreements
14. The Fourth Amendment, Law, and Post-9/11 Surveillance
15. Privacy and Civil Liberties
16. Viruses, Worms, and Other Computer Animals
17. The Password and Other Forms of Security Identification Methods
18. How secure is your E-mail? Can it become more secure?
19. A Famous Security Breach
20. An Overview of Two Prominent Virus Detection Programs
21. Hardware and Software Theft Issues
22. Firewalls
23. Denial of Service Attacks
24. The Major Components of a Computer Security Plan for a University
25. Employee and Citizen Monitoring
26. Cookies
27. Spyware
28. Spam
29. Privacy Laws

Categories
Python

Motivation In this assignment, we will explore Internet Measurements, a field of

Motivation
In this assignment, we will explore Internet Measurements, a field of Computer Networks which
focuses on large scale data collection systems and techniques that provide us with valuable
insights and help us understand (and troubleshoot) how the Internet works. There are multiple
systems and techniques that focus on DNS measurements, BGP measurements, topology
measurements, etc. There are multiple conferences in this area, which we invite you to explore
and keep up with the papers that are published. For example, the IMC conference is one of the
flagship conferences in this area: ACM Internet Measurement Conference
A gentle introduction into the Internet Measurement field is to work with large scale BGP
measurements and data to study topics such as:
Characterizing growth of the Internet using various measures, such as number of
advertised prefixes, the number of Autonomous Systems, the percentage growth of
prefixes advertised by Autonomous System, and the dynamics of Autonomous System
path lengths
Inferring problems related to short-lived Announcement and Withdrawals,
Inferring possible DDoS attacks by identifying community countermeasures such as
“Remote Triggered Blackholing”
Introduction
In this project we will use the BGPStream tool and its Python interface PyBGPStream to
understand the BGP protocol and interact with BGP data. The goal is to gain a better
understanding of BGP and to experience how researchers, practitioners, and engineers have
been using BGPStream to gain insight into the dynamics of the Internet. If you are interested in
going deeper, you can use these same tools to observe and analyze real-time BGP data or
download and analyze other historical BGP data.
BGP Measurements Project
Project Overview and Background
The zip file accompanying this assignment contains the code and data needed to implement the
functions in the file bgpm.py. You will submit only bgpm.py to Gradescope and all your code for
the project must be contained within bgpm.py.
This project description, in combination with the comments in bgpm.py, comprise the complete
requirements for the project. There are two complete sets of data included in the zip file and the
provided test harness in check_solution.py will test each of your functions against both sets
of data. You are welcome to copy and modify check_solution.py to better suit your
development and debugging workflow, but you will have the best chance of success with the
hidden data set used for grading if your final submission passes all the tests in the unmodified
check_solution.py.
This project is designed to work in the class VM where the BGPStream libraries are installed.
Your code will need to run without modification in the course VM.
Some of the functions will have runtimes of several minutes. There is a lot of data to process, so
the best way to speed up those functions is by focusing on the efficiency of your implementation.
It is possible, but not supported, to install BGPStream and PyBGPStream on your local machine.
Please don’t ask TA staff for help if you decide to do this. Gradescope imposes a hard time limit
of 40 minutes for a grading session. We have no control over this and will not be able to make
any allowances if your submission does not complete within that time limit.
Required Background
For this project, we will be using BGPStream, an open-source software framework for live and
historical BGP data analysis, supporting scientific research, operational monitoring, and post-
event analysis. BGPStream and PyBGPStream are maintained by the Center for Applied Internet
Data Analysis (CAIDA).
BGP Measurements Project
Read the resources
A high-level overview about how the BGPStream tool was developed was published by CAIDA in
BGPStream: A Software Framework for Live and Historical BGP Data Analysis. This paper provides
useful background and practical examples using BGPStream, so be sure to read it. Additionally,
you should read African peering connectivity revealed via BGP route collectors, which provides a
practical illustration of how the BGP collection system works.
Run Example Code Snippets
All the tasks are to be implemented using the Python interface to BGPStream. You are strongly
encouraged to browse the following resources to familiarize yourself with the tool, and to run
the example code snippets:
– PyBGPStream API: https://bgpstream.caida.org/docs/api/pybgpstream
– PyBGPStream API Tutorial: https://bgpstream.caida.org/docs/tutorials/pybgpst…
– PyBGPStream Repository: https://github.com/CAIDA/pybgpstream
– Official Examples: https://github.com/CAIDA/pybgpstream/tree/master/e…
Important Note
As will become apparent when you peruse the above documentation and tutorial information,
the majority of BGPStream use cases involve gathering data – either live or historical – directly
from the Route Collectors (which we refer to simply as “collectors”). The code for accessing a
collector or set of collectors directly usually looks like this:
stream = pybgpstream.BGPStream(
from_time=”2017-07-07 00:00:00″,
until_time=”2017-07-07 00:10:00 UTC”,
collectors=[“route-views.sg”, “route-views.eqix”],
record_type=”updates”,
filter=”peer 11666 and prefix more 210.180.0.0/16″
)
Each of the parameters to pybgpstream.BGPStream() winnows the data retrieved from the
collector(s). Because we are using pre-cached historical data in this project, you will not need to
specify a collector or a time range. You also don’t need to use any additional filtering.
BGP Measurements Project
For this project, you can use set up and configure your streams with:
stream = pybgpstream.BGPStream(data_interface=”singlefile”)
stream.set_data_interface_option(“singlefile”, type, fpath)
where type is one of [“rib-file”, “upd-file”]1 and fpath is a string representing the
path to a specific cache file. When processing multiple files, you will create one stream per file.
Familiarize Yourself with the BGP Record Format and BGP Attributes
It is critical that you understand the BGP record format, especially the meaning and content of
the fields (data attributes). A detailed explanation of BGP records and attributes can be found in
RFC 4271: A Border Gateway Protocol 4 (BGP-4).
It’s also worth spending some time exploring the provided data using the BGPReader command
line tool (“a command line tool that prints to standard output information about the BGP records
and the BGP elems that are part of a BGP stream”). Doing so will be particularly helpful in
understanding how the fields described in RFC 4271 and elsewhere map to the BGP record and
BGP elem concepts used by BGPStream and PyBGPStream.
Because PyBGPStream allows you to extract the BGP attributes from BGP records using code, you
will not have to interact with the BGP records in this format, but it is, nevertheless, helpful to see
some examples using BGPReader to understand the fields. The next section shows
Here, we will show sample command line output from BGPReader for illustration purposes:
# read records from an update file, filtering for IPv4 only
bgpreader -e –data-interface singlefile –data-interface-option
upd-file=./rrc04/update_files/ris.rrc04.updates.1609476900.300.cache
–filter ‘ipv 4’
# read records from a rib file, filtering for IPv4 only
bgpreader -e –data-interface singlefile –data-interface-option
rib-file=./rrc04/rib_files/ris.rrc04.ribs.1262332740.120.cache
–filter ‘ipv 4’
1 You can see a complete list of types by running: bgpreader –data-interface singlefile -o?
BGP Measurements Project
Update Example
The box below contains an example of an update record. In the record, the “|” character
separates different fields. In yellow we have highlighted the type (A stands for Advertisement),
the advertised prefix (210.180.224.0/19), the path (11666 3356 3786), and the origin AS (3786).
.0
RIB Example
The following is a Routing Information Base (RIB) record example. Consecutive “|” characters
indicate fields without data.
update|A|1499385779.000000|routeviews|route-
views.eqix|None|None|11666|206.126.236.24|210.180.224.0/19|206.
126.236.24|11666 3356 3786|11666:1000 3356:3 3356:2003 3356:575
3786:0 3356:22 11666:1002 3356:666 3356:86|None|None
R|R|1445306400.000000|routeviews|route-
views.sfmix|||32354|206.197.187.5|1.0.0.0/24|206.197.187.5|3235
4 15169|15169|||
Measurements Project
Setup
Do not rely on the directory layout of the provided data. Gradescope does not mirror the
directory layout from the provided files. Specifically, in your final submission, do not directly
access the filesystem in any way and do not import all or part of either os or pathlib. All
filesystem interaction will occur via PyBGPStream and the file paths will be taken from the Python
list in the parameter named cache_files that is passed to each function.
Cache Files / Snapshots
Locate the directory rrc04/rib_files included with this assignment. This directory contains
RIB dump files. Each filename (e.g., ris.rrc04.ribs.1262332740.120.cache) includes
the collector’s name (ris.rrc04), the type of data (ribs), and the Unix timestamp of the data
(1262332740, which you can convert to a date via either of the two above links).
Each of the cache files is a snapshot of BGPM data collected by the collector at the time of the
timestamp. In the rest of this assignment the term “snapshot” refers to the data in a particular
cache file. Do not pull your own data. Your solution will be graded using cached data only.
You will need to write code to process the cache files. Each entry in cache_files is a string
containing the full path to a cache file. To access a given path, your code will need to set up the
appropriate data interface in your BGPStream() constructor:
stream = pybgpstream.BGPStream(data_interface=”singlefile”)
stream.set_data_interface_option(“singlefile”, type, fpath)
where type is one of [“rib-file”, “upd-file”] and fpath is a string representing the
path to a specific cache file. When processing multiple files, you will create one stream per file.
BGP Measurements Project
Task 1. Understanding BGP Routing table Growth
In this task you will measure the growth over time of Autonomous Systems and advertised
prefixes. The growth of unique prefixes contributes to ever-growing routing tables handled by
routers in the Internet core. As optional background reading, please read the seminal paper On
Characterizing BGP Routing Table Growth.
Task 1A: Unique Advertised Prefixes Over Time
Using the data from cache files, measure the number of unique advertised prefixes over time.
Each file is an annual snapshot. Calculate the number of unique prefixes within each snapshot by
completing the function unique_prefixes_by_snapshot(). Make sure that your function
returns the data structure exactly as specified in bgpm.py.
Task 1B: Unique Autonomous Systems Over Time
Using the data from the cache files, measure the number of unique Autonomous Systems over
time. Each file is an annual snapshot. Calculate the number of unique ASes within each
snapshot by completing the function unique_ases_by_snapshot(). Make sure that your
function returns the data structure exactly as specified in bgpm.py.
Note: Consider all paths in each snapshot. Here, we consider all AS that appear in the paths (not
only the origin AS). You may encounter corner cases of paths with the following form: “25152
2914 18687 {7829,14265}”. In this case, consider the AS in the brackets as a single AS. So,
in this example, you will count 4 distinct ASes.
Task 1C: Top-10 Origin AS by Prefix Growth
Using the data from the cache files, calculate the percentage growth in advertised prefixes for
each AS over the entire timespan represented by the snapshots by completing the function
top_10_ases_by_prefix_growth(). Make sure that your function returns the data
structure exactly as specified in bgpm.py.
Consider each origin AS separately and measure the growth of the total unique prefixes
advertised by that AS over time. To compute this, for each origin AS:
Identify the first and the last snapshot where the origin AS appeared in the dataset.
Calculate the percentage increase of the advertised prefixes, using the first and the last
snapshots.
Report the top 10 origin AS sorted smallest to largest according to this metric.
Corner case: When calculating the prefixes originating from an origin AS, you may encounter
paths of the following form: “25152 2914 18687 {7829,14265}”. This is a corner case, and
it should affect only a small number of prefixes. In this case, you consider the entire set of AS
“{7829,14265}” as the origin AS.
Task 2: Routing Table Growth: AS-Path Length Evolution Over Time
In this task you will measure if an AS is reachable over longer or shorter path lengths as time
progresses. Towards this goal you will measure the AS path lengths, and how they evolve over
time.
Using the data from the cache files, calculate the shortest path for each origin AS in each snapshot
by completing the function shortest_path_by_origin_by_snapshot(). Make sure that
your function returns the data structure exactly as specified in bgpm.py.
For each snapshot, you will compute the shortest AS path length for each origin AS in the
snapshot by following the steps below:
– Identify each origin AS present in the snapshot. For example, given the path “11666
3356 3786”, “3786” is the origin AS.
– For each origin AS, identify all the paths for which it appears as the origin AS.
– Compute the length of each path by considering each AS in the path only once. In other
words, you want to remove the duplicate entries for the same AS in the same path and
count the total number of unique AS in the path.
– Example: Given the path “25152 2914 3786 2914 18313”, ”18313” is the origin
AS and ”2914” appears twice in the path. This is a path of length 4.
– Among all the paths for an AS within the snapshot, compute the shortest path length.
– Filter out all paths of length 1.
– Corner cases: The data that we are working with are real data, which means that there
may be few corner cases. In the vast majority of cases, paths have a straightforward
form of “25152 2914 3786”, but you might encounter corner cases such as:
If an AS path has a single unique AS or a single repeated AS (e.g., “25152
25152 25152”), the path has length 1 and should be ignored
If an AS path contains sets of multiple AS in brackets. This is related to
aggregation which you can read more about in RFC 4271.
Example: Given an AS path such as “25152 2914 18687 {2914,14265}
2945 18699”, the set “{2914,14265}” is counted as one unique AS for
the purpose of calculating the AS path length, even though “2914” is also
present outside the brackets – “2914” and “{2914,14265}” are distinct, so
the path length in this case is 6.
Example: Given an AS path such as “25152 2914 18687 18687 {18687}”,
the path length is 4 after removing duplicates, because “18687” and
“{18687}” are distinct.
You can ignore all other corner cases.
Task 3: Announcement-Withdrawal Event Durations
In this task, we will measure how long prefix Announcements last before they are withdrawn.
This matters because, when a prefix gets Advertised and then Withdrawn, this information
propagates and affects the volume of the associated BGP traffic. Optional background reading
on this topic can be found in The Shape of a BGP Update.
This task will use cache files from the update_files subdirectories. These are update files, so
you will pass “upd-file” in your call to set_data_interface_option(). Using the data from
the cache files, we will measure how long prefix Announcements last before they are withdrawn
by completing the function aw_event_durations(). Make sure that your function returns the
data structure exactly as specified in bgpm.py.
In defining Announcement Withdrawal (AW) events, we will only consider explicit withdrawals.
An explicit withdrawal occurs when a prefix is advertised with an (A)nnouncement and is then
(W)ithdrawn. In contrast, an implicit withdrawal occurs when a prefix is advertised (A) and then
re-advertised (A) – usually with different BGP attributes.
To compute the duration of an Explicit AW event for a given peerIP/prefix, you will need to
monitor the stream of (A)nnouncements and (W)ithdrawals separately per peerIP/prefix pair.
– Example: Given the stream: A1 A2 A3 W1 W2 W3 W4 for a specific peerIP/prefix pair,
you have an implicit withdrawal A1-A2, another implicit withdrawal A2-A3, and, finally,
an explicit withdrawal (and AW event) A3-W1. W1-W2, W2-W3, and W3-W4 are all
meaningless, as there’s no active advertisement. The duration of the AW event is the
time difference between A3 and W1. Again, we are only looking for last A and first W.
– Example: Given the stream: A1 A2 A3 W1 W2 W3 W4 A4 A5 W4 for a specific
peerIP/prefix pair, we have two AW events at A3-W1 and A5-W4.
– We consider only non-zero AW durations.
Task 4: RTBH Event Durations
In this task you will identify and measure the duration of Real-Time Blackholing (RTBH) events.
You will need to become familiar with Blackholing events. Good resources for this include RFC
7999, Section 2, BGP communities: A weapon for the Internet (Part 2), and the video Nokia –
SROS: RTBH – Blackhole Community.
This task will use cache files from the update_files_blackholing subdirectories. These are
update files, so you will pass “upd-file” in your call to set_data_interface_option().
Using the data from the cache files, we will identify events where prefixes are tagged with a
Remote Triggered Blackholing (RTBH) community and measure the time duration of the RTBH
events by completing the function rtbh_event_durations(). Make sure that your function
returns the data structure exactly as specified in bgpm.py.
The duration of an RTBH event for a given peerIP/prefix pair is the time elapsed between the last
(A)nnouncement of the peerIP/prefix that is tagged with an RTBH community value and the first
(W)ithdrawal of the peerIP/prefix. In other words, we are looking at the stream of
Announcements and Withdrawals for a given peerIP/prefix and identifying only explicit
withdrawals for an RTBH tagged peerIP/prefix.
To identify and compute the duration of an RTBH event for a given peerIP/prefix, you will need
to monitor the stream of (A)nnouncements and (W)ithdrawals separately per peerIP/prefix pair.
– Example: Given the stream: A1 A2 A3(RTBH) A4(RTBH) W1 W2 W3 W4 for a specific
peerIP/prefix pair, A4(RTBH)-W1 denotes an RTBH event and the duration is calculated
by taking the time difference between A4(RTBH) and W1.
– Note: There can be more than one RTBH event in a given stream. For example, in the
stream A1 A2 A3(RTBH) A4(RTBH) W1 W2 W3 W4 A5(RTBH) W5, there are two RTBH
events: A4(RTBH)-W1 and A5(RTBH)-W5.
– Example: Given the stream A1 A2 A3(RTBH) A4 A5 W1 W2 for a specific peerIP/prefix pair,
the announcement A3(RTBH) followed by A4 is an implicit withdrawal. There is no explicit
withdrawal and, thus, no RTBH event.
– In case of duplicate announcements, use the latest.
– Consider only non-zero duration events.
Submit bgpm.py
10 Task 1A
10 Task 1B
10 Task 1C
30 Task 2
20 Task 3
20 Task 4
100 Total Points

Categories
Python

There are three Comma Separated Value files as part of this assignment. Write a

There are three Comma Separated Value files as part of this assignment. Write a Python program to combine them appropriately into one file and write a Comma Separated Value file.
Once you have combined the files, output a simple table showing the cost of injuries per plant.i will upload the files

Categories
Python

https://media.githubusercontent.com/media/Ajim63/FIN-410-Python-Codes-and-Data/m

https://media.githubusercontent.com/media/Ajim63/FIN-410-Python-Codes-and-Data/main/Python%20Codes/Data/Heart.csv (Link for the data)

Categories
Python

Write Z specification for a Banking System according to the requirements given b

Write Z specification for a Banking System according to the requirements given below:
a) There are two types of accounts, i.e., Current account and Savings account.
b) Savings account requires minimum balance of 5000 rupees, but Current account
does not require any minimum balance.
c) Each account can have only one account holder, however, an account holder can
have more than one accounts.
d) Following operations are permitted on each account:
1) Create account:- Creation of a new account
2) Close account:- Closure (deletion) of an account
3) Withdraw cash:- Savings accounts have cash withdrawal limit of 10000
rupees per transaction whereas Current account does not have any limit
4) Deposit cash:- Any amount of cash may be deposited
Write program in Python Programming Language.
I need code in MS word file.

Categories
Python

I need Part 2 of this assignment. I have some of the code done I can share, I’m

I need Part 2 of this assignment. I have some of the code done I can share, I’m not sure if it’s completely correct. The problem I am having is that I cannot get turtle graphics to work.

Categories
Python

Write Z specification for a Banking System according to the requirements given b

Write Z specification for a Banking System according to the requirements given below:
a) There are two types of accounts, i.e., Current account and Savings account.
b) Savings account requires minimum balance of 5000 rupees, but Current account
does not require any minimum balance.
c) Each account can have only one account holder, however, an account holder can
have more than one accounts.
d) Following operations are permitted on each account:
1) Create account:- Creation of a new account
2) Close account:- Closure (deletion) of an account
3) Withdraw cash:- Savings accounts have cash withdrawal limit of 10000
rupees per transaction whereas Current account does not have any limit
4) Deposit cash:- Any amount of cash may be deposited
Write program in Python Programming Language.
I need code in MS word file.

Categories
Python

The objective of this project is to create a solution combining multiple concept

The objective of this project is to create a solution combining multiple concepts that have been presented in class, building off of the previous concepts of loops, string manipulation, and lists, along with the addition of:
dictionaries
user defined functions
files
As with project 2, note that you should only use techniques we have covered in class. Using more advanced concepts does not help your understanding of the basics, and is a red flag that the code may not be your own work. In particular, you may NOT use the Python break, quit, exit, continue or any other programming convention to prematurely exit out of a loop or your program. A thorough understanding of loops requires that you are able to structure the loop control correctly without using break or other forced exit. Even though you may pass the test cases, use of any of these instructions will result in a 20% reduction in your overall score. Do not use list or dictionary comprehension as a loop shortcut. If you know what this is and perfectly understand it, it is trivial for you to accomplish the same thing without list or dictionary comprehension. If you don’t know what it is, you should not be using it. If you have questions about this as you work on your program, discuss it with your class assistants or with the course instructors.
Description
Fictional restaurant Sparty Burger turned out to be a commercial success and they have since franchised across the country in the form of full-sized dine in restaurants, express restaurants, and food trucks. They need you to create a program that can analyze the revenue generated by their various restaurants. You will be given a CSV file that lists the store ids, locations (by state), store styles, and the revenues generated in the previous month. Your program will read through this file in order to perform its analyses. The analyses performed will be to count the number of restaurants in a given state, count the number of restaurants of a given restaurants, calculate the average revenue generated by restaurants in a given state, calculate the average revenue earned by restaurants of a given restaurants, and print the store that had the lowest revenue. For example, the program user may want to determine the average revenue of all restaurants in Alaska and then determine the average revenue of all restaurants in Michigan. To accomplish this, we will have a menu of options the user can choose from, as described below.
The first thing your main program will need to do is prompt the user for a CSV file name so that you can read the data pertaining to the restaurants. Your prompt must be exactly Enter the filename of the file containing restaurants data: (with a newline following the colon). You then need to read the file into the program so that the data can be used for the analyses. You do not have to worry about a user inputting an incorrect file name for the purposes of this project. In the real world, you might expect that there are not Sparty Burger restaurants of each style in every state. However, for simplicity in this project, you may assume that there is at least one restaurant of each style in every state.
Provided Input Files
An input CSV file with 1000 rows of data about restaurants is provided for you to use, and where most of the visible test cases will come from. The example file is named “Restaurants.csv”. The following are the first ten lines of this file:
id,state,style,revenue
985440,NV,dine in,247915.40
503958,KY,dine in,172806.17
894772,SD,dine in,209374.65
541001,HI,dine in,189545.15
142450,ID,dine in,243740.94
371493,MS,dine in,252821.10
636110,WA,dine in,156765.93
609532,AK,dine in,383282.52
524604,OK,express,322564.13
The first row is a header row and has the headings for what the items in each column represent. You can (and should) download this file and look at it with notepad or excel to see what the data looks like.
There is another file provided called TestFileRestaurants.csv which contains data of the same format, but only has 15 restaurants from 3 states. This is the file you should use initially so you can manually compute what the answers should be without relying on what the test cases are telling you should be your output. This is a much more realistic reflection of programming in real life. You need to try your program on some sample data to make sure it is computing things correctly – usually there will be no one to tell you if it’s right or wrong unless you verify it yourself.
In order to encourage you to do this kind of testing, the majority of the test cases will not be released right away. You should focus on getting your menus and loop structure correct, similar to what you did in project 2, and then use the test file to see if you are computing the correct values. The additional test cases will be released after 1 week.
There is a third file that your program will also be tested with that you can not download. This is to ensure that your program will work no matter what the filename, and no matter what the data is inside that file. This third file will follow the same format as the other two.
Menu
You will need to print out a menu where the user inputs which option they want. You may want to put this in a function, but it is not required that you do so.
The menu should be exactly as follows (the menu always prints a blank line first, and there is a newline after the Enter selection 1-6: prompt):
(1) Get the number of restaurants by state
(2) Get the number of restaurants by style
(3) Get the average revenue of restaurants by state
(4) Get the average revenue of restaurants by restaurant style
(5) Print restaurant with lowest revenue
(6) Exit
Enter a selection 1-6:
If the user enters an invalid menu selection (including a non-numeric input, or a number outside of the valid range), your program should not crash, but the function should print the message Invalid selection – must be a number from 1 to 6, display the menu again, and prompt the user for a valid selection. Hint: Think back to how you handled continuous prompting for project 2.
In the main program,
If the user selects options 1 or 3, the program will then prompt the user for a state and expects the input to be a two-character state abbreviation. State abbreviations are two capital letters but your program should be able to recognize the state abbreviation regardless of the character’s case. For instance mi, MI, Mi, and mI should all equate to the state abbreviation for Michigan. The prompt should be exactly
Enter a 2 letter state abbreviation, or ‘US’ for all restaurants in the U.S.:
(with a newline following the colon). The program will call a function for each of these menu selections and use the selected state as an argument to the function. If the user enters an unexpected input for the state, you should output the message
x is not a valid state abbreviation
(where x is the invalid string exactly as entered) and continue prompting the user until they provide a valid state abbreviation. A list of valid state abbreviations will be provided for you to use to check if the user input is a proper state abbreviation. Once the function returns, you will print an appropriate message such as
There are 24 Sparty Burger Restaurants in MI
or
The average revenue in MI is $25000.00
If the user selects options 2 or 4, the program should similarly prompt the user for a restaurant style. The prompt should be exactly
Enter the restaurant style, or ‘any’ for all styles:
(with a newline following the colon). Valid styles are “dine in”, “express”, and “truck”. Note how all of the styles are in all lowercase. The program should be able to identify these styles regardless of the letter cases in the input string. For instance Truck, TRUCK, tRuck, and any other variation of letter case should still evaluate as being truck. If the user enters an unexpected input for the style, you should output the message
x is not a valid restaurant style
(where x is the invalid string exactly as they entered it) and continue prompting the user until they provide a valid restaurant style. Again, when the function returns you should print out an appropriate message such as
There are 55 Sparty Burger truck style Restaurants
or
The average revenue of truck style restaurants is $25000.00
Average revenue should be displayed as dollars and cents. The restaurant style should be displayed in lower case.
Finally, selection 5 does not require any additional input – it looks through the entire list of restaurants for the one with the lowest revenue, regardless of state or restaurant style.
In addition to the valid selections for state abbreviations and the selections for restaurant style, the string ‘US’ should be a valid selection for the state, and ‘any’ should be a valid selection for restaurant style as well. The ‘US’ selection for the state will allow the program to search through the restaurants of all states and the ‘any’ selection allows the program to search through the restaurants of all styles.
Creating your dictionary
As you read in all of the lines in the file, you will create a dictionary of the data that you can use throughout the program. We are interested in various restaurants and the information associated with each one, so we will want to use unique information pertaining to each restaurant as the keys to the dictionary. For values, there’s more than one piece of information associated with each restaurant. You need to make the values in the dictionary a list containing that information, on the order it was given in the file. If you do not create your dictionary properly you will not pass the unit tests. Remember that the csv file contains a header row, which should not be included in the dictionary. Also note that when reading a csv file, everything comes in as a string (just like all input in Python), so think about which data elements need to be something other than string.
Required Functions
You will need to define and implement the following functions:
def count_by_state(parameter1, parameter2) – This function requires two parameters; the first is the dictionary of restaurants info, and the second is a string representing the state that we are interested in. The function will return an int value which represents the number of restaurants in the specified state. For example, if my dictionary is named Restaurants, calling the function using the code count_by_state(Restaurants, ‘MI’) would return the number of restaurants in Michigan.
def count_by_style(parameter1, parameter2) – This function requires two parameters; the first is the dictionary of restaurants’ info, and the second is a string representing the style of restaurant we are interested in. The function will return an int value which represents the number of restaurants of the specified style. For example, if my dictionary is named Restaurants, calling the function using the code count_by_style(Restaurants, ‘truck’) would return the number of restaurants that are food trucks.
def avg_by_state(parameter1, parameter2) – This function requires two parameters; the first is the dictionary of restaurants’ info, and the second is a string representing the state that we are interested in. The function will return a float value which represents the average revenue generated by the restaurants in the specified state. For example, if my dictionary is named Restaurants, calling the function using the code avg_by_state(Restaurants, ‘CO’) would return the average revenue of the restaurants in Colorado.
def avg_by_style(parameter1, parameter2) – This function requires two parameters; the first is the dictionary of restaurants’ info, and the second is a string representing the style of restaurants we are interested in. The function will return a float value that represents the average revenue generated by the restaurants of the specified style. For example, if my dictionary is named Restaurants, calling the function using the code avg_by_type(Restaurants, ‘express’) would return the average revenue of the restaurants that are express style restaurants.
def print_lowest_revenue(parameter1) – this function requires as its parameter the dictionary of restaurants info. The function will print out the information of the restuarant with the lowest, showing the restaurant ID, the state, the style, and the revenue like the following example:
Lowest Revenue: Restaurant 317298 in TX, express style, had $2445.99
Additional suggestion: You may find it easier to create a function to display the user menu. This may also help you minimize the number of lines of code you must copy to generate the menu wherever you need it in your program.
NOTE Checkpoint 1 requires passing tests that read the file, print your menu and accept input. However, you should also focus on building your dictionary during this week prior to checkpoint 1’s due date. Checkpoint 2 requires passing tests that require your function definitions be present. You do not need to implement the functions, and they do not need to work correctly in order to pass these test cases. So you should create function stubs for your functions (see zyBooks section 11.6) and fill in the details later. Warning! Even though you could pass the checkpoints with only function stubs, we strongly recommend you attempt to implement the details of at least one function before the checkpoint is due so you don’t run out of time in the following weeks.
Remember that your program needs to work with any file that follows the same format, even if it contains different data, and some of the hidden test cases will use an alternate file that you will not be able to see. Also, remember that the starter code contains several lists of data that will mimic the lists that will result when you ultimately read in your data file. You can use these to start the code that will build your dictionary and implement your functions. They will work the same regardless of where the data originally came from.

Categories
Python

This project includes several files, but all of your changes will be made to the

This project includes several files, but all of your changes will be made to the first four: scheme.py, scheme_reader.py, questions.scm, and tests.scm. You can download all of the project code as a zip archive.
Submit the project using submit proj4. The only files you are required to submit are scheme.py, scheme_reader.py, questions.scm, and tests.scm.
Project 4: A Scheme Interpreter
Eval calls apply,
which just calls eval again!
When does it all end?Introduction
In this project, you will develop an interpreter for a subset of the Scheme language. As you proceed, think about the issues that arise in the design of a programming language; many quirks of languages are the byproduct of implementation decisions in interpreters and compilers.
You will also implement some small programs in Scheme. Scheme is a simple but powerful functional language. You should find that much of what you have learned about Python transfers cleanly to Scheme as well as to other programming languages. To learn more about Scheme, you can read the original Structure and Interpretation of Computer Programs online for free. Examples from chapters 1 and 2 are included as test cases for this project. Language features from Chapters 3, 4, and 5 are not part of this project, but of course you are welcome to extend your interpreter to implement more of the language. Since we only include a subset of the language, your interpreter will not match exactly the behavior of other interpreters such as STk.
The project concludes with an open-ended graphics contest that challenges you to produce recursive images in only a few lines of Scheme. As an example of what you might create, the picture above abstractly depicts all the ways of making change for $0.50 using U.S. currency. All flowers appear at the end of a branch with length 50. Small angles in a branch indicate an additional coin, while large angles indicate a new currency denomination. In the contest, you too will have the chance to unleash your inner recursive artist.
This project includes several files, but all of your changes will be made to the first four: scheme.py, scheme_reader.py, questions.scm, and tests.scm. You can download all of the project code as a zip archive.
scheme.pyThe Scheme evaluator
scheme_reader.pyThe Scheme syntactic analyzer
questions.scmA collection of test cases written in Scheme
tests.scmA collection of test cases written in Scheme
scheme_tokens.pyA tokenizer for scheme
scheme_primitives.pyPrimitive Scheme procedures
scheme_test.pyA testing framework for Scheme
scheme_grader.pyA suite of tests for the project
ucb.pyUtility functions
autograder.pyUtility functions for grading
Logistics
This is a two-part, two-person project. All questions are labeled sequentially, but some are designated for certain people by a prefix of their letter (A or B). Both partners should understand the solutions to all questions.
In the first part, you will develop the interpreter in stages:
Reading Scheme expressions
Primitive procedure calls
Symbol evaluation and definition
Lambda expressions and procedure definition
Calling user-defined procedures
Evaluation of various special forms
In the second part, you will implement Scheme procedures that are similar to some exercises that you previously completed in Python.
There are 27 possible correctness points and 3 composition points. The composition score in this project will evaluate the clarity of your code and your ability to write tests that verify the behavior of your interpreter.
Submit the project using submit proj4. The only files you are required to submit are scheme.py, scheme_reader.py, questions.scm, and tests.scm.
The Scheme Language
Before you begin working on the project, review what you have learned in lecture about the Scheme language in Section 3.2 of Composing Programs.
Read-Eval-Print. The interpreter reads Scheme expressions, evaluates them, and prints the results.
scm> 2
2
scm> (((lambda (f) (lambda (x) (f f x)))
(lambda (f k) (if (zero? k) 1 (* k (f f (- k 1)))))) 5)
120
The starter code for your Scheme interpreter in scheme.py can successfully evaluate the first expression above, since it consists of a single number. The second (a computation of 5 factorial) will not work just yet.
Load. Our load procedure differs from standard Scheme in that we use a symbol for the file name. For example, to load tests.scm, evaluate the following call expression.
scm> (load ‘tests)
Symbols. Unlike some implementations of Scheme, in this project numbers and boolean values cannot be used as symbols. Also, symbols are always lowercased.
scm> (define 2 3)
Traceback (most recent call last):
0 (#define 2 3)
Error: bad argument to define
scm> ‘Hello
hello
Turtle Graphics. In addition to standard Scheme procedures, we include procedure calls to the Python turtle package. You can read the turtle module documentation online.
Note: The turtle Python module may not be installed by default on your personal computer. However, the turtle module is installed on the instructional machines. So, if you wish to create turtle graphics for this project (i.e. for the contest), then you’ll either need to setup turtle on your personal computer or use university computers.
Development
The tests.scm file contains a long list of example Scheme expressions and their expected values.
(+ 1 2)
; expect 3
(/ 1 0)
; expect Error
You can compare the output of your interpreter to the expected output by running scheme_test.py.
python3 scheme_test.py
For the example above, scheme_test.py will evaluate (+ 1 2) using your code in scheme.py, then output a test failure if 3 is not returned as the value. The second example tests for an error (but not the specific error message).
Only a small subset of tests are designated to run by default because tests.scm contains an (exit) call near the beginning, which halts testing. As you complete more of the project, you should move or remove this call. Note that your interpreter doesn’t know how to exit until Problems 3 and 4 are completed; all tests will run until then.
Important: As you proceed in the project, add new tests to the top of tests.scm to verify the behavior of your implementation. Your composition score for this project will depend on whether or not you have tested your implementation in ways that are different from the autograder.
As always, you can run the doctests for the project.
python3 -m doctest scheme.py scheme_reader.py
You can also run the autograder tests.
python3 scheme_grader.py
python3 scheme_grader.py -q 1
Debugging. Try using the trace decorator from the ucb module to follow the path of execution in your interpreter.
Exceptions. As you develop your Scheme interpreter, you may find that Python raises various uncaught exceptions when evaluating Scheme expressions. As a result, your Scheme interpreter will halt. Some of these may be the results of bugs in your program, and some may be useful indications of errors in user programs. The former should be fixed (of course!) and the latter should be handled, usually by raising a SchemeError. All SchemeError exceptions are handled and printed as error messages by the read_eval_print_loop function in scheme.py. Ideally, there should never be unhandled Python exceptions for any input to your interpreter.
Running Your Scheme Interpreter
To run your Scheme interpreter in an interactive mode, type:
python3 scheme.py
You can use your Scheme interpreter to evaluate the expressions in an input file by passing the file name as a command-line argument to scheme.py: python3 scheme.py tests.scm
Currently, your Scheme interpreter can handle a few simple expressions, such as: scm> 1
1
scm> 42
42
scm> #t
True
To exit the Scheme interpreter, issue either Ctrl-c or Ctrl-d or evaluate the exit procedure: scm> (exit)
The Reader
The function scheme_read in scheme_reader.py parses a Buffer (buffer.py) instance that returns valid Scheme tokens on invocations of current and pop methods. This function returns the next full Scheme expression in the src buffer, using this representation:
Scheme Data TypeOur Internal Representation
NumbersPython’s built-in int and float data types.
SymbolsPython’s built-in string data type.
Booleans (#t, #f)Python’s built-in True, False values.
PairsThe Pair class, defined in scheme_reader.py.
nilThe nil object, defined in scheme_reader.py.
Problem 1 (1 pt). Complete the scheme_read function in scheme_reader.py by adding support for quotation. This function dispatches on the type of the next token:
If the next token in src is the string “nil”, return the nil object. (provided)
If the next token is not a delimiter, then it is self-evaluating. Return it. (provided)
If the current token is a single quote (such as the first character of ‘bagel), then return a quote special form (such as (quote bagel)).
If the current token is a left parenthesis “(“, return the result of read_tail. (provided)
Problem 2 (2 pt). Complete the read_tail function in scheme_reader.py by adding support for dotted lists. A dotted list in Scheme is not necessarily a well-formed list, but instead has an arbitrary second attribute that may be any Scheme value.
The read_tail function expects to read the rest of a list or dotted list, assuming the open parenthesis of that list has already been popped by scheme_read.
Consider the case of calling scheme_read on input “(1 2 . 3)”. The read_tail function will be called on the suffix “1 2 . 3)”, which is
the pair consisting of the Scheme value 1 and the value of the tail “2 . 3)”, which isthe pair consisting of the Scheme value 2 and the Scheme value 3.
Thus, read_tail would return Pair(1, Pair(2, 3)).Hint: In order to verify that only one element follows a dot, after encountering a ‘.’, read one additional expression and then check to see that a closing parenthesis follows.
To verify that your solutions to Problem 1 and 2 work correctly, run the doctests for scheme_reader.py and test your parser interactively by running,
# python3 scheme_reader.py
read> 42
42
read> ‘(1 2 3)
(quote (1 2 3))
read> nil
()
read> ‘()
(quote ())
read> (1 (2 3) (4 (5)))
(1 (2 3) (4 (5)))
read> (1 (9 8) . 7)
(1 (9 8) . 7)
read> (hi there . (cs . (student)))
(hi there cs student)
The Evaluator
All further changes to the interpreter will be made in scheme.py. For each question, add a few tests to the top of tests.scm to verify the behavior of your implementation. In the implementation given to you, the scheme_eval function is complete, but few of the functions or methods it uses are implemented. In fact, the evaluator can only evaluate self-evaluating expressions: numbers, booleans, and nil.
Problem 3 (2 pt). Implement apply_primitive, which is called by scheme_apply. Primitive procedures are applied by calling a corresponding Python function that implements the procedure.
Scheme primitive procedures are represented as instances of the PrimitiveProcedure class, defined in scheme_primitives.py. A PrimitiveProcedure has two instance attributes:
fn is the Python function that implements the primitive Scheme procedure.
use_env is a boolean flag that indicates whether or not this primitive procedure will expect the current environment to be passed in as the last argument. The environment is required, for instance, to implement the primitive eval procedure.
To see a list of all Scheme primitive procedures used in the project, look in the scheme_primitives.py file. Any function decorated with @primitive will be added to the globally-defined _PRIMITIVES list.
The apply_primitive function takes a PrimitiveProcedure instance, a Scheme list of argument values, and the current environment. Your implementation should:
Convert the Scheme list to a Python list of arguments.
If the procedure.use_env is True, then add the current environment env as the last argument.
Call procedure.fn on those arguments (hint: use * notation).
If calling the function results in a TypeError exception being thrown, then raise a SchemeError instead.
The doctest for apply_primitive should now pass. However, your Scheme interpreter will still not be able to apply primitive procedures, because your Scheme interpreter still doesn’t know how to look up the values for the primitive procedure symbols (such as +, *, and car).
Problem 4 (2 pt) Implement the lookup method of the Frame class. It takes a symbol (Python string) and returns the value bound to that name in the first frame of the environment in which it is found. A Frame represents an environment via two instance attributes:
bindings is a dictionary that maps Scheme symbol keys (represented as Python strings) to Scheme values.
parent is the parent Frame instance. The parent of the Global Frame is None.
Your lookup implementation should,Return the value of a symbol in self.bindings if it exists.
Otherwise, lookup that symbol in the parent if it exists.
Otherwise, raise a SchemeError. (provided)
After you complete this problem, you should be able to evaluate primitive procedure calls, giving you the functionality of the Calculator language and more.
scm> +
#[primitive]
scm> (+ 1 2)
3
scm> (* 3 4 (- 5 2) 1)
36
scm> (odd? 31)
True
Problem A5 (1 pt). There are two missing parts in the do_define_form function, which handles the (define …) special forms. Implement just the first part, which binds names to values but does not create new procedures. do_define_form should return the name after performing the binding.
scm> (define tau (* 2 3.1415926))
tau
You should now be able to give names to values and evaluate symbols to those values.
scm> (define x 15)
x
scm> (define y (* 2 x))
y
scm> y
30
scm> (+ y (* y 2) 1)
91
scm> (define x 20)
x
scm> x
20
Problem B6 (1 pt). Implement the do_quote_form function, which evaluates the quote special form. Once you have done so, you can evaluate quoted expressions.
scm> ‘hello
hello
scm> ‘(1 . 2)
(1 . 2)
scm> ‘(1 (2 three . (4 . 5)))
(1 (2 three 4 . 5))
scm> (car ‘(a b))
a
scm> (eval (cons ‘car ‘(‘(1 2))))
1
At this point in the project, your Scheme interpreter should be be able to support the following features:
Evaluate atoms, which include numbers, booleans, nil, and symbols,
Evaluate the quote special form,
Evaluate lists,
Define symbols, and
Call primitive procedures, such as (+ (- 4 2) 5)
User-Defined Procedures
User-defined procedures are represented as instances of the LambdaProcedure class, defined in scheme.py. A LambdaProcedure instance has three instance attributes:
formals is a Scheme list of the formal parameters (symbols) that name the arguments of the procedure.
body is a single Scheme expression; the body of the procedure.
env is the environment in which the procedure was defined.
Problem 7 (2 pt). First, implement the begin special form, which includes a list of one or more sub-expressions that are each evaluated in order. The value of the final sub-expression is the value of the begin expression.
scm> (begin (+ 2 3) (+ 5 6))
11
scm> (begin (display 3) (newline) (+ 2 3))
3
5
scm> (begin (print 3) ‘(+ 2 3))
3
(+ 2 3)
Hint: When scheme_eval evaluates one of the LOGICAL_FORMS in scheme.py, it calls scheme_eval on the returned value. Take care that your Scheme interpreter doesn’t inadvertently call scheme_eval on the same value twice, or else you might have the following incorrect behavior:
scm> (begin 30 ‘hello)
Error: unknown identifier: hello
Problem 8 (2 pt). Implement the do_lambda_form method, which creates LambdaProcedure instances by evaluating lambda expressions. While you cannot call a user-defined procedure yet, you can verify that you have read the procedure correctly by evaluating a lambda expression.
scm> (lambda (x y) (+ x y))
(lambda (x y) (+ x y))
In Scheme, it is legal to have function bodies with more than one expression. In order to implement this feature, your do_lambda_form should detect when the body of a lambda expression contains multiple expressions. If so, then do_lambda_form should place those expressions inside of a (begin …) form, and use that begin expression as the body: scm> (lambda (y) (print y) (* y 2))
(lambda (y) (begin (print y) (* y 2)))
Problem A9 (1 pt). Currently, your Scheme interpreter is able to define user-defined procedures in the following manner:
scm> (define f (lambda (x) (* x 2)))
f
However, we’d like to be able to use the shorthand form of defining procedures: scm> (define (f x) (* x 2))
f
Modify the do_define_form function so that it correctly handles the shorthand procedure definition form above. Make sure that it can handle multi-expression bodies. Hint: construct a lambda expression and evaluate it with do_lambda_form.
Once you have completed this problem, you should find that defined procedures evaluate to lambda procedures.
scm> (define (square x) (* x x))
square
scm> square
(lambda (x) (* x x))
Problem 10 (2 pt). Implement the make_call_frame method of the Frame class, which:
Creates a new Frame instance, the parent of which is self. (provided)
Binds formal parameters to their corresponding argument values.
Raises a SchemeError if make_call_frame receives a different number of formal parameters and arguments.
Problem B11 (1 pt). Implement the check_formals function to raise an error whenever the Scheme list of formal parameters passed to it is invalid. Raise a SchemeError if the list of formals is not a well-formed list of symbols or if any symbol is repeated. (Hint: The symbol? procedure in scheme_primitives.py returns whether a value is a Scheme symbol.)
Problem 12 (2 pt). Implement scheme_apply to correctly apply user-defined LambdaProcedure instances. (The case of MuProcedures is handled later in the project). It should:
Create a new Frame, with all formal parameters bound to their argument values.
Evaluate the body of procedure in the environment represented by this new frame.
Return the value of calling procedure.
After you complete scheme_apply, user-defined functions (and lambda functions) should work in your Scheme interpreter. Now is an excellent time to revisit the tests in tests.scm and ensure that you pass the ones that involve definition (Sections 1.1.2 and 1.1.4). You should also add additional tests of your own at the top of tests.scm to verify that your interpreter is behaving as you expect.
Special Forms
Logical special forms include if, and, or, and cond. These expressions are special because not all of their sub-expressions may be evaluated.
In Scheme, only #f (also known as false or False) is a false value. All other values are true values. You can test whether a value is a true value or a false value using the provided Python functions scheme_true and scheme_false, defined in scheme_primitives.py.
Problem A13 (1 pt). Implement do_if_form so that if expressions are evaluated correctly. This function should return either the second (consequent) or third (alternative) expression of the if expression, depending on the value of the first (predicate) expression.
scm> (if (= 4 2) true false)
False
scm> (if (= 4 4) (* 1 2) (+ 3 4))
2
It is legal to pass in just two expressions to the if special form. In this case, you should return the second expression if the first expression evaluates to a true value. Otherwise, return the special okay value, which represents an undefined value.
scm> (if (= 4 2) true)
okay
Problem B14 (2 pt). Implement do_and_form and do_or_form so that and and or expressions are evaluated correctly.
The logical forms and and or are short-circuiting. For and, your interpreter should evaluate each sub-expression from left to right, and if any of these evaluates to False, then False is returned. If all but the last sub-expressions evaluate to true values, return the last sub-expression from do_and_form.
For or, evaluate each sub-expression from left to right. If any evaluates to a true value, then quote that value and return it. These return values must be quoted because they are evaluated in scheme_eval. If all but the last sub-expression evaluate to false, return the last sub-expression from do_or_form without quoting it.
scm> (and)
True
scm> (or)
False
scm> (and 4 5 6)
6 ; all operands are true values
scm> (or 5 2 1)
5 ; 5 is a true value
scm> (and #t #f 42 (/ 1 0))
False ; short-circuiting behavior of and
scm> (or 4 #t (/ 1 0))
4 ; short-circuiting behavior of or
Problem A15 (1 pt). Implement do_cond_form so that it returns the first result sub-expression corresponding to a true predicate (or else). Your implementation should match the following examples and the additional tests in tests.scm.
scm> (cond ((= 4 3) ‘nope)
((= 4 4) ‘hi)
(else ‘wait))
hi
scm> (cond ((= 4 3) ‘wat)
((= 4 4))
(else ‘hm))
True
scm> (cond ((= 4 4) ‘here 42)
(else ‘wat 0))
42
For the last example, where the body of a cond case has multiple expressions, you might find it helpful to replace cond-bodies with multiple expression bodies into a single begin expression, i.e., the following two expressions are equivalent. (cond ((= 4 4) ‘here 42))
(cond ((= 4 4) (begin ‘here 42)))
If the body of a cond case is empty, then do_cond_form should quote the value of the predicate and return it, if the predicate evaluates to a true value.
scm> (cond (12))
12
scm> (cond ((= 4 3))
(‘hi))
hi
The value of a cond is undefined if there are no true predicates and no else. In such a case, do_cond_form should return okay.
Problem A16 (2 pt). The let special form introduces local variables, giving them their initial values. For example,
scm> (define x ‘hi)
x
scm> (define y ‘bye)
y
scm> (let ((x 42)
(y (* 5 10)))
(list x y))
(42 50)
scm> (list x y)
(hi bye)
Implement the do_let_form method to have this effect and test it, by adding test cases to the top of tests.scm. Make sure your let correctly handles multi-expression bodies: scm> (let ((x 42)) x 1 2)
2
The let special form is equivalent to creating and then calling a lambda procedure. That is, the following two expressions are equivalent:
(let ((x 42) (y 16)) (+ x y))
((lambda (x y) (+ x y)) 42 16)
Thus, a let form creates a new Frame (containing the let bindings) which extends the current environment and evaluates the body of the let with respect to this new Frame. In your project code, you don’t have to actually create a LambdaProcedure and call it. Instead, you can create a new Frame, add the necessary bindings, and evaluate the expressions of the let body in this new environment.Problem B17 (2 pt). Implement do_mu_form to evaluate the mu special form, a non-standard Scheme expression type. A mu expression is similar to a lambda expression, but evaluates to a MuProcedure instance that is dynamically scoped. The MuProcedure class has been provided for you.
Additionally, complete scheme_apply to call MuProcedure procedures using dynamic scoping. Calling a LambdaProcedure uses lexical scoping: the parent of the new call frame is the environment in which the procedure was defined. Calling a MuProcedure created by a mu expression uses dynamic scoping: the parent of the new call frame is the environment in which the call expression was evaluated. As a result, a MuProcedure does not need to store an environment as an instance attribute. It can refer to names in the environment from which it was called.
scm> (define f (mu (x) (+ x y)))
f
scm> (define g (lambda (x y) (f (+ x x))))
g
scm> (g 3 7)
13
Your Scheme interpreter implementation is now complete. You should have been adding tests to the top of tests.scm as you did each problem. These tests will be evaluated as part of your composition score for the project.
Part 3: Write Some Scheme
Not only is your Scheme interpreter itself a tree-recursive program, but it is flexible enough to evaluate other recursive programs. Implement the following procedures in Scheme in questions.scm.
Problem 18 (2 pt). Implement the merge procedure, which takes in a comparator and two sorted list arguments and combines them into one sorted list. A comparator is a function that compares two values. For example:
scm> (merge (merge > ‘(6 4 1) ‘(8 5 2))
(8 6 5 4 2 1)
Problem 19 (2 pt). Implement the list-partitions procedure, which lists all of the ways to partition a positive integer total into at most max-pieces pieces that are all less than or equal to a positive integer max-value. Hint: Define a helper function to construct partitions.
The number 5 has 4 partitions using pieces up to a max-value of 3 and a max-pieces of 4:
3, 2 (two pieces)
3, 1, 1 (three pieces)
2, 2, 1 (three pieces)
2, 1, 1, 1 (four pieces)
Problem 20 (2 pt). You have been given the definition to an abstract implementation of trees. Use it to implement tree-sums, which is a function that returns a list of all possible sums of nodes, when traversing from root to leaf. For example, the following tree when passed through tree-sums will return (20 19 13 16 11):
Problem 21 (0 pt). Implement the hax procedure that draws the following recursive illustration when passed two arguments, a side length d and recursive depth k. The example below is drawn from (hax 200 4).
To see how this illustration is constructed, consider this annotated version that gives the relative lengths of lines of the component shapes in the figure.
Extra Credit
Problem 22 (3 pt). Complete the function scheme_optimized_eval in scheme.py. This alternative to scheme_eval is properly tail recursive. That is, the interpreter will allow an unbounded number of active tail calls in constant space.
Instead of recursively calling scheme_eval for tail calls and logical special forms, and let, replace the current expr and env with different expressions and environments. For call expressions, this change only applies to calling user-defined procedures.
Once you finish, uncomment the line scheme_eval = scheme_optimized_eval in scheme.py.
Extra for Experts
We have implemented a significant subset of Scheme in this project, but our interpreter can be extended with more features by following the extension instructions.