[racket] missing solution 20.1.1 ex:sem-funcs
On Mon, Sep 8, 2014 at 9:51 PM,
Matthias Felleisen <matthias at ccs.neu.edu> wrote:
On Sep 2, 2014, at 11:45 AM, Daniel Bastos wrote:
>
> > A candidate for a solution.
> >
> > Exercise 20.1.1. Assume the Definitions window in DrScheme contains
> > (define (f x) x). Identify the values among the following expressions:
> >
> > (1) (cons f empty)
> > (2) (f f)
> > (3) (cons f (cons 10 (cons (f 10) empty)))
> >
> > Explain why they are values and why the remaining expressions are not
> > values.
> >
> > Solution. First we consider (1). Here's the relevant part of the
> > grammar.
> >
> > <lst> = empty | (cons <val> <lst>)
> >
> > <val> = <boo> | <sym> | <num> | empty | <lst>
> > | <var> (names of defined functions)
> > | <prm>
> >
> > So (1) is a value because it is <lst> of the form (cons <var> empty),
> > where f is <var> because it is a defined function.
> >
> > Let's consider (3) before (2). (3) is a list of either <var> or <num>,
> > so (3) is <val> as well.
>
> You checked only one half of the value-grammar for lst. Check the other
> half, too. Report back whether you want to change the answer or not. --
> Matthias
>
I want to change it completely. I'm not very sure about what's going on.
Perhaps the other half would be this: since <var> is a value in this
context because f is in fact a defined function, then we get (cons <val>
<lst>) because empty is a <lst> too and then (cons <val> <lst>) = <lst> due
to the definition of <lst>. Since any <lst> is a <val>, we get a value. (Is
that what you meant with 'check the other half'?)
Here's my new complete attempt at the problem. (I ended up saying they're
all values, due to the fact that we know f and f always yields values.)
Exercise 20.1.1. Assume the Definitions window in DrScheme contains
(define (f x) x). Identify the values among the following expressions:
(1) (cons f empty)
(2) (f f)
(3) (cons f (cons 10 (cons (f 10) empty)))
Explain why they are values and why the remaining expressions are not
values.
Solution. A value is anything of the form
<val> = <boo> | <sym> | <num> | empty | <lst>
| <var> (names of defined functions)
| <prm>
where <lst> is of the form
<lst> = empty | (cons <val> <lst>).
Now we start with (1) and apply a series of substitutions based on the
definitions we have.
(cons f empty)
= (cons <var> <lst>) ;; since f is a <var>
= (cons <var> <lst>) ;; since empty is a <lst>
= (cons <val> <lst>) ;; since <var> is a subset of <val>
= <lst> ;; definition of <lst>
= <val> ;; definition of <val>
Therefore (1) is a value.
Next we consider (2). Here's the relevant part of the grammar.
<exp> = <var>
| <prm>
| (<exp> <exp> ...<exp>)
Again, we start with (2) and apply a series of substitutions.
(f f)
= (<var> <var>) ;; since f is a <var>
= (<exp> <exp>) ;; since <var> is a subset of <exp>
However, (<exp> <exp>) is not by definition a value. It is an
expression which may or may not /have/ a value. We know the
definition of f, however, which tells us that it behaves like
the identity function. So the evaluation of that (<exp> <exp>)
yields a function, which is a value. We end with
= <val>
Therefore (2) is a value.
Now (3).
(cons f (cons 10 (cons (f 10) empty)))
= (cons <var> (cons <num> (cons (<var> <num>) <lst>)))
Now again, the whole expressions depends on the application (<exp> <exp>),
which may or may not have a value. Since that is a call to f, the
identity function, we know it returns its argument, so
= (cons <var> (cons <num> (cons <num> <lst>)))
= (cons <var> (cons <num> (cons <val> <lst>))) ;; <num> is a <val>
= (cons <var> (cons <num> <lst>)) ;; definition of <lst>
= (cons <var> (cons <val> <lst>)) ;; <num> is a <val>
= (cons <var> <lst>) ;; definition of <lst>
= (cons <val> <lst>) ;; <var> is a <val>
= <lst> ;; definition of <lst>
= <val> ;; <lst> is a <val>
Therefore (3) is a value.
Thanks for your attention.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20140912/22846cbd/attachment.html>