3.1 Comparison to Lisp

Prev Up Next Page 19 of 800 Search internet

The lgs language has more in common with Lisp than meets the eye, but there are also essential differences.

Lisp syntax versus lgs syntax

A term like m + n in lgs corresponds to (+ m n) in Lisp. The difference, however, is merely a difference in syntactic sugar. How small the difference is becomes evident when looking at the 'quote' feature available in both Lisp and lgs.

Both Lisp and lgs have flexible syntax. In the examples given in the following we use standard Common Lisp syntax for Lisp and disregard the possibilities that Common Lisp readtables provide. Furthermore, we use the syntax defined by the base page for lgs and disregard that anybody can write their own base pages and define a completely different syntax.

Lisp quotes versus lgs quotes

A term like quote m + n end quote in lgs corresponds to (quote (+ m n)) in Lisp. In both systems, the value of such a quote is a three element list. In both systems, the first element of the list represents the plus operator, the second represents the m variable, and the third represents the n variable.

So, as you can see, in Logiweb the Lisp S-expressions lurk right under the syntactic sugar.

There are also differences, however.

Lisp symbols versus Logiweb references and indexes

As mentioned, the value of (quote (+ m n)) is a three element list. The first element of that list is a Lisp symbol which represents addition. In principle, Lisp symbols are 'atomic' in the sense that they have no internal structure. In principle, the only operation Lisp provides for symbols is test for equality.

The value of quote m + n end quote is also a three element list. The first element of that list is a Logiweb symbol which represents addition. Contrary to Lisp symbols, Logiweb symbols have structure.

A Logiweb symbol is a list (r,i,d) whose second element i is the index of the m + n construct and r is the reference of the home page of that construct. The third element d may contain something called 'debugging information'. Forget about d for now.

The reference r and the index i are both naturals (i.e. non-negative integers). Thus, Logiweb symbols are essentially made up of two natural numbers whereas a Lisp symbol is atomic.

Lisp print names versus the Logiweb name aspect

In principle, Lisp symbols have no structure. They do not even have a name. Lisp has something called an 'environment', however, and the environment maps Lisp symbols to an 'association list'. The association list in turn contains a 'print name' of the symbol.

The Lisp print name of a Lisp symbol corresponds to the Logiweb name aspect of a Logiweb symbol. In general, a Lisp association list defines a mapping from keys to values where the keys correspond to Logiweb aspects and the values correspond to the right hand sides of Logiweb definitions.

Lisp environments versus Logiweb caches

Common Lisp has a data structure which represents a Lisp environment. Common Lisp environments are almost-atomic in the sense that it is obvious that they contain a lot of information but one cannot dig it out.

The Logiweb analog of Lisp environments are called Logiweb caches. Logiweb caches differ from Lisp environments in that they have a well-defined structure and is made up of ordinary data structures like pairs and naturals.

Furthermore, the cache of a Logiweb page is easily accessible: The page symbol of a page has the cache of the page as value. As an example, on the combinations page, the value of combinations is the cache of the combinations page.

The base page defines an eval function which takes a term, a cache, and an association list of local variable bindings as input and returns the value of the term. However, the base page also defines other functions that use caches: The function that does macro expansion takes the environment as input. And the compile function takes a cache in which compiled versions of functions are missing as input, adds compiled versions, and returns the enriched cache.

The Lisp very special value versus the Logiweb very special value

Lisp has a very special value named NIL. NIL is the only value which represents falsehood. All other values represent truth.

In contrast, Logiweb has a very special value named true. true is the only value which represents truth. All other values represent falsehood.

NIL of Lisp and true of Logiweb both represent the empty list.

The base page uses the name true for Logiweb true. The base page also defines alternative names like <<>> for Logiweb true which may be used when using Logiweb true to denote the empty list.

Note that the lgs name for true is true and not just T. The Logiweb base page reserves all one letter words (a-z,A-Z) for variable names, so a T in an lgs-file denotes a variable and not true.

Lisp variables versus Logiweb variables

As mentioned, the value of (quote (+ m n)) is a three element list. The second element of that list represents the m variable. Likewise, the value of quote m + n end quote is a three element list whose second element represents m.

In Lisp, a variable like m is represented by a symbol. In Logiweb, m is treated like any other construct. Thus, in Logiweb, the m is represented as a one-element list whose sole element represents m.

Lisp can distinguish between a variable like m and a parameterless function call (f) in that m is a symbol and (f) is a list. Logiweb does something else: When Logiweb evaluates a construct, it looks up the value aspect of the construct. If the construct has a value aspect, it is considered to be a function. If the construct has no value aspect, it is considered to be a variable.

Logiweb allows variables to have arity different from zero. Variables with an arity different from zero are indexed variables.

Lisp symbols versus Logiweb strings

As mentioned, Logiweb symbols consist of a reference and an index, both of which are naturals. In most situations, Logiweb symbols are to Logiweb what Lisp symbols are to Lisp. Logiweb also has a notion of string constants, however, which in some cases are to Logiweb what symbols are to Lisp

Logiweb has the peculiarity that string constants are naturals (i.e. non-negative integers). As an example, the string constant "abc" has the value 97 + 256 * ( 98 + 256 * ( 99 + 256 ) ) = 23290465 where (97,98,99) is "abc" encoded in Unicode UTF-8.

Logiweb uses the string "value" to denote the value aspect and the string "name" to denote the name aspect, so this is one case where strings are to Logiweb what symbols are to Lisp.

Using strings to denote aspects could ruin the notational freedom of Logiweb: Even on a Chinese version of the base page, the value aspect has to be represented by the string "value" which is English. Logiweb solves that by using one level of indirection:

The base page contains the following statement: Define message of value as "value" end define. That statement makes the value construct denote the "value" aspect. A Danish base page might say Definer meddelelse af værdi som "value" slut definer which would make the værdi construct denote the "value" aspect.

Logiweb also uses strings for denoting fundamental constructs. As an example, quoting is fundamental in Logiweb (as opposed to being defined from more fundamental constructs). Quoting in Logiweb is represented by the string "quote".

Again, Logiweb uses indirection to ensure notational freedom. The base page contains the following statement: proclaim quote x end quote as "quote" end proclaim. That statement makes the quote x end quote construct denote quoting. Authors are free to proclaim any other construct to denote quoting.

Lisp literals versus Logiweb literals

In Lisp, a symbol with name 2009 denotes the natural two thousand and nine. Logiweb does not support such literals. Instead, the base page defines the following 20 constructs:


Using those definitions, the lgc compiler parses 2009 as 2(0(0(9))) which macro expands into something whose value is 2009.

Note that in constructs like 2" there is no space character between 2 and ". For that reason, 2009 has to be stated without spaces between the digits.

Lisp macros versus Logiweb macros

Logiweb macros are like Lisp macros: they are Turing complete and they operate on the parse tree of the source text rather than at the textual level as the C preprocessor does.

Lisp backquotes versus Logiweb backquotes

Exactly like Lisp backquotes, Logiweb backquotes are defined in the macro expansion machinery, c.f. the base page.

Debugging information

If you ask Lisp to evaluate (equal (quote (+ m n)) (quote (+ m n))) then Lisp will say that the statement is true. If you ask Logiweb to evaluate quote m + n end quote = quote m + n end quote then Logiweb will say that the statement is false. That is because the symbols inside the value of quote m + n end quote contain 'debugging information'.

Logiweb symbols have form (r,i,d) where d is the debugging information. The debugging information states which Logiweb page m + n occurs in and where on the page it occurs. If you write quote m + n end quote = quote m + n end quote you have two occurrences of m + n which occur different places and thus get different debugging information. If you write let x = quote m + n end quote in x = x then Logiweb will say that the statement is true.

Macro expansion may shuffle symbols, but if the macro expanders are defined suitably, they preserve the debugging information allowing to see where each symbol came from. As an example of use, the error messages generated by the proof checker on the check page use debugging information to locate which proof line of which proof is in error. Doing so would be difficult without debugging information because the proofs first undergo intricate macro expansion and then undergoes even more intricate 'tactic' expansion before they are proof checked.

In chemistry you can put a radioactive earmark on an atom of a molecule and then trace the molecule through a process. In lgs you can mimic that using debugging information: Symbols have form (r,i,d), but you can give them any form you like as long as they start with the reference r and the index i. Chances are that you would like the usual d to come after r and i in order not to fool programs which rely on it, but you can add extra elements after the d if you like. The easiest place to add such earmarks is during macro expansion.

Univocality of Logiweb

Lisp is a functional language and so is Logiweb. However, it is not too well-defined what a language must satisfy to be 'functional'.

One could say that Logiweb is pure functional and Lisp is not because Lisp can assign values to variables. However, it is still not too well-defined what a language must satisfy to be 'pure functional'.

For that reason it may be more informative to state that Logiweb is univocal and Lisp is not: If you apply the same Logiweb function to the same arguments twice, you get the same result the two times. If you apply the Lisp increment function to a variable two times, you get two distinct results.

As a consequence of univocality, Logiweb has no function which can tell what time it is and no function which can read from standard input. To write a Logiweb program which can find out what time it is, you need to use a Logiweb machine. A Logiweb machine is an infinite state machine whose state transitions and I/O is governed by a Logiweb function.

Some definitions of 'pure functional' requires the language to be side-effect free. But Logiweb functions need not be side effect free. Logiweb has 'spy', 'trace', 'print', and 'timer' functions which allow to emit data from the internals of the machinery to the outside world for the sake of debugging and efficiency tuning.

Personally, I have only met one language which was side effect free. That was an early alpha-test version of Logiweb which would not even talk with a debugger; it was a hell to debug.

Note that even though Logiweb allows side effects for the sake of debugging, such side effects are not portable. Do not use 'print' for printing. Optimizers may optimize print statements away, duplicate them, shuffle them, and do many other nasty things which makes print statements useless for other than debugging. Also note that side effects only allow data to flow out of Logiweb. Influx like reading from standard input is not permitted.

Lazy and Eager Lisp versus Logiweb

At the most fundamental level, Lisp is an eager functional programming language and Logiweb is a lazy functional programming language. As a programmer, however, you will use Logiweb for eager programs most of the time. That is because eager programs run faster than lazy ones, at least with present day hardware.

Simulations show that lazy Logiweb programs run very well on experimental machines with 100 cores or more. The present version of Logiweb only runs on one core.

Lisp functions are eager, but there exists lazy dialects of Lisp in which Lisp functions are lazy. Logiweb takes another approach in that it leaves the choice to the author of each page and each function.

The base page defines an eager define X as Y end define construct which ensures X to be defined as an eager function which evaluates its arguments in sequence before invoking the function itself. The sequential order is important because if evaluation of an argument results in an exception, the remaining arguments are not evaluated.

To provide a maximum of flexibility, Logiweb allows to embed eager data in lazy data and vice versa.

Lisp I/O versus Logiweb I/O

When Lisp needs to do I/O, it just calls functions that exchange data with the outside world. In Logiweb, exchanges with the outside world are encoded as data structures called 'events'.

To write a Logiweb program which can interact with the outside world, an author needs to define a 'handler'. A handler is a Logiweb function and is univocal like any other Logiweb function.

A handler is supposed to take a 'state' and a list of 'input events' as arguments and to produce a new state and a list of 'output events' as its return value. One may then start up a Logiweb machine with the given handler. The machine will then collect input and transform it to input events, invoke the handler, transform the returned output events into output, and then resume.

As an example of use, the Logiweb compiler itself is implemented as a handler and runs on the Logiweb Abstract Machine (lgwam). The lgwam program itself is in turn implemented in C. To port Logiweb to new architectures, the main task is to port lgwam.

Lisp types versus Logiweb types

Like Lisp, Logiweb types are checked at runtime. A compiler may do type inference at compile time. The present lgc compiler, however, does very little type inference at compile time.

Authors who want a typed version of Logiweb may include whatever type checker they like in the testsuite. Authors may even include type checkers which allows to apply different typing systems to different parts of the code.

If e.g. part of the code has to use Ada or ML types then it would be reasonable to define a "type/Ada" and a "type/ML" aspect of constructs and variables that have to be Ada and ML type checked, respectively. Logiweb itself would not assign any meaning to such aspects so one should avoid using a reserved word for the aspect. A string is 'reserved if it contains nothing but small letter a-z and space characters.

Prev Up Next Page 19 of 800 Search logiweb.eu

Copyright © 2010 Klaus Grue, GRD-2010-01-05