Wright
State University
Department of Computer Science and
Engineering
CS7100 Comparative Languages
Fall 2025
Assignment 1
Prasad
Scheme
+ Functional Programming Refresher
- NOTE: Choose language R5RS
in Racket IDE for developing and running Scheme programs. Leave your
programs as
generic as possible, that is, if it is naturally applicable to symbols,
strings and numbers, then do not needlessly constrain them to
work just for symbols. Some of these functions must work on
nested lists as specified. Test your functions thoroughly, especially
on edge cases as the examples given are not guaranteed to cover all
cases.
- You
must use the function name specified in the questions.
- The Scheme lectures covering the Comparative Languages prerequsite course background are adequate for doing this assignment.
Recursive
Definitions (For pacing yourself:
September 18,
2025; 11:59pm)
1. Write
a 2-argument definition for the function remove-12 that removes the first two (two leftmost) top-level occurrences of a given item from a
(linear) list of items.
E.g.,
(remove-12
'c '(a b c d c x c)) = (a
b d x c)
(remove-12
'dog '(my dog loves dog food))
= (my
loves food)
(remove-12
3 '( 3 1 2 3 5 3 6)) =
(1 2 5 3 6)
(remove-12
'food '( water))
= (water)
You
are allowed to use more than one function to accomplish your task as
long as you use recursive definitions and function composition
operation. You should use car, cdr, cons, null?, eq? and cond for uniformity. (While if-construct is equivalent to cond-construct, the latter enables better organization of the code.) You should not use let-constructs and imperative constructs such as set!.
2.
Given
an arithmetic expression in prefix form built using +, *, variables
(as symbols) and numbers, write a recursive definition for
the 1-argument funtion infix
that transforms the prefix expression into the equivalent infix form. Note
that variables and numbers constitute the base cases, and the
parenthesized expressions involving the binary operators constitute the
inductive cases. E.g.,
(infix '5) = 5
(infix 'x) = x
(infix '(+ (* 1 2) (+ x y))) = ((1 * 2) + (x + y))
(infix '(* z 6)) = (z * 6)
You may assume that input expression is syntactically valid. You are not allowed to use any auxilliary function or use let-construct to force you to use the recursive structure.
3. Write
a function lswapper(s1
s2 slist) using higher order function map that returns
a linear list similar to slist,
but with all occurrences of s1
replaced by s2
and all occurrences of s2
replaced by s1. E.g.,
(lswapper 'x 'y '(a b n
m)) = (a b n m)
(lswapper 'a 'c '(a b c d)) = (c b a d)
(lswapper 'b 'c '(a b c b)) = (a c b c)
You should not use any explicit recursion.
4. Write
a function count-if,
which takes a predicate p?
and a nested list ls,
and returns the number of occurrences of elements in ls that satisfy p?. E.g.,
(count-if
(lambda (x) (eq? 'z x)) '((f x) z (((z x c v z)
(y))))) = 3
(count-if
number? '((f x) y (((x z) x)))) = 0
(count-if
zero? '((f x) 0 (((x 0 z) x)))) =>>> throws an exception
The last call throws an exception because applying zero? to a non-number is a contract violation.
You are not allowed to define any auxilliary function or use let-construct.
Sample
"Well-documented" Definition
The
following example is for Intermediate-Student language of Racket. The
equivalent renditions for R5RS (Standard Scheme) are shown in asg1.ppt.
; HtDP book Exercise 5.1.2
; Develop the function chkgss. It consumes
two numbers,
guess and
target.
; Depending on how guess relates to target,
the function produces one of the following three answers:
;'TooSmall,
'Perfect, or
'TooLarge.
; CONTRACT: chkgss
:
number number -> { TooSmall, Perfect,
TooLarge }
; PURPOSE: chkgss takes two numbers - a guess and a
target, and
;
returns one of the symbol TooSmall, Perfect or TooLarge
;
depending on whether target is more, equal or less than guess
; CODE:
(define (chkgss guess target)
(cond [(> guess target) 'TooLarge ]
[(< guess target) 'TooSmall ]
[(= guess target) 'Perfect ]
)
)
; TEST CASES and EXPECTED OUTCOMES - multiple
alternatives given
;(in general, focus on boundary conditions and coverage)
(chkgss 7 5) "=" 'TooLarge
(eq?
(chkgss 5 5) 'Perfect)
(check-expect (chkgss 3 5) 'TooSmall)
What to turn in?
You can turn-in your well-documented solution including test cases (with good
coverage) and answers you obtain as comments in a single
runnable Racket file asg1.rkt
on Pilot under Dropbox > Assignment 1. Make sure that the file
is in
a form that one can add test calls to at the end and run it under
Racket IDE.