HN Explorer

Ask HN: SICP says "Program == Language Evaluator" What does this mean?

8 points by hackingsicp ↗ HN
Chapter 4, 2nd page (in my edition)

"Metalinguistic abstraction -- establishing new languages -- plays an important role in all branches of engineering design. It is particularly important to computer programming, because in programming not only can we formulate new languages but we can also implement these languages by constructing evaluators. An evaluator (or interpreter) for a programming language is a procedure that, when applied to an expression of the language, performs the actions required to evaluate that expression.

It is no exaggeration to regard this as the most fundamental idea in programming:

The evaluator, which determines the meaning of expressions in a programming language, is just another program.

To appreciate this point is to change our images of ourselves as programmers. We come to see ourselves as designers of languages, rather than only users of languages designed by others.

In fact, we can regard almost any program as the evaluator for some language."

I didn't understand that last sentence at all. The authors give some examples(a constraint propagation framework etc) from earlier chapters, which they say are languages with their own primitives etc.

But the claim seems to be more generic (emphasis mine) "we can regard almost any program as the evaluator for some language"

I am having some trouble wrapping my head around that. What "language" would a typical web app be viewed as? What are its semantics?

Let us say I have an inventory tracking web app program which deals with, say users, warehouses, orders etc. How is this "viewable as a language"? How do I go about writing an evaluator for this "language"?

Where does a program stop being "viewable as a language" If I write a small program (say to calculate Fibonacci numbers, can that be "viewed as a language"?

I am missing something very profound here. If anyone has any insights, I would be very grateful.

Help?

11 comments

[ 3.5 ms ] story [ 37.1 ms ] thread
jacquesm
The input data would be considered to be 'in' the language.

Think of the evaluator as a classic unix 'filter', the language it implements describes how the input should be formatted.

Just like when you write 'english', you expect the processor of your 'output' to be able to evaluate the english language so that it can produce meaningful output from your input.

I think it is as simple as that. But if it isn't I'm sure it won't be long before I'm corrected ;)

edited slightly for clarity (added the 'to be in' in the first sentence)

plinkplonk
"The input data would be considered the language"

really? I would have thought that the question is one of equivalence between a program (not the input) and a language (evaluator)

so i read the quoted SICP fragment to mean

input --> program --> output

and somehow an equivalent

input --> (equivalent to program) language evaluator --> output

with the "language" (that is evaluated by the evaluator) and "program" being (somehow) "points of view". This seems to posit an equivalence between a program and a language evaluator.

Not really disputing your(jacquesm's) formulation, just providing an alternative. I don't completely understand the quoted paragraph either.

I find it a little hard to think of a randomly chosen program (say the HN webapp) as a language. The inputs would be submissions, upvotes (clicks), downvotes (clicks)etc. The output would be the display page and scores etc. How is this a language processor?

Seems to be one of those "zen koan" elements of SICP, which needs a flash of insight to understand. :-)

edited for clarity,

(1) responding to jacquesm's response "input -->(equivalent to program)language evaluator" substituted for "input --> language"

(2) expanded HN web app example in terms of explicit inputs and outputs

jacquesm
the program implements the language, but is not usually written in the language that it implements.
plinkplonk
"The program implements the language, but is not usually written in the language that it implements."

I agree. Edited my formulation to make it more clear.

jacquesm
I think the problem is that the abstraction from 'program processes data' to 'program implements language' is a pretty tricky one to get your head around.

When you're using stuff like lex+yacc though you quickly realize that almost every processing that you do on structured data of some sort is actually equivalent to implementing a language.

tuukkah
Consider your example of a web app: if you implement the app following the REST principles, then the app simply evaluates a language of HTTP methods (verbs) and URIs (nouns). "GET /users" "POST /orders"...

Edit: And your program printing the Fibonacci numbers has a single verb whose semantics is to calculate and output.

harshavr
The user of the web app has a model and a desired result in mind and somehow needs to communicate this intention to the system. Viewed this way, it is clear that there must be a language in which this communication happens. Of course, we call this the interface. A user interface can be thought of as very high-level, very domain-specific language.
devijvers
1. Turing machine: there is no difference between data and instructions. Meaning: any data can be interpreted as instructions (e.g. 1 + 1, GET /, [ 1, 2, 3], ...)

2. Writing is turning ideas into meaningless symbols, reading is turning meaningless symbols into ideas.

3. The alphabet consists of meaningless symbols and meaningless sounds.

Conclusion: any sensory cues can be interpreted, given meaning, and be converted into action; also by computers.

horia314
Hello,

I don't really have as deep an understanding of this subject as I'd like, so my explanation might seem rough, but here's my two cents.

You can say a language is a set of rules. Syntactic rules describe what proper sentences in that language look like, while semantic rules describe actions associated with syntactic constructs. The most basic of languages have simple semantic rules. For each language, you can have a program, which accepts as it's input a sentence, checks if it respects the syntactic rules of that language, and then performs the actions dictated by the semantic rules. This bit is clear, I think. Starting from the other direction, if you have a program, you can invent a language, which describes what the program does (semantic) and what are proper inputs (syntactic).

Some examples are in order.

* Suppose you have a program that finds out the maximum element in a sequence of comma separated numbers. What would the language associated with this program be? Well, it's syntactic rules are simple : a proper input sentence of this program's language is a list of comma separated numbers. The semantic action associated with such a sentence would be to find the maximum of the sentence.

* For your Fibonacci example. Even a simple function/program such as this defines it's own language. What would the syntactic rules be? A proper sentence for the Fibonacci function would be a single number (let's call it n). The semantic rule associated is calculating the nth number in the series.

* Of course, no list of examples would be complete without the poster children on language - program equivalence : regular expressions and compilers. Regular expressions are written in a small language that describes a program which, when given a certain input, says weather the input matches or doesn't. The syntactic and semantic rules are more complex than in our previous examples, but are well known. As for compilers, if we bend our minds and language a little bit, we can say that GCC is a program which receives a sentence written in the C programming language (so GCC's syntactic rules are C's syntactic rules), and produces an equivalent program in machine language (so GCC's semantic rules are to produce a machine language translation of a C program).

Anyway, I hope these few examples help.

christopherdone
I don't think this is really what is meant in SICP. It's not that the function takes in inputs, it's that the program itself is a language evaluator. Consider the following program:

    (define (add-squares x y)
      (+ (* x x) (* y y)))
This is a program which evaluates a squares-adding language in which we have a limited number of expressions. Such as:

    (add-squares 2 4)
    (add-squares (add-squares 4 3) 5)
etc.
christopherdone
I believe SICP's definition of a language involves these: means of simple data, means of combination and means of abstraction. Numbers, strings, data structures/objects are the simple data as you would find in any program. Functions and variables are means of abstraction. And what those functions and variables define also create new abstractions and means of combination. This is where our own language comes in. In this way, all your programs define languages, and to run them is to perform evaluation of these languages. So the program is the evaluator of a language we've defined in trying to describe our problem domain. I'd give examples but SICP gives ample.