WEBVTT

1
00:00:16.167 --> 00:00:19.316
<v ->How are you doing everyone?</v>

2
00:00:19.316 --> 00:00:22.391
We're getting started, so thanks for coming to the first

3
00:00:22.391 --> 00:00:25.684
distinguished lecture of the fall semester.

4
00:00:25.684 --> 00:00:28.086
We have a really great series of speakers this fall.

5
00:00:28.086 --> 00:00:30.270
It's my pleasure to introduce our first speaker,

6
00:00:30.270 --> 00:00:33.102
Sumit Gulwani from Microsoft Research.

7
00:00:33.102 --> 00:00:36.435
Sumit is a Senior Researcher at Redmond.

8
00:00:38.175 --> 00:00:42.651
He got his PhD from Berkeley in 2005 and actually won

9
00:00:42.651 --> 00:00:46.634
the Sigplan Inaugural Dissertation Award.

10
00:00:46.634 --> 00:00:50.047
Sumit has done lots of amazing work on program verification

11
00:00:50.047 --> 00:00:52.689
and program synthesis.

12
00:00:52.689 --> 00:00:56.349
He's got lots of awards, too many to list them all.

13
00:00:56.349 --> 00:00:59.867
Suffice it to say, he's been involved in a lot of the

14
00:00:59.867 --> 00:01:02.934
recent breakthroughs in program synthesis,

15
00:01:02.934 --> 00:01:05.492
which has been a dream for 30 years,

16
00:01:05.492 --> 00:01:08.156
and now it's finally coming into reality,

17
00:01:08.156 --> 00:01:10.001
which is really exciting.

18
00:01:10.001 --> 00:01:12.057
So as some evidence of this,

19
00:01:12.057 --> 00:01:14.715
I was looking at Sumit's list of publications,

20
00:01:14.715 --> 00:01:18.205
and I was amazed he actually had two communications

21
00:01:18.205 --> 00:01:21.025
and research highlights in one issue

22
00:01:21.025 --> 00:01:23.807
which I didn't realize was possible before.

23
00:01:23.807 --> 00:01:25.885
So there are only about 24 of these a year,

24
00:01:25.885 --> 00:01:27.516
and so he had two at once.

25
00:01:27.516 --> 00:01:31.027
I think that suggests the strength of his work.

26
00:01:31.027 --> 00:01:34.625
And one of the research highlights was on this

27
00:01:34.625 --> 00:01:38.258
new feature in Microsoft Excel called Flash Fill

28
00:01:38.258 --> 00:01:41.387
that he's gonna actually demo for us today.

29
00:01:41.387 --> 00:01:45.015
And this is really an amazing story

30
00:01:45.015 --> 00:01:48.932
of doing work that's foundational and very deep

31
00:01:50.237 --> 00:01:53.950
and taking it all the way to a pool that's actually

32
00:01:53.950 --> 00:01:56.950
deployed and came out in Excel 2013.

33
00:01:58.116 --> 00:02:00.164
So that's pretty incredible.

34
00:02:00.164 --> 00:02:02.814
So that feature has received lots of praise

35
00:02:02.814 --> 00:02:05.431
from Wired magazine, UC magazine,

36
00:02:05.431 --> 00:02:07.848
lot of these kinds of places.

37
00:02:08.868 --> 00:02:10.785
Although my favorite quote about this

38
00:02:10.785 --> 00:02:12.096
was from CNN Money.

39
00:02:12.096 --> 00:02:15.423
It said "this is Excel 2013's feature

40
00:02:15.423 --> 00:02:18.215
that should have been available years ago.

41
00:02:18.215 --> 00:02:20.628
So apparently it's not good enough to make financial

42
00:02:20.628 --> 00:02:23.202
ground-breaking work, and then register it to practice,

43
00:02:23.202 --> 00:02:27.369
you should have also have been able to time travel.

44
00:02:29.411 --> 00:02:31.510
Some people just aren't grateful.

45
00:02:31.510 --> 00:02:34.861
So today, Sumit is gonna tell us about this work

46
00:02:34.861 --> 00:02:37.444
and (mumbles).

47
00:02:42.938 --> 00:02:46.233
So thank you very much for coming, Sumit.

48
00:02:46.233 --> 00:02:48.483
(applause)

49
00:02:51.420 --> 00:02:53.565
<v ->Hi everyone, and thanks a lot Jack</v>

50
00:02:53.565 --> 00:02:56.683
for the extremely kind and generous introduction,

51
00:02:56.683 --> 00:02:59.785
and thanks Jeff and Mike for inviting me here.

52
00:02:59.785 --> 00:03:01.375
Thanks for being here.

53
00:03:01.375 --> 00:03:04.835
So I will talk about end-user programming and intelligent

54
00:03:04.835 --> 00:03:06.252
tutoring systems.

55
00:03:07.452 --> 00:03:10.210
And the thing that connects these two areas

56
00:03:10.210 --> 00:03:13.443
is this technology that I call program synthesis.

57
00:03:13.443 --> 00:03:16.061
So there have been lots of people who have participated

58
00:03:16.061 --> 00:03:20.228
but there are too many for me to put them up on the slide.

59
00:03:21.217 --> 00:03:23.144
You can see the names

60
00:03:23.144 --> 00:03:26.395
when I talk about selected topics.

61
00:03:26.395 --> 00:03:28.803
Let met start by talking about,

62
00:03:28.803 --> 00:03:32.059
this is an introduction about what program synthesis is.

63
00:03:32.059 --> 00:03:35.752
So the goal of program synthesis is to synthesize

64
00:03:35.752 --> 00:03:39.601
a program in some underlying domain-specific languages.

65
00:03:39.601 --> 00:03:43.089
From the user's intent that the user has specified

66
00:03:43.089 --> 00:03:46.966
in some form and using some kind of search algorithm.

67
00:03:46.966 --> 00:03:50.230
That search algorithm is to translate the user's intent

68
00:03:50.230 --> 00:03:52.377
to an appropriate program underlying

69
00:03:52.377 --> 00:03:54.163
domain-specific language.

70
00:03:54.163 --> 00:03:56.913
This problem several decades ago,

71
00:03:59.250 --> 00:04:00.083
but today it has become even more important

72
00:04:00.083 --> 00:04:01.833
to revisit this topic

73
00:04:04.015 --> 00:04:06.593
because of variety of computational devices

74
00:04:06.593 --> 00:04:09.409
and platforms that are available today.

75
00:04:09.409 --> 00:04:12.907
Even a seasoned programmer has trouble trying to figure out

76
00:04:12.907 --> 00:04:16.460
or remember the syntax of these different platforms,

77
00:04:16.460 --> 00:04:18.637
what APIs they offer and so on.

78
00:04:18.637 --> 00:04:20.794
But the more interesting thing is today billions of

79
00:04:20.794 --> 00:04:23.419
non-programmers have access to these devices,

80
00:04:23.419 --> 00:04:26.178
and they cannot technically program these devices.

81
00:04:26.178 --> 00:04:28.474
So program synthesis can help these end-users

82
00:04:28.474 --> 00:04:30.677
to be able to program these devices.

83
00:04:30.677 --> 00:04:33.242
And the second point, the reason why we want to revisit

84
00:04:33.242 --> 00:04:36.615
this topic today is that the enabling technology

85
00:04:36.615 --> 00:04:39.938
to make program synthesis a reality is now available

86
00:04:39.938 --> 00:04:43.500
in the form of better search algorithms and even

87
00:04:43.500 --> 00:04:44.833
faster machines.

88
00:04:45.948 --> 00:04:48.086
In fact, segment of the search algorithms

89
00:04:48.086 --> 00:04:52.077
that we'll use in this work are very easily (mumbles)

90
00:04:52.077 --> 00:04:56.244
so this is a good application for the multi-cores.

91
00:04:57.246 --> 00:04:59.765
So I'll start with this disclaimer that we can synthesize

92
00:04:59.765 --> 00:05:02.319
today programs of size 10 to 20.

93
00:05:02.319 --> 00:05:05.667
It's obviously (mumbles) that I'm talking about.

94
00:05:05.667 --> 00:05:07.668
But my goal in this talk is to convince you

95
00:05:07.668 --> 00:05:10.585
that this itself is a revolutionary capability.

96
00:05:10.585 --> 00:05:13.331
If you target the right set of application domains

97
00:05:13.331 --> 00:05:16.219
and you provide the right intent specification mechanism

98
00:05:16.219 --> 00:05:17.552
to the end-user.

99
00:05:19.802 --> 00:05:23.260
So there can be several kinds of users who can benefit

100
00:05:23.260 --> 00:05:25.095
from the synthesis technology.

101
00:05:25.095 --> 00:05:27.675
At the very top of the pyramid is the right algorithm

102
00:05:27.675 --> 00:05:29.782
designers and software developers.

103
00:05:29.782 --> 00:05:33.822
(mumbles) a lot of work to cater to these kinds

104
00:05:33.822 --> 00:05:37.287
of people and we could synthesize a variety of programs

105
00:05:37.287 --> 00:05:40.742
in domains ranging from bit-vector algorithms,

106
00:05:40.742 --> 00:05:43.075
SIMD versions of algorithms,

107
00:05:44.815 --> 00:05:46.826
even some algorithms that you might find

108
00:05:46.826 --> 00:05:50.137
in undergraduate textbooks like sorting or spacing

109
00:05:50.137 --> 00:05:52.135
software you can algorithm.

110
00:05:52.135 --> 00:05:55.401
We could even synthesize program inverses, regular

111
00:05:55.401 --> 00:05:58.873
serializer we can automatically synthesize the deserializer.

112
00:05:58.873 --> 00:06:02.142
We can even synthesize some graph algorithms.

113
00:06:02.142 --> 00:06:03.641
When you think about it,

114
00:06:03.641 --> 00:06:05.976
this is a revolutionary impact that I'm talking about.

115
00:06:05.976 --> 00:06:07.857
Would this help the common man?

116
00:06:07.857 --> 00:06:09.848
Most of these algorithms are already known,

117
00:06:09.848 --> 00:06:12.129
and even if we can synthesize algorithms,

118
00:06:12.129 --> 00:06:15.996
this is not figured out impact-driven algorithms

119
00:06:15.996 --> 00:06:17.052
all the time.

120
00:06:17.052 --> 00:06:19.790
That led us to invest into people who are at the

121
00:06:19.790 --> 00:06:22.131
bottom part of this pyramid who are end-users

122
00:06:22.131 --> 00:06:23.406
or non-programmers.

123
00:06:23.406 --> 00:06:26.454
So enabling non-programmers to even program computers,

124
00:06:26.454 --> 00:06:29.173
it can be one of the most practical useful applications

125
00:06:29.173 --> 00:06:31.825
of this technology today.

126
00:06:31.825 --> 00:06:34.589
And in the latter part of my talk, I will show how similar

127
00:06:34.589 --> 00:06:37.161
technology can also be applied to the students and teachers

128
00:06:37.161 --> 00:06:39.994
in several educational activities.

129
00:06:41.502 --> 00:06:43.453
So this is the outline of this talk.

130
00:06:43.453 --> 00:06:45.885
In the first half, I will talk about different kinds

131
00:06:45.885 --> 00:06:48.391
of end-user programming applications,

132
00:06:48.391 --> 00:06:51.301
and first I will focus on programming by example

133
00:06:51.301 --> 00:06:54.313
and then I will talk about programming by natural language,

134
00:06:54.313 --> 00:06:56.338
because these end-users cannot

135
00:06:56.338 --> 00:06:58.386
write logical specifications, right?

136
00:06:58.386 --> 00:07:00.571
But they can easily express their intent using this

137
00:07:00.571 --> 00:07:02.377
other specification mechanisms like examples

138
00:07:02.377 --> 00:07:03.753
and natural languages.

139
00:07:03.753 --> 00:07:06.400
And the challenge is how you work with them to resolve

140
00:07:06.400 --> 00:07:09.586
any ambiguity that might be there in these specifications.

141
00:07:09.586 --> 00:07:11.554
And in the latter half of the talk, I will focus on

142
00:07:11.554 --> 00:07:13.217
intelligent tutoring systems,

143
00:07:13.217 --> 00:07:15.267
where I will talk in particular

144
00:07:15.267 --> 00:07:17.065
about automatically generating practice problems

145
00:07:17.065 --> 00:07:19.665
for students and how to give feedback to students

146
00:07:19.665 --> 00:07:21.415
on their assignments.

147
00:07:22.718 --> 00:07:25.064
So this is the kind of general methodology that we use

148
00:07:25.064 --> 00:07:26.763
for end-user programming.

149
00:07:26.763 --> 00:07:30.930
First we need to identify important domain of tasks,

150
00:07:31.930 --> 00:07:35.396
that you apply programs and this technology to.

151
00:07:35.396 --> 00:07:36.229
So this is a domain of tasks

152
00:07:36.229 --> 00:07:38.674
that a lot of users struggle with.

153
00:07:38.674 --> 00:07:42.377
So one recipe for doing this is to go and study headquarters

154
00:07:42.377 --> 00:07:44.497
which is what I did when I did some of this research,

155
00:07:44.497 --> 00:07:46.157
to see what are the kinds of tasks that end-users

156
00:07:46.157 --> 00:07:47.707
are struggling with.

157
00:07:47.707 --> 00:07:50.621
Then try to design a domain-specific language

158
00:07:50.621 --> 00:07:52.821
that can completely and succinctly describe

159
00:07:52.821 --> 00:07:55.421
the tasks in this domain.

160
00:07:55.421 --> 00:07:57.359
So there's a tension between how you design this

161
00:07:57.359 --> 00:07:58.664
domain-specific language.

162
00:07:58.664 --> 00:08:01.530
So I want it to be explicit enough so that it can express

163
00:08:01.530 --> 00:08:05.507
a variety of tasks that users are struggling with.

164
00:08:05.507 --> 00:08:07.040
But on the other hand,

165
00:08:07.040 --> 00:08:09.277
you want this domain-specific language

166
00:08:09.277 --> 00:08:11.029
to be restricted enough so that you can do

167
00:08:11.029 --> 00:08:13.475
(mumbles) synthesis for this language.

168
00:08:13.475 --> 00:08:16.003
So that's why you will not always choose a pretty complete

169
00:08:16.003 --> 00:08:18.202
language like C to do your programming.

170
00:08:18.202 --> 00:08:21.082
Then once the domain-specific language is there,

171
00:08:21.082 --> 00:08:23.073
then you want to develop the algorithm,

172
00:08:23.073 --> 00:08:24.605
which is effectively the most challenging part

173
00:08:24.605 --> 00:08:25.733
in this process.

174
00:08:25.733 --> 00:08:27.989
That is going to take the user's intent

175
00:08:27.989 --> 00:08:30.480
and it's going to translate that into likely programs

176
00:08:30.480 --> 00:08:32.685
in this domain-specific language.

177
00:08:32.685 --> 00:08:34.963
And you might actually end up with multiple programs

178
00:08:34.963 --> 00:08:36.780
that match the (mumbles) specification that the end-user

179
00:08:36.780 --> 00:08:39.281
might have provided to you, so you want them to rank

180
00:08:39.281 --> 00:08:40.837
these different programs.

181
00:08:40.837 --> 00:08:43.477
And also, in fact, that the user could resolve any

182
00:08:43.477 --> 00:08:45.946
ambiguities that might be present.

183
00:08:45.946 --> 00:08:49.394
So you can see this is quite an intensive set of activities

184
00:08:49.394 --> 00:08:51.419
that you have to go in order to build up

185
00:08:51.419 --> 00:08:53.336
that end-to-end system.

186
00:08:54.851 --> 00:08:57.163
One of the challenges that I mentioned is

187
00:08:57.163 --> 00:08:58.468
how do you resolve

188
00:08:58.468 --> 00:09:02.037
ambiguities in the (under) specification that the user

189
00:09:02.037 --> 00:09:03.471
might have provided?

190
00:09:03.471 --> 00:09:05.302
So I'm going to just list down some options here

191
00:09:05.302 --> 00:09:07.175
and you will see some of these things coming up

192
00:09:07.175 --> 00:09:08.856
in my demo that I'm going to show you

193
00:09:08.856 --> 00:09:11.498
after what I'm going to talk about.

194
00:09:11.498 --> 00:09:15.125
So very simple things that a user can actually inspect

195
00:09:15.125 --> 00:09:18.503
the results of the program synthesizer on some given input

196
00:09:18.503 --> 00:09:21.178
and then see what's wrong and then accordingly,

197
00:09:21.178 --> 00:09:23.954
provide more examples or refine their natural language

198
00:09:23.954 --> 00:09:26.231
description, this is the most standard, the most elementary

199
00:09:26.231 --> 00:09:28.279
form of abstraction that you can pass to the user.

200
00:09:28.279 --> 00:09:29.928
But there are other things that you can actually

201
00:09:29.928 --> 00:09:31.256
also consider doing.

202
00:09:31.256 --> 00:09:33.231
So the system can actually ask some directed questions

203
00:09:33.231 --> 00:09:34.114
to the user.

204
00:09:34.114 --> 00:09:35.097
So the system can say

205
00:09:35.097 --> 00:09:37.412
"Tell me, what is the output of this input?"

206
00:09:37.412 --> 00:09:39.704
Or refine, rephrase this part in a natural language

207
00:09:39.704 --> 00:09:42.598
that you can actually as I mentioned.

208
00:09:42.598 --> 00:09:45.192
In some systems, in some cases, domains you will realize

209
00:09:45.192 --> 00:09:47.540
that if you choose random examples, then you get

210
00:09:47.540 --> 00:09:51.443
obviously guarantees on the correctness of the synthesizer.

211
00:09:51.443 --> 00:09:54.171
Then the system can also use some machine learning

212
00:09:54.171 --> 00:09:57.910
techniques to all the solutions in some ranked order.

213
00:09:57.910 --> 00:10:00.411
In fact, the user can take a solution that the system

214
00:10:00.411 --> 00:10:05.214
has provided and can start adapting it to other languages.

215
00:10:05.214 --> 00:10:07.447
We can also paraphrase the solution that the system

216
00:10:07.447 --> 00:10:09.004
produces in natural language.

217
00:10:09.004 --> 00:10:11.063
So there's a variety of techniques that you can use

218
00:10:11.063 --> 00:10:13.479
to impact that the user could resolve any ambiguities

219
00:10:13.479 --> 00:10:16.729
that might be there in the synthesizer.

220
00:10:17.890 --> 00:10:20.049
And one of the challenges is that

221
00:10:20.049 --> 00:10:22.444
what search techniques do you use (mumbles)

222
00:10:22.444 --> 00:10:26.509
(under) specification of the user into programs

223
00:10:26.509 --> 00:10:29.467
in the underlying domain-specific language?

224
00:10:29.467 --> 00:10:31.896
So this is a case where I personally write explanations

225
00:10:31.896 --> 00:10:34.124
from various areas in computer science,

226
00:10:34.124 --> 00:10:37.828
including Formal Methods, this is my own area of expertise

227
00:10:37.828 --> 00:10:41.995
where we try to leverage the SAT/SMT solvers.

228
00:10:44.638 --> 00:10:48.509
We can also consider using some goal-directed search,

229
00:10:48.509 --> 00:10:51.197
that is common in the AI community.

230
00:10:51.197 --> 00:10:54.628
Some of the techniques that we have used have also

231
00:10:54.628 --> 00:10:58.436
inspired by the area called Version space algebras

232
00:10:58.436 --> 00:11:01.518
which are popular in the Machine Learning community.

233
00:11:01.518 --> 00:11:03.730
There are some algorithms that we'll talk about also

234
00:11:03.730 --> 00:11:07.681
from randomized algorithms in the Theory community.

235
00:11:07.681 --> 00:11:09.611
Then I will also show you one slide,

236
00:11:09.611 --> 00:11:13.075
how we can use the Web to actually find some context

237
00:11:13.075 --> 00:11:14.492
for the end-user.

238
00:11:16.402 --> 00:11:18.584
And then techniques from Natural Language Understanding

239
00:11:18.584 --> 00:11:22.823
also values the space and then comes to the

240
00:11:22.823 --> 00:11:26.659
With this kind of introduction to end-user programming,

241
00:11:26.659 --> 00:11:29.979
then we now go into a little bit more depth on

242
00:11:29.979 --> 00:11:32.563
programming by example.

243
00:11:32.563 --> 00:11:35.877
So I'm gonna talk about spreadsheet macros,

244
00:11:35.877 --> 00:11:38.622
and let us start out with the demo,

245
00:11:38.622 --> 00:11:42.048
and then I will talk a little more about the technique

246
00:11:42.048 --> 00:11:43.465
at the end of it.

247
00:11:49.138 --> 00:11:52.730
So how many of you have used a spreadsheet cell before?

248
00:11:52.730 --> 00:11:54.426
Quite a few of you, good.

249
00:11:54.426 --> 00:11:56.099
Very good, it's okay, now it's been

250
00:11:56.099 --> 00:11:58.266
(mumbles)

251
00:12:02.526 --> 00:12:05.430
So writing down social security numbers in the first column

252
00:12:05.430 --> 00:12:07.943
that you want to format by (mumbles)

253
00:12:07.943 --> 00:12:10.146
that you see in the second column.

254
00:12:10.146 --> 00:12:12.419
So what I'm going to do is to do it,

255
00:12:12.419 --> 00:12:13.779
but also if you have

256
00:12:13.779 --> 00:12:16.170
(mumbles) spreadsheet.

257
00:12:16.170 --> 00:12:17.836
In a moment, if you can do this,

258
00:12:17.836 --> 00:12:19.522
you can write an Excel macro.

259
00:12:19.522 --> 00:12:20.532
You need a step

260
00:12:20.532 --> 00:12:23.345
that can authorize this task for you.

261
00:12:23.345 --> 00:12:27.512
But then, for a non-programmer, then you're stuck.

262
00:12:29.511 --> 00:12:30.917
So this new feature,

263
00:12:30.917 --> 00:12:33.305
the latest in Excel called Flash Fill,

264
00:12:33.305 --> 00:12:37.000
you can do this task as the example that I've done.

265
00:12:37.000 --> 00:12:40.033
So this is the example that we are provided.

266
00:12:40.033 --> 00:12:42.950
(mumbles) program.

267
00:12:44.426 --> 00:12:47.676
(mumbles) spreadsheet.

268
00:12:53.572 --> 00:12:55.004
But what if you are a user who does not even know

269
00:12:55.004 --> 00:12:56.630
that this feature exists?

270
00:12:56.630 --> 00:12:59.530
Well, you just (mumbles) task.

271
00:12:59.530 --> 00:13:01.838
So let's say I want to extract this here.

272
00:13:01.838 --> 00:13:03.801
So I'll give you an example.

273
00:13:03.801 --> 00:13:05.112
In a moment I'll start

274
00:13:05.112 --> 00:13:06.861
and give you a second example.

275
00:13:06.861 --> 00:13:09.028
(mumbles)

276
00:13:11.325 --> 00:13:13.942
You need to know that this feature actually exists

277
00:13:13.942 --> 00:13:15.789
and that's an auto property of Excel

278
00:13:15.789 --> 00:13:18.039
(mumbles).

279
00:13:20.322 --> 00:13:22.124
Now, in general, this would be difficult

280
00:13:22.124 --> 00:13:24.315
to teach the user from this one example,

281
00:13:24.315 --> 00:13:28.377
but examples are specification (mumbles).

282
00:13:28.377 --> 00:13:29.896
So in this scenario,

283
00:13:29.896 --> 00:13:32.592
we have a bunch of medical billing codes,

284
00:13:32.592 --> 00:13:34.473
some of which have a right bracket at the end

285
00:13:34.473 --> 00:13:36.210
as you see in row six through row ten,

286
00:13:36.210 --> 00:13:38.813
some of which don't have a right bracket.

287
00:13:38.813 --> 00:13:40.946
Suppose that you want to add a right bracket

288
00:13:40.946 --> 00:13:43.355
where it is missing.

289
00:13:43.355 --> 00:13:45.499
So if you give the example as I've given,

290
00:13:45.499 --> 00:13:47.879
and the system comes up with a simpler specification

291
00:13:47.879 --> 00:13:49.978
(mumbles)

292
00:13:49.978 --> 00:13:53.486
Maybe this is what you wanted, and then you are done.

293
00:13:53.486 --> 00:13:56.062
But row six through row ten are incorrect.

294
00:13:56.062 --> 00:13:58.123
So you can fix any one of these.

295
00:13:58.123 --> 00:13:59.432
So if I fix row eight, if I fix that,

296
00:13:59.432 --> 00:14:01.683
then it does the same thing.

297
00:14:01.683 --> 00:14:05.333
For example, it will be able to better generalize

298
00:14:05.333 --> 00:14:07.940
the intent that I have

299
00:14:07.940 --> 00:14:11.843
and be able to complete the task for me.

300
00:14:11.843 --> 00:14:13.611
So this technology that we use

301
00:14:13.611 --> 00:14:15.816
to extract (mumbles).

302
00:14:15.816 --> 00:14:18.419
In this case, I have (mumbles).

303
00:14:18.419 --> 00:14:20.752
I will go to the elements to

304
00:14:24.319 --> 00:14:26.486
(mumbles)

305
00:14:30.256 --> 00:14:32.786
You can rearrange most of the programs.

306
00:14:32.786 --> 00:14:35.241
In this case, I want to enter a new application.

307
00:14:35.241 --> 00:14:37.107
I'll give you an example

308
00:14:37.107 --> 00:14:39.357
that we'll discuss as well.

309
00:14:40.807 --> 00:14:43.557
So this is my final example here.

310
00:14:44.845 --> 00:14:48.845
So what do you think (mumbles)?

311
00:14:52.168 --> 00:14:54.457
<v Audience Member>What was the question?</v>

312
00:14:54.457 --> 00:14:58.487
<v ->What do you think is the intent there?</v>

313
00:14:58.487 --> 00:15:01.371
<v Audience Member>Row two.</v>

314
00:15:01.371 --> 00:15:03.290
<v ->Row two, okay, so here.</v>

315
00:15:03.290 --> 00:15:07.290
What do you think is (mumbles)?

316
00:15:10.727 --> 00:15:12.202
(mumbles)

317
00:15:12.202 --> 00:15:16.369
And here also you can guess (mumbles).

318
00:15:19.614 --> 00:15:22.864
So what do you think is happening here?

319
00:15:25.487 --> 00:15:28.570
(mumbles) row seven.

320
00:15:35.141 --> 00:15:37.724
But maybe this is not what you want.

321
00:15:37.724 --> 00:15:39.619
Maybe you want the first name

322
00:15:39.619 --> 00:15:41.689
and the first two letters of the last name.

323
00:15:41.689 --> 00:15:43.939
Then you just go like this.

324
00:15:48.654 --> 00:15:52.531
What do you think is happening in the last column?

325
00:15:52.531 --> 00:15:54.370
The system is smart enough to figure out

326
00:15:54.370 --> 00:15:56.474
that the small F is not coming from the last two Fs

327
00:15:56.474 --> 00:15:57.941
in Jeff's first name.

328
00:15:57.941 --> 00:16:01.524
So the emphasis (mumbles).

329
00:16:08.039 --> 00:16:09.539
So the next thing.

330
00:16:12.240 --> 00:16:15.907
So the first challenge to find this problem,

331
00:16:17.972 --> 00:16:20.283
we have to see the Excel byproducts.

332
00:16:20.283 --> 00:16:21.816
So once I define this problem,

333
00:16:21.816 --> 00:16:23.817
I go to (mumbles),

334
00:16:23.817 --> 00:16:25.886
that can express most of these tasks.

335
00:16:25.886 --> 00:16:28.050
So the programs that we synthesize here

336
00:16:28.050 --> 00:16:30.510
come from the domain specific language.

337
00:16:30.510 --> 00:16:33.229
So we have our conditions at the very top,

338
00:16:33.229 --> 00:16:36.141
and you don't know which one (mumbles).

339
00:16:36.141 --> 00:16:37.762
So we have a segment,

340
00:16:37.762 --> 00:16:40.132
then we have the Boolean Expression b.

341
00:16:40.132 --> 00:16:42.299
(mumbles)

342
00:16:47.975 --> 00:16:52.142
that checks how many times (mumbles).

343
00:17:00.715 --> 00:17:02.532
And then the next expressions,

344
00:17:02.532 --> 00:17:04.252
which are called trace expressions,

345
00:17:04.252 --> 00:17:08.252
are simply a confabulation of other expressions.

346
00:17:09.102 --> 00:17:11.269
(mumbles)

347
00:17:13.544 --> 00:17:16.885
So this is actually specified by the byproducts

348
00:17:16.885 --> 00:17:19.809
from which you want to extract the substring.

349
00:17:19.809 --> 00:17:21.736
And the position expressions

350
00:17:21.736 --> 00:17:24.486
which (mumbles).

351
00:17:29.783 --> 00:17:33.367
For our use, the condition expressions are specified.

352
00:17:33.367 --> 00:17:34.758
So condition expressions

353
00:17:34.758 --> 00:17:37.327
or index expressions can be a constant,

354
00:17:37.327 --> 00:17:40.244
or it is this interesting construct

355
00:17:42.226 --> 00:17:45.484
which takes the expressions (mumbles).

356
00:17:45.484 --> 00:17:49.225
So what it does, is it matches that position in the string

357
00:17:49.225 --> 00:17:53.300
such that the left side of the position.

358
00:17:53.300 --> 00:17:55.527
In fact, a suffix of the left side of the solution

359
00:17:55.527 --> 00:17:57.326
matches with r1

360
00:17:57.326 --> 00:17:59.756
and the right side of the position.

361
00:17:59.756 --> 00:18:03.839
So we want to size up (mumbles).

362
00:18:06.877 --> 00:18:08.973
And the expressions are simply

363
00:18:08.973 --> 00:18:13.140
some combinations of predefined (mumbles).

364
00:18:17.165 --> 00:18:19.819
So this is some different from usual.

365
00:18:19.819 --> 00:18:22.212
So let's say the Boolean substring of s

366
00:18:22.212 --> 00:18:25.399
is specified by two expressions, p and p'.

367
00:18:25.399 --> 00:18:27.785
And on this blue line, there is s,

368
00:18:27.785 --> 00:18:30.330
and let's say this p is a solution.

369
00:18:30.330 --> 00:18:31.866
And the left side of p,

370
00:18:31.866 --> 00:18:33.622
in fact the suffix of the left side of p

371
00:18:33.622 --> 00:18:35.955
matches with the r1

372
00:18:35.955 --> 00:18:38.462
and the right side of p matches with r2.

373
00:18:38.462 --> 00:18:42.363
So the left side of p' matches with r1' and so on.

374
00:18:42.363 --> 00:18:46.025
And then (mumbles).

375
00:18:46.025 --> 00:18:48.511
So therefore, look at the two special cases here.

376
00:18:48.511 --> 00:18:51.727
How do I occupy my (mumbles)

377
00:18:51.727 --> 00:18:53.491
that didn't match anything?

378
00:18:53.491 --> 00:18:55.293
So this is really describing the property

379
00:18:55.293 --> 00:18:57.969
of the assumption that you are (mumbles).

380
00:18:57.969 --> 00:18:59.761
And we often have cases

381
00:18:59.761 --> 00:19:02.429
where r1 and r2 (mumbles),

382
00:19:02.429 --> 00:19:05.512
so this is describing the boundaries.

383
00:19:06.812 --> 00:19:09.859
But now we mix and match all the strings

384
00:19:09.859 --> 00:19:12.109
(mumbles).

385
00:19:13.622 --> 00:19:16.494
So this is really what language design is.

386
00:19:16.494 --> 00:19:20.077
Designs are for (mumbles).

387
00:19:23.305 --> 00:19:26.592
So this is my example that I want to have.

388
00:19:26.592 --> 00:19:28.759
(mumbles)

389
00:19:30.274 --> 00:19:33.774
So the program (mumbles).

390
00:19:35.082 --> 00:19:37.249
(mumbles)

391
00:19:43.582 --> 00:19:47.165
So let's say you have 40 property examples.

392
00:19:48.592 --> 00:19:52.106
And you want to synthesize program b

393
00:19:52.106 --> 00:19:56.545
that uses the substrings of all these examples.

394
00:19:56.545 --> 00:19:59.249
So what we do is we see one set of programs

395
00:19:59.249 --> 00:20:02.249
that are (mumbles).

396
00:20:03.321 --> 00:20:05.843
So let that set be s1.

397
00:20:05.843 --> 00:20:08.311
Then I want to compute a set of one programs.

398
00:20:08.311 --> 00:20:10.478
(mumbles)

399
00:20:13.663 --> 00:20:15.805
And that will be intersecting sets.

400
00:20:15.805 --> 00:20:17.659
So the intersection is not at p,

401
00:20:17.659 --> 00:20:20.492
then I (mumbles).

402
00:20:23.589 --> 00:20:25.233
The key challenge here is that

403
00:20:25.233 --> 00:20:27.949
the number of programs that we have may be huge.

404
00:20:27.949 --> 00:20:30.116
(mumbles)

405
00:20:45.036 --> 00:20:49.345
And now let's say one of the sets is empty.

406
00:20:49.345 --> 00:20:50.970
Then what we do is we try to find

407
00:20:50.970 --> 00:20:53.485
the smallest partition of these sets

408
00:20:53.485 --> 00:20:57.516
so that the intersection of the sets (mumbles).

409
00:20:57.516 --> 00:21:00.849
So let's say (mumbles).

410
00:21:03.145 --> 00:21:05.391
So this gives us ideas about how to synthesize

411
00:21:05.391 --> 00:21:08.724
that control (mumbles).

412
00:21:11.494 --> 00:21:14.810
So you want to be able to partition these sets,

413
00:21:14.810 --> 00:21:18.642
and then (mumbles).

414
00:21:18.642 --> 00:21:20.809
(mumbles)

415
00:21:33.326 --> 00:21:34.775
So what about ranking?

416
00:21:34.775 --> 00:21:36.785
Because we work with lots of programs,

417
00:21:36.785 --> 00:21:38.280
so we want to be working

418
00:21:38.280 --> 00:21:40.706
with a program that is (mumbles).

419
00:21:40.706 --> 00:21:43.504
So here's two kinds of (mumbles).

420
00:21:43.504 --> 00:21:46.044
So we prefer programs that are short,

421
00:21:46.044 --> 00:21:48.163
so fewer number of conditionals,

422
00:21:48.163 --> 00:21:50.506
shorter expressions and so on.

423
00:21:50.506 --> 00:21:51.984
But at the same time,

424
00:21:51.984 --> 00:21:54.045
you also need to prefer programs

425
00:21:54.045 --> 00:21:56.545
with less number of constants.

426
00:22:08.398 --> 00:22:09.951
So with these two principles,

427
00:22:09.951 --> 00:22:11.229
we're able to make

428
00:22:11.229 --> 00:22:12.761
(mumbles)

429
00:22:12.761 --> 00:22:14.544
Some are a little more tricky,

430
00:22:14.544 --> 00:22:16.739
so let me show you some examples of that.

431
00:22:16.739 --> 00:22:19.103
So, the baseline strategy,

432
00:22:19.103 --> 00:22:21.794
you want to pick any minimal sized program

433
00:22:21.794 --> 00:22:23.892
using a minimal number of constants.

434
00:22:23.892 --> 00:22:25.864
Then you try to use some manual schemes

435
00:22:25.864 --> 00:22:28.899
to break conflicts using a weighted score

436
00:22:28.899 --> 00:22:30.510
of various program features.

437
00:22:30.510 --> 00:22:33.333
And then you can use machine learning.

438
00:22:33.333 --> 00:22:36.069
And I will show you what's the best.

439
00:22:36.069 --> 00:22:38.423
So these are some of the examples.

440
00:22:38.423 --> 00:22:40.455
So with baseline,

441
00:22:40.455 --> 00:22:42.096
you just use like 90.

442
00:22:42.096 --> 00:22:44.269
Then you require, for example,

443
00:22:44.269 --> 00:22:45.269
smart tasks.

444
00:22:47.032 --> 00:22:48.659
When you do it manually,

445
00:22:48.659 --> 00:22:51.013
you use lots of other program features

446
00:22:51.013 --> 00:22:54.013
and then (mumbles).

447
00:23:03.251 --> 00:23:07.050
So this is what I call syntactic string transformations.

448
00:23:07.050 --> 00:23:09.240
Now, there are also other string transformations

449
00:23:09.240 --> 00:23:10.964
that are not syntactic.

450
00:23:10.964 --> 00:23:14.366
So I call them semantic string transformations

451
00:23:14.366 --> 00:23:18.533
and then you might want to know number transformations.

452
00:23:22.106 --> 00:23:26.273
But sometimes the data is compromised (mumbles).

453
00:23:29.221 --> 00:23:31.027
So let me show you another video

454
00:23:31.027 --> 00:23:32.638
that's going to walk you through

455
00:23:32.638 --> 00:23:34.232
some of the extensions.

456
00:23:34.232 --> 00:23:37.315
So this is stuff that's not released.

457
00:23:39.134 --> 00:23:42.551
I don't have this installed on my laptop.

458
00:23:53.079 --> 00:23:55.760
<v ->I'm going to show you some testing extensions</v>

459
00:23:55.760 --> 00:23:58.982
of the Flash Fill technology in Excel 2013.

460
00:23:58.982 --> 00:24:01.385
Flash Fill allows you to perform so-called

461
00:24:01.385 --> 00:24:04.299
syntactic transformations on the strings.

462
00:24:04.299 --> 00:24:07.111
I will show you how we can extend this technology

463
00:24:07.111 --> 00:24:10.911
to also perform semantic transformations for the strings.

464
00:24:10.911 --> 00:24:14.225
So consider this table on the right side.

465
00:24:14.225 --> 00:24:17.714
When a user wants to map the item in the first column,

466
00:24:17.714 --> 00:24:20.292
and the second item in the second column,

467
00:24:20.292 --> 00:24:22.343
(mumbles).

468
00:24:22.343 --> 00:24:26.165
So the (mumbles) is not a syntactic transformation

469
00:24:26.165 --> 00:24:28.748
of the new columns on the left.

470
00:24:30.080 --> 00:24:32.380
In fact, by performing this transformation

471
00:24:32.380 --> 00:24:34.628
requires the user to have some macro knowledge

472
00:24:34.628 --> 00:24:38.461
which the user has in a file on the left side.

473
00:24:40.015 --> 00:24:42.882
So in particular, what the user wants to do

474
00:24:42.882 --> 00:24:46.065
is to make additional (mumbles) on the left side

475
00:24:46.065 --> 00:24:47.648
in the item column.

476
00:24:48.566 --> 00:24:51.897
Then index (mumbles)

477
00:24:51.897 --> 00:24:54.458
which I can then put in the label on the right

478
00:24:54.458 --> 00:24:57.708
and extract (mumbles).

479
00:24:58.773 --> 00:25:01.278
Then perform some semantic transformations

480
00:25:01.278 --> 00:25:03.179
such as (mumbles)

481
00:25:03.179 --> 00:25:06.080
or move the dollar sign from the purchase price.

482
00:25:06.080 --> 00:25:09.865
And then move this phone number that you see at the top.

483
00:25:09.865 --> 00:25:12.041
Now, our interesting expansion

484
00:25:12.041 --> 00:25:13.738
can perform all of this

485
00:25:13.738 --> 00:25:16.405
with just the click of a button.

486
00:25:18.114 --> 00:25:19.496
So once you connect

487
00:25:19.496 --> 00:25:21.663
(mumbles)

488
00:25:24.663 --> 00:25:26.029
how to join them,

489
00:25:26.029 --> 00:25:28.446
what qualities to predict on,

490
00:25:31.547 --> 00:25:33.015
the four indexing,

491
00:25:33.015 --> 00:25:34.966
what the solutions look like

492
00:25:34.966 --> 00:25:37.049
after indexing and so on.

493
00:25:38.380 --> 00:25:39.530
The second thing

494
00:25:39.530 --> 00:25:41.697
(mumbles)

495
00:25:44.775 --> 00:25:46.230
So consider that stuff

496
00:25:46.230 --> 00:25:48.980
forming the knowledge to do this.

497
00:25:51.728 --> 00:25:54.648
(mumbles)

498
00:25:54.648 --> 00:25:58.815
Every language has its own syntax for following numbers.

499
00:26:00.545 --> 00:26:04.173
Again, examples are a universal way to express an intent

500
00:26:04.173 --> 00:26:05.748
and you do not need to remember

501
00:26:05.748 --> 00:26:07.331
the latest formula.

502
00:26:09.060 --> 00:26:10.436
A couple of examples

503
00:26:10.436 --> 00:26:12.050
of what you want to do,

504
00:26:12.050 --> 00:26:15.800
and the computer will understand your intent.

505
00:26:18.335 --> 00:26:19.851
It can also be used to

506
00:26:19.851 --> 00:26:22.018
(mumbles)

507
00:26:28.418 --> 00:26:30.585
(mumbles)

508
00:26:35.512 --> 00:26:38.542
Now I'm going to show you something a little bit different

509
00:26:38.542 --> 00:26:40.461
which is about remembering

510
00:26:40.461 --> 00:26:41.848
things that are still

511
00:26:41.848 --> 00:26:44.015
(mumbles)

512
00:26:46.371 --> 00:26:48.038
So in this scenario,

513
00:26:49.694 --> 00:26:53.361
the user wants to (mumbles)

514
00:26:54.602 --> 00:26:56.769
(mumbles)

515
00:26:58.709 --> 00:27:00.195
It has three complications.

516
00:27:00.195 --> 00:27:01.805
In the top left area,

517
00:27:01.805 --> 00:27:03.870
the user wants to

518
00:27:03.870 --> 00:27:06.037
(mumbles)

519
00:27:10.316 --> 00:27:12.816
Furthermore, the user wants to

520
00:27:14.126 --> 00:27:18.126
put all one in red, all two in green, and so on.

521
00:27:19.075 --> 00:27:20.532
(mumbles)

522
00:27:20.532 --> 00:27:22.646
This is exactly how the end-user

523
00:27:22.646 --> 00:27:26.137
describes it to (mumbles).

524
00:27:26.137 --> 00:27:29.075
And the user is willing to pay $20 to anyone

525
00:27:29.075 --> 00:27:32.055
who gives them the script to organize this task.

526
00:27:32.055 --> 00:27:33.501
So now I'm going to show you

527
00:27:33.501 --> 00:27:35.501
how to do this for free.

528
00:27:38.261 --> 00:27:40.428
(mumbles)

529
00:27:45.857 --> 00:27:48.024
(mumbles)

530
00:28:00.781 --> 00:28:02.948
(mumbles)

531
00:28:19.223 --> 00:28:21.306
<v ->So that is one example.</v>

532
00:28:26.983 --> 00:28:28.764
So now I'm going to move on

533
00:28:28.764 --> 00:28:30.676
to another kind of programming,

534
00:28:30.676 --> 00:28:32.517
and that is programming by natural language.

535
00:28:32.517 --> 00:28:34.692
So there's some main tasks explained in the example,

536
00:28:34.692 --> 00:28:36.145
but in certain tasks,

537
00:28:36.145 --> 00:28:39.978
you need to specify (mumbles)

538
00:28:41.149 --> 00:28:43.360
So then we're going to talk a little bit

539
00:28:43.360 --> 00:28:47.180
about programming smartphone scripts.

540
00:28:47.180 --> 00:28:49.285
So these are kinds of smartphone scripts

541
00:28:49.285 --> 00:28:51.452
that people want to write.

542
00:28:53.385 --> 00:28:55.282
So I receive an SMS message

543
00:28:55.282 --> 00:28:57.995
then automatically send the reply "I'm driving"

544
00:28:57.995 --> 00:28:59.162
to the sender.

545
00:29:03.355 --> 00:29:06.597
So a state-of-the-art programming system

546
00:29:06.597 --> 00:29:08.214
for my second set of steps

547
00:29:08.214 --> 00:29:11.464
is actually a visual programming model.

548
00:29:18.340 --> 00:29:21.777
So to ease the life of seasoned programmer,

549
00:29:21.777 --> 00:29:24.194
I (mumbles).

550
00:29:27.343 --> 00:29:29.510
(mumbles)

551
00:29:36.356 --> 00:29:39.898
And this is a part that we can do.

552
00:29:39.898 --> 00:29:42.231
So as you saw in Flash Fill,

553
00:29:43.285 --> 00:29:45.535
(mumbles).

554
00:29:49.200 --> 00:29:51.087
But again, there's no expressive language

555
00:29:51.087 --> 00:29:53.793
that has been generated by (mumbles),

556
00:29:53.793 --> 00:29:56.939
seeing what kinds of scripts it's asking for,

557
00:29:56.939 --> 00:29:58.774
and then designing a language

558
00:29:58.774 --> 00:30:02.119
that can describe most of those aspects.

559
00:30:02.119 --> 00:30:04.786
So what you see in this language

560
00:30:06.426 --> 00:30:08.788
is a part that is going to be

561
00:30:08.788 --> 00:30:11.161
derived from the natural language statement

562
00:30:11.161 --> 00:30:12.781
that the user is going to save,

563
00:30:12.781 --> 00:30:14.806
and then the rest of the green part

564
00:30:14.806 --> 00:30:17.031
is going to be automatically put in

565
00:30:17.031 --> 00:30:18.963
to alert the synthesis technology.

566
00:30:18.963 --> 00:30:22.439
So this is more or less how the technology works.

567
00:30:22.439 --> 00:30:25.122
So the user, let's say, sees this.

568
00:30:25.122 --> 00:30:29.289
The natural language description (mumbles).

569
00:30:30.599 --> 00:30:32.570
So the red components are coming directly

570
00:30:32.570 --> 00:30:35.251
from some (mumbles) in the natural language,

571
00:30:35.251 --> 00:30:38.251
and then (mumbles).

572
00:30:42.588 --> 00:30:43.535
Key insights are

573
00:30:43.535 --> 00:30:46.193
that the script is meticulously laid out

574
00:30:46.193 --> 00:30:50.110
some components and some relationships or data.

575
00:30:52.339 --> 00:30:55.553
And the component is either an API or an Entity

576
00:30:55.553 --> 00:30:57.961
which I define as an API return value

577
00:30:57.961 --> 00:30:59.451
or constant or input.

578
00:30:59.451 --> 00:31:02.744
It is these two things (mumbles).

579
00:31:02.744 --> 00:31:06.411
(mumbles) how this is done.

580
00:31:07.452 --> 00:31:08.942
So we discover these things

581
00:31:08.942 --> 00:31:10.900
using natural language processing techniques

582
00:31:10.900 --> 00:31:12.544
and type-based synthesis.

583
00:31:12.544 --> 00:31:15.294
So we (mumbles).

584
00:31:18.237 --> 00:31:20.404
(mumbles)

585
00:31:24.228 --> 00:31:26.479
The synthesis identity is using feedback

586
00:31:26.479 --> 00:31:30.646
from the processing engine (mumbles).

587
00:31:31.778 --> 00:31:34.063
Once you get here,

588
00:31:34.063 --> 00:31:36.681
we use some (mumbles) to infer missing relations

589
00:31:36.681 --> 00:31:38.546
using type-based synthesis

590
00:31:38.546 --> 00:31:40.713
(mumbles)

591
00:31:42.303 --> 00:31:46.053
So I know in time (mumbles).

592
00:31:47.758 --> 00:31:49.925
(mumbles)

593
00:31:52.967 --> 00:31:54.300
Lots of programs

594
00:31:56.268 --> 00:31:58.768
that we then rank and present.

595
00:32:02.861 --> 00:32:06.122
So let me actually show you a demo right here.

596
00:32:06.122 --> 00:32:07.943
I will play a quick video.

597
00:32:07.943 --> 00:32:10.193
And this demo is not for domain specific language

598
00:32:10.193 --> 00:32:14.360
but other domain specific language called (mumbles)

599
00:32:15.763 --> 00:32:17.930
(mumbles)

600
00:32:25.310 --> 00:32:26.665
<v Man>TouchDevelop</v>

601
00:32:26.665 --> 00:32:29.237
is a touch centric programming environment

602
00:32:29.237 --> 00:32:31.418
on Windows targeting end-users.

603
00:32:31.418 --> 00:32:34.350
It provides AVI interaction over the phone

604
00:32:34.350 --> 00:32:35.350
and sensors.

605
00:32:36.460 --> 00:32:39.832
In TouchDevelop, people program via touch.

606
00:32:39.832 --> 00:32:42.186
Let me show how people create a script

607
00:32:42.186 --> 00:32:44.519
that posts a random photo to the screen

608
00:32:44.519 --> 00:32:45.852
of TouchDevelop.

609
00:32:47.327 --> 00:32:48.906
First, I create a command

610
00:32:48.906 --> 00:32:52.048
to retrieve the random picture.

611
00:32:52.048 --> 00:32:53.850
I navigate over all the choices

612
00:32:53.850 --> 00:32:56.481
to select a random picture from my collection

613
00:32:56.481 --> 00:32:59.233
and save it to a variable.

614
00:32:59.233 --> 00:33:02.613
Next, I need to post a picture to the screen.

615
00:33:02.613 --> 00:33:05.674
I select the variable pick that I just created

616
00:33:05.674 --> 00:33:08.304
and select post to wall.

617
00:33:08.304 --> 00:33:09.845
Now the script is done,

618
00:33:09.845 --> 00:33:12.250
and I can run it directly on my phone.

619
00:33:12.250 --> 00:33:13.390
What I show next

620
00:33:13.390 --> 00:33:17.153
is how to achieve the same thing in our synthesizer.

621
00:33:17.153 --> 00:33:19.872
And you open the synthesizer by hitting the search button

622
00:33:19.872 --> 00:33:22.039
and type, say, post photo.

623
00:33:23.721 --> 00:33:27.306
The synthesizer (mumbles) TouchDevelop's AVIs

624
00:33:27.306 --> 00:33:28.892
and synthesizes additional code

625
00:33:28.892 --> 00:33:31.894
to combine (mumbles).

626
00:33:31.894 --> 00:33:35.190
Since there might be multiple interpretations of the query,

627
00:33:35.190 --> 00:33:37.903
the synthesizer ranks the synthesized (mumbles)

628
00:33:37.903 --> 00:33:40.616
and presents only the top choices.

629
00:33:40.616 --> 00:33:43.799
I can select the top one to insert it into my script,

630
00:33:43.799 --> 00:33:45.890
and I had the exact same script

631
00:33:45.890 --> 00:33:47.661
that I created a moment ago.

632
00:33:47.661 --> 00:33:50.283
Let us move on to another example.

633
00:33:50.283 --> 00:33:52.016
Say I want to play a song.

634
00:33:52.016 --> 00:33:54.942
The intended script is at the top choice.

635
00:33:54.942 --> 00:33:59.056
Or I want to check if I can access my current location,

636
00:33:59.056 --> 00:34:01.389
extract the nearest address,

637
00:34:02.565 --> 00:34:04.482
and post to the screen.

638
00:34:07.102 --> 00:34:10.782
I can also give the key words in a different order,

639
00:34:10.782 --> 00:34:13.782
like to describe a current location.

640
00:34:17.527 --> 00:34:19.934
And I can send this via SMS to my friend

641
00:34:19.934 --> 00:34:23.101
whose phone number I've just typed in.

642
00:34:28.970 --> 00:34:30.634
In this next example,

643
00:34:30.634 --> 00:34:33.136
I want to tint a random photo.

644
00:34:33.136 --> 00:34:35.273
Since I did not specify the tinted color,

645
00:34:35.273 --> 00:34:39.444
the synthesizer uses the default color which is sepia.

646
00:34:39.444 --> 00:34:43.021
However, if I have a color, for example blue,

647
00:34:43.021 --> 00:34:45.271
it will use it immediately.

648
00:34:46.172 --> 00:34:49.944
Now I can save the blue-tinted picture to the library.

649
00:34:49.944 --> 00:34:52.784
In this example, I want to take a picture

650
00:34:52.784 --> 00:34:55.034
and save it to the library.

651
00:34:57.860 --> 00:35:00.882
How about drawing some text on a picture

652
00:35:00.882 --> 00:35:02.632
that I've just taken?

653
00:35:05.763 --> 00:35:08.763
For example, TouchDevelop is so cool

654
00:35:11.778 --> 00:35:12.611
in black,

655
00:35:15.115 --> 00:35:17.532
and save that to the library.

656
00:35:24.468 --> 00:35:28.635
I could also draw the current location to the picture

657
00:35:30.844 --> 00:35:33.083
in a random color.

658
00:35:33.083 --> 00:35:34.947
Note that this system is smart enough

659
00:35:34.947 --> 00:35:39.568
to infer the conversion of location to screen automatic.

660
00:35:39.568 --> 00:35:42.474
It gives feedback to the user's words or phrases

661
00:35:42.474 --> 00:35:44.592
that it does not understand.

662
00:35:44.592 --> 00:35:46.605
Suppose I entered a color pink

663
00:35:46.605 --> 00:35:49.500
and TouchDevelop does not have any matching AVI

664
00:35:49.500 --> 00:35:53.667
and the synthesizer performs the schematic for me.

665
00:35:55.486 --> 00:35:57.806
The synthesizer also synthesizes code

666
00:35:57.806 --> 00:36:01.149
that is relevant to the current program context.

667
00:36:01.149 --> 00:36:02.577
In this new script,

668
00:36:02.577 --> 00:36:05.705
I have a global variable n of (mumbles)

669
00:36:05.705 --> 00:36:08.034
and a function Fibo that takes the number

670
00:36:08.034 --> 00:36:09.701
and returns to them.

671
00:36:10.575 --> 00:36:13.486
In the main function, I have two local variables,

672
00:36:13.486 --> 00:36:16.024
x and (mumbles).

673
00:36:16.024 --> 00:36:19.607
Now I want to call the function Fibo is 10.

674
00:36:23.645 --> 00:36:26.145
Or with the global variable n.

675
00:36:27.885 --> 00:36:29.468
Or with n plus ten.

676
00:36:30.490 --> 00:36:35.449
The synthesizer presents the two most likely options.

677
00:36:35.449 --> 00:36:38.782
Since x is a phone number, I round it

678
00:36:40.067 --> 00:36:42.400
perhaps two or three inches,

679
00:36:43.940 --> 00:36:48.041
or I can round it in the (mumbles) Fibo.

680
00:36:48.041 --> 00:36:51.890
The synthesizer is capable of synthesizing conditionals.

681
00:36:51.890 --> 00:36:53.986
For example, if I want to check

682
00:36:53.986 --> 00:36:56.569
if the media player is playing,

683
00:36:57.940 --> 00:37:00.773
and if this is the case, pause it.

684
00:37:04.558 --> 00:37:06.706
Or, if it was currently paused,

685
00:37:06.706 --> 00:37:08.206
resume the player.

686
00:37:10.193 --> 00:37:13.693
The synthesizer can also generate loops...

687
00:37:17.502 --> 00:37:21.085
including (mumbles) loops.

688
00:37:24.373 --> 00:37:26.827
Next I will show how to create the loop

689
00:37:26.827 --> 00:37:30.994
that iterates ten times (mumbles).

690
00:37:39.793 --> 00:37:42.973
Note that there are two interpretations to this example.

691
00:37:42.973 --> 00:37:45.246
The intended one is shown at the top.

692
00:37:45.246 --> 00:37:47.685
In the second step, the synthesizer generates

693
00:37:47.685 --> 00:37:50.854
a temporary variable for the addition operation

694
00:37:50.854 --> 00:37:53.687
which the user could use later on.

695
00:37:54.600 --> 00:37:56.114
As the final example,

696
00:37:56.114 --> 00:37:59.166
let us combine the picture sample that I showed earlier

697
00:37:59.166 --> 00:38:00.333
with the loop.

698
00:38:07.510 --> 00:38:09.731
Here is the synthesized data.

699
00:38:09.731 --> 00:38:12.047
It iterates 15 times.

700
00:38:12.047 --> 00:38:15.318
Each time, it takes a random picture with a random color

701
00:38:15.318 --> 00:38:18.297
and posts it to the screen.

702
00:38:18.297 --> 00:38:20.964
Now, it can run it on the phone.

703
00:38:29.584 --> 00:38:33.252
<v ->That was a demo of (mumbles).</v>

704
00:38:33.252 --> 00:38:36.176
I think that there's a real opportunity here to develop

705
00:38:36.176 --> 00:38:39.617
(mumbles) programming that allows you to program

706
00:38:39.617 --> 00:38:42.573
the examples in that video.

707
00:38:42.573 --> 00:38:45.256
Now moving on to the second part of the program

708
00:38:45.256 --> 00:38:48.135
to the application of similar technologies

709
00:38:48.135 --> 00:38:50.468
in computer-aided education.

710
00:38:52.632 --> 00:38:55.473
(mumbles) connections between user programming

711
00:38:55.473 --> 00:38:57.255
and computer-aided education.

712
00:38:57.255 --> 00:39:00.715
So in the case of an end-user that teaches a computer,

713
00:39:00.715 --> 00:39:02.851
and the computer uses that knowledge

714
00:39:02.851 --> 00:39:05.747
to automate repetitive tasks for the user.

715
00:39:05.747 --> 00:39:07.589
In the case of education,

716
00:39:07.589 --> 00:39:10.553
it is the teacher who (mumbles).

717
00:39:10.553 --> 00:39:11.973
The teacher will teach the computer

718
00:39:11.973 --> 00:39:13.495
about the subject domain,

719
00:39:13.495 --> 00:39:16.461
and the computer will be able to use that knowledge

720
00:39:16.461 --> 00:39:17.802
to teach students.

721
00:39:17.802 --> 00:39:19.196
What I'm going to talk about now

722
00:39:19.196 --> 00:39:22.803
is the interaction between the end-user and the computer

723
00:39:22.803 --> 00:39:24.895
in user programming tasks.

724
00:39:24.895 --> 00:39:27.435
Similarly, in the case of education,

725
00:39:27.435 --> 00:39:29.897
there is some kind of (mumbles) that has to happen

726
00:39:29.897 --> 00:39:31.949
between the student and the computer

727
00:39:31.949 --> 00:39:34.725
in order for the computer to (mumbles).

728
00:39:34.725 --> 00:39:36.943
<v Audience Member>Before you go too far with this,</v>

729
00:39:36.943 --> 00:39:39.398
you gave very interesting demos about

730
00:39:39.398 --> 00:39:40.648
the Flash Fill.

731
00:39:42.179 --> 00:39:43.765
Do you have any report

732
00:39:43.765 --> 00:39:46.529
about users' success with this, the learning time,

733
00:39:46.529 --> 00:39:49.429
what the audiences do, the problems they run into,

734
00:39:49.429 --> 00:39:52.476
how often they accomplish their goals?

735
00:39:52.476 --> 00:39:55.505
<v ->So, unfortunately, we have not detected (mumbles) yet,</v>

736
00:39:55.505 --> 00:39:58.074
but these are some of the things that are ongoing.

737
00:39:58.074 --> 00:40:00.644
Where we want to show some people certain tasks,

738
00:40:00.644 --> 00:40:02.056
computer programmers,

739
00:40:02.056 --> 00:40:03.313
and then to measure

740
00:40:03.313 --> 00:40:05.415
how long did the computer programmer require

741
00:40:05.415 --> 00:40:09.582
to program the task and (mumbles)?

742
00:40:11.005 --> 00:40:12.969
<v Audience Member>And even Flash Fill?</v>

743
00:40:12.969 --> 00:40:15.695
You released the product without testing it?

744
00:40:15.695 --> 00:40:17.338
<v ->So programming user status</v>

745
00:40:17.338 --> 00:40:20.712
with respect to how many people are trying to use it

746
00:40:20.712 --> 00:40:23.412
or whatever types of tasks they're trying to do,

747
00:40:23.412 --> 00:40:25.827
so all of our benchmarks are based upon

748
00:40:25.827 --> 00:40:27.729
what they saw in headquarters.

749
00:40:27.729 --> 00:40:30.708
<v Audience Member>And are you logging usage</v>

750
00:40:30.708 --> 00:40:34.359
so at least you have some data about how much they use it?

751
00:40:34.359 --> 00:40:35.757
<v ->Unfortunately, no.</v>

752
00:40:35.757 --> 00:40:39.708
We wish we did, but there's logistic issues (mumbles).

753
00:40:39.708 --> 00:40:43.791
So logistic issues for why we could not log that.

754
00:40:47.572 --> 00:40:51.739
Unfortunately, these demos are not backed up by (mumbles).

755
00:40:55.386 --> 00:40:58.053
But we are working towards that.

756
00:41:00.003 --> 00:41:03.086
I thought (mumbles).

757
00:41:05.374 --> 00:41:07.304
So the second thing, the second interaction

758
00:41:07.304 --> 00:41:09.609
between end-user programming and computer-aided education

759
00:41:09.609 --> 00:41:13.776
is interactivity that has to (mumbles).

760
00:41:16.673 --> 00:41:20.840
Now, implications of this (mumbles).

761
00:41:22.494 --> 00:41:24.661
(mumbles)

762
00:41:29.031 --> 00:41:30.972
So there are a variety of tasks

763
00:41:30.972 --> 00:41:33.629
that can be used in computer-aided education.

764
00:41:33.629 --> 00:41:35.643
Like generating problems,

765
00:41:35.643 --> 00:41:38.189
generating sample solutions to those problems,

766
00:41:38.189 --> 00:41:39.503
generating feedback,

767
00:41:39.503 --> 00:41:42.673
and authoring content inside the computer.

768
00:41:42.673 --> 00:41:45.360
And one thing (mumbles)

769
00:41:45.360 --> 00:41:47.042
a variety of subject domains

770
00:41:47.042 --> 00:41:49.827
including mathematics, programming, and language learning.

771
00:41:49.827 --> 00:41:52.391
So I'm going to focus on some specific tasks.

772
00:41:52.391 --> 00:41:54.558
(mumbles)

773
00:41:57.999 --> 00:42:00.697
But before that, let me talk about some commonalities

774
00:42:00.697 --> 00:42:03.904
between the difference of the domains (mumbles).

775
00:42:03.904 --> 00:42:06.167
So most of these domains are a variety of content

776
00:42:06.167 --> 00:42:08.417
(mumbles).

777
00:42:09.437 --> 00:42:13.380
So one is called procedural, another is called conceptual.

778
00:42:13.380 --> 00:42:14.991
In the procedural category,

779
00:42:14.991 --> 00:42:16.397
we use those tasks.

780
00:42:16.397 --> 00:42:17.996
There is a procedure

781
00:42:17.996 --> 00:42:20.430
that the script is supposed to memorize,

782
00:42:20.430 --> 00:42:22.968
and there is (mumbles) variables.

783
00:42:22.968 --> 00:42:25.648
So this is especially common in mathematics.

784
00:42:25.648 --> 00:42:27.863
The student is supposed to understand

785
00:42:27.863 --> 00:42:31.946
the procedure for numbers and types of variables.

786
00:42:33.815 --> 00:42:37.354
These things are also common in undergraduate curriculum.

787
00:42:37.354 --> 00:42:40.771
For instance, (mumbles).

788
00:42:41.976 --> 00:42:44.143
(mumbles)

789
00:42:54.787 --> 00:42:56.291
Then the other thing,

790
00:42:56.291 --> 00:42:58.404
once you (mumbles)

791
00:42:58.404 --> 00:43:02.487
there is no realistic known procedure to (mumbles).

792
00:43:02.487 --> 00:43:06.440
So this is why (mumbles) and so on.

793
00:43:06.440 --> 00:43:09.246
So this would generate proofs for students

794
00:43:09.246 --> 00:43:11.920
and construct some process such as

795
00:43:11.920 --> 00:43:16.087
constructions or common constructions of algorithms.

796
00:43:19.515 --> 00:43:21.259
So with end-user programming,

797
00:43:21.259 --> 00:43:23.099
we focus on two aspects of education.

798
00:43:23.099 --> 00:43:24.742
One is called program synthesis

799
00:43:24.742 --> 00:43:26.795
and the other is feedback synthesis.

800
00:43:26.795 --> 00:43:30.962
So now (mumbles) ask some questions.

801
00:43:32.893 --> 00:43:35.172
So the point of generating problems

802
00:43:35.172 --> 00:43:36.721
is to be able to do

803
00:43:36.721 --> 00:43:41.233
problems that are similar to a given problem,

804
00:43:41.233 --> 00:43:43.239
and this can help avoid copyright issues

805
00:43:43.239 --> 00:43:45.055
or prevent cheating in MOOCs,

806
00:43:45.055 --> 00:43:47.691
where every student can be given a different problem

807
00:43:47.691 --> 00:43:49.441
of a similar problem.

808
00:43:50.315 --> 00:43:52.669
This is especially important (mumbles)

809
00:43:52.669 --> 00:43:55.594
to synthesize certain structures that are going on inside.

810
00:43:55.594 --> 00:43:58.059
So how many of you are a MOOCs (mumbles)?

811
00:43:58.059 --> 00:44:00.680
These are massive online courses

812
00:44:00.680 --> 00:44:04.436
where the content is being put online

813
00:44:04.436 --> 00:44:08.805
and students are participating (mumbles).

814
00:44:08.805 --> 00:44:10.243
The goal of program synthesis

815
00:44:10.243 --> 00:44:14.047
can be to generate a problem of a given difficulty level

816
00:44:14.047 --> 00:44:16.081
and concept usage.

817
00:44:16.081 --> 00:44:20.248
So this can be used to (mumbles).

818
00:44:23.089 --> 00:44:27.017
Let's talk about how we can (mumbles) procedural content

819
00:44:27.017 --> 00:44:30.569
and how we use test based input generation techniques

820
00:44:30.569 --> 00:44:32.921
to be able to do that.

821
00:44:32.921 --> 00:44:35.590
So suppose you want to teach someone addition.

822
00:44:35.590 --> 00:44:36.999
How would you go about doing that?

823
00:44:36.999 --> 00:44:38.650
So you start with simple concepts

824
00:44:38.650 --> 00:44:42.483
and then you want more sophisticated concepts.

825
00:44:43.556 --> 00:44:45.704
It's important that (mumbles) single dates

826
00:44:45.704 --> 00:44:47.877
and how to do multiple digits without that.

827
00:44:47.877 --> 00:44:50.044
(mumbles)

828
00:44:52.457 --> 00:44:55.101
So normally we can automatically generate problems

829
00:44:55.101 --> 00:44:58.101
that demonstrate different concepts.

830
00:45:00.366 --> 00:45:04.033
So by definition (mumbles).

831
00:45:04.902 --> 00:45:09.069
So this is a program where (mumbles).

832
00:45:12.190 --> 00:45:15.380
Notice the different processes that you see here.

833
00:45:15.380 --> 00:45:17.459
They are simply different types of thoughts

834
00:45:17.459 --> 00:45:18.848
in this procedure.

835
00:45:18.848 --> 00:45:20.950
And these thoughts have been captured

836
00:45:20.950 --> 00:45:22.895
in this expression that I've shown you.

837
00:45:22.895 --> 00:45:25.183
And then we can use techniques

838
00:45:25.183 --> 00:45:28.633
that have often been used to find (mumbles) software.

839
00:45:28.633 --> 00:45:32.800
So we can use those techniques to (mumbles).

840
00:45:37.202 --> 00:45:39.570
So this can be used as a foundational way

841
00:45:39.570 --> 00:45:41.987
to generate these procedures.

842
00:45:46.039 --> 00:45:48.959
So we can also use this kind of technique

843
00:45:48.959 --> 00:45:50.876
for comparing integers.

844
00:45:53.607 --> 00:45:56.488
So this is a program comparing two integers

845
00:45:56.488 --> 00:46:00.006
where the students are supposed to compare by (mumbles)

846
00:46:00.006 --> 00:46:02.707
and then comparing them name by name.

847
00:46:02.707 --> 00:46:05.112
So in the graph that you see here,

848
00:46:05.112 --> 00:46:06.610
there are two kinds of problems,

849
00:46:06.610 --> 00:46:07.903
one blue one green.

850
00:46:07.903 --> 00:46:09.519
One is this green progression

851
00:46:09.519 --> 00:46:11.261
and the other is a blue progression.

852
00:46:11.261 --> 00:46:13.638
So as you move down (mumbles).

853
00:46:13.638 --> 00:46:15.249
So the green progression quickly moves

854
00:46:15.249 --> 00:46:17.173
into more than one problem

855
00:46:17.173 --> 00:46:20.686
and by completely ignoring (mumbles).

856
00:46:20.686 --> 00:46:23.403
But the blue progression has more (mumbles)

857
00:46:23.403 --> 00:46:26.236
in terms of the class of problems.

858
00:46:29.117 --> 00:46:30.836
So then one can use this technology

859
00:46:30.836 --> 00:46:33.753
for pre and post existing problems.

860
00:46:35.902 --> 00:46:37.619
So like I said,

861
00:46:37.619 --> 00:46:39.919
we can generate problems by session content,

862
00:46:39.919 --> 00:46:41.737
and one of the techniques that we use

863
00:46:41.737 --> 00:46:45.759
is called template based generalization.

864
00:46:45.759 --> 00:46:49.335
So normally, if we're talking about problems like this,

865
00:46:49.335 --> 00:46:51.731
where the goal is to make the left side

866
00:46:51.731 --> 00:46:54.306
equal to the right side.

867
00:46:54.306 --> 00:46:56.463
Now, some of these problems might be

868
00:46:56.463 --> 00:47:00.439
really easier compared to (mumbles).

869
00:47:00.439 --> 00:47:02.138
So we have a technology which

870
00:47:02.138 --> 00:47:03.820
can make a simple problem

871
00:47:03.820 --> 00:47:05.811
and then output green problems

872
00:47:05.811 --> 00:47:08.593
that are really similar in structure to the problem

873
00:47:08.593 --> 00:47:10.760
(mumbles)

874
00:47:11.750 --> 00:47:13.733
And the thing about technology is

875
00:47:13.733 --> 00:47:15.443
that the first problem is generalized

876
00:47:15.443 --> 00:47:17.827
into this orange query.

877
00:47:17.827 --> 00:47:20.345
There, the (mumbles)

878
00:47:20.345 --> 00:47:23.678
which can be written by a plus or minus.

879
00:47:25.239 --> 00:47:27.406
(mumbles)

880
00:47:30.197 --> 00:47:32.221
So the sense of generalization is

881
00:47:32.221 --> 00:47:33.945
that we make each our favorite

882
00:47:33.945 --> 00:47:37.278
and then the (mumbles).

883
00:47:42.050 --> 00:47:43.733
And when we understand this,

884
00:47:43.733 --> 00:47:45.511
we use search

885
00:47:45.511 --> 00:47:48.825
to pile all of our (mumbles).

886
00:47:48.825 --> 00:47:51.322
But then (mumbles)

887
00:47:51.322 --> 00:47:53.979
to check whether a certain substantiation

888
00:47:53.979 --> 00:47:56.241
leads to better problem outcome.

889
00:47:56.241 --> 00:48:00.158
Because one of them (mumbles).

890
00:48:01.489 --> 00:48:04.156
So the check, we use a technique

891
00:48:05.114 --> 00:48:07.197
from the user specification.

892
00:48:07.197 --> 00:48:09.480
So the idea is to simply test the

893
00:48:09.480 --> 00:48:12.791
rightness of this problem on the data interface.

894
00:48:12.791 --> 00:48:16.958
And this is an addition formula (mumbles).

895
00:48:20.971 --> 00:48:23.164
So this is actually an inductive process,

896
00:48:23.164 --> 00:48:26.219
so (mumbles) generating some other problems

897
00:48:26.219 --> 00:48:29.521
which are really much simpler than the data points

898
00:48:29.521 --> 00:48:31.771
(mumbles).

899
00:48:36.140 --> 00:48:40.307
So this technology works for (mumbles).

900
00:48:46.304 --> 00:48:50.471
So basically, in general, you have (mumbles).

901
00:48:54.449 --> 00:48:57.699
These are the problems that we can see.

902
00:48:59.148 --> 00:49:01.315
(mumbles)

903
00:49:03.002 --> 00:49:05.319
So let me show you another application

904
00:49:05.319 --> 00:49:07.789
of the (mumbles).

905
00:49:07.789 --> 00:49:11.505
So this is the context of the language we're using.

906
00:49:11.505 --> 00:49:12.972
So these are two problems

907
00:49:12.972 --> 00:49:15.389
that we see in the SAT exams,

908
00:49:16.494 --> 00:49:19.161
and that is sentence completion.

909
00:49:20.178 --> 00:49:22.809
So does someone know the answer to the first problem?

910
00:49:22.809 --> 00:49:23.642
So you have to figure out

911
00:49:23.642 --> 00:49:24.475
which of the options is the right choice

912
00:49:24.475 --> 00:49:26.774
for the first sentence completion.

913
00:49:26.774 --> 00:49:28.781
(mumbles)

914
00:49:28.781 --> 00:49:30.219
Yes, so that's right.

915
00:49:30.219 --> 00:49:31.951
What of the second one?

916
00:49:31.951 --> 00:49:33.897
(mumbles)

917
00:49:33.897 --> 00:49:35.697
So, one of these problems

918
00:49:35.697 --> 00:49:37.202
is a real SAT problem

919
00:49:37.202 --> 00:49:40.160
and the other has been automatically synthesized.

920
00:49:40.160 --> 00:49:41.511
Do you guys want to guess

921
00:49:41.511 --> 00:49:43.171
which one was the original one

922
00:49:43.171 --> 00:49:46.671
and was the automatically synthesized one?

923
00:49:48.283 --> 00:49:50.610
So, the original one is the first one

924
00:49:50.610 --> 00:49:52.882
and the second was synthesized.

925
00:49:52.882 --> 00:49:55.715
And the (mumbles)

926
00:49:57.030 --> 00:49:58.449
So that's the example

927
00:49:58.449 --> 00:50:00.358
in how we generated the example.

928
00:50:00.358 --> 00:50:02.553
So you see an example of how we generated a problem.

929
00:50:02.553 --> 00:50:04.720
(mumbles)

930
00:50:07.084 --> 00:50:10.351
So we made the problem by one and we generalized a template,

931
00:50:10.351 --> 00:50:13.422
and the template is something like this.

932
00:50:13.422 --> 00:50:15.589
(mumbles)

933
00:50:18.732 --> 00:50:22.736
And then we specialized the template T1 to template T2.

934
00:50:22.736 --> 00:50:24.903
(mumbles)

935
00:50:29.448 --> 00:50:32.981
and then we started to find that (mumbles).

936
00:50:32.981 --> 00:50:34.645
So in the case of algebra,

937
00:50:34.645 --> 00:50:38.479
we were trying to find (mumbles)

938
00:50:38.479 --> 00:50:41.268
and here we find that this is our template

939
00:50:41.268 --> 00:50:43.380
using the search.

940
00:50:43.380 --> 00:50:45.351
So we search for the (mumbles)

941
00:50:45.351 --> 00:50:47.851
using a scatter search engine.

942
00:50:48.720 --> 00:50:52.887
And then this is called the operating synthesizer.

943
00:50:54.185 --> 00:50:55.651
So the idea of this is

944
00:50:55.651 --> 00:50:58.571
generalization for content.

945
00:50:58.571 --> 00:51:01.995
So that's another technique (mumbles).

946
00:51:01.995 --> 00:51:04.745
So skipping over the last slides,

947
00:51:05.779 --> 00:51:09.112
it is on automatically delayed feedback.

948
00:51:12.560 --> 00:51:15.382
So, I will talk about generating feedback

949
00:51:15.382 --> 00:51:16.952
for procedural content,

950
00:51:16.952 --> 00:51:19.519
but let me focus more on the ranking feedback

951
00:51:19.519 --> 00:51:21.857
for conceptual product.

952
00:51:21.857 --> 00:51:26.024
So let's say the teacher comes in and tries this program.

953
00:51:28.752 --> 00:51:30.724
And you can use a bunch of feedback matrix

954
00:51:30.724 --> 00:51:34.141
with feedback (mumbles).

955
00:51:35.018 --> 00:51:37.588
So, various feedback metrics called counterexamples.

956
00:51:37.588 --> 00:51:40.338
So you (mumbles)

957
00:51:41.709 --> 00:51:43.876
(mumbles)

958
00:51:44.748 --> 00:51:48.702
How many of you have heard of the system PexForFun?

959
00:51:48.702 --> 00:51:49.535
So not many.

960
00:51:49.535 --> 00:51:51.307
It is a system that has been designed

961
00:51:51.307 --> 00:51:53.311
by a small group of colleagues.

962
00:51:53.311 --> 00:51:57.478
There, you can submit some items to a programming problem.

963
00:51:58.346 --> 00:52:01.693
(mumbles) give you a longer example

964
00:52:01.693 --> 00:52:04.693
and then (mumbles).

965
00:52:05.607 --> 00:52:07.975
So this is a content that was submitted

966
00:52:07.975 --> 00:52:10.340
by someone (mumbles).

967
00:52:10.340 --> 00:52:12.507
So there's some bug here.

968
00:52:13.840 --> 00:52:16.548
And then, for this example,

969
00:52:16.548 --> 00:52:19.862
the square (mumbles) accept,

970
00:52:19.862 --> 00:52:21.945
and then another example.

971
00:52:22.849 --> 00:52:25.016
(mumbles)

972
00:52:32.218 --> 00:52:35.301
So all the (mumbles)

973
00:52:41.117 --> 00:52:45.284
And all this is getting closer to the (mumbles).

974
00:52:47.184 --> 00:52:50.905
But synthesis keeps getting the same counterexample.

975
00:52:50.905 --> 00:52:53.155
(mumbles).

976
00:52:57.442 --> 00:52:59.576
So this is the kind of sample

977
00:52:59.576 --> 00:53:02.516
that people are coming in with.

978
00:53:02.516 --> 00:53:05.895
This is the feedback based on one of these cases.

979
00:53:05.895 --> 00:53:07.562
You can take a look.

980
00:53:14.763 --> 00:53:17.368
So for (mumbles)

981
00:53:17.368 --> 00:53:19.118
can provide feedback.

982
00:53:22.940 --> 00:53:26.413
Based upon (mumbles).

983
00:53:26.413 --> 00:53:29.492
So not only telling them why the solution is wrong,

984
00:53:29.492 --> 00:53:32.467
but also where the bug is in the solution.

985
00:53:32.467 --> 00:53:36.300
And this technique (mumbles).

986
00:53:39.788 --> 00:53:41.955
(mumbles)

987
00:53:43.336 --> 00:53:45.503
(mumbles)

988
00:53:49.638 --> 00:53:52.619
And then we find the minimal set of changes

989
00:53:52.619 --> 00:53:54.664
that convert a buggy solution

990
00:53:54.664 --> 00:53:55.838
into a correct one

991
00:53:55.838 --> 00:53:57.110
is phrased as a sketch problem.

992
00:53:57.110 --> 00:54:00.377
So that is the attempt (mumbles).

993
00:54:00.377 --> 00:54:02.085
So these are two different.

994
00:54:02.085 --> 00:54:04.395
So these (mumbles) array reverse are non buggy.

995
00:54:04.395 --> 00:54:08.562
So how many are there computer programming (mumbles)?

996
00:54:11.217 --> 00:54:13.384
(mumbles)

997
00:54:20.324 --> 00:54:22.965
So this can work still.

998
00:54:22.965 --> 00:54:27.132
For cases where the number of (mumbles).

999
00:54:28.273 --> 00:54:31.766
So we hear what users are saying about this,

1000
00:54:31.766 --> 00:54:35.174
so we have the content (mumbles).

1001
00:54:35.174 --> 00:54:37.341
(mumbles)

1002
00:54:43.304 --> 00:54:46.038
And then there's (mumbles)

1003
00:54:46.038 --> 00:54:49.621
but there's not (mumbles).

1004
00:54:50.508 --> 00:54:53.370
By running the steps through the nearest problem

1005
00:54:53.370 --> 00:54:55.106
(mumbles).

1006
00:54:55.106 --> 00:54:58.523
So this (mumbles) cases.

1007
00:55:03.560 --> 00:55:06.262
So this is in the context of popular constructions.

1008
00:55:06.262 --> 00:55:09.007
So the last (mumbles).

1009
00:55:09.007 --> 00:55:13.174
And these are the different attempts at the automata.

1010
00:55:15.187 --> 00:55:17.354
(mumbles)

1011
00:55:23.578 --> 00:55:24.870
For the first one,

1012
00:55:24.870 --> 00:55:26.961
the object is almost correct

1013
00:55:26.961 --> 00:55:29.208
except the eight.

1014
00:55:29.208 --> 00:55:31.499
And then based on edit distance,

1015
00:55:31.499 --> 00:55:33.330
the system ascribes a grade

1016
00:55:33.330 --> 00:55:36.163
based on feedback for the student.

1017
00:55:39.410 --> 00:55:40.590
But the second one

1018
00:55:40.590 --> 00:55:44.757
is quite far off in terms of being the right solution.

1019
00:55:46.050 --> 00:55:48.332
but (mumbles)

1020
00:55:48.332 --> 00:55:50.415
based on counterexamples.

1021
00:55:53.414 --> 00:55:57.581
Shorter counterexamples (mumbles).

1022
00:55:59.210 --> 00:56:02.543
Number three (mumbles).

1023
00:56:07.847 --> 00:56:11.514
So the student's (mumbles).

1024
00:56:16.083 --> 00:56:18.277
So this is the content of the feedback

1025
00:56:18.277 --> 00:56:22.444
which I mentioned when I said (mumbles).

1026
00:56:23.696 --> 00:56:26.361
So most students make all these different

1027
00:56:26.361 --> 00:56:28.383
types of (mumbles).

1028
00:56:28.383 --> 00:56:30.550
(mumbles)

1029
00:56:36.492 --> 00:56:38.325
make those attempts to

1030
00:56:39.447 --> 00:56:41.614
(mumbles)

1031
00:56:43.858 --> 00:56:46.572
But I want to focus your attention on

1032
00:56:46.572 --> 00:56:48.822
(mumbles).

1033
00:56:56.367 --> 00:56:58.521
So notice how, for some of them,

1034
00:56:58.521 --> 00:57:00.568
the computer instructors are incorrect.

1035
00:57:00.568 --> 00:57:02.806
They gave full marks to an incorrect.

1036
00:57:02.806 --> 00:57:05.489
For some of them, the instructors made a mistake.

1037
00:57:05.489 --> 00:57:09.111
They gave different marks to incorrect attempts.

1038
00:57:09.111 --> 00:57:13.278
And we asked the instructor to reevaluate the data,

1039
00:57:15.352 --> 00:57:19.960
and the instructors agreed that the tool was more fair.

1040
00:57:19.960 --> 00:57:24.127
The greatest compliment, actually (mumbles)

1041
00:57:26.459 --> 00:57:30.626
He said that the tool does a much better job than he.

1042
00:57:31.973 --> 00:57:34.140
(mumbles)

1043
00:57:39.345 --> 00:57:41.668
This is the last concluding slide.

1044
00:57:41.668 --> 00:57:43.304
So I want to emphasize

1045
00:57:43.304 --> 00:57:47.058
that program synthesis is quite a challenging problem.

1046
00:57:47.058 --> 00:57:49.475
But if you define it properly

1047
00:57:50.355 --> 00:57:52.583
we can come up with quick solutions to it,

1048
00:57:52.583 --> 00:57:56.550
and (mumbles) the right domain specific language (mumbles)

1049
00:57:56.550 --> 00:58:00.405
design the right intent specifications (mumbles)

1050
00:58:00.405 --> 00:58:01.905
search techniques.

1051
00:58:03.163 --> 00:58:05.490
And then there are a good variety of applications

1052
00:58:05.490 --> 00:58:07.939
that (mumbles) specific techniques

1053
00:58:07.939 --> 00:58:10.051
in the context of end-user programming

1054
00:58:10.051 --> 00:58:12.370
and in the context of education.

1055
00:58:12.370 --> 00:58:14.117
So thanks for your attention.

1056
00:58:14.117 --> 00:58:16.155
I'd be happy to take any questions.

1057
00:58:16.155 --> 00:58:18.405
(applause)

1058
00:58:25.490 --> 00:58:29.490
<v ->[Audience Member 2] (mumbles)</v>

1059
00:58:39.100 --> 00:58:41.267
(mumbles)

1060
00:58:49.459 --> 00:58:51.626
(mumbles)

1061
00:59:44.746 --> 00:59:48.064
<v ->This one has offered (mumbles) technologies.</v>

1062
00:59:48.064 --> 00:59:51.041
So what can technology do?

1063
00:59:51.041 --> 00:59:54.081
I'm not talking about (mumbles)

1064
00:59:54.081 --> 00:59:58.248
but my goal here is to actually showcase (mumbles)

1065
01:00:02.832 --> 01:00:06.525
and then once you see (mumbles)

1066
01:00:06.525 --> 01:00:09.858
some kind of (mumbles).

1067
01:00:15.516 --> 01:00:17.683
(mumbles)

1068
01:00:23.479 --> 01:00:27.519
So let's say a student (mumbles)

1069
01:00:27.519 --> 01:00:29.696
you normally give them feedback.

1070
01:00:29.696 --> 01:00:33.863
But you also figure out what (mumbles).

1071
01:00:37.810 --> 01:00:39.977
(mumbles)

1072
01:00:47.330 --> 01:00:49.497
(mumbles)

1073
01:01:08.590 --> 01:01:10.560
<v ->[Audience Member 3] I was wondering,</v>

1074
01:01:10.560 --> 01:01:14.727
what's your opinion on (mumbles) essays.

1075
01:01:19.185 --> 01:01:21.652
How are you going to be able to provide feedback

1076
01:01:21.652 --> 01:01:22.958
to things like that,

1077
01:01:22.958 --> 01:01:25.051
where they're very abstract?

1078
01:01:25.051 --> 01:01:28.888
<v ->So there is somewhat in the area of providing feedback</v>

1079
01:01:28.888 --> 01:01:30.728
(mumbles)

1080
01:01:30.728 --> 01:01:33.145
I recall that in my GRE exam,

1081
01:01:34.468 --> 01:01:38.135
there would be a (mumbles).

1082
01:01:41.265 --> 01:01:44.932
But I'm not much (mumbles).

1083
01:01:49.410 --> 01:01:51.577
(mumbles)

1084
01:02:22.982 --> 01:02:26.899
And my hope is that (mumbles).

1085
01:02:28.415 --> 01:02:30.519
(mumbles)

1086
01:02:30.519 --> 01:02:33.936
but personally (mumbles)

1087
01:02:39.201 --> 01:02:40.738
<v ->[Audience Member 3] And a follow-up question</v>

1088
01:02:40.738 --> 01:02:42.282
to the feedback poll.

1089
01:02:42.282 --> 01:02:45.615
What if it is (mumbles)

1090
01:02:47.165 --> 01:02:48.667
What is you just have,

1091
01:02:48.667 --> 01:02:52.500
'cause it's all based on what you have, right?

1092
01:02:53.929 --> 01:02:56.904
So with professors, your comparison,

1093
01:02:56.904 --> 01:03:01.071
you're providing more justification for (mumbles)

1094
01:03:02.251 --> 01:03:04.395
<v ->In this case, the professor who participated in this</v>

1095
01:03:04.395 --> 01:03:07.062
also (mumbles).

1096
01:03:08.394 --> 01:03:10.492
(mumbles)

1097
01:03:10.492 --> 01:03:14.659
<v ->[Audience Member 3] Okay (laughs).</v>

1098
01:03:19.874 --> 01:03:22.124
(applause)