A riddle regarding type safety

Of course, I have explained to the students in my language theory class what type safety means (remember: progress + preservation) and we have studied this notion time and again for some of the TAPL languages. However, I don't feel like the notion really sinked in universally. Some students consider all this semantics and calculus stuff as obscure and there is a certain critical mass of notation, when passed, concepts are not understood anymore (by some if not many of the Bachelor-level students in my class).

Last night, I came up with a nice "semantics riddle" for type safety:

What would be a super-trivial language with a type system and an SOS semantics such that type safety is violated?


I gave the students 2 minutes to think about the question.

I emphasized several times that the language should be super-trivial.

I also asked them for a general strategy for mis-designing a language to be type-unsafe.

One idea that popped up was to support some notion of cast.

We agreed that this would not be trivial, certainly not super-trivial.


Here is my reference solution:

Syntax of expressions

e ::= v | z

(Hence, there are expressions (forms) x, y and z.)

Values (normal forms)

v := x | y

Types

t ::= a | b

(a and b are the possible types.)

Small-step relation

z -> x

(Yes, we only have one axiom.)

Typing rules

x : a

y : b

z : b

(Yes, we have only axioms here.)

Demonstration of lack of type safety

The term z is the culprit.

z : b but z -> x and x : a


Regards,
Ralf


Comments

  1. James IryDecember 7, 2011 at 5:19 PM

    More trivial solutions are possible with unityping and a lack of progress instead of a lack of preservation. A very degenerate case is

    term syntax
    e ::= x

    types
    t ::= a

    typing
    x : a

    values
    none

    reduction
    none

    So we have neither a reduction semantics for x nor is x a value.

    But maybe that's too trivial to be a language? ;-) I'll try again

    term syntax
    e ::= x | y | z

    types
    t :: = a

    typing
    x : a
    y : a
    z : a

    values
    v ::= y

    reduction
    x -> z

    So x reduces to z which has no defined reduction yet isn't a value.

    ReplyDelete

Post a Comment

Popular posts from this blog

SWI-Prolog's Java Interface JPL

I would like to mix Java and Prolog code on a number of occasions. Together with a student of mine (Joachim Pehl), we just convinced ourselves that the JPL library of SWI-Prolog is really cool. Basically JPL allows you to call Prolog from Java and Java from Prolog. But the question is, of course, how easy is it and can you easily go back and forth . For instance, can we call Prolog from Java and call back Java from Prolog and share Java state throughout? Sure it works! PROLOG PORTION FOLLOWS % This library is all we need to call Java from Prolog :- ensure_loaded(library(jpl)). main :- % Create an object jpl_new(class([],['Test']), [], X), % Printing objects is like printing object ids write(X),nl, % Access a field of the object; happens to be static jpl_get(X, state, Y), % Prints whatever the state's value is write(Y),nl. JAVA PORTION FOLLOWS // This jar is all we need to call Prolog from Java import jpl.*; public class Test { public static int state = 0; ...
Read more

Lecture series on advanced (functional) programming concepts

[ Added 10 Aug 2010: Here is the link to the first lecture's video: " The Expression Problem ". ] If you are a programming nerd or something of a similar species, you may know of C9 Lectures at http://channel9.msdn.com/tags/C9+Lectures . Several of the lectures are given by Erik Meijer who has turned many chapters of Graham Hutton 's book " Programming in Haskell " into videos. In my recent, recorded lecture on " Programming Paradigms and Formal Semantics ", I also incorporated Graham's text, but you should really watch Erik's lectures, if you haven't---they are more fun. I am inspired by his ability to present relatively simple content in such a crisp, insightful, and enjoyable manner. In the aforementioned lecture, I covered all kinds of "crazy stuff" though, and in the end, I had to deliver body bags to my Bachelor students---in the form of a radically simple examination. Thanks a lot btw to @grammarware for helping with t...
Read more

Should I declare defeat on the research topic of API migration?

Of course, I won't, but perhaps I should! Then, I could turn to lower-hanging fruits in research, which I first need to spot, which I can't though because I am a bit obsessed with API migration (and admittedly some other stuff such as megamodeling ). Sigh! It was around 2004 that I became interested in API migration and I have talked about it here and there ever since. Perhaps I am thinking that talking about a difficult problem of interest helps in discovering the solution of the problem, or at least a sensible path to go. Wishful thinking so far! In theory , the objective of API migration made a lot of sense while I was on the XML team at Microsoft because there are obviously way too many XML APIs. In practice , nothing happened on this front because I didn't understand automated API migration well enough back then. Add to this that API migration is something that is potentially risky for the API provider and the API migrator . So you need to mash up a rocket scientist ...
Read more