Seite 1 von 1

Assignment 6.3

Verfasst: 27. Nov 2013 16:12
von AlexanderF
hello,

should it mean:

"Try to encode lists of natural numbers WITH VARIANTS in our language:

data NatList = Nil | Cons(Nat, NatList)

Why is it not possible to encode lists of natural numbers in e?"

because Im not sure if it is realy not possible to encode it in our language,
because we have lambda expressions in the language
and we have numbers in the language.

regards, Alexander

Re: Assignment 6.3

Verfasst: 27. Nov 2013 17:43
von cofi
We also have types in our language.

Re: Assignment 6.3

Verfasst: 27. Nov 2013 18:40
von AlexanderF
cofi hat geschrieben:We also have types in our language.
I do not know what you want to say.

Re: Assignment 6.3

Verfasst: 27. Nov 2013 19:15
von cofi
Well and I don't know how to get more specific without spelling out the problem with our language ;)

Because our language is typed (or rather the way it is typed) you can't do what you want to do with lambda expressions.

Re: Assignment 6.3

Verfasst: 27. Nov 2013 22:45
von AlexanderF
cofi hat geschrieben: Because our language is typed (or rather the way it is typed) you can't do what you want to do with lambda expressions.
Really?

I think I can do with lambda expressions what I want to do.

We have type Num in our language

so one can for example use church encoding

to encode numbers: (well, it does not make much sense because we have numbers, and it is a little bit strange because we use the type Num to encode numbers with lambda expressions)

n = \f:Num->Num, \x:Num. f{n times applied on} x.
(In general one can use here annother type than Num, but Num is the only type we have in the language)

And I think, it could also be possible to enocde lists (like one can read on the wikipedia page).


Besides one can also encode lists as numbers in general.

Re: Assignment 6.3

Verfasst: 27. Nov 2013 22:58
von cofi
With your approach you can a _subset_ of the possible lists, namely the lists of length n (to stick with your example). But that is not what the type defintion calls for. You can define lists of a maximal length with our language (and type system) namely by inlining the NumList definition but you can't do what the definition requires.

Re: Assignment 6.3

Verfasst: 27. Nov 2013 23:01
von erdweg
I think it would be instructive (and the tasks asks you) to actually try to spell out the encoding. Does your idea really work?

Re: Assignment 6.3

Verfasst: 28. Nov 2013 14:21
von dschneid
I think there might be a misunderstanding regarding the interpretation of the task.

It might be true that you can write programs which work with lists of numbers, by using appropriate encodings.

However, I think the task asks one to define lists as a language construct. This is something different. An example of the difference: In C you can work with Booleans (simply because zero and non-zero numbers are treated as false and true), but there are no Booleans as a built-in type of the language. An even more drastic example: You can certainly do everything you can write in C in an assembly language, including working with lists of numbers. However, assembly languages don't have language constructs explicitly for working with lists.

Re: Assignment 6.3

Verfasst: 28. Nov 2013 14:31
von erdweg
dschneid hat geschrieben:However, I think the task asks one to define lists as a language construct.
No. The task asks you to encode (in the sense of embed) lists of natural numbers using existing language constructs. The encoding should be type-safe. I tried to clarify the task description.

Sebastian

Re: Assignment 6.3

Verfasst: 28. Nov 2013 14:39
von dschneid
Yes, I was being imprecise. What I meant was that the task is about adding lists as an instance of a language construct.

Anyway, I'll try not to confuse people any further. I think the task is clearer now.