As long as you don't test it you are in a quantum state, the same as for the Schrödinger's cat. Your code is either buggy or is not.

Hence, bugs are in fact triggered by users.

I tried to solve some of the last Advent of Code enigmas with LispE, and I discovered a plethora of problems, which I didn't think would erupt after so many years of tests.

​

​

Old school text generation

The method we will present here belongs to the old school, the one before chatGPT and other language models. But sometimes, if you don't have a dozen GPUs at hand and a good terabyte of hard disk, well, the normal configuration of a computer scientist today... Ah, this is not your case... I didn't know... Sorry...

So there are some traditional methods to achieve similar results. Well, it won't write your year-end report...

I want to show you how you can implement one with LispE. (Yeah... I know again)

The grammar

In the case of an old-fashioned generation, you need a generation grammar.

For those in the know, the parser that I will describe next is called a Chart Parser.

For example:

  S : NP VP
  PP : PREP NNP
  NP : DET NOUN
  NP : DET NOUN PP
  NP : DET ADJ NOUN
  NNP : DET NLOC
  NNP : DET ADJ NLOC
  VP : VERB NP
  DET : "the" "a" "this" "that
  NOUN : "cat" "dog" "bat" "man" "woman" "child" "puppy
  NLOC : "house" "barn" "flat" "city" "country
  VERB: "eats" "chases" "dicks" "sees"
  PREP: "of" "from" "in"
  ADJ: "big" "small" "blue" "red" "yellow" "petite"

There is also a grammar for French, but it is admittedly a bit complicated to read, especially because of the agreement rules.

Compile this thing

This grammar is rather simple to read. We start with a sentence node "S", which is composed of a nominal group and a verbal group. The rules that follow give the different forms that each of these groups can take. Thus a nominal group: NNP can be broken down into a determiner followed by an adjective and a noun.

The compilation of this grammar consists in creating a large dictionary indexed on the left parts of these rules:

{
   %ADJ:("big" "small" "blue" "red" "yellow" "petite")
   %DET:("the" "a" "this" "that")
   %NLOC:("house" "barn" "flat" "city" "country")
   %NOUN:("cat" "dog" "bat" "man" "woman" "child" "puppy")
   %PREP:("of" "from" "in")
   %VERB:("eats" "chases" "bites" "sees")
   ADJ:"%ADJ"
   DET:"%DET"
   NLOC:"%NLOC"
   NNP:(("DET" "NLOC") ("DET" "ADJ" "NLOC"))
   NOUN:"%NOUN"
   NP:(
      ("DET" "NOUN")
      ("DET" "NOUN" "PP")
      ("DET" "ADJ" "NOUN")
   )
   PP:(("PREP" "NNP"))
   PREP:"%PREP"
   S:(("NP" "VP"))
   VERB:"%VERB"
   VP:(("VERB" "NP"))
}

Some lines are simple copy/paste of the rules above, except for the lexical rules which are preceded by a "%". The goal is to be able to differentiate between applying a rule and generating words.

Analyze and generate with the same grammar

This is certainly the nice thing about the approach we propose here.

We will use this grammar in both directions, which means that we can feed it a piece of sentence and let it finish.

For example, if we start with: a cat, it can then propose its own continuations.

Note that here, the continuations will draw random words from the word lists. This can result in completely ridiculous sentences... or not.

The first step

The user provides the beginning of a sentence, but also, and this is fundamental, the initial symbol corresponding to what (s)he wants to produce.

This symbol is an entry point in our grammar. We will choose: S.

In other words, we will ask the system to produce a sentence.

In the first step we have two lists in parallel:

   Words   Categories
("a "cat")  ("S")

The replacement

S is an entry point in the grammar whose value is: ("NP" "VP")

So we replace the structure above to reflect this possibility.

  Words     Categories
("a "cat") ("NP" "VP")

The head of the category list is now: NP.

Since there are several possible rules for NP, we'll just loop around to find the one that covers our list of words:

  Words        Categories
("a "cat") ("DET" "Noun" "VP")

Now our head is DET which points to a lexical item. We just have to check that "a" belongs to the list associated with "DET".

This is the case, we can then eliminate elements from both lists:

  Words  Categories
("cat") ("Noun" "VP")

We can do the same operation for "Noun", the word list is then empty.

Words Categories
()     ("VP")

We then switch to the generation mode.

Generation

VP returns a list with only one element: ("Verb" "NP")

     Categories             Words
  ("Verb" "NP")          ("a" "cat")

Note that "Generated" contains as initial value the words coming from our sentence.

Since Verb is a lexical item, we draw a word at random from our list of verbs:

     Categories             Words
      ("NP")         ("a "cat" "chases")

We then draw a rule at random from those associated with NP:

     Categories             Words
("Det" "Adj" "Noun")    ("a "cat" "chases")

The job is now very simple, just draw a determiner, an adjective and a noun at random from their respective list:

     Categories                Words
        ()         ("a "cat" "chases" "a" "big" "dog")

Since the list of categories is now empty we stop there and returns our sentence.

Implementation detail in LispE

If you take a quick look at the code of the parser, you will observe the presence of two functions: match and generate. These functions are based on the extensive use of defpat, the pattern programming functions in LispE.

match

match is used to check if the words in a sentence can be parsed by the grammar. The conditions for match to succeed are twofold:

• Either the word list and the category list are empty
• Either the word list is empty and the system continues in generation mode on the remaining categories

​

; We have used up all our words and categories
; No need to go further
(defpat match ([] [] consume) 
   (nconcn consume "$$") 
)

; We stop and generate, the word list is empty
(defpat match ( current_pos [] consume)   
   (generate current_pos consume)
)

; We check the rule associated to the leading category
; consp checks if an object is a list. If it is not the case, it is a lexical rule.
; If not, we loop over the possible rules. 
(defpat match ( [POS $ current_pos] [w $ sentence] consume)
   (setq rule (key grammar POS))
   (if (consp rule) ; if it is a group of rules, we loop to find the right one
      (loop r rule
         (setq poslst (match (nconcn r current_pos) (cons w sentence) consume)
         (if poslst
            (return poslst) ; we find one we stop
         )
      )
      (if (in (key grammar rule) w) ; otherwise it is a lexical rule and we check if the current word is part of it
         (match current_pos sentence (nconcn consume w))
      )
   )
)

Note that "$" is the tail separator operator. Hence "match((NP Verb NP))" will return "POS = NP" and "current_pos = (Verb NP)".

generate

Generation is the final step. Thanks to pattern programming, this operation is reduced to two functions.

; Generating a word
; We are looking for a rule
; This one is either a normal rule (consp) or a lexical rule
(defpat generate([POS $ current_pos] tree)
   (setq r (key grammar POS))
   (if (consp r)
      ; here places the categories of a randomly drawn rule on top
      (generate (nconcn (random_choice 1 r 30) current_pos) tree) 
      ; here we add a word drawn at random
      (generate current_pos (nconc tree (random_choice 1 (key grammar r) 30)) 
   )
)  

; There are no more categories available, we place an end-of-sequence symbol to indicate that 
; all was generated
(defpat generate ([] tree) (nconc tree "%%") )

Conclusion

For those who have already had the opportunity to work with Prolog, this way of designing a program should seem very familiar. For others, this way of programming may seem rather confusing. The use of a pattern to distinguish different functions with the same name but different arguments is called "polymorphism". This kind of operation is also available in C++:

    Element* provideString(wstring& c);
    Element* provideString(string& c);
    Element* provideString(wchar_t c);
    Element* provideString(u_uchar c);

For example, these lines of code come from the interpreter LispE itself.

What distinguishes defpat here from the example above, however, is the richness and complexity of the patterns that can be dynamically used to parse a list of words and categories. Instead of a static compiled call, we have here a very flexible method that allows us to concentrate on the code specific to the detected pattern.

In particular, this method allows tree or graph traversal without the programmer ever getting lost in the tangle of special cases. If the list of elements evolves, it is often enough to add an additional function to take these new elements into account without redesigning the rest of the program.

Someone asked me recently, what was the motivation behind LispE. Here is an example of the kind of functionalities that LispE proposes.

Adventures games were very popular at the beginning of the PC revolution back at the beginning of the 80s. Implementing a game is not very difficult in itself, but it is far from being a trivial task.

However, function programming concepts such as data types and pattern matching can prove incredibly handy to implement such a game.

For instance, you can transform each of your different actions into a Data Type:

(data Command   
   [Move atom_]
   [Break atom_ atom_]
   [Open atom_ atom_]
   [Kill atom_ atom_]
   [Pick atom_ atom_]
   [Take atom_]
   [Drop atom_]
)

(Note that [..] are equivalent to (..), we can freely choose one or the other for more code clarity)

A Data Type provides some very interesting way of controlling how your input is handled in your code. For instance, in each of these definitions, we define the number of arguments and their basic type. In this case, each should be an atom.

However, a data type should not be confused with a struct as in languages such as C++ or Java. It does not record any data structures in memory. Functional Programming tries to keep away from side-effect, while struct in imperative languages wouldn't care less.

If we take the following C struct:

struct {
   int i;
   char c;
} foo;

foo.i = 10;
foo.c = 'a';

Nothing prevents us from modifying the internal values of that struct, which of course might provoke some side-effect.

So what's the point?

These structures shine when used in collaboration with pattern functions.

(defpat action ( [Pick 'up x] ) ...)
(defpat action ( [Take x] ) ...)
(defpat action ( [Drop x] ... )
(defpat action ( [Move direction] ...)

The function action in this context is polymorphic and can be triggered with different data types.

(action [Move 'left])
(action [Pick 'up 'stone])

Each of these actions will then be matched against the corresponding function definitions above.

If you have a look on: minizork_en.lisp, you'll see that we take a string as input and then apply a few transformations:

(setq dialog "GET THE STONE")

; car and cdr have also been repurposed for strings
; GET THE STONE is transformed into: Get the stone

(setq dialog (+ (upper . car dialog) . lower . cdr dialog))

; We replace synonyms with their official value: Get --> Take
; We transform each of our strings into atoms. 
; Note that select returns the first non null value
; We remove stopwords (replaced with "~")
; We eventually obtain: (Take stone)

(setq commands 
  (filterlist '(neq '~) ; we remove stopwords
     (maplist ; we replace words with their synonyms or remove stopwords
         (λ(x) (atom . select (key filterwords x) x)) 
         (split dialog " "))))

Once this transformation has been completed, we can try our new command:

(maybe
   (action command) ; (action [Take stone])
   (println "Wrong command")
)

Basically, if there is an error, we catch it and execute the last line.

The use of pattern functions with data types simplify quite a lot the whole code.

When you implement your own programming language, one of the problems is to implement a GUI to play with it. If you compile with WASM, you can solve this issue and a as a bonus you will be able to demonstrate your language across the Internet quite easily.

However, there are some real issues. One is that Web Assembly handle strings as arrays of integers.

If you are interested, I compiled my own language: LispE as a WASM library.

I have written a few blogs about how to do it: https://github.com/naver/lispe/wiki/6.18-Handling-strings-in-WASM-without-burning-yourself

Here is also a guide on how to use this library: https://github.com/naver/lispe/wiki/6.17-A-WebAssembly-version-of-LispE

I have been working for a few years on my own implementation of Lisp. I have extensively described the language syntax here: https://github.com/naver/lispe/wiki.

The real reason of this version of Lisp is that I wanted to explore array languages such as APL, so I implemented a version of Lisp that is based on arrays and not linked lists. Thanks to this implementation, I was able to implement many operators that are very similar to APL, but which would be implemented on top of a Lisp syntax. However, you can still use traditional Lisp instructions such as car and cdr.

This Lisp also provides many specific types: such as tensors, matrices or dictionaries.

For instance, you can create a tensor in one line of code: (rho 4 5 6 (iota 120)).

I have written a blog on this topic: https://github.com/naver/lispe/wiki/6.20-Conway-Game-of-Life-in-LispE

There are also some implementations for the resolution of Advent of Code enigma in the examples directory. That will give you some flavors of what I try to achieve.

I also provide installers for mac (intel and apple silicon) and windows: https://github.com/naver/lispe/tree/master/binaries. I also compile a version for WebAssembly: See the WASM directory for an example of how to execute LispE in a browser.

For those who are interested, I also implemented my own terminal editor, which is part of the language itself but can also be used independently: jag.

https://github.com/naver/lispe/wiki/1.2-Jag:-Terminal-Editor-With-Mouse-Support-and-Colour-Highlighting

It is implemented as two C++ classes, that can be derived for your own purpose, even though the internal documentation might be a bit lacking.

The whole project is open-source, and was developped from within Naver corporation, however, there are not strings attached.

I have also implemented a mechanism to implement external libraries that can be loaded within the language itself.