Difference between revisions of "How Complex is "Personal Computing"? (2009)"

Latest revision as of 22:03, 6 December 2017

so I'll just put thing you guys whoop I should

get your signature back

I was just gonna write the name of I'll

put it over here so the the

basic apologize

in advance for a couple of

things one

is one is the

brevity and the

kind of livid is a navy term for five

pounds of shit in a one pound bag and

so we have a lot more information

that we'd like to talk

to you about but we haven't ever

been able to fit it into an hour and

so we're gonna try

to give you the gist of some of the things that we're

doing but this website

Vpr i.org

maybe our talks are kind of a commercial

to just have

you look at some of the stuff there so I'm just gonna spend a few

minutes giving you the context

for a project

that the NSF reviewers turned

the preposterous proposal when they turned it down

anybody ever been turned down by an

NSF peer review

now it turns out that the program managers at

NSF have always had the power to override those and

in this case the program manager

did override it so we got our money anyway

but they only gave us money to

cover about half the expenses of this project

so we raised a matching amount of

money to do it it's a project that a

number of us have been thinking about for

as long as 30 years that would be really

interesting to do and

it would be very much in the original spirit

of what computer science was supposed to be as articulated

in the 60s by Al

so

that kind of

starts with the quintessential Maxwell's equations t-shirt

and

this is one that everybody's

seen and if

you're familiar with Maxwell you know that he actually

wrote five papers arriving

at these conclusions and in five different ways

he did this over a period of years using

different models and the original

form of maskull's equations was not fiddle on a t-shirt

so this form was

actually made by several people including

the Germans who were much more interested in it than the

British in

no small part because Maxwell's

equations violated Newton and Newton was

a god Maxwell was only their best guy

in the 19th century but Newton was

a god and of course the

interesting thing about getting him in this form is

although Faraday's

experiments showed that there

should be a symmetric relationship between the

electric and magnetic fields the equation didn't

show those relations as symmetric

and this asymmetry and this

things led to Einstein's theory of relativity and

in fact a much simpler form of writing

these guys down and reason

I'm putting it up there is I had a similar

experience when I was in

graduate school trying to understand programming languages and

I looked at the bottom of page 13 of the list

1.5 manual and here

was McCarthy's formulation of Lisp using itself

as a metal language and

how many people have had the experience of

going through this it takes a couple of hours on

a Sunday afternoon to do and you run out of fingers

because you have your fingers down in all the places that recursos

and reenters and so

forth and I felt I understand stood it when I found in

this code there is one bug

and the thing I got

out of it is boy after those two hours I

understood what programming languages were about a factor

hundred better than I did before I went in because

McCarthy had carved away all the bullshit and

God that's something

that was more powerful than any other programming language of the day

powerful expressively the most programming languages

today and had

done it in this interesting

form and

in fact it had a lot of effect on subsequent

things that were done and because I

had a math degree I just love

this stuff and so we

tried these ideas a number of times on

various projects including some of the stuff we did it Xerox

PARC that

gee you can

do a programming language in under a thousand lines of

code or you might be able to do it in the page and

there are advantages to the

page for sure so

so

the thing we were speculating about is

do you it'd be really interesting if

you could apply this way of looking

at processes to an entire system that's well

understood like personal computing so

we have now this interesting idea that if

science is the study of and modeling

of phenomena in order to understand it better we actually

build artifacts that exhibit interesting

phenomena and what John

did is to take the phenomena exhibited by programming

languages of the day and find an abstraction that

captured them his abstraction happened to be more powerful than

the ones he was looking at which is kind of an old

mathematicians trick you know solved the more

general problem if you can and so

the idea here was be

interesting to take this body

of behavior from the end-user to the

metal of the Machine and

try to understand it

by right making a model that you could actually run it would generate

the same phenomena and

so how many t-shirts would it take to

do all of personal computing that's the question here you

can see why they called it preposterous right

because Microsoft's version of this is

a few hundred million lines of code their

operating system and the

same Microsoft Office is about 220 million

lines of code but if

you think about it with the view of well what is it

doing really and how many things in

decided to do differently for example are

actually the same thing masquerading under a

few simple parameterizations and

and also the first time around that this stuff

was done it was only ten thousand lines of code it at

Xerox PARC and there's not a lot more

functionality now

than there was back then so the idea is this

could be a lot smaller and

be very interesting to see for the same reasons

that these two guys are interesting but this

would be look look like so that's what our project is

and there's one more tea involved here

which is we one

of the things that's nice about

making things small and simple is you got

something like a Model T Ford which any 12

year old could take apart in the

barn over the weekend and put together only had about 350

major parts in it and about a

thousand screws and nuts and bolts and stuff so anybody

who grew up in a farm like I did

where there's still Model T trucks

and in the 40 they would be routinely taken apart

they recently were still around this you couldn't couldn't really

kill them because everything

that broke on them was fixable in the blacksmithing

shop that every farm had back then there was nothing

true they didn't even have a distributor they didn't even have gears

they had

belts and pulleys on them

so but they're a real automobiles so they had this

interesting thing they caused even though their automobiles

around and before them they caused the automobile revolution

in America because they were so easy to

manufacture and they lasted well and so forth so

just one bottle T

story the

gap the spark

gap on Model T was

optimized to be the width of a dime

and somebody asked Henry Ford once why

did you do that and he said well people always

lose gauges but they usually have a dime on them

so he's fully expected anybody who's had one of

these things would be able to just fix it and tweak it up and

that's what happened so it's a nice metaphor

so

my theory is before you write the Ferrari code

you should write model-t code because there's

a 12 year old kid who just isn't gonna be able to

understand the Ferrari code and you have a moral obligation

to write that Model T code that is understandable

so

kind of the standard model for personal

computing is from the

Xerox PARC

experience and so

the bitmap screen that can display anything and

a way of organizing views on

the display and people

have been confused by the difference between desktop publishing

and Microsoft for instance has

been and window display

they're actually the same thing just these

guys have boundaries around the views and

publishing you don't have boundaries around the views

but aside from that everything else is exactly the

same and it was done with the same code

so this is a modern version of it

and I'm

disappointed in this display because

Danny molang has done a lot of work to

do really fantastic graphics

which some of the

things are shown here and you can't see

how crisp and beautiful it is but this is kind

of a modern version of it done with some of the stuff that

that that

we've done and just to show you a little slant

of it here

so I I can

edit this as I'm as I'm

used to doing

and

but I can this

thing is programmed completely differently than the way you might think

so for instance the the

code behind these paragraphs is the

justification and the editor

for come to about 23

lines of code in one of the languages we developed

to do this and I'm not gonna explain

exactly how we did this but I'll just give you a little

flavor of what's actually going on here so

you can think of this as swarm programming

so what we have is thousands

and thousands of parallel processes

running at the same time and these are

all objects and

so the slowest

simplest way you can think of

doing the

problem here is

well just follow the guy in

front of you if you don't have anybody in front of you you know where

to go if you're over the margin tell the guy in front of you

and if somebody tells you they're on the margin and you're the

first there's a blank in front of you then go to the next line all

right so that's four things that do

a text justification

Oulu sore anything they're just all

running and they're related to each other so we call

this particles and fields type programming and

there's a lot of it in this in the system

and you notice that I've embedded a view

of the entire document recursively into it so

that was operating at the same time so

this is basically this kind of stuff in which

each part of the thing has been mathematize dand done in

a separate programming language and of course we have to

make the programming languages to do it we have to make the tools to make the

programming languages to do it

and

but what we don't try to do so these are the

three main operating systems and

won't tell you which one the lemon is

but they're all big and

we want to avoid apples and oranges

comparison so

the stuff that we're doing is is

not there's nothing that we can do

that can be honestly compared to

what Microsoft or Apple do because

they have legacy problems we don't have

there's a million things so we don't even worry about that

but here's a t-shirt with a mustard seed on

it and that gives you kind of what we're out after

out after more than a factor of a thousand change

in the size of the code that it takes to make this

kind of phenomena something

more like a factor of 10,000

and

so

if you have the end-user at one end and you have a power supply at

the other you have a lot

of different kinds of phenomena in there and the question

how many t-shirts do you actually have to do so

you think of the the two

and a half D anti-alias graphics as

you'd love to have that in one or two t-shirts

o that's regularly a couple hundred thousand lines of

code and if

you think of the number of different languages you

might want to invent to mathematize the different

parts of these things there's probably five or ten different languages you

have to do so you have to have a metal language metal language has

to deal with itself and and so forth and

you'd

like to improve semantics of programming and so

forth so we have a dozen or so powerful

principles here are ten of them there's nothing more

boring than somebody enumerated list

on a slide so I'll just

point out that most of these powerful principles

have been around since I started in computing in the early

60s and most of

them are not in general use today or in use the way they

were originally used so

some of these are things that

have been resurrected so

the particles infield is something that hasn't

hasn't been used very much but

the notion of simulating time not letting the CPU

determine what time is all about goes back

to both Simula and john

mccarthy situation calculus these are

old ideas but they

have the great advantage that you don't get

deadlocks from trying to use monitors and semaphores so

the basic idea is if you simulate the time that

you're running in you cannot have race conditions that you haven't explicitly

allowed and so

on so the underlying idea here is that

math wins not standard math but

math that you actually invent in order

to characterize all the different behaviors that you

half and with that I'm going to

turn it over to Dan amma lang who

will talk to you a little bit about how we do the graphics

because this is kind of a classic case study

of

give you this

dan is a graduate

student at UC san diego and

just got his master's for part

his and is on his way to getting his PhD for

the rest of it

and well what we'd like to

do here is to I don't

think anything I said needs questions except maybe

to the end but be great I brought

the three people who did a lot of work

in this system along there

the time you get to my age you're just a figurehead some

thrill to actual actually

bring people who are doing stuff here and to have them

tell you a little bit about how they're approaching these

problems and hope you do ask

questions hello

so like Alan said my name is

Dan am Liang I'm a grad student like you guys

so go easy on me I'm

getting towards the end of my

times of PhD students so

I'm gonna present to you basically

where I am on my dissertation work I have still

about a year and a little more than

that to go although I've noticed that kind of just extends

forward it's a tradition of PhD

students right so

I'm a UCSD PhD student and I but

I'm also an employee of viewpoints Research Institute

and so my little niche in this project

is the 2d rendering system because we'd

build a whole

basically a whole software stack

and we're not allowed to just delegate to the

operating system routines we want to reinvent programming

at every level so I have some background in computer

graphics and some in programming languages

and computer architecture and so

basically it fell on me to

figure out how to do two new rendering so the the

sub-project of mine is called Jazeera and like

I said it's a 2d graphics rendering the spirit of this project

the idea is to provide something that's practical

useful for the other projects sub

projects that viewpoints to actually use specifically

the focus right now is building

user interfaces and so my

job is to discover what are the minimal algorithms

the powerful abstractions new representations so

that I don't use up our code but budget and

just in my sub project because

the goal here is again is to happen

and you know the whole system's the whole thing is is minimal

so and again this isn't

hough I'm doing computer graphics the focus here is more

software engineering I'm not going to do

anything that's really advancing the state-of-the-art computer

graphics so much so

what are the requirements of this graphics library

well today in today's systems

you expect anti-aliased vector graphics

what people use nowadays is typically flash

SVG core graphics on mac OS x

windows presentation foundation so

that that's kind of and not my competitors but

what's similar to what

currently provides that functionality today

in commercial systems right so in

that in a 2d render you want to have bezzie

outlines for your shapes you want to be able to display text

transformations clipping all pretty

traditional stuff the blending

operations digital images pen stroking for

the outline of of

shapes so as

I was working on this I started with the Cairo open-source

vendor project

which I've been working on before I joined

viewpoints and so I was able to take kind of a lessons

learned from working on Cairo which is the render

behind Firefox and various

open source applications and so

as I was kind of going through the Cairo code and

thinking you know stepping back from it and figure

out what really is the high level intention

of these coders I came

across the rasterization stage which is probably

the most complex part of the whole

software library anyone who's taken an undergrad

computer graphics of course that's had to implement

like scanline fill knows that it's it's it's

kind of tricky getting all the edge cases and and there really

isn't a strict formula that tells you what what

he output should be there it's usually described as some sort

of an algorithm with data structures active edge list etc

and and so I couldn't figure

know what really is the highest level semantics of rasterization

so

and it's difficult so I looked

at I look at some kind of non-traditional algorithms

for forwarding Astros ation especially

things specific to 2d because I can kind of ignore the complexities

of 3d here and

and and you

know one one method kind of stuck out at me there's

this approach called analytic area based anti-aliasing

rasterization that looks sort of like

formula but everyone's still expressed in terms of like a big

K statement and so I felt

you know there's still something to be extracted here so I

called my mom

luckily she's a high school geometry teacher

and a great

partner to have and trying to figure out all this computational

geometry that I was in the middle and so we had

we sat down for about 10 days and

did like pair programming with a pencil and paper

and we didn't end up with an interesting formula

if you pose a problem this way if we

say given the XY coordinates to the lower left corner of

a pixel we can say that the coverage contribution of

one edge of that shape is calculated

this way so if we just look at it one edge at a time you

can actually use it using an approximation

square for the pixel you can the bottom

function is what you is kind of what you want to look at most

it's just that you can actually combine these

three pretty much standard functions in in

2d geometry in an interesting way

that gets you a nice coverage

result from 0 to 100 so if the the

pixel is entirely outside of the figure at 0 if

entirely within you get 100 if it's on the edge you get somewhere

between the two and

I only have 10 minutes but

basically the top one is variation

of the area of a trapezoid the second one is the

clamp function in mathematics and the third one is a

variation of the point slope formula

for line anyway

once we have it for that one edge then it

works out such that you the total coverage

contribution of the entire polygon is just a linear

combination of those edge contributions with the little additional

adjustment so now we have a formula

but this doesn't execute so

I haven't really won yet but at

least I've you know posed it in a way that then I can

imagine some sort of higher-level language that can that

can turn this into actual executable code so the punchline

is oh okay so then to verify it you

know I wrote some prototypes I have

this node demo all I'll do for you basically you're

going to see you're gonna see

1,000 snowflakes they're all identical so

it's not very realistic that all

have independent position a vertical velocity

and angular velocity and

I'll just animate them and I'm not

using the GPU at all here this is just on the CPU

I render it to an image a bitmap and

then just hand it to the operating system to throw up on the screen

and so this isn't really speed demon

per se but it's just to prove that first of all visual

results are good and that

it's fast enough that I'm not paying myself into a corner

yeah and then so after it starts up it'll

fade in a bit this is actually supposed to be white

or light blue on black you just imagine

this I'm sorry it's

kind of painful for maintenance

and so I just no flex because we

want to render text really quickly without having to use

some sort of cash and speech scheme because that kind of muddies up your

code so as long as I can render something that's text like

because each one of these snowflakes

is composed of 64 cubic Bezier which

is usually much more than what a typical

glyph is that you render on the screen

so as long as I can do these snowflakes quickly then you know that

I can make a case that it'll scale out to the text

rendering so zooming and just to show you that it's vector

graphics not not just

raster graphics it's being scaled it's it's

coming from the vector primitives at each frame

yeah this is like when the screen savers you

can stare out all day but hip denies

me enough so then

so then yeah here's the punchline

the goal was to figure out how to express all that

in 80 lines of code

and I'll explain what this is so

this is a new programming language called called

nyle again the goal is to

express the 2d rendering in a way that is both succinctly

on matted to a variety of execution

environments and doesn't preclude efficient execution

so after

writing these prototypes it

it seemed to me that the best model

for for the software would be a dataflow

stream processing model more generic

then then like the stream the stream languages

today are kind of more tied to specific deep

to GPU hardware this is kind of a more

abstract stream processing model so

yeah the idea is that everything is

just data streams that are being processed by a series of kernels

that have been connected in a network and in an interesting

interesting fashion and you get your pixel values

at that at the end of the pipeline and then we want

optimize the syntax for each one of those kernels for

expressing arithmetic vector

computations you know domain basically

domain-specific language for arithmetic

stream processing and

then we want to be able to then generate

code for a variety of environments so like a generate

code to see because that'll get a sufficient execution javascript

interesting because it's dynamic we can do demos and the browser easily

it's they could perhaps you know we

can make a nice IDE out of it perhaps we

target more exotic languages like Haskell which

ends up having similar Nile has very

similar sin that semantics in Haskell and then

you know we could go blue sky and say maybe

we can generate code that runs on the GPU directly from the

math and maybe we can go even further and if and and

generate hardware directly

from the specifications that's expressed in this high-level

map we'll see haven't done that yet yes sure

why

right so I am I am depending

on some magic technology that

can express my compiler in some very succinctly

luckily I'm not the only one on this project

you can probably tell it comes after

my talk right so

I'm gonna breeze through this real quick but this is

explanation of the semantics of the language with

two example kernels on the bottom

yeah it's kind of like kind

of a it's kind of a mix of Haskell and APL

but a very restricted subset of Haskell

with yeah

sorry I gotta move on so

now that now that I have this program this this

programming language to express it in now

I can get you know the core more

than just the core of a 2d rendering about 386 lines

of code really the

two files are the ones that are needed for for

the snow demo the rest of them are

kind of they

expanded of beyond just the core way you need from a 2d renderer the compositor

does although compositing blending modes you get in in

flash in PDF pen stroking gets you the outlines etc

etc but

now I have to get it to run even though I have this language so

initially I was just kind of manly translated

I had like two windows open one with my Niall ideal

code and then one with like JavaScript or C and

I'd kind of pretend like I were a compiler during

the early stages of the project but then

alex is can demonstrate a translator

that the

he worked on that allowed us to generate JavaScript that

could allow this renderer to code code to

run in a web browser so

see

I thought this oh of course not sorry

one so

so we can do just

basic rendering and the way

I do this in the web browser and I'm actually doing all the work in JavaScript

and then there's an API call I can use in the web

browser if anyone knows about the canvas tag I can get I

can fill this a JavaScript array with color values and

then tell the browser just throw those color values on

the screen exactly the way I've popular.if

them in the ray which gets me sort of like a

rudimentary frame buffer so you can zoom in and see

that you know it's anti-alias I

know it looks horrible on the projector huh

it is we need so

that gets us basic anti-aliased rendering and

then I'll just do one more that's

seen and

then we get little fancier with

Safari has an

unusual bug sometimes it doesn't pull in there we go we

can use one of those compositing operations to get

this same star that's been rendered but textured

with with the radial gradient on on to

the picture background so

you can get a pretty good idea the the color fades away as

from the radius it's kind of a standard 2d

rendering okay

all right so

but wait but

now we're working on a novel to see translator again we're doing

translation first alex is working on translator

to go to see and and then

hopefully you know this is something we're hoping to have the next

days will have a practical real-world graphics render

synthesized from this high-level high level mathematics

and just to give you an idea of how this fits

into the whole software development cycle just for the C

generator we have these novel files now

programs go through a novelty translator we spit

out a header file a C file sent it through

the C compiler we get an object file which we link with a

bit of runtime support very little

then you have you have

your application all

right so everything we have just

general policy in the company is everything is open-source

MIT license you can check out my

stuff on github and the future work is

to expand the backends for the compiler

expand the feature set I want to have something that's pretty

close to the commercial 2d renders and

then I'd like to

try other problem domains that

I'm hoping are well suited or that my language

is well suited for like audio decoding or 3d rendering

video decoding data decompression

that type of stuff so I don't have

much time I'm am I'm at a time so

maybe we can hold questions for when we're all done is

thanks now this

microphone working yes

hi so I'm Alex

and just jump

and I guess even before I started working with Alan

I was a programming languages geek kind of and I

always like having ideas about things that could help out

programmers and stuff one thing that really gets to

me : especially at that time

that really got to me was that you can't

just keep having ideas and just sort of you

know experiment with the ideas quickly because

you have to prototype a programming language when

ideas and that usually takes a lot of time there's

a lot of effort that goes into it and programming language

designers like me we tend to get

lethargic you know and feel like oh man okay I have a

couple of ideas that might work but I really have to be

selective because I don't have infinite time to implement

all these things and so I

was so upset about this so

I called my mom and she said she

said Alex I'm a dermatologist what do you want me to do

so that didn't help very much but

but

yeah thank you all so that

luckily Alan pointed me to some

papers from the 1960s and 70s that were

really interesting and one of them was

a paper by Val Shui

who was a guy at UCLA in the 60s and

it was about a language called meta 2 that

he developed and it was a language

it was a compiler generator kind of

very similar to parsing expression grammars that

are sort of involved now and but

the but this was in the 60s and the computing

resources that Valve we had were

very limited and so

and yet somehow he was

able to come up with this little language that was fairly easy

to learn and allowed him to

implement a pretty interesting

subset of Algol in like a page of code

and the language itself the the meta language could

be compiled by itself in about a page

of code as well and so I get that stuff

and I thought wow I have to implement this on my own to try this out

you know the bootstrapping was beautiful everything

so once I did that which

took a day or so I felt

really empowered because I had been using these

uh these larger frameworks like polyglot for

extending Java they had written things by hand

quite a few times to

know that you know it was very costly and so

when I started doing this thing with meta 2 I got

excited and I started extending it to kind

of catch up with the times because for instance the

original thing didn't support backtracking

because resources were limited

and by now you can do as much backtracking as you want and it's

not a big deal so anyway

I had some ideas about extensions that I could have

on this thing and this this was

kind of the the birth of my language called Oh meta which

we have used to implement several programming

languages in this project that we're experimenting with and

the goal of this thing is to minimize

the amount of time that it takes to go from idea to

a working prototype and I'm

not so much I'm not so worried about the

efficiency of the prototype or whatever as long as I can get something

that runs efficiently enough for me to try out the

idea and make sure that it's that

it's a you know an interesting thing to pursue further

and so on but we've had a pretty good luck with that

kind of thing and things that we've made with it have

been fairly efficient so far so what you're looking at

right now is kind of like a small talk workspace

interface that lets you type in some code and evaluate

it on the fly and this is running inside the browser I

have several meta implementations this particular

one uses JavaScript as the target language as the assembly

language underneath and so in this

web browser I can just type in a

bunch of code like well even any

JavaScript expression like that I can

evaluate on the fly but that's

not very interesting right because I as a language guy I

control over the language that I'm using and so the

you tell it to evaluate is not necessarily the

stuff that gets evaluated there's a level of Indra

there's an interaction here in this function groups

called translate code that

gets called with this string that you want to evaluate

and is supposed to return the the

thing that you pass to the eval function in JavaScript

so it doesn't matter what it says right now

but the cool thing about this

is it lets you replace the programming language that's been

that's being used in this interface very

easily and of course it's very self-serving

because Oh Matta is sort of the ideal language as

concerned to write something like translate code I'm

very modest so

let's see here I

don't know why I can't see

well oh

know what's going on hang on one sec technical

difficulties okay so

instead of going over the language and

stuff I'm just gonna say few words about it

hen I'm gonna show you a bunch of examples and end up with

Dan's niall translator so the

the main idea in the language is that pattern matching is

good for most things that you care about in writing a

translator for instance if all you care about

is lexical analysis you could pattern match on a stream of characters

and produce a stream of tokens similarly to

write a parser you can pattern match on the stream of tokens

to produce parse trees and then code

generation at least naive code generation can be

done by pattern matching on a parse tree to

output some code and so on even transformations

on parse trees and optimizations can be done

in the same way and so

let's start off with something

fairly standard so

little while ago is set down with a friend of mine and

I wrote a library in JavaScript that's about 70

lines of code that implements

the semantics of Prolog including your unification

backtracking all that stuff and that's

what's being loaded on the top of the page the

that you see right here is

a grammar written in omena that

teaches the browser how to understand Prolog syntax

it doesn't include things like the special

list syntax you know in Prolog but

that doesn't matter anyway because it's just syntactic sugar so

the the important stuff is there and it's

fairly easy to grasp and gist and so on

so I'm gonna load this stuff

and okay

now

down here I can tell

my Prolog translator to answer certain

Prolog queries given a few

facts and rules just like you would do in a in a

real Prolog interpreter and so

in this first example I'm asking for all the natural numbers given

that zero is a natural number and the successor of X is

a natural number if X is a natural number and so

if I select this stuff

and tell it to execute it's

saying that zero is a natural number so it's kind of small one

natural number two is a natural number and so on

forever until I tell it I'm

done and then this next example should

be very familiar it's

it's

the usual thing that everyone does in Prolog

in their first couple of sessions

right it's a it's an all

male in child world

so I'm asking for all the grandfather and

grandchild relationships given that you

know Abe is Homer's father Homer's Lisa's father homers

Bart's father and homey Homer is

Maggie's father and then there's the rule

for grandfather in there

which yeah it doesn't include women I guess

I'm not PCs so

when I say that you get the right answers

it enumerates all the three relationships that

you care about so

to show one

of these before I move on to the meaty scope

where

is this by

the way this is a wiki also and so anyone

who's interested in this stuff can just open up this webpage

on their browser without downloading anything and see

projects try them out and make their own project save

them and so on

so ok on this page

what I have it's roughly a page of

code here this is logo syntax and

on the left hand side you see sort

of the BNF style rules to describe

logo syntax using left recursion and stuff it's

fairly readable and on the right hand side there's

some JavaScript code that's being output by the semantic

actions and and then

this is the neat part after I've defined

there's a little bit of runtime support above

the grammar I can read the find

translate code to be a function that takes in the code that

you tell it to evaluate and then passes

to smiley my turtle the code to evaluate and

and it doesn't return any useful

value undefined by the way I'm returning the undefined

string because one JavaScript tries

to evaluate the undefined string

it's not going to do much so if I

select all this stuff and tell it to

evaluate quickly this added

my code added a you know dynamically

added a canvas elements to this page and

then down here

so

it's also switched the language that's understood

by this browser where there's a work space

so I can teach it to do a spiral which

is code that I actually took from the Wikipedia page on

on logo and then

if I tell it to draw a spiral and I can

call it was too quickly

- up but I can draw

ell hopefully I don't

cheating but it actually draws in real-time

and it looks really cute so anyway now

I'm going to show you some more interesting examples

first thing I want to show you is that

there's a little JavaScript

compiler it's not really a compiler that's a bit of a misnomer

what this is in this case by

the way I have implemented a very

nearly complete subset of JavaScript it's

about like maybe 90 or 95% of the

language using all meta and I have a translator

that takes the JavaScript program and

outputs some small talk and it

works on top of squeak so that's pretty neat to play with

but I don't have time to show that today and I

have a couple other backends for that but in this case what

I have is a JavaScript parser written in nomada

that's about 120 140

code I don't remember exactly what it is and then

after that I have a translator

that pattern matches on the parse trees that I generate

and outputs the JavaScript code again so it's sort of the identity

transformation on JavaScript which on its own is not

interesting but the neat thing about it is that once you

have something like that you can easily because Oh Matta is object-oriented

you can inherit from these grammars and override

certain rules for instance if you want to add

new kind of statement you override the statement rule and

uh and add some new construct

so I'm gonna skip

over that example but you you guys get the idea so

far right okay and of course

O'Meara is implemented in itself

so

in a very similar style

to that JavaScript translator that

I just showed you so this is the parser for Oh Mehta and

underneath is the code generator which just

translates the parse trees to JavaScript and

I have a little bit of a library that I wrote that's

maybe something like 50 lines of

whatever that supports the semantics of Oh meta in JavaScript

and that's the way a bootstrap Oh

you you just implement

a very minimal set of semantics as a

library in that host language and then I do

the parsing and cogeneration in no

matter but one interesting thing here

is that you don't have to do this you know very direct

two-step process you can do

interesting things with it so for instance the

O meta translator is just taking a parse tree and

outputting the JavaScript but my parser is not extremely

smart for instance if you if

you have nested or expressions you know

hile you're doing your pattern matching as you often do if

I use parentheses you know I say X or Y or

Z that's going to generate two

or operations you know and the or operation

no matter has to remember the position that you're at so

that it can backtrack properly and so on and

that's sort of wasteful so one thing

that I did

that was very straightforward was

I implemented an optimal optimus

asian framework for all meta parse trees in

nomada itself after I had the stuff

working and so what you see on top here is a grammar

that pattern matches on a parse tree

for a matter and by looking at this you can see how little

to implement in order to have a language like cometa it's

very similar to Brian for its pegs you

know you only have or and cleani

star cleany plus this is assignment

which is used for binding expressions to names

there's a knot operation look

ahead and so on so it's fairly straightforward anyway

this is kind of like a visitor for a meta

parse trees and on its own

it's not very useful but then down here what I'm doing

is I'm ism inheriting this visitor and overriding

the and and orals so

that when I have nesting you know if I have an end

that has an end as an argument I can pull out

the parts of that end

into the outer end and the semantics is going to be

the same except it's going to be more efficient because I only have

you know to implement that one operation

and and when I implemented

this the the Oh manage is implementation

became I think 30 percent faster which was pretty

neat for very minimal effort

anyway oh yeah

and the last thing I want to show you here before I

show the Dan

stuff is so if you

if you end up taking the time to take a look to

look at this stuff online I encourage you to look at this project

it's called meta to t oo which is a pun

on you know the meta to which had

the Roman numeral two that I told you about before

and what this is is a language that's very

close to a meta implemented entirely

in this little project and so at first this

this javascript object that

you see up here is a is the

library like object that

implements all of the semantics that you need for doing the

parsing and pattern matching and then down here

what I have is the parser for this language

written in know meta and then I have a couple of

examples you know with with

arithmetic expressions and so on but

then of course that is not sufficient to do bootstrapping

but what you really need to do is once

you have the the Oh Matt alike language working

you want to write that you want to implement that guy in

itself which is what I do down

here and you can see it's a little bit

uglier than no matter particularly because the semantic

actions have to be enclosed in these funny

characters and so on but I did that so that I wouldn't

have to implement the JavaScript parser as part

of this thing right so I can just blindly consume the JavaScript

and output it in the translated code

so anyway that's

the implementation of that and you can compile the compiler with

e original compiler that I wrote with no meta and it works

and then the thing that really tests it later

on is if you take the the version

of the compiler that was generated from the code up

here by using the no matter you know compiler

if you take that and and

compile it with itself and replace the thing you're

using with that result and it still works down

here you know you're you're good and that

kind of works so it's a it's a neat little example of bootstrapping

if you want to take a look

at that later on so I think

oh yeah one less thing that I want to show here

and take a quick look at

this JavaScript doesn't have multi-line string

literals right but if you look at this

I'm actually using one right here it looks very Python

esque and the reason why I can do

that is because you know this translate code thing my

doesn't have to be JavaScript right I have that

intermediate thing the JavaScript parser and and

translator that I showed you before and I can easily inherit

from that and add new kinds

of things so that was very straightforward and the the other neat thing

about having things having these languages implemented

and no matter is that there's a thing called foreign rule

invocation that allows a grammar to lend its

input stream to another grammar temporarily and

it's an it's an alternative to inheritance

for instance that you may have noticed that the language

that I'm using in this workspace is not just JavaScript and

it's not just no matter it's kind of a mash-up of these two languages

and if you wanted to implement that with single

inheritance you would have to inherit from one

of these translators and then implement the functionality

of the other translator which would be very

annoying to have to do and

multiple inheritance is clearly a bad idea I'm not going

to go into that because of all the you

know complications and and so on and so

with foreign rule invocation I can just have one grammar

that doesn't inherit from either if I don't want to and just

says try parsing my input as a no matter

grammar and if that doesn't work try parsing my input as a JavaScript

statement or expression or whatever sorry

punch line yes okay

so what you're looking

at here is part

of my translator for the Niall language that Dan was talking

about so the stuff on top

implements is a is a grammar that on its own implements

the offside rule you know indentation as block structure that

see in Python and Haskell and so on a neat thing

about that is that that's modularized away from

whatever language that you're implementing so all this

stuff like a keeping track of a

stack of indentation levels and so on that can be done

in that one grammar and my

my Nile parser which is down here

also written in no matter just inherits

from that guy and can just say you know

I I want to I want

to indent I don't

know that's identifier anyway

there's there's there's a bunch of indentation

code ah here we go so I want to I

want to tab over here and then there are these

funny unicode characters that dan is very fond

of and so on so

this is the the parser part of the implementation

of Dan's thing and there's also

a type checker and code generator that

are written by pattern matching on those

structures that I'm creating on the right hand side and the

so it's a it's a fairly you

know that one of the cool things about Dan's language is

that in addition to you know types being used

for making sure that you don't get things

wrong the the types matter a lot

for efficient code generation for Niall and

it turned out to be relatively straightforward

to keep track of types in these grammars since

you know the grammars are kind of like class

grammar no matter is pretty much like a class

an object-oriented language you can have state associated

with running instances of that grammar and then

you can keep the symbol table on there and and so on and in

do proper type checking so I

think I'm gonna stop here sorry if I ran a

little long and SM is gonna

nd just to clarify pegs

on their own don't support left recursion but there's

a cool trick that you can do with the memo table that's used by packrat

parsers I wrote a paper about that you

guys Rangers

you have all these

right so

right now I don't have a great answer to that I try

it out and hopefully it works but

we're hoping that at

some point soon we're going to be able to use the princess

and I'll programs that then has I kind

of think of them as the meaning of the thing

I care about and it would be really great to have an automatic

way to check the meaning against

it's true okay

we can discuss

it offline you don't need this

there are

please feel

free to leave us be all the time be another ten minutes

I'm Kazama I work at viewpoints

as well as um understood at UCLA actually

called my father but he said you

should be out party

so what part

of all the interest is I'm sure you have seen an imperative

as well as declarative methodologies to do

programming imperative is how implementations

are darling declarative is we've seen

Prolog language you know its meanings they're compact

they're very understandable

but we need search in order to

to execute them so that the often not practical part

what your interests are here to save codes as

well as to add understandability to problems

is is there a way to kind of combine

both at the same time which is not very common today this

is a famous quote that I made recently that

the natural combination of the claritin

predators is missing a couple

of methodologies that we kind of studied in

this direction is one is I'm just I'm just gonna quickly

go over it but basically

if you add a

layer of logic on top of your

your your languages to support search

basically your heuristic search you can do

programming with a little bit of overhead if

you're always willing to add optimizations so

in the in the presence of multiple methods if

there's an optimization that always tells

you based on the state which method is the is

the good method to take so you always do this check to to

ut the different alternatives then you have this lovely

the overhead of checking to do your normal

imperative but when you do want when you do have

the you know leverage

to do kind of search you can you

have the option to say well explore possibilities

and find the best best scenario to

do so this is what this this prodigies are

all about you know allows you to kind of separate the optimizations

and here is the from from the actual implementations

the actions that you see here to satisfy the

goals so implements that the budget programs

really small they're really cute and slow

but there have this nice way that

you can add for example this chess program

that was about three hundred lines of code that even

included some text ASCII

art graphics where

you could just actually add any arbitrary number of heuristics

that say based on the the states that you

explore basically heuristics tell you which one

is the better one to do and then these heuristics

tell you that you know it's better to take a move

when you actually capture the opponent's piece then

try not to get captures we're adding some numeric

values so you can basically reorder

the you know alternatives

but another more serious one

was you know in compilers need to do register

allocations which is you have registers

and you have variables in the program these variables the

decide where they gonna be in on the registers and

this has happens to be an NP complete problem this hard

problem if you want to do it optimally and then it's this

is nice way because you know you just allow

a high-level goal that that kind of this this

is using methodology in Smalltalk program that

you just expressed the goal that all variables want

to be you know assigned and you then

you have you tell it what what

actions are taken when you're doing this this task

which is usually assigning particular

register with the variable or deciding to spill or split

and then you define the optimizations on top of

this that says based on whatever state you are if

you have room for the next variable then take that

particular method if you have otherwise take the

spill method you know it just in has a layer

on top of your normal logic you can

express that in more

declarative way but the problem with

here is success as you know is that if you're implementing

your own search it's often becomes interactable so

recent or studies then I'm going to show

now is more based on boolean

satisfiability sad solvers constraint

solving technologies which are recently

been shown that it's much you

know it's a scale much better so our Britta

more recent stuff is not based on the search that we come

up with ourselves but based kind of plugging

whatever a tool that we have two external tools

that are really good at solving problems using sad

solving technologies as we will see that

have their own problems that they're kind of not very and

they're not nice to adding user

specific heuristics so

eventually we want some combination of the

two two ways the heuristic searching or sad

solving technologies to rethink that

you know might answer our problem so this

this project is about adding syntactic sugars

to programming languages in this case I'm showing you

examples from an extension of Java language where

we allowing first-order logic expressions

like this or you know set comprehension stuff

like this this is from a lloyd

language actually it's a model object modeling language

so we we allow these kind

of expressions in the language but they serve two purposes one

is that we can easily do sugar these two low-level

syntax of the program so these are actually

runnable so if I but this is actually

a part of the code of the binary tree and

if I actually instantiate an object and I run it

you know because it's gonna be compiled to a low-level

code is going to be runnable even though it's compact but

that's not the only thing that we're interested to save lines

of code we're also interested in having

a runnable executed runnable meanings

meanings that are actually executable you see when

we say meanings we mean high-level expressions

like this that says I want

a graph that is a cyclic then this is the meaning

cyclic that there's no note that that kind of points

back to itself right it's nice to be able to without

implementation I should be able to execute this meaning

that not just running in the program that kind

of using some constraint solving technology to actually

find a satisfying state for

that particular constraint so so

that's what I'm saying executable in terms of we

can use some external tool to get

what state that we're happy without actually any implementations

now we're going to use that for two

things one is the software reliability I'm showing you

an implementation of the bubble sort for

in this this extension that is pretty routine

it's a bubble sort routine but

we see that you know this is in the in light of

you know program annotations you've seen in a Java

modeling language and others where you just

annotate the program with meanings basically

which says this particular method is accomplishing

this this expression this is followed

by that insurance clause that says the job of

the sort method is that it's going to find some value

that's a permutation of the the old alts

all this and it's gonna be a sorted

is something that we can automatically insert instrument

in the in the compiled version so that if when method of

methods are done these constraints

these expression is going to be evaluated

and if they happen to be false that means the

method was faulty method was buggy or if

they if they even happened to have some kind

of runtime failure like a division by

zero that it's not easily found we

can kind of catch that exception and use

the exec use these efficacious

as kind of a fallback as an

alternative that the method didn't work but

we can have an alternative to to try

what accomplish what we want and in this case

we can use we kind

of translate this expression into the synthetic

the logic syntax where we can can call an external tool

to to find basically sort this list

so it's a

live but bigger example is this an implementation

of red-black tree that also have annotations

for the insert and delete methods basically

saying on an insert insert you just

have one one you note added to the set of the

notes and I delete you have one less

and basically assuming

they have some some implementation that's not reliable

you can just you know use this the

annotations to accomplish what what they do actually

you can think of this

so I found the implementation typically

about five six hundred lines of code or three hundred

lines of code of Java because of a lot of corner

cases that these balance trees need to satisfy

this you can think of it as a kind of a

minimalistic runnable implementation as

you will it's like an interface for for

the whoever wants to implement it but the neat thing that

this has that the interfaces don't have its runnable

so you can have actually write what these two methods

are gonna be in the future but because

you have annotated them actually you can we can test them

and run them because yeah you know we

have that underlying reasoning system so

that you actually without the implementation can test your

program interface to

to move around another

so this is the last thing I'm showing is that

you can always intentionally use

this fallback system the use of

fallback when you want to do something bit clearer

deeply you don't you don't even want to implement

something but you know you can use the constraint solving technology

that kind of embedded in your in your language

to accomplish something that's kind of

cumbersome so in this case for example this is a it's

a a GUI

example where this is very simple a user just puts

dots on the screen you see these four dots are

putting in screen without a problem so the the the

job of this particular method the ad body is

very trivial it's just you know draws the dot and this

box shows that there's

this restriction on this this

application that says a user should not

put two dots too close to each other there's a minimum distance that

they might have so you imagine the

the normal you know invocation

of this method is very trivial it just draws it as as

far as those violations are not you know those

specifications are not violated it's okay

it just but under a corner case is

when actually somebody put a red dot here and that

kind of you know violated that

property you don't want you don't want to implement that that's

thing to do potentially a lot of dots needs to be moved

around right so in that case you

just don't handle it in your in your program

and we're gonna kind of you

can't automatically fall back to constraint solving in a sad solving

- to do what - basically shift some dots

around - to satisfy those properties and that's what's happening

here and you

see that that box here is saying there's a restriction

of how much those dots are you know are allowed to shift

by by the by the method so

you see that you know these two are shifted

little bit you know to make sure the separation is happening so basically

I'm showing you the code that that does

this this is the

this is the entire code that when you're when you're adding a

dot you see that it has this this

check that it needs to do that

I'm written here also in a in

a high level syntax of alloy the first order logic that

they have the two things that says no to dust

oo you know too close to each other and when you

do move them you know you're not allowed to remove them by more

than an a value and you see that there's no implementations

here so that when I put that red dot you

know it kind of automatically figured out

those are the things that just

wanted to show you so if you have any questions or

for previous

before

basically

but also II think that we don't have a cat

the other

find

those

Difference between revisions of "How Complex is "Personal Computing"? (2009)"

Latest revision as of 22:03, 6 December 2017

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Tool box

Tools

@@ Line 3: / Line 3: @@
 |id=HAT4iewOHDs
 |alignment=left
-|autoresize=false
+|autoresize=true
 }}
+<subtitle id="0:0:7">so I'll just put thing you guys whoop I  should</subtitle>
+<subtitle id="0:0:10"> get your signature back</subtitle>
+<subtitle id="0:0:13"> I was  just gonna write the name of I'll</subtitle>
+<subtitle id="0:0:16"> put it  over here so the the</subtitle>
+<subtitle id="0:0:19"> basic apologize</subtitle>
+<subtitle id="0:0:22"> in  advance for a couple of</subtitle>
+<subtitle id="0:0:25"> things one</subtitle>
+<subtitle id="0:0:28"> is  one is the</subtitle>
+<subtitle id="0:0:31"> brevity and the</subtitle>
+<subtitle id="0:0:34"> kind of livid  is a navy term for five</subtitle>
+<subtitle id="0:0:37"> pounds of shit  in a one pound bag and</subtitle>
+<subtitle id="0:0:40"> so we have a lot  more information</subtitle>
+<subtitle id="0:0:43"> that we'd like to talk</subtitle>
+<subtitle id="0:0:46">  to you about but we haven't ever</subtitle>
+<subtitle id="0:0:49"> been  able to fit it into an hour and</subtitle>
+<subtitle id="0:0:52"> so we're  gonna try</subtitle>
+<subtitle id="0:0:55"> to give you the gist of some  of the things that we're</subtitle>
+<subtitle id="0:0:58"> doing but this  website</subtitle>
+<subtitle id="0:1:1"> Vpr i.org</subtitle>
+<subtitle id="0:1:7">maybe our talks are kind of a commercial</subtitle>
+<subtitle id="0:1:10">  to just have</subtitle>
+<subtitle id="0:1:13"> you look at some of the  stuff there so I'm just gonna spend a  few</subtitle>
+<subtitle id="0:1:16"> minutes giving you the context</subtitle>
+<subtitle id="0:1:19"> for a  project</subtitle>
+<subtitle id="0:1:22"> that the NSF reviewers turned</subtitle>
+<subtitle id="0:1:25">the preposterous proposal when they  turned it down</subtitle>
+<subtitle id="0:1:28"> anybody ever been turned  down by an</subtitle>
+<subtitle id="0:1:31"> NSF peer review</subtitle>
+<subtitle id="0:1:34"> now it turns  out that the program managers at</subtitle>
+<subtitle id="0:1:37"> NSF  have always had the power to override  those and</subtitle>
+<subtitle id="0:1:40"> in this case the program  manager</subtitle>
+<subtitle id="0:1:43"> did override it so we got our  money anyway</subtitle>
+<subtitle id="0:1:46"> but they only gave us money  to</subtitle>
+<subtitle id="0:1:49"> cover about half the expenses of this  project</subtitle>
+<subtitle id="0:1:52"> so we raised a matching amount  of</subtitle>
+<subtitle id="0:1:55"> money to do it it's a project that a</subtitle>
+<subtitle id="0:1:58">  number of us have been thinking about  for</subtitle>
+<subtitle id="0:2:1"> as long as 30 years that would be  really</subtitle>
+<subtitle id="0:2:4"> interesting to do and</subtitle>
+<subtitle id="0:2:7"> it would be  very much in the original spirit</subtitle>
+<subtitle id="0:2:10"> of what  computer science was supposed to be as  articulated</subtitle>
+<subtitle id="0:2:13"> in the 60s by Al</subtitle>
+<subtitle id="0:2:16">  so</subtitle>
+<subtitle id="0:2:19"> that kind of</subtitle>
+<subtitle id="0:2:22"> starts with the  quintessential Maxwell's equations  t-shirt</subtitle>
+<subtitle id="0:2:25"> and</subtitle>
+<subtitle id="0:2:28"> this is one that everybody's</subtitle>
+<subtitle id="0:2:31">  seen and if</subtitle>
+<subtitle id="0:2:34"> you're familiar with Maxwell  you know that he actually</subtitle>
+<subtitle id="0:2:37"> wrote five  papers arriving</subtitle>
+<subtitle id="0:2:40"> at these conclusions and  in five different ways</subtitle>
+<subtitle id="0:2:43"> he did this over  a period of years using</subtitle>
+<subtitle id="0:2:46"> different models  and the original</subtitle>
+<subtitle id="0:2:49"> form of maskull's  equations was not fiddle on a t-shirt</subtitle>
+<subtitle id="0:2:52">  so this form was</subtitle>
+<subtitle id="0:2:55"> actually made by  several people including</subtitle>
+<subtitle id="0:2:58"> the Germans who  were much more interested in it than the</subtitle>
+<subtitle id="0:3:1">  British in</subtitle>
+<subtitle id="0:3:4"> no small part because  Maxwell's</subtitle>
+<subtitle id="0:3:7"> equations violated Newton and  Newton was</subtitle>
+<subtitle id="0:3:10"> a god Maxwell was only their  best guy</subtitle>
+<subtitle id="0:3:13"> in the 19th century but Newton  was</subtitle>
+<subtitle id="0:3:16"> a god and of course the</subtitle>
+<subtitle id="0:3:19"> interesting  thing about getting him in this form is</subtitle>
+<subtitle id="0:3:22">  although Faraday's</subtitle>
+<subtitle id="0:3:25"> experiments showed  that there</subtitle>
+<subtitle id="0:3:28"> should be a symmetric  relationship between the</subtitle>
+<subtitle id="0:3:31"> electric and  magnetic fields the equation didn't</subtitle>
+<subtitle id="0:3:34"> show  those relations as symmetric</subtitle>
+<subtitle id="0:3:37"> and this  asymmetry and this</subtitle>
+<subtitle id="0:3:40">things led to Einstein's theory of  relativity and</subtitle>
+<subtitle id="0:3:43"> in fact a much simpler  form of writing</subtitle>
+<subtitle id="0:3:46"> these guys down and  reason</subtitle>
+<subtitle id="0:3:49"> I'm putting it up there is I had  a similar</subtitle>
+<subtitle id="0:3:52"> experience when I was in</subtitle>
+<subtitle id="0:3:55">graduate school trying to understand  programming languages and</subtitle>
+<subtitle id="0:3:58"> I looked at  the bottom of page 13 of the list</subtitle>
+<subtitle id="0:4:1"> 1.5  manual and here</subtitle>
+<subtitle id="0:4:4"> was McCarthy's  formulation of Lisp using itself</subtitle>
+<subtitle id="0:4:7"> as a  metal language and</subtitle>
+<subtitle id="0:4:10"> how many people have  had the experience of</subtitle>
+<subtitle id="0:4:13"> going through this  it takes a couple of hours on</subtitle>
+<subtitle id="0:4:16"> a Sunday  afternoon to do and you run out of  fingers</subtitle>
+<subtitle id="0:4:19"> because you have your fingers  down in all the places that recursos</subtitle>
+<subtitle id="0:4:22"> and  reenters and so</subtitle>
+<subtitle id="0:4:25"> forth and I felt I  understand stood it when I found  in</subtitle>
+<subtitle id="0:4:28"> this code there is one bug</subtitle>
+<subtitle id="0:4:31"> and the  thing I got</subtitle>
+<subtitle id="0:4:34"> out of it is boy after those  two hours I</subtitle>
+<subtitle id="0:4:37"> understood what programming  languages were about a factor</subtitle>
+<subtitle id="0:4:40">hundred better than I did before I went  in because</subtitle>
+<subtitle id="0:4:43"> McCarthy had carved away all  the bullshit and</subtitle>
+<subtitle id="0:4:46"> God that's something</subtitle>
+<subtitle id="0:4:49">that was more powerful than any other  programming language of the day</subtitle>
+<subtitle id="0:4:52">powerful expressively the most  programming languages</subtitle>
+<subtitle id="0:4:55"> today and had</subtitle>
+<subtitle id="0:4:58"> done  it in this interesting</subtitle>
+<subtitle id="0:5:1"> form and</subtitle>
+<subtitle id="0:5:4"> in fact  it had a lot of effect on subsequent</subtitle>
+<subtitle id="0:5:7">  things that were done and because I</subtitle>
+<subtitle id="0:5:10"> had  a math degree I just love</subtitle>
+<subtitle id="0:5:13"> this stuff and  so we</subtitle>
+<subtitle id="0:5:16"> tried these ideas a number of  times on</subtitle>
+<subtitle id="0:5:19"> various projects including some  of the stuff we did it  Xerox</subtitle>
+<subtitle id="0:5:22"> PARC that</subtitle>
+<subtitle id="0:5:25"> gee you can</subtitle>
+<subtitle id="0:5:28"> do a  programming language in under a thousand  lines of</subtitle>
+<subtitle id="0:5:31"> code or you might be able to do  it in the page and</subtitle>
+<subtitle id="0:5:34"> there are advantages  to the</subtitle>
+<subtitle id="0:5:37"> page for sure so</subtitle>
+<subtitle id="0:5:40"> so</subtitle>
+<subtitle id="0:5:43"> the thing we  were speculating about is</subtitle>
+<subtitle id="0:5:46"> do you it'd be  really interesting if</subtitle>
+<subtitle id="0:5:52">you could apply this way of looking</subtitle>
+<subtitle id="0:5:55"> at  processes to an entire system that's  well</subtitle>
+<subtitle id="0:5:58"> understood like personal computing  so</subtitle>
+<subtitle id="0:6:1"> we have now this interesting idea  that if</subtitle>
+<subtitle id="0:6:4"> science is the study of and  modeling</subtitle>
+<subtitle id="0:6:7"> of phenomena in order to  understand it better we actually</subtitle>
+<subtitle id="0:6:10"> build  artifacts that exhibit interesting</subtitle>
+<subtitle id="0:6:13">  phenomena and what John</subtitle>
+<subtitle id="0:6:16"> did is to take  the phenomena exhibited by programming</subtitle>
+<subtitle id="0:6:19">languages of the day and find an  abstraction that</subtitle>
+<subtitle id="0:6:22"> captured them his  abstraction happened to be more powerful  than</subtitle>
+<subtitle id="0:6:25"> the ones he was looking at which is  kind of an old</subtitle>
+<subtitle id="0:6:28"> mathematicians trick you  know solved the more</subtitle>
+<subtitle id="0:6:31"> general problem if  you can and so</subtitle>
+<subtitle id="0:6:34"> the idea here was be</subtitle>
+<subtitle id="0:6:37">  interesting to take this body</subtitle>
+<subtitle id="0:6:40"> of  behavior from the end-user to the</subtitle>
+<subtitle id="0:6:43"> metal  of the Machine and</subtitle>
+<subtitle id="0:6:46"> try to understand it</subtitle>
+<subtitle id="0:6:49">by right making a model that you could  actually run it would generate</subtitle>
+<subtitle id="0:6:52"> the same  phenomena and</subtitle>
+<subtitle id="0:6:55"> so how many t-shirts would  it take to</subtitle>
+<subtitle id="0:6:58"> do all of personal computing  that's the question here you</subtitle>
+<subtitle id="0:7:1"> can see why  they called it preposterous right</subtitle>
+<subtitle id="0:7:4">  because Microsoft's version of this is</subtitle>
+<subtitle id="0:7:7"> a  few hundred million lines of code their</subtitle>
+<subtitle id="0:7:10">  operating system and the</subtitle>
+<subtitle id="0:7:13"> same Microsoft  Office is about 220 million</subtitle>
+<subtitle id="0:7:16"> lines of  code but if</subtitle>
+<subtitle id="0:7:19"> you think about it with the  view of well what is it</subtitle>
+<subtitle id="0:7:22"> doing really and  how many things in</subtitle>
+<subtitle id="0:7:25">decided to do differently for example  are</subtitle>
+<subtitle id="0:7:28"> actually the same thing masquerading  under a</subtitle>
+<subtitle id="0:7:31"> few simple parameterizations and</subtitle>
+<subtitle id="0:7:34">  and also the first time around that this  stuff</subtitle>
+<subtitle id="0:7:37"> was done it was only ten thousand  lines of code it at</subtitle>
+<subtitle id="0:7:40"> Xerox PARC and  there's not a lot more</subtitle>
+<subtitle id="0:7:43"> functionality now</subtitle>
+<subtitle id="0:7:46">  than there was back then so the idea is  this</subtitle>
+<subtitle id="0:7:49"> could be a lot smaller and</subtitle>
+<subtitle id="0:7:52"> be very  interesting to see for the same reasons</subtitle>
+<subtitle id="0:7:55">  that these two guys are interesting but  this</subtitle>
+<subtitle id="0:7:58"> would be look look like so that's  what our project  is</subtitle>
+<subtitle id="0:8:1"> and there's one more tea involved  here</subtitle>
+<subtitle id="0:8:4"> which is we one</subtitle>
+<subtitle id="0:8:7"> of the things  that's nice about</subtitle>
+<subtitle id="0:8:10"> making things small  and simple is you got</subtitle>
+<subtitle id="0:8:13"> something like a  Model T Ford which any 12</subtitle>
+<subtitle id="0:8:16"> year old could  take apart in the</subtitle>
+<subtitle id="0:8:19"> barn over the weekend  and put together only had about 350</subtitle>
+<subtitle id="0:8:22">  major parts in it and about a</subtitle>
+<subtitle id="0:8:25"> thousand  screws and nuts and bolts and stuff so  anybody</subtitle>
+<subtitle id="0:8:28"> who grew up in a farm like I did</subtitle>
+<subtitle id="0:8:31">where there's still Model T trucks</subtitle>
+<subtitle id="0:8:34"> and  in the 40 they would be routinely taken  apart</subtitle>
+<subtitle id="0:8:37"> they recently were still around  this you couldn't couldn't really</subtitle>
+<subtitle id="0:8:40"> kill  them because everything</subtitle>
+<subtitle id="0:8:43"> that broke on  them was fixable in the blacksmithing</subtitle>
+<subtitle id="0:8:46">  shop that every farm had back then there  was nothing</subtitle>
+<subtitle id="0:8:49"> true they didn't even have a  distributor they didn't even have gears</subtitle>
+<subtitle id="0:8:52">  they had</subtitle>
+<subtitle id="0:8:55"> belts and pulleys on them</subtitle>
+<subtitle id="0:8:58"> so  but they're a real automobiles so they  had this</subtitle>
+<subtitle id="0:9:1"> interesting thing they caused  even though their automobiles</subtitle>
+<subtitle id="0:9:4"> around and  before them they caused the automobile  revolution</subtitle>
+<subtitle id="0:9:7"> in America because they were  so easy to</subtitle>
+<subtitle id="0:9:10"> manufacture and they lasted  well and so forth so</subtitle>
+<subtitle id="0:9:13"> just one bottle T</subtitle>
+<subtitle id="0:9:16">  story the</subtitle>
+<subtitle id="0:9:19"> gap the spark</subtitle>
+<subtitle id="0:9:22"> gap on Model T  was</subtitle>
+<subtitle id="0:9:25"> optimized to be the width of a dime</subtitle>
+<subtitle id="0:9:28">  and somebody asked Henry Ford once why</subtitle>
+<subtitle id="0:9:31">  did you do that and he said well people  always</subtitle>
+<subtitle id="0:9:34"> lose gauges but they usually have  a dime on them</subtitle>
+<subtitle id="0:9:37"> so he's fully expected  anybody who's had one of</subtitle>
+<subtitle id="0:9:40"> these things  would be able to just fix it and tweak  it up and</subtitle>
+<subtitle id="0:9:43"> that's what happened so it's a  nice metaphor</subtitle>
+<subtitle id="0:9:46">so</subtitle>
+<subtitle id="0:9:49"> my theory is before you write the  Ferrari code</subtitle>
+<subtitle id="0:9:52"> you should write model-t  code because there's</subtitle>
+<subtitle id="0:9:55"> a 12 year old kid  who just isn't gonna be able to</subtitle>
+<subtitle id="0:9:58">understand the Ferrari code and you have  a moral obligation</subtitle>
+<subtitle id="0:10:1"> to write that Model T  code that is understandable</subtitle>
+<subtitle id="0:10:4"></subtitle>
+<subtitle id="0:10:7"> so</subtitle>
+<subtitle id="0:10:10"> kind of  the standard model for personal</subtitle>
+<subtitle id="0:10:13">  computing is from the</subtitle>
+<subtitle id="0:10:16"> Xerox PARC</subtitle>
+<subtitle id="0:10:19">  experience and so</subtitle>
+<subtitle id="0:10:22"> the bitmap screen that  can display anything and</subtitle>
+<subtitle id="0:10:25"> a way of  organizing views on</subtitle>
+<subtitle id="0:10:28"> the display and  people</subtitle>
+<subtitle id="0:10:31"> have been confused by the  difference between desktop publishing</subtitle>
+<subtitle id="0:10:34">  and Microsoft for instance has</subtitle>
+<subtitle id="0:10:37"> been and  window display</subtitle>
+<subtitle id="0:10:40"> they're actually the same  thing just these</subtitle>
+<subtitle id="0:10:43"> guys have boundaries  around the views and</subtitle>
+<subtitle id="0:10:46">publishing you don't have boundaries  around the views</subtitle>
+<subtitle id="0:10:49"> but aside from that  everything else is exactly the</subtitle>
+<subtitle id="0:10:52"> same and  it was done with the same code</subtitle>
+<subtitle id="0:10:55"> so this  is a modern version of it</subtitle>
+<subtitle id="0:10:58"> and I'm</subtitle>
+<subtitle id="0:11:1">  disappointed in this display because</subtitle>
+<subtitle id="0:11:4">  Danny molang has done a lot of work to</subtitle>
+<subtitle id="0:11:7">  do really fantastic graphics</subtitle>
+<subtitle id="0:11:10"> which some  of the</subtitle>
+<subtitle id="0:11:13"> things are shown here and you  can't see</subtitle>
+<subtitle id="0:11:16"> how crisp and beautiful it is  but this is kind</subtitle>
+<subtitle id="0:11:19"> of a modern version of  it done with some of the stuff that</subtitle>
+<subtitle id="0:11:22"> that  that</subtitle>
+<subtitle id="0:11:25"> we've done and just to show you a  little slant</subtitle>
+<subtitle id="0:11:28"> of it  here</subtitle>
+<subtitle id="0:11:31"> so I I can</subtitle>
+<subtitle id="0:11:34"> edit this as I'm as I'm</subtitle>
+<subtitle id="0:11:37">  used to doing</subtitle>
+<subtitle id="0:11:40">and</subtitle>
+<subtitle id="0:11:43"> but I can this</subtitle>
+<subtitle id="0:11:46"> thing is programmed  completely differently than the way you  might think</subtitle>
+<subtitle id="0:11:49"> so for instance the the</subtitle>
+<subtitle id="0:11:52"> code  behind these paragraphs is the</subtitle>
+<subtitle id="0:11:55">  justification and the editor</subtitle>
+<subtitle id="0:11:58"> for come to  about 23</subtitle>
+<subtitle id="0:12:1"> lines of code in one of the  languages we developed</subtitle>
+<subtitle id="0:12:4"> to do this and  I'm not gonna explain</subtitle>
+<subtitle id="0:12:7"> exactly how we did  this but I'll just give you a little</subtitle>
+<subtitle id="0:12:10">  flavor of what's actually going on here  so</subtitle>
+<subtitle id="0:12:13"> you can think of this as swarm  programming</subtitle>
+<subtitle id="0:12:16"> so what we have is thousands</subtitle>
+<subtitle id="0:12:19">  and thousands of parallel processes</subtitle>
+<subtitle id="0:12:22">  running at the same time and these are</subtitle>
+<subtitle id="0:12:25">  all objects and</subtitle>
+<subtitle id="0:12:28"> so the slowest</subtitle>
+<subtitle id="0:12:31"> simplest  way you can think of</subtitle>
+<subtitle id="0:12:34"> doing the</subtitle>
+<subtitle id="0:12:37"> problem  here is</subtitle>
+<subtitle id="0:12:40"> well just follow the guy in</subtitle>
+<subtitle id="0:12:43">front of you if you don't have anybody  in front of you you know where</subtitle>
+<subtitle id="0:12:46"> to go if  you're over the margin tell the guy in  front of you</subtitle>
+<subtitle id="0:12:49"> and if somebody tells you  they're on the margin and you're the</subtitle>
+<subtitle id="0:12:52">first there's a blank in front of you  then go to the next line all</subtitle>
+<subtitle id="0:12:55"> right so  that's four things that do</subtitle>
+<subtitle id="0:12:58"> a text  justification</subtitle>
+<subtitle id="0:13:1"> Oulu sore anything they're  just all</subtitle>
+<subtitle id="0:13:4"> running and they're related to  each other so we call</subtitle>
+<subtitle id="0:13:7"> this particles and  fields type programming and</subtitle>
+<subtitle id="0:13:10"> there's a  lot of it in this in the system</subtitle>
+<subtitle id="0:13:13"> and you  notice that I've embedded a view</subtitle>
+<subtitle id="0:13:16"> of the  entire document recursively into it so</subtitle>
+<subtitle id="0:13:19">  that was operating at the same time so</subtitle>
+<subtitle id="0:13:22">this is basically this kind of stuff in  which</subtitle>
+<subtitle id="0:13:25"> each part of the thing has been  mathematize dand done in</subtitle>
+<subtitle id="0:13:28"> a separate  programming language and of course we  have to</subtitle>
+<subtitle id="0:13:31"> make the programming languages  to do it we have to make the tools to  make the</subtitle>
+<subtitle id="0:13:34"> programming languages to do it</subtitle>
+<subtitle id="0:13:37">  and</subtitle>
+<subtitle id="0:13:40">but what we don't try to do so these are  the</subtitle>
+<subtitle id="0:13:43"> three main operating systems and</subtitle>
+<subtitle id="0:13:46">  won't tell you which one the lemon is</subtitle>
+<subtitle id="0:13:49">  but they're all big and</subtitle>
+<subtitle id="0:13:52"> we want to avoid  apples and oranges</subtitle>
+<subtitle id="0:13:55"> comparison so</subtitle>
+<subtitle id="0:13:58"> the  stuff that we're doing is is</subtitle>
+<subtitle id="0:14:1"> not there's  nothing that we can do</subtitle>
+<subtitle id="0:14:4"> that can be  honestly compared to</subtitle>
+<subtitle id="0:14:7"> what Microsoft or  Apple do because</subtitle>
+<subtitle id="0:14:10"> they have legacy  problems we don't have</subtitle>
+<subtitle id="0:14:13"> there's a million  things so we don't even worry about that</subtitle>
+<subtitle id="0:14:16">  but here's a t-shirt with a mustard seed  on</subtitle>
+<subtitle id="0:14:19"> it and that gives you kind of what  we're out after</subtitle>
+<subtitle id="0:14:22"> out after more than a  factor of a thousand change</subtitle>
+<subtitle id="0:14:25"> in the size  of the code that it takes to make this</subtitle>
+<subtitle id="0:14:28">  kind of phenomena something</subtitle>
+<subtitle id="0:14:31"> more like a  factor of 10,000</subtitle>
+<subtitle id="0:14:34"> and</subtitle>
+<subtitle id="0:14:37">so</subtitle>
+<subtitle id="0:14:40"> if you have the end-user at one end  and you have a power supply at</subtitle>
+<subtitle id="0:14:43"> the other  you have a lot</subtitle>
+<subtitle id="0:14:46"> of different kinds of  phenomena in there and the question</subtitle>
+<subtitle id="0:14:49">how many t-shirts do you actually have  to do so</subtitle>
+<subtitle id="0:14:52"> you think of the the two</subtitle>
+<subtitle id="0:14:55"> and a  half D anti-alias graphics as</subtitle>
+<subtitle id="0:14:58"> you'd love  to have that in one or two t-shirts</subtitle>
+<subtitle id="0:15:1">o that's regularly a couple hundred  thousand lines of</subtitle>
+<subtitle id="0:15:4"> code and if</subtitle>
+<subtitle id="0:15:7"> you think  of the number of different languages you</subtitle>
+<subtitle id="0:15:10">  might want to invent to mathematize the  different</subtitle>
+<subtitle id="0:15:13"> parts of these things there's  probably five or ten different languages  you</subtitle>
+<subtitle id="0:15:16"> have to do so you have to have a  metal language metal language has</subtitle>
+<subtitle id="0:15:19"> to  deal with itself and and so forth and</subtitle>
+<subtitle id="0:15:22">  you'd</subtitle>
+<subtitle id="0:15:25"> like to improve semantics of  programming and so</subtitle>
+<subtitle id="0:15:28"> forth so we have a  dozen or so powerful</subtitle>
+<subtitle id="0:15:31"> principles here are  ten of them there's nothing more</subtitle>
+<subtitle id="0:15:34"> boring  than somebody enumerated list</subtitle>
+<subtitle id="0:15:37"> on a slide  so I'll just</subtitle>
+<subtitle id="0:15:40"> point out that most of  these powerful principles</subtitle>
+<subtitle id="0:15:43">have been around since I started in  computing in the early</subtitle>
+<subtitle id="0:15:46"> 60s and most of</subtitle>
+<subtitle id="0:15:49">them are not in general use today or in  use the way they</subtitle>
+<subtitle id="0:15:52"> were originally used so</subtitle>
+<subtitle id="0:15:55">  some of these are things that</subtitle>
+<subtitle id="0:15:58"> have been  resurrected so</subtitle>
+<subtitle id="0:16:1"> the particles infield is  something that hasn't</subtitle>
+<subtitle id="0:16:4"> hasn't been used  very much but</subtitle>
+<subtitle id="0:16:7"> the notion of simulating  time not letting the CPU</subtitle>
+<subtitle id="0:16:10"> determine what  time is all about goes back</subtitle>
+<subtitle id="0:16:13"> to both  Simula and john</subtitle>
+<subtitle id="0:16:16"> mccarthy situation  calculus these are</subtitle>
+<subtitle id="0:16:19"> old ideas but they</subtitle>
+<subtitle id="0:16:22">have the great advantage that you don't  get</subtitle>
+<subtitle id="0:16:25"> deadlocks from trying to use  monitors and semaphores  so</subtitle>
+<subtitle id="0:16:28"> the basic idea is if you simulate the  time that</subtitle>
+<subtitle id="0:16:31"> you're running in you cannot  have race conditions that you haven't  explicitly</subtitle>
+<subtitle id="0:16:34"> allowed and so</subtitle>
+<subtitle id="0:16:37"> on so the  underlying idea here is that</subtitle>
+<subtitle id="0:16:40"> math wins  not standard math but</subtitle>
+<subtitle id="0:16:43"> math that you  actually invent in order</subtitle>
+<subtitle id="0:16:46"> to characterize  all the different behaviors that you</subtitle>
+<subtitle id="0:16:49">  half and with that I'm going to</subtitle>
+<subtitle id="0:16:52"> turn it  over to Dan amma lang who</subtitle>
+<subtitle id="0:16:55"> will talk to  you a little bit about how we do the  graphics</subtitle>
+<subtitle id="0:16:58"> because this is kind of a  classic case study</subtitle>
+<subtitle id="0:17:1"> of</subtitle>
+<subtitle id="0:17:4"> give you this</subtitle>
+<subtitle id="0:17:7"> dan  is a graduate</subtitle>
+<subtitle id="0:17:10"> student at UC san diego  and</subtitle>
+<subtitle id="0:17:13"> just got his master's for part</subtitle>
+<subtitle id="0:17:16">his and is on his way to getting his  PhD for</subtitle>
+<subtitle id="0:17:19"> the rest of it</subtitle>
+<subtitle id="0:17:22"> and well what  we'd like to</subtitle>
+<subtitle id="0:17:25"> do here is to I don't</subtitle>
+<subtitle id="0:17:28"> think  anything I said needs questions except  maybe</subtitle>
+<subtitle id="0:17:31"> to the end but be great  I brought</subtitle>
+<subtitle id="0:17:34"> the three people who did a lot  of work</subtitle>
+<subtitle id="0:17:37"> in this system along there</subtitle>
+<subtitle id="0:17:40">the time you get to my age you're just a  figurehead some</subtitle>
+<subtitle id="0:17:43"> thrill to actual  actually</subtitle>
+<subtitle id="0:17:46"> bring people who are doing  stuff here and to have them</subtitle>
+<subtitle id="0:17:49"> tell you a  little bit about how they're approaching  these</subtitle>
+<subtitle id="0:17:52"> problems and hope you do ask</subtitle>
+<subtitle id="0:17:55">  questions hello</subtitle>
+<subtitle id="0:17:58"> so like Alan said my  name is</subtitle>
+<subtitle id="0:18:1"> Dan am Liang I'm a grad student  like you guys</subtitle>
+<subtitle id="0:18:4"> so go easy on me I'm</subtitle>
+<subtitle id="0:18:7">  getting towards the end of my</subtitle>
+<subtitle id="0:18:10"> times of  PhD students so</subtitle>
+<subtitle id="0:18:13"> I'm gonna present to you  basically</subtitle>
+<subtitle id="0:18:16"> where I am on my dissertation  work I have still</subtitle>
+<subtitle id="0:18:19"> about a year and a  little more than</subtitle>
+<subtitle id="0:18:22"> that to go although  I've noticed that kind of just extends</subtitle>
+<subtitle id="0:18:25">  forward it's a tradition of PhD</subtitle>
+<subtitle id="0:18:28"> students  right so</subtitle>
+<subtitle id="0:18:31"> I'm a UCSD PhD student and I  but</subtitle>
+<subtitle id="0:18:34"> I'm also an employee of viewpoints  Research Institute</subtitle>
+<subtitle id="0:18:37"> and so my little  niche in this project</subtitle>
+<subtitle id="0:18:40"> is the 2d  rendering system because we'd</subtitle>
+<subtitle id="0:18:43">build  a whole</subtitle>
+<subtitle id="0:18:46"> basically a whole software stack</subtitle>
+<subtitle id="0:18:49">and we're not allowed to just delegate  to the</subtitle>
+<subtitle id="0:18:52"> operating system routines we want  to reinvent programming</subtitle>
+<subtitle id="0:18:55"> at every level  so I have some background in computer</subtitle>
+<subtitle id="0:18:58">  graphics and some in programming  languages</subtitle>
+<subtitle id="0:19:1"> and computer architecture and  so</subtitle>
+<subtitle id="0:19:4"> basically it fell on me to</subtitle>
+<subtitle id="0:19:7"> figure out  how to do two new rendering so the the</subtitle>
+<subtitle id="0:19:10">sub-project of mine is called Jazeera  and like</subtitle>
+<subtitle id="0:19:13"> I said it's a 2d graphics  rendering the spirit of this project</subtitle>
+<subtitle id="0:19:16"> the  idea is to provide something that's  practical</subtitle>
+<subtitle id="0:19:19"> useful for the other projects  sub</subtitle>
+<subtitle id="0:19:22"> projects that viewpoints to actually  use specifically</subtitle>
+<subtitle id="0:19:25"> the focus right now is  building</subtitle>
+<subtitle id="0:19:28"> user interfaces and so my</subtitle>
+<subtitle id="0:19:31"> job  is to discover what are the minimal  algorithms</subtitle>
+<subtitle id="0:19:34"> the powerful abstractions new  representations so</subtitle>
+<subtitle id="0:19:37"> that I don't use up  our code but budget and</subtitle>
+<subtitle id="0:19:40"> just in my sub  project because</subtitle>
+<subtitle id="0:19:43"> the goal here is again  is to happen</subtitle>
+<subtitle id="0:19:46"> and you know the whole  system's the whole thing is is minimal</subtitle>
+<subtitle id="0:19:49">  so and again this isn't</subtitle>
+<subtitle id="0:19:52">hough I'm doing computer graphics the  focus here is more</subtitle>
+<subtitle id="0:19:55"> software engineering  I'm not going to do</subtitle>
+<subtitle id="0:19:58"> anything that's  really advancing the state-of-the-art  computer</subtitle>
+<subtitle id="0:20:1"> graphics so much so</subtitle>
+<subtitle id="0:20:4"> what are  the requirements of this graphics  library</subtitle>
+<subtitle id="0:20:7"> well today in today's systems</subtitle>
+<subtitle id="0:20:10">  you expect anti-aliased vector graphics</subtitle>
+<subtitle id="0:20:13">  what people use nowadays is typically  flash</subtitle>
+<subtitle id="0:20:16"> SVG core graphics on mac OS x</subtitle>
+<subtitle id="0:20:19">  windows presentation foundation so</subtitle>
+<subtitle id="0:20:22"> that  that's kind of and not my competitors  but</subtitle>
+<subtitle id="0:20:25"> what's similar to what</subtitle>
+<subtitle id="0:20:28"> currently  provides that functionality today</subtitle>
+<subtitle id="0:20:31"> in  commercial systems right so in</subtitle>
+<subtitle id="0:20:34"> that in a  2d render you want to have bezzie</subtitle>
+<subtitle id="0:20:37">  outlines for your shapes you want to be  able to display text</subtitle>
+<subtitle id="0:20:40"> transformations  clipping all pretty</subtitle>
+<subtitle id="0:20:43"> traditional stuff  the blending</subtitle>
+<subtitle id="0:20:46"> operations digital images  pen stroking for</subtitle>
+<subtitle id="0:20:49"> the outline of  of</subtitle>
+<subtitle id="0:20:52"> shapes so as</subtitle>
+<subtitle id="0:20:55"> I was working on this I  started with the Cairo open-source</subtitle>
+<subtitle id="0:20:58">  vendor project</subtitle>
+<subtitle id="0:21:1"> which I've been working  on before I joined</subtitle>
+<subtitle id="0:21:4"> viewpoints and so I  was able to take kind of a lessons</subtitle>
+<subtitle id="0:21:7">learned from working on Cairo which is  the render</subtitle>
+<subtitle id="0:21:10"> behind Firefox and various</subtitle>
+<subtitle id="0:21:13">  open source applications and so</subtitle>
+<subtitle id="0:21:16"> as I was  kind of going through the Cairo code and</subtitle>
+<subtitle id="0:21:19">  thinking you know stepping back from it  and figure</subtitle>
+<subtitle id="0:21:22"> out what really is the high  level intention</subtitle>
+<subtitle id="0:21:25"> of these coders I came</subtitle>
+<subtitle id="0:21:28">  across the rasterization stage which is  probably</subtitle>
+<subtitle id="0:21:31"> the most complex part of the  whole</subtitle>
+<subtitle id="0:21:34"> software library anyone who's  taken an undergrad</subtitle>
+<subtitle id="0:21:37"> computer graphics of  course that's had to implement</subtitle>
+<subtitle id="0:21:40"> like  scanline fill knows that it's it's it's</subtitle>
+<subtitle id="0:21:43">kind of tricky getting all the edge  cases and and there really</subtitle>
+<subtitle id="0:21:46"> isn't a  strict formula that tells you what what</subtitle>
+<subtitle id="0:21:49">he output should be there it's usually  described as some sort</subtitle>
+<subtitle id="0:21:52"> of an algorithm  with data structures active edge list  etc</subtitle>
+<subtitle id="0:21:55"> and and so I couldn't figure</subtitle>
+<subtitle id="0:21:58">know what really is the highest level  semantics of rasterization</subtitle>
+<subtitle id="0:22:1"> so</subtitle>
+<subtitle id="0:22:4"> and it's  difficult so I looked</subtitle>
+<subtitle id="0:22:7"> at I look at some  kind of non-traditional algorithms</subtitle>
+<subtitle id="0:22:10"> for  forwarding Astros ation especially</subtitle>
+<subtitle id="0:22:13">things specific to 2d because I can kind  of ignore the complexities</subtitle>
+<subtitle id="0:22:16"> of 3d here  and</subtitle>
+<subtitle id="0:22:19"> and and you</subtitle>
+<subtitle id="0:22:22"> know one one method kind  of stuck out at me there's</subtitle>
+<subtitle id="0:22:25"> this approach  called analytic area based anti-aliasing</subtitle>
+<subtitle id="0:22:28">  rasterization that looks sort of like</subtitle>
+<subtitle id="0:22:31">formula but everyone's still expressed  in terms of like a big</subtitle>
+<subtitle id="0:22:34"> K statement and  so I felt</subtitle>
+<subtitle id="0:22:37"> you know there's still  something to be extracted here so I</subtitle>
+<subtitle id="0:22:40">  called my mom</subtitle>
+<subtitle id="0:22:43"> luckily she's a high  school geometry teacher</subtitle>
+<subtitle id="0:22:46"> and  a great</subtitle>
+<subtitle id="0:22:49"> partner to have and trying to  figure out all this computational</subtitle>
+<subtitle id="0:22:52">  geometry that I was in the middle and so  we had</subtitle>
+<subtitle id="0:22:55"> we sat down for about 10 days and</subtitle>
+<subtitle id="0:22:58">  did like pair programming with a pencil  and paper</subtitle>
+<subtitle id="0:23:1"> and we didn't end up with an  interesting formula</subtitle>
+<subtitle id="0:23:4"> if you pose a  problem this way if we</subtitle>
+<subtitle id="0:23:7"> say given the XY  coordinates to the lower left corner of</subtitle>
+<subtitle id="0:23:10">a pixel we can say that the coverage  contribution of</subtitle>
+<subtitle id="0:23:13"> one edge of that shape  is calculated</subtitle>
+<subtitle id="0:23:16"> this way so if we just  look at it one edge at a time you</subtitle>
+<subtitle id="0:23:19"> can  actually use it using an approximation</subtitle>
+<subtitle id="0:23:22">  square for the pixel you can the bottom</subtitle>
+<subtitle id="0:23:25">function is what you is kind of what you  want to look at most</subtitle>
+<subtitle id="0:23:28"> it's just that you  can actually combine these</subtitle>
+<subtitle id="0:23:31"> three pretty  much standard functions in in</subtitle>
+<subtitle id="0:23:34"> 2d  geometry in an interesting way</subtitle>
+<subtitle id="0:23:37"> that gets  you a nice coverage</subtitle>
+<subtitle id="0:23:40"> result from 0 to 100  so if the the</subtitle>
+<subtitle id="0:23:43"> pixel is entirely outside  of the figure at 0 if</subtitle>
+<subtitle id="0:23:46">entirely within you get 100 if it's on  the edge you get somewhere</subtitle>
+<subtitle id="0:23:49"> between the  two and</subtitle>
+<subtitle id="0:23:52"> I only have 10 minutes but</subtitle>
+<subtitle id="0:23:55">  basically the top one is variation</subtitle>
+<subtitle id="0:23:58"> of  the area of a trapezoid the second one  is the</subtitle>
+<subtitle id="0:24:1"> clamp function in mathematics and  the third one is a</subtitle>
+<subtitle id="0:24:4"> variation of the  point slope formula</subtitle>
+<subtitle id="0:24:7"> for line anyway</subtitle>
+<subtitle id="0:24:10">once we have it for that one edge then  it</subtitle>
+<subtitle id="0:24:13"> works out such that you the total  coverage</subtitle>
+<subtitle id="0:24:16"> contribution of the entire  polygon is just a linear</subtitle>
+<subtitle id="0:24:19"> combination of  those edge contributions with the little  additional</subtitle>
+<subtitle id="0:24:22"> adjustment so now we have a  formula</subtitle>
+<subtitle id="0:24:25"> but this doesn't execute so</subtitle>
+<subtitle id="0:24:28"> I  haven't really won yet but at</subtitle>
+<subtitle id="0:24:31"> least I've  you know posed it in a way that then I  can</subtitle>
+<subtitle id="0:24:34"> imagine some sort of higher-level  language that can that</subtitle>
+<subtitle id="0:24:37"> can turn this  into actual executable code so the  punchline</subtitle>
+<subtitle id="0:24:40"> is oh okay so then to verify  it  you</subtitle>
+<subtitle id="0:24:43"> know I wrote some prototypes I have</subtitle>
+<subtitle id="0:24:46">this node demo all I'll do for you  basically you're</subtitle>
+<subtitle id="0:24:49"> going to see you're  gonna see</subtitle>
+<subtitle id="0:24:52"> 1,000 snowflakes they're all  identical so</subtitle>
+<subtitle id="0:24:55"> it's not very realistic  that all</subtitle>
+<subtitle id="0:24:58"> have independent position  a vertical velocity</subtitle>
+<subtitle id="0:25:1"> and angular velocity  and</subtitle>
+<subtitle id="0:25:4"> I'll just animate them and I'm not</subtitle>
+<subtitle id="0:25:7">using the GPU at all here this is just  on the CPU</subtitle>
+<subtitle id="0:25:10"> I render it to an image a  bitmap and</subtitle>
+<subtitle id="0:25:13"> then just hand it to the  operating system to throw up on the  screen</subtitle>
+<subtitle id="0:25:16"> and so this isn't really speed  demon</subtitle>
+<subtitle id="0:25:19"> per se but it's just to prove that  first of all visual</subtitle>
+<subtitle id="0:25:22"> results are good and  that</subtitle>
+<subtitle id="0:25:25"> it's fast enough that I'm not  paying myself into a corner</subtitle>
+<subtitle id="0:25:28"></subtitle>
+<subtitle id="0:25:31"> yeah and  then so after it starts up it'll</subtitle>
+<subtitle id="0:25:34"> fade in  a bit this is actually supposed to be  white</subtitle>
+<subtitle id="0:25:37"> or light blue on black you just  imagine</subtitle>
+<subtitle id="0:25:40"> this I'm sorry it's</subtitle>
+<subtitle id="0:25:43"> kind of  painful for maintenance</subtitle>
+<subtitle id="0:25:46"> and so I just no  flex because we</subtitle>
+<subtitle id="0:25:49"> want to render text  really quickly without having to use</subtitle>
+<subtitle id="0:25:52">some sort of cash and speech scheme  because that kind of muddies up your</subtitle>
+<subtitle id="0:25:55">code so as long as I can render  something that's text like</subtitle>
+<subtitle id="0:25:58"> because each  one of these snowflakes</subtitle>
+<subtitle id="0:26:1"> is composed of  64 cubic Bezier which</subtitle>
+<subtitle id="0:26:4"> is usually much  more than what a typical</subtitle>
+<subtitle id="0:26:7"> glyph is that  you render on the screen</subtitle>
+<subtitle id="0:26:10"> so as long as I  can do these snowflakes quickly then you  know that</subtitle>
+<subtitle id="0:26:13"> I can make a case that it'll  scale out to the text</subtitle>
+<subtitle id="0:26:16"> rendering so  zooming and just to show you that it's  vector</subtitle>
+<subtitle id="0:26:19"> graphics not not just</subtitle>
+<subtitle id="0:26:22"> raster  graphics it's being scaled it's it's</subtitle>
+<subtitle id="0:26:25">coming from the vector primitives at  each frame</subtitle>
+<subtitle id="0:26:28"> yeah this is like when the  screen savers you</subtitle>
+<subtitle id="0:26:31"> can stare out all day  but hip denies</subtitle>
+<subtitle id="0:26:34"> me enough so then</subtitle>
+<subtitle id="0:26:37"> so then  yeah here's the punchline</subtitle>
+<subtitle id="0:26:40"> the goal was  to figure out how to express all that</subtitle>
+<subtitle id="0:26:43"> in  80 lines of code</subtitle>
+<subtitle id="0:26:46"> and I'll explain what  this is so</subtitle>
+<subtitle id="0:26:49"> this is a new programming  language called called</subtitle>
+<subtitle id="0:26:52"> nyle again the  goal is to</subtitle>
+<subtitle id="0:26:55"> express the 2d rendering in a  way that is both succinctly</subtitle>
+<subtitle id="0:26:58"> on matted to  a variety of execution</subtitle>
+<subtitle id="0:27:1"> environments and  doesn't preclude efficient execution</subtitle>
+<subtitle id="0:27:4">  so after</subtitle>
+<subtitle id="0:27:7"> writing these prototypes it</subtitle>
+<subtitle id="0:27:10"> it  seemed to me that the best model</subtitle>
+<subtitle id="0:27:13"> for for  the software would be a dataflow</subtitle>
+<subtitle id="0:27:16"> stream  processing model more generic</subtitle>
+<subtitle id="0:27:19"> then then  like the stream the stream languages</subtitle>
+<subtitle id="0:27:22">  today are kind of more tied to specific  deep</subtitle>
+<subtitle id="0:27:25"> to GPU hardware this is kind of a  more</subtitle>
+<subtitle id="0:27:28"> abstract stream processing model so</subtitle>
+<subtitle id="0:27:31">  yeah the idea is that everything is</subtitle>
+<subtitle id="0:27:34">just data streams that are being  processed by a series of kernels</subtitle>
+<subtitle id="0:27:37"> that  have been connected in a network and in  an interesting</subtitle>
+<subtitle id="0:27:40"> interesting fashion and  you get your pixel values</subtitle>
+<subtitle id="0:27:43"> at that at the  end of the pipeline and then we want</subtitle>
+<subtitle id="0:27:46">optimize the syntax for each one of  those kernels for</subtitle>
+<subtitle id="0:27:49"> expressing arithmetic  vector</subtitle>
+<subtitle id="0:27:52"> computations you know domain  basically</subtitle>
+<subtitle id="0:27:55"> domain-specific language for  arithmetic</subtitle>
+<subtitle id="0:27:58"> stream processing and</subtitle>
+<subtitle id="0:28:1"> then we  want to be able to then generate</subtitle>
+<subtitle id="0:28:4"> code  for a variety of environments so like a  generate</subtitle>
+<subtitle id="0:28:7"> code to see because that'll get  a sufficient execution javascript</subtitle>
+<subtitle id="0:28:10">interesting because it's dynamic we can  do demos and the browser easily</subtitle>
+<subtitle id="0:28:13"> it's  they could perhaps you know we</subtitle>
+<subtitle id="0:28:16"> can make  a nice IDE out of it perhaps we</subtitle>
+<subtitle id="0:28:19">target more exotic languages like  Haskell which</subtitle>
+<subtitle id="0:28:22"> ends up having similar  Nile has very</subtitle>
+<subtitle id="0:28:25"> similar sin that semantics  in Haskell and then</subtitle>
+<subtitle id="0:28:28"> you know we could go  blue sky and say maybe</subtitle>
+<subtitle id="0:28:31"> we can generate  code that runs on the GPU directly from  the</subtitle>
+<subtitle id="0:28:34"> math and maybe we can go even  further and if and and</subtitle>
+<subtitle id="0:28:37"> generate hardware  directly</subtitle>
+<subtitle id="0:28:40"> from the specifications that's  expressed in this high-level</subtitle>
+<subtitle id="0:28:43"> map we'll  see haven't done that yet yes sure</subtitle>
+<subtitle id="0:28:55">why</subtitle>
+<subtitle id="0:29:7">right so I am I am depending</subtitle>
+<subtitle id="0:29:10"> on some  magic technology that</subtitle>
+<subtitle id="0:29:13"> can express my  compiler in some very succinctly</subtitle>
+<subtitle id="0:29:16"> luckily  I'm not the only one on this project</subtitle>
+<subtitle id="0:29:19"> you  can probably tell it comes after</subtitle>
+<subtitle id="0:29:22"> my talk  right so</subtitle>
+<subtitle id="0:29:25"> I'm gonna breeze through this  real quick but this is</subtitle>
+<subtitle id="0:29:28">explanation of the semantics of the  language with</subtitle>
+<subtitle id="0:29:31"> two example kernels on the  bottom</subtitle>
+<subtitle id="0:29:34"> yeah it's kind of like kind</subtitle>
+<subtitle id="0:29:37"> of a  it's kind of a mix of Haskell and APL</subtitle>
+<subtitle id="0:29:40">  but a very restricted subset of Haskell</subtitle>
+<subtitle id="0:29:43">  with yeah</subtitle>
+<subtitle id="0:29:46"> sorry I gotta move on so</subtitle>
+<subtitle id="0:29:49"> now  that now that I have this program this  this</subtitle>
+<subtitle id="0:29:52"> programming language to express it  in now</subtitle>
+<subtitle id="0:29:55"> I can get you know the core more</subtitle>
+<subtitle id="0:29:58">than just the core of a 2d rendering  about 386 lines</subtitle>
+<subtitle id="0:30:1"> of code really the</subtitle>
+<subtitle id="0:30:4">two files are the ones that are needed  for for</subtitle>
+<subtitle id="0:30:7"> the snow demo the rest of them  are</subtitle>
+<subtitle id="0:30:10"> kind of they</subtitle>
+<subtitle id="0:30:13"> expanded of beyond just  the core way you need from a 2d renderer  the compositor</subtitle>
+<subtitle id="0:30:16"> does although compositing  blending modes you get in in</subtitle>
+<subtitle id="0:30:19"> flash in  PDF pen stroking gets you the outlines  etc</subtitle>
+<subtitle id="0:30:22"> etc but</subtitle>
+<subtitle id="0:30:25"> now I have to get it to run  even though I have this language so</subtitle>
+<subtitle id="0:30:28">initially I was just kind of manly  translated</subtitle>
+<subtitle id="0:30:31"> I had like two windows open  one with my Niall ideal</subtitle>
+<subtitle id="0:30:34"> code and then  one with like JavaScript or C and</subtitle>
+<subtitle id="0:30:37"> I'd  kind of pretend like I were a compiler  during</subtitle>
+<subtitle id="0:30:40"> the early stages of the project  but then</subtitle>
+<subtitle id="0:30:43"> alex is can demonstrate a  translator</subtitle>
+<subtitle id="0:30:46"> that the</subtitle>
+<subtitle id="0:30:49"> he worked on that  allowed us to generate JavaScript that</subtitle>
+<subtitle id="0:30:52">  could allow this renderer to code code  to</subtitle>
+<subtitle id="0:30:55"> run in a web browser so</subtitle>
+<subtitle id="0:30:58">see</subtitle>
+<subtitle id="0:31:4">I thought this oh of course not sorry</subtitle>
+<subtitle id="0:31:7">one  so</subtitle>
+<subtitle id="0:31:10">  so we can do just</subtitle>
+<subtitle id="0:31:13"> basic rendering and  the way</subtitle>
+<subtitle id="0:31:16"> I do this in the web browser and  I'm actually doing all the work in  JavaScript</subtitle>
+<subtitle id="0:31:19"> and then there's an API call  I can use in the web</subtitle>
+<subtitle id="0:31:22"> browser if anyone  knows about the canvas tag I can get I</subtitle>
+<subtitle id="0:31:25">can fill this a JavaScript array with  color values and</subtitle>
+<subtitle id="0:31:28"> then tell the browser  just throw those color values on</subtitle>
+<subtitle id="0:31:31"> the  screen exactly the way I've popular.if</subtitle>
+<subtitle id="0:31:34">  them in the ray which gets me sort of  like a</subtitle>
+<subtitle id="0:31:37"> rudimentary frame buffer so you  can zoom in and see</subtitle>
+<subtitle id="0:31:40"> that you know it's  anti-alias I</subtitle>
+<subtitle id="0:31:43"> know it looks horrible on  the projector huh</subtitle>
+<subtitle id="0:31:46"> it is we need so</subtitle>
+<subtitle id="0:31:49"> that  gets us basic anti-aliased rendering and</subtitle>
+<subtitle id="0:31:52">  then I'll just do one more that's</subtitle>
+<subtitle id="0:31:55"> seen  and</subtitle>
+<subtitle id="0:31:58"> then we get little fancier with</subtitle>
+<subtitle id="0:32:1">Safari has an</subtitle>
+<subtitle id="0:32:4"> unusual bug sometimes it  doesn't pull in there we go we</subtitle>
+<subtitle id="0:32:7"> can use  one of those compositing operations to  get</subtitle>
+<subtitle id="0:32:10"> this same star that's been rendered  but textured</subtitle>
+<subtitle id="0:32:13"> with with the radial  gradient on on to</subtitle>
+<subtitle id="0:32:16"> the picture background  so</subtitle>
+<subtitle id="0:32:19"> you can get a pretty good idea the  the color fades away as</subtitle>
+<subtitle id="0:32:22">from the radius it's kind of a standard  2d</subtitle>
+<subtitle id="0:32:25"> rendering okay</subtitle>
+<subtitle id="0:32:28"> all right so</subtitle>
+<subtitle id="0:32:31"> but wait  but</subtitle>
+<subtitle id="0:32:34"> now we're working on a novel to see  translator again we're doing</subtitle>
+<subtitle id="0:32:37">translation first alex is working on  translator</subtitle>
+<subtitle id="0:32:40"> to go to see and and then</subtitle>
+<subtitle id="0:32:43">hopefully you know this is something  we're hoping to have the next</subtitle>
+<subtitle id="0:32:46">days will have a practical real-world  graphics render</subtitle>
+<subtitle id="0:32:49"> synthesized from this  high-level high level mathematics</subtitle>
+<subtitle id="0:32:52"> and  just to give you an idea of how this  fits</subtitle>
+<subtitle id="0:32:55"> into the whole software development  cycle just for the C</subtitle>
+<subtitle id="0:32:58"> generator we have  these novel files now</subtitle>
+<subtitle id="0:33:1"> programs go  through a novelty translator we spit</subtitle>
+<subtitle id="0:33:4"> out  a header file a C file sent it through</subtitle>
+<subtitle id="0:33:7">the C compiler we get an object file  which we link with a</subtitle>
+<subtitle id="0:33:10"> bit of runtime  support very little</subtitle>
+<subtitle id="0:33:13">then you have  you have</subtitle>
+<subtitle id="0:33:16"> your application all</subtitle>
+<subtitle id="0:33:19"> right so  everything we have just</subtitle>
+<subtitle id="0:33:22"> general policy  in the company is everything is  open-source</subtitle>
+<subtitle id="0:33:25"> MIT license you can check  out my</subtitle>
+<subtitle id="0:33:28"> stuff on github and the future  work is</subtitle>
+<subtitle id="0:33:31"> to expand the backends for the  compiler</subtitle>
+<subtitle id="0:33:34"> expand the feature set I want  to have something that's pretty</subtitle>
+<subtitle id="0:33:37"> close to  the commercial 2d renders and</subtitle>
+<subtitle id="0:33:40"> then I'd  like to</subtitle>
+<subtitle id="0:33:43"> try other problem domains that</subtitle>
+<subtitle id="0:33:46">  I'm hoping are well suited or that my  language</subtitle>
+<subtitle id="0:33:49"> is well suited for like audio  decoding or 3d rendering</subtitle>
+<subtitle id="0:33:52"> video decoding  data decompression</subtitle>
+<subtitle id="0:33:55"> that type of stuff so  I don't have</subtitle>
+<subtitle id="0:33:58"> much time  I'm am I'm at a time so</subtitle>
+<subtitle id="0:34:1"> maybe we can  hold questions for when we're all done  is</subtitle>
+<subtitle id="0:34:16">thanks now this</subtitle>
+<subtitle id="0:34:19"> microphone working yes</subtitle>
+<subtitle id="0:35:4">hi so I'm Alex</subtitle>
+<subtitle id="0:35:7"> and just jump</subtitle>
+<subtitle id="0:35:10">and I guess even before I started  working with Alan</subtitle>
+<subtitle id="0:35:13"> I was a programming  languages geek kind of and I</subtitle>
+<subtitle id="0:35:16"> always like  having ideas about things that could  help out</subtitle>
+<subtitle id="0:35:19"> programmers and stuff one thing  that really gets to</subtitle>
+<subtitle id="0:35:22"> me :  especially at that time</subtitle>
+<subtitle id="0:35:25"> that really got  to me was that you can't</subtitle>
+<subtitle id="0:35:28"> just keep  having ideas and just sort of you</subtitle>
+<subtitle id="0:35:31"> know  experiment with the ideas quickly  because</subtitle>
+<subtitle id="0:35:34"> you have to prototype a  programming language when</subtitle>
+<subtitle id="0:35:37">ideas and that usually takes a lot of  time there's</subtitle>
+<subtitle id="0:35:40"> a lot of effort that goes  into it and programming language</subtitle>
+<subtitle id="0:35:43">  designers like me we tend to get</subtitle>
+<subtitle id="0:35:46">lethargic you know and feel like oh man  okay I have a</subtitle>
+<subtitle id="0:35:49"> couple of ideas that might  work but I really have to be</subtitle>
+<subtitle id="0:35:52"> selective  because I don't have infinite time to  implement</subtitle>
+<subtitle id="0:35:55"> all these things and so I</subtitle>
+<subtitle id="0:35:58"> was  so upset about this so</subtitle>
+<subtitle id="0:36:1"> I called my mom  and she said she</subtitle>
+<subtitle id="0:36:4"> said Alex I'm a  dermatologist what do you want me to do</subtitle>
+<subtitle id="0:36:7">  so that didn't help very much but</subtitle>
+<subtitle id="0:36:10"> but</subtitle>
+<subtitle id="0:36:13">  yeah thank you all so that</subtitle>
+<subtitle id="0:36:16"> luckily Alan  pointed me to some</subtitle>
+<subtitle id="0:36:19"> papers from the 1960s  and 70s that were</subtitle>
+<subtitle id="0:36:22"> really interesting and  one of them was</subtitle>
+<subtitle id="0:36:25"> a paper by Val Shui</subtitle>
+<subtitle id="0:36:28"> who  was a guy at UCLA in the 60s and</subtitle>
+<subtitle id="0:36:31"> it was  about a language called meta 2 that</subtitle>
+<subtitle id="0:36:34"> he  developed and it was a language</subtitle>
+<subtitle id="0:36:37"> it was a  compiler generator kind of</subtitle>
+<subtitle id="0:36:40">very similar to parsing expression  grammars that</subtitle>
+<subtitle id="0:36:43"> are sort of involved now  and but</subtitle>
+<subtitle id="0:36:46"> the but this was in the 60s and  the computing</subtitle>
+<subtitle id="0:36:49"> resources that Valve we  had were</subtitle>
+<subtitle id="0:36:52"> very limited and so</subtitle>
+<subtitle id="0:36:55"> and yet  somehow he was</subtitle>
+<subtitle id="0:36:58"> able to come up with this  little language that was fairly easy</subtitle>
+<subtitle id="0:37:1"> to  learn and allowed him to</subtitle>
+<subtitle id="0:37:4"> implement a  pretty interesting</subtitle>
+<subtitle id="0:37:7"> subset of Algol in  like a page of code</subtitle>
+<subtitle id="0:37:10"> and the language  itself the the meta language could</subtitle>
+<subtitle id="0:37:13"> be  compiled by itself in about a page</subtitle>
+<subtitle id="0:37:16"> of  code as well and so I  get that stuff</subtitle>
+<subtitle id="0:37:19"> and I thought wow I have  to implement this on my own to try this  out</subtitle>
+<subtitle id="0:37:22">  you know the bootstrapping was beautiful  everything</subtitle>
+<subtitle id="0:37:25"> so once I did that which</subtitle>
+<subtitle id="0:37:28">took a day or so  I felt</subtitle>
+<subtitle id="0:37:31"> really empowered because I had  been using these</subtitle>
+<subtitle id="0:37:34"> uh these larger  frameworks like polyglot for</subtitle>
+<subtitle id="0:37:37"> extending  Java they had written things by hand</subtitle>
+<subtitle id="0:37:40">  quite a few times to</subtitle>
+<subtitle id="0:37:43"> know that you know  it was very costly and so</subtitle>
+<subtitle id="0:37:46"> when I started  doing this thing with meta 2 I got</subtitle>
+<subtitle id="0:37:49">  excited and I started extending it to  kind</subtitle>
+<subtitle id="0:37:52"> of catch up with the times because  for instance the</subtitle>
+<subtitle id="0:37:55"> original thing didn't  support backtracking</subtitle>
+<subtitle id="0:37:58"> because resources  were limited</subtitle>
+<subtitle id="0:38:1"> and by now you can do as  much backtracking as you want and it's</subtitle>
+<subtitle id="0:38:4">  not a big deal so anyway</subtitle>
+<subtitle id="0:38:7"> I had some  ideas about extensions that I could have</subtitle>
+<subtitle id="0:38:10">  on this thing and this this was</subtitle>
+<subtitle id="0:38:13"> kind of  the the birth of my language called Oh  meta which</subtitle>
+<subtitle id="0:38:16"> we have used to implement  several programming</subtitle>
+<subtitle id="0:38:19"> languages in this  project that we're experimenting with  and</subtitle>
+<subtitle id="0:38:22"> the goal of this thing is to  minimize</subtitle>
+<subtitle id="0:38:25"> the amount of time that it  takes to go from idea to</subtitle>
+<subtitle id="0:38:28"> a working  prototype and I'm</subtitle>
+<subtitle id="0:38:31"> not so much I'm not so  worried about the</subtitle>
+<subtitle id="0:38:34"> efficiency of the  prototype or whatever as long as I can  get something</subtitle>
+<subtitle id="0:38:36"> that runs efficiently  enough for me to try out the</subtitle>
+<subtitle id="0:38:39"> idea and  make sure that it's that</subtitle>
+<subtitle id="0:38:43"> it's a you know  an interesting thing to pursue further</subtitle>
+<subtitle id="0:38:45">and so on  but we've had a pretty good luck with  that</subtitle>
+<subtitle id="0:38:48"> kind of thing and things that we've  made with it have</subtitle>
+<subtitle id="0:38:51"> been fairly efficient  so far so what you're looking at</subtitle>
+<subtitle id="0:38:54"> right  now is kind of like a small talk  workspace</subtitle>
+<subtitle id="0:38:57"> interface that lets you type  in some code and evaluate</subtitle>
+<subtitle id="0:39:0"> it on the fly  and this is running inside the browser I</subtitle>
+<subtitle id="0:39:3">have several meta implementations this  particular</subtitle>
+<subtitle id="0:39:6"> one uses JavaScript as the  target language as the assembly</subtitle>
+<subtitle id="0:39:9"> language  underneath and so in this</subtitle>
+<subtitle id="0:39:12"> web browser I  can just type in a</subtitle>
+<subtitle id="0:39:15"> bunch of code like  well even any</subtitle>
+<subtitle id="0:39:18"> JavaScript expression like  that I can</subtitle>
+<subtitle id="0:39:21"> evaluate on the fly but  that's</subtitle>
+<subtitle id="0:39:24"> not very interesting right  because I as a language guy I</subtitle>
+<subtitle id="0:39:27">control over the language that I'm using  and so the</subtitle>
+<subtitle id="0:39:30">you tell it to evaluate is not  necessarily the</subtitle>
+<subtitle id="0:39:33"> stuff that gets  evaluated there's a level of Indra</subtitle>
+<subtitle id="0:39:36">there's an interaction here in this  function groups</subtitle>
+<subtitle id="0:39:39"> called translate code  that</subtitle>
+<subtitle id="0:39:42"> gets called with this string that  you want to evaluate</subtitle>
+<subtitle id="0:39:45"> and is supposed to  return the the</subtitle>
+<subtitle id="0:39:48"> thing that you pass to  the eval function in JavaScript</subtitle>
+<subtitle id="0:39:51"> so it  doesn't matter what it says right now</subtitle>
+<subtitle id="0:39:54">  but the cool thing about this</subtitle>
+<subtitle id="0:39:57"> is it lets  you replace the programming language  that's been</subtitle>
+<subtitle id="0:40:0"> that's being used in this  interface very</subtitle>
+<subtitle id="0:40:3"> easily and of course it's  very self-serving</subtitle>
+<subtitle id="0:40:6"> because Oh Matta is  sort of the ideal language as</subtitle>
+<subtitle id="0:40:9">concerned to write something like  translate code  I'm</subtitle>
+<subtitle id="0:40:12"> very modest so</subtitle>
+<subtitle id="0:40:15"> let's see here I</subtitle>
+<subtitle id="0:40:18">  don't know why I can't see</subtitle>
+<subtitle id="0:40:21"> well oh</subtitle>
+<subtitle id="0:40:24">know what's going on hang on one sec  technical</subtitle>
+<subtitle id="0:40:27"> difficulties okay so</subtitle>
+<subtitle id="0:40:30"> instead  of going over the language and</subtitle>
+<subtitle id="0:40:33"> stuff I'm  just gonna say few words about it</subtitle>
+<subtitle id="0:40:36">hen I'm gonna show you a bunch of  examples and end up with</subtitle>
+<subtitle id="0:40:39"> Dan's niall  translator so the</subtitle>
+<subtitle id="0:40:42"> the main idea in the  language is that pattern matching is</subtitle>
+<subtitle id="0:40:45">good for most things that you care about  in writing a</subtitle>
+<subtitle id="0:40:48"> translator for instance if  all you care about</subtitle>
+<subtitle id="0:40:51"> is lexical analysis  you could pattern match on a stream of  characters</subtitle>
+<subtitle id="0:40:54"> and produce a stream of  tokens similarly to</subtitle>
+<subtitle id="0:40:57"> write a parser you  can pattern match on the stream of  tokens</subtitle>
+<subtitle id="0:41:0"> to produce parse trees and then  code</subtitle>
+<subtitle id="0:41:3"> generation at least naive code  generation can be</subtitle>
+<subtitle id="0:41:6"> done by pattern  matching on a parse tree to</subtitle>
+<subtitle id="0:41:9"> output some  code and so on even transformations</subtitle>
+<subtitle id="0:41:12"> on  parse trees and optimizations can be  done</subtitle>
+<subtitle id="0:41:15"> in the same way and so</subtitle>
+<subtitle id="0:41:18"> let's start  off with something</subtitle>
+<subtitle id="0:41:21"> fairly standard so</subtitle>
+<subtitle id="0:41:24">little while ago is set down with a  friend of mine and</subtitle>
+<subtitle id="0:41:27"> I wrote a library in  JavaScript that's about 70</subtitle>
+<subtitle id="0:41:30"> lines of code  that implements</subtitle>
+<subtitle id="0:41:33"> the semantics of Prolog  including your unification</subtitle>
+<subtitle id="0:41:36"> backtracking  all that stuff and that's</subtitle>
+<subtitle id="0:41:39"> what's being  loaded on the top of the page the</subtitle>
+<subtitle id="0:41:42">that you see right here  is</subtitle>
+<subtitle id="0:41:45"> a grammar written in omena that</subtitle>
+<subtitle id="0:41:48">  teaches the browser how to understand  Prolog syntax</subtitle>
+<subtitle id="0:41:51"> it doesn't include things  like the special</subtitle>
+<subtitle id="0:41:54"> list syntax you know in  Prolog but</subtitle>
+<subtitle id="0:41:57"> that doesn't matter anyway  because it's just syntactic sugar so</subtitle>
+<subtitle id="0:42:0"> the  the important stuff is there and it's</subtitle>
+<subtitle id="0:42:3">  fairly easy to grasp and gist and so on</subtitle>
+<subtitle id="0:42:6">  so I'm gonna load this stuff</subtitle>
+<subtitle id="0:42:9"> and okay</subtitle>
+<subtitle id="0:42:12">  now</subtitle>
+<subtitle id="0:42:15"> down here I can tell</subtitle>
+<subtitle id="0:42:18"> my Prolog  translator to answer certain</subtitle>
+<subtitle id="0:42:21"> Prolog  queries given a few</subtitle>
+<subtitle id="0:42:24"> facts and rules just  like you would do in a in a</subtitle>
+<subtitle id="0:42:27"> real Prolog  interpreter and so</subtitle>
+<subtitle id="0:42:30"> in this first example  I'm asking for all the natural numbers  given</subtitle>
+<subtitle id="0:42:33"> that zero is a natural number and  the successor of X is</subtitle>
+<subtitle id="0:42:36"> a natural number  if X is a natural number and so</subtitle>
+<subtitle id="0:42:39"> if I  select this stuff</subtitle>
+<subtitle id="0:42:42"> and tell it to execute  it's</subtitle>
+<subtitle id="0:42:45"> saying that zero is a natural  number so it's kind of small one</subtitle>
+<subtitle id="0:42:48">natural number two is a natural number  and so on</subtitle>
+<subtitle id="0:42:51"> forever until I tell it I'm</subtitle>
+<subtitle id="0:42:54">  done and then this next example should</subtitle>
+<subtitle id="0:42:57">  be very familiar it's</subtitle>
+<subtitle id="0:43:0"> it's</subtitle>
+<subtitle id="0:43:3"> the usual  thing that everyone does in Prolog</subtitle>
+<subtitle id="0:43:6"> in  their first couple of sessions</subtitle>
+<subtitle id="0:43:9"> right  it's a it's an all</subtitle>
+<subtitle id="0:43:12"> male in child world</subtitle>
+<subtitle id="0:43:15">  so I'm asking for all the grandfather  and</subtitle>
+<subtitle id="0:43:18"> grandchild relationships given that  you</subtitle>
+<subtitle id="0:43:21"> know Abe is Homer's father Homer's  Lisa's father homers</subtitle>
+<subtitle id="0:43:24"> Bart's father and  homey Homer is</subtitle>
+<subtitle id="0:43:27"> Maggie's father and then  there's the rule</subtitle>
+<subtitle id="0:43:30"> for grandfather in  there</subtitle>
+<subtitle id="0:43:33"> which yeah it doesn't include  women I guess</subtitle>
+<subtitle id="0:43:36"> I'm not PCs so</subtitle>
+<subtitle id="0:43:39"> when I say  that you get the right answers</subtitle>
+<subtitle id="0:43:42"> it  enumerates all the three relationships  that</subtitle>
+<subtitle id="0:43:45"> you care about so</subtitle>
+<subtitle id="0:43:48">to show  one</subtitle>
+<subtitle id="0:43:51"> of these before I move on to the  meaty scope</subtitle>
+<subtitle id="0:43:54"> where</subtitle>
+<subtitle id="0:43:57"> is this by</subtitle>
+<subtitle id="0:44:0"> the way  this is a wiki also and so anyone</subtitle>
+<subtitle id="0:44:3"> who's  interested in this stuff can just open  up this webpage</subtitle>
+<subtitle id="0:44:6"> on their browser without  downloading anything and see</subtitle>
+<subtitle id="0:44:9">projects try them out and make their own  project save</subtitle>
+<subtitle id="0:44:12"> them and so on</subtitle>
+<subtitle id="0:44:15"> so ok on  this page</subtitle>
+<subtitle id="0:44:18"> what I have it's roughly a  page of</subtitle>
+<subtitle id="0:44:21"> code here this is logo syntax  and</subtitle>
+<subtitle id="0:44:24"> on the left hand side you see sort</subtitle>
+<subtitle id="0:44:27">  of the BNF style rules to describe</subtitle>
+<subtitle id="0:44:30">logo syntax using left recursion and  stuff it's</subtitle>
+<subtitle id="0:44:33"> fairly readable and on the  right hand side there's</subtitle>
+<subtitle id="0:44:36"> some JavaScript  code that's being output by the semantic</subtitle>
+<subtitle id="0:44:39">  actions and and then</subtitle>
+<subtitle id="0:44:42"> this is the neat  part after I've defined</subtitle>
+<subtitle id="0:44:45">there's a little bit of runtime support  above</subtitle>
+<subtitle id="0:44:48"> the grammar I can read the find</subtitle>
+<subtitle id="0:44:51">translate code to be a function that  takes in the code that</subtitle>
+<subtitle id="0:44:54"> you tell it to  evaluate and then passes</subtitle>
+<subtitle id="0:44:57"> to smiley my  turtle the code to evaluate and</subtitle>
+<subtitle id="0:45:0"> and it  doesn't return any useful</subtitle>
+<subtitle id="0:45:3"> value  undefined by the way I'm returning the  undefined</subtitle>
+<subtitle id="0:45:6"> string because one JavaScript  tries</subtitle>
+<subtitle id="0:45:9"> to evaluate the undefined string</subtitle>
+<subtitle id="0:45:12">  it's not going to do much so if I</subtitle>
+<subtitle id="0:45:15"> select  all this stuff and tell it to</subtitle>
+<subtitle id="0:45:18"> evaluate  quickly this added</subtitle>
+<subtitle id="0:45:21"> my code added a you  know dynamically</subtitle>
+<subtitle id="0:45:24"> added a canvas elements  to this page and</subtitle>
+<subtitle id="0:45:27"> then down here</subtitle>
+<subtitle id="0:45:30"> so</subtitle>
+<subtitle id="0:45:33"> it's  also switched the language that's  understood</subtitle>
+<subtitle id="0:45:36"> by this browser where there's  a work space</subtitle>
+<subtitle id="0:45:39"> so I can teach it to do a  spiral which</subtitle>
+<subtitle id="0:45:42"> is code that I actually  took from the Wikipedia page on</subtitle>
+<subtitle id="0:45:45"> on logo  and then</subtitle>
+<subtitle id="0:45:48"> if I tell it to draw a spiral  and I can</subtitle>
+<subtitle id="0:45:51"> call  it was too quickly</subtitle>
+<subtitle id="0:45:54"> - up but I can draw</subtitle>
+<subtitle id="0:46:0">ell hopefully I don't</subtitle>
+<subtitle id="0:46:3">cheating but it actually draws in  real-time</subtitle>
+<subtitle id="0:46:6"> and it looks really cute so  anyway now</subtitle>
+<subtitle id="0:46:9"> I'm going to show you some  more interesting examples</subtitle>
+<subtitle id="0:46:12"> first thing I  want to show you is that</subtitle>
+<subtitle id="0:46:15"> there's a  little JavaScript</subtitle>
+<subtitle id="0:46:18"> compiler it's not  really a compiler that's a bit of a  misnomer</subtitle>
+<subtitle id="0:46:21"> what this is in this case by</subtitle>
+<subtitle id="0:46:24">  the way I have implemented a very</subtitle>
+<subtitle id="0:46:27"> nearly  complete subset of JavaScript it's</subtitle>
+<subtitle id="0:46:30"> about  like maybe 90 or 95% of the</subtitle>
+<subtitle id="0:46:33"> language  using all meta and I have a translator</subtitle>
+<subtitle id="0:46:36">  that takes the JavaScript program and</subtitle>
+<subtitle id="0:46:39">  outputs some small talk and it</subtitle>
+<subtitle id="0:46:42"> works on  top of squeak so that's pretty neat to  play with</subtitle>
+<subtitle id="0:46:45"> but I don't have time to show  that today and I</subtitle>
+<subtitle id="0:46:48"> have a couple other  backends for that but in this case what</subtitle>
+<subtitle id="0:46:51">  I have is a JavaScript parser written in  nomada</subtitle>
+<subtitle id="0:46:54"> that's about 120 140</subtitle>
+<subtitle id="0:46:57">code I don't remember exactly what it is  and then</subtitle>
+<subtitle id="0:47:0"> after that I have a translator</subtitle>
+<subtitle id="0:47:3">that pattern matches on the parse trees  that I generate</subtitle>
+<subtitle id="0:47:6"> and outputs the  JavaScript code again so it's sort of  the identity</subtitle>
+<subtitle id="0:47:9"> transformation on  JavaScript which on its own is not</subtitle>
+<subtitle id="0:47:12">interesting but the neat thing about it  is that once you</subtitle>
+<subtitle id="0:47:15"> have something like  that you can easily because Oh Matta is  object-oriented</subtitle>
+<subtitle id="0:47:18"> you can inherit from  these grammars and override</subtitle>
+<subtitle id="0:47:21"> certain  rules for instance if you want to add</subtitle>
+<subtitle id="0:47:24">new kind of statement you override the  statement rule and</subtitle>
+<subtitle id="0:47:27"> uh and add some new  construct</subtitle>
+<subtitle id="0:47:30"> so I'm gonna skip</subtitle>
+<subtitle id="0:47:33"> over that  example but you you guys get the idea so</subtitle>
+<subtitle id="0:47:36">  far right okay and of course</subtitle>
+<subtitle id="0:47:39"> O'Meara is  implemented in itself</subtitle>
+<subtitle id="0:47:42"> so</subtitle>
+<subtitle id="0:47:45"> in a very  similar style</subtitle>
+<subtitle id="0:47:48"> to that JavaScript  translator that</subtitle>
+<subtitle id="0:47:51"> I just showed you so  this is the parser for Oh Mehta and</subtitle>
+<subtitle id="0:47:54">  underneath is the code generator which  just</subtitle>
+<subtitle id="0:47:57"> translates the parse trees to  JavaScript and</subtitle>
+<subtitle id="0:48:0"> I have a little bit of a  library that I wrote that's</subtitle>
+<subtitle id="0:48:3"> maybe  something like 50 lines of</subtitle>
+<subtitle id="0:48:6">whatever that supports the semantics of  Oh meta in JavaScript</subtitle>
+<subtitle id="0:48:9"> and that's the way  a bootstrap Oh</subtitle>
+<subtitle id="0:48:12">you  you just implement</subtitle>
+<subtitle id="0:48:15"> a very minimal set of  semantics as a</subtitle>
+<subtitle id="0:48:18"> library in that host  language and then I do</subtitle>
+<subtitle id="0:48:21"> the parsing and  cogeneration in no</subtitle>
+<subtitle id="0:48:24"> matter but one  interesting thing here</subtitle>
+<subtitle id="0:48:27"> is that you don't  have to do this you know very direct</subtitle>
+<subtitle id="0:48:30">  two-step process you can do</subtitle>
+<subtitle id="0:48:33">interesting things with it so for  instance the</subtitle>
+<subtitle id="0:48:36"> O meta translator is just  taking a parse tree and</subtitle>
+<subtitle id="0:48:39"> outputting the  JavaScript but my parser is not  extremely</subtitle>
+<subtitle id="0:48:42"> smart for instance if you if</subtitle>
+<subtitle id="0:48:45">  you have nested or expressions you know</subtitle>
+<subtitle id="0:48:48">hile you're doing your pattern matching  as you often do if</subtitle>
+<subtitle id="0:48:51"> I use parentheses you  know I say X or Y or</subtitle>
+<subtitle id="0:48:54"> Z that's going to  generate two</subtitle>
+<subtitle id="0:48:57"> or operations you know and  the or operation</subtitle>
+<subtitle id="0:49:0"> no matter has to  remember the position that you're at so</subtitle>
+<subtitle id="0:49:3">that it can backtrack properly and so on  and</subtitle>
+<subtitle id="0:49:6"> that's sort of wasteful so one thing</subtitle>
+<subtitle id="0:49:9">  that I did</subtitle>
+<subtitle id="0:49:12"> that was very straightforward  was</subtitle>
+<subtitle id="0:49:15"> I implemented an optimal optimus</subtitle>
+<subtitle id="0:49:18">  asian framework for all meta parse trees  in</subtitle>
+<subtitle id="0:49:21"> nomada itself after I had the stuff</subtitle>
+<subtitle id="0:49:24">  working and so what you see on top here  is a grammar</subtitle>
+<subtitle id="0:49:27"> that pattern matches on a  parse tree</subtitle>
+<subtitle id="0:49:30"> for a matter and by looking  at this you can see how little</subtitle>
+<subtitle id="0:49:33">to implement in order to have a language  like cometa it's</subtitle>
+<subtitle id="0:49:36"> very similar to Brian  for its pegs you</subtitle>
+<subtitle id="0:49:39"> know you only have or  and cleani</subtitle>
+<subtitle id="0:49:42"> star cleany plus this is  assignment</subtitle>
+<subtitle id="0:49:45"> which is used for binding  expressions to names</subtitle>
+<subtitle id="0:49:48"> there's a knot  operation look</subtitle>
+<subtitle id="0:49:51"> ahead and so on so it's  fairly straightforward anyway</subtitle>
+<subtitle id="0:49:54"> this is  kind of like a visitor for a meta</subtitle>
+<subtitle id="0:49:57"> parse  trees and on its own</subtitle>
+<subtitle id="0:50:0"> it's not very  useful but then down here what I'm doing</subtitle>
+<subtitle id="0:50:3">  is I'm ism inheriting this visitor and  overriding</subtitle>
+<subtitle id="0:50:6"> the and and orals so</subtitle>
+<subtitle id="0:50:9"> that  when I have nesting you know if I have  an end</subtitle>
+<subtitle id="0:50:12"> that has an end as an argument I  can pull out</subtitle>
+<subtitle id="0:50:15"> the parts of that end</subtitle>
+<subtitle id="0:50:18"> into  the outer end and the semantics is going  to be</subtitle>
+<subtitle id="0:50:21"> the same except it's going to be  more efficient because I only have</subtitle>
+<subtitle id="0:50:24"> you  know to implement that one operation</subtitle>
+<subtitle id="0:50:27">  and and when I implemented</subtitle>
+<subtitle id="0:50:30"> this the the  Oh manage is implementation</subtitle>
+<subtitle id="0:50:33"> became I  think 30 percent faster which was pretty</subtitle>
+<subtitle id="0:50:36">  neat for very minimal effort</subtitle>
+<subtitle id="0:50:39"> anyway oh  yeah</subtitle>
+<subtitle id="0:50:42"> and the last thing I want to show  you here before I</subtitle>
+<subtitle id="0:50:45"> show the Dan</subtitle>
+<subtitle id="0:50:48"> stuff is  so if you</subtitle>
+<subtitle id="0:50:51"> if you end up taking the time  to take a look to</subtitle>
+<subtitle id="0:50:54"> look at this stuff  online I encourage you to look at this  project</subtitle>
+<subtitle id="0:50:57"> it's called meta to t oo which  is a pun</subtitle>
+<subtitle id="0:51:0"> on you know the meta to which  had</subtitle>
+<subtitle id="0:51:3"> the Roman numeral two that I told  you about before</subtitle>
+<subtitle id="0:51:6"> and what this is is a  language that's very</subtitle>
+<subtitle id="0:51:9"> close to a meta  implemented entirely</subtitle>
+<subtitle id="0:51:12"> in this little  project and so at first this</subtitle>
+<subtitle id="0:51:15"> this  javascript object that</subtitle>
+<subtitle id="0:51:18"> you see up here  is a is the</subtitle>
+<subtitle id="0:51:21"> library like object that</subtitle>
+<subtitle id="0:51:24">implements all of the semantics that you  need for doing the</subtitle>
+<subtitle id="0:51:27"> parsing and pattern  matching and then down here</subtitle>
+<subtitle id="0:51:30"> what I have  is the parser for this language</subtitle>
+<subtitle id="0:51:33"> written  in know meta and then I have a couple of</subtitle>
+<subtitle id="0:51:36">  examples you know with with</subtitle>
+<subtitle id="0:51:39"> arithmetic  expressions and so on but</subtitle>
+<subtitle id="0:51:42"> then of course  that is not sufficient to do  bootstrapping</subtitle>
+<subtitle id="0:51:45"> but what you really need  to do is once</subtitle>
+<subtitle id="0:51:48"> you have the the Oh Matt  alike language working</subtitle>
+<subtitle id="0:51:51"> you want to write  that you want to implement that guy in</subtitle>
+<subtitle id="0:51:54">  itself which is what I do down</subtitle>
+<subtitle id="0:51:57"> here  and you can see it's a little bit</subtitle>
+<subtitle id="0:52:0"> uglier  than no matter particularly because the  semantic</subtitle>
+<subtitle id="0:52:3"> actions have to be enclosed in  these funny</subtitle>
+<subtitle id="0:52:6"> characters and so on but I  did that so that I wouldn't</subtitle>
+<subtitle id="0:52:9"> have to  implement the JavaScript parser as part</subtitle>
+<subtitle id="0:52:12">of this thing right so I can just  blindly consume the JavaScript</subtitle>
+<subtitle id="0:52:15"> and  output it in the translated code</subtitle>
+<subtitle id="0:52:18"> so  anyway that's</subtitle>
+<subtitle id="0:52:21"> the implementation of that  and you can compile the compiler with</subtitle>
+<subtitle id="0:52:24">e original compiler that I wrote with  no meta and it works</subtitle>
+<subtitle id="0:52:27"> and then the thing  that really tests it later</subtitle>
+<subtitle id="0:52:30"> on is if you  take the the version</subtitle>
+<subtitle id="0:52:33"> of the compiler  that was generated from the code up</subtitle>
+<subtitle id="0:52:36"> here  by using the no matter you know compiler</subtitle>
+<subtitle id="0:52:39">  if you take that and and</subtitle>
+<subtitle id="0:52:42"> compile it with  itself and replace the thing you're</subtitle>
+<subtitle id="0:52:45">  using with that result and it still  works down</subtitle>
+<subtitle id="0:52:48"> here you know you're you're  good and that</subtitle>
+<subtitle id="0:52:51"> kind of works so it's a  it's a neat little example of  bootstrapping</subtitle>
+<subtitle id="0:52:54"> if you want to take a look</subtitle>
+<subtitle id="0:52:57">  at that later on so I think</subtitle>
+<subtitle id="0:53:0"> oh yeah one  less thing that I want to show here</subtitle>
+<subtitle id="0:53:3"> and  take a quick look at</subtitle>
+<subtitle id="0:53:6"> this JavaScript  doesn't have multi-line string</subtitle>
+<subtitle id="0:53:9"> literals  right but if you look at this</subtitle>
+<subtitle id="0:53:12"> I'm  actually using one right here it looks  very Python</subtitle>
+<subtitle id="0:53:15"> esque and the reason why I  can do</subtitle>
+<subtitle id="0:53:18"> that is because you know this  translate code thing my</subtitle>
+<subtitle id="0:53:21">doesn't have to be JavaScript right I  have that</subtitle>
+<subtitle id="0:53:24"> intermediate thing the  JavaScript parser and and</subtitle>
+<subtitle id="0:53:27"> translator  that I showed you before and I can  easily inherit</subtitle>
+<subtitle id="0:53:30"> from that and add new  kinds</subtitle>
+<subtitle id="0:53:33"> of things so that was very  straightforward and the the other neat  thing</subtitle>
+<subtitle id="0:53:36"> about having things having these  languages implemented</subtitle>
+<subtitle id="0:53:39"> and no matter is  that there's a thing called foreign rule</subtitle>
+<subtitle id="0:53:42">  invocation that allows a grammar to lend  its</subtitle>
+<subtitle id="0:53:45"> input stream to another grammar  temporarily and</subtitle>
+<subtitle id="0:53:48"> it's an it's an  alternative to inheritance</subtitle>
+<subtitle id="0:53:51"> for instance  that you may have noticed that the  language</subtitle>
+<subtitle id="0:53:54"> that I'm using in this  workspace is not just JavaScript and</subtitle>
+<subtitle id="0:53:57">it's not just no matter it's kind of a  mash-up of these two languages</subtitle>
+<subtitle id="0:54:0"> and if  you wanted to implement that with single</subtitle>
+<subtitle id="0:54:3">  inheritance you would have to inherit  from one</subtitle>
+<subtitle id="0:54:6"> of these translators and then  implement the functionality</subtitle>
+<subtitle id="0:54:9"> of the other  translator which would be very</subtitle>
+<subtitle id="0:54:12"> annoying  to have to do and</subtitle>
+<subtitle id="0:54:15"> multiple inheritance  is clearly a bad idea I'm not going</subtitle>
+<subtitle id="0:54:18"> to  go into that because of all the you</subtitle>
+<subtitle id="0:54:21"> know  complications and and so on and so</subtitle>
+<subtitle id="0:54:24"> with  foreign rule invocation I can just have  one grammar</subtitle>
+<subtitle id="0:54:27"> that doesn't inherit from  either if I don't want to and just</subtitle>
+<subtitle id="0:54:30"> says  try parsing my input as a no matter</subtitle>
+<subtitle id="0:54:33">grammar and if that doesn't work try  parsing my input as a JavaScript</subtitle>
+<subtitle id="0:54:36">  statement or expression or whatever  sorry</subtitle>
+<subtitle id="0:54:39"> punch line yes okay</subtitle>
+<subtitle id="0:54:42"> so what you're  looking</subtitle>
+<subtitle id="0:54:45"> at here is part</subtitle>
+<subtitle id="0:54:48"> of my translator  for the Niall language that Dan was  talking</subtitle>
+<subtitle id="0:54:51"> about so the stuff on top</subtitle>
+<subtitle id="0:54:54">implements is a is a grammar that on its  own implements</subtitle>
+<subtitle id="0:54:57"> the offside rule you know  indentation as block structure that</subtitle>
+<subtitle id="0:55:0">see in Python and Haskell and so on a  neat thing</subtitle>
+<subtitle id="0:55:3"> about that is that that's  modularized away from</subtitle>
+<subtitle id="0:55:6"> whatever language  that you're implementing so all this</subtitle>
+<subtitle id="0:55:9">  stuff like a keeping track of a</subtitle>
+<subtitle id="0:55:12"> stack of  indentation levels and so on that can be  done</subtitle>
+<subtitle id="0:55:15"> in that one grammar and my</subtitle>
+<subtitle id="0:55:18"> my Nile  parser which is down here</subtitle>
+<subtitle id="0:55:21"> also written  in no matter just inherits</subtitle>
+<subtitle id="0:55:24"> from that guy  and can just say you know</subtitle>
+<subtitle id="0:55:27"> I I want to I  want</subtitle>
+<subtitle id="0:55:30"> to indent I don't</subtitle>
+<subtitle id="0:55:33"> know that's  identifier anyway</subtitle>
+<subtitle id="0:55:36"> there's there's  there's a bunch of indentation</subtitle>
+<subtitle id="0:55:39"> code ah  here we go so I want to I</subtitle>
+<subtitle id="0:55:42"> want to tab  over here and then there are these</subtitle>
+<subtitle id="0:55:45"> funny  unicode characters that dan is very fond</subtitle>
+<subtitle id="0:55:48">  of and so on so</subtitle>
+<subtitle id="0:55:51"> this is the the parser  part of the implementation</subtitle>
+<subtitle id="0:55:54"> of Dan's  thing and there's also</subtitle>
+<subtitle id="0:55:57"> a type checker  and code generator that</subtitle>
+<subtitle id="0:56:0"> are written by  pattern matching on those</subtitle>
+<subtitle id="0:56:3">structures that I'm creating on the  right hand side and the</subtitle>
+<subtitle id="0:56:6"> so it's a it's a  fairly you</subtitle>
+<subtitle id="0:56:9"> know that one of the cool  things about Dan's language is</subtitle>
+<subtitle id="0:56:12"> that in  addition to you know types being used</subtitle>
+<subtitle id="0:56:15">  for making sure that you don't get  things</subtitle>
+<subtitle id="0:56:18"> wrong the the types matter a lot</subtitle>
+<subtitle id="0:56:21">for efficient code generation for Niall  and</subtitle>
+<subtitle id="0:56:24"> it turned out to be relatively  straightforward</subtitle>
+<subtitle id="0:56:27"> to keep track of types  in these grammars since</subtitle>
+<subtitle id="0:56:30"> you know the  grammars are kind of like class</subtitle>
+<subtitle id="0:56:33"> grammar  no matter is pretty much like a class</subtitle>
+<subtitle id="0:56:36">an object-oriented language you can have  state associated</subtitle>
+<subtitle id="0:56:39"> with running instances  of that grammar and then</subtitle>
+<subtitle id="0:56:42"> you can keep  the symbol table on there and and so on  and in</subtitle>
+<subtitle id="0:56:45"> do proper type checking so I</subtitle>
+<subtitle id="0:56:48">  think I'm gonna stop here sorry if I ran  a</subtitle>
+<subtitle id="0:56:51"> little long and SM is gonna</subtitle>
+<subtitle id="0:58:36">nd just to clarify pegs</subtitle>
+<subtitle id="0:58:39"> on their own  don't support left recursion but there's</subtitle>
+<subtitle id="0:58:42">a cool trick that you can do with the  memo table that's used by packrat</subtitle>
+<subtitle id="0:58:45">  parsers I wrote a paper about that you</subtitle>
+<subtitle id="0:58:48">  guys Rangers</subtitle>
+<subtitle id="0:58:57">you have all these</subtitle>
+<subtitle id="0:59:6">right so</subtitle>
+<subtitle id="0:59:9"> right now I don't have a great  answer to that I try</subtitle>
+<subtitle id="0:59:12"> it out and  hopefully it works but</subtitle>
+<subtitle id="0:59:15"> we're hoping that  at</subtitle>
+<subtitle id="0:59:18"> some point soon we're going to be  able to use the princess</subtitle>
+<subtitle id="0:59:21"> and I'll  programs that then has I kind</subtitle>
+<subtitle id="0:59:24"> of think  of them as the meaning of the thing</subtitle>
+<subtitle id="0:59:27">I care about and it would be really  great to have an automatic</subtitle>
+<subtitle id="0:59:30"> way to check  the meaning against</subtitle>
+<subtitle id="0:59:33"> it's true okay</subtitle>
+<subtitle id="0:59:36">  we can discuss</subtitle>
+<subtitle id="0:59:39"> it offline you don't need  this</subtitle>
+<subtitle id="1:0:54">there are</subtitle>
+<subtitle id="1:1:9">please feel</subtitle>
+<subtitle id="1:1:12"> free to leave us be all the  time be another ten minutes</subtitle>
+<subtitle id="1:1:15">  I'm Kazama I work at viewpoints</subtitle>
+<subtitle id="1:1:18"> as well  as um understood at UCLA actually</subtitle>
+<subtitle id="1:1:21"> called  my father but he said you</subtitle>
+<subtitle id="1:1:24"> should be out  party</subtitle>
+<subtitle id="1:1:27"> so what part</subtitle>
+<subtitle id="1:1:30"> of all the interest  is I'm sure you have seen an imperative</subtitle>
+<subtitle id="1:1:33">  as well as declarative methodologies to  do</subtitle>
+<subtitle id="1:1:36"> programming imperative is how  implementations</subtitle>
+<subtitle id="1:1:39"> are darling  declarative is we've seen</subtitle>
+<subtitle id="1:1:42"> Prolog  language you know its meanings they're  compact</subtitle>
+<subtitle id="1:1:45">  they're very understandable</subtitle>
+<subtitle id="1:1:48"> but we need  search in order to</subtitle>
+<subtitle id="1:1:51"> to execute them so  that the often not practical part</subtitle>
+<subtitle id="1:1:54">what your interests are here to save  codes as</subtitle>
+<subtitle id="1:1:57"> well as to add  understandability to problems</subtitle>
+<subtitle id="1:2:0"> is is  there a way to kind of combine</subtitle>
+<subtitle id="1:2:3"> both at  the same time which is not very common  today this</subtitle>
+<subtitle id="1:2:6"> is a famous quote that I made  recently that</subtitle>
+<subtitle id="1:2:9"> the natural combination of  the claritin</subtitle>
+<subtitle id="1:2:12"> predators is missing a  couple</subtitle>
+<subtitle id="1:2:15"> of methodologies that we kind of  studied in</subtitle>
+<subtitle id="1:2:18"> this direction is one is I'm  just I'm just gonna quickly</subtitle>
+<subtitle id="1:2:21"> go over it  but basically</subtitle>
+<subtitle id="1:2:24"> if you add a</subtitle>
+<subtitle id="1:2:27"> layer of  logic on top of your</subtitle>
+<subtitle id="1:2:30"> your your languages  to support search</subtitle>
+<subtitle id="1:2:33"> basically your  heuristic search you can do</subtitle>
+<subtitle id="1:2:36">programming with a little bit of  overhead if</subtitle>
+<subtitle id="1:2:39"> you're always willing to add  optimizations so</subtitle>
+<subtitle id="1:2:42"> in the in the presence  of multiple methods if</subtitle>
+<subtitle id="1:2:45">there's an optimization that always  tells</subtitle>
+<subtitle id="1:2:48"> you based on the state which  method is the is</subtitle>
+<subtitle id="1:2:51"> the good method to take  so you always do this check to to</subtitle>
+<subtitle id="1:2:54">ut the different alternatives then you  have this lovely</subtitle>
+<subtitle id="1:2:57"> the overhead of  checking to do your normal</subtitle>
+<subtitle id="1:3:0"> imperative  but when you do want when you do have</subtitle>
+<subtitle id="1:3:3">  the you know leverage</subtitle>
+<subtitle id="1:3:6"> to do kind of  search you can you</subtitle>
+<subtitle id="1:3:9"> have the option to  say well explore possibilities</subtitle>
+<subtitle id="1:3:12"> and find  the best best scenario to</subtitle>
+<subtitle id="1:3:15"> do so this is  what this this prodigies are</subtitle>
+<subtitle id="1:3:18"> all about  you know allows you to kind of separate  the optimizations</subtitle>
+<subtitle id="1:3:21"> and here is the  from from the actual implementations</subtitle>
+<subtitle id="1:3:24"> the  actions that you see here to satisfy the</subtitle>
+<subtitle id="1:3:27">  goals so implements that the budget  programs</subtitle>
+<subtitle id="1:3:30"> really small they're really  cute and slow</subtitle>
+<subtitle id="1:3:33"> but there have this nice  way that</subtitle>
+<subtitle id="1:3:36"> you can add for example this  chess program</subtitle>
+<subtitle id="1:3:39"> that was about three  hundred lines of code that even</subtitle>
+<subtitle id="1:3:42"> included  some text ASCII</subtitle>
+<subtitle id="1:3:45"> art graphics where</subtitle>
+<subtitle id="1:3:48"> you  could just actually add any arbitrary  number of heuristics</subtitle>
+<subtitle id="1:3:51"> that say based on  the the states that you</subtitle>
+<subtitle id="1:3:54"> explore  basically heuristics tell you which one</subtitle>
+<subtitle id="1:3:57">is the better one to do and then these  heuristics</subtitle>
+<subtitle id="1:4:0"> tell you that you know it's  better to take a move</subtitle>
+<subtitle id="1:4:3"> when you actually  capture the opponent's piece then</subtitle>
+<subtitle id="1:4:6"> try  not to get captures we're adding some  numeric</subtitle>
+<subtitle id="1:4:9"> values so you can basically  reorder</subtitle>
+<subtitle id="1:4:12"> the you know alternatives</subtitle>
+<subtitle id="1:4:15"> but  another more serious one</subtitle>
+<subtitle id="1:4:18"> was you know in  compilers need to do register</subtitle>
+<subtitle id="1:4:21">  allocations which is you have registers</subtitle>
+<subtitle id="1:4:24">and you have variables in the program  these variables the</subtitle>
+<subtitle id="1:4:27">decide where they gonna be in on the  registers and</subtitle>
+<subtitle id="1:4:30"> this has happens to be an  NP complete problem this hard</subtitle>
+<subtitle id="1:4:33"> problem if  you want to do it optimally and then  it's this</subtitle>
+<subtitle id="1:4:36"> is nice way because you know  you just allow</subtitle>
+<subtitle id="1:4:39"> a high-level goal that  that kind of this this</subtitle>
+<subtitle id="1:4:42"> is using  methodology in Smalltalk program that</subtitle>
+<subtitle id="1:4:45">you just expressed the goal that all  variables want</subtitle>
+<subtitle id="1:4:48"> to be you know assigned  and you then</subtitle>
+<subtitle id="1:4:51"> you have you tell it what  what</subtitle>
+<subtitle id="1:4:54"> actions are taken when you're doing  this this task</subtitle>
+<subtitle id="1:4:57"> which is usually  assigning particular</subtitle>
+<subtitle id="1:5:0"> register with the  variable or deciding to spill or split</subtitle>
+<subtitle id="1:5:3">  and then you define the optimizations on  top of</subtitle>
+<subtitle id="1:5:6"> this that says based on whatever  state you are if</subtitle>
+<subtitle id="1:5:9"> you have room for the  next variable then take that</subtitle>
+<subtitle id="1:5:12"> particular  method if you have otherwise take the</subtitle>
+<subtitle id="1:5:15">spill method you know it just in has a  layer</subtitle>
+<subtitle id="1:5:18"> on top of your normal logic you  can</subtitle>
+<subtitle id="1:5:21"> express that in more</subtitle>
+<subtitle id="1:5:24"> declarative way  but the problem with</subtitle>
+<subtitle id="1:5:27"> here is success as  you know is that if you're implementing</subtitle>
+<subtitle id="1:5:30">your own search it's often becomes  interactable  so</subtitle>
+<subtitle id="1:5:33"> recent or studies  then I'm going to show</subtitle>
+<subtitle id="1:5:36"> now is more based  on boolean</subtitle>
+<subtitle id="1:5:39"> satisfiability sad solvers  constraint</subtitle>
+<subtitle id="1:5:42"> solving technologies which  are recently</subtitle>
+<subtitle id="1:5:45"> been shown that it's much  you</subtitle>
+<subtitle id="1:5:48"> know it's a scale much better so our  Britta</subtitle>
+<subtitle id="1:5:51"> more recent stuff is not based on  the search that we come</subtitle>
+<subtitle id="1:5:54"> up with  ourselves but based kind of plugging</subtitle>
+<subtitle id="1:5:57">whatever a tool that we have two  external tools</subtitle>
+<subtitle id="1:6:0"> that are really good at  solving problems using sad</subtitle>
+<subtitle id="1:6:3"> solving  technologies as we will see that</subtitle>
+<subtitle id="1:6:6">have their own problems that they're  kind of not very and</subtitle>
+<subtitle id="1:6:9"> they're not nice to  adding user</subtitle>
+<subtitle id="1:6:12"> specific heuristics so</subtitle>
+<subtitle id="1:6:15">  eventually we want some combination of  the</subtitle>
+<subtitle id="1:6:18"> two two ways the heuristic searching  or sad</subtitle>
+<subtitle id="1:6:21"> solving technologies to rethink  that</subtitle>
+<subtitle id="1:6:24"> you know might answer our problem  so this</subtitle>
+<subtitle id="1:6:27"> this project is about adding  syntactic sugars</subtitle>
+<subtitle id="1:6:30"> to programming  languages in this case I'm showing you</subtitle>
+<subtitle id="1:6:33">examples from an extension of Java  language where</subtitle>
+<subtitle id="1:6:36"> we allowing first-order  logic expressions</subtitle>
+<subtitle id="1:6:39"> like this or you know  set comprehension stuff</subtitle>
+<subtitle id="1:6:42"> like this this  is from a lloyd</subtitle>
+<subtitle id="1:6:45"> language actually it's a  model object modeling language</subtitle>
+<subtitle id="1:6:48"> so we we  allow these kind</subtitle>
+<subtitle id="1:6:51"> of expressions in the  language but they serve two purposes one</subtitle>
+<subtitle id="1:6:54">  is that we can easily do sugar these two  low-level</subtitle>
+<subtitle id="1:6:57"> syntax of the program so these  are actually</subtitle>
+<subtitle id="1:7:0"> runnable so if I but this  is actually</subtitle>
+<subtitle id="1:7:3"> a part of the code of the  binary tree and</subtitle>
+<subtitle id="1:7:6"> if I actually  instantiate an object and I run it</subtitle>
+<subtitle id="1:7:9"> you  know because it's gonna be compiled to a  low-level</subtitle>
+<subtitle id="1:7:12"> code is going to be runnable  even though it's compact but</subtitle>
+<subtitle id="1:7:15"> that's not  the only thing that we're interested to  save lines</subtitle>
+<subtitle id="1:7:18"> of code we're also interested  in having</subtitle>
+<subtitle id="1:7:21"> a runnable executed runnable  meanings</subtitle>
+<subtitle id="1:7:24"> meanings that are actually  executable you see when</subtitle>
+<subtitle id="1:7:27"> we say meanings  we mean high-level expressions</subtitle>
+<subtitle id="1:7:30"> like this  that says I want</subtitle>
+<subtitle id="1:7:33"> a graph that is a  cyclic then this is the meaning</subtitle>
+<subtitle id="1:7:36">cyclic that there's no note that that  kind of points</subtitle>
+<subtitle id="1:7:39"> back to itself right it's  nice to be able to without</subtitle>
+<subtitle id="1:7:42">implementation I should be able to  execute this  meaning</subtitle>
+<subtitle id="1:7:45"> that not just running in the  program that kind</subtitle>
+<subtitle id="1:7:48"> of using some  constraint solving technology to  actually</subtitle>
+<subtitle id="1:7:51"> find a satisfying state for</subtitle>
+<subtitle id="1:7:54">  that particular constraint so so</subtitle>
+<subtitle id="1:7:57"> that's  what I'm saying executable in terms of  we</subtitle>
+<subtitle id="1:8:0"> can use some external tool to get</subtitle>
+<subtitle id="1:8:3">what state that we're happy without  actually any implementations</subtitle>
+<subtitle id="1:8:6"> now we're  going to use that for two</subtitle>
+<subtitle id="1:8:9"> things one is  the software reliability I'm showing you</subtitle>
+<subtitle id="1:8:12">  an implementation of the bubble sort for</subtitle>
+<subtitle id="1:8:15">in this this extension that is pretty  routine</subtitle>
+<subtitle id="1:8:18"> it's a bubble sort routine but</subtitle>
+<subtitle id="1:8:21">we see that you know this is in the in  light of</subtitle>
+<subtitle id="1:8:24"> you know program annotations  you've seen in a Java</subtitle>
+<subtitle id="1:8:27"> modeling language  and others where you just</subtitle>
+<subtitle id="1:8:30"> annotate the  program with meanings basically</subtitle>
+<subtitle id="1:8:33"> which  says this particular method is  accomplishing</subtitle>
+<subtitle id="1:8:36"> this this expression this  is followed</subtitle>
+<subtitle id="1:8:39"> by that insurance clause  that says the job of</subtitle>
+<subtitle id="1:8:42"> the sort method is  that it's going to find some value</subtitle>
+<subtitle id="1:8:45">  that's a permutation of the the old alts</subtitle>
+<subtitle id="1:8:48">  all this and it's gonna be a sorted</subtitle>
+<subtitle id="1:8:51">is something that we can automatically  insert instrument</subtitle>
+<subtitle id="1:8:54"> in the in the compiled  version so that if when method of</subtitle>
+<subtitle id="1:8:57">  methods are done these constraints</subtitle>
+<subtitle id="1:9:0">these expression is going to be  evaluated</subtitle>
+<subtitle id="1:9:3"> and if they happen to be false  that means the</subtitle>
+<subtitle id="1:9:6"> method was faulty method  was buggy or if</subtitle>
+<subtitle id="1:9:9"> they if they even  happened to have some kind</subtitle>
+<subtitle id="1:9:12"> of runtime  failure like a division by</subtitle>
+<subtitle id="1:9:15"> zero that  it's not easily found we</subtitle>
+<subtitle id="1:9:18"> can kind of  catch that exception and use</subtitle>
+<subtitle id="1:9:21"> the exec  use these efficacious</subtitle>
+<subtitle id="1:9:24"> as kind of a  fallback as an</subtitle>
+<subtitle id="1:9:27"> alternative that the  method didn't work but</subtitle>
+<subtitle id="1:9:30"> we can have an  alternative to to try</subtitle>
+<subtitle id="1:9:33"> what accomplish  what we want and in this case</subtitle>
+<subtitle id="1:9:36"> we can use  we kind</subtitle>
+<subtitle id="1:9:39"> of translate this expression  into the synthetic</subtitle>
+<subtitle id="1:9:42"> the logic syntax  where we can can call an external tool</subtitle>
+<subtitle id="1:9:45">  to to find basically sort this list</subtitle>
+<subtitle id="1:9:48">so it's a</subtitle>
+<subtitle id="1:9:51"> live but bigger example is  this an implementation</subtitle>
+<subtitle id="1:9:54"> of red-black tree  that also have annotations</subtitle>
+<subtitle id="1:9:57"> for the  insert and delete methods basically</subtitle>
+<subtitle id="1:10:0">  saying on an insert insert you just</subtitle>
+<subtitle id="1:10:3"> have  one one you note added to the set of the</subtitle>
+<subtitle id="1:10:6">  notes and I delete you have one less</subtitle>
+<subtitle id="1:10:9"> and  basically assuming</subtitle>
+<subtitle id="1:10:12"> they have some some  implementation that's not reliable</subtitle>
+<subtitle id="1:10:15"> you  can just you know use this the</subtitle>
+<subtitle id="1:10:18">  annotations to accomplish what what they  do actually</subtitle>
+<subtitle id="1:10:21"> you can think of this</subtitle>
+<subtitle id="1:10:24"> so I  found the implementation typically</subtitle>
+<subtitle id="1:10:27"> about  five six hundred lines of code or three  hundred</subtitle>
+<subtitle id="1:10:30"> lines of code of Java because of  a lot of corner</subtitle>
+<subtitle id="1:10:33"> cases that these balance  trees need to satisfy</subtitle>
+<subtitle id="1:10:36"> this you can think  of it as a kind of a</subtitle>
+<subtitle id="1:10:39"> minimalistic  runnable implementation as</subtitle>
+<subtitle id="1:10:42"> you will it's  like an interface for for</subtitle>
+<subtitle id="1:10:45"> the whoever  wants to implement it but the neat thing  that</subtitle>
+<subtitle id="1:10:48"> this has that the interfaces don't  have its runnable</subtitle>
+<subtitle id="1:10:51"> so you can have  actually write what these two methods</subtitle>
+<subtitle id="1:10:54">  are gonna be in the future but because</subtitle>
+<subtitle id="1:10:57">you have annotated them actually you can  we can test them</subtitle>
+<subtitle id="1:11:0"> and run them because  yeah you know we</subtitle>
+<subtitle id="1:11:3"> have that underlying  reasoning system so</subtitle>
+<subtitle id="1:11:6"> that you actually  without the implementation can test your</subtitle>
+<subtitle id="1:11:9">  program interface to</subtitle>
+<subtitle id="1:11:12"> to move around  another</subtitle>
+<subtitle id="1:11:15"> so this is the last thing I'm  showing is that</subtitle>
+<subtitle id="1:11:18"> you can always  intentionally use</subtitle>
+<subtitle id="1:11:21"> this fallback system  the use of</subtitle>
+<subtitle id="1:11:24"> fallback when you want to do  something bit clearer</subtitle>
+<subtitle id="1:11:27"> deeply you don't  you don't even want to implement</subtitle>
+<subtitle id="1:11:30">something but you know you can use the  constraint solving technology</subtitle>
+<subtitle id="1:11:33"> that kind  of embedded in your in your language</subtitle>
+<subtitle id="1:11:36"> to  accomplish something that's kind of</subtitle>
+<subtitle id="1:11:39">cumbersome so in this case for example  this is a it's</subtitle>
+<subtitle id="1:11:42"> a a GUI</subtitle>
+<subtitle id="1:11:45"> example where  this is very simple a user just puts</subtitle>
+<subtitle id="1:11:48">dots on the screen you see these four  dots are</subtitle>
+<subtitle id="1:11:51"> putting in screen without a  problem so the the the</subtitle>
+<subtitle id="1:11:54"> job of this  particular method the ad body is</subtitle>
+<subtitle id="1:11:57"> very  trivial it's just you know draws the dot  and this</subtitle>
+<subtitle id="1:12:0"> box shows that  there's</subtitle>
+<subtitle id="1:12:3"> this restriction on this this</subtitle>
+<subtitle id="1:12:6">  application that says a user should not</subtitle>
+<subtitle id="1:12:9">put two dots too close to each other  there's a minimum distance that</subtitle>
+<subtitle id="1:12:12"> they  might have so you imagine the</subtitle>
+<subtitle id="1:12:15"> the normal  you know invocation</subtitle>
+<subtitle id="1:12:18"> of this method is  very trivial it just draws it as as</subtitle>
+<subtitle id="1:12:21"> far  as those violations are not you know  those</subtitle>
+<subtitle id="1:12:24"> specifications are not violated  it's okay</subtitle>
+<subtitle id="1:12:27">  it just but under a corner case is</subtitle>
+<subtitle id="1:12:30"> when  actually somebody put a red dot here and  that</subtitle>
+<subtitle id="1:12:33"> kind of you know violated that</subtitle>
+<subtitle id="1:12:36">property you don't want you don't want  to implement that that's</subtitle>
+<subtitle id="1:12:39">thing to do potentially a lot of dots  needs to be moved</subtitle>
+<subtitle id="1:12:42"> around right so in  that case you</subtitle>
+<subtitle id="1:12:45"> just don't handle it in  your in your program</subtitle>
+<subtitle id="1:12:48"> and we're gonna  kind of you</subtitle>
+<subtitle id="1:12:51"> can't automatically fall  back to constraint solving in a sad  solving</subtitle>
+<subtitle id="1:12:54"> - to do what - basically shift  some dots</subtitle>
+<subtitle id="1:12:57"> around - to satisfy those  properties and that's what's happening</subtitle>
+<subtitle id="1:13:0">  here and you</subtitle>
+<subtitle id="1:13:3"> see that that box here is  saying there's a restriction</subtitle>
+<subtitle id="1:13:6"> of how much  those dots are you know are allowed to  shift</subtitle>
+<subtitle id="1:13:9"> by by the by the method so</subtitle>
+<subtitle id="1:13:12"> you see  that you know these two are shifted</subtitle>
+<subtitle id="1:13:15">little bit you know to make sure the  separation is happening so basically</subtitle>
+<subtitle id="1:13:18"> I'm  showing you the code that that does</subtitle>
+<subtitle id="1:13:21"> this  this is the</subtitle>
+<subtitle id="1:13:24"> this is the entire code that  when you're when you're adding a</subtitle>
+<subtitle id="1:13:27"> dot you  see that it has this this</subtitle>
+<subtitle id="1:13:30"> check that it  needs to do that</subtitle>
+<subtitle id="1:13:33"> I'm written here also  in a in</subtitle>
+<subtitle id="1:13:36"> a high level syntax of alloy the  first order logic that</subtitle>
+<subtitle id="1:13:39"> they have the two  things that says no to dust</subtitle>
+<subtitle id="1:13:42">oo you know too close to each other and  when you</subtitle>
+<subtitle id="1:13:45"> do move them you know you're  not allowed to remove them by more</subtitle>
+<subtitle id="1:13:48"> than  an a value and you see that there's no  implementations</subtitle>
+<subtitle id="1:13:51"> here so that when I put  that red dot you</subtitle>
+<subtitle id="1:13:54"> know it kind of  automatically figured out</subtitle>
+<subtitle id="1:13:57">  those are the things that just</subtitle>
+<subtitle id="1:14:0"> wanted to  show you so if you have any questions or</subtitle>
+<subtitle id="1:14:3">  for previous</subtitle>
+<subtitle id="1:16:6">before</subtitle>
+<subtitle id="1:16:21">basically</subtitle>
+<subtitle id="1:16:36">but also II think that we don't have a  cat</subtitle>
+<subtitle id="1:16:39">  the other</subtitle>
+<subtitle id="1:16:51">find</subtitle>
+<subtitle id="1:17:42">those</subtitle>