How Complex is "Personal Computing"? (2009)

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