newLISP compiler

Started by cormullion, October 04, 2009, 04:54:17 AM

Previous topic - Next topic

cormullion

I stumbled over this the other day.



http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf">An Incremental Approach to Compiler Construction



I haven't read it all, but I'm wondering... Is it technically possible to write a compiler for newLISP? I know Scheme and newLISP are very different, but are they that different?



I know that newLISP isn't intended to have a compiler. I'm just wondering whether it's (theoretically) possible.

Lutz

#1
Yes, you could compile newLISP if you take away some of its dynamic nature. Like no other Lisp, newLISP implements the code-equals-data paradigm 100%. E.g. self modifying code like this (created by Kazimir):


; no iteration, no recursion, but runs forever
(define (f)
  (begin
    (println (inc cnt))
    (push (last f) f -1)
    (if (> (length f) 3) (pop f 1))))


or sequences like this:


(define (foo x) . . . )

(save "foo.lsp" 'foo)


... would not be allowed in code to be compiled. One would work around this by compiling incrementally only designated functions, e.g. by introducing a built-in 'compile' function. This is how Common Lisp systems work, selectively compiling functions in an interpreted environment.



Another obstacle is the data-type polymorphic nature of many newLISP functions. It doesn't make compilation impossible but produces less efficient compiled code, when data types are not known during compile time. This could be alleviated somewhat by introducing type-tags in newLISP source, to help the compiler where possible.



My philosophy is to keep newLISP 100% dynamic, giving the programmer a maximum freedom of expression and comfortable interactive working. A scripting language not limited by all sorts of constraints and extra features to make it a compilable language at the same time.



When analyzing programs, which do have performance bottle-necks, you will always find those problems isolated to specific portions of the code. These portions can be compiled in another language and 'import'ed.



Many times programs already exist to efficiently perform a certain complex function. In that case newLISP has functions like 'exec' and 'process' and facilities like pipes and networking, to interact with those programs.



Compilable Lisp and Scheme were created in a time where people still believed, they could create that one programming tool for every purpose. Today we know the optimal way is, to use different specialized tools together to solve complex problems.

unixtechie

#2
There is another answer, given by Alexander Burger, the creator of another tiny fast micro-lisp, called "pico-lisp" (or picolisp); its home page is at  http://www.software-lab.de">http://www.software-lab.de (click on "download" )



In his paper called

" Pico Lisp A Radical Approach to Application Development"

(pdf is here:  http://www.software-lab.de/radical.pdf">http://www.software-lab.de/radical.pdf )

Alexander looks at a number of considerations and re-thinks them. Number one there is "Lisp needs a compiler"



Have a look at it, there's something in that, I think

Elica

#3
Lutz is absolutely right. I'm now finishing a Logo compiler (internally Logo is very close to Lisp), so to support its dynamic features (like defining variables and functions at run time) it has incremental JIT-like compilation.



The fact that datatype is a property of the datum, not a property of the variable adds some extra checks whenever the datum is being used.



Also, support for dynamic and syntax scopes adds some difficulties.



In a nutshell, in an ordinary non-dynamic program there is a huge increase of performance. In a very dynamic program (which modifies itself at run-time) the performance could be worse than that of an interpreter.



Fortunately, most programs in Logo do not use the dynamic features of the language, like constructing a list of command and then executing it. So, a compiler gives a pleasant speed improvement for the average users.



Unfortunately a compiler for Logo (and Lisp) will put its developer in the programming hell, so if Lutz is a software masochist (like me), he can give it a try :)



Making a compiler for languages like C and Pascal is a lot easier and straightforward.

Jeff

#4
It would be nice to have a more robust API to extend newlisp from C, though. The "extend rather than embed" philosophy of Python is equally applicable to newlisp. I write a lot of C libraries and end up spending a lot of time gluing the code together with newlisp. A few glue functions in a shared library or a header file with some simple conventions that would allow newlisp to auto-discover/auto-register functions via a macro or something... that would allow us to add new datatypes and fast-as-c routines to newlisp without affecting its dynamic character.
Jeff

=====

Old programmers don\'t die. They just parse on...



http://artfulcode.net\">Artful code

cormullion

#5
Picolisp article is interesting, thanks. I've yet to look into it in detail - anyone care to summarize their thoughts about it?



I understand the philosophy of 'no compiler needed' better. I like Jeff's idea too, though. Is this the 'plugin' idea that would allow people to extend the language in new directions without affecting the core system too much? Sounds good to me.

Jeff

#6
I think an extension api with the following components would let us do whatever is necessary:



1) an include with the major types - nil, cell, symbol, etc

2) a shared library would have an "init" function that calls a macro or function that registers a function with newlisp; it would also have a "close" function that would deallocate any resources it was holding on exit; an "exception" handler that did whatever was necessary for cleanup when the newlisp interpreter requires it (e.g. during a fatal error or trapped signal)

3) a few functions to pack/unpack data from cells as basic c types; basically, the reverse of pack/unpack on the c side

4) a function to call a newlisp function on a cell from c

5) some basic documentation of the above, with coding conventions for copying arguments, reference returns, et al



If I am missing something, please chime in :)
Jeff

=====

Old programmers don\'t die. They just parse on...



http://artfulcode.net\">Artful code

HPW

#7
Quote2) a shared library would have an "init" function that calls a macro or function that registers a function with newlisp;....


For my neobook-newlisp framework I had done a similar interface.

The extension-dlls gets 2 functions exported(my delphi-examples):

('MyPlugin' is replaced with the real DLL-Name)

FUNCTION MyPluginCmdList( password,language,cmdlist : PChar ): BOOLEAN; stdcall;
VAR      cmdstr     : STRING;
begin
  IF ExtPasswordcheck(password) Then
    BEGIN
    IF AnsiUpperCase(language) = 'LISP' THEN
      BEGIN
      cmdstr := '(list ';
      cmdstr := cmdstr+'(list "MyPluginCommand1"                   "1" 6)'; Commandname+CmdId+NumberOfParams
      cmdstr := cmdstr+'(list "MyPluginCommand2"                   "2" 1)';
...
...
      cmdstr := cmdstr+')';
      END
    ELSE
      BEGIN
      cmdstr := '';
      cmdstr := cmdstr+'MyPluginCommand1'+           '|1|6'+chr(13)+chr(10);
      cmdstr := cmdstr+'MyPluginCommand2'+           '|2|1'+chr(13)+chr(10);
...
...
      END;
    StrCopy ( cmdlist, PChar(cmdstr));
    END;
end;

FUNCTION MyPluginExec( password,cmdid,Params0,Params1,Params2,Params3,Params4,Params5,Params6,Params7,Params8,Params9 : PChar ) : BOOLEAN;  stdcall;
VAR
  IDNum : Integer;
BEGIN
  IF ExtPasswordcheck(password) Then
    BEGIN
      IDNum := StrToInt(cmdid);
      { Examine the Action string to determine which Plug-In command to execute... }
      CASE IDNum OF
        1 : Result := MyPluginCommand1( Params0, Params1, Params2, Params3, Params4, Params5 );
        2 : Result := MyPluginCommand2( Params0, FALSE );
...
...
       ELSE Result := FALSE;
      END;
    END;
END;


In newlisp I use this functions to import and free the DLL-commands:

(define (nbreg nbexeccmd nbpassw nbdllcmdlst)
(dolist (nbcmdlst nbdllcmdlst)
(begin
(setq nbparastr1 "")
(setq nbparastr2 (string nbexeccmd " "" nbpassw "" "" (nth 1 nbcmdlst) "" "))
(for (x 1 (last nbcmdlst)1)
(begin
(setq nbparastr1 (string nbparastr1 "nbpara" x " "))
(setq nbparastr2 (string nbparastr2 "nbpara" x " "))))
(set(sym (first nbcmdlst))
(eval-string (string "(quote(lambda (" nbparastr1 ")(" nbparastr2 ")))")))
(constant (global (eval-string (string (char 39)(first nbcmdlst)))))
)
)
)
(define (nbdllreg nbdllname nbpassw   nbcmdlist)
(if (not(eval(sym(string nbdllname "Exec"))))
(import (nbget(string "[*/*" nbdllname "DllName]")255)(string nbdllname "Exec")))
(if (not(eval(sym(string nbdllname "CmdList"))))
(import (nbget(string "[*/*" nbdllname "DllName]")255)(string nbdllname "CmdList")))
(setq nbRegisteredPlugins (append nbRegisteredPlugins (eval-string (string "(list "" nbdllname "")"))))
(setq nbcmdlist (dup " " 10000))
(eval-string (string "(" nbdllname "CmdList "" nbpassw "" "LISP" nbcmdlist)"))
(setq nbcmdlist(eval-string(get-string nbcmdlist)))
(set(sym(string nbdllname "CmdCount"))2)
(nbreg (string nbdllname "Exec") nbpassw nbcmdlist)
)
(define (nbfreelib  nbdllname nbrefcount nbdllHandle)
(if (not(eval(sym "GetModuleHandleA")))
(import "kernel32.dll" "GetModuleHandleA"))
(if (not(eval(sym "FreeLibrary")))
(import "kernel32.dll" "FreeLibrary"))
(dolist (nbdllname nbRegisteredPlugins)
(setq nbdllHandle(GetModuleHandleA (nbget (string "[*/*" nbdllname "DllName]") 255))
nbrefcount (eval-string(string nbdllname "CmdCount"))
)
(for (x 1 nbrefcount 1)
(FreeLibrary nbdllHandle))
)
)


So a
(nbdllreg "MyPluginName" "1234")
 does the import and a
(nbfreelib)
does reset the reference-counter to free the DLL.
Hans-Peter

cormullion

#8
It seems like a great idea, allowing newLISP to remain small and compact yet running compiled routines when necessary. If running such an imported function is as simple as writing:



(load "./plugins/zip.nlp")

(zip "string")



then it would be perfect. I might even learn C... :)

newdep

#9
XLisp also does something like this, it has a more flexible way of handling library's import..
-- (define? (Cornflakes))