How to flatten a disembodied property list (DPL)?

Sjoerd,

I assume your list is really like this:

test = list(nil 'a '(1 2 3) 'b nil 'c '( nil d (7 8 9) e (10 11 12) ) 'f '( nil ) 'g '(13 14 15) )

rather than

test = list(nil 'a '(1 2 3) 'b nil 'c '( nil 'd '(7 8 9) 'e '(10 11 12) ) 'f '( nil ) 'g '(13 14 15) )

(otherwise it has quotes embedded within the quoted lists, which wouldn't make sense). Once you quote the outer list, everything within it is quoted.

This recursive (non-destructive) function does (I think) what you want. It seems a rather unusual requirement...

procedure(CCFflattenStrangeDPL(dpl)
  let((key value result)
    dpl=cdr(dpl)
    while(dpl
      key=car(dpl)
      value=cadr(dpl)
      dpl=cddr(dpl)
      result=lconc(result
        copy(
          if(listp(value) && !car(value) then
            CCFflattenStrangeDPL(value)
          else
            value
          )
        )
      )
    )
    car(result)
  )
)

Andrew

Andrew responded as I was coding up a solution, but figured I would post mine as well. Also, please refer to Andrew's post on fixing your DPL structure:

procedure(flatten(data)
  cond(
    (dplp(data)
      foreach(mapcan key reverse(data->?)
        let((val)
          val = get(data key)
          if(listp(val)
            flatten(copy(val)) ; then
            ncons(val)
          )
        )
      )
    )
    (listp(data)
      foreach(mapcan val data
        if(listp(val)
          flatten(copy(val)) ; then
          ncons(val)
        )
      )
    )
    (t
      error("Unexpected value: %L\n" data)
    )
  )
)
test = '(nil a (1 2 3) b nil c (nil d (7 8 9) e (10 11 12)) f (nil) g (13 14 15))
flatten(test) == '(1 2 3 7 8
    9 10 11 12 13
    14 15
)

Hi Andrew,

First of all: I like the procedure name you chose, neat!

Second: I see now what mistake I made when I typed the test DPL.

Regarding the strange usecase:

In my flow, I have documents describing every macro block. In it is the terminal/pin description of that macro. I use Python to extract that information from those documents and generate a functional view (verilog) with all the pins of all macros that go out of the analog toplevel (big macro contaning all other macros) towards the digital macro. This verilog file is used to generate a symbol (create cellview from cellview). This symbol is used as basis to generate the schematic and add all levelshifters (currently over 2000... so way too many to do manually) to this schematic. I have defined the order (left to right) of all pins, such that they align nicely with the location of the sub-macros. Part of the code I've written is that all sub-macros are symbols in a DPL, with the value either being a list of terminal names, or, if sub-orders are defined, a new DPL. For the generation of the pins and adding of the level shifters it's much easier to have a long flat list, rather than a DPL, although that may work as well. So a very specific use-case indeed.

This is how I specify the order:

interfaceVars->layout->order = list( nil )
interfaceVars->layout->order->rfio = nil
interfaceVars->layout->order->tx = list( nil 'paldo nil 'padac nil 'tres nil 'ldo nil 'dtcycl nil 'skew nil 'other nil 'dca nil 'rfcalgen nil )
interfaceVars->layout->order->pmu = list( nil 'macro nil 'cldo nil 'gldo nil 'bgap nil 'other nil )
interfaceVars->layout->order->other = nil
interfaceVars->layout->order->rxif = list( nil 'iir list( nil 'channel1 nil 'channel2 nil ) 'bbamp nil 'adc nil 'lodiv nil 'other nil )
interfaceVars->layout->order->rxfe = list( nil 'lna list( nil 'channel1 nil 'channel2 nil ) 'ldo nil 'mix nil ' rfdet nil 'other nil )
interfaceVars->layout->order->sx = list( nil 'other nil 'logen nil 'dtc nil ' rfsampler nil 'xobuf nil 'rfcounter nil 'dco nil )

The odd thing is however, that in some cases, when I want to look at the content of order:

interfaceVars->layout->order

The order is reversed: first it shows:

(nil sx (nil other nil logen nil
dtc nil rfsampler nil xobuf
nil rfcounter nil dco nil
) rxfe (nil lna nil ldo nil
mix nil rfdet nil other
nil
)
rxif (nil iir nil bbamp nil
adc nil lodiv nil other
nil
) other nil pmu
(nil macro nil cldo nil
gldo nil bgap nil other
nil
) tx (nil paldo nil padac nil
tres nil ldo nil dtcycl
nil skew nil other nil
dca nil rfcalgen nil
) rfio nil
)

So first sx, and finishes with rfio.

Whereas when I do:

interfaceVars->layout->order->?

It shows the proper order:

(rfio tx pmu other rxif
    rxfe sx
)

Unfortunately, with both your solution and the solution of AaronSymko (see below), the result is in the wrong order. Simply reversing it doesn't work: yes, the macro order becomes correct, but the sub-macro order is still incorrect: it starts with rfio and then tx... But with tx for instance, it starts with rfcalgen, in stead of paldo. When I look at the DPL with the list of terminals/pins (I'll take a look at your code to see where I can properly apply the reverse.

The odd thing is: with the numerical example I gave it works fine...

Thank you very much for your quick response, and neat solution, I certainly couldn't do it any shorter or interesting.

With kind regards,

Sjoerd

Hi AAronSymko,

Thank you very much foryour solution and time. Please see my response to Andrews solution as well.

With kind regards,

Sjoerd

Sjoerd,

The trouble is that DPLs are not really intended to be treated as an ordered data structure. The mechanism is that when you add a new slot via dpl->slot=value then if there's no key called "slot" in the DPL already, it will insert it at the beginning (after the initial dummy value in the DPL) because that's the most efficient place to add it. The ->? operator happens to collect the slot names in reverse, but I don't think that's documented behaviour (I would be wary of assuming that). Because you are constructing the top-level slots in sequence, these are reversed - but the lower level DPLs are specified literally as lists and so they are in the order they were specified.

You'd need to know the expected order in each level which adds to the complexity.

This variant might do what you want:

CCFflattenStrangeDPL(interfaceVars->layout->order t) ; t is to reverse the top level

procedure(CCFflattenStrangeDPL(dpl @optional reverse)
  let((key value result subResult)
    dpl=cdr(dpl)
    while(dpl
      key=car(dpl)
      value=cadr(dpl)
      dpl=cddr(dpl)
      subResult=
        copy(
          if(listp(value) && !car(value) then
            ; don't pass down the reverse flag
            ; so only reverse the top level
            CCFflattenStrangeDPL(value)
          else
            value
          )
        )
      if(reverse then
        result=cons(subResult result)
      else
        result=lconc(result subResult)
      )
    )
    if(reverse then
      foreach(mapcan item result item)
    else
      car(result)
    )
  )
)

Andrew

Hi Andrew,

Thank you for the explanation. Your explanation confirms what I see happening.

I'll test the code later today.
By the way: is there an other (prefered, easily "traversable" ) way of specifying order in Virtuoso/SKILL?

With kind regards,

Sjoerd