Bridging the Semantic Gap in Gradual Programming
Observing a disconnect between programmer intent and program meaning, Gradual Programming by Bor-Yuh Evan Chang, Amer Diwan, and Jeremy G. Siek explores tools' lack of knowledge in understanding programmers' priorities, hindering productivity and reliability. Through examples like iteration orders and non-determinism, the authors propose addressing semantic gaps for enhanced program optimization and efficiency.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Gradual Programming: Bridging the Semantic Gap Bor-Yuh Evan Chang Amer Diwan Jeremy G. Siek University of Colorado, Boulder PLDI FIT 2009
Have you noticed a time where your program is not optimized where you expect? Observation: A disconnect between programmer intent and program meaning I need a map data structure Load class file Run class initialization Create hashtable semantic gap Problem: Tools (IDEs, checkers, optimizers) have no knowledge of what the programmer cares about hampering programmer productivity, software reliability, and execution efficiency Bor-Yuh Evan Chang, Amer Diwan, and Jeremy G. Siek - Gradual Programming 2
Example: Iteration Order Must specify an iteration order even when it should not matter class OpenArray extends Object { private Double data[]; public boolean contains(Object lookFor) { for (i = 0; i < data.length; i++) { if (data[i].equals(lookFor)) return true; } return false; } } } class OpenArray extends Object { private Double data[]; public boolean contains(Object lookFor) { for (i = 0; i < data.length; i++) { if (data[i].equals(lookFor)) return true; } return false; } Compiler cannot choose a different iteration order (e.g., parallel) Bor-Yuh Evan Chang, Amer Diwan, and Jeremy G. Siek - Gradual Programming 3
Wild and Crazy Idea: Use Non-Determinism Programmer starts with a potentially non-deterministic program Analysis identifies instances of under- determinedness Programmer eliminates under- determinedness Question: What does this mean? Is it under-determined ? Response: Depends, is the iteration order important? over-determined just right class OpenArray extends Object { private Double data[]; public boolean contains(Object lookFor) { for (i = 0; i < data.length; i++) { if (data[i].equals(lookFor)) return true; } return false; } } } class OpenArray extends Object { private Double data[]; public boolean contains(Object lookFor) { i 0 .. data.length-1 { if (data[i].equals(lookFor)) return true; } return false; } starting point under-determined Bor-Yuh Evan Chang, Amer Diwan, and Jeremy G. Siek - Gradual Programming 4
Lets try a few program variants public boolean contains(Object lookFor) { for (i = 0; i < data.length; i++) { if (data[i].equals(lookFor)) return true; } return false; } Do they compute the same result? Approach: Try to verify equivalence of program variants up to a specification public boolean contains(Object lookFor) { for (i = data.length-1; i >= 0; i--) { if (data[i].equals(lookFor)) return true; } return false; } public boolean contains(Object lookFor) { parallel_for (0, data.length-1) i => { if (data[i].equals(lookFor)) return true; } return false; } Yes Pick any one No Ask user What about here? Bor-Yuh Evan Chang, Amer Diwan, and Jeremy G. Siek - Gradual Programming 5
Surprisingly, analysis says no. Why? Exceptions! Need user interaction to refine specification that captures programmer intent a.data = null a.contains( ) left-to-right iteration returns true right-to-left iteration throws NullPointerException Bor-Yuh Evan Chang, Amer Diwan, and Jeremy G. Siek - Gradual Programming 6
Scary Proposal? Fix semantics per program : Abstract constructs with many possible concrete implementations Apply program analysis to find inconsistent implementations Interact with the user to refine the specification Language designer role can enumerate the possible implementations Bor-Yuh Evan Chang, Amer Diwan, and Jeremy G. Siek - Gradual Programming 7
Bridging the Semantic Gap I need a map data structure Looks like iterator order matters for your program Yes, I need iteration in sorted order Let s use a balanced binary tree (TreeMap) Bor-Yuh Evan Chang, Amer Diwan, and Jeremy G. Siek - Gradual Programming 8
