6. Programming by example

Today's topics

Programming by example

Programming by demonstration

(Automatic program generation?)

Problems of computers

Too much repetitive chores!

Example1: indenting 100 lines

code:from.rb

def tarai(x,y,z,indent=0)

puts "#{' '*indent}tarai(#{x},#{y},#{z})"

if x <= y then

y

else

tarai(tarai(x-1,y,z),

tarai(y-1,z,x),

tarai(z-1,x,y),

indent+1)

end

end

code:to.rb

# def tarai(x,y,z,indent=0)

# puts "#{' '*indent}tarai(#{x},#{y},#{z})"

# if x <= y then

# y

# else

# tarai(tarai(x-1,y,z),

# tarai(y-1,z,x),

# tarai(z-1,x,y),

# indent+1)

# end

# end

Example1: indenting 100 lines

Write a program?

Write a macro?

Find special featues?

Example2: Calculate a function many times with different parameters

code:cf.txt

10 × 9 / 5 + 32 =

20 × 9 / 5 + 32 =

30 × 9 / 5 + 32 =

...

Should write a program?

Example3: Object layout

https://gyazo.com/8f4889fa166f8100a3a108ad01d2e3a0

Just do it as a routine work?

Solutions

Add more features to the application

Applications will become huge

Use programmable macros

Usually not easy

Write programs

Programming is not easy for everybody

Use predictions!

Predict user's next operation from history

Detect repetitive tasks

Predict next parameter

e.g. 1, 2, 3 => 4

Create a macro from examples

Creating a program from examples

Goal: automatic programming from example data

Programming by Example (PBE)

Programming by Demonstration (PBD)

Merits of PBE

Creating programs without writing codes

Programming for the rest of us

Merits of PBE/PBD

Tasks can be repeated easily

Creating macros

No need for providing many features

No need for programming

No programming knowledge required

No abstract thinking required

Easy to understand the result

Programming for non-programmers

No need for editing program texts

Example: classification of email mesages

Writing codes

code:mail.pl

if(/From: masui.*/){ ...

Using PBE

Inference from user operations

Creating GUI programs

Create a program from GUI operations

Bridge the gap between behavior and programming

e.g. GUI design system

Eliminate the gap between display and program

Books on PBD/PBE

http://gyazo.com/faf7afca309669b6fcf4ca7c56784459.png

Books on PBD/PBE

http://gyazo.com/7023e93cdd3569ba57f6b38ecad9b60f.png

Books on PBD/PBE

http://gyazo.com/ff1f4d2e9b739ca809c6aa710d47afe7.png

Allen Cypher

Working on PBE for 20+ years

http://gyazo.com/28aae39177a8bb0a5db71e11aa8cbace.png

Taxonomy of PBD systems

Intelligent / non-intelligent

Create a program or not

Simple / complicated

Simple PBD

Remember operations / redu operations

Prediction using application knoledge

Prediction from statistic data

Detecting repetitive patterns

Complicated PBD

Automatic adaptation

Machine learning

Inductive reasoning

Inductive reasoning

Get a theorem from examples

Generalization

Examples => hypotheses => verification

Example data used for prediction

Implicit data

Operation history

User context

Corpus

Dictionaries

Explicit (extra) data

Create a program from example data

Inplicit data + explicit data

Teach the system with examples

Common techniques for PBD

Use operation history, context, dictionaries

Use ad-hoc application knowledges

Correcting wrong inference

Automatic generation of example data

Visual representation of user operations and programs

Simple PBD examples

Browser history

UNIX shell

Reactive Keyboard

Predictive calculator

Dynamic Macro

POBox

Eager

SnappingEditor

Smart Make

History-based calculator

Completion using browsing history

http://gyazo.com/d10af2afca10df05c52cbea83ab93e8f.png

UNIX shell, Emacs

Use shortcut keys

% !!

% !c

completion

Predicting long name from partial string

Dynamic abbreviation

Use existing strings as a dictionary

Demo: Emacs completion, dabbrev

Use M-/ key

Predict next key input from previous keystrokes on Unix shell

Good for slow typers

PPM (Prediction by Partial Match)

Predict next character based on history

Used for text compression

Good prediction => good compression ratio

PPM Method

Predict next character based on these values

Text compression algorithms

Dictionary-based (LZ)

Create a dictionary of words

Pointer to next appearance

Prediction + coding

PPM method

Huffman coding / arithmetic coding

Text compression with Huffman coding

When probability is unknown

2 bits requred for each character

1*0.5 + 2 * 0.25 + 2 * 3 * 0.125 = 1.75bits / char

Arithmetic coding = extension to Huffman coding

Janken = rock-paper-scissors

http://gyazo.com/8f3f344d62b29641a47fc6195eed5004.png

Predictive calculator (Witten)

PPM-based

Predict keystrokes from previous keystrokes

e.g. 1 + 2 = , 1 + 3 = , ...

.1 mc m+= +/- + 1 = exp * mr =

Predict next entry based on history

Repeat previous tasks on Emacs

Extract a pattern from key history

Detect repetitive keystrokes

Automatic macro creation

Demo: Dynamic Macro

Predict next number

Dynamic Macro on Firefox

Firefox extension

Dynamic Macro

Two repetitive operation + REP key => do it once more

Longest key sequence is used

Dynamic Macro (Cont'd)

Operation ABA + REP key => execute B

One more REP => execute AB

http://gyazo.com/ac2b347a7042f920edd576ee07c4b7f4.png

Prediction-based Japanese text input system

Select a candidate from the list

Give small conditions to get the list

Approximate pattern matching

POBox algorithm

Specify pronunciation / handwriting

Show candidate words

Use corpuses for predicting next word

Approximate pattern matching if no candidate found

Products

Demo: POBox

HyperSnapping (Masui)

Snapping-based drawing editor

Prediction similar to Dynamic Macro

https://gyazo.com/ae10f0e13797c754c8ed896eb73a2749

Demo: HyperSnapping

Eager (Cypher)

http://gyazo.com/6137905efa632ac7386ffdc7647a9891.png

Eager

Predict next GUI operation from previous operations

The system is always watching the user

Predicted operation is shown to the user

Same operation by the user => prediction approved

Other operation => prediction rejected

Everything seems okay => automatic execution

Video: Eager

https://www.youtube.com/watch?v=X6ZL4BXOfbk

Smart Make (Masui)

Calculate file dependencies from shell operations

Shell commands specify relationship between files

Dependency extraction

Cannot be calculated from command args

Use file creatiton/access time

Smart Make

code:smartmake:txt

101% grep a /etc/passwd > passwd.a

102% grep b /etc/passwd > passwd.b

103% tar cvf passwd.tar passwd.a passwd.b

a passwd.a 2 blocks

a passwd.b 3 blocks

104% compress < passwd.tar > passwd.tar.Z

105% uuencode passwd.tar.Z passwd.tar.Z > passwd.UU

106% ls

passwd.UU passwd.a passwd.b passwd.tar passwd.tar.Z

107% mm

passwd.tar.Z: passwd.tar

compress < passwd.tar > passwd.tar.Z

passwd.tar: passwd.a passwd.b

tar cvf passwd.tar passwd.a passwd.b

passwd.b:

grep b /etc/passwd > passwd.b

passwd.a:

grep a /etc/passwd > passwd.a

History-based calculator (Masui)

Use 'undo' key

Change the parameter and recalculate

Example: C/F conversion

10 10

× 10

9 9

／ 90

5 5

＋ 18

32 32

＝ 50

Calculation with other values

Use backspace key for undo

- 50 previous result

BS 32 last parameter displayed

BS 5 parameter displayed

BS 9

BS 10 first parameter

20 20 enter new parameter

＝ 68 new F calculated

30 30 enter new parameter

＝ 86 new F calculated

...

State transition of recalculation

http://gyazo.com/641016c4ecdf0940427df5b27bf8175b.png

Demonstration-based interface

The system infers user's needs from demonstrated data

Examples

Editing by Example

TELS

SmallStar

Triggers

Metamouse

Chimera

Mondrian

Layout by Example

KidSIM

Stagecast

Viscuit

CoScripter

Sicri

Editing by Example (Nix)

Show texts before and after conversion

Edit commands are not shown

Use a subset of RegExp

Infer a conversion rule and apply it to the rest

TELS (Mo)

Infer GUI operations on text editor and generate a program

Insert/delete/move/select operations

Detect loop

↓

Use a subset of RegExp

Texts before/after conversion

code:before.txt

John Bix, 2416 22 St., N.W., Calgary, T2M 3Y7. 284-4983

Tom Bryce, Suite 1, 2741 Banff Blvd., N.W., Calgary, T2L 1J4. 229-4567

Brent Little, 2429 Cherokee Dr., N.W., Calgary, T2L 2J6. 289-5678

Mike Hermann, 3604 Centre Street, N.W., Calgary, T2M 3X7. 234-0001

code:after.txt

John Bix,

2416 22 St., N.W.,

Calgary,

T2M 3Y7.

Tom Bryce,

Suite 1,

2741 Banff Blvd., N.W.,

Calgary,

T2L 1J4.

Brent Little,

2429 Cherokee Dr., N.W.,

Calgary,

T2L 2J6.

Mike Hermann,

3604 Centre Street, N.W.,

Calgary,

T2M 3X7.

Generating a program

https://gyazo.com/88c6657deef4e8e62aa694e7d321a0ed

Generating a program (Cont'd)

https://gyazo.com/32b050371399acb749a7d3812af4f50b

SmallStar (Halbert)

Create a GUI macro by demonstration

Generated macro can be edited

http://gyazo.com/dca4a743d9c8da3dbc0132fe656ca9c5.png

http://gyazo.com/595a5a4cf92cadbf60b4c8309bdce796.png

Triggers (Potter)

Macro creation based on bitmap pattern matching

e.g. mouse click if "OK" is displayed}

When a specified patten is displayed, perform specified operations

e.g. change the color of all negative data

http://gyazo.com/cd25caa5d14b850f9a1d9da2d6beb0c9.png

Video: Triggers

Preform any GUI operation based on bitmap pattern matching

http://www.youtube.com/watch?v=FxDOlhysFcM

Metamouse (Maulsby)

http://gyazo.com/b2c205758a98d4041a4cd24c400a4f64.png

http://gyazo.com/3c6533eb47820cefa1a288b31d82f0e3.png

Metamouse

Create a program based on editing history

Program = a set of prodution rules

e.g. If a line touches a rectangle, move the rectangle for the length of the line

Loop operation can be generated

Use geometric constraints (touch, cross, etc.)

Inference errors can be corrected by user

Chimera (Kurlander)

Show editing history and use it later

http://gyazo.com/ab3b00b63c4a6b9ac5fba9fd58d93f90.png

http://gyazo.com/5761803ec7e69458997cc4b71189d7ae.png

Layout By Example (Hudson)

Show layout examples and users select one of them

http://gyazo.com/8b337e894e2863996edb20c7306b790b.png

KidSIM (Cypher)

http://gyazo.com/e3811d24bde71596f7aedef782f60d90.png

KidSIM

Animation generater based on

Use before-after pairs

Graphical Rewrite Rule (GRR)

Fire the rule if the pattern matches

Commercial version of KidSIM

http://gyazo.com/ac046dc993ee300f647599f3ba9e988f.png

Programming env for kids

Use graphical rewrite rule

http://gyazo.com/66a451fefd3be1832a7418b017065fd9.png

http://www.youtube.com/watch?v=0N8cpLHZ41I

https://www.youtube.com/watch?v=kxeaeCajuFc

https://www.youtube.com/watch?v=L0Gg76f60ao

https://www.youtube.com/watch?v=8q-Pbg8sCV0

Use GRR

Fill the gap between operations and texts by inferences

http://gyazo.com/42c5d4b68b126fe6e6eb496167208781.png

Gaps between GUI operations and text representations

http://gyazo.com/da5488a47c80c9fea0bccebc43a50f8e.png

Inference on Agentsheets

http://gyazo.com/3492b4d80cf3b72b3b3af4186c5d2bb5.png

Record user operations on Firefox

Generated macros shared on Wiki

https://www.youtube.com/watch?v=TyQPwPgbRZQ

Interactive evolutional computation

Add interactivety to genetic algorithm

Repeat selecting a good one from generated candidates

Generating the best result

Generating the best algorithm

Graph layout using genetic programming (Masui)

Evaluation function is important on genetic algorithm

Automatically generate evaluation function from examples given by the user

Stochastic method

Generate better solution based on evaluation function}

Generate next solutions stochastically based on previous solutions

No need for layout algorithms

Genetic Algorithm (GA)

Simulated Annealing (SA)

Example of stochastic layout system

VLSI layout using stochastic methods

http://gyazo.com/d552207ae20dbed910c518d59e48e1ea.png

Using stochastic methods for graph layout

Find the best solution which optimizes the evaluation function

http://gyazo.com/8a28ce95b25c9fe78d8f583114577fc6.png

Problems of stochastic methods

Slow

Best solution is not always generated

Hard to define good evaluation function

Constraints and evaluation are not the same

Example: Find a "nice" point in a rectangle

What evaluation function is suitable?

https://gyazo.com/340109116a80ef84b0a7e370be9cc736

http://gyazo.com/d03154eeb529d6cbddf7862010e7fc8a.png

http://gyazo.com/bf06f4b7382f172adc55fea9f02350ef.png

Demonstration-based approach

Create an evaluation function by giving examples

Users only judge good/bad

Generating an evaluation function from the judgement

Method

Give good/bad layout examples

Find an evaluation function which can judge good/bad

Use the function for further layout using GA

Given layouts to the system

http://gyazo.com/c203269a8abf8cd58ea730b9c119fe4f.png

Generated evaluation function

(ADD (SUB (ADD (MUL (MUL (MUL (ADD (ADD (ADD SUM(diry) SUM(minangle)) (ADD 44.00 69.00)) (MUL 43.00 MIN(diry))) 5.00) (ADD (ABS MAX(minangle) MIN(dist)) (ADD (ABS 74.00 MIN(dirx)) (ABS 15.00 SUM(locx))))) SUM(minangle)) (MUL 12.00 (CMP (DIV 57.00 MIN(locx)) (CMP 94.00 MIN(intersec))))) (DIV (ABS (MUL (SUB SUM(locy) 27.00) (CMP 28.00 65.00)) 62.00) SUM(dirx))) (CMP (ABS (DIV 67.00 SUM(locy)) (CMP (ABS (ABS 73.00 (CMP 67.00 SUM(dist))) MIN(intersec)) (ABS MIN(dist) MIN(diry)))) MIN(diry)))

Layout calculated by the evaluation function

http://gyazo.com/bb72e5ebf630d30e1ddc8fff69b13a74.png

Evolutional art

Artificial selection by users

Biomorph (Richard Dawkins)

Galapagos (Karl Sims)

sbart (Unemi)

Biomorph

by Richard Dawkins

Artificial evolution by users

Select a good child from ramdomly-generated children

Evolution of Biomorph

https://gyazo.com/189863961ab4de620dab6d570ac8dfd9

http://i.gyazo.com/f16acd4cabf8e9bcd10b11fcfa92b1be.png

Result

http://images.digopaul.com/wp-content/uploads/related_images/2015/09/10/biomorph_3.jpg

Galapagos (Sims)

Presented at NTT ICC

Select one from 9 examples

http://gyazo.com/922ac4cc0136595f718209c81e6d4874.png

Results of the evolution

http://gyazo.com/3ffc4dfce6ee255512e690f4939d3306.png

http://gyazo.com/356252a15a0243c5915b83662c2047a0.png

sbart (Unemi)

http://gyazo.com/06cb5d773b1add3e24775950e0fa5ab3.png

Current status of PBE

Useful systems are rare

Often easier to write programs than using PBEs

Generalization/inferencing is difficult

Full of heuristics

Correction by users

Fear from users

Requirements

Better than non-PBE

Worth extra work for giving examples

Users can expect the result

Users don't have fears

Don't interrupt users who don't use PBE

No fatal risk from wrong guess

Users are not surprised by the behavior

Cannot be used for complicated work

Better write a program than using PBE

Criticism from Bonnie Nardi

No loops and conditionals

Examples should be correct

Difficult to correct errors

Inference is difficult

Future of PBE

Using PBE in the real-world

Using PBE with search systems

Using PBE for text input systems

Using PBE in the real-world

Use contexts as examples

Use a smart phone at a station

Create a program

Run a probram based on the context

Select an application

based on history

Real-world programming

Create a program based on sensor information

Integration with search systems

Give examples to original dictionary

e.g. Japanese text input

Selected words are added to system dictionary

Conclusion

Various PBE systems are getting popular slowly

Graphical PBE, real-world PBE are promising