CS5314: Concepts of Programing Languages
Spring 2016
Assignment II: Higher Order Functions in Scheme
Due Date: April 13, 2016

Functional programming is at its core a computational paradigm that consists solely of function definitions and function applications. Functions are "first class" meaning they can be values of variables, passed as parameters, and returned as the result of a function application. Higher order functions add power to the kinds of computations that can be accomplished in the purely functional progamming paradigm. Our project will give you experience with this paradigm, by having you design, code, and test a set of functions, including some higher order functions. Note: to get full credit for the assignment, some of your functions will have to be higher order (see section on grading).

Problem description - the data to be used. Suppose you are managing a sports team for your school, for example an intramural coed basketball team. We will use 2 different lists as input data for your set of functions. The first input list in this project concerns statistics for a set of teams, the Team_record_list that records the wins and losses for each team for a season. The following BNF defines the syntax of this list:

Team_record_list --> ( T_record_seq ) 
T_record_seq --> (Team_record) | (Team_record) T_record_seq 
Team_record -->  id int1 int2

where id is the team name, int1 is number of the wins and int2 is number of the losses this season for this team. For example, this is a Team_record_list:
((cardinals 5 10) (bluejays 15 3)).

The second input list for the project describes the scoring record for each player on a team in a nested Scheme list. For example, (cardinals (james (10 15 3)) means that the player james on the cardinals team played 3 games in which he scored 10, 15, 3 points repectively. The Team_scoring_list will be a list of such sublists, for example:

( (cardinals (mary (2 14)) (james (10 15 3))) (crows (joe (2)) (sue (5 10 15 20)) (frank (5 15))) )

The BNF describing the structure of the Team_scoring_list in which { (, ), int, id } are all terminal symbols, is shown below:

Team_scoring_list --> ( T_score_seq ) 
T_score_seq --> (id PL_score_seq) | (id PL_score_seq) T_score-seq 
PL_score_seq --> ( id (Scores) ) 
Scores --> int | int Scores

where in T_score_seq, id is a terminal that is the team's name, and in PL_score_seq, id is a terminal that is the player's name with the list Scores that are the player's scoring record for the season.

Functions to be written.

Getting organized: Since there are several Scheme functions to define, first figure out which input data structure is the actual input for each of the functions. It might be easier to complete the functions that use the same input list first, before starting to deal with the next input list structure, but that is up to you. Remember you can define any helper functions you need, as named functions or as lambda expressions, but you have to include all such commented definitions in your final Scheme project submission so your functions can be run.

To use test-driven development with Scheme, the DrRacket environment has been designed with a check-expect function that allows you to give the system a function application on a specific input, and the return value expected, so that DrRacket can check to see if the expected answer is returned. Here is how you would write this:

; function-name: input1-type input2-type -> output-type
; A brief description of the purpose of the function, including weirdness
(define (function-name input1 input2)
(check-expect (function-name example-input1_1 example-input2_1) expected-result1)
(check-expect (function-name example-input1_2 example-input2_2) expected-result2)
(check-expect (function-name example-input1_3 example-input2_3) expected-result3)
(check-expect (function-name example-input1_4 example-input2_4) expected-result4)

This useful website contains information about our version of DrRacket and lists many built-in functions and operations.

Also, please recall that typing Control-i in DrRacket will re-indent your code for you (i.e., sort of a pretty-print that shows syntactic nesting) which helps to find syntax errors.

Grading: The project is due on Weds, April 13th. As usual there will be a 24 hour late turn-in period, but recall that late projects have a 20% reduction in the max grade they can achieve. Your functions will be graded on how they satisfy the specifications above, and should include comments in the code to aid reader understanding. The main point of this project is to learn how to use the power of higher order functions in Scheme. Here is a webpage to consult as to the built-in higher order functions available for your use in our version of DrRacket.

The 150 points for this project will be apportioned in this manner (including some partial credit in some categories):

Remember that you are NOT supposed to write these functions to do complete error checking on the inputs to be used; just assume that the input they receive will be of appropriate type (e.g., atom, number or list).

One fine point: the topThree and topthreeScorers functions actually require in their specification that there be at least 3 teams and 3 players (respectively). Suggestion: write these functions assuming the data list(s) will be long enough; once they work with that assumption you can consider implementing error checking (in case there is not enough data to satisfy the functionality defined). Note: it will be worth more to complete all the function definitions, than do accomplish these 2 error checks and perhaps not complete all the functions, so use your time wisely.

Test data about the players and teams with answers expected from a correct implementation will be made available on this webpage here.

If you define 'helper' functions, they will have to include comments as to their functionality, and you will have to design test data for them. For example, if the incrbyone function was a helper function, then you would have to turn in the following code that includes a few sample commented function applications to show how the function can be applied. This will allow us to easily execute your function definition in DrRacket for grading and should allow for some partial credit in case not all of the functions work correctly.

(define (incrbyone x) (+ 1 x)) ;increments its parameter by 1
(incrbyone 5) ; answer is 6
(incrbyone (* 4 2)) ; answer is 9

Recall the informal instructions on installing and using DrRacket.

Final submission. We expect you will turn in a single file containing your complete set of commented function definitions used in your solution through WEB-Cat. This file should also contain sample function applications for all of your helper functions; these function applications should be located in the file immediately after the helper function definition. Hint: write your helper functions as you need them and test them with appropriate function applications. Later, you can comment out these function applications using ";" while testing your other code.

Last updated 9:58pm on March 30, 2016 BGR

12:50pm 3/30 Major changes/additions: rule for Team_record; function description for: sortedTeamRatio, topThree, averageScorePerPlayer, maxScore, topThreeScorers; using DrRacket automatic re-indent; test data section.