PL OurScheme project for the spring of 2017, Part 2 (“Project 2”)
Due : 6/25(日) midnight (23:59)
Copyright By PowCoder代写 加微信 powcoder
// Some test input of Project 1 may again appear in Project 2
// e.g., if in Project 1 the input was : (1 2 3)
// then in Project 2, this input may reappear as : ‘(1 2 3)
// or : (quote (1 2 3))
In Project 1, you have done the following :
＊ You wrote a scanner or a 「scanner layer」 (consisting of several
functions).
This scanner is responsible for (1) using separators to get tokens
from the user’s actual input, and (2) deciding what tokens they are ;
In a sense, the scanner “transforms” the actual input stream of
characters into a (conceptual) input stream of tokens.
＊ You wrote a parser or a 「parser layer」(consisting of several
functions).
The parser “reads” the conceptual input stream of tokens by calling
the scanner, and decides whether the input stream of tokens
satisfies the grammar of an S-expression.
Once the parser makes sure that the tokens “read”
satisfies the grammar of an S-expression, it constructs
an internal, tree-like data structure for this S-expression.
＊ You wrote a “pretty-printer”. Given a pointer to an internal data
structure that corresponds to some S-expression, the pretty-printer
prints out this S-expression in some pre-determined format.
＊ You managed to print an error message signifying the location
of the so-called “error character” whenever the system encounters
a syntax error in the user’s input.
＊ You organized the working of your OurScheme interpreter in some way,
so that the working of your system corresponds to the following
“code skeleton” :
Print : ‘Welcome to OurScheme!’
Print : ‘> ‘
ReadSExp( s_exp );
if no syntax error (no “unexpected token” or “unclosed string”)
then PrintSExp( s_exp );
PrintErrorMessage() ;
until user has just entered LEFT_PAREN “exit” RIGHT_PAREN
EOF encountered
if ( END-OF-FILE encountered ) // and NOT 「user entered ‘(exit)’」
Print ‘ERROR (no more input) : END-OF-FILE encountered’
Print ‘\n’
Print : ‘Thanks for using OurScheme!’
For Project 2, you are to extend your system so that the following are
realized (by your system).
＊ All “primitive exressions” (expressions that involve primitive
operations) can be evaluated.
＊ ‘define’ is supported (but no definition (and use) of functions yet)
＊ “Conditional processing” (via the use of ‘if’ and ‘cond’) is supported.
＊ Sequencing (functional composition and the use of ‘begin’) is supported.
Your main program should now look something like the following.
Print : ‘Welcome to OurScheme!’
Print : ‘> ‘
ReadSExp( inSExp );
if no syntax error
EvalSExp( inSExp, resultSExp ) ;
if evaluation error
then PrintEvaluationError() ;
else // no evaluation error
PrintSExp( resultSExp );
end-then // no syntax error
else // syntax error
PrintSyntaxError() ;
until user has just entered LEFT_PAREN “exit” RIGHT_PAREN
EOF encountered
if ( END-OF-FILE encountered ) // and NOT 「user entered ‘(exit)’」
Print ‘ERROR (no more input) : END-OF-FILE encountered’
Print ‘\n’
Print : ‘Thanks for using OurScheme!’
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
error的判斷(怎樣的寫法應該算什麼樣的error？)是以HowToWriteOurScheme.doc為準
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Below are the primitives (and features) that your system should implement.
(括號內的數字指的是這個function可接受的argument的數目 – i.e., the number of
arguments that this function can take)
1. Constructors
list (>= 0)
2. Bypassing the default evaluation
3. The binding of a symbol to an S-expression
define (2)
; Once a symbol is defined (or “bound”), the user can enter
; this symbol, and the system will return its binding.
; however, the user is not allowed to redefine symbols that happen
; to be system primitives such as ‘cons’ or ‘car’ or ‘cdr’, etc.
4. Part accessors
5. Primitive predicates (all functions below can only take 1 argument)
number? // in OurSchem, real? = number?, but not in Scheme (there are complex-numbers)
6. Basic arithmetic, logical and string operations
; in evaluating ‘and’ or ‘or’, it is possible that some “argument expr”
; does not get evaluated ; use Petite Scheme to see what this means
; e.g., (set! a 5) a (and (set! a 10) #f (set! a 100)) a (or #t (set! a 200)) a
and (>= 2)
or (>= 2)
; all functions below can take 2 or more arguments
string-append
7. Eqivalence tester
eqv? (2)
equal? (2)
8. Sequencing and functional composition
begin (>= 1)
; the user may also enter, e.g., >>(car (cdr ‘(1 2 3 4)))<< 9. Conditionals ; in evaluating 'if' or 'cond', it is possible that some "sub-expr" ; does not get evaluated (this is the meaning of conditional expressions) ; ; use Petite Scheme to check ; if (2 or 3) cond (>= 1)
10. clean-environment
; 此指令將user的definitions清空，一切重新開始
clean-environment (0)
Example : // assuming that we run the system using interactive I/O
// ========= I/O starts below and does not include this line ========
Welcome to OurScheme!
> ; 1. A list (or rather, a dotted pair) is CONSTRUCTED.
(cons 3 4) ; an operation on two objects
) ; ‘(3 . nil)’ = ‘(3)’
) ; same thing
> (CONS 3 4) ; Scheme distinquishs between upper and lower cases
ERROR (unbound symbol) : CONS
> (cons hello 4)
ERROR (unbound symbol) : hello
ERROR (unbound symbol) : hello
> (CONS hello there)
ERROR (unbound symbol) : CONS
> (cons 1 2 3)
ERROR (incorrect number of arguments) : cons
> ; 2. To “by pass” the default interpretation of an S-exp
ERROR (attempt to apply non-function) : 3
> ‘(3 4 5)
> (quote (3 (4 5)))
ERROR (attempt to apply non-function) : 4321
> (cons 3 ‘(4321 5))
> (list 3 (4 5))
ERROR (attempt to apply non-function) : 4
> (list 3 ‘(4 5))
> ; 2. To give a (symbolic) name to an object
; Meaning of DEFINE revisited (“令”)
; Basically, DEFINE sets up a (temporary) binding between a symbol
; and an S-expression
; DEFINE sets up the binding between a name and an internal data structure
ERROR (unbound symbol) : abc
> (define a 5) ; “令a為5”; 讓我們把”那個東西”又稱為’a’
> a ; Is ‘a’ a name for something?
> (define x ‘((3 4) 5)) ; 讓我們把”那個東西”又稱為’x’
> x ; Is ‘x’ a name for something?
> ; Combining (1), (2) and (3)
(define hello ‘(1 2 . 3))
hello defined
> (cons hello
> (cons hello
> (define hello “CYCU ICE (1 2 3)”)
hello defined
> (cons hello
‘(400 (5000 600) 70)
( “CYCU ICE (1 2 3)”
> (define there “Number One!”)
there defined
> (cons hello there)
( “CYCU ICE (1 2 3)”
“Number One!”
> (define hello ‘(1 2 . (3)))
hello defined
> (list 3 4)
> ( list hello
> ; 3. Whenever a function is called, its parameters are evaluated first.
; However, if the first symbol of a to-be-evaluated list
; is not bound to a function in the first place, the evaluation process
; stops, and an appropriate error message is issued.
ERROR (unbound symbol) : f
> (cons 3 b)
ERROR (unbound symbol) : b
> (cons 3 a)
ERROR (attempt to apply non-function) : 5
> (define a ‘(3 4))
> (cons 5 a)
> ; 4. Different parts of a list (or a dotted pair) can be
; individually accessed
(car ‘(3 4)) ; the “left part” of a dotted pair
> (car ‘((3 4) 5) )
> (car ‘((3 4) 5 . 6) )
> (car ‘((3 4) . 5) )
> (car WarAndPeace!)
ERROR (unbound symbol) : WarAndPeace!
> (cdr ‘((3 4) 5) ) ; the “right part” of a dotted pair
> (cdr ‘((3 4) ” Year!” . 6) )
( ” Year!”
> (cdr ‘((3 4) . “Merry Christmas!”) )
“Merry Christmas!”
; Different parts of a list can be accessed by mixing the use of
; CAR and CDR
(car (cdr ‘((3 4) 5) ))
> (car (cdr ‘((3 4) 5 . 6) ))
> (car (cdr ‘((3 4) 5 6 7) ))
> (cdr (cdr ‘((3 4) 5 6 7) )
ERROR (car with incorrect argument type) : 3
> (car 3 4)
ERROR (incorrect number of arguments) : car
> (car 3 . 5)
ERROR (non-list) : ( car
> ; 5. Primitive predicates (A predicate is a function that returns
; “true” or “false”; By convention, the name of a predicate
; should have a suffix ‘?’)
> (atom? 3)
> (atom? ‘(1 . 2))
> (pair? 3) ; Other Lisps do not have PAIR; they have ATOM
> (pair? ‘(3 4))
> (pair? ‘(3 . 4))
> (pair? “Hello, there!”)
> (list? 3)
> (list? ‘(1 2 3))
> (list? ‘(1 2 . 3))
> (null? ()) ; is it the empty list?
> (null? #f)
> (null? ‘(3 . 4))
> (integer? 3)
> (integer? +3)
> (integer? 3.4)
> (integer? -.4)
> (real? 3)
> (real? 3.4)
> (real? .5)
> (number? 3) ; in OurScheme, is-real IFF is-number
> (number? 3.4) ; but in other Schemes, there may be complex numbers
> (string? “Hi”) ; therefore, in other Scheme, a number may not be real
> (string? +3.4)
> (boolean? #t)
> (boolean? ())
> (boolean? #f)
> (boolean? ‘(3 . 4))
> (symbol? ‘abc)
> (symbol? 3)
> (number? America)
ERROR (unbound symbol) : America
> (define America ‘(U. S. A.))
America defined
> (symbol? America)
> (pair? America)
> (pair? American)
ERROR (unbound symbol) : American
> (boolean? America)
> (pair? Europe 4)
ERROR (incorrect number of arguments) : pair?
> (pair? America Europe)
ERROR (incorrect number of arguments) : pair?
> (define Europe ‘hi)
Europe defined
> (pair? America Europe)
ERROR (incorrect number of arguments) : pair?
> (define a . 5)
ERROR (non-list) : ( define
> (define a) ; problem with the number of parameters
ERROR (DEFINE format) : ( define
> (define a 10 20)
ERROR (DEFINE format) : ( define
> (define cons 5) ; attempt to redefine a system primitive
ERROR (DEFINE format) : ( define
; 6. Basic arithmetic, logical and string operations
> (+ 3 7 10 25)
> (- 3 7 10 25)
> (/ 5 2) ; integer division
> (/ 5 2.0) ; float division ; a float is always printed in 3 digits
> (/ 2 3.0) ; Use printf( “%.3f”, …) in C or String.format( “%.3f”, …) in Java
> (- 3.5 5)
> (* 3 “Hi”)
ERROR (* with incorrect argument type) : “Hi”
ERROR (incorrect number of arguments) : *
> (* 3 4 5)
> (* 1 2 3 4 5)
> (- 1 2 3 4 5)
> (define a 5)
> (/ 15 a)
> (/ 15.0 3)
> (/ 30 5 0) ; always test for “division by 0” before performing division
ERROR (division by zero) : /
> (+ 15.125 4)
> (not #t)
> (> 3.125 2)
> (>= 3.25 2)
> (< 3.125 2) > (<= 3.125 2) > (+ a a a)
> (string-append “Hello,” ” there!”)
“Hello, there!”
> (string-append “Hello,” ” there!” ” Wait!”)
“Hello, there! Wait!”
> (string>? “az” “aw”)
> (string (string=? “az” “aw”)
> (string=? “az” (string-append “a” “z”))
> (string>? “az” “aw” “ax”)
> (string (string=? “az” “aw” “ax”)
> (string>? “az” “aw” “atuv”)
> (string>? 15 “hi”)
ERROR (string>? with incorrect argument type) : 15
> (+ 15 “hi”)
ERROR (+ with incorrect argument type) : “hi”
> (string>? “hi” “there” a)
ERROR (string>? with incorrect argument type) : 5
> (string>? “hi” “there” about)
ERROR (unbound symbol) : about
> (string>? “hi” “there” about a)
ERROR (unbound symbol) : about
> ; 7. eqv? and equal?
; eqv? returns “true” only when the two being compared
; objects are atoms (except in the case of strings)
; or when the two being compared objects “occupy the
; same memory space”.
; equal?, on the other hand, is the usual notion of
; equality comparison
(eqv? 3 3)
> (eqv? a a)
> (eqv? a ‘(3 4))
> (equal? a ‘(3 4))
> (define b a)
> (eqv? a b)
> (define c ‘(3 4))
> (eqv? a c)
> (equal? a c)
> (eqv? ‘(3 4) ‘(3 4))
> (eqv? “Hi” “Hi”)
> (equal? a a)
> (equal? ‘(3 4) ‘(3 4))
> (equal? “Hi” “Hi”)
> ; some functional compositions
(not (pair? 3))
> (define a 5)
> ( and ; ‘and’ either returns the evaluated result of
(pair? 3) ; the first one that is evaluated to nil
a ; or the evaluated result of the last one
> ( and #t a )
> ( or ; ‘or’ either returns the evaluated result of
a ; the first one that is not evaluated to nil
(null? ()) ; or the evaluated result of the last one
; Let us talk about conditionals before we talk about
; sequencing and functional composition
; 9. Conditionals
(if (> 3 2) ‘good ‘bad)
> (define a 5)
> (if a ‘good ‘bad) ; note : ‘if’ can take just two arguments
> (if #t 30)
> (if #f 20)
ERROR (no return value) : ( if
> (if (not a) ‘good ‘bad)
> (define a nil)
> (if a ‘(1 2) ‘(3 4))
> (if (not a) ‘((1 (2) 1) 1) ‘((3) (4 3)))
> (define b 4)
> ; ‘else’ is a keyword (and not a reserve word) in OurScheme
; (or rather, Scheme) ;
; according to our textbook (by Sebesta), a keyword has a
; special meaning ONLY WHEN it appears in some special contexts
; (translation: when the word appears in contexts that are not
; special, the word is just an “ordinary word”)
; ‘else’ has a special meaning only when it appear as the first
; element of the last condition of ‘cond’ ;
; in all other cases, ‘else’ is considered a normal symbol
(cond ((> 3 b) ‘bad)
((> b 3) ‘good)
(else “What happened?”) ; this ‘else’ has a special meaning ;
) ; it means “in all other cases” here
> (cond ((> 3 b) ‘bad)
(else ‘good) ; this ‘else’ is treated as a normal symbol
(else “What happened”); this ‘else’ is treated as a keyword
ERROR (unbound symbol) : else
> (define else #f)
else defined
> (cond ((> 3 b) ‘bad)
(else ‘good) ; the normal symbol ‘else’ is bound to nil
(else “What happened”); this ‘else’ means “in all other cases”
“What happened”
> (cond ((> 3 b) ‘bad)
((> b 5) ‘bad)
(else “What happened?”)
“What happened?”
> (cond ((> 3 4) ‘bad)
((> 4 5) ‘bad)
ERROR (no return value) : ( cond
> (cond ((> 3 4) ‘bad)
((> 4 3) ‘good)
> (cond ((> y 4) ‘bad)
((> 4 3) ‘good)
ERROR (unbound symbol) : y
ERROR (COND format) : ( cond
> (cond #t 3)
ERROR (COND format) : ( cond
> (cond (#t 3))
> (cond (#f 3))
ERROR (no return value) : ( cond
> (cond (#t (3 4)))
ERROR (attempt to apply non-function) : 3
> (cond (#f (3 4)) 5)
ERROR (COND format) : ( cond
> (cond (#f (3 4)) (5 6))
> (cond (#f (3 4)) (“Hi” (cons 5) . 6))
ERROR (COND format) : ( cond
> (cond (#f (3 4)) (“Hi” (cons 5) 6))
ERROR (incorrect number of arguments) : cons
> (cond (#f (3 4)) (“Hi” (cons 5 6) 7))
; 8. Sequencing and functional composition
; Can be more complex than what is given here
(define d 20)
> (if #t 3 5)
> (define a 20)
> (define b 40)
( if (> a b)
(+ a (* a b))
(- b (+ a a))
( if (> a b)
(+ a (* a b))
(- b (+ a a))
> (if #t (begin 3 4 5) (begin 6 7))
> (if #t (3 4 5) (6 7))
ERROR (attempt to apply non-function) : 3
> (if #f (3 4 5) (6 7))
ERROR (attempt to apply non-function) : 6
> (cond ((> 5 3) ‘good ‘better ‘best) (#t ‘OK?) )
; 10. clean-environment cleans up the (user-defined) environment
(clean-environment)
environment-cleaned
ERROR (unbound symbol) : a
> (define a 5)
> (clean-environment)
environment cleaned
ERROR (unbound symbol) : a
; 11. the binding of a symbol can be a function, which is an atom too
cons ; the binding of the symbol ‘cons’ is a function with original name being ‘cons’ > (atom? cons) > (define myCons cons) ; let the binding of ‘myCons’ be the binding of ‘cons’ > myCons ; the binding of ‘myCons’ is a function with original name being ‘cons’ > (define a (myCons car cdr)) ( # # # > (define a (list car cdr)) # ( # > ((car a) (cons car cdr)) ; just think of a function as a “value” just like 3 > ( ((car a) (cons car cdr)) ; test data like this will not appear Thanks for using OurScheme! // ========================================================================= Project 2可能會出現的error – 總整理 一、Project 1的四個可能會出現的error，在Project 2 依舊可能會出現： ERROR (unexpected token) : atom or ‘(‘ expected when token at Line X Column Y is >>…<<
ERROR (unexpected token) : ')' expected when token at Line X Column Y is >>…<<
ERROR (no closing quote) : END-OF-LINE encountered at Line X Column Y
ERROR (no more input) : END-OF-FILE encountered
二、Project 2增加了以下的這些error：
> (cons 3 . 5) > (cons 3 (cons 3 . 5)) > (cons 3) > (exit 0) ERROR (car with incorrect argument type) : 3 ERROR (attempt to apply non-function) : 3 > (if #f 3) > (cond (#f 3) (#f 4)) > noSuchThing > (cons noSuchThing noOtherThingEither) > (/ 30 5 0) 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com
#
myCons defined
#
#
‘((10 20) (30 40) . 50) ; until Prob. 6, 7, 13, 14, 15 and 16
// ========= I/O ends above and does not include this line ========
ERROR (non-list) : ( cons
ERROR (non-list) : ( cons
ERROR (incorrect number of arguments) : cons
ERROR (incorrect number of arguments) : exit
ERROR (no return value) : ( if
ERROR (no return value) : ( cond
ERROR (unbound symbol) : noSuchThing
ERROR (unbound symbol) : noSuchThing
ERROR (division by zero) : /