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

Software Engineering Teaching Meets LLMs

Software Engineering Teaching Meets LLMs Context: On 2023-05-26 I attended the  VERSEN  event  SEN Classrooms (26 May 2023) . (What is VERSEN? I quote from the VERSEN website: VERSEN is " the Dutch National Association for Software Engineering. Its mission is to bring together researchers, educators and practitioners in the field of software engineering ") (I haven't been in Utrecht in a while. It was great to be back. I love the campus and the science park.) My keynote presentation had the title " Software Engineering Career Planning in the Age of AGI+/- ". My slides are available here: [ .pdf ] Loads of relevant content is linked on those slides, but there is probably not much ROI from the slides alone. I want to call out though my DOs and the DON'Ts for teaching adaptation in software engineering. SE Teaching Adaptation — DON’Ts   Don’t ban the use of AI. Don’t ignore the new role of AI. Don’t grade homework likely done by LLM. Don’t aim at outsmarting th
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