nconc with (back)quote'd list constants

Whilst I agree to some extent with the sentiment of avoiding nconc, I'm not sure I agree that using mappend (as you've implemented it) is a good idea. The point that the style guide is trying to make, I think, is that if you are doing one-off nconcs to gain performance/memory utilization benefits over append, then it's not worth it. If however you're doing repeated nconcs rather than appends, then really you are approaching the problem the wrong way - repeated nconcs and appends are both bad because they both have to traverse the first list to find the end - so as the list gets longer they take more time. nconc saves copying the second list, but it doesn't save the time to reach the end of the first list. Your mappend is simply calling append repeatedly - doing this with nconc is (almost) as bad.

mapcan, like most destructive functions, can definitely be useful if care is taken because of the side effects. If you can guarantee that the return value of the function is a new (non-shared) list, then it is safe and advantageous to use. Because there are relatively few destructive functions, it doesn't take much effort to look for potential bugs like this.

Potentially you could just do:

(defun CCFmappend (func @rest lists)
  (apply 'mapcan (lambda (@rest args) (copy (apply func args))) lists))

which generalizes it to multiple lists, and uses copy to guarantee a unique list. If you can guarantee  that the list in your mapping function isn't shared though, it's not needed and you can save a little time and garbage - although it's only going to generate as much garbage as the length of the final list in that case, so the savings may not be worth it.

Note I didn't do any profiling of this to check.

Andrew.

Oh, and by the way, I always recommend against defining your own "core" functions without prefixes, unless they are in (say) a lexical scope where you can see the definition too. The reason is that for a casual reader, they look like standard functions - and secondly if Cadence then defines a core function which happens to have the same name, your code will break...

In your example, you used a function foldl1.

Andrew.

Andrew Beckett said:

Potentially you could just do:

(defun CCFmappend (func @rest lists)
  (apply 'mapcan (lambda (@rest args) (copy (apply func args))) lists))

which generalizes it to multiple lists, and uses copy to guarantee a unique list.

Thanks Andrew!  I had not thought of using copy, which I think is rather brilliant.

Andrew Beckett said:

If you can guarantee that the list in your mapping function isn't shared though, it's not needed and you can save a little time and garbage - although it's only going to generate as much garbage as the length of the final list in that case, so the savings may not be worth it.

Yeah, it's a relatively small penalty for me since my lists are usually small.  Then again, I've used mapcan for years, and only perhaps once or twice have I ever run into this stale-list problem.  Maybe a better solution is to prefer consing fresh lists to using quoted constants?

 Ah, I still remember that fateful day when I discovered that a caller can modify a quoted constant list inside a procedure....

ILS-> (defun foo () '(1 2 3))
foo
ILS-> (remd 2 (foo))
(1 3)
ILS-> (foo)
(1 3)
ILS-> pp(foo)
(procedure (foo)
    (quote 
	(1 3)
    )
)
nil

Totally blew my mind. :)

Andrew Beckett said:

Whilst I agree to some extent with the sentiment of avoiding nconc, I'm not sure I agree that using mappend (as you've implemented it) is a good idea. The point that the style guide is trying to make, I think, is that if you are doing one-off nconcs to gain performance/memory utilization benefits over append, then it's not worth it. If however you're doing repeated nconcs rather than appends, then really you are approaching the problem the wrong way - repeated nconcs and appends are both bad because they both have to traverse the first list to find the end - so as the list gets longer they take more time. nconc saves copying the second list, but it doesn't save the time to reach the end of the first list. Your mappend is simply calling append repeatedly - doing this with nconc is (almost) as bad.

One thing SKILL has which I have not yet found in Common Lisp is tconc and lconc.  Do you think it would be even more efficient to define CCFmappend in terms of tconc and lconc rather than mapcan? 

Andrew Beckett said:

Oh, and by the way, I always recommend against defining your own "core" functions without prefixes, unless they are in (say) a lexical scope where you can see the definition too. The reason is that for a casual reader, they look like standard functions - and secondly if Cadence then defines a core function which happens to have the same name, your code will break...

In your example, you used a function foldl1.

Yes, that code originally lived in a lexical scope (my own personal module system), and I totally forgot it was unprefixed!

This reminds me of a broader philosophical issue, however.  One feature of Lisp that has gathered much praise over the decades is how functions defined by the programmer look and feel just like functions built into the language.  Without closer inspection, you wouldn't know that fold1 wasn't a SKILL primitive operator.

I always hear this being described as an advantage, adding to Lisp's flexibility and expressiveness.  However, in systems like Emacs and Virtuoso that lack package/module systems, there is a strong push in the opposite direction, for programmers to name their functions in a conspicuous manner (i.e. with "user" prefixes) so as to avoid inadvertently clashing with builtins!

I have mixed feelings about this.  In the absense of modules/packages, prefixing makes sense from a maintenance point of view.  However, prefixing destroys that sense of smoothly extending a core language, because SKILL functions all look likeThis(), but my functions have to look CCFlikeThis(), with big ugly capital letters on the front. 

If I want to add some Common Lisp primitives like "first", "second", "third", etc. to SKILL, I technically ought to name them "CLfirst", "CLsecond", "CLthird", ....   The point is to make SKILL look more like CL, but the effort is largely nullified by putting capital CL at the beginning of everything.  (Emacs has the same problem: cl-first, cl-second...  At least it's lowercase.) 

I guess there's no point in trying to make SKILL look like another dialect, because such an effort can never be 100% successful without writing a full interpreter.  However, SKILL itself has added gratuitous primitives to its core to make itself look more like Scheme!  For example, eq? is exactly like eq.  Why do we need both of them?  If you're willing to add eq?, why not add zero?, one?, number?, positive?, and procedure? as well?  I sense a half-hearted attempt at Scheme-compatibility.  Everyone knows SKILL++ can never be 100% compatible with Scheme, so why did they even try?  Why flood the namespace with redundant Schemey names for the Maclispy/Common Lispy primitives SKILL inherited from Franz Lisp?  I even made a list of them all:

boolean? (obj)

define (g_general g_general \@optional g_general \@rest g_general "ggg")

eq? (g_general g_general "gg")

equal? (g_general g_general "gg")

eqv? (g_general g_general "gg")

even? (g_general "g")

for_each (u_function l_list "ul")

integer? (g_general "g")

list? (g_general "g")

negative? (g_general "g")

null? (g_general "g")

odd? (g_general "g")

pair? (g_general "g")

real? (g_general "g")

set! (s_symbol g_general "sg")

set_car (l_list g_general "lg")
set_cdr (l_list l_list "ll")

setcar (l_list g_general "lg")
setcdr (l_list l_list "ll")

symbol? (g_general "g")

symbolToString (symbol "s")

vector? (g_general "g")

All of these are redundant names.  If you are going to add all the IEEE Scheme names for things, you should at least finish the job!  Will the remaining primitives ever be added?  Why even bother anyway?

tweeks said:

One thing SKILL has which I have not yet found in Common Lisp is tconc and lconc.  Do you think it would be even more efficient to define CCFmappend in terms of tconc and lconc rather than mapcan? 

I don't think there would be any benefit in doing that. tconc and lconc still destructively modify the list - and each time you call them it has to do a cdr to find the end of the list (not that expensive, but mapcan is more direct, I think).

Andrew.

I was looking at name spaces to give us the ability to create packages, this is absolutely important to PDK development and delivery cycles. If the code is developed within the PDK version namespace, the same function can exist in VM in multiple namespace and my pcell would evaluate in the proper version of the namespace.

Much of duplicate function problem is legacy, where application developers needed particular functionality and created their own, applying their own knowledge of lisp and naming conventions to the implementation. Although naming rules may have been established for the initial development, the tools are built by application developers and in the past (long ago, in a valley far away), the naming guidance was not strictly enforced. When I was there, Virtuoso R&D had engaged in major efforts to increase the software quality with methodologies such as design and code reviews to minimize these issues. Quality has improved greatly since I left. {8^)

Once a command is created and used, even internally, they can be hard to factor out without a giant review of the existing code. Some of them have evolved into aliases but others are buried in contexts and the developers are long gone. If, as a customer, I am using set_car and you eliminate it, you just broke my design flow. And what if my source code is no longer available (I blame the guy before me)...

Ted

Andrew Beckett said:

I don't think there would be any benefit in doing that. tconc and lconc still destructively modify the list - and each time you call them it has to do a cdr to find the end of the list (not that expensive, but mapcan is more direct, I think).

That is true.  My thinking was, if you're going to append 100 lists (or n lists in general) to an initial list, then it's faster to create a tconc structure and call lconc 100 times than to call append or nconc 100 times, because then you only need to walk down the initial list once.  Indeed, this would seem to be tconc's raison d'être. 

Hey wait a minute--shouldn't mapcan use tconc internally rather than nconc?

theopaone said:

 

I was looking at name spaces to give us the ability to create packages, this is absolutely important to PDK development and delivery cycles. If the code is developed within the PDK version namespace, the same function can exist in VM in multiple namespace and my pcell would evaluate in the proper version of the namespace.

You mean using the SKILL makeNamespace() mechanism?  Andrew said it is not ready for primetime.

However, since environments are first-class in SKILL++, I think someone could make a pretty good namespace/module/package system out of them.... :)  I wish someone would do that and post it here!

theopaone said:

 Much of duplicate function problem is legacy, where application developers needed particular functionality and created their own, applying their own knowledge of lisp and naming conventions to the implementation. Although naming rules may have been established for the initial development, the tools are built by application developers and in the past (long ago, in a valley far away), the naming guidance was not strictly enforced. When I was there, Virtuoso R&D had engaged in major efforts to increase the software quality with methodologies such as design and code reviews to minimize these issues. Quality has improved greatly since I left. {8^)

Once a command is created and used, even internally, they can be hard to factor out without a giant review of the existing code. Some of them have evolved into aliases but others are buried in contexts and the developers are long gone. If, as a customer, I am using set_car and you eliminate it, you just broke my design flow. And what if my source code is no longer available (I blame the guy before me)...

Ted

Haha!  Thank you very much for the inside perspective, Ted. :)

I think I've answered a bit about why SKILL has adopted parts of Schema and Common LISP an another thread, but one little point:

tweeks said:

Hey wait a minute--shouldn't mapcan use tconc internally rather than nconc?

It doesn't do either. It keeps track of the end of the list as it goes along - so there's no need to actually store it in a tconc structure. It certainly doesn't use nconc.

Andrew.

Andrew Beckett said:

Hey wait a minute--shouldn't mapcan use tconc internally rather than nconc?

It doesn't do either. It keeps track of the end of the list as it goes along - so there's no need to actually store it in a tconc structure. It certainly doesn't use nconc.

[/quote]

The reference manual lied to me!

mapcan

mapcan(u_funcl_arg1[ l_arg2 ... ])=> l_result

Description

Applies a function to successive elements of the argument lists and returns the result of appending these intermediate results. All of the lists should have the same length.

Specifically, a function is applied to the car of all the argument lists, passed in the same order as the argument lists. The second elements are processed next, continuing until the last element is processed. The result of each call to u_func must be a list. These lists are concatenated using nconc and the resulting list of all the concatenations is the result of mapcan. The argument u_func must accept as many arguments as there are lists.

Tom,

I just took a look in the source code, and actually it's effectively using tconc. It keeps a structure like a tconc inside - in other words, a pointer to the beginning of the list, and a pointer to the last cons cell. This is all done in the virtual machine rather than using tconc itself.

I suspect that the manual describes it in terms of nconc because there's no external visibility of the tconc and that might confuse people. However, the wording suggesting that it's using nconc might lead you to suspect that it has the efficiency (or rather inefficiency) of nconc.

I filed CCR 1318514 to make the documentation a bit more truthful!

Regards,

Andrew.