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.

The concept Linguistic abstraction: Linguistic abstraction is the act of establishing a new language

In 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 Example of the LAML course home page system

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)

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 BRL

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/" ) ) )

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

LAML

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.

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.

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 Similar embedded language LAML transformation functions

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.

Reference The generated Course Plan page (web only)

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

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 SICP: Metalinguistic abstraction

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 SICP: The full story about 'Lisp in Lisp'

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 R5RS: Eval R5RS: Apply

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