strpack update - data alignment

[Patrick O'Leary]

When I first started talking about strpack (back when I was calling it struct.jl) one of the not-implemented-yet plans was to have a flexible way of specifying padding other than the explicit and "native" schemes implemented by Python's struct module. I think I've come up with something pretty good, but I'd like to hear your thoughts. Here's the teaser:

julia> show_struct_pads(s"hIdhqbB", align_default)

0x0000 [Int16-------------][PadByte-][PadByte-][Uint32--------------------------------]
0x0008 [Float64-----------------------------------------------------------------------]
0x0010 [Int16-------------][PadByte-][PadByte-][PadByte-][PadByte-][PadByte-][PadByte-]
0x0018 [Int64-------------------------------------------------------------------------]
0x0020 [Int8----][Uint8---][PadByte-][PadByte-][PadByte-][PadByte-][PadByte-][PadByte-]

julia> show_struct_pads(s"hIdhqbB", align_packed)

0x0000 [Int16-------------][Uint32--------------------------------][Float64------------
0x0008 -----------------------------------------------------------][Int16-------------]
0x0010 [Int64-------------------------------------------------------------------------]
0x0018 [Int8----][Uint8---]

julia> show_struct_pads(s"hIdhqbB", align_packmax(4))

0x0000 [Int16-------------][PadByte-][PadByte-][Uint32--------------------------------]
0x0008 [Float64-----------------------------------------------------------------------]
0x0010 [Int16-------------][PadByte-][PadByte-][Int64----------------------------------
0x0018 ---------------------------------------][Int8----][Uint8---][PadByte-][PadByte-]

julia> show_struct_pads(s"hIdhqbB", align_x86_pc_linux_gnu)

0x0000 [Int16-------------][PadByte-][PadByte-][Uint32--------------------------------]
0x0008 [Float64-----------------------------------------------------------------------]
0x0010 [Int16-------------][PadByte-][PadByte-][Int64----------------------------------
0x0018 ---------------------------------------][Int8----][Uint8---][PadByte-][PadByte-]

The alignment strategies are specified by—what else—a composite type called DataAlign. While it has an API that you'd normally use, it's quickest to show you the definition and go from there.
type DataAlign
    ttable::Dict
    # default::(Type -> Integer); used for bits types not in ttable
    default::Function
    # aggregate::(Vector{Integer} -> Integer); used for composite types not in ttable
    aggregate::Function
end

The ttable field is the type replacement table, which allows ad hoc alignment specifications for any type. The two functions apply if the type in question isn't in the table; which function depends on whether the type is a simple type or a composite (aggregate, using the term I see in ABI documentation). The API lets you compose definitions. If you wanted to have a strategy based on align_x86_pc_linux_gnu, but ensuring 8-byte alignment for each struct (like using __attribute__ (( align(n) ))), you can specify:

align_x86_pc_linux_gnu_8 = align_structpack(align_x86_pc_linux_gnu, 8)

There are other API functions to do other combinations, including adding items to the alignment table. That one uses a new method on Dicts which I've called merge; I've implemented it the easy way but there's probably a more efficient way which should probably go into base/.

None of this is tied in to the rest of strpack yet, so you can't use these to do reads/writes. Also, there's no predefined platform-native alignment. I don't think we can do that without a ccall, but if it can be done without a ccall, please let me know how.

Other developments:

• I've dumped the Nothing-typed padding hacks in favor of a bitstype named PadByte. I'd have done that sooner, but I didn't think of it, since defining your own bitstype is a rather unusual feature.
• Similarly, the string specifying endianness is gone in favor of type dispatch.

The new stuff is at the bottom: https://github.com/pao/julia/blob/topic/strpack/extras/strpack.jl

[Stefan Karpinski]

I definitely need to read through this a few more times, but from a quick first read through, this looks amazing.

[Tim Holy]

Wow, Patrick, this is amazing. (Note to others: I understood the
show_struct_pads output better once I displayed Patrick's message with a fixed-
width font.)

I don't know much about packing, but I presume that packing is defined in the
source, right? So it's not the case that it will depend upon whatever compiler
flags were set when the library was compiled?

What happens if a structure has a structure member? Do you just concatenate
the strings?

--Tim

On Saturday, April 28, 2012 07:03:33 PM Patrick O'Leary wrote:
> When I first started talking about strpack (back when I was calling it
> struct.jl) one of the not-implemented-yet plans was to have a flexible way
> of specifying padding other than the explicit and "native" schemes
> implemented by Python's struct module. I think I've come up with something
> pretty good, but I'd like to hear your thoughts. Here's the teaser:
>
> julia> show_struct_pads(s"hIdhqbB", align_default)
>
> 0x0000
> [Int16-------------][PadByte-][PadByte-][Uint32-----------------------------
> ---] 0x0008
> [Float64--------------------------------------------------------------------

> ---] 0x0010

> [Int16-------------][PadByte-][PadByte-][PadByte-][PadByte-][PadByte-][PadBy
> te-] 0x0018
> [Int64----------------------------------------------------------------------

> ---] 0x0020

> [Int8----][Uint8---][PadByte-][PadByte-][PadByte-][PadByte-][PadByte-][PadBy
> te-]
>
> julia> show_struct_pads(s"hIdhqbB", align_packed)
>
> 0x0000
> [Int16-------------][Uint32--------------------------------][Float64--------
> ---- 0x0008
> -----------------------------------------------------------][Int16----------
> ---] 0x0010
> [Int64----------------------------------------------------------------------

> ---] 0x0018 [Int8----][Uint8---]

>
> julia> show_struct_pads(s"hIdhqbB", align_packmax(4))
>
> 0x0000
> [Int16-------------][PadByte-][PadByte-][Uint32-----------------------------
> ---] 0x0008
> [Float64--------------------------------------------------------------------
> ---] 0x0010
> [Int16-------------][PadByte-][PadByte-][Int64------------------------------

> ---- 0x0018

> ---------------------------------------][Int8----][Uint8---][PadByte-][PadBy
> te-]
>
> julia> show_struct_pads(s"hIdhqbB", align_x86_pc_linux_gnu)
>
> 0x0000
> [Int16-------------][PadByte-][PadByte-][Uint32-----------------------------
> ---] 0x0008
> [Float64--------------------------------------------------------------------
> ---] 0x0010
> [Int16-------------][PadByte-][PadByte-][Int64------------------------------

> ---- 0x0018

> ---------------------------------------][Int8----][Uint8---][PadByte-][PadBy
> te-]
>

> - I've dumped the Nothing-typed padding hacks in favor of a bitstype

> named PadByte. I'd have done that sooner, but I didn't think of it,
> since defining your own bitstype is a rather unusual feature.

> - Similarly, the string specifying endianness is gone in favor of type

[Patrick O'Leary]

On Sunday, April 29, 2012 8:10:49 AM UTC-5, Tim wrote:

Wow, Patrick, this is amazing. (Note to others: I understood the
show_struct_pads output better once I displayed Patrick's message with a fixed-
width font.)

Should be fine if you're viewing on the web or in HTML. It's the one thing it's more useful than annoying for.

 

I don't know much about packing, but I presume that packing is defined in the
source, right? So it's not the case that it will depend upon whatever compiler
flags were set when the library was compiled?

It depends. If you're trying to use a C interface compiled on the same platform, you'll need platform-native alignment. That isn't done yet; I've got to write a little C to discover it (though realistically, align_default will probably be correct unless you're on x86 Linux). If you're working with some kind of serialization, it should have explicitly defined rules for which you can either define an appropriate DataAlign or explicitly insert PadBytes into the structure and use align_packed.

What happens if a structure has a structure member? Do you just concatenate
the strings?

This works with the existing strpack stuff that's been in master. I'd use "interpolate" rather than "concatenate" if I were to put it in those terms.

[Stefan Karpinski]

Here's a slightly reformatted version of Patrick's email:

https://raw.github.com/gist/ce4bf156d43dc42e0deb/c91cd886fb2528a66b7da0a84f5c726a92ae7261/gistfile1.txt

[Patrick O'Leary]

Thanks, Stefan.

[Stefan Karpinski]

It's not quite clear to me why the alignment specification is an argument to the show_struct_pads (which I think should be called show_struct_layout) function instead of being part of the struct specification itself. Shouldn't full layout be part of the struct specification?

[Patrick O'Leary]

I haven't tied anything in yet; the goal for yesterday was to get the memory layouts correct given an alignment, and a separate argument was the shortest path to prototype. (The meat of course is the pad() method, not the show_struct_pads() method).

I'm not yet sure how deep this should connect. One issue I see with making them a part of Struct is that these won't work well with the s"" reader macro. Making them dynamic also means you can read with one alignment and write with another--that's also an argument for allowing endianness to be redefined, which the current version does not support. I also don't think it will play well with the Struct{T}(::Type{T}) constructor if pad bytes are a static part of the type, since we can't edit the existing type we're building machinery for in that case.

Note to self, I think since the PadBytes are now represented explicitly in the type, they'll be accessible via indexing. Need to fix that.

The show method is so I can visualize and debug, so I don't care what we call it :) The name made sense when I wrote it, but agree it does a bit more than that now. Renamed.

[Stefan Karpinski]

Another thought is that I find struct specifiers completely unreadable. Even though I've used the pack and unpack functions in Perl and Ruby hundreds of times, I have to pull up the damned documentation *every* time to lookup what the letter specifiers mean. Could we do something a little saner that matches Julia's type names better and is a bit more combinatorial instead? Something like this:

i8     Int8

i16    Int16

i32    Int32

i64    Int64

u8     Uint8

u16    Uint16

u32    Uint32

u64    Uint64

f32    Float32

f64    Float64

b1     1-bit Bool

b8     8-bit Bool

b32    32-bit Bool

c      Char (32-bit)

s<n>   n-byte UTF-8 string

s      NUL-terminated UTF-8 string

_<n>   n-byte padding

For clarity, I would suggest that spaces and commas be allowed and completely ignored in struct specifications, letting the programmer organize things visually as they see fit.

Bools are an interesting case because they are represented by ints in C, which are (typically) 32-bits, but in C++ bool is an actual type and it's 8-bit. C structs also support packed bitfields, so there are lots of different cases. Maybe b1 could mean a single-bit boolean, while b8 would be a bool represented as 8-bits, while b32 would be a bool represented as a 32-bit int. Obviously, we could support 16-bit and 64-bit versions too, just for the sake of completeness.

The numbers are a little mixed-up because some things use bit counts and other use byte counts, but giving a string length in bits is really weird. Doing everything in bytes makes sense, but there's a strong case to be made for b1, although maybe b without a number could mean a 1-bit Bool field in that case.

For endianness specifications, it would be nice to be able to just use the non-standard string literal suffix business to specify it for the whole thing:

s"i32 f32"  => native

s"i32 f32"b => big-endian

s"i32 f32"l => little-endian

I'm not sure how useful it really is be to be able to specify per-field endianness. It's hard to imagine actual use cases where that's a reasonable thing to do.

There's also a question of arrays and repetition. Consider the case where a struct contains an inline array of 12 doubles. Maybe that could be written like this:

s"i32 f64[12]"

This struct would have two fields, the second of which is an array. Repetition is related but slightly different: you may want to avoid writing out 12 individual fields; we could possibly use ^ for this:

s"i32 f64^12"

This struct would have 13 fields, rather than two.

Yet another thought: what about named fields? Something like this might make sense:

s"count: i32, values: f64[12]"

This may be starting to look a little too much like a mini programming language though.

[Mike Nolta]

Starting to look a lot like erlang's bit syntax.

-Mike

[Patrick O'Leary]

On Sunday, April 29, 2012 2:00:37 PM UTC-5, Stefan Karpinski wrote:

Another thought is that I find struct specifiers completely unreadable. Even though I've used the pack and unpack functions in Perl and Ruby hundreds of times, I have to pull up the damned documentation *every* time to lookup what the letter specifiers mean. Could we do something a little saner that matches Julia's type names better and is a bit more combinatorial instead? Something like this:

Reasonable, though it's a writing new code vs. porting old code thing.
 

For clarity, I would suggest that spaces and commas be allowed and completely ignored in struct specifications, letting the programmer organize things visually as they see fit.

Already support it (and comments with # to eol, just like regex with /x).
 

Bools are an interesting case because they are represented by ints in C, which are (typically) 32-bits, but in C++ bool is an actual type and it's 8-bit. C structs also support packed bitfields, so there are lots of different cases. Maybe b1 could mean a single-bit boolean, while b8 would be a bool represented as 8-bits, while b32 would be a bool represented as a 32-bit int. Obviously, we could support 16-bit and 64-bit versions too, just for the sake of completeness.

We've also got these BitVector things now too.
 

The numbers are a little mixed-up because some things use bit counts and other use byte counts, but giving a string length in bits is really weird. Doing everything in bytes makes sense, but there's a strong case to be made for b1, although maybe b without a number could mean a 1-bit Bool field in that case.

For endianness specifications, it would be nice to be able to just use the non-standard string literal suffix business to specify it for the whole thing:

s"i32 f32"  => native

s"i32 f32"b => big-endian

s"i32 f32"l => little-endian

That's not really any different than the existing mechanism which uses the leading character in the string, just put in a different spot. (Goal 1 was "do what Python does," since it was something I already understood.) This is a more Julian approach, it would just need to be done.
 

I'm not sure how useful it really is be to be able to specify per-field endianness. It's hard to imagine actual use cases where that's a reasonable thing to do.

I'm not sure if Perl or Ruby support this. Python does not.

 

There's also a question of arrays and repetition. Consider the case where a struct contains an inline array of 12 doubles. Maybe that could be written like this:

s"i32 f64[12]"

This struct would have two fields, the second of which is an array. Repetition is related but slightly different: you may want to avoid writing out 12 individual fields; we could possibly use ^ for this:

s"i32 f64^12"

This struct would have 13 fields, rather than two.

The current implementation does not differentiate between these. Would exponentiation or multiplication be the more appropriate analogy for the latter case?

Yet another thought: what about named fields? Something like this might make sense:

s"count: i32, values: f64[12]"

Already supported with different syntax.

 

This may be starting to look a little too much like a mini programming language though.

It is already a DSL, the question is how big do you want it? This is starting to look difficult to regex your way through.

[Stefan Karpinski]

On Sun, Apr 29, 2012 at 3:17 PM, Mike Nolta <mi...@nolta.net> wrote:

Starting to look a lot like erlang's bit syntax.

That's cool with me — I'm all for stealing good ideas :-)

[Patrick O'Leary]

On Sunday, April 29, 2012 2:17:24 PM UTC-5, Mike Nolta wrote:

Starting to look a lot like erlang's bit syntax.

 
I had forgotten about that. I'm not quite sure I want to go below the byte level just yet. The best thing to do might just be to declare a small bits type if you really need it, and use that explicitly when defining your struct.

[Mike Nolta]

Me too -- i think it's one of erlang's best features.

-Mike

[Stefan Karpinski]

Ok, sounds like you're all over this. I'm not sure how much of a concern porting struct code from Python really is and Perl and Ruby already have a different and incompatible pack/unpack DSL, so I feel like a fresh start that's easier to understand is pretty defensible.

Regarding * versus ^ for repetition, Julia strings use * for concatenation and ^ for repetition already, which is more commensurate with the mathematical view of strings as a non-commutative monoid. Using + for concatenation is an algebraic horror because string concatenation is very non-commutative, while + is only used to denote a commutative operation in algebra. Using * for repetition is also weird because it's a little hard to remember if you should write str*n or n*str. With ^ it's completely obvious: the power has to be the count and the "base" has to be the string. This also allows using the power_by_squaring algorithm to do more efficient string repetition, although I created the RepString type instead (which Jeff really hates).

[Tim Holy]

On Sunday, April 29, 2012 03:00:37 PM Stefan Karpinski wrote:
> Another thought is that I find struct specifiers completely unreadable.

I have no experience using this type of thing in other languages, so I have a
naive question: how often will we need them directly? Being able to say
Struct(Range1{Int}) seems like it circumvents the need to specify them
directly.

--Tim

[Stefan Karpinski]

I've used pack/unpack extensively in Perl/Ruby, but it's possible that something more like what you suggest would make sense in Julia because we can actually talk about types in a first-class way that other dynamic languages can't. But I still think having this sort of ability is good. Let's see where it goes.

[Patrick O'Leary]

On Sunday, April 29, 2012 2:34:23 PM UTC-5, Stefan Karpinski wrote:

Ok, sounds like you're all over this. I'm not sure how much of a concern porting struct code from Python really is and Perl and Ruby already have a different and incompatible pack/unpack DSL, so I feel like a fresh start that's easier to understand is pretty defensible.

It's probably not a concern. Just starting from what I know best (as should be clear from my introductory post on the topic). I may have to mangle your syntax a bit, but your shortnames seem reasonable. Incidentally, long names are already useable with the current syntax: s"[4]{Int32}" is an array of Int32s, for instance.

 

Regarding * versus ^ for repetition, Julia strings use * for concatenation and ^ for repetition already, which is more commensurate with the mathematical view of strings as a non-commutative monoid. Using + for concatenation is an algebraic horror because string concatenation is very non-commutative, while + is only used to denote a commutative operation in algebra. Using * for repetition is also weird because it's a little hard to remember if you should write str*n or n*str. With ^ it's completely obvious: the power has to be the count and the "base" has to be the string. This also allows using the power_by_squaring algorithm to do more efficient string repetition, although I created the RepString type instead (which Jeff really hates).

Huh. I did not notice that ^ and * were already operators on strings. Works for me!

[Kevin Squire]

This came up in the tuple concatenation discussion, but this seemed like the better place to respond.

Regarding * versus ^ for repetition, Julia strings use * for concatenation and ^ for repetition already, which is more commensurate with the mathematical view of strings as a non-commutative monoid. Using + for concatenation is an algebraic horror because string concatenation is very non-commutative, while + is only used to denote a commutative operation in algebra. Using * for repetition is also weird because it's a little hard to remember if you should write str*n or n*str. With ^ it's completely obvious: the power has to be the count and the "base" has to be the string. This also allows using the power_by_squaring algorithm to do more efficient string repetition, although I created the RepString type instead (which Jeff really hates).

Is the reasoning behind "*" is to treat strings as monoids, and "*" as the "dot" operator?  I was beating my head against the wall earlier this week, trying to figure out how to concatenate strings with out using strcat (and of course, it didn't occur to me to just grep the source...).  Despite having read this post before, the idea of using "*" totally slipped my mind, because the idea seemed so foreign to me.  I can always redefine my own functions, but could this be rethought?  

According to the ultimate source of all information (http://en.wikipedia.org/wiki/Comparison_of_programming_languages_(strings)#Concatenation) most programming languages use "+" as a (non-commutatitive) concatenation operator.  Given that julia has a boring syntax that attempts to look like other languages (according to Stephan in the Stanford talk?), and that no one uses "*" (probably because of possible confusion) could we abandon the need for "+" to be commutative and just use it?  

julia> (+)(s::String...) = strcat(s...)

julia> "abcd"+"def"

"abcddef"

I did try some of the other possibilities shown in the wikipedia link.  Unfortunately, some of them don't work:

julia> (++)(s::String...) = strcat(s...)

syntax error: invalid method name (call + +)

julia> (..)(s::String...) = strcat(s...)

julia> ..("asdf", "asdf")

"asdfasdf"

julia> "asdf" .. "adf"

syntax error: extra input after end of expression

julia> "asdf" (..) "adf"

syntax error: extra input after end of expression

Even just using whitespace to combine strings would be nice:

julia> "abcd""def"

"abcddef"

julia> "abcd" "def"

syntax error: extra input after end of expression

Thoughts?

Kevin

[Elliot Saba]

Using "+" for string concatenation seems like a no-brainer to me.  Many, many languages do this, and of those that don't, I usually find myself wishing they did.

As for multiplication and exponentiation on strings, "asd"*2 becoming "asdasd" makes a strange kind of sense to me, but that is only because I'm used to python's [0,1,2]*2 == [0,1,2,0,1,2] semantics.

Using exponentiation doesn't make much sense to me, because that operator is already pretty overloaded. (Exponentiation, bitwise XOR, etc....)

-E

[Stefan Karpinski]

None of this really address any of the substance of my argument in that post other than "that's not how other languages do it", which I find less than convincing. Under the */^ scheme, power-by-squaring algorithm is a perfectly reasonable algorithm for string repetition. I guess I'd rather just not have operators for string concatenation or repetition at all and use functions.

[Kevin Squire]

Your argument is mathematically quite beautiful, but to me, not very practical.  I was simply suggesting to keep the syntax familiar for people coming from other languages.  

Kevin

[Stefan Karpinski]

That is a reasonable argument — although there's a LOT of disagreement between languages with regards to string concatenation operators, as that wikipedia page shows. The languages in the + camp do seem to be the most popular and mainstream ones, however.

[Stefan Karpinski]

Jeff recently proposed (to me) that we replace the strcat() function with just string(), making it turn the concatenation of its arguments into a string via printing to a MemIO object. If we shorten that name a bit it makes it more reasonable to just use a function: str(). The repeat() could be similarly shortened to rep(s,n). For what it's worth, str is the name that Clojure uses — and Clojure generally has rather good taste.

[Kevin Squire]

That's true.  Even though I don't program Haskell, I actually like (++), but julia doesn't seem to like it.

Kevin

[Stefan Karpinski]

That's not an operator in Julia's syntax (currently). If it were, I would probably want to make it an increment operator like it is in C (`++x` would mean `x += one(x)`, incrementing by a value of the appropriate type).

[John Myles White]

Just putting this out there for fun: if we had an ^ operator for strings, we could start using Julia code to contribute beautiful code to the literature on algorithms for testing whether strings are square-free.

 -- John

[Stefan Karpinski]

Can you elaborate on that? I'm unclear on whether this is arguing for or against * as a string concatenation operator.

[John Myles White]

It's an argument for * as a concatenation operator.

 -- John

[Toivo Henningsson]

On May 10, 10:03 pm, Stefan Karpinski <ste...@karpinski.org> wrote:
> That is a reasonable argument — although there's a LOT of disagreement
> between languages with regards to string concatenation operators, as that
> wikipedia page shows. The languages in the + camp do seem to be the most
> popular and mainstream ones, however.

I really like the * for string concatenation. I always thought there
was something fishy with string + string, but I didn't know what it
was until I read your argument for using * instead. Sure, it deserves
a spot in the manual. But you get used to it soon enough. I really
appreciate Julia for being a more mathematically consistent language
than most.