Understanding search queries, semantics, and "Meaning" ...aren't we all looking for meaning?

[Jonathan Gardner]

On Dec 30 2008, 3:25 pm, 5lvqbw... at sneakemail.com wrote:
> > In a typical SQL database, when you type in "SELECT foo FROM bar WHERE
> > baz='bo'", you are not writing a program, at least not in the sense of
> > Python or C or Java or Perl where you give instructions on HOW to run
> > the program. You are writing a program in the sense of Lisp or Scheme
> > or Haskell in that you are giving instructions on WHAT the program is.
>
> I've gotten a strong inkling that parsing a query yields new code,
> (lambdas) that are created on the fly to do the search.
>

More on this at the very end. Just smile to know that you're very
close.

> > course. Instead, it transforms the query (the WHAT) into a set of
> > procedures that describe HOW to get the result.
>
> For now I'm not parsing actual text queries... my real "search query"
> is coded directly in python like this:
> p1 = lambda: db.search_leaf('x location', 'lte', 5)
> p2 = lambda: db.search_leaf('footprint', 'eq', '0603')
> p3 = lambda: db.search(db.AND, p1, p2)
>
> p4 = lambda: db.search_leaf('x location', 'gte', 19)
> p5 = lambda: db.search_leaf('footprint', 'eq', '0402')
> p6 = lambda: db.search(db.AND, p1, p2)
>
> fc = db.search(db.OR, p3, p4)
>
> this particular example doesn't necessarily make any sense, but in
> effect I'm trying to string together lambda functions which are
> created explicitly for the individual query, then strung together with
> combiner functions.
>

If only compilers were so simple... Again, you're writing the "HOW"
when you're doing what you're doing above, when you really want to
write the "WHAT".

Oh, and BTW, lambdas are just an expression to generate a function
quickly. You're confusing the python lambda expression with lambdas
the theoretical concepts. Lambdas the theoretical concept are really
Python's callable objects. Python just expresses them in a very weird
way that is seemingly unrelated to lambda the theoretical concept (but
really is).

> > Oh, by the way, this step is nondeterministic. Why? Well, no one can
> > really say what the BEST way to run any sufficiently complicated
> > program is. We can point out good ways and bad ways, but not the best
> > way. It's like the travelling salesman problem in a way.
>
> The nondeterministic stuff... wow, I've come across (call/cc...),
> (require...), and different variants of this, both in sicp, teach
> yourself scheme, the plt docs, other places, etc., but it still eludes
> me.  I'm afraid that unless I understand it, I'll wind up creating
> some type of cargo-cult mimcry of a database without doing it right
> (http://en.wikipedia.org/wiki/Cargo_cult)
>

Sorry, I got confused on the meaning of non-deterministic programming.
I forgot that this was a specific thing in the Scheme world.

Yes, you've got to understand this. It makes writing a compiler much,
much easier, almost trivial.

> > programmer, will be infinitely better for it. When you understand it,
> > you will really unlock the full potential of Python and Scheme and
> > whatever other language is out there because you will see how to go
> > from HOW languages to WHAT languages.
>
> I'm under the impression python doesn't have the internal guts for
> nondeterministic programming, specifcially that its lambdas are
> limited to single-line expressions, but I may be wrong here.
>

(Recall what I mentioned about lambdas above. It applies here as
well.)

> Still, at the begining of the nondeterministic section of SICP
> (section 4.3), it says "nondeterministic computing... is useful for
> 'generate and test' applications", which almost categorically sounds
> like an element-by-element search for what you're looking for.  This
> was my initial intention behind (prematurely?) optimizing the database
> by using parameter keys instead of something like [x for x in stuff if
> pred(x, val)] filtering.
>

Yes, you certainly can't use list comprehensions to solve your
problems. They're too primitive and part of the interface is that they
actually iterate through the sequence.

> > Programmers who can write compilers are GOOD programmers. Programmers
> > who can understand someone else's compilers are even better.
>
> Does incorporating a search capability in an application necessarily
> mean I'm writing a search compiler?  That seems overkill for the
> specific case, but may be true generally.  For instance, if a word
> processing app allows you to search for characters with a certain
> font, is that incorporating a search compiler and query language?  Or
> is it just brute-force filtering?
>

Ok, here's some big picture hand-waving.

I'm going to make an assertion, and it turns out to be fundamental. I
won't explain it here but I hope you'll learn what it means as time
goes on. The assertion is this:

  All programs simply transform one program's code into another
program's code.

By program, I mean, a set of instructions to a computer of some sort
that are meant to be actually evaluated somehow. By program's code, I
mean a description in any form of such a program.

For instance, all human language is really some kind of program code.
So is all Scheme, Lisp, Python, whatever code. So is HTML. So are
bytes and words in memory representing a compiled program. So are IP
packets on the internet.

When you type in search terms to the search feature of Word, you are
writing program code. Sure, the program code is going to be
interpreted in some way, but it represents a program that says, "Find,
by whatever method available, the next instance of text matching the
text I type in here". That's a fairly easy thing to do, and you don't
need to know about relational algebra and non-deterministic code to
write a correct and fast solution.

If you're going to implement a general function that takes arbitrary
search criteria against arbitrary structured data and uses several
methods together to find the answers, that's going to require a fairly
advanced compiler and optimizer. You can use Scheme's non-
deterministic methods to build that program, which is really neat and
a big time-saver in terms of development time. That level of program
is pretty advanced and only those who really understand how to write a
compiler can put it together.

For the mouse-hovering bit, since you're always running the same
query, you can "pre-compile" it and just write a specific index and
some specific code to look it up. This isn't too difficult.