Strange, I thought many Lisp systems still have source level list-based interpreters. For Common Lisp I would think: SBCL (optional), CLISP, Allegro CL, LispWorks, ECL, ... They can also compile code. Compiling Lisp code was also already available in the first Lisp implementations and having a compiler was an explicit goal of the original implementors.
Let's use the LispWorks Listener (the REPL tool):
CL-USER 25 > (defun foo (bar) (break) (print (list :hello bar)))
FOO
CL-USER 26 > (foo 10)
Break.
1 (continue) Return from break.
2 (abort) Return to top loop level 0.
Type :b for backtrace or :c <option number> to proceed.
Type :bug-form "<subject>" for a bug report template or :? for other options.
CL-USER 27 : 1 > :bq
INVOKE-DEBUGGER <- BREAK <- FOO <- EVAL <- CAPI::CAPI-TOP-LEVEL-FUNCTION <- CAPI::INTERACTIVE-PANE-TOP-LOOP
<- MP::PROCESS-SG-FUNCTION
CL-USER 28 : 1 > :n
Call to INVOKE-DEBUGGER
CL-USER 29 : 1 > :n
Call to BREAK
CL-USER 30 : 1 > :n
Interpreted call to FOO
CL-USER 31 : 1 > :lambda
(LAMBDA (BAR) (DECLARE (SYSTEM::SOURCE-LEVEL #<EQ Hash Table{0} 81D03EFF03>)) (DECLARE (LAMBDA-NAME FOO)) (BREAK) (PRINT (LIST :HELLO BAR)))
The debugger output of the currently running function looks like a linked list to me. I could modify it destructively, if I wanted.LispWorks has a list-level interpreter. One can also compile code.
Typically Lisp interpreters tend to be written in C, since that usually is more portable than Assembler.
> On the downside, this is all of course completely unchecked and pretty unsafe, and, to come back to the original point, you do not have such conveniences as lexical scoping.
I would expect from a typical Lisp interpreter (a source level list-based interpreter) that it does all kinds of runtime checks and also provides lexical scoping. If there is a clojure, then this closure would be a combination of some function and an environment. In standard Common Lisp there is no access to that environment, but I could look from an inspector into it:
CL-USER 54 > (defun example (a) (lambda () (break) (print a)))
EXAMPLE
CL-USER 55 > (example 10)
#<anonymous interpreted function 8020001A59>
CL-USER 56 > (describe *)
#<anonymous interpreted function 8020001A59> is a TYPE::INTERPRETED-FUNCTION
Code (LAMBDA NIL (BREAK) (PRINT A))
Environment ((A . 10) (#:SOURCE-LEVEL-ENVIRONMENT-MARKER FUNCTION NIL . #<EQ Hash Table{0} 81D03EFF03>) (#:FUNCTOR-MARKER LAMBDA (A) (DECLARE (SYSTEM::SOURCE-LEVEL #<EQ Hash Table{0} 81D03EFF03>)) (DECLARE (LAMBDA-NAME EXAMPLE)) (LAMBDA NIL (BREAK) (PRINT A))))
As we can see, the interpreted closure has code a list and an environment, where A = 10.I doubt that actually, though I don't have LispWorks installed to try it. Modifying a function at runtime as if it were a list is actually the best test to see if your Lisp really represents functions as lists, or as some other internal object that is rendered as a list in the REPL by accessing the stored definition. E.g. both CLISP and guile error out if I try `(car (lambda (a b) (+ a b)))`.
Another good test is to construct a function at runtime and try to call it. To do that you will probaby need to call `eval` or equivalent, just like you would in Lua or Python. Not in Picolisp though, which is why I consider it to be the only truly homoiconic programming language.
You can doubt that. But I have done it. I know that it works.
CL-USER 63 > (defun foo (a) (print 'hey) (print a))
FOO
CL-USER 64 > (foo 'jack)
HEY
JACK
JACK
CL-USER 65 > (function-lambda-expression 'foo)
(LAMBDA (A) (DECLARE (SYSTEM::SOURCE-LEVEL #<EQ Hash Table{0} 81D03EFF03>)) (DECLARE (LAMBDA-NAME FOO)) (PRINT (QUOTE HEY)) (PRINT A))
NIL
FOO
CL-USER 66 > (fifth *)
(PRINT (QUOTE HEY))
CL-USER 67 > (setf (fifth (function-lambda-expression 'foo)) '(print 'hello))
(PRINT (QUOTE HELLO))
CL-USER 68 > (foo 'jack)
HELLO
JACK
JACK
> E.g. both CLISP and guile error out if I try `(car (lambda (a b) (+ a b)))`.Sure, but in CLISP the function is still a list internally. An interpreted function is a record, which stores the code as a list internally. The internally stored list is interpreted.
Python compiles the code to byte code. CLISP has both a list-based interpreter and a byte code interpreter.
Edit: lexical analysis -> lexical scope
So if there is another form that is actually being used for the execution, the change in source must have been detected and propagated to that other form.
Anyway, that situation looks like true blue interpreted functions. There is nested list source you can tweak, and the tweaks somehow go into effect.
CL-USER 100 > (defun unroll (n exp) `(lambda () ,(loop repeat n collect exp)))
UNROLL
CL-USER 101 > (unroll 3 '(foo))
(LAMBDA NIL ((FOO) (FOO) (FOO)))
CL-USER 102 > (eval *)
#<anonymous interpreted function 8020000EC9>
CL-USER 103 > (describe *)
#<anonymous interpreted function 8020000EC9> is a TYPE::INTERPRETED-FUNCTION
CODE (LAMBDA NIL ((FOO) (FOO) (FOO)))
As you can see, the thing is basically the same as a cons cell with two entries the type and the code: (TYPE::INTERPRETED-FUNCTION . (LAMBDA NIL ((FOO) (FOO) (FOO))))
The above Lisp implementation does not use a cons cell, but a different type mechanism to easily and reliably identify the runtime type.I picolisp this is hardwired into the interpreter. The interpreter will also need to check every time at runtime, if the list structure is actually a function and what kind of function it is.
In above Lisp, the type of the function is encoded during EVAL and the check for the type is then a type tag check.
for this example here, using the LispWorks implementation, it also makes no difference for EVAL if it is a function with 10 or with 100000 subforms. The execution time is small. No special processing of the list of subforms takes place. For example the code is not compiled, not converted to byte code, not converted to another representation.
CL-USER 111 > (let ((f (unroll 10 '(foo)))) (time (eval f)))
Timing the evaluation of (EVAL F)
User time = 0.000
System time = 0.000
Elapsed time = 0.000
Allocation = 184 bytes
0 Page faults
GC time = 0.000
#<anonymous interpreted function 8020001DA9>
CL-USER 112 > (let ((f (unroll 100000 '(foo)))) (time (eval f)))
Timing the evaluation of (EVAL F)
User time = 0.000
System time = 0.000
Elapsed time = 0.000
Allocation = 184 bytes
0 Page faults
GC time = 0.000
#<anonymous interpreted function 8020000839>
CL-USER 113 > (defun unroll (n exp) `(lambda () ,(loop repeat n collect exp)))
UNROLLI always thought that `eval` in CL was an un-idiomatic and fairly expensive operation, even for code that is not compiled. You learn something every day...
An interpreted function in a Common Lisp cannot literally just be a lambda expression list, because that would not satisfy the type system. It has to be of type function and a function is not a subtype of list.
What happens is that there is some container object which says "I'm an (interpreted) function", which has slots that hold the raw source code. It might not be a lambda form; for instance, the original lambda might be destructured into parameters and body that are separately held.
There is some API by which the interpreter gets to those pieces and then it's just recursing over the nested lists.
> Another good test is to construct a function at runtime and try to call it.
Common Lisp doesn't provide a standard API for constructing an interpreted function (or even make provisions for the existence of such a thing). Lisps that have interpreted functions may expose a way for application code to construct them without having to eval a lambda expression.
It's just a matter of constructing that aforementioned container object and stuffing it with the code piece or pieces. If that is possible then that object is something you can call.
When you call that function, eval ends up used anyway.
Portability is not a concern. Either you run something 64 bit POSIX or you aren't going to use Picolisp (except if you get your hands on an old 32 bit build). I think it's usually tested by a user on OpenBSD but outside of Debian you're basically on your own.
There are like three basic data types. Fixnums, symbols and the linked list. If you do something similar to what you're showing from SBCL (or LispWorks, didn't read closely enough at first) it'll look pretty much like it does in source.
$ pil +
: (de myfun ()(prinl "yo")(prinl "world"))
: (cdr myfun)
-> ((prinl "yo") (prinl "world"))
: myfun
-> (NIL ((prinl "hey")) (prinl "world"))
: (myfun)
yo
world
-> "world"
: (set (cdr myfun) '(prinl "hey"))
-> (prinl "hey")
: myfun
-> (NIL (prinl "hey") (prinl "world"))
: (myfun)
hey
world
-> "world"
Hijacking the 'de mechanism is not something you'll do often, but looking at definitions like this you'll do a lot, and from time to time navigate it with list browsing functions.It boils down to some very simple interpreter behaviours, and after some time surprises become quite rare. I find it takes off quite a bit of cognitive load when solving non-trivial scripting tasks compared to e.g. bash or Python. Especially since 'fork and 'in/'out are so easy to work with, with the former you just pass in an executable list, '((V1 V2 Vn)(code 'here)(bye)), with the latter you get a direct no-hassle connection to POSIX pipes.
CL-USER 63 > (defun foo (a) (print 'hey) (print a))
FOO
CL-USER 64 > (foo 'jack)
HEY
JACK
JACK
CL-USER 65 > (function-lambda-expression 'foo)
(LAMBDA (A) (DECLARE (SYSTEM::SOURCE-LEVEL #<EQ Hash Table{0} 81D03EFF03>)) (DECLARE (LAMBDA-NAME FOO)) (PRINT (QUOTE HEY)) (PRINT A))
NIL
FOO
CL-USER 66 > (fifth *)
(PRINT (QUOTE HEY))
CL-USER 67 > (setf (fifth (function-lambda-expression 'foo)) '(print 'hello))
(PRINT (QUOTE HELLO))
CL-USER 68 > (foo 'jack)
HELLO
JACK
JACK (LAMBDA (A)
(DECLARE (SYSTEM::SOURCE-LEVEL #<EQ Hash Table{0} 81D03EFF03>))
(DECLARE (LAMBDA-NAME FOO))
(PRINT (QUOTE HEY))
(PRINT A))
If not, one would probably need to do a bit of fiddling to tear away the function from the symbol if one should feel a sudden urge to do so.Perhaps similar to this:
: (de myfun (D)(prinl "heyo") (prinl D))
-> myfun
: myfun
-> ((D) (prinl "heyo") (prinl D))
: (mapcar '((D) (prinl "heyo") (prinl D)) '("world"))
heyo
world
-> ("world")
: (mapcar '(NIL (prinl "hey")) '(lel))
hey
-> ("hey")
: (car myfun)
-> (D)
: (cdr myfun)
-> ((prinl "heyo") (prinl D))
: (cons (car myfun) (cdr myfun))
-> ((D) (prinl "heyo") (prinl D))
: (mapcar (cons (car myfun) (cdr myfun)) '("world"))
heyo
world
-> ("world")
Mostly I use this to get at an implementation so I can test it or a portion of it against some particular value, or just to see how something works. Most builtins are implemented in assembler and their symbols only return a pointer, but for example 'doc is implemented in Picolisp: : doc
-> ((Sym Browser) (raw T) (call (or Browser (sys "BROWSER") "w3m") (pack "file:" (and (= 47 (char (path "@"))) "//") (path (if (get Sym 'doc) (pack @ "#" Sym) "@doc/ref.html")))) (raw NIL))
: de
-> 270351
: macro
-> ("Prg" (run (fill "Prg")))
I really like the Picolisp 'match (https://software-lab.de/doc/refM.html#match ) function. What's the easiest way to do the same in Common Lisp? If it's not obvious from the examples there, it can also be used with character lists, i.e. transient symbols, i.e. strings, chopped up into a list of UTF-8 characters. It's similar to unification in logic programming, which is something Picolisp supports. CL-USER 130 > (defun myfun (d) (print "heyo") (print d))
MYFUN
CL-USER 131 > (let ((source (function-lambda-expression #'myfun)))
(mapcar (eval (list* 'lambda
(second source)
(nthcdr 4 source)))
'("world")))
"heyo"
"world"
("world")
Above can in some ways done in many Lisp implementations. It's in this form simply not widely used. For most applications it's more interesting to use macros to manipulate code, which then can be compiled to efficient code.Pattern matching is much implemented in Lisp.
I had adopted this code for a pattern matcher from a book (LISP, Winston/Horn), probably >30 years ago:
CL-USER 115 > (pmatch:match '(#$a is #$b) '(this is a test))
((B (A TEST)) (A (THIS)))
CL-USER 116 > (pmatch:match '(#$X (d #$Y) #$Z) '((a b c) (d (e f) g) h i))
((Z (H I)) (Y ((E F) G)) (X ((A B C))))
Not to say, that Picolisp isn't great for you, but it is not the only language where lists can be manipulated.Don't think I've made this claim.
Can the #$a &c. be used as variables?
: (and (match '("h" "e" "l" "l" "o" @A ~(chop "ld")) (chop "helloworld")) @A)
-> ("w" "o" "r")That's true, but it sounds a bit as if Lisp interpreters are something very unusual. The syntax and other details may differ, but the general idea of executing source code via an interpreter is very old, often implemented - similar also the idea that the code can be mutable. It's just not very fashionable, since some Lisp dialects are designed such that one wants the compiler to be able to statically check the code for various things, before runtime.
In Common Lisp we would not want to introduce variables into an outer scope by enclosed functions. One would explicitly set up a scope.
Example: this is a macro example, which creates a scope, where the matching match-variables are also Lisp variables.
CL-USER 165 > (pmatch:when-match (append (coerce "hello" 'list)
'(#$a)
(coerce "ld" 'list))
(coerce "helloworld" 'list)
(length a))
3