Scheming in Scheme
Register and submit here.
Revised 911. Corrected maximum bitstring length conflict. Reworded text related to zeropadding bit strings. Added clarification to the rotation operator.
Revised 916. Corrected three examples by correcting an operator typo replacingwithin the explanation of the XOR operator. Added parens to make syntactically valid expressions in the graph examples.
Revised 924. One line of the testOutput file was incorrect. Line 90 has been corrected in the testOutput file.
Bitstring Expression Language: 25 Points Description
You must write a Java program named Bitstrings that is executable directly from the commandline. This program must accept a commandline string denoting the name of a BITS file. A BITS file contains a list of BITExpressions, one per line. The Bitstrings program must read every BITexpression in the BITS file, evaluate the BITexpression, and print the results in the order they appear in the file.
Syntax of a BITExpression
1. A BITexpression involves operations on bitstrings. The syntax of a BITexpression is informally but rigorously defined below. a. A bitstring literal oneormore consecutive 0 s or 1 s is a BITexpression.
b. The word undefined is a BITexpression.
c. A single alphabetic character is a BITexpression. The character is a variable.
d. If E1 and E2 are BITexpressions then each of the following is a BITexpression. i. E1 E2
ii. E1 E2iii. E1 E2iv.! E1
v. E1
2. If E1 , E2 , and E3 are BITexpressions, and ENV is an environment,
a.ENV E1is a BITexpression.
An environment is a list of declaration of the formDECL1 DECL2 … DECLn
A declaration is of the formV E3where V is a single alphabetical character denoting a variable. Variable
V is associated with the value of E3 only in the context of E1 as long as the variable has not been redeclared within a subexpression of E1.
3. Additionally, for ease of coding, we impose the constraint that there is at least one space between any two consecutive language elements. For example, ! 1001 is not valid because there is no space between the bang ! and the parenthesis . However,! 1001is a valid BITexpression .
Semantics of a BITexpression
The following adhoc rules describe the semantics of a BITexpression.
1. There are only two kinds of values in this language: bitstrings and the word undefined.
2. Bitstrings have a maximum length of 2019 digits. If any literal or operation would produce a bitstring of length 2020 or greater, that
operation or literal produces the value undefined instead.
3. Any operation that operates on the value undefined produces the value undefined.
4. The value of a bitstring literal is itself except see 2 above.
5. The value of the word undefined is itself.
6. The value of a variable is the value associated with the variable in the closest containing environment. Any variable whose value is not
present in any containing environment has a value of undefined.
7. The value of the expressions given in the syntactic definitions of 1.d are obtained by application of an operator to the value of its
operands as defined below.
Gitlab
i. ii.
iii.
iv. v.
denotes the bitstring concatenation operator. For example,011 1 yields 0111.
denotes the bitwise exclusiveor operator. The exclusiveor operator is applied to each pair of corresponding digits in the two operands. For example,0101 0011 yields 0110. If the operands are both bitstrings and of unequal length, the shortest bitstring is implicitly zeropadded leftwards so that the two operands are of identical length.
denotes the bitstring zipper operator. The zipper operator interleaves the operand digits in the output. For example,111 1 yields 101011. If the operands are both bitstrings and of unequal length, the shortest bitstring is implicitly zeropadded leftwards so that the two operands are of identical length.
! denotes the bitstring negation operator. The negation operator inverts each digit in the bitstring. For example, ! 01011 yields 10100.
denotes the bitstring rotation operator. The rotation operator swaps consectuive pairs of digits in a bitstring. If the operand is of odd length, the operand is zeropadded leftwards by one digit prior to rotation. For example, the rotation of a bitstring of length five consisting of the digits D0D1D2D3D4 will produce the six digits D00D2D1D4D3. For a specific example,0111
yields 1011.
CS 421 : Programming LanguagesKenny Hunt
34491:ude.xalwu.sc:sptth
8. The value of a BITexpression that begins with an environment is the value of its rightmost operand such that all variables declared in the environment are replaced by their values wherever they occur in the operand. Environment expressions form a heirarchy of variable namespaces. Be careful that you handle these types of expressions correctly. For example, the expression a 1 b 0a b yields 10. This expression can be understood as meaning something like Let variable a be 1 and let variable b be 0 in the expressiona b. The expression a 1 b 0a b a b yields 00.
Examples
Coding Help
I recommend writing a class named Environment . This would likely be an extention of a Map class that also contains a Map the parent environment. When loooking up the value of a variable, you look in the environment and then recursively move up the chainofparents until you either find the variable or fail to find.
I recommend writing a class that generates a sequence of tokens from an input string. You can then scan through the tokens and process them oneatatime to evaluate an expression. The token stream should probably support something like a peekn function that gives the token that is nth ahead of the location you are presently at when processing the input stream.
By way of explanation, consider evaluating the BITexpression! 10 01 . You would write something like an evaluate TokenStream tsfunction that returns the result of evaluating the tokens in the stream. For this example, the token stream would initially be positioned at the beginning of a sequence of 8 tokens as illustrated in Figure 1 where the red triangle denotes the current location of the tokenstream cursor. The first token isfollowed by ! followed byand others.
Figure 1
The evaluate function first asks What type of expression am I evaluating?. The only possible answers are the ones listed in the syntactic description: a bitstring literal, undefined, a variable, an expression involving an operator, an environment expression. This question would be answered by peeking ahead as many tokens as necessary to determine the expression type. In Figure 1, you would need to peek1 know that the expression is either an evironment expression or an expression with an operator. Afterward, a peek2 tells you that the expression is a negation. This is enough to know what to do: move the tokensequence pointer ahead two tokens; evaluate the next expression you see; negate that expression; move the tokensequence pointer ahead by one to account for the closing parenthesis and return the negated value.
Figure 2
Figure 2 shows the state of the token stream after moving ahead two tokens such that you are now ready to evaluate the next BIT expression that you see: in this case, the expression is 10 01 . This invocation of the evaluate function would return the value 1001 while positioning the cursor immediately after the closing parenthesis of the concatentaion. Finally, the first invocation of evaluate returns the value 0110 and the token stream would be positioned immediately after the last parenthesis.
Testing
Ive created a test file testInput.txt and corresponding expected output testOutput.txt.
Scheme functions 75 Points
You must write each of the following scheme functions. You must use only basic scheme functions those described in class, do not use thirdparty libraries to support any of your work. Do not use any function with side effects.
101110101110
undefinedundefined
aundefined
111 00 11100
0101 0011 0110
0 111 010101
! 0101 1010
10101 101010
a 00 b 11 a b0011
11111a 00 b 11 a b111110011
CS 421 : Programming LanguagesKenny Hunt
1. 5 Points Write a Scheme function interleave L1 L2 that accepts lists L1 and L2. The function produces a list such that the elements are interleaved elements of L1 and L2, beginning with L1.
2. 5 Points Write a function named keystore L1 KEY that accepts a list of twotuples L1 and a value KEY. This function returns the second value of the first tuple that begins with KEY. If L1 doesnt contain the KEY, return the emtpy list.
3. 5 Points Write a function named listreplace ALIST SYM VAL that accepts a list of elements and returns that list where all SYMs a single symbol have been replaced by the VAL some scheme value. The replacement must occur even within nested lists. For example:
4. 5 Points Write a function named firstn L1 N that returns the first N elements of L1. If N is negative, return the empty list. If N exceeds the length of L1 return all elements of L1.
5. 5 Points Write a function named forgetn L1 N that returns the elements of L1 except for the first N. If N is negative, return all elements. If N exceeds the length of L1 return the empty list.
6. 10 Points Write a function runningsum L that takes a list of numbers L and generates a list of the runnining sums. See the following examples for clarification.
7. 10 Points Write a function counts XS that takes a list of items XS and generates a counting of the elements in XS. The returned object is a list of lists. Each element of the returned object is a list of length two containing an element X of XS and an integer denoting the number of occurrences of X in XS. The order of the elements in the computed list is not specified. For example:
8. 5 Points Write a function indices L1 X that takes a list of elements L1 and an element X. The function returns a list of the indices in L1 that contain X. See the following examples for clarificaton.
9. 5 Points Write a function jointogether L1 L2 that takes a sorted list ascending of integers L1 and a sorted list of elements L2 and returns a sorted list containing all elements of both L1 and L2. See the following examples for clarificaton.
10. 10 Points Write a function mergesorter L1 that takes listofintegers L1 and returns all elements of L1 in sorted order. You must use a mergesort technique that, in the recursive case, a splits L1 into two approximatelyequallength lists, b sorts those lists, and then c merges the lists to obtain the result. See the following examples for clarificaton.
interleave 1 2 3 4 5 61 4 2 5 3 6
interleave 1 2 3 41 4 2 3
interleave1 21 2
interleave a b c d e f 5 9a e f b c 5 d 9
keystore a 2 b c c 3 4 c3 4
keystore a 2 b c c 3 4 bc
keystore a 2 b c c 3 4 z
keystorea a
listreplace a b c a 33 b c
listreplace a a b c c a 33 3 b c c
listreplacea 3
listreplace a a a a 33 3 3
firstn a b c d e f 3a b c
firstn a b c d e f 3
firstn a b c d e f 33a b c d e f
firstn0
forgetn a b c d e f 3d e f
forgetn a b c d e f 3a b c d e f
forgetn a b c d e f 33
forgetn0
runningsum1 2 31 3 6
runningsum
runningsum3 0 2 33 3 1 4
counts a b c c b ba 1 b 3 c 2
counts
counts 1 3 c c f1 1 3 1 c 2 f 1
indices a b c a e f a a0 3 6
indices a a b b c d a0
indices a b c a e f a z
indicesa b a b0 4
jointogether 3 12 18 12 15 2212 3 12 15 18 22
jointogether12 15 2212 15 18
jointogether 3 12 18 3 12 18
jointogether 3 4 5 100 200 300 400 500 6003 4 5 100 200 300 400 500 600
CS 421 : Programming LanguagesKenny Hunt
11. 10 Points Consider two techniques for representing a graph as Scheme lists. We can represent a directed graph as a list of edges. We call this representation an elgraph i.e. edgelist graph. An edge is itself a list of length two such that the first element is a symbol denoting the source of the edge and the second element is a symbol denoting the target of the edge. Note that an edge is a list not just a pair. For example, the following is a graph: x y y z x z. We can also represent a graph similar to an adjacency matrix. We call this representation an xgraph i.e. matrixgraph. In this case, a graph is a list of adjacencies where an adjacency is a list of length two such that the first element is a node a symbol and the second element is a list of the targets of that node. For example, the following is a graph: x y z y z z .
Write function elgraphxgraph g, that accepts an elgraph g and returns an xgraph of g. Write function xgraphelgraph g, that accepts an xgraph g and returns an elgraph of g.
Additional Requirements
1. You must submit all your work using using a project named CS421 with a folder named hw1. Within this folder you must have a file named scheme.rkt along with your Java project this can be packaged as a subfolder containing your code. Here is a .
2. You must have the statmement lang racket as the first line in your scheme.rkt file.
3. You must have the statement provide interleave keystore listreplace firstn forgetn runningsum counts indices
jointogether mergesorter elgraphxgraph xgraphelgraph as the last line in your sheme.rkt file.
4. The Scheme functions you submit must not use any imperative features. Do not use set, while, display, or begin! You will receive 0 points for any problem that uses these constructs. You may only use define to define functions; any other use will incur a loss of all points for that
problem.
5. Do not write code that breaks a problem into more cases than necessary. Points will be deducted for including unnecessary cases.
6. You must follow good SE practices. The following apply to Java and several apply to all code.
Associate a block with every conditional branch
A leftcurly will never have a character after it on any line
All variable names begin with lowercase letters
All class names begin with uppercase letters
Use methods. If you write a method longer than about 20 lines of code, break it into other methods
Never copyandpaste
No empty lines unless they separate things like blocks of code, methods, or variable declarations
Delete all spurious comments
Never print unless you are writing a commandlinen driven program
Use spaces in expressions. A single space should surround every variable, number, and operator.
Never have a line longer than about 80 characters this is flexible and Im not going to get overly picky, but 80 is a good rule of thumb Dont create objects that you dont use
Dont have instance variables that should be local
elgraphxgraph x y y z x zx y z y z z .
xgraphelgraph x y z y z z x y y z x z.
GitLab
GitLab tutorial
mergesorter 3 1 5 4 21 2 3 4 5
mergesorter
mergesorter 11
CS 421 : Programming LanguagesKenny Hunt
lmth.lairotutlairotutbaltigderahs 34491:ude.xalwu.sc:sptth
Reviews
There are no reviews yet.