How Complex is "Personal Computing"? (2009)

From Viewpoints Intelligent Archive
Revision as of 22:03, 6 December 2017 by Ohshima (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
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