Hacker News Reader

Comment by mppm | Hacker News Reader

> The debugger output of the currently running function looks like a linked list to me. I could modify it destructively, if I wanted.

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.

View on HN

> I doubt that actually

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.

Mmh. Like I said, I'm not familiar with LispWorks, so take this with a grain of salt, but to me it looks like the system is just retrieving the original source expression that it keeps around in addition to the executable representation. But this is ultimately a question of implementation. My original point was that in Picolisp runtime-constructed lists are directly executable, without any processing. An unroller function that takes an action `foo` and a runtime number, e.g. 3, would return `'(() (foo) (foo) (foo))` and that would be it. In other Lisps you would first build the equivalent of this list and then pass it to `eval` to make it actually executable. Whether this step is expensive or not depends on the system. E.g. efficient closures require scanning the containing scopes and creating minimal state objects. Just storing the parent environment pointer would be super-inefficient and would prevent the entire environment from being garbage-collected, hence my claim that dynamic scope is the only thing that really makes sense in a direct-interpreted lisp, and that the presence of lexical scope implies some nontrivial processing before execution, though not necessarily as extensive as what would usually be called compilation.

Edit: lexical analysis -> lexical scope

    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)))
    UNROLL

I stand corrected, thank you :)

I 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...

A Common Lisp implementation may implement EVAL by calling the compiler. That would be more expensive. Several Common Lisp implementation use EVAL to create an interpreted function and then the user can call COMPILE to compile these.

But the behavior changed accordingly when lispm mutated the source expression.

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.

> (car (lambda (a b) (+ a b)))

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.

Reply on news.ycombinator.com