{"id":23608,"date":"2023-05-05T02:32:04","date_gmt":"2023-05-05T02:32:04","guid":{"rendered":"https:\/\/www.booksofall.com\/?post_type=product&p=23608"},"modified":"2023-05-05T02:32:05","modified_gmt":"2023-05-05T02:32:05","slug":"programming-languages-application-and-interpretation","status":"publish","type":"product","link":"https:\/\/www.booksofall.com\/fr\/programming-languages-application-and-interpretation\/","title":{"rendered":"Programming Languages: Application and Interpretation"},"content":{"rendered":"
\n

2 Everything (We Will Say) About Parsing<\/h2>\n

Parsing is the act of turning an input character stream into a more structured, internal representation. A common internal representation is as a tree, which programs can recursively process<\/a>. For instance, given the stream.<\/p>\n

23 + 5 – 6<\/p>\n

we might want a tree representing addition whose left node represents the number 23 and whose right node represents subtraction of 6 from 5. A parser<\/a> is responsible for performing this transformation.<\/p>\n

Parsing is a large, complex problem that is far from solved due to the difficulties of ambiguity. For instance, an alternate parse tree for the above input expression might put subtraction at the top and addition below it. We might also want to consider whether this addition operation is commutative and hence whether the order of arguments can be switched. Everything only gets much, much worse when we get to full-fledged programming languages<\/a> (to say nothing of natural languages).<\/p>\n

2.1 A Lightweight, Built-In First Half of a Parser<\/h3>\n

These problems make parsing a worthy topic in its own right, and entire books, tools, and courses are devoted to it. However, from our perspective parsing is mostly a distraction, because we want to study the parts of programming languages that are not parsing. We will therefore exploit a handy feature of Racket to manage the transformation of input streams into trees: read. read is tied to the parenthetical form of the language, in that it parses fully (and hence unambiguously) parenthesized terms into a built-in tree form. For instance, running (read) on the parenthesized form of the above input\u2014<\/p>\n

(+ 23 (- 5 6))<\/p>\n

\u2014will produce a list, whose first element is the symbol \u2019+, second element is the number 23, and third element is a list; this list\u2019s first element is the symbol \u2019-, second element is the number 5, and third element is the number 6.<\/p>\n

2.2 A Convenient Shortcut<\/h3>\n

As you know you need to test your programs extensively, which is hard to do when you must manually type terms in over and over again. Fortunately, as you might expect, the parenthetical syntax is integrated deeply into Racket through the mechanism of quotation. That is, \u2019<expr>\u2014which you saw a moment ago in the above example\u2014acts as if you had run (read) and typed <expr> at the prompt (and, of course, evaluates to the value the (read) would have).<\/p>\n

2.3 Types for Parsing<\/h3>\n

Actually, I\u2019ve lied a little. I said that (read)\u2014or equivalently, using quotation\u2014will produce a list, etc. That\u2019s true in regular Racket, but in Typed PLAI, the type it returns a distinct type called an s-expression, written in Typed PLAI as s-expression:<\/span><\/p>\n

> (read)
\n– s-expression
\n[type in (+ 23 (- 5 6))]
\n‘(+ 23 (- 5 6)) <\/span><\/p>\n

R<\/span><\/a>acket<\/a> has a very rich language of s-expressions<\/a> (it even has notation to represent cyclic structures), but we will use only the simple fragment of it.<\/span><\/p>\n<\/div>\n

\n

In the typed language, an s-expression is treated distinctly from the other types, such as numbers and lists. Underneath, an s-expression is a large recursive datatype that consists of all the base printable values\u2014numbers, strings, symbols, and so on\u2014and printable collections (lists, vectors, etc.) of s-expressions. As a result, base types like numbers, symbols, and strings are both their own type and an instance of s-expression. Typing such data can be fairly problematic, as we will discuss later [REF].<\/p>\n

Typed PLAI<\/a> takes a simple approach. When written on their own, values like numbers are of those respective types. But when written inside a complex s-expression\u2014in particular, as created by read or quotation\u2014they have type s-expression. You have to then cast them to their native types. For instance:<\/p>\n

\"\"<\/p>\n

This is similar to the casting that a Java<\/a> programmer would have to insert. We will study casting itself later [REF].<\/p><\/blockquote>\n<\/div>\n","protected":false},"excerpt":{"rendered":"