CSE341: Programming Languages��Section 10

​

Final-Exam Review

Spring 2023

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

Memoization

CSE 341: Programming Languages

12

• If a function has no side effects and does not read mutable memory, no need to compute it twice for the same arguments
• Can instead keep a cache of previous results
• Net win if (1) maintaining cache is cheaper than recomputing and (2) cached results are reused
• Function needs a way to “keep the previous results”
• For recursive functions, this memoization can lead to exponentially faster programs
• Related to algorithmic technique of dynamic programming (CSE 421)

Factorial (!) with a cache

OOP Approach = “By Row”

• Define a class with 1 abstract method per operation
• In dynamic typing, this can be conceptual, not explicit
• “Fill out the grid” with subclass per row
• Each class has a method for each column
• Can share methods if appropriate (e.g., method in shared superclass)

Question 8 from Autumn 17 practice final