CSE341: Programming Languages��Section 9

​

Double Dispatch, Visitor Pattern

Autumn 2021

1

Reminders

• Homework 5 grades are (almost) out
• Homework 6 due on Friday, Dec 10th, 5PM
• Racket style guide on course website under resources

CSE 341: Programming Languages

2

Dispatch Overview

Dispatch is the runtime procedure for looking up which function to call based on the parameters given:

• Racket (and Java) use Single Dispatch on the implicit this parameter
• Uses runtime class of this to lookup the method when a call is made
• This is what you learned in CSE 143
• Double Dispatch uses the runtime classes of both this and a single method parameter
• Racket/Java do not have this, but we can emulate it
• You can dispatch on any number of the parameters and the general term for this is Multiple Dispatch or Multimethods

Emulating Double Dispatch

• To emulate double dispatch in Racket just use the built-in single dispatch procedure twice!
• Have the principal method immediately call another method on its first parameter, passing this as an argument
• The second call will implicitly know the class of the this parameter
• It will also know the class of the first parameter of the principal method, because of Single Dispatch

Double Dispatch Example: RPS

• Suppose we wanted to code up a game of “Rock-Paper-Scissors”:
• A game that is played in rounds with 2 players.
• Each player gets to pick a tool: one of “Rock”, “Paper”, or “Scissors”.
• Each combination results in a winner/loser (except when both are the same):
• Rock beats Scissors
• Paper beats Rock
• Scissors beats Paper

Final Quiz Review

Subtyping

• If ta <: tb, then t -> ta <: t -> tb
• A function can return “more than it needs to”
• Jargon: “Return types are covariant”

​

• If tb <: ta, then ta -> t <: tb -> t
• A function can assume “less than it needs to” about arguments
• Jargon: “Argument types are contravariant”

​

• If t3 <: t1 and t2 <: t4, then t1 -> t2 <: t3 -> t4

Question 9 from Spring 19 practice final

Mixins

• Takes an existing class and creates a new subclass of it by adding a set of methods
• A class can be made out of:
• One superclass [old idea]
• The methods from any number of mixins [new idea]
• Its own additions and changes [old idea]
• Example: A mixin that provides <, >, ==, !=, >=, <= in terms of a three-way compare provided by the superclass (see comparable and time-of-day% in code)

Question 7 from Spring 19 practice final

Soundness and Completeness

• A type system is sound if it never accepts a program that, when run with some input, does X

​

• A type system is complete if it never rejects a program that, no matter what input it is run with, will not do X

​

• Notice soundness/completeness is with respect to X

Soundness and Completeness

Programs for which there is >= 1 input that makes the program do bad thing X

All possible programs

(in syntax of some language)

Programs for which there is no input that makes the program do bad thing X

Type system accepting these programs is sound but incomplete (common goal)

Soundness and Completeness

Programs for which there is >= 1 input that makes the program do bad thing X

All possible programs

(in syntax of some language)

Programs for which there is no input that makes the program do bad thing X

Type system accepting these programs is unsound and incomplete

Soundness and Completeness

Programs for which there is >= 1 input that makes the program do bad thing X

All possible programs

(in syntax of some language)

Programs for which there is no input that makes the program do bad thing X

Type system accepting these programs is unsound and is complete

Soundness and Completeness

Programs for which there is >= 1 input that makes the program do bad thing X

All possible programs

(in syntax of some language)

Programs for which there is no input that makes the program do bad thing X

Type system accepting these programs is sound and complete (impossible if type-checker always terminates)

Question 6 from Autumn 17 practice final