[MUSIC PLAYING]
PROFESSOR: I'd like to
welcome you to this
course on computer science.
Actually, that's a terrible
way to start.
Computer science is a terrible
name for this business.
First of all, it's
not a science.
It might be engineering or it
might be art, but we'll
actually see that computer
so-called science actually has
a lot in common with magic,
and we'll see
that in this course.
So it's not a science.
It's also not really very
much about computers.
And it's not about computers in
the same sense that physics
is not really about particle
accelerators, and biology is
not really about microscopes
and petri dishes.
And it's not about computers
in the same sense that
geometry is not really about
using surveying instruments.
In fact, there's a lot of
commonality between computer
science and geometry.
Geometry, first of all,
is another subject
with a lousy name.
The name comes from Gaia,
meaning the Earth, and metron,
meaning to measure.
Geometry originally
meant measuring
the Earth or surveying.
And the reason for that was
that, thousands of years ago,
the Egyptian priesthood
developed the rudiments of
geometry in order to figure
out how to restore the
boundaries of fields that were
destroyed in the annual
flooding of the Nile.
And to the Egyptians who did
that, geometry really was the
use of surveying instruments.
Now, the reason that we think
computer science is about
computers is pretty much the
same reason that the Egyptians
thought geometry was about
surveying instruments.
And that is, when some field
is just getting started and
you don't really understand it
very well, it's very easy to
confuse the essence of what
you're doing with the tools
that you use.
And indeed, on some absolute
scale of things, we probably
know less about the essence of
computer science than the
ancient Egyptians really
knew about geometry.
Well, what do I mean by the
essence of computer science?
What do I mean by the
essence of geometry?
See, it's certainly true that
these Egyptians went off and
used surveying instruments, but
when we look back on them
after a couple of thousand
years, we say, gee, what they
were doing, the important stuff
they were doing, was to
begin to formalize notions about
space and time, to start
a way of talking about
mathematical truths formally.
That led to the axiomatic
method.
That led to sort of all of
modern mathematics, figuring
out a way to talk precisely
about so-called declarative
knowledge, what is true.
Well, similarly, I think in the
future people will look
back and say, yes, those
primitives in the 20th century
were fiddling around with
these gadgets called
computers, but really what they
were doing is starting to
learn how to formalize
intuitions about process, how
to do things, starting to
develop a way to talk
precisely about how-to
knowledge, as opposed to
geometry that talks about
what is true.
Let me give you an
example of that.
Let's take a look.
Here is a piece of mathematics
that says what
a square root is.
The square root of X is the
number Y, such that Y squared
is equal to X and Y
is greater than 0.
Now, that's a fine piece of
mathematics, but just telling
you what a square root is
doesn't really say anything
about how you might go
out and find one.
So let's contrast that with a
piece of imperative knowledge,
how you might go out and
find a square root.
This, in fact, also comes
from Egypt, not
ancient, ancient Egypt.
This is an algorithm due to
Heron of Alexandria, called
how to find a square root
by successive averaging.
And what it says is that, in
order to find a square root,
you make a guess, you
improve that guess--
and the way you improve the
guess is to average the guess
and X over the guess, and we'll
talk a little bit later
about why that's a reasonable
thing--
and you keep improving the guess
until it's good enough.
That's a method.
That's how to do something
as opposed to declarative
knowledge that says what
you're looking for.
That's a process.
Well, what's a process
in general?
It's kind of hard to say.
You can think of it as like a
magical spirit that sort of
lives in the computer
and does something.
And the thing that directs a
process is a pattern of rules
called a procedure.
So procedures are the spells,
if you like, that control
these magical spirits that
are the processes.
I guess you know everyone needs
a magical language, and
sorcerers, real sorcerers, use
ancient Arcadian or Sumerian
or Babylonian or whatever.
We're going to conjure our
spirits in a magical language
called Lisp, which is a language
designed for talking
about, for casting the spells
that are procedures to direct
the processes.
Now, it's very easy
to learn Lisp.
In fact, in a few minutes,
I'm going to teach you,
essentially, all of Lisp.
I'm going to teach you,
essentially, all of the rules.
And you shouldn't find that
particularly surprising.
That's sort of like saying it's
very easy to learn the
rules of chess.
And indeed, in a few minutes,
you can tell somebody the
rules of chess.
But of course, that's very
different from saying you
understand the implications of
those rules and how to use
those rules to become a
masterful chess player.
Well, Lisp is the same way.
We're going to state the rules
in a few minutes, and it'll be
very easy to see.
But what's really hard is going
to be the implications
of those rules, how you exploit
those rules to be a
master programmer.
And the implications of those
rules are going to take us
the, well, the whole rest of
the subject and, of course,
way beyond.
OK, so in computer science,
we're in the business of
formalizing this sort of how-to
imperative knowledge,
how to do stuff.
And the real issues of computer
science are, of
course, not telling people
how to do square roots.
Because if that was
all it was, there
wouldn't be no big deal.
The real problems come when we
try to build very, very large
systems, computer programs that
are thousands of pages
long, so long that nobody can
really hold them in their
heads all at once.
And the only reason that that's
possible is because
there are techniques for
controlling the complexity of
these large systems. And these
techniques that are
controlling complexity
are what this
course is really about.
And in some sense, that's
really what
computer science is about.
Now, that may seem like a very
strange thing to say.
Because after all, a lot of
people besides computer
scientists deal with controlling
complexity.
A large airliner is an extremely
complex system, and
the aeronautical engineers who
design that are dealing with
immense complexity.
But there's a difference
between that kind of
complexity and what we deal
with in computer science.
And that is that computer
science, in some
sense, isn't real.
You see, when an engineer is
designing a physical system,
that's made out of real parts.
The engineers who worry about
that have to address problems
of tolerance and approximation
and noise in the system.
So for example, as an electrical
engineer, I can go
off and easily build a one-stage
amplifier or a
two-stage amplifier, and I can
imagine cascading a lot of
them to build a million-stage
amplifier.
But it's ridiculous to build
such a thing, because long
before the millionth stage,
the thermal noise in those
components way at the beginning
is going to get
amplified and make the whole
thing meaningless.
Computer science deals with
idealized components.
We know as much as we want about
these little program and
data pieces that we're fitting
things together.
We don't have to worry
about tolerance.
And that means that, in building
a large program,
there's not all that much
difference between what I can
build and what I can imagine,
because the parts are these
abstract entities that I
know as much as I want.
I know about them as precisely
as I'd like.
So as opposed to other kinds
of engineering, where the
constraints on what you can
build are the constraints of
physical systems, the
constraints of physics and
noise and approximation, the
constraints imposed in
building large software systems
are the limitations of
our own minds.
So in that sense, computer
science is like an abstract
form of engineering.
It's the kind of engineering
where you ignore the
constraints that are
imposed by reality.
Well, what are some of
these techniques?
They're not special to
computer science.
First technique, which is used
in all of engineering, is a
kind of abstraction called
black-box abstraction.
Take something and build
a box about it.
Let's see, for example, if we
looked at that square root
method, I might want to take
that and build a box.
That sort of says, to find the
square root of X. And that
might be a whole complicated
set of rules.
And that might end up being a
kind of thing where I can put
in, say, 36 and say, what's
the square root of 36?
And out comes 6.
And the important thing is that
I'd like to design that
so that if George comes along
and would like to compute,
say, the square root of A plus
the square root of B, he can
take this thing and use it as
a module without having to
look inside and build something
that looks like
this, like an A and a B and a
square root box and another
square root box and then
something that adds that would
put out the answer.
And you can see, just from the
fact that I want to do that,
is from George's point of view,
the internals of what's
in here should not
be important.
So for instance, it shouldn't
matter that, when I wrote
this, I said I want to find the
square root of X. I could
have said the square root of Y,
or the square root of A, or
anything at all.
That's the fundamental notion of
putting something in a box
using black-box abstraction
to suppress detail.
And the reason for that is you
want to go off and build
bigger boxes.
Now, there's another reason
for doing black-box
abstraction other than you want
to suppress detail for
building bigger boxes.
Sometimes you want to say that
your way of doing something,
your how-to method, is an
instance of a more general
thing, and you'd like your
language to be able to express
that generality.
Let me show you another example
sticking with square roots.
Let's go back and take another
look at that slide with the
square root algorithm on it.
Remember what that says.
That says, in order to do
something, I make a guess, and
I improve that guess,
and I sort of keep
improving that guess.
So there's the general strategy
of, I'm looking for
something, and the way
I find it is that I
keep improving it.
Now, that's a particular case
of another kind of strategy
for finding a fixed point
of something.
So you have a fixed point
of a function.
A fixed point of a function
is something, is a value.
A fixed point of a function F is
a value Y, such that F of Y
equals Y. And the way I might do
that is start with a guess.
And then if I want something
that doesn't change when I
keep applying F, is I'll keep
applying F over and over until
that result doesn't
change very much.
So there's a general strategy.
And then, for example, to
compute the square root of X,
I can try and find a fixed point
of the function which
takes Y to the average of X/Y.
And the idea that is that if I
really had Y equal to the square
root of X, then Y and
X/Y would be the same value.
They'd both be the square root
of X, because X over the
square root of X is the
square root of X.
And so the average if Y were
equal to the square of X, then
the average wouldn't change.
So the square root of X
is a fixed point of
that particular function.
Now, what I'd like to have,
I'd like to express the
general strategy for finding
fixed points.
So what I might imagine doing,
is to find, is to be able to
use my language to define a box
that says "fixed point,"
just like I could make a box
that says "square root." And
I'd like to be able to express
this in my language.
So I'd like to express not only
the imperative how-to
knowledge of a particular thing
like square root, but
I'd like to be able to express
the imperative knowledge of
how to do a general thing like
how to find fixed point.
And in fact, let's go back and
look at that slide again.
See, not only is this a piece
of imperative knowledge, how
to find a fixed point, but
over here on the bottom,
there's another piece of
imperative knowledge which
says, one way to compute square
root is to apply this
general fixed point method.
So I'd like to also
be able to express
that imperative knowledge.
What would that look like?
That would say, this fixed point
box is such that if I
input to it the function that
takes Y to the average of Y
and X/Y, then what should come
out of that fixed point box is
a method for finding
square roots.
So in these boxes we're
building, we're not only
building boxes that you input
numbers and output numbers,
we're going to be building in
boxes that, in effect, compute
methods like finding
square root.
And my take is their inputs
functions, like Y goes to the
average of Y and X/Y. The reason
we want to do that, the
reason this is a procedure, will
end up being a procedure,
as we'll see, whose value is
another procedure, the reason
we want to do that is because
procedures are going to be our
ways of talking about imperative
knowledge.
And the way to make that very
powerful is to be able to talk
about other kinds
of knowledge.
So here is a procedure that, in
effect, talks about another
procedure, a general strategy
that itself talks about
general strategies.
Well, our first topic in this
course-- there'll be three
major topics-- will be black-box
abstraction.
Let's look at that in a little
bit more detail.
What we're going to do is we
will start out talking about
how Lisp is built up out
of primitive objects.
What does the language
supply with us?
And we'll see that there are
primitive procedures and
primitive data.
Then we're going to see, how do
you take those primitives
and combine them to make more
complicated things, means of
combination?
And what we'll see is that
there are ways of putting
things together, putting
primitive procedures together
to make more complicated
procedures.
And we'll see how to put
primitive data together to
make compound data.
Then we'll say, well, having
made those compounds things,
how do you abstract them?
How do you put those black boxes
around them so you can
use them as components in
more complex things?
And we'll see that's done by
defining procedures and a
technique for dealing with
compound data called data
abstraction.
And then, what's maybe the most
important thing, is going
from just the rules to how
does an expert work?
How do you express common
patterns of doing things, like
saying, well, there's a general
method of fixed point
and square root is a particular
case of that?
And we're going to use--
I've already hinted at it--
something called higher-order
procedures, namely procedures
whose inputs and outputs are
themselves procedures.
And then we'll also see
something very interesting.
We'll see, as we go further and
further on and become more
abstract, there'll be very--
well, the line between what we
consider to be data and what
we consider to be procedures
is going to blur at an
incredible rate.
Well, that's our first
subject, black-box
abstraction.
Let's look at the
second topic.
I can introduce it like this.
See, suppose I want to
express the idea--
remember, we're talking
about ideas--
suppose I want to express the
idea that I can take something
and multiply it by the sum
of two other things.
So for example, I might say, if
I had 1 and 3 and multiply
that by 2, I get 8.
But I'm talking about the
general idea of what's called
linear combination, that you
can add two things and
multiply them by
something else.
It's very easy when I think
about it for numbers, but
suppose I also want to use that
same idea to think about,
I could add two vectors, a1 and
a2, and then scale them by
some factor x and get
another vector.
Or I might say, I want to think
about a1 and a2 as being
polynomials, and I might want
to add those two polynomials
and then multiply them by 2 to
get a more complicated one.
Or a1 and a2 might be electrical
signals, and I
might want to think about
summing those two electrical
signals and then putting the
whole thing through an
amplifier, multiplying it by
some factor of 2 or something.
The idea is I want to
think about the
general notion of that.
Now, if our language is going
to be good language for
expressing those kind of general
ideas, if I really,
really can do that, I'd like to
be able to say I'm going to
multiply by x the sum of a1 and
a2, and I'd like that to
express the general idea of all
different kinds of things
that a1 and a2 could be.
Now, if you think about that,
there's a problem, because
after all, the actual primitive
operations that go
on in the machine are obviously
going to be
different if I'm adding two
numbers than if I'm adding two
polynomials, or if I'm adding
the representation of two
electrical signals
or wave forms.
Somewhere, there has to be the
knowledge of the kinds of
various things that you
can add and the
ways of adding them.
Now, to construct such a system,
the question is, where
do I put that knowledge?
How do I think about
the different kinds
of choices I have?
And if tomorrow George comes up
with a new kind of object
that might be added and
multiplied, how do I add
George's new object to the
system without screwing up
everything that was
already there?
Well, that's going to be the
second big topic, the way of
controlling that kind
of complexity.
And the way you do that is by
establishing conventional
interfaces, agreed upon ways of
plugging things together.
Just like in electrical
engineering, people have
standard impedances for
connectors, and then you know
if you build something with
one of those standard
impedances, you can plug it
together with something else.
So that's going to be our
second large topic,
conventional interfaces.
What we're going to see is,
first, we're going to talk
about the problem of generic
operations, which is the one I
alluded to, things like "plus"
that have to work with all
different kinds of data.
So we talk about generic
operations.
Then we're going to talk about
really large-scale structures.
How do you put together very
large programs that model the
kinds of complex systems
in the real world that
you'd like to model?
And what we're going to see
is that there are two very
important metaphors for putting
together such systems.
One is called object-oriented
programming, where you sort of
think of your system as a kind
of society full of little
things that interact by sending
information between them.
And then the second one is
operations on aggregates,
called streams, where you think
of a large system put
together kind of like a signal
processing engineer puts
together a large electrical
system.
That's going to be
our second topic.
Now, the third thing we're going
to come to, the third
basic technique for controlling
complexity, is
making new languages.
Because sometimes, when you're
sort of overwhelmed by the
complexity of a design, the
way that you control that
complexity is to pick a
new design language.
And the purpose of the new
design language will be to
highlight different aspects
of the system.
It will suppress some kinds of
details and emphasize other
kinds of details.
This is going to be the most
magical part of the course.
We're going to start out by
actually looking at the
technology for building new
computer languages.
The first thing we're going to
do is actually build in Lisp.
We're going to express in Lisp
the process of interpreting
Lisp itself.
And that's going to be a very
sort of self-circular thing.
There's a little mystical
symbol that
has to do with that.
The process of interpreting Lisp
is sort of a giant wheel
of two processes, apply and
eval, which sort of constantly
reduce expressions
to each other.
Then we're going to see all
sorts of other magical things.
Here's another magical symbol.
This is sort of the Y operator,
which is, in some
sense, the expression
of infinity inside
our procedural language.
We'll take a look at that.
In any case, this section
of the course is called
Metalinguistic Abstraction,
abstracting by talking about
how you construct
new languages.
As I said, we're going to start
out by looking at the
process of interpretation.
We're going to look
at this apply-eval
loop, and build Lisp.
Then, just to show you that this
is very general, we're
going to use exactly the same
technology to build a very
different kind of language, a
so-called logic programming
language, where you don't really
talk about procedures
at all that have inputs
and outputs.
What you do is talk about
relations between things.
And then finally, we're going
to talk about how you
implement these things very
concretely on the very
simplest kind of machines.
We'll see something like this.
This is a picture of a chip,
which is the Lisp interpreter
that we will be talking about
then in hardware.
Well, there's an outline of the
course, three big topics.
Black-box abstraction,
conventional interfaces,
metalinguistic abstraction.
Now, let's take a break now and
then we'll get started.
[MUSIC PLAYING]
Let's actually start in
learning Lisp now.
Actually, we'll start out by
learning something much more
important, maybe the very most
important thing in this
course, which is not Lisp, in
particular, of course, but
rather a general framework for
thinking about languages that
I already alluded to.
When somebody tells you they're
going to show you a
language, what you should say
is, what I'd like you to tell
me is what are the primitive
elements?
What does the language
come with?
Then, what are the ways you
put those together?
What are the means
of combination?
What are the things that allow
you to take these primitive
elements and build bigger
things out of them?
What are the ways of putting
things together?
And then, what are the
means of abstraction?
How do we take those complicated
things and draw
those boxes around them?
How do we name them so that we
can now use them as if they
were primitive elements
in making still
more complex things?
And so on, and so
on, and so on.
So when someone says to you,
gee, I have a great new
computer language, you don't
say, how many characters does
it take to invert a matrix?
It's irrelevant.
What you say is, if the language
did not come with
matrices built in or with
something else built in, how
could I then build that thing?
What are the means of
combination which would allow
me to do that?
And then, what are the means of
abstraction which allow me
then to use those as elements
in making more complicated
things yet?
Well, we're going to see that
Lisp has some primitive data
and some primitive procedures.
In fact, let's really start.
And here's a piece of
primitive data in
Lisp, number 3.
Actually, if I'm being
very pedantic, that's
not the number 3.
That's some symbol that
represents Plato's concept of
the number 3.
And here's another.
Here's some more primitive
data in Lisp, 17.4.
Or actually, some representation
of 17.4.
And here's another one, 5.
Here's another primitive
object that's
built in Lisp, addition.
Actually, to use the same kind
of pedantic-- this is a name
for the primitive method
of adding things.
Just like this is a name for
Plato's number 3, this is a
name for Plato's concept
of how you add things.
So those are some primitive
elements.
I can put them together.
I can say, gee, what's the
sum of 3 and 17.4 and 5?
And the way I do that is to
say, let's apply the sum
operator to these
three numbers.
And I should get, what?
8, 17.
25.4.
So I should be able to ask Lisp
what the value of this
is, and it will return 25.4.
Let's introduce some names.
This thing that I typed is
called a combination.
And a combination consists,
in general,
of applying an operator--
so this is an operator--
to some operands.
These are the operands.
And of course, I can make
more complex things.
The reason I can get complexity
out of this is
because the operands themselves,
in general, can be
combinations.
So for instance, I could say,
what is the sum of 3 and the
product of 5 and
6 and 8 and 2?
And I should get-- let's see--
30, 40, 43.
So Lisp should tell
me that that's 43.
Forming combinations is the
basic needs of combination
that we'll be looking at.
And then, well, you see
some syntax here.
Lisp uses what's called prefix
notation, which means that the
operator is written to the
left of the operands.
It's just a convention.
And notice, it's fully
parenthesized.
And the parentheses make it
completely unambiguous.
So by looking at this, I can see
that there's the operator,
and there are 1, 2,
3, 4 operands.
And I can see that the second
operand here is itself some
combination that has one
operator and two operands.
Parentheses in Lisp are a little
bit, or are very unlike
parentheses in conventional
mathematics.
In mathematics, we sort of use
them to mean grouping, and it
sort of doesn't hurt if
sometimes you leave out
parentheses if people
understand
that that's a group.
And in general, it doesn't
hurt if you put in extra
parentheses, because that
maybe makes the
grouping more distinct.
Lisp is not like that.
In Lisp, you cannot leave out
parentheses, and you cannot
put in extra parentheses,
because putting in parentheses
always means, exactly and
precisely, this is a
combination which has
meaning, applying
operators to operands.
And if I left this out, if I
left those parentheses out, it
would mean something else.
In fact, the way to think about
this, is really what I'm
doing when I write something
like this is writing a tree.
So this combination is a tree
that has a plus and then a 3
and then a something else
and an 8 and a 2.
And then this something else
here is itself a little
subtree that has a star
and a 5 and a 6.
And the way to think of that
is, really, what's going on
are we're writing these trees,
and parentheses are just a way
to write this two-dimensional
structure as a linear
character string.
Because at least when Lisp first
started and people had
teletypes or punch cards or
whatever, this was more
convenient.
Maybe if Lisp started today,
the syntax of Lisp
would look like that.
Well, let's look at
what that actually
looks like on the computer.
Here I have a Lisp interaction
set up.
There's a editor.
And on the top, I'm going to
type some values and ask Lisp
what they are.
So for instance, I can say
to Lisp, what's the
value of that symbol?
That's 3.
And I ask Lisp to evaluate it.
And there you see Lisp has
returned on the bottom, and
said, oh yeah, that's 3.
Or I can say, what's the
sum of 3 and 4 and 8?
What's that combination?
And ask Lisp to evaluate it.
That's 15.
Or I can type in something
more complicated.
I can say, what's the sum of the
product of 3 and the sum
of 7 and 19.5?
And you'll notice here that Lisp
has something built in
that helps me keep track of
all these parentheses.
Watch as I type the next closed
parentheses, which is
going to close the combination
starting with the star.
The opening one will flash.
Here, I'll rub those out
and do it again.
Type close, and you see
that closes the plus.
Close again, that
closes the star.
Now I'm back to the sum,
and maybe I'm going to
add that all to 4.
That closes the plus.
Now I have a complete
combination, and I can ask
Lisp for the value of that.
That kind of paren balancing is
something that's built into
a lot of Lisp systems to help
you keep track, because it is
kind of hard just by hand doing
all these parentheses.
There's another kind of
convention for keeping track
of parentheses.
Let me write another complicated
combination.
Let's take the sum of the
product of 3 and 5 and add
that to something.
And now what I'm going to do is
I'm going to indent so that
the operands are written
vertically.
Which the sum of that and
the product of 47 and--
let's say the product
of 47 with a
difference of 20 and 6.8.
That means subtract
6.8 from 20.
And then you see the
parentheses close.
Close the minus.
Close the star.
And now let's get another
operator.
You see the Lisp editor here
is indenting to the right
position automatically to
help me keep track.
I'll do that again.
I'll close that last
parentheses again.
You see it balances the plus.
Now I can say, what's
the value of that?
So those two things, indenting
to the right level, which is
called pretty printing, and
flashing parentheses, are two
things that a lot of Lisp
systems have built in to help
you keep track.
And you should learn
how to use them.
Well, those are the
primitives.
There's a means of
combination.
Now let's go up to the
means of abstraction.
I'd like to be able to take
the idea that I do some
combination like this, and
abstract it and give it a
simple name, so I can use
that as an element.
And I do that in Lisp with
"define." So I can say, for
example, define A to be the
product of 5 and 5.
And now I could say, for
example, to Lisp, what is the
product of A and A?
And this should be 25, and
this should be 625.
And then, crucial thing,
I can now use A--
here I've used it in
a combination--
but I could use that in other
more complicated things that I
name in turn.
So I could say, define B to be
the sum of, we'll say, A and
the product of 5 and A. And
then close the plus.
Let's take a look at that
on the computer and
see how that looks.
So I'll just type what
I wrote on the board.
I could say, define A to be
the product of 5 and 5.
And I'll tell that to Lisp.
And notice what Lisp responded
there with
was an A in the bottom.
In general, when you type in
a definition in Lisp, it
responds with the symbol
being defined.
Now I could say to Lisp, what
is the product of A and A?
And it says that's 625.
I can define B to be the sum of
A and the product of 5 and
A. Close a paren closes
the star.
Close the plus.
Close the "define." Lisp says,
OK, B, there on the bottom.
And now I can say to Lisp,
what's the value of B?
And I can say something more
complicated, like what's the
sum of A and the quotient
of B and 5?
That slash is divide, another
primitive operator.
I've divided B by 5,
added it to A. Lisp
says, OK, that's 55.
So there's what it looks like.
There's the basic means
of defining something.
It's the simplest kind of
naming, but it's not really
very powerful.
See, what I'd really
like to name--
remember, we're talking about
general methods--
I'd like to name, oh, the
general idea that, for
example, I could multiply 5 by
5, or 6 by 6, or 1,001 by
1,001, 1,001.7 by 1,001.7.
I'd like to be able to name
the general idea of
multiplying something
by itself.
Well, you know what that is.
That's called squaring.
And the way I can do that in
Lisp is I can say, define to
square something x, multiply
x by itself.
And then having done that,
I could say to Lisp, for
example, what's the
square of 10?
And Lisp will say 100.
So now let's actually look at
that a little more closely.
Right, there's the definition
of square.
To square something, multiply
it by itself.
You see this x here.
That x is kind of a pronoun,
which is the something that
I'm going to square.
And what I do with it
is I multiply x, I
multiply it by itself.
OK.
So there's the notation for
defining a procedure.
Actually, this is a little bit
confusing, because this is
sort of how I might
use square.
And I say square root of x or
square root of 10, but it's
not making it very clear that
I'm actually naming something.
So let me write this definition
in another way that
makes it a little
bit more clear
that I'm naming something.
I'll say, "define" square to
be lambda of x times xx.
Here, I'm naming something
square, just like over here,
I'm naming something A. The
thing that I'm naming square--
here, the thing I named A was
the value of this combination.
Here, the thing that I'm naming
square is this thing
that begins with lambda, and
lambda is Lisp's way of saying
make a procedure.
Let's look at that more
closely on the slide.
The way I read that definition
is to say, I define square to
be make a procedure--
that's what the lambda is--
make a procedure with
an argument named x.
And what it does is return
the results of
multiplying x by itself.
Now, in general, we're going to
be using this top form of
defining, just because it's a
little bit more convenient.
But don't lose sight of the fact
that it's really this.
In fact, as far as the Lisp
interpreter's concerned,
there's no difference between
typing this to it and typing
this to it.
And there's a word for that,
sort of syntactic sugar.
What syntactic sugar means,
it's having somewhat more
convenient surface forms
for typing something.
So this is just really syntactic
sugar for this
underlying Greek thing
with the lambda.
And the reason you should
remember that is don't forget
that, when I write something
like this, I'm
really naming something.
I'm naming something square,
and the something that I'm
naming square is a procedure
that's getting constructed.
Well, let's look at that
on the computer, too.
So I'll come and I'll say,
define square of
x to be times xx.
Now I'll tell Lisp that.
It says "square." See, I've
named something "square." Now,
having done that, I can
ask Lisp for, what's
the square of 1,001?
Or in general, I could say,
what's the square of the sum
of 5 and 7?
The square of 12's 144.
Or I can use square itself
as an element in some
combination.
I can say, what's the sum
of the square of 3 and
the square of 4?
9 and 16 is 25.
Or I can use square as an
element in some much more
complicated thing.
I can say, what's the square
of, the sqare of,
the square of 1,001?
And there's the square of the
square of the square of 1,001.
Or I can say to Lisp, what
is square itself?
What's the value of that?
And Lisp returns some
conventional way of telling me
that that's a procedure.
It says, "compound procedure
square." Remember, the value
of square is this procedure, and
the thing with the stars
and the brackets are just Lisp's
conventional way of
describing that.
Let's look at two more
examples of defining.
Here are two more procedures.
I can define the average of x
and y to be the sum of x and y
divided by 2.
Or having had average and mean
square, having had average and
square, I can use that to talk
about the mean square of
something, which is the average
of the square of x and
the square of y.
So for example, having done
that, I could say, what's the
mean square of 2 and 3?
And I should get the average
of 4 and 9, which is 6.5.
The key thing here is that,
having defined square, I can
use it as if it were
primitive.
So if we look here on the
slide, if I look at mean
square, the person defining mean
square doesn't have to
know, at this point, whether
square was something built
into the language or
whether it was a
procedure that was defined.
And that's a key thing in Lisp,
that you do not make
arbitrary distinctions between
things that happen to be
primitive in the language
and things that
happen to be built in.
A person using that shouldn't
even have to know.
So the things you construct get
used with all the power
and flexibility as if they
were primitives.
In fact, you can drive that
home by looking on the
computer one more time.
We talked about plus.
And in fact, if I come here on
the computer screen and say,
what is the value of plus?
Notice what Lisp types out.
On the bottom there, it typed
out, "compound procedure
plus." Because, in this system,
it turns out that the
addition operator is itself
a compound procedure.
And if I didn't just type that
in, you'd never know that, and
it wouldn't make any
difference anyway.
We don't care.
It's below the level of
the abstraction that
we're dealing with.
So the key thing is you cannot
tell, should not be able to
tell, in general, the difference
between things that
are built in and things
that are compound.
Why is that?
Because the things that are
compound have an abstraction
wrapper wrapped around them.
We've seen almost all the
elements of Lisp now.
There's only one more we have to
look at, and that is how to
make a case analysis.
Let me show you what I mean.
We might want to think about the
mathematical definition of
the absolute value functions.
I might say the absolute value
of x is the function which has
the property that it's
negative of x.
For x less than 0, it's
0 for x equal to 0.
And it's x for x
greater than 0.
And Lisp has a way of making
case analyses.
Let me define for you
absolute value.
Say define the absolute value
of x is conditional.
This means case analysis,
COND.
If x is less than 0, the
answer is negate x.
What I've written here
is a clause.
This whole thing is a
conditional clause,
and it has two parts.
This part here is a predicate
or a condition.
That's a condition.
And the condition is expressed
by something called a
predicate, and a predicate in
Lisp is some sort of thing
that returns either
true or false.
And you see Lisp has a
primitive procedure,
less-than, that tests whether
something is true or false.
And the other part of a clause
is an action or a thing to do,
in the case where that's true.
And here, what I'm doing
is negating x.
The negation operator, the
minus sign in Lisp is
a little bit funny.
If there's two or more
arguments, if there's two
arguments it subtracts the
second one from the first, and
we saw that.
And if there's one argument,
it negates it.
So this corresponds to that.
And then there's another
COND clause.
It says, in the case where
x is equal to 0,
the answer is 0.
And in the case where
x is greater than 0,
the answer is x.
Close that clause.
Close the COND.
Close the definition.
And there's the definition
of absolute value.
And you see it's the case
analysis that looks very much
like the case analysis you
use in mathematics.
There's a somewhat different
way of writing a restricted
case analysis.
Often, you have a case analysis
where you only have
one case, where you test
something, and then depending
on whether it's true or false,
you do something.
And here's another definition of
absolute value which looks
almost the same, which says,
if x is less than 0, the
result is negate x.
Otherwise, the answer is x.
And we'll be using "if" a lot.
But again, the thing to remember
is that this form of
absolute value that you're
looking at here, and then this
one over here that I wrote
on the board, are
essentially the same.
And "if" and COND are--
well, whichever way
you like it.
You can think of COND as
syntactic sugar for "if," or
you can think of "if" as
syntactic sugar for COND, and
it doesn't make any
difference.
The person implementing a Lisp
system will pick one and
implement the other
in terms of that.
And it doesn't matter
which one you pick.
Why don't we break now, and
then take some questions.
How come sometimes when I write
define, I put an open
paren here and say, define open
paren something or other,
and sometimes when
I write this, I
don't put an open paren?
The answer is, this particular
form of "define," where you
say define some expression, is
this very special thing for
defining procedures.
But again, what it really means
is I'm defining this
symbol, square, to be that.
So the way you should think
about it is what "define" does
is you write "define," and the
second thing you write is the
symbol here-- no open paren--
the symbol you're defining and
what you're defining it to be.
That's like here
and like here.
That's sort of the basic way
you use "define." And then,
there's this special syntactic
trick which allows you to
define procedures that
look like this.
So the difference is, it's
whether or not you're defining
a procedure.
[MUSIC PLAYING]
Well, believe it or not, you
actually now know enough Lisp
to write essentially any
numerical procedure that you'd
write in a language like FORTRAN
or Basic or whatever,
or, essentially, any
other language.
And you're probably saying,
that's not believable, because
you know that these languages
have things like "for
statements," and "do until
while" or something.
But we don't really
need any of that.
In fact, we're not going
to use any of
that in this course.
Let me show you.
Again, looking back at square
root, let's go back to this
square root algorithm of
Heron of Alexandria.
Remember what that said.
It said, to find an
approximation to the square
root of X, you make a guess,
you improve that guess by
averaging the guess and
X over the guess.
You keep improving that until
the guess is good enough.
I already alluded to the idea.
The idea is that, if the initial
guess that you took
was actually equal to the square
root of X, then G here
would be equal to X/G.
So if you hit the square
root, averaging them
wouldn't change it.
If the G that you picked was
larger than the square root of
X, then X/G will be smaller than
the square root of X, so
that when you average
G and X/G, you get
something in between.
So if you pick a G that's
too small, your
answer will be too large.
If you pick a G that's too
large, if your G is larger
than the square root of X and
X/G will be smaller than the
square root of X.
So averaging always gives you
something in between.
And then, it's not quite
trivial, but it's possible to
show that, in fact, if G misses
the square root of X by
a little bit, the average of G
and X/G will actually keep
getting closer to the square
root of X. So if you keep
doing this enough, you'll
eventually get as
close as you want.
And then there's another fact,
that you can always start out
this process by using 1
as an initial guess.
And it'll always converge to
the square root of X. So
that's this method of successive
averaging due to
Heron of Alexandria.
Let's write it in Lisp.
Well, the central idea is, what
does it mean to try a
guess for the square
root of X?
Let's write that.
So we'll say, define to try a
guess for the square root of
X, what do we do?
We'll say, if the guess is good
enough to be a guess for
the square root of X,
then, as an answer,
we'll take the guess.
Otherwise, we will try
the improved guess.
We'll improve that guess for
the square root of X, and
we'll try that as a guess for
the square root of X. Close
the "try." Close the "if." Close
the "define." So that's
how we try a guess.
And then, the next part of the
process said, in order to
compute square roots, we'll
say, define to compute the
square root of X, we will try
1 as a guess for the square
root of X. Well, we have to
define a couple more things.
We have to say, how is
a guess good enough?
And how do we improve a guess?
So let's look at that.
The algorithm to improve a guess
for the square root of
X, we average--
that was the algorithm--
we average the guess with
the quotient of
dividing X by the guess.
That's how we improve a guess.
And to tell whether a guess is
good enough, well, we have to
decide something.
This is supposed to be a guess
for the square root of X, so
one possible thing you can do
is say, when you take that
guess and square it, do you get
something very close to X?
So one way to say that is to
say, I square the guess,
subtract X from that, and see if
the absolute value of that
whole thing is less than some
small number, which depends on
my purposes.
So there's a complete procedure
for how to compute
the square root of X. Let's look
at the structure of that
a little bit.
I have the whole thing.
I have the notion of how to
compute a square root.
That's some kind of module.
That's some kind of black box.
It's defined in terms of how to
try a guess for the square
root of X.
"Try" is defined in terms of,
well, telling whether
something is good enough
and telling
how to improve something.
So good enough.
"Try" is defined in terms of
"good enough" and "improve."
And let's see what
else I fill in.
Well, I'll go down this tree.
"Good enough" was defined
in terms of
absolute value, and square.
And improve was defined in
terms of something called
averaging and then some other
primitive operator.
Square root's defined in terms
of "try." "Try" is defined in
terms of "good enough"
and "improve,"
but also "try" itself.
So "try" is also defined in
terms of how to try itself.
Well, that may give you some
problems. Your high school
geometry teacher probably told
you that it's naughty to try
and define things in terms of
themselves, because it doesn't
make sense.
But that's false.
Sometimes it makes perfect
sense to define things in
terms of themselves.
And this is the case.
And we can look at that.
We could write down what this
means, and say, suppose I
asked Lisp what the square
root of 2 is.
What's the square
root of 2 mean?
Well, that means I try
1 as a guess for the
square root of 2.
Now I look.
I say, gee, is 1 a good
enough guess for the
square root of 2?
And that depends on the test
that "good enough" does.
And in this case, "good enough"
will say, no, 1 is not
a good enough guess for
the square root of 2.
So that will reduce to saying,
I have to try an improved--
improve 1 as a guess for the
square root of 2, and try that
as a guess for the
square root of 2.
Improving 1 as a guess for the
square root of 2 means I
average 1 and 2 divided by 1.
So this is going
to be average.
This piece here will be the
average of 1 and the
quotient of 2 by 1.
That's this piece here.
And this is 1.5.
So this square root of 2 reduces
to trying 1 for the
square root of 2, which reduces
to trying 1.5 as a
guess for the square
root of 2.
So that makes sense.
Let's look at the rest
of the process.
If I try 1.5, that reduces.
1.5 turns out to be not good
enough as a guess for the
square root of 2.
So that reduces to trying the
average of 1.5 and 2 divided
by 1.5 as a guess for the
square root of 2.
That average turns
out to be 1.333.
So this whole thing reduces to
trying 1.333 as a guess for
the square root of 2.
And then so on.
That reduces to another called
a "good enough," 1.4
something or other.
And then it keeps going until
the process finally stops with
something that "good enough"
thinks is good enough, which,
in this case, is 1.4142
something or other.
So the process makes
perfect sense.
This, by the way, is called
a recursive definition.
And the ability to make
recursive definitions is a
source of incredible power.
And as you can already see I've
hinted at, it's the thing
that effectively allows you to
do these infinite computations
that go on until something is
true, without having any other
constricts other than the
ability to call a procedure.
Well, let's see, there's
one more thing.
Let me show you a variant of
this definition of square root
here on the slide.
Here's sort of the same thing.
What I've done here is packaged
the definitions of
"improve" and "good enough"
and "try" inside "square
root." So, in effect, what
I've done is I've built a
square root box.
So I've built a box that's the
square root procedure that
someone can use.
They might put in 36
and get out 6.
And then, packaged inside this
box are the definitions of
"try" and "good enough"
and "improve."
So they're hidden
inside this box.
And the reason for doing that
is that, if someone's using
this square root, if George is
using this square root, George
probably doesn't care very much
that, when I implemented
square root, I had things inside
there called "try" and
"good enough" and "improve." And
in fact, Harry might have
a cube root procedure that has
"try" and "good enough" and
"improve." And in order to not
get the whole system confused,
it'd be good for Harry to
package his internal
procedures inside his
cube root procedure.
Well, this is called block
structure, this particular way
of packaging internals inside
of a definition.
And let's go back and look
at the slide again.
The way to read this kind of
procedure is to say, to define
"square root," well, inside that
definition, I'll have the
definition of an "improve" and
the definition of "good
enough" and the definition of
"try." And then, subject to
those definitions, the way I
do square root is to try 1.
And notice here, I don't have
to say 1 as a guess for the
square root of X, because since
it's all inside the
square root, it sort of
has this X known.
Let me summarize.
We started out with the idea
that what we're going to be
doing is expressing imperative
knowledge.
And in fact, here's a slide
that summarizes the way we
looked at Lisp.
We started out by looking at
some primitive elements in
addition and multiplication,
some predicates for testing
whether something is less-than
or something's equal.
And in fact, we saw really
sneakily in the system we're
actually using, these aren't
actually primitives, but it
doesn't matter.
What matters is we're going
to use them as if they're
primitives.
We're not going to
look inside.
We also have some primitive
data and some numbers.
We saw some means of
composition, means of
combination, the basic one being
composing functions and
building combinations with
operators and operands.
And there were some other
things, like COND and "if" and
"define." But the main thing
about "define," in particular,
was that it was the means
of abstraction.
It was the way that
we name things.
You can also see from this slide
not only where we've
been, but holes we
have to fill in.
At some point, we'll have to
talk about how you combine
primitive data to get compound
data, and how you abstract
data so you can use large
globs of data as
if they were primitive.
So that's where we're going.
But before we do that, for the
next couple of lectures we're
going to be talking about, first
of all, how it is that
you make a link between these
procedures we write and the
processes that happen
in the machine.
And then, how it is that you
start using the power of Lisp
to talk not only about these
individual little
computations, but about general
conventional methods
of doing things.
OK, are there any questions?
AUDIENCE: Yes.
If we defined A using
parentheses instead of as we
did, what would be
the difference?
PROFESSOR: If I wrote this, if
I wrote that, what I would be
doing is defining a procedure
named A. In this case, a
procedure of no arguments,
which, when I ran it, would
give me back 5 times 5.
AUDIENCE: Right.
I mean, you come up with the
same thing, except for you
really got a different--
PROFESSOR: Right.
And the difference would
be, in the old one--
Let me be a little
bit clearer here.
Let's call this A, like here.
And pretend here, just for
contrast, I wrote, define D to
be the product of 5 and 5.
And the difference between
those, let's think about
interactions with the
Lisp interpreter.
I could type in A and Lisp
would return 25.
I could type in D, if I just
typed in D, Lisp would return
compound procedure D, because
that's what it is.
It's a procedure.
I could run D. I could say,
what's the value of running D?
Here is a combination
with no operands.
I see there are no operands.
I didn't put any after D. And
it would say, oh, that's 25.
Or I could say, just for
completeness, if I typed in,
what's the value of running A?
I get an error.
The error would be the same
one as over there.
It'd be the error would say,
sorry, 25, which is the value
of A, is not an operator that
I can apply to something.
Ich möchte sie willkommen heißen zum Computerwissenschaften Kurs.
Eigentlich ist das ein schrecklicher Beginn. Computerwissenschaften ist ein schrecklicher Name für dieses Business.
Erstens, es ist keine Wissenschaft.
Es könnte Ingenieurswesen sein oder auch Kunst.
Aber wir werden sehen, dass Computer - das so genannte Wissenschaften sehr viel gemeinsam hat mit Magie.
Wir werden das in diesem Kurs sehen.
Also es ist keine Wissenschaft. Es geht auch nicht wirklich um Computer.
Und es geht nicht um Computer, so wie Physik nicht wirklich mit Teilchenbeschleuniger zu tun hat.
Und Biologie ist nicht wirklich über Mikroskope und Petrischalen.
Es geht nicht um Computer, so wie es in der Geometrie
nicht wirklich darum geht, Feldmessinstrumente zu verwenden.
Eigentlich gibt es viele Gemeinsamkeiten zwischen Computerwissenschaften und Geometrie.
Zuerst, Geometrie, ist ein anderes Fach mit elenden Namen.
Der Name kommt von "gaia", was " Erde" bedeutet und "metron" , was "messen" bedeutet.
Geometrie meinte ursprünglich das messen der Erde, oder vermessen.
Und der Grund dafür war, dass tausende Jahre früher
die Ägyptische Priesterschaft die Anfänge der Geometrie entwickelten
um herauszufinden, wie man die Grenzen auf Feldern wiederherstellen könnte,
die nach der jährlichen Flut des Nils zerstört worden waren.
Und für die Ägypter, die das taten, war Geometrie wirklich
das Verwenden von Feldvermessungsgeräten.
Nun, der Greund warum wir denken, dass Computerwissenschaften von Computern handelt,
ist ziemlich genau der Grund warum die Ägypter glauben
Geometrie hätte mit Feldvermessungsgeräten zu tun.
[MUSiK]
Ich kann sagen: Was ist die Summe von 3 und 17.4 und 5? Und der Weg, wie ich das mache
ist, zu sagen, wir wollen den Summen Oprator zu diesen drei Zahlen verwenden und es sollte 25.5 herauskommen.
Wir wollen ein paar Begriffe einführen. Das, was ich geschrieben habe, nennt sich Kombination.
Eine Kombination besteht im allgemeinen daraus, einen Operator zu verwenden ( also das ist ein Operator)
mit Operanden ( das sind die Operanden).
Und natürlich kann ich komplexere Dinge machen
Lassen Sie mich eine andere komplizierte Kombination aufschreiben.
Mal sehen, die Summe des Produkts von 3 und 5
und das addieren zu etwas. Also, was ich jetzt machen werde, ist das die Operanden
vertikal geschrieben werden. Die Summe davon und dem Produkt von 47 und - sagen wir dem Produkt von 47
mit der Differenz von 30 und 6.8
Das heißt 6.8 von 20 substrahieren. Und dann sehen Sie die geschlossene Klammer.
Schließen Sie das minus (-) ein, schließen sie den Stern (*)
Und jetzt gehen wir zu einem anderen Operator. Hier sehen Sie den Lisp Editor.
Quisiera darles la bienvenida
a este curso de ciencias del computador.
En realidad, esta es una manera
terrible de empezar
Ciencias del computador
es un nombre terrible para este negocio.
En primer lugar,
no es una ciencia.
Podría ser ingeniería o podría ser arte,
pero veremos que la así llamada
ciencia del computador
tiene mucho en común con la magia,
y eso lo veremos
en este curso.
Así que no es una ciencia.
Tampoco es acerca de computadoras.
Y no es acerca de computadoras
en el mismo sentido que la física
no es acerca de aceleradores de partículas,
y la biología
no es acerca de microscopios y cápsulas de Petri.
Y no acerca de computadores,
de la misma manera que
la geometría no es acerca
de usar elementos de inspección.
De hecho, hay mucho en común
con las ciencias de la computación
y la geometría.
La geometría, en principio, es otra área
con un nombre malísimo.
El nombre proviene de Gaia,
que significa la Tierra, y metron,
que significa medir.
Geometría originalmente
significaba la medición
de la Tierra o la inspección.
Y la razón de eso es que,
hace miles de años,
los sacerdotes egipcios desarrollaron
los rudimentos de
la geometría para poder determinar
como restaurar los
límites de los campos que eran destruídos
en la inundaciones
anuales del Nilo.
Y para los egipcios que hacían eso,
la geometría era de hecho
el uso de instrumentos de inspección.
Ahora bien, la razón por la que pensamos
que las ciencias del computador son acerca
de computadoras es la misma razón
por la que los egipcios
pensaban que la geometría era
acerca de instrumentos de inspección.
Y es que, cuando un campo recién
está comenzando
y no es realmente comprendido muy bien,
es muy fácil
confundir la esencia de los que se hace
con las herramientas
que se utilizan.
En efecto, en alguna escala absoluta,
probablemente sabemos
menos sobre la esencia
de las ciencias del computador
que los antiguos egipcios
acerca de la geometría.
Bueno, ¿ qué quiero decir con esencia
de las ciencias del computador?
¿Qué quiero decir con la esencia
de la geometría?
Verán, es cierto que esos egipcios
salían y usaban
instrumentos de inspección, pero
cuando cuando los miramos
un par de miles de años después,
decimos que lo que
estaban haciendo, lo realmente importante
que estaban haciendo, era
empezar a formalizar las nociones del
espacio y del tiempo, a comenzar
a hablar acerca de verdades matemáticas
formalmente.
Eso llevó al método axiomático.
Y eso llevó a casi todas
las matemáticas modernas.
Descubriendo una manera de hablar
precisamente acerca del así llamando
conocimiento declarativo.
Acerca de lo que es verdadero.
Similarmente, pienso que en futuro,
la gente observará hacia atrás
y dirá que sí, que esos primitivos del
siglo XX
estaban jugueteando con esos
dispositivos llamados
computadoras, pero que en realidad lo que
estaban haciendo era comenzar
a aprender a formalizar intuiciones
acerca del proceso, acerca de cómo
hacer cosas. Empezar a desarrollar
una manera para hablar
precisamente acerca del conocimiento
del 'cómo', en contraste con
con la geometría que habla sobre
lo que es verdad.
Déjenme darles un ejemplo de esto.
Echemos un vistazo.
Aquí está una pieza matemática
que dice qué
es una raíz cuadrada.
La raíz cuadrada de X es el número Y,
tal que Y al cuadrado
es igual a X e Y es mayor a cero.
Ahora bien, esa es una pieza
matemática, pero solamente decirte
qué es una raíz cuadrada no dice
realmente nada
acerca de cómo uno puede ir
y encontrar una.
Así que contrastemos eso con una pieza
de conocimiento imperativo,
cómo ir y encontrar la raíz cuadrada.
Esto, de hecho, también proviene de
Egipto,
pero no el antiguo, antiguo Egipto.
Este es un algoritmo de
Herón de Alejandría, llamado
cómo encontrar la raíz cuadrada
mediante promedios sucesivos.
Y lo que dice es que,
para hallar la raíz cuadrada,
uno hace una estimación y luego
la mejora.
Y la manera en la que mejora esa
estimación es promediándola
con X sobre la estimación.
Luego hablaremos un poco acerca de
por qué eso es algo razonable.
Y se sigue mejorando la estimación
hasta que sea lo suficientemente buena.
Eso es un método.
Eso es cómo hacer algo
en oposición al conocimiento
declarativo que dice
qué es lo que están buscando.
Eso es un proceso.
Ahora bien,
¿Qué es un proceso en general?
Es difícil de decir.
Uno podría pensarlo como un espíritu
mágico que
vive en la computadora y hace algo.
Y aquello que dirige a un proceso
es una patrón de reglas
llamado procedimiento.
Así que los procedimientos son hechizos,
por así decirlo, que controlan
a estos espíritus mágicos
que son los procesos.
Imagino que saben que todos necesitan
un lenguaje mágico y que
los hechiceros, los verdaderos hechiceros,
usaban antiguo Arcadio o Sumerio
o Babilonio o lo que sea.
Nosotros conjuraremos nuestros espíritus
en un lenguaje mágico
llamado Lisp, que es un lenguaje
diseñado para hablar sobre
y para realizar los hechizos
que son los procedimienntos que dirigen
los procesos.
Ahora bien, es muy fácil aprender Lisp.
De hecho, en unos pocos minutos,
les enseñaré,
esencialmente, todo Lisp.
Les voy a enseñar, esencialmente,
todas las reglas.
Y no deberían encontrar eso
particularmente sorprendente.
Es como decir que es muy fácil aprender
las reglas del ajedrez.
Y en efecto, en unos pocos minutos,
le pueden contar a alguien
las reglas del ajedrez.
Pero por supuesto, eso es muy diferente
a que tu digas que
entiendes las implicaciones de esas reglas
y cómo usarlas
para convertirte en un excelente
jugador de ajedrez.
Bueno, Lisp es así.
Declararemos las reglas en unos minutos
y serán muy fácil de ver.
Pero lo que será realmente difícil
son las implicaciones
de esas reglas, cómo explotarlas
para ser
un maestro programador.
Y las implicaciones de esas reglas
nos llevarán
bueno, el resto de la materia y,
por supuesto,
mucho más.
Así que es ciencias de la computación,
estamos en el negocio de
formalizar esta forma de
conocimiento imperativo.
Cómo hacer cosas.
Y los verdaderos problemas de
las ciencias de la computación son,
por supuesto, no decirle a la gente
cómo calcular raíces cuadradas.
Porque si eso fuera todo lo que hay,
no sería un gran inconveniente.
Los verdaderos problemas vienen cuando
intentamos construir sistemas muy grandes,
programas de computadoras que
tienen miles de páginas de longitud.
Tan largos que nadie puede realmente
mantenerlo en su cabeza
todo al mismo tiempo.
Y la razón por la que eso es posible,
es porque
hay técnicas que controlan la complejidad
de estos sistemas grandes.
Y esas técnicas
que controlan la complejidad son
el verdadero objeto de este curso.
Y de alguna manera,
eso es acerca de lo que
las ciencias de la computación son.
Ahora bien, eso puede parecer
algo muy extraño de decir.
Porque, después de todo, un montón
de gente al margen de los computadores
científicos lidian con el control de
la complejidad.
Una gran aerolínea un es sistema
extremadamente complejo y
los ingenieros aeronáuticos que la
diseñan lidian con
una complejidad inmensa.
Pero hay una diferencia entre esa clase
de complejidad y lo que nos enfrentamos
en las ciencias de la computación.
Y eso es que es la ciencias de
la computación
en algún sentido, no son reales.
Verán, cuando un ingeniero está
diseñando un sistema físico,
eso está hecho de piezas reales.
Los ingenieros que se preocupan de eso
tienen que resolver problemas
de tolerancia, aproximación
y ruido en el sistema.
Por ejemplo, como un ingeniero eléctrico,
puedo ir
y construir fácilmente un amplificador
de un nivel
o un amplificador de dos niveles,
y puedo imaginar apilar muchos de ellos
para construir un amplificador
de millones de niveles.
Pero es ridículo construir algo así,
porque mucho antes
del millonésimo nivel,
el sonido térmico en esos
componentes en el principio será
amplificado y dejará toda la construcción
sin sentido.
Las ciencias de la computación lidian
con componentes idealizados.
Sabemos tanto como queremos acerca
de estos pequeños programas y
piezas de datos que estamos juntando.
No nos tenemos que preocupar
acerca de la tolerancia.
Y eso significa que, al construir
un programa grande,
no hay mucha diferencia
entre lo que puedo
construir y lo que puedo imaginar,
porque las partes son estas
entidades abstractas de las que
conozco tanto como quiero.
Conozco sobre ellas con tanta
precisión como quiera.
Así que en contraste con otras
formas de ingeniería, donde
las restricciones sobre lo que puedo
construir son aquellas de los
sistemas físicos, las restricciones
de la física y
del ruido y de la aproximación,
las restricciones impuestas
sobre los grandes sistemas de software
son las limitaciones
de nuestras propias mentes.
Así que de alguna manera,
las ciencias de la computación son
una forma abstracta de ingeniería.
Es la clase de ingeniería donde
se ignoran las
restricciones que se imponen
sobre la realidad
Bueno, ¿cuáles son algunas
de estas técnicas?
No son únicas de las
ciencias de la computación
La primera técnica, que se usa
en toda forma de ingeniería, es
una especie de abstracción llamada
abstracción de caja negra.
Agarrar algo y
construir una caja alrededor.
Por ejemplo, si miramos el método para
obtener raíces cuadradas,
podría querer agarrarlo
y construir una caja
que dijera cómo encontrar la raíz
cuadrada de X. Y eso
podría ser complejo conjunto de reglas.
Y eso podría terminar siendo una cosa
donde puedo poner,
digamos, 36 y preguntar cuál es la
raíz cuadrada de 36.
Y saldrá un 6.
Y lo importante es que me gustaría
diseñarlo para que si
George viniese y quisiese computar,
digamos, la raíz cuadrada de A
más la raíz cuadrada de B, él podría
agarrar esta cosa y usarla
como un módulo sin tener
que mirar adentro y construir algo
que se parezca a esto:
Una A, una B y una
caja de raíz cuadrada y otra
caja de raíz cuadrada y luego
algo que sume
que devuelva la respuesta.
Y pueden ver, que solo
por el hecho de que quiero hacer eso,
desde el punto de vista de George,
lo que hay adentro de esto
no debería ser importante.
Así que, por ejemplo, no debería
importar que, cuando escribo esto,
digo que quiero hallar
la raíz cuadrada de X. Podría
haber dicho la raíz cuadrada de Y,
o la raíz cuadrada de A, o
ninguna cosa.
Esa es la noción fundamental
de poner algo en una caja,
usar abstracción de caja negra
para suprimir detalle.
Y la razón de eso es que uno
querría ir construir
cajas más grandes.
Hay otra razón para hacer
abstracción de caja negra
más allá de queres suprimir
detalles para
construir cajas más grandes.
A veces, uno quiere decir que
la manera de hacer algo,
el método, es una instancia
de algo más general,
y uno quisiera que el lenguaje
sea capaz de expresar
esa generalidad.
Déjenme darles otro ejemplo,
siguiendo con raíces cuadradas.
Miremos de vuelta la diapositiva
del algoritmo de la raíz cuadrada.
Recuerden lo que dice.
Dice que, para hacer algo,
hago una estimación y
mejoro esa estimación y sigo
mejorándola.
Así que es la estrategia general.
Busco algo
y la forma en la que lo encuentro es
seguir mejorándolo.
Ahora bien, eso es un caso particular
de otra clase de estrategia
para hallar un punto fijo de algo.
Así que tienes un punto fijo
de una función
Un punto fijo de una función es algo,
un valor.
Un punto fijo de una función F
es un valor Y, tal que F(Y)
es igual a Y. Y la forma en que podría
hacerlo es empezando con una estimación.
Y luego si quiero que algo no cambie
cuando
le sigo aplicando F, sigo aplicando F
una y otra vez hasta
que el resultado no cambie
demasiado.
Así que hay una estrategia general.
Y luego, por ejemplo, para computar
la raíz cuadrada de X
puedo intentar y hallar un punto fijo
de la función que
lleva a Y al promedio de X/Y.
Y la idea es que si
realmente tuviera en Y la raíz
cuadrada de X, entonces Y y
X/Y serían el mismo valor.
Ambos serían la raíz cuadrada de X,
porque X sobre
la raíz cuadrada de X
es la raíz cuadrada de X.
Así que si Y fuera
la raíz cuadrada de X,
entonces el promedio no cambiaría.
Así que la raíz cuadrada de X es
un punto fijo
de una función en particular.
Ahora bien, lo que me gustaría tener,
lo que me gustaría expresar es
una estrategia general para hallar
puntos fijos.
Así que lo podría imaginar hacer,
es ser capaz de
usar mi lenguaje para definir una caja
que dijera "punto fijo",
de la misma manera que podría hacer una
caja que dijera "raíz cuadrada".
Y me gustaría poder expresar
esto en mi lenguaje.
Así que me gustaría expresar
no sólo el conocimento imperativo
de una cosa en particular
como la raíz cuadrada, sino que
me gustaría poder expresar el
conocimiento imperativo de
cómo hacer algo general como hallar un
punto fijo.
Y de hecho, miremos la diapositiva
de vuelta.
No sólo es una pieza de conocimento
imperativo, cómo
hallar un punto fijo,
pare aquí debajo hay
otra pieza de conocimento imperativo que
dice que una forma de computar
la raíz cuadrada es aplicar este
método general de punto fijo.
Así que quiero ser capaz
de expresar
ese conocimiento imperativo.
¿Cómo se vería eso?
Diría, esta caja de punto fijo
es tal que si
le introduzco la función que
lleva a Y de al promedio de Y
y X/Y, entonces lo que saldrá
de esa caja de punto fijo será
un método para hallar raíces cuadradas.
Así que en estas cajas que estamos
construyendo, no sólo estamos
construyendo cajas que reciben números
y devuelven números,
sino también construiremos cajas que,
en efecto, computan
métodos como hallar la raíz cuadrada.
Y lo hago introduciendo funciones,
como Y va
al promedio de Y y X/Y. Y la razón por
la queremos hacer eso,
la razón por la que es un procedimiento,
que terminará siendo un procedimiento,
cuyo valor es, como veremos, otro
procedimiento, la razón por la que
queremos hacer eso es porque
los procedimientos van a ser nuestros
medios para hablar acerca de
conocimiento imperativo.
Y la forma de hacer eso muy
poderoso es poder hablar
acerca de otros tipos de conocimiento.
Así que aquí hay un procedimiento que,
en efecto, habla sobre otro
procedimiento. Una estrategia general que
por sí misma habla sobre
estrategias generales.
El primer tema de este curso
-- habrá tres grandes temas--
será abstracción de caja negra.
Miremos eso con un poco más de detalle.
Lo que haremos es empezar a hablar sobre
como Lisp está construido con
objetos primitivos.
¿Qué nos provee el lenguaje?
Y veremos que hay
procedimientos primitivos
y datos primitivos.
Luego veremos cómo tomar esas primitivas
y combinarlas para hacer cosas más
complicadas.
Medio de combinación.
Y lo que veremos es que hay formas
de poner
cosas juntas, poner primitivas juntas
para hacer procedimientos más
complicados.
Y veremos cómo combinar datos primitivos
para hacer datos compuestos.
Luego diremos, bueno, habiendo hecho
estas cosas compuestas,
¿cómo las abstraemos?
¿Cómo ponemos esas cajas negras
alrededor para
usarlas como componentes en cosas más
complejas?
Y veremos que eso se hace
definiendo procedimientos y
una técnica para lidiar con datos
compuestos llamada
abstracción de datos.
Y luego, lo que quizá es lo
más importante, es ir
desde sólo las reglas a como
trabaja un experto.
¿Cómo expresar patrones comunes para
hacer cosas, como
digamos, bueno, hay un método
general del punto fijo
y la raíz cuadrada es un caso particular
de eso?
Y usaremos,
ya les di la pista, algo llamado
procedimientos
de alto orden. Procedimientos
cuyas entradas y salidas
son procedimientos.
Y luego veremos algo muy interesante.
Veremos, mientras avanzamos más
y más y nos volvamos
más abstractos, que
la línea entre lo que consideramos datos
y lo que
consideramos procedimientos se hará difusa
a un ritmo increíble.
Bueno, ese el primer tema:
Abstracciones
de caja negra.
Miremos el segundo tema
Puedo introducirlo así>
Supongan que quiero expresar la idea --
recuerden, estamos hablando de ideas --
Supongan que quiero expresa la idea de
puedo tomar algo
y multiplicarlo por la suma de dos otras cosas.
Por ejemplo, so tuviera 1 y 3
y multiplico
eso por 2, obtendría 8.
Pero estoy hablando de la idea general
de lo que se conoce como
combinación lineal, que puedas
sumar dos cosas
y multiplicarlas por otra.
Es muy fácil cuando lo pienso para
números, pero
supongan que quiero usar la misma idea
para sumar dos vectores a1 y a2,
y luego escalarlos por
algún factor X y obtener otro vector.
O podría decir,
quisiera pensar a a1 y a2
como polinomios y quisiera sumar
esos dos polinomios
y luego multiplicarlos por 2
para obtener otro más complicado.
O a1 y a2 pueden ser señales eléctricas
y podría
pensar acerca de sumar esas dos señales
eléctricas y luego poner resultado
a travéz
de un amplificador, multiplicándolo
pr un facto de 2 o algo.
La idea es que quiero pensar sobre
la noción general de eso.
Ahora, si nuestro lenguaje va ser
un buen lenguaje
para expresar ese tipo de ideas
generales, si yo pudiera
realmente hacer eso, me gustaría
ser capaz de decir que voy a
multiplicar por X la suma de a1 y a2,
y me gustaría que eso
expresra la idea general de
todas las cosas diferentes que
a1 y a2 puedan ser.
Si piensan sobre eso,
hay un problema porque
después de todo, las verdaderas
operaciones primitivas que van
a la máquina serán obviamente diferentes
si estuviera sumando dos números
o si estuviera sumando
dos polinomios, o si estuviera
sumando la representación de dos
señales eléctricas o formas de ondas.
En algún lugar, tiene que haber
un conocimiento de la clase de
distintas cosas que uno puede sumar
y la forma de sumarlas.
Para construir un sistema así,
la pregunta es, ¿dónde
pongo ese conocimiento?
¿Cómo hago para pensar acerca de
las diferentes clases
de opciones que tengo?
Y si mañana George viene con una
nueva clase de objeto
que puede ser sumado y multiplicado,
¿Cómo agrego
el nuevo objeto de George
al sistema sin arruinar
todo lo que ya estaba allí?
Bueno, ese será el segundo gran tema.
La forma de controlar esa clase de complejidad.
Y la forma de hacerlo es
establecimiento interfaces
convencionales, poniendo de acuerdo
en formas de combinar cosas.
De la misma manera que la ingeniería
eléctrica, la gente
tiene impedancias estándar para conectores,
y luego sabes
que si construyes algo con uno de esas
impedancias
estándard, entonces puedes conectarlo
con otra cosa.
Así que ese será nuestro
segundo gran tema,
interfaces convencionales.
Lo que veremos es que,
primero, hablaremos
sobre el problema de operaciones
genéricas, que es aquél
al que aludí, cosas como "suma"
que tiene que trabajar con
diferentes tipos de datos.
Así que hablamos de operaciones
genéricas.
Luego vamos a hablar sobre
estructuras de larga escala.
¿Cómo combinar programs muy grandes
que modelan
la clase de sistemas complejos del mundo real
que queremos modelar?
Y vermos que hay dos
metáforas muy importantes para combinar
dichos sistemas.
Una se llama programación orientada
a objetos, donde uno
piensa al sistema como una sociedad
llena de pequeñas coasa
que interactúan enviándose
información entre ellos.
Y la segunda es operaciones
en agregados,
llamados flujos, donde uno piensa
a un sistema grande combinado
de la misma forma que un ingeniero
de procesamiento de señales
construye un sistema eléctrico.
Ese será nuestro segundo tema.
La tercer forma veremos,
la tercer ténica
básica para controlar complejidad
es crear nuevos lenguajes.
Porque a veces, cuando uno está
sobrepasado
por la complejidad del diseño,
la manera en que controlas
esa complejidad es elegir
un nuevo lenguaje de diseño.
Y el propósito de este nuevo lenguaje
de diseño será
resaltar diferentes
aspectos del sistema.
Suprimirá algunos detalles y
enfatizará
otros tipos de detalles.
Esa va a ser la parte
más mágica del curso.
Vamos a empezar por mirar
a la tecnología para construir
nuevos lenguajes de computadora.
Lo primero que haremos es
construir en Lisp.
Vamos a expresar en Lisp
el proceso de interpretar
el propio Lisp.
Y eso va a ser algo
medio meta circular.
Hay un pequeño símbolo místico
que tiene que ver con eso.
El proceso de interpretar Lis
es como una rueda gigante
de dos procesos, apply y eval,
que constantente
reducen expresiones entre sí.
Luego veremos todo tipo
de otras cosas mágicas.
Este es otro símbolo mágico.
Este es como el operador Y,
que es, de alguna manera,
la expresión de infinito
dentro de nuestro lenguaje procedural.
Le echaremos un vistazo a eso.
En cualquier caso, esta sección
del curso se llama
Abstracción Metalinguística,
abstrayendo hablando acerca de
cómo construir nuevos lenguajes.
Como dije, vamos a empezar mirando al
proceso de interpretación.
Miraremos este ciclo de apply-eval
y contruiremos Lisp.
Luego, solo para mostrarles que
es estoy es muy general,
vamos a usar la misma tecnología
para construir un muy
diferente tipo de lenguaje, un lenguaje
conocido como lenguaje de
programación lógica, donde no se
habla de procedimientos
que tienen entradas y salidas.
Lo que se hace es hablar de relaciones
entre cosas.
Y luego, finalmente, vamos a hablar
sobre cómo
implementar estas cosas de manera
muy concreta en
los tipos de máquinas más simples.
Veremos algo así.
Esta es una imagen de un chip,
que es el intérprete de Lisp
del que hablaremos en hardware.
Bueno, hay un bosquejo del curso,
tres grande tópicos.
Abstracción de caja negra,
interfaces convencionales,
abstracción metalinguística.
Ahora, tomémonos un descanso
y luego empezaremos.
Empecemos aprendiendo Lisp ahora.
De hecho, empezaremos aprendiendo
algo mucho más
importante, quizá la cosa más importante
de este curso, que no es Lisp, en particular,
por supuesto, sino
un framework general para pensar
sobre lenguajes al que
ya aludí.
Cuando alguien te dice que te va
mostrar un
lenguaje, lo que deberían decir es,
lo que me gustaría que dijeras es
cuáles son los elemento primitivos.
¿Con qué viene el lenguaje?
Luego, ¿cuáles son las formas
de combinar esas cosas?
¿Cuáles son los medios de combinación?
¿Cuáles son las cosas que te
permiten tomar esos elementos
primitivos y construir
cosas más grandes con ellos?
¿Cuáles con las formas de
combinar cosas?
Y luego,
¿cuáles son los medios de abstracción?
¿Cómo tomamos esas cosas
complicadas y dibujamos
cajas alrededor de ellas?
¿Cómo las nombramos
para que las podamos usar
como elementos primitivos para hacer
cosas aún más complejas?
Y así y así y así.
Así que cuando alguien te dice,
"tengo un gran lenguaje
de computadora nuevo", no le preguntes
cuántos caracteres necesita
para invertir una matriz.
Es irrelevante.
Lo que dices es,
si el lenguaje no viene con matrices
o con otra cosa, ¿cómo
puedo hacer para contruirla?
¿Cuáles son los medio de combinación
que me permiten
hacer eso?
Y luego, ¿cuáles son los medios
de abstracción que me permiten
usar esos elementos para hacer
cosas más complicadas?
Bueno, veremos que Lisp
tiene algunos datos primitivos
y algunos procedimientos primitivos.
De hecho, empecemos realmente.
Aquí hay una pieza de dato primitivo
en Lisp, el número 3.
En realidad, si estuviera muy pedante,
ese no es el número 3.
Ese es un símbolo que representa
el concepto de Platón
del número 3.
Y aquí hay otro.
Aquí hay más datos primitivos
en Lisp, 17.4.
O, en realidad, alguna representación
del 17.4.
Y aquí hay otra, 5.
Aquí hay otro objetivo primitivo
que está construido
en Lisp, la suma.
En verdad, para ser igual de pedante,
este es un nombre
para el método primitivo
para sumar cosas.
De la misma manera que esto es un
nombre para el número 3 de Platón, esto es
un nombre para el concepto platónico
de cómo sumar cosas.
Así que esos son elementos primitivos.
Los puedo poner juntos.
Puedo decir, ¿cuál es la suma de
3 y 17.4 y 5?
Y la forma de hacerlo es decir,
apliquemos el operador de suma
a estos tres números.
Y debo obtener, ¿qué?
8,17.
25.4.
Así que debería poder preguntarle
a Lisp cuál es el valor de esto
y me devolverá 25.4.
Introduzcamos algunos nombres.
Eso que escribí se llama
una combinación.
Y una combinación consiste,
en general,
en aplicar un operador --
esto es un operador--
a algunos operandos.
Estos son los operandos.
Y por supuesto, puedo hacer
cosas más complejas.
La razón por la que puede obtener
complejidad de esto es
porque en los operandos mismo,
en general, pueden ser
combinaciones.
Así que por ejemplo, podría decir
¿cuál es la suma de 3 y
el producto de 5 y 6 y 8 y 2?
Y debería obtener, veamos.
30, 40, 43.
Así que Lisp debería
decirme que eso es 43.
Formar combinaciones es la
necesidad de combinación
más básica que veremos.
Y luego, bueno,
verán un poco de sintaxis aquí.
Lisp usa lo que se llama notación
prefija, que quiere decir que
el operador se escribe a la izquierda
de los operandos.
Sólo es una convención.
Y noten, está totalmente
entre paréntesis.
Y los paréntesis lo dejan
completamente sin ambiguedades.
Asi que mirando esto, puedo ver
que está el operador,
y que hay 1,2,3,4 operandos.
Y puedo ver que el segundo operando
aquí es en sí mismo una
combinación que tiene
un operador y dos operandos.
Los paréntesis en Lisp, son un poco,
o muy diferentes,
a los paréntesis de la matemática
convencional.
En matemática, lo usamos para indicar
una agrupación,
y a veces no molesta que no los pongas
si la gente entiende
que eso es un grupo.
Y en general,
no molesta si pones paréntesis
de más, porque quizá distinga
más aún la agrupación.
Lisp no es así.
En Lisp, no puede dejar los paréntesis,
y no puede poner paréntesis
de más, porque agregar
paréntesis
siempre significa de manera
exacta y precisa que esto es
una combinación que
tiene sentido, aplicando
operadores a operandos.
Y si no los pongo,
si no pongo esos paréntesis,
significaría otra cosa.
De hecho, la manera de pensar sobre esto
es que lo que realmente estoy
haciendo cuando escribo algo así
es estar escribiendo un árbol.
Así que esta combinación es un árbol
que tiene un más y luego un 3
y luego algo más y un 8 y un 2.
Y entonces esta otra cosa
es en sí misma un pequeño
subárbol que tiene una estrella
y un 5 y un 6.
Y la manera de pensar en eso
es que lo que en verdad
estamos escribiendo estos árboles
y los paréntesis son una forma
de escribir esta estructura
de dos dimensiones como
una cadena de caracteres lineal.
Porque, por lo menos al principio,
cuando Lisp comenzaba y la gente
tenía teletipo o tarjetas perforadas
o lo que sea, esto
era más conveniente.
Quizá si Lisp apareciera hoy,
la sintaxis de Lisp
se vería así.
Bueno, observemos cómo
se ve eso
en una computadora.
Aquí tengo establecida
una interacción Lisp.
Hay un editor.
Y arriba, voy a tipear algunos valores
y preguntarle a Lisp
lo que son.
Por ejemplo, puedo preguntarle a Lisp,
cuál es
el valor de este símbolo.
Es un 3.
Y le pido a Lisp que lo evalúe.
Y ahí ven que Lisp ha terminado
debajo y ha dicho
oh sí, es un 3.
O puedo decir, ¿cuál es la suma de 3 y
4 y de 8?
¿Cuánto da esa combinación?
Y pedirle a Lisp que lo evalúe.
Es 15.
O puedo tipear algo
más complicado.
Puedo preguntar cuál es la suma
del producto de 3 y la suma
de 7 y 19.5.
Y notarán que Lisp viene
con algo incorporado
que ayuda para dar seguimiento
a todos estos paréntesis.
Miren que al tipear el próximo
paréntesis de cierre, que va
a cerrar la combinación que
comienza con la estrella,
el paréntesis de apertura
se remarcará.
Borraré estos y lo haré de nuevo.
Tipeo el cierre y
verán que cierra el más.
Cierro de nuevo y
eso cierra la estrella.
Ahora vuelvo a la suma,
y quizá voy a sumar
a todo eso un 4.
Eso cierra el más.
Ahora tengo una combinación
completa y puedo preguntarle
a Lisp el valor de eso.
Ese balanceo de paréntesis
está incorporado en un montón
de sistemas Lisp para dar seguimiento
porque es realmente
difícil de hacer a mano con todos
esos paréntesis.
Hay otra convención
para mantener un seguimiento
de los paréntesis.
Déjenme escribir otra
combinación complicada.
Tomemos la suma del producto
de 3 y de 5 y sumemos eso
a algo más.
Y lo que voy a hacer es
indentar para que
los operandos se escriban
verticalmente.
Que es la suma de eso y
el producto de 47 y --
digamos el producto el 47 con la
diferencia de 20 y 6.8.
Eso quiere decir restarle 6.8 a 20.
Y luego ven los
paréntesis cerrarse.
Cierro el menos.
Cierro la estrella.
Y ahora pongamos otro operando.
Verán que el editor de Lisp
está indentando a la derecha
de la posición automáticamente
para ayudarme a dar seguimiento.
Lo haré de nuevo.
Cerraré ese último
paréntesis de nuevo.
Verán que balancea el más.
Ahora puedo preguntar,
¿cuál es el valor de eso?
Así que esas dos cosas,
indentar a la derecha, que se conoce
como impresión bonita,
y remarcar paréntesis, son dos
cosas que muchos sistemas Lisp
tienen incorporadas para ayudar
a dar seguimiento.
Y deberían aprender cómo usarlos.
Bueno, esas son las primitivas.
Hay un medio de combinación.
Ahora vayamos a los medios
de abstracción.
Me gustaría poder tomar la idea
de que hago una
combinación como esta
y abstraerla y darle un
nombre simple, para que la pueda
usar como un elemento.
Y eso lo hago en Lisp con "define".
Y puedo decir,
por ejemplo, define A para que sea
el producto de 5 y 5.
Y luego puedo preguntarle a Lisp,
por ejemplo, cuál es el
producto de A y A.
Y esto debería ser 25,
y esto otro debería ser 625.
Y luego, algo crucial,
puedo usar ahora A--
aquí lo usé como una combinación--
pero puedo usarlo en cosas
más complicadas que puedo
nombrar también.
Así que puedo decir, define B para
que sea la suma de, digamos, A y
el producto de 5 y A.
Y luego cierro el más.
Miremos esto en la computadora y
observemos cómo se ve.
Solo tipearé lo que escribí
en el pizarrón.
Puedo decir, define A como
el producto de 5 y 5.
Y contarle eso a a Lisp.
Y noten que Lisp
respondió ahí con
una A debajo.
En general, cuando tipeas
una definición en Lisp,
éste responde con el símbolo
que se está definiendo.
Ahora podría preguntarle a Lisp
cuál es el producto de A y A.
Y dice que es 625.
Puedo definir B como la suma
de A y el producto de 5 y A.
Cierro el paréntesis de la estrella.
Cierro el más.
Cierro el "define". Lisp dice, OK,
B, ahí debajo.
Y ahora puedo preguntarle a Lisp
el valor de B.
O puedo pedirle algo más complicado,
como cuál es
la suma de A y el cociente entre B y 5.
Esa barra es dividir, otro
operador primitivo.
Dividí B por 5 y se lo sumé a A.
Lisp dice,
OK, eso es 55.
Así que así es que cómo se ve.
Ahí está el medio básico
para definir algo.
Es la manera más simple de nombrar,
pero no es realmente
muy poderoso.
Verán, lo que en verdad
quisiera nombrar --
recuerden que estamos hablando
de métodos generales --
Me gustaría nombrar la idea general de,
por ejemplo, multiplicar 5 por 5,
o 6 por 6, o 1001
por 1001, o 1001.7 por 1001.7.
Me gustaría poder nombrar
la idea general de
multiplicar algo por sí mismo.
Bueno, ustedes saben qué es.
Se llama elevar al cuadrado.
Y la forma en que puedo
hacerlo en Lisp es definir
"square" de algo X como
multiplicar X por sí mismo.
Y al hacer eso, puedo
preguntarle a Lisp, por ejemplo,
cuánto es 10 al cuadrado.
Y Lisp dirá 100.
Ahora miremos esto
un poco más de cerca.
Aquí está la definición de "square".
Para elevar algo al cuadrado,
multiplicarlo por sí mismo.
Ven esta X aquí.
Es algo así como un pronombre,
algo a lo que
voy a elevar al cuadrado.
Y lo que hago con él es
multiplico X,
lo multiplico por sí mismo.
OK.
Esa es la notación para definir
un procedimiento.
De hecho, esto es un poco confuso,
porque es
algo así a cómo usaría "square".
Y digo "square" de X,
o "square" de 10, pero
no estoy dejando muy en claro
que estoy en efecto nombrando algo.
Así que déjenme escribir esta
definición de otra forma
que deja un poco más claro
que estoy nombrando algo.
Diré, "define square" como
lambda de x , multiplicar X por X.
Aquí estoy nombrando algo como "square",
de la misma manera que aquí
estoy nombrando algo A. Pero aquello a
lo que estoy llamando "square"--
Aquí, lo que nombro A
es el valor de esta combinación.
Aquí, lo que estoy llamando "square"
es esta cosa que
comienza con un lambda, y
lambda es la forma de Lisp de decir
"haz un procedimiento".
Miremos esto más de cerca
en la diapositiva.
La manera en leo esta definición es
defino "square" como
un procedimiento --
eso es lo que la lambda es--
Haz un procedimiento
con un argumento llamado X.
Y lo hace es retorna el resultado de
multiplicar X por sí mismo.
Ahora bien, en general,
vamos a usar esta anterior forma
de definir, solamente porque
es un poco más conveniente.
Pero no pierdan de vista el hecho
que en realidad es esto.
De hecho, en lo que al intérprete
de Lisp respecta,
no hay diferencia entre tipear esto
o tipear esto otro.
Y hay una palabra para eso,
azúcar sintáctico.
Lo que azúcar sintáctico significa,
es tener formas más
convenientes para escribir algo.
Así que esto es en realidad esto es
azúcar sintáctico para
esta cosa griega con la lambda.
Y la razón por la que deben recordar
esto es que no se olviden que,
al escribir algo así,
estoy realmente nombrando algo.
Estoy nombrando algo como "square",
y ese algo que estoy
nombrando como "square" es un
procedimiento que se está construyendo.
Miremos eso en la computadora también.
Así que diré, "define square" de
X como multiplicar X por X.
Ahora digámosle eso a Lisp.
Dice "square". Ven, he nombrado algo
como "square". Ahora,
habiendo hecho esto,
le puedo preguntar a Lisp cuál es
"square" de 1001?
O , en general, podría decir,
¿cuánto es elevar al cuadrado la suma de
de 5 y de 7?
Eso es elevar al cuadrado 12, 144.
O puedo usar "square" en sí mismo
como un elemento en alguna
combinación.
Puedo preguntar,
¿cuál es la suma del "square" de 3 y
el "square"de 4?
9 más 16 es 25.
O puedo usar "square" como un elemento
en una cosa mucho más
complicada.
Puedo preguntar, ¿cuál es el "square" del
"square" del
"square" de 1001?
Y eso elevar al cuadrado
el cuadrado del cuadrado de 1001.
O puedo preguntarle a Lisp
¿qué es "square"?
¿Cuál es el valor de eso?
Y Lisp retorna una manera
convencional para decirme
que eso es un procedimiento.
Dice, "procedimiento compuesto square".
Recuerden que el valor de
"square" es este procedimiento,
y las estrellas
y los corchetes es la forma
convencional de Lisp
para describir eso.
Ahora veamos dos
ejemplos más de definición.
Aquí hay dos procedimientos más.
Defino el promedio de X e Y
como la suma de X y de Y
dividido por 2.
O teniendo el promedio
y el cuadrado medio, teniendo el promedio
y el cuadrado, puedo usarlos para definir
el "mean square" o cuadrado medio de
algo, que es el promedio
del cuadrado de X y el
cuadrado de Y.
Así que por ejemplo, habiendo hecho eso,
podría preguntar cuál es
el "mean square" de 2 y 3?
Y debería obtener el promedio
de 4 y 9, que es 6.5.
Lo clave aquí es que, al haber
definido "square", puedo
usarlo como si fuera una primitiva.
Así que si miramos en
la diapositiva, si miro a
"mean square", la persona que define
el cuadrado medio no tiene que
saber, en este punto, si "square"
vino incorporado
en el lenguaje o si fue
un procedimiento que fue definido.
Y eso es algo clave en Lisp,
que uno no hace
distinciones arbitrarias entre
cosas que resultan que son
primitivas del lenguaje
y cosas que
resultan que viene incorporadas.
Una persona usándolo
ni siquiera debería tener que saberlo.
Así que las que cosas que construimos
son usada con todo el poder
y la flexibilidad
a que si fueran primitivas.
De hecho, podemos asentar esto
mirando en la
computadora una vez más.
Ya hablamos del "plus".
Y de hecho, si vengo aquí en la
pantalla de la computadora y pregunto
cuál es el valor de "plus".
Noten lo que escribe Lisp.
Aquí debajo, escribió
"procedimiento compuesto
plus". Porque en este sistema,
resulta que el
operador de adición es en sí mismo
un procedimiento compuesto.
Y si no hubiera tipeado esto,
ustedes nunca lo hubieran sabido, y
de cualquier manera no habría
marcado la diferencia.
No nos interesa.
Está por debajo del nivel de
abstracción
con el que estamos lidiando.
Así que la clave es que uno no puede
determinar, no debería ser capaz
de determinar, en general, la diferencia
entre cosas que
están incorporadas y
cosas que son compuestas.
¿Por qué es esto?
Porque las cosas compuestas
tienen una abstracción
alrededor de ellas.
Ya hemos visto casi todos los
elementos de Lisp.
Solo queda una cosa más que tenemos
que mirar, y eso cómo
hacer un análisis de casos.
Déjenme mostrarles lo que quiero decir.
Querríamos pensar acerca de la
definición matemática del
de la función de valor absoluto.
Podría decir que el valor absoluto
de X es al función que tiene la
propiedad que es el negativo de X
para X menor a cero. Cero si X es igual a cero.
Y es X para X mayor a cero.
Y Lisp tiene una forma de hacer
análisis de casos.
Déjenme definirles el valor absoluto.
Defino el valor absoluto de X
como un condicional.
Esto significa análisis de casos, COND.
Si X es menor a 0,
la respuesta es negar X.
Lo que escribí aquí es una cláusula.
Toda esta cosa
es una cláusula condicional,
y tiene dos partes.
Esta parte es el
predicado de la condición.
Eso es una condición.
Y la condición se expresa
con algo llamado
predicato. Y un predicado en Lisp
es una cosa
que devuelve o verdadero o falso.
Y puede ver que Lisp tiene un
procedimiento primitivo,
"less-than", menor que,
que prueba si algo es verdadero o falso.
Y la parte de la cláusula es
un acción o algo para hacer
en el caso en el que eso
sea verdadero.
Y aquí, lo que estoy
haciendo es negar X.
El operador de negación,
el símbolo menos en Lisp,
es un poco gracioso.
Si hay dos o más argumentos, si hay dos
argumentos, le resta el segundo al primero, y
ya vimos eso.
Y si hay un único argumento, lo niega.
Así que eso se corresponde con aquello.
Y luego hay otra cláusula COND.
Dice que en el caso
en que X es igual a cero,
la respuesta es cero.
Y en el caso donde X es mayor a cero,
la respuesta es X.
Cierro la cláusula.
Cierro el COND.
Cierro la definición.
Y esa es la definición
de valor absoluto.
Y verán que el análisis de casos
es muy parecido
al análisis de casos
que usan en matemáticas.
Hay una manera algo diferente
de escribir un caso de
análisis restringido.
A menudo, uno tiene un caso de
análisis donde hay un único
caso, donde pruebas una condición,
y luego, dependiendo de
si es verdadero o falso, haces algo.
Y hay otra definición
de valor absoluto que es
muy parecida y que dice que
si X es menor a cero, entonces
el resultado es el negado de x.
En otro caso, la respuesta es X.
Y usaremos el "IF" un montón.
Pero de nuevo, lo que hay que
recordar es que esta form
de valor absoluto que están mirando
aquí, y esta otra
aquí que escribí en el pizarrón, son
esencialmente lo mismo.
Y "IF" y "COND" son--
Bueno, de la manera que quieran.
Pueden pensar en "COND"
como azúcar sintáctico para "IF", o
pueden pensar en "IF"
como azúcar sintáctico para "COND", y
no marca la diferencia.
La persona que implemente un
sistema Lisp, elegirá una de las dos
e implementará la otra
en términos del elegido.
Y no importa cuál elijas.
¿Por qué no nos tomamos un descanso?
Y luego respondemos algunas preguntas.
¿Cómo es que a veces cuando escribo
"define", abro un
paréntesis aquí y digo, "define"
abro paréntesis algo u otra cosa,
y a veces cuando escribo esto,
no abro paréntesis?
La respuesta es que esta forma
particular de "define", donde uno
dice "define" alguna expresión es
una cosa muy especial para
definir procedimientos.
Pero de nuevo, lo que realmente
significa es que estoy definiendo este
símbolo, "square", como eso.
Así que la manera en que deberían pensar
en eso es que lo que hace "define"
es uno escribe "define" y la segunda
cosa que escribe es e
símbolo aquí -- sin paréntesis--
el símbolo que uno está definiendo
y qué uno esta definiendo que sea.
Como aquí y aquí.
Esa es la manera básica de
usar "define". Y luego,
hay una truco sintáctico especial
que le permite a uno
definir un procedimiento que se ve así.
Así que la diferencia es si uno
está o no definiendo
un procedimiento.
Bueno, créanlo o no,
ya saben suficiente Lisp
para esencialmente escribir
cualquier procedimento numérico
que escribirían es un lenguaje como
FORTRAN o Basic o lo que sea,
o esencialmente, cualquier
otro lenguaje.
Y probablemente digan que
eso no es creíble porque
saben que esos lenguajes
tiene cosas como "for"
o sentencias como "do until while"
o algo así.
Pero en realidad no necesitamos
nada de eso.
De hecho, no usaremos
nada de eso
en este curso.
Déjenme mostrarles.
De nuevo, mirando a la raíz cuadrada,
volvamos al
algoritmo de raíz cuadrada de
Herón de Alejandría.
Recuerden lo que decía.
Decía, para hallar una
aproximación de la raíz
cuadrada de X, hacer una estimación
y mejorar esa estimación
promediándola con X sobre la estimación.
Se sigue mejorándola hasta que la
estimación sea lo suficientemente buena.
Ya aludí a la idea.
La idea es que si
la estimación inicial que uno hizo
fuera igual a la raíz cuadrada de X,
entonces G aquí
sería igual a X/G.
Así que si uno alcanza
la raíz cuadrada, promediarla
no cambiaría nada.
Si la G que uno elige es más grande
que la raíz cuadrada de
X, entonces X/G será menor que
la raíz cuadrada de X, así que
cuando uno promedie G y X/G, obtendrá
algo en el medio.
Así que si uno elige un G
que es muy pequeño,
la respuesta será muy grande.
Si uno elige un G que es muy grande,
si el G de uno es más grande
que la raíz cuadrada de X y
X/G será menor que
la raíz cuadrada de X.
Así que promediar siempre
de algo en el medio.
Y luego, no es trivial,
pero es posible
mostrar que, de hecho, si G es ligeramente
distinto a la raíz cuadrada de X,
el promedio de G y X/G seguirá
acercándose a la raíz cuadrada de X.
Así que si uno sigue
haciendo esto lo suficiente,
eventualmente estará
tan cerca como quiera.
Y luego está el otro hecho de que
uno siempre puede empezar este
proceso usando un 1 como
estimación inicial.
Y siempre convergerá
a la raíz cuadrada de X. Así
que ese es el método de promedios sucesivos
de Herón de Alejandría.
Escribámoslo en Lisp.
Bueno, la idea central es:
¿qué significa hacer una
estimación de la raíz cuadrada de X?
Escribamos eso.
Diremos, "define" para probar
una estimación de la raíz cuadrada de X.
¿Qué hacemos?
Diremos, si la estimación es lo
suficientemente buena para
la raíz cuadrada de X, entonces,
como respuesta,
tomaremos la estimación.
En otro caso, intentaremos
mejorar la estimación.
Mejoraremos la estimación
para la raíz cuadrada de X y
la probaremos como una estimación
para la raíz cuadrada de X. Cierro
el "TRY". Cierro el "IF".
Cierro el "define". Así que así
es como probamos una estimación.
Y luego, la otra parte del proceso
dice que, para
computar las raíces cuadradas, diremos
"define" para computar las
raíces cuadradas de X, probaremos
1 como una estimación de la raíz
cuadrada de X. Bueno,
tenemos que definir un par de cosas más.
Tenemos que decir cómo es una estimación
lo suficientemente buena.
Y cómo mejoramos esa estimación.
Miremos eso.
El algoritmo para mejorar la estimación
de la raíz cuadrada de
X, promediamos--
ese era el algoritmo--
promediamos la estimación con el
cociente de
dividir X por la estimación.
Así es como mejoramos una estimación.
Y para determinar si una estimación
es lo suficientemente buena, bueno,
tenemos que dedicir algo.
Esto se supone que es una estimación
de la raíz cuadrada de X, así
que una posible cosa que pueden hacer
es preguntar si al tomar
la estimación y elevarla al cuadrado
se obtiene algo muy cercano a X.
Una forma de decir eso es decir
elevo al cuadrado la estimación,
le resto X a eso y veo
si el valor absoluto
de toda esa cosa es menor que algún
número pequeño, que depende
de mi propósito.
Así que ese es un procedimento
completo para cómo computar
la raíz cuadrada de X.
Veamos la estructura de eso
un poco.
Tengo toda la cosa.
Tengo la noción de cómo computar
la raíz cuadrada.
Es una especie de módulo.
Es una especie de caja negra.
Está definido en términos de cómo
probar una estimación para la raíz
cuadrada de X.
"TRY" está definido en términos de,
bueno, poder determinar
si algo es lo
suficientemente bueno y decir
cómo mejorar algo.
Lo suficientemente bueno.
"TRY" está definido en términos de
"GOOD-ENOUGH" e "IMPROVE".
Y vemos que más puedo completar.
Bueno, bajaré por este árbol.
"GOOD-ENOUGH"
está definido en términos del
valor absoluto y de "SQUARE"".
E "IMPROVE" está definido en términos de
algo llamado
promedio y
luego otro operador primitivo.
La raíz cuadrada está definida en
términos de "TRY". "TRY" está
definido en términos de "GOOD-ENOUGH"
e "IMPROVE",
pero también
en términos del mismo "TRY".
Así que "TRY" está definido en términos
de "TRY" en sí mismo.
Bueno, eso podría darles algunos
problemas. Su profesor de geometría
de secundario probablemente les dijo
que está mal definir ir y
definir cosas en términos
de sí mismos, porque
no tiene sentido.
Pero eso es falso.
A veces tiene perfecto sentido
definir cosas en
términos de ellas mismas.
Y este es el caso.
Y podemos mirar eso.
Podemos escribir lo que esto significa
y decir, supongan que
le pregunto a Lisp
qué es la raíz cuadrada de 2.
¿Qué significa la raíz
cuadrada de 2?
Bueno, eso significa que pruebo con 1
como una estimación
para la raíz cuadrada de 2.
Y ahora miro.
Pregunto si 1 es una estimación
lo suficientemente buena
para la raíz cuadrada de 2.
Y eso depende de la prueba
que hace "GOOD-ENOUGH".
Y en este caso, "GOOD-ENOUGH" dice
que no, que 1 no es
una estimación lo suficientemente buena
de la raíz cuadrada de 2.
Y eso se reduce en decir,
tengo que probar una mejora--
mejorar 1 como estimación para la
raíz cuadrada de 2, y probar eso
como una estimación de la
raíz cuadrada de 2.
Mejorar 1 como una estimación
de la raíz cuadrada de 2 significa que
promedio 1 y 2 dividido 1.
Así que está será un promedio.
Esta cosa de aquí será el promedio
de 1 y del
cociente entre 2 y 1.
Es esta pieza de aquí.
Y eso es 1.5.
Así que la raíz cuadrada de 2
se reduce a probar 1 para
la raíz cuadrada 2, que se reduce
a probar 1.5 como la
estimación para la raíz cuadrada de 2.
Así que eso tiene sentido.
Miremos el resto del proceso.
Si probarmos 1.5, eso reduce.
1.5 resulta que no es una estimación
lo suficientemente buena para
la raíz cuadrada de 2.
Y eso reduce en probar el promedio
de 1.5 y 2 dividido por
1.5 como estimación para
la raíz cuadrada de 2.
Y ese promedio resulta ser 1.333.
Así que toda esta cosa reduce
en probar 1.333 como una estimación
de la raíz cuadrada de 2.
Y luego seguimos así.
Eso reduce a otro llamado
a "GOOD-ENOUGH", 1.4
algo u otro.
Y sigo así hasta que el proceso
finalmente se detiene con
algo que es lo suficientemente bueno,
cree que es lo suficientemente bueno, que
en este caso, es 1.4142, algo u otro.
Así que el proceso
tiene perfecto sentido.
Esto se llama, por cierto,
una definición recursiva.
Y la habilidad de poder hacer
definiciones recursivas es
una fuente de increíble poder.
Y como pueden ver que di la pista,
es la cosa
que efectivamente nos permite
hacer estos cómputos infinitos
que continúan hasta que algo
se hace verdadero, sin tener otra
restricción más que la posibilidad
de llamar a un procedimiento.
Bueno, veamos, hay una cosa más.
Déjenme mostrarles una variante
de la definición de raíz cuadrada
aquí en la diapositiva.
Es casi la misma cosa.
Lo que hemos hecho es
empaquetar las definiciones de
"IMPROVE", "GOOD-ENOUGH" y "TRY"
dentro de "SQUARE-
ROOT". Así que, de hecho, lo que hice fue
construir una
caja de raíz cuadrada.
Así que construí una caja
que el procedimiento de raíz cuadrada
que alguien puede usar.
Podrían poner 36 y saldría un 6.
Y luego, empaquetados dentro de esta caja,
están las definiciones de
"TRY", "GOOD-ENOUGH" e "IMPROVE",
Están escondidas dentro
de la caja.
Y la razón para hacer eso
es que si, si alguien está usando
la raíz cuadrada, si George está
usando la raíz cuadrada, a George
probablemente no le interese que
cuando implementé
la raíz cuadrada, tenía cosa dentro
llamadas "TRY" y
"GOOD-ENOUGH" e "IMPROVE".
Y, de hecho, Harry podría tener
un procedimiento de raíz cúbica
que tiene "TRY" y "GOOD-ENOUGH" e
"IMPROVE". Y para no confundir
a todo el sistema,
sería bueno que Harry
empaquetara los procedimientos
internos dentro de su procedimiento
de raíz cúbica.
Bueno, esto se llama estructura
de bloque, esta forma particular
de empaquetar las entrañas dentro
de la definición.
Volvamos y miremos la diapositiva
de nuevo.
La manera de leer esta especie
de procedimiento es decir, para definir
la raíz cuadrada, bueno, dentro
de la definición tengo la
definición de "IMPROVE" y la
definción de "GOOD-
ENOUGH" y la definición de "TRY".
Y luego, sujeto a
esas definiciones, la manera de hacer
la raíz cuadrada es probar con 1.
Y noten que aquí no tengo que decir que
1 es una estimación para la
raíz cuadrada de X, porque como
todo está dentro de
raíz cuadrada, casi que tiene
este X conocido.
Déjenme resumir.
Empezamos con la idea
de que lo vamos a estar
haciendo es expresar
conocimiento imperativo.
Y de hecho, aquí hay una diapositiva
que resume la manera en que
miramos en Lisp.
Empezamos mirando algunos
elementos primitivos en
la adición y la multiplicación,
algunos predicados para probar
si algo es menor o igual que otra cosa.
Y de hecho, vimos que en el sistema que
estamos usando, estas ni siquiera son
en efecto primitivas, pero
que no importa.
Lo que importa es que vamos
a usarlas como si fueran
primitivas.
No vamos a mirar adentro.
También tenemos algunos datos
primitivos y algunos números.
Vimos algunos medios de
composición, medios de
combianción, siendo el básico
la composición de funciones y
la construcción de combinaciones
con operadores y operandos.
Y luego hay otras cosas,
como "COND" e "IF" y
"DEFINE". Pero lo principal de
"DEFINE" en particular,
era que un medio de abstracción.
Era la forma en la que nombramos cosas.
También pueden ver de esta
diapositiva que no sólo dónde
hemos estado, sino los agujeros
que tenemos que llenar.
En algún punto, tenemos que
hablar acerca de cómo combinar
datos primitivos para obtener
datos compuestos y cómo abstraer
datos para poder usar grandes
pedazos de datos como
si fueran primitivos.
Así que ahí es hacia donde vamos.
Pero antes de hacer eso, por
el próximo par de clases, vamos
a estar hablando, en primer lugar,
cómo es que uno
enlaza estos procedimiento
que escribimos y los procesos
que ocurren dentro de la máquina.
Y luego, cómo es que uno puede
empezar a usa el poder de Lisp
para hablar no sólo acerca
estos pequeños cómputos
individuales, sino también acerca
de métodos de convención general
para hacer cosas.
OK. ¿Hay alguna pregunta?
AUDIENCIA: Sí.
Si definimos A usando paréntesis
en vez de como lo
hicimos, ¿cuál sería la diferencia?
PROFESOR: Si escribo esto,
si escribo aquello, lo que estaría
haciendo es definir un procedimiento
llamado A. En este caso, un
procedimiento sin argumentos,
que, cuando lo corra, me
devolverá 5 multiplicado por 5.
AUDIENCIA: Bien.
Quiero decir, obtienes el mismo
resultado, excepto que para uno
realmente tiene diferentes--
PROFESOR: Correcto.
Y la diferencia sería, en el viejo --
Déjenme ser un poco más claro aquí.
Llamemos a esto A, como aquí.
Y pretendan que aquí, solo para
contrastar, defino D como
el producto de 5 y 5.
Y la diferencia entre ambos,
pensemos acerca de
interacciones con el
intérprete de Lisp.
Podría tipear A y Lisp devolvería 25.
Podría tipear D, y si solo tipeo D,
Lisp retornaría un
procedimiento compuesto D,
porque eso es lo que es.
Es un procedimiento.
Podría correr D. Podría decir,
¿cuál es el valor de correr D?
Esta es una combinación sin operandos.
Veo que no hay operandos.
No puse ninguno después de D.
O podría decir, sólo por completitud,
si tipeara,
¿cuál es el valor de correr A?
Y obtendría un error.
El error sería el mismo que allí.
El error diría, lo siento, 25,
que es el valor de
A, no es un operador
que pueda aplicar a algo.
Benvenuti a questo corso di "scienza computazionale".
A dire il vero, questo è un inizio terribile. "Scienza computazionale" è un nome terribile per quello di cui parleremo.
Innanzitutto, non è una scienza.
Potremmo parlare di ingegneria o di arte.
Ma vedremo che la cosiddetta scienza computazionale ha molto in comune con la magia.
È quello di cui ci occuperemo in questo corso.
Quindi non è una scienza e non riguarda nemmeno tanto i computer.
E non si occupa di computer come la fisica non si occupa di accelleratori di particelle.
O come la biologia non si occupa di microscopi e piastre di Petri.
Non si occupa di computer allo stesso modo in cui la geometria
non si occupa proprio di strumenti di rilevamento.
Gostaria de lhes dar as boas vindas ao
curso de Ciência da Computação.
Na verdade, esta é um forma terrível de se começar.
Ciência da Computação é um nome horrível para este negócio.
Primeiramente, nao é uma ciência.
Poderia ser engenharia,
ou poderia ser arte.
Mas, nós, na verdade, percebemos que a assim chamada ciência da computação tem, na realidade, muito em comum com mágica.
Nos vamos ver isso neste curso.
Então, não é uma ciência. Também não é muito realmente sobre computadores.
E também não é sobre computadores, da mesma forma que Física não é realmente sobre aceleradores de partículas.
E Biologia não é realmente sobre microscópios e placas de Petri.
E não é sobre computadores no mesmo sentido em que geometria
não é realmente sobre usar instrumentos de pesquisa.
Na verdade, há muito em comum entre Ciência da Computação e Geometria.
Para começar, Geometria é outra matéria com um nome inadequado.
O nome vem de "gaia", que significa "a Terra", e "metron", que significa medir.
Geometria originalmente significava medir a Terra, ou investigar.
E a razão disso é que, milhares de anos atrás,
os sacerdotes egípcios desenvolveram os rudimentos da Geometria
de modo a descobrir como restaurar os limites dos campos
que eram destruídos na enchente anual do rio Nilo.
E para os egípcios que faziam isso, Geometria realmente era
o uso de instrumentos de pesquisa.
Agora, o mitov pelo qual nós achamos que Ciência da Computação é sobre computadores
tem muito a ver com a mesma razão pela qual os egípcios pensavam que
Geometria era sobre topografia.
Isto é, quando algum campo de pesquisa está começando
e você não o entende muito bem
é muito fácil confundir a essência do que você está fazendo
com as ferramentas que você usa.
E realmente, sobre algumas medidas absolutas das coisas
nós provavelmente sabemos menos sobre a essência da Ciência da Computação
que os antigos egípcios realmente sabiam sobre Geometria.
O que eu quero dizer com essência da Ciência da Computação?
O que eu quero dizer com essência da Geometria?
Vejam, certamente é verdade que esses egípcios WENT OFF e usaram
instrumentos de topografia, mas quando nós olhamos para eles
após dois mil anos, nós dizemos
o que ele estavam fazendo, a coisa importante que eles estavam fazendo
foi começar a formalizar noções sobre espaço e tempo.
Começar uma maneira de falar sobre verdades matemáticas formalmente
que levaram ao método axiomático que levou, de alguma forma, a
todo o método da matemática moderna
Descobrindo uma maneira de falar de forma precisa do assim chamado
conhecimento declarativo - o que é verdade.
Bem, da mesma forma, penso que no futuro as pessoas vão olhar para trás
e dizer, sim, esses primitivos no século XX estavam
mexendo com essas máquinas chamadas computadores,
mas, na verdade, o que eles estavam fazendo foi começar a aprender como
formalizar intuições sobre processo - como fazer coisas.
Começando a desenvolver uma maneira de falar de forma precisa sobre
"como conhecer" de forma oposta à Geometria,
que fala sobre "o que é verdade."
Deixe-me lhes dar um exemplo disso.
Eis aqui um trabalho de Matemática que diz o que é
uma raiz quadrada.
A raiz quadrada de x é o número y que
levado ao quadrado é igual à x, sendo y maior que zero.
Agora essa é uma boa peça da Matemática, mas
apenas dizer a vocês o que é uma raiz quadrada
não diz realmente nada sobre como vocês
poderiam ir e encontrar uma
Então vamos contrastar que com uma peça de conhecimento imperativo
como você poderia ir e encontrar uma raiz quadrada.
Isso de fato vem do Egito. Não o antigo, antigo
Egito. Esse é um algoritmo de Heron da Alexandria
chamado "Como encontrar uma raiz quadrada
por desvio quadrado médio".
Mas o que isso diz é, para encontrar uma raiz quadrada
você dá um palpite
você melhora esse palpite
e a forma de melhorar o palpite
é ..... o palpite e x sobre o palpite
e mais tarde nós vamos falar um pouco sobre por que
isso é uma coisa razoável
e você continua a melhorar o palpite até que esteja bom.
Mas esse é um método.
É sobre como fazer algo, em vez do conhecimento
declarativo que diz que o que você está procurando.
É um processo.
Bem, o que é um processo em geral?
É meio difícil dizer.
Pode-se pensar nisso como um espírito mágico
que meio que vive no computador e faz algo.
A coisa que dirreciona o processo é um padrão de regras
chamado um prodecimento.
Portanto, procedimento são os feitiços, se vocês preferirem
que controlam esses espíritos mágicos que são os processos.
Bem, eu acho que vocês sabem que todos precisam de uma linguagem mágica
e os bruxos, bruxos verdadeiros, usam antigas
acadiana ou suméria ou babilônica ou ou qualquer outra.
Nós vamos conjurar nossos espíritos numa linguagem mágica
chamada LISP.
Que é a linguagem feita para falar sobre,
para lançar os feitiços que são os procedimentos
para conduzir os processos.
Agora é muito fácil aprender LISP.
Na verdade, em poucos minutos eu vou ensinar a vocês
basicamente tudo sobre a linguagem LISP.
Vou ensinar a vocês basicamente todas as regras.
E vocês não deveriam achar isso particularmente surpreendente.
É mais ou menos como dizer
que é muito fácil aprender as regras do xadrez.
E na verade, em poucos minutos você pode ensinar
a alguém as regras do xadrez.
Mas, é claro, isso é bem diferente de se dizer
que você entende as implicações dessas regras
e como usá-las para se tornar
um mestre no xadrez.
Bem, LISP é a mesma coisa.
Vamos enumerar as regras daqui a poucos minutos
e será bem fácil de ver.
Mas o que vai ser realmente difícil é perceber
as implicações dessas regras - como explorar
essas regras para ser um mestre programador.
E as implicações dessas regras vão
nos levar a, bem, a todo o resto da matéria
e, é claro, muito além.
OK. Então na Ciência da Computação nós estamos tratando
de formalizar o "como" do conhecimento imperativo.
Como fazer coisas.
E as questões verdadeiras da Ciência da Computação não são, é claro,
dizer às pessoas como extrair raiz quadradas.
Porque se isso fosse tudo, não haveria problema nenhum aí.
Os verdadeiros problemas surgem quando tentamos construir
sistemas muito muito grandes.
Programas de computador que possuem milhares de páginas.
Tão longos que ninguém pode realmente tê-los em suas
cabeças de uma vez só.
E a única razão pela qual isso é possível é
porque há ténicas
que são técnicas para controlar
a complexidade desses sistemas enormes.
E essas técnicas para controlar
a complexidade são o assunto deste curso.
E em algum aspecto, isso é, na verdade, o objeto
da Ciência da Computação.
Bem, isso pode parecer algo bem estranho de se dizer
porque, no final, um monte de gente além dos cientistas
da computação lidam com o controle da complexidade.
Um grande companhia aérea é um sistema extremamente complexo
e os engenheiros aeronáuticos que projetaram
isso estão lidando com uma imensa complexidade.
Mas existe uma diferença entre esse tipo de complexidade
e aquela com a qual lidamos na Ciência da Computação.
E a diferença está no fato de que a Ciência da computação, de alguma forma,
não é real.
Vejam bem, quando um engenheiro está projetando
um sistema físico que é feito de partes reais,
os engenheiros não se preocupam como
lidar com problemas de tolerância e
aproximação e barulho no sistema.
Então, por exemplo, sendo um engenheiro elétrico
eu posso sair e facilmente construir um amplificador de ONE STAGE
ou um aplificador de BIVOLT? e eu posso imaginar
sobrepondo vários deles para construir
um amplificador de MILLION STAGE
no entanto, seria ridículo construir algo assim
porque bem antes do MILLONTH STAGE
o barulho termal nesses componentes
WAY no começo vai
amplificar e fazer a coisa toda ficar sem sentido.
A Ciência da Computação lida com componentes idealizados.
Nós sabemos tanto quanto queremos sobre essas
pequenas peças de programas e de dados que nós estamos encaixando.
Portanto, nós não temos de nos preocupar com tolerância,
e isso significa que, ao construir um programa grande,
não existe tanta diferença assim entre
o que eu posso construir e o que posso imaginar.
Porque as partes são essas entidades abstratas
que eu conheço tanto quanto quero.
Eu sei sobre elas precisamente o tanto que eu quiser.
Assim, em oposição a outros tipos de engenharia
em que os limites/restrições/obstáculos on WHICH pode-se construir
são os obstáculos dos sistemas físicos --
os obstáculos da física e barulho e aproximação -
os obstáculos impostos ao se construir grandes sistemas de software
são as limitações de nossas mentes.
Portanto, nesse sentido, a Ciência da Computação é como
uma forma abstrata de engenharia.
É o tipo de engenharia na qual se ignora
os limites que são impostos pela realidade.
OK. Bem, quais são algumas dessas técnicas?
Elas não são privativas da Ciência da Computação.
A primeira técnica, que é usada em toda a engenharia,
é um tipo de abstração chamado "Abstração da caixa preta".
Tome algo e construa uma caixa sobre isso.
Por exemplo, nós vimos o método da raiz quadrada.
Eu poderia pegar isso e construir uma caixa.
Dize-se "Encontrar a raiz quadrada de x."
E isso deveria ser todo um conjunto complicado de regras,
e deveria terminar sendo o tipo de coisa
em que se coloca dentro, digamos, 36, e dizer
"Qual é a raiz quadrada de 36?" e sai 6.
E o importante é que eu gostaria de DESIGN que
de modo que se George chegar e desejar computar
a raiz quadrada de a mais a raiz quadrada de b
ele pode pegar essa coisa e usar como um módulo
sem ter de olhar dentro
e construir algo que se pareça com isso:
deveria ser um a e um b e uma caixa de raiz quadrada
e outra caixa de raiz quadrada
e então algo que some.
E isso deveria dar a resposta.
E pode-se ver que somente do fato de que
eu quero fazer isso ponto de vista do George
a parte interna do que está aqui
não deveria ser importante.
Assim, por exemplo, não deveria importar
quando eu escrevo isso eu disse que quero encontrar a
raiz quadrada de x. Eu poderia ter dito
a raiz quadrada de y ou a raiz quadrada de a
or qualquer coisa.
Essa é a noção fundamental de se colocar algo
numa caixa.
Usar a caixa preta da abstração para suprimir detalhe
e a razão para isso é que
você quer chegar e construir caixas maiores.
Bem, existe outra razão para fazer
caixa da preta da abstração além
de querer suprimir detalhe para construir caixas maiores.
algumas vezes você quer dizer que seu jeito
de fazer algo, seu método de "como fazer"
é uma instância de uma coisa mais geral
e você gostaria sua linguagem para ser capaz
de expressar essa generalidade.
Deixe-me lhes dar outro exemplo
ficando com a raiz quadrada.
Vamos voltar e dar mais uma olhada naquele slide
com o algoritmo da raiz quadrada nele.
Lembra o que ele diz?
Ele diz que, para fazer algo,
eu dou um palpite e eu melhoro esse palpite
e eu meio que continuo melhorando aquele palpite
assim existe uma estratégia geral de procurar
por algo e uma maneira de encontrá-lo
Eu continuo a melhorá-lo
Agora isso é um caso particular de outro
tipo de estratégia para encontrar um ponto fixo de algo
um ponto fixo de uma função é algo, é
um valor - um ponto fixo de uma função f
é um valor y tal que f de y igual a y.
E a forma que eu devo fazer isso
é começar com um palpite
e se eu quero algo que não mude
quando eu continuo aplicando f
é eu vou continuar aplicando f continuamente até
que aquele resultado não mude muito.
Então existe uma estratégia geral.
E então, por exemplo, para computar a raiz
quadrada de x, eu posso tentar encontrar
um ponto fixo da função que toma y
PARA A MÉDIA DE x sobre y.
E a ideia disso é que se eu realmente tivesse y
igual à raiz quadrada de x
então y e x sobre y seria o mesmo valor.
Eles seriam ambos a raiz quadrada de x
e, é claro, x sobre a raiz quadrada de x.
E então a média, if y fosse igual à raiz quadrada de x,
então a média não mudaria. Então a raiz quadrada
de x é como (?) um ponto fixo daquela função particular
Agora o que eu gostaria de ter, eu gostaria de expressar a
estratégia geral para encontrar pontos fixos.
Então o que eu deveria imaginar fazer é encontrar, é ser capaz
para usar minha linguagem, para definir uma caixa que dia: ponto
fixo. Da mesma forma eu poderia fazer uma caixa que diz "raiz
quadrada", e eu gostaria de ser capaz de expressar ESTA em minha
linguagem. Eu gostaria de expressar não apenas o
conhecimento imperativo de uma coisa particular
como a raiz quadrada, mas eu gostaria de ser capaz de
expressar o conhecimento imperativo de como fazer
um ponto fixo. E, de fato, vamos voltar e olhar
aquele slide novamente. Esta é uma parte do conhecimento
imperativo? Como encontrar um ponto fixo, mas
aqui no fundo existe uma nova parte do
conhecimento imperativo que diz que uma maneira de
computar raiz quadrada é aplicar esse método geral
do ponto fixo. Então, eu gostaria também de ser capaz de expressar
aquele conhecimento imperativo.
Isso significaria que "Esta caixa de ponto fixo é tal que
se eu colocar algo na entrada, a fundação que leva "y" à
média de "y" amd x sobre y e o que deveria sair
desta caixa de ponto fixo é um método para se encontrar
raízes quadradas. Então, nessas caixas que estamos construindo
você tem não apenas números de entrada e saída, nós
podemos estar construindo em caixas que, de fato, podem estar construindo
métodos computacionais de como achar raiz quadrada.
E minha opinião é que eles são funções de entrada
como y vai para a média de y e x sobre y.
E a razão pela qual nós deveríamos fazer isso, isso é um procedimento
procedimentos vão ser nosso jeito de falar
sobre conhecimento imperativo.
E a forma de transformá-lo em algo poderoso
é ser capaz de falar sobre outros tipos de
conhecimento. Então aqui está um procedimento que, de fato,
trata de outro prodecimento.
E a estragégia geral que, ela mesma, trata
de estratégias gerais. OK, bem, nosso primeiro
tópico para este curso será, ou melhor, os três maiores
tópicos serão extração de caixas-pretas. Vamos tratar
desse assunto de uma forma um pouco mais detalhada... O que nós vamos
fazer é, nós vamos .... nós vamos começar falando sobre
como a LISP é construída a partir de objetos primitivos.
Como, o que faz a linguagem SUPPLY conosco
e vamos ver que eles são prodecimentos primitivos
e dados primitivos. Então nós vamos ver como
você pega esses primitivos e os combina
de forma a fazer coisas complicadas. Essas formas
de combinação, e vamos ver que existem
formas de ordenar coisas juntas, colocando
prodecimentos primitivos para fazer mais
procedimentos complicados. E vamos ver como
colocar dados primitivos juntos para fazer dados compostos.
Então vamos dizer "Bem, tendo FEITO essas
coisas compostas, como se faz para abstrair delas?"
"Como você colocar essas caixas pretas ao redor delas
de forma que você possa usá-las como componentes em
coisas mais complexas?" E veremos que isso é feito
definindo procedimentos e técnicas para
lidar com dados compostos, chamados "dados de abstração".
E então o que deve ser a coisa mais importante
é passar de apenas regras para "Como um
expert trabalhar?" Como se expressam padrões
comuns de se fazer coisas, como dizer "Bem, existe
um método geral de FIXED-POINT e raiz quadrada
é um caso particular daquilo." E nós vamos usar
algo chamado procedimentos de alta ordem, especialmente
procedimentos cuja entrada e saída são, elas próprias,
procedimentos e então vamosobservar algo
muito interessante: à medida que avançamos mais e mais
nós vamos abstrair, bem..., a linha entre o que
consideramos dados, e o que consideramos
prodecimento vai se tornar tênue de uma forma
incrível. Tudo bem, bem, este é o nosso primeiro assunto: extração da
caixa-preta. Vamos dar uma olhada no segundo tópico: introduza
dessa forma: suponha que eu queira expressar a ideia, e
lembrem-se, estamos falando sobre ideias - eu quero
expressar a ideia de que eu posso tomar algo e
multiplicá-lo pela soma de duas outras coisas. Então, por
exemplo, se eu somar 1 com 3 e multiplicar por 2, eu
obtenho 8. Mas eu estou falando sobre a ideia geral
daquilo que se chama "combinação linear": que você
pode adicionar duas coisas e multiplicá-las por
algo mais. É muito fácil quando eu penso
sobre isso para números, mas suponham que eu também queira
usar esta mesma ideia para pensar sobre "eu posso
somar dois vetores: a1 e a2 e depois SCALE os pelo
mesmo fator "x" e conseguir um outro vetor. Or eu
deveria dizer que quero pensar sobre a1 e a2 como se esses
polinômios, e eu gostaria de somar esses dois
polinômios e depois multiplicá-los por 2 para conseguir
um mais complicado. Or a1 e a2 poderiam ser
sinais elétricos e eu gostaria de pensar como
somar esses dois sinais elétricos e então
colocar a toda coisa num amplificador e
multiplicar por, digamos, 2 ou algo assim. A
ideia é que eu quero pensar sobre a noção geral
daquilo. Agora, se minha linguagem vai ser
uma boa linguagem para expressar essas ideias gerais
de modo que eu realmente possa fazer aquilo, eu gostaria de ser capaz de
diz "eu vou multiplicar por X a soma de a1
e a2, e eu gostaria que isso expressasse a ideia
geral. De todos os diferentes tipos de coisas que a1 e a2
podem ser. Agora, se você pensar bem, existe um problema,
pois, afinal, todas as operacoes primitivas reais que
entram numa maquina vao obviamente ser diferentes
se eu estou adicionando dois números polinomiais
ou se eu estiver adicioando a representacao de dois sinais
eletricos ou formas de onda em algum lugar tem de haver
conhecimento dos tipos de varias coisa que voce pode adicionar
e as formas de adiciona-las. Agora, para construir tal sistema
a questao eh onde eu coloco aquele conhecimento, como eu
penso sobre os diferentes tipos de escolhas que tenho
e se amanhã George chegar com um novo tipo de objeto
que pode ser adicionado e multiplicado. Como é que eu adiciono
o novo objeto de George ao sistema sem estragar
tudo que já estava lá?
Esse vai ser o segundo tópico, a maneira de controlar
esse tipo de complexidade. E a maneira que se faz isso
é estabelecendo interfaces convencionais. Acordadas as
formas de colocar (CONECTAR) coisas juntas. Exatamente como na engenharia
elétrica as pessoas têm padrão IMPENDÊNCIAS para
conectores e então você sabe se você controi
algo com um desses padrões de impendências
que você pode conectar com outra coisa.
Portanto, este vai ser o nosso segundo grande tópico:
interfaces convencionais. O que nós vamos ver
é primeiramente que nós vamos falar sobre o problema das operações
genéricas, à qual eu aludi,
coisas como PLUS que têm de trabalhar com todos os tipos de dados
Nós vamos falar sobre operações genéricas
e depois vamos falar sobre SCALE STRUCTURES,
como juntarmos programas muito grandes
que modelam os tipos de sistemas complexas no mundo real que você gostaria
de modelar e o que vocês vão ver
é que existem duas metáforas muito importantes para
colocar junto tais sistemas - um é chamado de objeto orientado
de programção, onde você pensa o seu sistema
como um tipo de sociedade de pequenas coisas que interagem enviando
informação entre eles. E o segundo são
operações que agregam os chamados STREAMS streams onde você
pensa em sistemas grandes que pôem juntos tipo
como uma única engenharia de processamento pôe junto um grande
sistema elétrico.
Esse vai ser o nosso segundo tópico. Agora, a terceira
coisa que vamos abordar, a terceira técnica básica
para controlar a complexidade é construir novas linguagens,
pois, às vezes, quando você está assoberbado
pela complexidade de um design, a forma de se controlar
essa coomplixidade é escolher uma nova linguagem de design e
o objetivo de novas linguagens de design
será iluminar os diferentes aspectos do sistema.
Ela vai suprimir alguns tipos de detalhes e enfatizar
outros tipos de detalhes.
Essa vai ser a parte mais mágica do curso.
Nós vamos começar olhando efetivamente para a
a tecnologia usada na construção de novas linguagens de computador.
A primeira coisa que vamos fazer é, na verdade, construir
em LISP. Nós vamos expressar em LISP o processo de
interpretar a própria LISP. E isso vai ser um tipo VERY
de coisa autocircular. Existe um pouco de símbolo místico
que tem a ver com o que veremos que é uma ....
O processo de interpretar LISP é um tipo de roda gigante
de dois processos, aplicar e avaliar
que tipo de expressões constantemente reduzem
a cada um. Então, vamos ver todo tipo
de coisas mágicas. Eis aqui outro símbolo mágico.
Este é um tipo de operador Y, que é em algum senso
a expressão do infinito dentro de nossa linguagem procedimental
vamos dar uma olhada nisso. Esta parte do curso é
chamada de abstração metalinguistica ao falar sobre
como construímos novas linguagens
como eu disse que íamos começar a olhar
para o processo de interpretação. Nós vamos olhar
para essa volta LOOP aplicar/avaliar.
E construir LIPS e apenas para mostrar que isso é muito
geral, vamos usar exatamente a mesma tecnologia
para construir um tipo muito diferente de linguagem -
a assim chamada linguagem lógica de programção em que
não se fala realmente sobre prodecimentos de forma alguma que tenha entradas e saídas.
O que se fala é sobre as relações entre coisas
e, aí então, finalmente,
vamos falar sobre como implementar essas
coisas de forma bastante concreta no tipo mais de simples de máquinas
Vamos ver algo como
qual é a EXEMPLO/PICTURE de um chip que é o intéprete da LISP
sobre o qual vamos falar então no hardware.
Bem, ok, aqui está um esboço do curso.
Três tópicos: abstração da caixa preta,
interfaces convencionais e
abstração metalinguística.
Agora vamos para um pouco, para depois darmos início.
[MÚSICA]
Muito bem, bom, vamos na verdade começar a aprender a linguagem LISP agora.
Vamos iniciar aprendendo algo muito mais importante,
talvez a coisa mais importante de todas deste curso -
que não é a LIPS em particular, é claro,
mas um quadro geral para se pensar sobre linguagens.
Eu já me mencionei aqui que, quando alguém lhe diz que vai lhe mostrar uma linguagem,
o que você deveria dizer é "Tudo bem, o que eu gostaria que você me dissesse é, quais são os elementos primtivos?"
Com o que a linguagem vem
Então, quais são as formas que você coloca isso junto, quais são os meios de combinação
Quais são as coisas que permitem que você leve esses elementos primitivos e construa coisas maiores a partir deles.
Quais são as maneiras de se colocar coisas juntas?
E então, quais são as formas de abstração?
Como é que pegamos essas coisas complicadas, e desenhamos essas caixas ao redor delas?
Como a nominamos, de forma que possamos usá-las como elas fossem elementos primitivos
para fazer coisas ainda mais complexas, e assim em diante
Então, quando alguém lhes diz, Nossa, eu tenho uma ótima nova linguagem de computador
Você não diz: quantos caracteres são necessários para inverter a matriz?
Isto é irrelevante. O que você diz é: Como, se, as linguagens não vêm com matrizes construídas, ou com alguma outra coisa construída
Como eu poderia, então, construir aquela coisa? Quais são os meios de combinação que me permitiriam fazer isso?
E então, quais são as formas de abstração que me permitiriam, então, usar aqueles elementos para fazer coisas ainda mais complicadas?
Bem, nós vamos ver que LISP tem alguns dados primitivos, e alguns procedimentos primitivos.
De fato, vamos realmente começar. Aqui está um pedaço de um dato primitivo em LISP.
Número 3, na verade, se eu estiver sendo bem pedante, não é o número 3
é algum símbolo que representa o conceito de Platão do número 3.
Eis aqui alguns dados primitivos na linguagem LISP:
17.4, ou, na verdade, alguma representação de 17.4.
E eis aqui outro, 5.
Eis aqui outro objeto primitivo que está construído dentro da LISP, adição (+).
Na verdade, para usar o mesmo tipo de pedantismo, este é um nome para o método primitivo de adicionar coisas,
da mesma forma, este é o nome para o número 3.
Este é um nome para o conceito de Plantão de como adicionar coisas.
Certo, aqueles são alguns elementos primitivos. Eu posso colocá-los juntos.
Eu posso dizer: qual é a soma de 3 e 17.4 e 5? E a forma que eu faço isso
é dizer, vamos aplicar o operador de soma a esses três números e eu devo conseguir 25.4.
Bem, eu deveria ser capaz de perguntar Lisp qual é o valor disso, e ela me daria 25.4.
Vamos introduzir alguns nomes. Essa coisa que digitei aqui é chamada de combinação.
E uma combinação consiste em geral de aplicar um operador (então isto é um operador)
para alguns operandos (esses são os operandos).
E é claro que posso fazer coisas mais complexas.
A razão pela qual eu poderia conseguir complexidade disso é porque os operandos mesmos, em geral, podem ser combinações.
Assim, por exemplo, eu poderia dizer: qual é a soma de 3 e o produto de 5 e 6, e 8 e 2.
E eu deveria obter, vamos ver... 43, então Lisp me diz que é 43.
Formar combinações, aqui estamos procurando as maneiras básicas de combinação.
E assim, vocês veem alguma sintaxe aqui. Lisp usa o que chamamos de notação de prefixo,
o que significa que o operador está escrito à esquerda dos operados (é uma convenção apenas).
E observem que está completamente entre parênteses, e os parênteses fazem isso completamente não ambíguo.
Assim, olhando para isso, posso ver o que existe o operador, and existem 1...2...3...4 operandos.
É 3.Eu pedi a Lisp para avaliá-lo, de vocês podem ver que Lisp respondeu
embaixo, e disse, é isso mes, é 3.
Ou eu posso dizer: qual é a soma de 3, 4 e 8? Qual é aquela combinação?
میں کمپیوٹر سائنس کے اس کورس میں آپ کا استقبال چاہوں گا.
اصل میں، شروع کرنے کے لئے ایک خوفناک طریقہ ہے. کمپیوٹر سائنس اس کاروبار
کے لئے ایک خوفناک نام ہے.
سب سے پہلے، یہ ایک سائنس نہیں ہے
یہ انجینئرنگ ، یا یہ فن ہو سکتے ہیں
ہم اس کورس میں ملاحظہ کرنے کے لئے جا رہے ہیں.
لہذا یہ ایک سائنس نہیں ہے. یہ بھی واقعی کمپیوٹر کے بارے میں بہت زیادہ نہیں ہے.
اور یہ ایک ہی احساس ہے کہ فزکس ذرہ سریع کار کے بارے میں واقعی نہیں ہے میں کمپیوٹر کے بارے میں نہیں ہے.
برتن کے بارے میں واقعی میں بہت نہیں ہے.microscopes اور petri اور حیاتیات
واقعی میں بہت سروے آلات کا استعمال کرتے ہوئے کے بارے میں نہیں ہے.
اصل میں، کمپیوٹر سائنس اور جیومیٹری کے درمیان میں بہت یکساں ہے.
جیومیٹری، سب سے پہلے ایک ناقص نام کے ساتھ ایک اور موضوع ہے.
نام 'گایا،' کا مطلب ہے 'زمین' اور 'metron،' معنی 'کا طریقہ سے آتا ہے."