# Programming by Examples Applications, Algorithms & Ambiguity Resolution

Programming by Examples Applications, Algorithms & Ambiguity Resolution Lecture 2: Algorithms and Ambiguity Resolution Sumit Gulwani Winter School in Software Engineering TRDDC, Pune Outline Lecture 1: Applications DSLs Lecture 2: Search Algorithm Ambiguity Resolution Ranking User interaction models

Leveraging ML for improving synthesis Lecture 3: Hands-on session Lecture 4: Miscellaneous related topics Programming using Natural Language Applications in computer-aided Education The Four Big Bets 2 Programming-by-Examples Architecture Example-based Intent Program set (a sub-DSL of D) Program Synthesizer

DSL D 3 Search Methodology Goal: Set of expr of kind that satisfies spec [denoted ] : DSL (top-level) expression Conjunction of (input stateoutput value ) [denoted ] Methodology: Based on divide-and-conquer style problem decomposition. is reduced to simpler problems (over sub-expressions of e or sub-constraints of ). Top-down (as opposed to bottom-up enumerative search). FlashMeta: A Framework for Inductive Program

Synthesis; 4 Problem Reduction Rules ( [ 1 ] , [ 2 ]) ( [ 1 ] , [ 2 ]) An alternative strategy: , where Let be a non-terminal defined as ( [ 1 ] , [ 2 ]) 5 Problem Reduction Rules Inverse Set: Let F be an n-ary operator.

{ ( 1Abc ) , ( Abc, ) = , 6 Problem Reduction Rules Inverse Set: Let F be an n-ary operator. { ( 1Abc ) , (

Abc, ) = 1 { ( , , ) ,(( , , )} h ) = Consider the SubStr(x,i,j) operator ) ,(6,8)} 1 ( Ab Ab = |1x = ( Ab Abcd { ()0,2

= The notion of inverse sets (and corresponding reduction rules) can be generalized to the conditional setting. 7 Generalizing output values to output properties User specification Examples: Conjunction of (input stateoutput value) Inductive Spec: Conjunction of (input state, output property) 8 Output properties Task Elements belonging to the output list

Elements not belonging to the output list Contiguous subsequence of the output list Prefix of the output list 9 Output properties Task Prefix of the output table (seq of records) Or rather, Prefixes of projections of the output table 10 Generalizing output values to output properties User specification

Examples: Conjunction of (input stateoutput value) Inductive Spec: Conjunction of (input state, output property) Search methodology (Conditional) Inverse set: Backward propagation of values (Conditional) Witness function: Backward propagation of properties 11 Problem Reduction of strings T := Map(L,S) list substring fn S := y: FlashExtract DSL list of lines L := Filter(Split(d,), B) boolean fn B := y: Spec for T Spec for L

Spec for S 12 Problem Reduction SubStr grammar Spec for E substring expr E := SubStr(x,P1,P2) position expr P := K | Pos(x,R1,R2,K) Spec for P1 Redmond, WA

Spec for P2 Redmond, WA 13 Outline Lecture 1: Applications DSLs Lecture 2: Search Algorithm Ambiguity Resolution Ranking User interaction models Leveraging ML for improving synthesis Lecture 3: Hands-on session Lecture 4: Miscellaneous related topics

Programming using Natural Language Applications in computer-aided Education The Four Big Bets 14 Programming-by-Examples Architecture Examplebased Intent Program Synthesizer Rankin g functio n DSL D

Ranked Program Program set setsub-DSL of (a (a sub-DSL of D) D) Witness function s 15 Basic ranking scheme Prefer programs with simpler Kolmogorov complexity Prefer fewer constants. Prefer smaller constants. Input

Amey Karkare Ravindra Naik Output Amey Ravindra 1st Word If (input = Amey Karkare) then Amey else Ravindra Amey 16 Challenges with Basic ranking scheme Prefer programs with simpler Kolmogorov complexity Prefer fewer constants. Prefer smaller constants. Input Amey Karkare Ravindra Naik

Output Karkare, Amey Naik, Ravindra 2nd Word + , + 1st Word Karkare, Amey How to select between Fewer larger constants vs. More smaller constants? Idea: Associate numeric weights with Predicting a correct program in Programming by Example; CAV 2015; constants. 17 omparison of Ranking Strategies over FlashFill Benchmark Basic

Strategy Basic Learning Learning Average # of examples required 4.17 1.48 Predicting a correct program in Programming by Example; CAV 2015; 18 FlashFill Ranking Demo 19 Challenges with Basic ranking scheme

Prefer programs with simpler Kolmogorov complexity Prefer fewer constants. Prefer smaller constants. Input Missing page numbers, 1993 Output 1993 64-67, 1995 1st1995 Number from the left 1st Number from the right How to select between Same number of same-sized constants? Learning to Learn Programs from Examples: Going Beyond Program Structure ; IJCAI 2017; Ellis, Gulwani

20 Challenges with Basic ranking scheme Prefer programs with simpler Kolmogorov complexity Prefer fewer constants. Prefer smaller constants. Input v [CPT-0123 [CPT-456] Output [CPT-0123] [CPT-456] v + ] SubStr(v, 0, Pos(v,number,1)) + ] What if the correct program has larger Kolmogorov complexity?

Idea: Examine data/trace features (in addition to program features) Learning to Learn Programs from Examples: Going Beyond Program Structure ; IJCAI 2017; Ellis, Gulwani 21 Outline Lecture 1: Applications DSLs Lecture 2: Search Algorithm Ambiguity Resolution Ranking User interaction models Leveraging ML for improving synthesis Lecture 3: Hands-on session Lecture 4: Miscellaneous related topics

Programming using Natural Language Applications in computer-aided Education The Four Big Bets 22 Need for a fall-back mechanism It's a great concept, but it can also lead to lots of bad data. I think many users will look at a few "flash filled" cells, and just assume that it worked. Be very careful. most of the extracted data will be fine. But there might be exceptions that you don't notice unless you examine the results very carefully. 23

Programming-by-Examples Architecture Refined Intent Exampl e based Intent Rankin g functio n Program Synthesizer DSL D Ranked Program set

(a sub-DSL of D) Witness function s Intended Program in D Debugging Test inputs Translator Intended Program in R/Python/C#/C+ +/ 24

User Interaction Models for Ambiguity Resolution Make it easy to inspect output correctness User can accordingly provide more examples Show programs in any desired programming language; in English Enable effective navigation between programs Computer initiated interactivity (Active learning) Cluster inputs/outputs based on syntactic patterns. Highlight less confident entries in the output based on distinguishing inputs. User Interaction Models for Disambiguation in Programming by Example, [UIST 2015] Mayer, Soares, Grechkin, Le, Marron, Polozov, Singh, Zorn, Gulwani FlashProfile: Interactive Synthesis of Syntactic Profiles, 25 [Under submission] Padhi, Jain, Perelman, Polozov, Gulwani, Millstein

FlashExtract Demo (User Interaction Models) 26 Outline Lecture 1: Applications DSLs Lecture 2: Search Algorithm Ambiguity Resolution Ranking User interaction models Leveraging ML for improving synthesis Lecture 3: Hands-on session Lecture 4: Miscellaneous related topics Programming using Natural Language Applications in computer-aided Education The Four Big Bets

27 PL meets ML in PBE PBE component (or, more generally, some intelligent software component) Advantages Logical Creative strategi heuristi es cs Written by developer s

Feature s Model Can be learned and maintained by ML-backed runtime Better models Less time to author Online adaptation, personalization Programming by Examples: PL meets ML; Gulwani, Jain; Invited Talk paper at PL meets ML opportunity 1: Search Algorithm PL aspects Domain-specific language specified as grammar rules.

Top-down/goal-directed search using Inverse semantics. Heuristics that can be machine learned Which grammar production to eliminate or try first? Which sub-goal resulting from application of inverse semantics to try first? 29 Eliminating Grammar Productions condition-free expr C := Concat(A, C) | A atomic expression A := SubStr(X, P, P) Input Output | amey

[email protected] Only Concat() branch ConstantString raghava [email protected] possible n Input rg sridhar, amey raghavan, Input sumesh sridhar, Outpu t sr ra Outpu

t sr Need to consider only SubStr() branch Can be Concat() or SubStr() depending on ranking function 30 Neural-guided Deductive Search Controller predict the top-ranked program score from each branch. explore all branches having Replace predicted scores by actual scores as learning progresses. Prediction based on supervised training standard LSTM architecture

100s of tasks, 1 task on average yields 1000 subproblems. Neural-guided Deductive Search for Real-Time Program Synthesis from Examples; Mohta, Kalyan, Polozov, Batra, Gulwani, Jain 31 SPEED-UP Initial Results Average speed-up: 1.67 32 PL-meets-ML opportunity 2: Program Ranking PL aspects Syntactic features of a program Number of constants, size of constants

Features of outputs/execution traces of a program on extra inputs. IsYear, Numeric Deviation, Number of characters Heuristics that can be machine learned Weights over various features Non-syntactic features isPersonName. 33 PL meets ML opportunity 3: Disambiguation Communicate actionable information back to user. PL aspects Generate multiple top-ranked programs Enable effective navigation between those programs. Highlight ambiguity based on distinguishing inputs. An input where different programs generate different outputs.

Heuristics that can be machine learned Highlight ambiguity based on clustering of inputs/outputs based on their syntactic and other features. When to stop highlighting ambiguity? User Interaction Models for Disambiguation in Programming by Example, [UIST 2015] Mayer, Soares, Grechkin, Le, Marron, Polozov, Singh, Zorn, Gulwani FlashProfile: Interactive Synthesis of Syntactic Profiles, 34 [ArxiV Report] Padhi, Jain, Perelman, Polozov, Gulwani, Millstein Programming-by-Examples Architecture Refined Intent Exampl e based Intent

Rankin g functio n Program Synthesizer DSL D Ranked Program set (a sub-DSL of D) Witness function s Intended

Program in D Debugging Test inputs Translator Intended Program in R/Python/C#/C+ +/ 35 Conclusion PBE is a revolutionary new frontier in AI. 99% of end users are non-programmers. Data scientists spend 80% time cleaning data. Developers spend 40% time refactoring code during migration.

PL meets ML in AI software creation ML can synthesize code heuristics: better, efficient, PBE PL aspect Heuristics that can adaptable component Search Algorithm Program Ranking Disambiguatio DSL, Inverse functions Features be machine learned Non-deterministic choices

Weights Program Clustering, 36

## Recently Viewed Presentations

• Arial MS Pゴシック Book Antiqua Wingdings 2 Calibri Symbol Wingdings Habitat 1_Habitat 2_Habitat 3_Habitat 4_Habitat 5_Habitat 6_Habitat 7_Habitat 8_Habitat Analyzing Data Forked-Line Method, F2 UuDd x UuDd Genotypes U--D-- Chance Deviation Mendel Goodness of Fit Null Hypothesis Answer these questions…
• It is wrong to have malicious and unjustifiable feelings of animosity towards others, but it is right for Christians to have and exercise deep feelings of aversion towards things that are evil in the sight of God. "These six things...
• Saturday Afternoon Presentation of Trophies By NAWB President Audrey Drinkwater (NGWBJ) Part 1 Trophy Table News & Views Trophy Best Article printed in News & Views Mike Davey Burbage Trophy Best Photo - Wine / Beermaking Theme Bernard Lamb Young's...
• Statistics and Data Analysis. Professor William Greene. Stern School of Business ... A variable that will take a value assigned to it by the outcome of a random experiment. Realization of a random variable: The outcome of the experiment after...
• "We lived in the same cell before, further down the hill, but were supposed to come to the village, so we did in October. I had lived in the old house since we were married.We had no help at all...
• Daniel Bustillo, Director, Healthcare Career Advancement Program. Tim Herbert, Senior Vice President, Research and Market Intelligence, Comps TIA . Albert Shih, Ph.D., Advanced Manufacturing National Program Office, National Institute of Standards and Technology, and Professor, University of Michigan . UNITED...
• Recombinant DNA The ability to combine the DNA of one organism with the DNA of another organism. Recombinant DNA technology was first used in the 1970's with bacteria. Recombinant Bacteria Remove bacterial DNA (plasmid). Cut the Bacterial DNA with "restriction...
• Critical Components in the Formation of Clinical Pastoral Education Supervisors ... Call to mind the ACPE Supervisor who influenced your desire / decision to become a supervisor. ... and Certification (SWR) Larry J. Smith E-mail address: [email protected] 254-724-1059. 97.82.209.105. Travis...