Language Assignment 1 Scheme Solution

Purpose




This assignment asks you to begin using a functional programming language named Scheme, which is a modern dialect of the venerable language Lisp. Lisp was designed by John McCarthy, at MIT, in 1958. Scheme was designed by Guy Steele and Gerald Sussman, at MIT, in 1975.







Submission




Homework is due at 11:59PM, Mountain Time, on the day it is due. Late work is not accepted. To submit your solution to an assignment, login to a lab computer, change to the directory containing the les you want to submit, and execute:







submit jbuffenb class assignment









For example:







submit jbuffenb cs101 hw1









The submit program has a nice man page.







Documentation




Scheme lecture slides are at:







pub/slides/slides-scheme.pdf





CS 354-2 (S20) LA1 (Jan 28 Tue)
2






Scheme is described in Section 11.3 of our textbook.




The onyx cluster has a Scheme interpreter, named Guile, the documentation of which can be viewed by:







info Guile Reference



2info R5RS










and demonstrated by:







pub/sum/scheme









This documentation, in HTML, is also at:







https://www.gnu.org/software/guile/docs/docs.html









The interactive interpreter also has online documentation, for some functions.




For example:







$ guile



 



Enter ‘,help’ for help.



scheme@(guile-user) ,d append



- Scheme Procedure: append . args



6




Return a list consisting of the



8elements the lists passed as




arguments.



10










11
(append ’(x)
’(y))
==
(x
y)
12
(append ’(a)
’(b c d))
==
(a
b c d)



(append ’(a (b)) ’((c))) == (a (b) (c))



14




Return a list consisting of the



elements the lists passed as



arguments.



18




(append ’(a b) ’(c . d)) == (a b c . d)



20
(append ’() ’a)
== a



scheme@(guile-user)






CS 354-2 (S20) LA1 (Jan 28 Tue)
3



Assignment




Write and fully demonstrate a function named super-duper, with this interface:







(super-duper source count)









The function returns a copy of the list source, with every element duplicated count times. If source is an atom, it is immediately returned, without dupli-cation.




For example:







(super-duper 123 1)



) 123



3




(super-duper 123 2)



) 123



6




(super-duper ’() 1)



) ()



9




(super-duper ’() 2)



) ()



12




(super-duper ’(x) 1)



) (x)



15




(super-duper ’(x) 2)



) (x x)



18




(super-duper ’(x y) 1)



) (x y)



21




(super-duper ’(x y) 2)



) (x x y y)



24




(super-duper ’((a b) y) 3)



) ((a a a b b b) (a a a b b b) (a a a b b b)



y y y)






CS 354-2 (S20) LA1 (Jan 28 Tue)
4






Of course, you can de ne other functions and call them from super-duper.




You are required to use only the pure subset of Scheme:




no side-e ecting functions, with an exclamation mark in their names (e.g., set-car! and set-cdr!)




no loops (e.g., do, foreach, and map)




Historically, students often want to use the built-in function append. There are several reasons why you should not use append:




It doesn’t really do what you want. Use cons. It is just a function. See:







1




2




pub/etc/append.scm




pub/etc/append1.scm






It does not make a copy of its arguments, as required by the assignment. Paraphrasing the reference manual: append doesn’t modify the given argu-ments, but the return value may share structure with the nal argument.




Test your solution thoroughly. The quality of your test suite will in uence your grade.




Finally, do not try to nd a solution on the Internet. You’ll possibly be asked to solve a similar problem on an exam, and if you have not developed a solution on your own, you will not be able to do so on the exam.