Suggestions for algorithmic analysis of Lisp programs?

Question

What operations in Common Lisp programs should be considered primitive enough to take one “step” in algorithmic analysis? How widespread are modern leaflets in their implementation?

Of course, arithmetic with small integers will be considered one step, but what about large numbers? What about the difference between reverse and nreverse ? In particular, nreverse theta reverse ? What about all array and sequence operations? Also, how macros appear inside - how should I think of macros when analyzing complexity?

Answer 1

• Do not try to find the bottom layer of homogeneous "single steps", just know what is O (1) and what is not.
• The addition of "large numbers" ( bignum s) should be O (log n), where n is the largest of the integers. There are many different algorithms for multiplication; I am not an expert in this field, and this is likely to be implementation specific.
• reverse and nreverse can be implemented O (n) ( reverse using the cdr-input-and-cons-output; nreverse by exchanging pointers during cdring). If I understand the unfamiliar term "theta" correctly, then yes. Please note, however, that the CL standard does not give any guarantees regarding the complexity of time.
• The built-in sequence operations are usually implemented by choosing a realistic implementation in the form of an array or a list depending on the type of argument, and therefore it should be expected that this is a normal efficient algorithm for this data type.
• Macros simply expand into different code. You can look at their extension or see what they document, or make an educated guess about using an algorithm that uses their extension. The complexity of the macro expander does not matter at all (if you are not using eval / compile , in which case you need to think about the complexity of the implementation compiler), since it runs once during compilation; only extended code matters.