I'm new here, I have a question in the scheme that I've been trying to solve for two whole days (really).
I'm getting ready for a test in a few days and I do not know what to do.
I would be very happy if you could help me, because I also do not find much material on this language, the Internet does not have much support.
The question was given to me by the lecturer, it is not taken from any textbook in my opinion, but I study with the book SICP, the question goes like this:
This question deals with the odd-or expressions and the value of the substitution model. In resolving the question, except for the last section, assume that There is no implementaion for "or" in Scheme (i.e. do not rely on existing implementaion of "or" expressions.)
The odd-or expression is defined as:
(or-odd exp1 exp2… expn)
When at least one expression is obtained as an argument (1> = n, (and the number of arguments is odd.
The value of the odd-or expression is obtained as follows:
First, evaluate the expression exp1. If the value is not false, Return it. Otherwise, evaluate the expression exp2 but do not refer to its value (for example, it could be an expression print operation). Then check the value of the expression exp3 - if it is not false return it. If so, rewrite The exp4 and move to exp5 and so on until the last expression.
When you get to the last expression (whose index is odd) you return its value.
for example Revaluation (or 1 2 3) will return 1, revaluation (or-odd false (display 2) 3) will print 2 and return 3.
1) Implement the following procedures (must use the tag package):
• The odd-or-make constructor, which receives a list of expressions as an
argument
• Selectors :
- expression-get that works on a whole odd-or expression.
- first-exp , second-exp and rest-exps that works on exps
- and the predicates Odd-or and Exp-last? Note that the predicate should
also check that number of arguments is odd
Also write down the type of each of them on the actual side.
2) Implement odd-or-eval. It is recommended to use begin.
3) Now, assume that or expressions exist in a language, and write a procedure for performing a syntactic derivation of expressions or-even for or expressions.
Signature of the procedure should be
I want to run bounty but have to wait two days, if there is an option to give points to whoever will help me I will do so.
This question is very difficult for me. very hard. I would love if someone could help me with it, the first part I think I was able to do, the second and third part - I do not even know how to start, it's so hard.
The code I made for the first part:
#lang racket
;Signature: attach-tag(x,tag)
;Type: [Symbol*T -> Pair(Symbol, T)]
(define attach-tag (lambda (x tag) (cons tag x)))
;Signature: get-tag(tagged)
;Type: Pair(Symbol,T) -> Symbol
(define get-tag (lambda (tagged) (car tagged)))
;Signature: get-content(tagged)
;Type: [Pair(Symbol,T) -> T]
(define get-content (lambda (tagged) (cdr tagged)))
;Signature: tagged-data?(datum)
;Type: [T -> Boolean]
(define tagged-data?
(lambda (datum)
(and (pair? datum) (symbol? (car datum))) ))
;Signature: tagged-by?(tagged,tag)
;Type: [T*Symbol -> Boolean]
(define tagged-by?
(lambda (tagged tag)
(and (tagged-data? tagged)
(eq? (get-tag tagged) tag))))
;Type: [LIST(T)->or-odd]
(define make-or-odd
(lambda (expressions)
(attach-tag expressions 'or-odd)))
;Type: [T -> Boolean]
(define or-odd?
(lambda (exp) (and (tagged-by? exp 'or-odd)
(list? (car get-content exp))
(eq? (remainder (length (get-content exp)) 2) 1))))
;Type: [T -> Boolean]
(define last-exps?
(lambda (exp) (null? (cdr exp))))
;Type: [or-odd -> LIST(T)]
(define get-expressions
(lambda (or-odd) (car (get-content or-odd))))
;Type: [LIST(T)->T]
(define first-exp
(lambda (exps) (car (exps))))
;Type: [LIST(T)->T]
(define second-exp
(lambda (exps) (cadr (exps))))
;Type: [LIST(T)->T]
(define rest-exp
(lambda (exps) (cddr (exps))))
If something is not clear, I will explain again, just tell me, this question is important to me, I would be happy if you could help me.
So the code you have to write manipulate expressions, and you need to write an evaluator for a new primitive or-odd kind of expression.
Let's name E be the set of all expressions in your languages.
An expression e in E is either a literal value (we don't need variables for now), or a compound form (f e1 .. en) where e1 to en are expressions from E, and f designates some function or primitive. Here we are interested in the case where f is or-odd.
Let's write [e] the evaluation function for any expression e in E.
For any expression v in E that is a literal value, [v] is defined as v itself. We want to give a definition of [(or-odd e1 .. en)] for all suitable values of v and e1 to en expressions from E.
When at least one expression is obtained as an argument (1> = n, (and the number of arguments is odd.
We have to give a definition for n being odd and at least 1, if I understand correctly.
First, evaluate the expression exp1. If the value is not false, Return it. Otherwise, evaluate the expression exp2 but do not refer to its value (for example, it could be an expression print operation). Then check the value of the expression exp3 - if it is not false return it. If so, rewrite The exp4 and move to exp5 and so on until the last expression. When you get to the last expression (whose index is odd) you return its value.
Let n be an odd number greater than zero, and e1 to en expressions from E.
[(or-odd e1 e2 e3 ... en)] is:
Let v1 = [e1] (it exists because n => 1)
if v1 is false or if there is no e2, return v1.
otherwise, there is an expression e2, as well as, at least, an expression e3 (because n is odd)
let v2 = [e2]
recursively compute [(or-odd e3 ... en)] as the value of [(or-odd e1 e2 e3 ... en)]
In a more Common Lispy way, we could write a function that looks like this, where evaluate is a generic evaluation function and evaluate-or-odd the specific function that evaluates or-odd terms:
(defun evaluate-or-odd (e)
(let ((v1 (evaluate (first e))))
(cond
((not v1) v1)
((not (rest e)) v1)
(t (let ((e2/en (rest e)))
;; evaluate and discard
(evaluate e2/en)
;;
(evaluate-or-odd (rest e2/en)))))))
But the above is not what you have to write exactly, this is more a specification of what you need to implement using the API that is given to you.
In your question you define a lot of helper functions and their signatures, and what is being asked to you is to use them to write an evaluator like above, and without using the existing or (but I guess you can use if or cond).
So you have to define a function like this:
(define odd-or-eval
(lambda (odd-or-exp)
...))
And the odd-or-expr would have been created by a call like this:
(odd-or-make (list e1 e2 e3))
For some values e1, e2 and e3.
So first, from this, you need to get access to the expressions that the data is containing, and you would call:
(get-expressions odd-or-exp)
And this would return a list of expressions.
Than you can enter the recursive process of evaluating your special term for this list of expressions.
You need to call first-exp or rest-exp to destructure the different child expressions.
Notice that you need to evaluate the children elements, but there is no general evaluate function available. I hope this is some part that is missing in your question, let's call that function evaluate.
You need to evaluate the first expression, compare it to false, etc. as described above. Eventually you will return a result or recursively call the evaluator on the remaining expressions. I won't add more details because I think this probably should be enough for you to get started, but do not hesitate to ask questions if something needs clarification.
In case you don't have an evaluate function, maybe you are suppose to write code that transforms code, ie. you need to builda new expression based on the original one.