Chapter 6
Linguistic abstraction

Kurt NÝrmark
Department of Computer Science, Aalborg University, Denmark


Abstract
Previous lecture Next lecture
Index References Contents
In this lecture we will see how to establish new languages by means of Lisp and Scheme. If we - for academic reasons - establish the same language as we come from we are in the business of meta circular abstraction (in our case Lisp in Lisp). This will be briefly illustrated. We will also see how SGML/HTML/XML languages can be hosted in Scheme.


Introduction to linguistic abstraction

Linguistic abstraction
Slide Annotated slide Contents Index
References Textbook 

The concept Linguistic abstraction: Linguistic abstraction is the act of establishing a new languageIn many contexts, linguistic abstraction is qualified with the word 'meta'. Thus we speak about metalinguistic abstraction, emphasizing that we enter a higher language level than the level we came from.

  • Abstraction by means of functions

    • Encapsulation, naming and parametrization of a potentially complex expression

    • Use of good abstractions makes a program easier to understand

    • Use of abstractions makes a program shorter, because the functions can be called from more than one context

  • Abstraction by means of languages

    • Involves primitive means of expressions as well as the way the primitives can be meaningfully composed

    • A more global kind of abstraction than functional abstraction

    • Raises lexical, syntactical and - most important - semantical concerns

    • Specialized or general purpose language

Abstraction is a central discipline in all serious programming efforts. We have discussed functional abstraction in earlier parts of this material. Procedural abstraction is central in both the imperative paradigm and the object-oriented paradigm. Here we have contrasted functional abstraction with linguistic abstraction.

Problem solving by means of linguistic abstraction is a very powerful approach

Linguistic abstraction in Lisp
Slide Annotated slide Contents Index
References Textbook 

The are several possible approaches to linguistic abstractions in Lisp

  • Incremental approaches

    • Each new construct is defined by a function or a macro

      • Macros are used for new surface syntax, and in cases where evaluation order issues prevent use of functions

    • Fine grained linguistic abstraction

  • Total approaches

    • Writing an interpreter for the new language    or

    • Translating the new language to an existing language (compilation)

    • Coarse grained linguistic abstraction

Fine grained linguistic abstraction in Lisp
Slide Annotated slide Contents Index
References Textbook 

Due to the uniform notation of language constructs and functions, a set of Scheme functions can be seen as an extension of the Scheme language

  • Incremental extension of the language

    • The functional paradigm is well-suited because application of functions can be nested into each other

    • The definitions of the functions implement the language

    • A possible approach:

      • the inner functions are more or less self evaluating

      • the outermost function is responsible for the realization of the language

Programming in Lisp can be seen as incremental language development

An example of fine grained abstraction
Slide Annotated slide Contents Index
References Textbook 

A fine grained implementation of a course home page language

Each of the forms in the language are implemented as a Scheme function

Program: A sample document in a course home page language. The outer 'keyword' is course-home-page . Inside a course-home-page form there may be a number of subclauses. We see a name clause, a number-of-lectures clause etc. The important point of the example is that the expression is regarded as a clause in a new language, which we somehow want to implement with the purpose of 'solving some problem' - here to generate a set of coherent web pages for some activity.
(course-home-page

  (name "Programming Paradigms")

  (number-of-lectures 15)

  (lecture-names
    "intr" "scheme" "higher-order-fn" 
    "eval-order" "lisp-languages")

  (current-lecture 3)

  (links
    "schemers.org" "http://www.schemers.org/"
    "LAML" "http://www.cs.auc.dk/~normark/laml/"
    "Haskell" "http://haskell.org/"
  )
)

Program: An almost empty outline of the functions that implement the course home page language. Each kind of subexpression is either implemented as a function or as a macro. In this simple example, macros are not used.
(define (course-home-page name-form number-form lecture-list current-form
                          link-form process-form)

  ; The real implementation of
  ; the course home page language

)



(define (name nm) 
 (list 'name nm))

(define (number-of-lectures n) 
 (list 'number-of-lectures n))

(define (lecture-names . name-lst) 
 (cons 'lecture-names name-lst))

(define (current-lecture n) 
 (list 'current-lecture n))

(define (links . lnk-list) 
 (cons 'links lnk-list))

Reference

Coarse grained linguistic abstraction in Lisp
Slide Annotated slide Contents Index
References Textbook 

It is relatively easy and straightforward to establish a new language in Lisp syntax

  • Establishing a new 'Lisp language'

    • Generic parsing can be done by the Lisp reader

    • It is possible to concentrate on the semantic issues

    • Language checking and error handling should not be forgotten

An example of coarse grained abstraction
Slide Annotated slide Contents Index
References Textbook 

Transformation of a document which is represented as a list structure

Program: A sample document in the course home page language. This is an example of a web document in the new course home page language. We will not implement the language here, just sketch the overall approach of the processing of the document.
(course-home-page

  (name "Programming Paradigms")

  (number-of-lectures 15)

  (lecture-names
    "intr" "scheme" "higher-order-fn" 
    "eval-order" "lisp-languages")

  (current-lecture 3)

  (links
    "schemers.org" "http://www.schemers.org/"
    "LAML" "http://www.cs.auc.dk/~normark/laml/"
    "Haskell" "http://haskell.org/"
  )
)

Program: Reading the document as a list structure. We open a port to the document and use the read primitive in Scheme to read the list expression on the file. The procedure or function process-document is supposed to implement the processing semantics of the new language.
(let* ((port (open-input-file "new-document.lsp"))
       (new-document (read port))
      )

   ; new-document is a reference to the list structure
   ; representation of the new document.

   (process-document! new-document)

   (close-input-port port)
)

Program: A simple demo processing of the document. We just extract some information about the document. No attempt is made here to implement the language, nor to process the document in any realistic way.
(define (process-document! doc)
  (file-write (transform-document doc) "res.lsp"))

(define (transform-document doc)
  (let ((top-level-forms (document-forms doc)))
   (map
     (lambda (subform) 
       (subform-keyword subform))
     top-level-forms)))


(define document-forms cdr)
(define subform-keyword car)


Language embedding

Embedded languages
Slide Annotated slide Contents Index
References Textbook 

The concept embedded language: A new language N is an embedded language in an existing language E if an expression in N can be used as a subexpression of a construct in E.As a matter of practical organization the interpreter of the new language N is made available as a function in the existing language E.

  • There are many examples of embedding web languages and programming languages

    • Embedding of CSS in HTML, SVG and other XML languages

    • Embedding of Javascript in HTML for client dynamics

    • Embedding of a programming language in HTML at the server-side

      • ASP: HTML embedding of Visual Basic fragments

      • JSP: HTML embedding of Java fragments

      • PHP: HTML embedding of C-like fragments

      • BRL: HTML embedding of Scheme fragments

More or less elegant embedding of one language into the other is found in numerous web contexts

Examples of language embedding in HTML
Slide Annotated slide Contents Index
References Textbook 

Concrete illustrations of JSP, ASP, and BRL documents

Program: An example of an ASP document.
<% @Language=VBScript %>
<html dir=ltr>
<head>
<title>View Guest Book</title>
</head>
<body bgcolor="#FFFFFF" text="#000000">
<%
'This section makes it possible for visitors to sort the data in the
   columns in ascending order.
if request.form("sort")<> "" THEN
StrSort=request.form("sort")
ELSE
StrSort="TB1 ASC"
END IF
strQuery="SELECT * FROM Guestbook ORDER BY " &StrSort
'Database path statement describing the driver to use and the
   path to the desired database.
strProvider = "Driver=Microsoft Access Driver (*.mdb); DBQ=C:\Inetpub\Wwwroot\Tutorial\guestbook.mdb;"
IF Request("ID") <> "" THEN
strIDNum=Request("ID")
'Creates an instance of an Active server component
set objConn = server.createobject("ADODB.Connection")
'Opens the connection to the data store
objConn.Open strProvider
'Instantiate Command object and use ActiveConnection property to
'attach connection to Command object
set cm = Server.CreateObject("ADODB.Command")
cm.ActiveConnection = objConn
'Define SQL query
cm.CommandText = "DELETE FROM Guestbook WHERE ID = " &strIDNum
cm.Execute
END IF
'Instantiate a Recordset object and open a recordset using
'the Open method
Set rst = Server.CreateObject("ADODB.recordset")
rst.Open strQuery, strProvider
%>
<h1>Guest Book</h1>
<form name=viewdb.asp action=viewdb.asp method=post>
<table border=1 cellspacing=3 cellpadding=3 rules=box>
<%
ON ERROR RESUME NEXT
IF rst.EOF THEN
Response.Write "There are no entries in the database."
ELSE%>
<tr>
<%
'Deletes rows from the database, this cannot be undone
Response.Write "<td width=200><center>Delete Record</center></td>"
FOR i = 1 to rst.Fields.Count -1
Response.Write "<td width=200><input name=sort value=" & rst(i).Name 
   & " type=submit></td>"
NEXT
WHILE NOT rst.EOF %>
<tr>
<%
Response.Write "<td align=left valign=top bgcolor='#ffffff'>
   <a href=viewdb.asp?id=" & rst(0) & ">Delete</a></td>"
FOR i = 1 to rst.fields.count - 1
Response.Write "<td align=left valign=top bgcolor='#ffffff'>" & rst(i)
   &"</td>"
NEXT
rst.MoveNext
WEND
END IF
%>
</table>
</form>
</body>
</html>

Program: An example of a JSP document.
<%--
 
  Copyright 2001 Sun Microsystems, Inc. All Rights Reserved.
  
  This software is the proprietary information of Sun Microsystems, Inc.  
  Use is subject to license terms.
  
--%>

<%@ include file="initdestroy.jsp" %>
<%@ page import="java.util.*, cart.*" %>

<jsp:useBean id="bookDB" class="database.BookDB" scope="page" >
  <jsp:setProperty name="bookDB" property="database" value="<%=bookDBEJB%>" />
</jsp:useBean>
<jsp:useBean id="cart" scope="session" class="cart.ShoppingCart"/>
<jsp:useBean id="currency" class="util.Currency" scope="session">
  <jsp:setProperty name="currency" property="locale" value="<%=request.getLocale()%>"/>
</jsp:useBean>

<html>
<head><title>Shopping Cart</title></head>
<%@ include file="banner.jsp" %>
<%
  String bookId = request.getParameter("Remove");
  if (bookId != null) {
    cart.remove(bookId);
    bookDB.setBookId(bookId);
  		BookDetails book = bookDB.getBookDetails();
%>

<font color="red" size="+2">You just removed: <strong><%=book.getTitle()%>
</strong> 
<br>&nbsp;<br> 
</font>

<%
  } 

if (request.getParameter("Clear") != null) {
  cart.clear();
%>

<font color="red" size="+2"><strong> 
You just cleared your shopping cart! 
</strong><br>&nbsp;<br></font>

<%
  }
  // Print a summary of the shopping cart
  int num = cart.getNumberOfItems();
  if (num > 0) {
%>


<font size="+2">You have <%=num%> <%=(num==1 ? " item" : " items")%> in your shopping cart.
</font><br>&nbsp;

<table> 
<tr> 
<th align=left>Quantity</TH> 
<th align=left>Title</TH> 
<th align=left>Price</TH> 
</tr>

<% 
    Iterator i = cart.getItems().iterator();
    while (i.hasNext()) {
      ShoppingCartItem item = (ShoppingCartItem)i.next();
      BookDetails book = (BookDetails)item.getItem();
%>

<tr> 
<td align="right" bgcolor="#ffffff"> 
<%=item.getQuantity()%>
</td> 

<td bgcolor="#ffffaa"> 
<strong><a href="<%=request.getContextPath()%>/bookdetails?bookId=<%=book.getBookId()%>">
<%=book.getTitle()%></a></strong> 
</td> 

<td bgcolor="#ffffaa" align="right"> 
<jsp:setProperty name="currency" property="amount" value="<%=book.getPrice()%>"/>
<jsp:getProperty name="currency" property="format"/>&nbsp;</td>  

<td bgcolor="#ffffaa"> 
<strong> 
<a href="<%=request.getContextPath()%>/showcart?Remove=<%=book.getBookId()%>">Remove Item</a></strong> 
</td></tr>

<%
    // End of while
  		}
%>

<tr><td colspan="5" bgcolor="#ffffff"> 
<br></td></tr> 

<tr> 
<td colspan="2" align="right" "bgcolor="#ffffff"> 
Subtotal:</td> 
<td bgcolor="#ffffaa" align="right"> 
<jsp:setProperty name="currency" property="amount" value="<%=cart.getTotal()%>"/>
<jsp:getProperty name="currency" property="format"/>
</td> 
</td><td><br></td></tr></table> 

<p>&nbsp;<p>
<strong><a href="<%=request.getContextPath()%>/catalog">Continue Shopping</a>&nbsp;&nbsp;&nbsp;  
<a href="<%=request.getContextPath()%>/cashier">Check Out</a>&nbsp;&nbsp;&nbsp; 
<a href="<%=request.getContextPath()%>/showcart?Clear=clear">Clear Cart</a></strong>
<% 
} else { 
%>

<font size="+2">There is nothing in your shopping cart.</font> 
<br>&nbsp;<br> 
<center><a href="<%=request.getContextPath()%>/catalog">Back to the Catalog</a> </center>

<%
  // End of if
  }
%>

</body>
</html>

Program: An example of a BRL document. BRL - Beautiful Report Language - is a Scheme based web server framework which allows the web programmer to embed Scheme fragments into HTML
<html>
 <head>
 [
  (inputs word) ; HTML input.  Will be null if no such input.
  (define newword
    (if (null? word)
        "something"
        word))
 ]
  <title>Backwards</title>
 </head>
 
 <body>
  <form>
  Type a word: <input name="word">
  <input type="Submit">
  </form>
  
  <p>[newword] spelled backwards is
     [(list->string (reverse (string->list newword)))]
  </p>
  
  <p>This message brought to you by [(cgi SERVER_NAME)] as a public
  service.</p>
  
 </body>
</html>

Reference

Course home page embedding in Scheme
Slide Annotated slide Contents Index
References Textbook 

The simple course home page language is an embedded list language in Scheme

Program: A sample embedding of a course home document in a Scheme program. We use a quasiquotation to provide for a representation of the course home page as a list structure in the Scheme context.
(let ((ttl "Programming Paradigms")
      (max 5)
      (current 3)
     )

 `(course-home-page

   (name ,ttl)

   (number-of-lectures ,max)

   ,(cons 
     'lecture-names
     (map downcase-string  
       (list "intr" "scheme" "HIGHER-ORDER-FN" 
       "eval-order" "lisp-languages")))

   (current-lecture ,current)

   (links
     "schemers.org" "http://www.schemers.org/"
     "LAML" "http://www.cs.auc.dk/~normark/laml/"
     "Haskell" "http://haskell.org/"
   )
  )   
)


Language Mirroring

Mirrored Languages
Slide Annotated slide Contents Index
References Textbook 

The concept mirrored language: A new language N is a mirrored language in an existing language E if an expression in N in a systematic way can be represented as an expression in E.The mirror of N in E does not call for a new interpreter. A new interpreter as need for an embedded language i E. A mirror expression N-expr is written in E, and it can be evaluated by the processor (interpreter) of E.

  • LAML provides mirrors of a number of XML languages in Scheme:

    • HTML 4.01 and XHTML1.0

    • SVG

    • A number educational languages, such as LENO and the Course Home Page language (Course Plan)

An introduction of LAML - with special emphasis on the HTML mirroring rules
Go to side trackLAML
Course home page mirroring in Scheme (1)
Slide Annotated slide Contents Index
References Textbook 

The simple course home page is mirrored as an XML language in Scheme and LAML

  • Steps involved in the mirroring process:

    • Write an XML DTD of the language

    • Parse the XML DTD to a Scheme data structure

    • Synthesize the mirror of the language by the XML-in-LAML mirror generation tool

    • When using the course home page language, load the mirror as a Scheme library

Program: The course home page DTD. The DTD is essentially a context free grammar of the new XML language. XML DTDs are a heritages from SGML (The Standard Generalized Markup Language).
<!ENTITY % Number "CDATA">
    <!-- one or more digits -->

<!ENTITY % URI "CDATA">
    <!-- a Uniform Resource Identifier, see [RFC2396] -->

<!ELEMENT course-home-page
  (lecture-names, links)
>

<!ATTLIST course-home-page
  name                 CDATA          "#REQUIRED"
  number-of-lectures   %Number;        "#REQUIRED"
  current-lecture      %Number;        "#IMPLIED"
>

<!ELEMENT lecture-names
  (lecture-name+)
>

<!ELEMENT lecture-name
  (#PCDATA)
>

<!ELEMENT links
  (link*)
>

<!ELEMENT link
  (#PCDATA)
>

<!ATTLIST link
  href               %URI;             "#REQUIRED"
>

Program: The script that parses the DTD.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/mirrored-languages/dtd/parse-dtd.laml

Program: The script that generates the mirror.
(load (string-append laml-dir "laml.scm"))
(laml-tool-load "xml-in-laml/xml-in-laml.scm")

; ------------------------------------------------------------------------
; Tool parameters

; The name of the language for which we create a mirror
(define mirror-name "course-homepage")

; The full path to the parsed DTD:
(define parsed-dtd-path
  (in-startup-directory "course-home-page.lsp"))

; The full path of the mirror target directory
(define mirror-target-dir (string-append (startup-directory) "../mirror/"))

(define action-elements '(course-home-page))

(define default-xml-represent-white-space "#f")

(define auto-lib-loading "#t")


; End tool parameters
; -------------------------------------------------------------------------

(let ((mirror-destination-file
        (string-append mirror-target-dir mirror-name "-mirror" ".scm")))
  (generate-mirror parsed-dtd-path mirror-destination-file mirror-name))

Program: The mirror in Scheme of the course home page.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/mirrored-languages/mirror/course-homepage-mirror.scm

Course home page mirroring in Scheme (2)
Slide Annotated slide Contents Index
References Textbook 

A sample course home page document that uses the XML-in-LAML course home page mirror functions

Program: A sample course home page that uses the course home page mirror functions.
(load (string-append laml-dir "laml.scm"))       
(define (course-home-page! doc) 'nothing)
(load "../mirror/course-homepage-mirror.scm")

(let ((ttl "Programming Paradigms")
      (max 5)
      (current 3))

 (course-home-page  'name ttl 'number-of-lectures "5"
                   'current-lecture "3"
   (lecture-names
     (map 
       (compose lecture-name  downcase-string)  
       (list "intr" "scheme" "HIGHER-ORDER-FN" 
             "eval-order" "lisp-languages")))
   (links
     (link  "schemers.org" 'href "http://www.schemers.org/")
     (link  "LAML" 'href "http://www.cs.auc.dk/~normark/laml/")
     (link  "Haskell" 'href "http://haskell.org/")
   )))

Further processing and transformation is done by the action procedure course-home-page!

References

Course home pages ala Course Plan
Slide Annotated slide Contents Index
References Textbook 
The course home pages of the Programming Paradigms is made by the Course Plan system. The principles used in the Course Plan system are the same as illustrated about for the toy course home pages.

A real life course home page mirror in Scheme - The Course Plan system

Program: A Course Plan XML-in-LAML document.
y:/Kurt/Files/courses/prog3/prog3-03/sources/notes/includes/course-plan-example/example.laml

Reference

Embedding versus mirroring
Slide Annotated slide Contents Index
References Textbook 

How does a list-embedding of new language in Scheme compare to a mirroring of the language Scheme?

Embedding in Scheme

Mirroring in Scheme

New language fragments are represented as lists

New language fragments are represented as Scheme expressions

Many different interpretations can be provided for

The most typical transformation is 'built in', as obtained by evaluation of the Scheme expression

Processing requires a specialized interpreter

The (first level of) processing is done by the standard Scheme interpreter

Relatively awkward to combine with use of higher-order functions

Mixes well with higher-order functions


Lisp in Lisp

Why 'Lisp in Lisp'
Slide Annotated slide Contents Index
References Textbook 
In this section we will look at a principled implementation of Lisp in Lisp. In concrete terms we will study a partial Scheme implementation in Scheme itself.

Why do we study an implementation of Scheme in Scheme?

  • Motivations:

    • To illustrate the idea of linguistic abstraction in Lisp

      • Lisp is both the implementation language and the new language

    • To understand the overall principles of interpreters

    • To illustrate the use of important Lisp implementation concepts, such as environments

    • To provide a playground that provides for easy experimentation with the semantics of Scheme

We will refer to a concrete Scheme implementation from the book 'Structure and Interpretation of Computer Programs' (SICP).

Reference

An overview of Scheme constructs
Slide Annotated slide Contents Index
References Textbook 

What is the basic classification of constructs in Scheme?

  • Syntax

    • Fundamental syntactical constructs such as lambda , define , and if

  • Primitive functions and procedures

    • Fundamental functions and procedures, which cannot in a reasonable way be implemented in the language

  • Library Syntax

    • Syntactical extensions which can be implemented by macros

  • Library functions and procedures

    • Functions and procedures which can be implemented on the ground of more primitive features

Parenthesized prefix notation is used as a common notation for all kinds of constructs

This provides for an uniform notation across the different kinds of constructs in the language

Scheme in Scheme
Slide Annotated slide Contents Index
References Textbook 

It is possible to write a relatively full, but brief meta circular Scheme interpreter in Scheme

Program: The eval and apply functions (procedures) of the Scheme interpreters. The full interpreter needs a lot of relatively small helping functions (procedures) that we do not show here.
(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((quoted? exp) (text-of-quotation exp))
        ((variable? exp) (lookup-variable-value exp env))
        ((definition? exp) (eval-definition exp env))
        ((assignment? exp) (eval-assignment exp env))
        ((lambda? exp) (make-procedure exp env))
        ((conditional? exp) (eval-cond (clauses exp) env))
        ((application? exp)  (apply (eval (operator exp) env)
                                          (list-of-values (operands exp) env)))
        (else (error "Unknown expression type -- EVAL" exp))))


(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure
            (apply-primitive-procedure procedure arguments)))
        ((compound-procedure? procedure)
            (eval-sequence (procedure-body procedure)
                                  (extend-environment
                                     (parameters procedure)
                                     arguments
                                     (procedure-environment procedure))))
        (else  (error "Unknown procedure type -- APPLY" procedure))))

Reference

The eval and apply primitives
Slide Annotated slide Contents Index
References Textbook 

The implementation primitive eval of a Lisp systems is typically made available in the language, hereby providing access to evaluation of syntactical expressions (lists) in a given environment

The apply primitive is also available as a convenient mechanism for application of a function, in cases where all the parameters are available in a list

Table. An illustration of eval and apply. In the first two rows we construct a list structure of the usual html , head , title , and body HTML mirror functions. In the first row, the list structure is made by the list function. In the second row, we use the convenient backquote (semiquote) facility. In both cases we get the same result. The last three rows illustrate the use of apply . apply is handy in the cases where the parameters of a function is already organized in a list. What it interesting in our current context, however, is that apply is really an implementation primitive of Scheme, which is made available in the language itself.
Expression

Value

(let* ((ttl "My Document")
       (bdy (list 'p "A paragraph"))
       (doc
        (list 'html
         (list 'head
          (list 'title ttl))
         (list 'body bdy)))
      ) 
 (render (eval doc)))
<html>
 <head>
  <title>My Document</title>
 </head>
 <body>
  <p>A paragraph</p>
 </body>
</html>
(let* ((ttl "My Document")
       (bdy (list 'p "A paragraph"))
       (doc
        `(html 
           (head (title ,ttl))
           (body ,bdy))))
  (render (eval doc)))
<html>
 <head>
  <title>My Document</title>
 </head>
 <body>
  <p>A paragraph</p>
 </body>
</html>
(+ 1 2 3 4)
10
(+ (list 1 2 3 4))
Error: + expects argument of type number; 
 given (1 2 3 4)
(apply + (list 1 2 3 4))
10
 

References


Collected references
Contents Index
Example of the LAML course home page system
BRL
LAML transformation functions
Similar embedded language
The generated Course Plan page (web only)
SICP: Metalinguistic abstraction
SICP: The full story about 'Lisp in Lisp'
R5RS: Apply
R5RS: Eval

 

Chapter 6: Linguistic abstraction
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: July 2, 2013, 09:15:51