Discussion of Homotopy Type Theory and Univalent Foundations
 help / color / mirror / Atom feed
* [HoTT] two's complement integers
@ 2021-03-04 20:43 Michael Shulman
  2021-03-04 21:11 ` Martin Escardo
  0 siblings, 1 reply; 8+ messages in thread
From: Michael Shulman @ 2021-03-04 20:43 UTC (permalink / raw)
  To: HomotopyTypeTheory@googlegroups.com

Has anyone considered the following HIT definition of the integers?

data ℤ : Type where
  zero : ℤ                              -- 0
  negOne : ℤ                            -- -1
  dbl : ℤ → ℤ                           -- n ↦ 2n
  sucDbl : ℤ → ℤ                        -- n ↦ 2n+1
  dblZero : dbl zero ≡ zero             -- 2·0 = 0
  sucDblNegOne : sucDbl negOne ≡ negOne -- 2·(-1)+1 = -1

The idea is that it's an arbitrary-precision version of little-endian
two's-complement, with sucDbl and dbl representing 1 and 0
respectively, and negOne and zero representing the highest-order sign
bit 1 and 0 respectively.  Thus for instance

sucDbl (dbl (sucDbl (sucDbl zero))) = 01101 = 13
dbl (sucDbl (dbl (dbl negOne))) = 10010 = -14

The two path-constructors enable arbitrary expansion of the precision, e.g.

01101 = 001101 = 0001101 = ...
10010 = 110010 = 1110010 = ...

This seems like a fairly nice definition: it should already be a set
without any truncation, it's binary rather than unary, and the
arithmetic operations can be defined in the usual digit-by-digit way
without splitting into cases by sign.  Mathematically speaking, it
represents integers by their images in the 2-adic integers, with zero
and negOne representing infinite tails of 0s and 1s respectively.  (An
arbitrary 2-adic integer, of course, is just a stream of bits.)

Best,
Mike

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQw4h46DtKATiwUvm%3DL%3DjEGng2XdYGAhKbi7fhis%2By_TPw%40mail.gmail.com.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [HoTT] two's complement integers
  2021-03-04 20:43 [HoTT] two's complement integers Michael Shulman
@ 2021-03-04 21:11 ` Martin Escardo
  2021-03-04 22:05   ` Michael Shulman
  0 siblings, 1 reply; 8+ messages in thread
From: Martin Escardo @ 2021-03-04 21:11 UTC (permalink / raw)
  To: Michael Shulman, HomotopyTypeTheory@googlegroups.com

Nice. I haven't seen this. But I have considered two similar things:

(1) The natural numbers defined by

  0
  2x+1
  2x+2

This is not a HIT - just a normal inductive types.

(2) A HIT for the dyadics numbers D in the interval [0,1] with constructors

data 𝔹 : Type₀ where
  L R : 𝔹                           -- 0 and 1
  l r : 𝔹 → 𝔹                       -- x ↦ x/2 and x ↦ (x+1)/2
  eqL : L   ≡ l L                   -- 0 = 0/2
  eqM : l R ≡ r L                   -- 1/2 = (0+1)/2
  eqR : R   ≡ r R                   -- 1 = (1+1)/2

Then, like your HIT, this is automatically a set without the need of
truncation. But I didn't find an simple proof of this. Together with
Alex Rice, we proved this by showing it to be equivalent to another type
which is easily seen to be a aset:

data 𝔻 :  Type₀ where
 middle : 𝔻
 left   : 𝔻 → 𝔻
 right  : 𝔻 → 𝔻

data 𝔹' : Type₀ where
 L' : 𝔹'
 R' : 𝔹'
 η  : 𝔻 → 𝔹'

l' : 𝔹' → 𝔹'
l' L'    = L'
l' R'    = η middle
l' (η x) = η (left x)

r' : 𝔹' → 𝔹'
r' L'    = η middle
r' R'    = R'
r' (η x) = η (right x)

eqL' : L'    ≡ l' L'
eqM' : l' R' ≡ r' L'
eqR' : R'    ≡ r' R'

eqL' = refl
eqM' = refl
eqR' = refl

Then the types 𝔹 and 𝔹' are equivalent, and clearly 𝔹' is a set
because it has decidable equality.

Moreover, the "binary systems" (𝔹,L,R,l,r,eqL,eqM,eqR) and
(𝔹',L',R',l',r',eqL',eqM',eqR') are isomorphic.

(And we implemented in this in Cubical Agda.)

I wonder if your definition of the integers with the HIT is isomorphic
to an inductively defined version without a HIT as above, and this is
how you proved it to be a set.

Martin

On 04/03/2021 20:43, Michael Shulman wrote:
> Has anyone considered the following HIT definition of the integers?
> 
> data ℤ : Type where
>   zero : ℤ                              -- 0
>   negOne : ℤ                            -- -1
>   dbl : ℤ → ℤ                           -- n ↦ 2n
>   sucDbl : ℤ → ℤ                        -- n ↦ 2n+1
>   dblZero : dbl zero ≡ zero             -- 2·0 = 0
>   sucDblNegOne : sucDbl negOne ≡ negOne -- 2·(-1)+1 = -1
> 
> The idea is that it's an arbitrary-precision version of little-endian
> two's-complement, with sucDbl and dbl representing 1 and 0
> respectively, and negOne and zero representing the highest-order sign
> bit 1 and 0 respectively.  Thus for instance
> 
> sucDbl (dbl (sucDbl (sucDbl zero))) = 01101 = 13
> dbl (sucDbl (dbl (dbl negOne))) = 10010 = -14
> 
> The two path-constructors enable arbitrary expansion of the precision, e.g.
> 
> 01101 = 001101 = 0001101 = ...
> 10010 = 110010 = 1110010 = ...
> 
> This seems like a fairly nice definition: it should already be a set
> without any truncation, it's binary rather than unary, and the
> arithmetic operations can be defined in the usual digit-by-digit way
> without splitting into cases by sign.  Mathematically speaking, it
> represents integers by their images in the 2-adic integers, with zero
> and negOne representing infinite tails of 0s and 1s respectively.  (An
> arbitrary 2-adic integer, of course, is just a stream of bits.)
> 
> Best,
> Mike
> 

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/9eefbc82-ba49-b101-433d-c3c1e452ecda%40googlemail.com.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [HoTT] two's complement integers
  2021-03-04 21:11 ` Martin Escardo
@ 2021-03-04 22:05   ` Michael Shulman
  2021-03-04 22:42     ` Martin Escardo
  2021-03-04 23:16     ` Nicolai Kraus
  0 siblings, 2 replies; 8+ messages in thread
From: Michael Shulman @ 2021-03-04 22:05 UTC (permalink / raw)
  To: Martin Escardo; +Cc: HomotopyTypeTheory@googlegroups.com

On Thu, Mar 4, 2021 at 1:11 PM Martin Escardo <escardo.martin@gmail.com> wrote:
> I wonder if your definition of the integers with the HIT is isomorphic
> to an inductively defined version without a HIT as above, and this is
> how you proved it to be a set.

No, I just did an encode-decode.  I formalized most of it, up to some
obviously true lemmas about squares and cubes.

I thought for a little bit about whether there is an equivalent
"lower" inductive version, but nothing immediately occurred to me.  Do
you have a suggestion?

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQwsn-MLHzw%3DW5wxZ49Bp%2BHS9nr261YQJLgQ9E60K2Pcmg%40mail.gmail.com.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [HoTT] two's complement integers
  2021-03-04 22:05   ` Michael Shulman
@ 2021-03-04 22:42     ` Martin Escardo
  2021-03-04 23:16     ` Nicolai Kraus
  1 sibling, 0 replies; 8+ messages in thread
From: Martin Escardo @ 2021-03-04 22:42 UTC (permalink / raw)
  To: Michael Shulman, Martin Escardo; +Cc: HomotopyTypeTheory@googlegroups.com



On 04/03/2021 22:05, Michael Shulman wrote:
> On Thu, Mar 4, 2021 at 1:11 PM Martin Escardo <escardo.martin@gmail.com> wrote:
>> I wonder if your definition of the integers with the HIT is isomorphic
>> to an inductively defined version without a HIT as above, and this is
>> how you proved it to be a set.
> 
> No, I just did an encode-decode.  I formalized most of it, up to some
> obviously true lemmas about squares and cubes.
> 
> I thought for a little bit about whether there is an equivalent
> "lower" inductive version, but nothing immediately occurred to me.  Do
> you have a suggestion?


For example, take ℤ' = ℕ + ℕ and define the functions you have in your
hit and prove the equations you have in your HIT.

Then using the HIT universal property you get a function from your ℤ to
this ℤ', and conversely you define a function from ℤ' to ℤ "manually".

This is what Alex Rice and I did to prove that our 𝔹 and 𝔹' are
equivalent. The cubes don't disappear completely, of course. But there
were much fewer cubes than when we tried to prove directly that 𝔹 is a
set, and we gave up because the code was getting too long and
unpleasant, with too many cases to check. The indirect version was much
shorter and pleasing.

Martin




-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/8f4c4a68-dbe0-055b-3462-3230cd09c86f%40gmail.com.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [HoTT] two's complement integers
  2021-03-04 22:05   ` Michael Shulman
  2021-03-04 22:42     ` Martin Escardo
@ 2021-03-04 23:16     ` Nicolai Kraus
  2021-03-05  2:27       ` Michael Shulman
  1 sibling, 1 reply; 8+ messages in thread
From: Nicolai Kraus @ 2021-03-04 23:16 UTC (permalink / raw)
  To: HomotopyTypeTheory

[-- Attachment #1: Type: text/plain, Size: 1114 bytes --]

On 04/03/2021 22:05, Michael Shulman wrote:
> I thought for a little bit about whether there is an equivalent
> "lower" inductive version, but nothing immediately occurred to me.  Do
> you have a suggestion?

I'm not sure what the precise thing is that you're looking for because, 
without further specification, any standard definition of Z would 
qualify :-)
The HIT is neat, but wouldn't it in practice behave pretty similar to a 
standard representation via binary lists? E.g. something like Unit + 
Bool * List(Bool), where inl(*) is zero, the first Bool is the sign, and 
you add a 1 in front of the list in order to get a positive integer. 
What's the advantage of the HIT - maybe one can avoid case distinctions?
Nicolai

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/58a0a515-d8fa-4eb2-9555-d3a41fdee728%40gmail.com.

[-- Attachment #2: Type: text/html, Size: 3716 bytes --]

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [HoTT] two's complement integers
  2021-03-04 23:16     ` Nicolai Kraus
@ 2021-03-05  2:27       ` Michael Shulman
  2021-03-05  3:02         ` Jason Gross
  0 siblings, 1 reply; 8+ messages in thread
From: Michael Shulman @ 2021-03-05  2:27 UTC (permalink / raw)
  To: Nicolai Kraus; +Cc: HomotopyTypeTheory

On Thu, Mar 4, 2021 at 3:16 PM Nicolai Kraus <nicolai.kraus@gmail.com> wrote:
> I'm not sure what the precise thing is that you're looking for because, without further specification, any standard definition of Z would qualify :-)

Yes, that seems to be what Martin suggested too with ℕ + ℕ.  It seemed
to me as though the distance between ℕ + ℕ and my ℤ is greater than
the distance between his 𝔹 and 𝔹', but maybe not in any important
way.

> The HIT is neat, but wouldn't it in practice behave pretty similar to a standard representation via binary lists? E.g. something like Unit + Bool * List(Bool), where inl(*) is zero, the first Bool is the sign, and you add a 1 in front of the list in order to get a positive integer. What's the advantage of the HIT - maybe one can avoid case distinctions?

Is there a non-HIT binary representation that can be interpreted as
two's-complement (thereby avoiding case distinctions on sign)?  I
haven't been able to figure out a way to do that with mere lists of
booleans.

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQwtAMVnOG7D_A_s1EMAum4fv_x945MLB%2B01Y_pMdEKC2w%40mail.gmail.com.

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [HoTT] two's complement integers
  2021-03-05  2:27       ` Michael Shulman
@ 2021-03-05  3:02         ` Jason Gross
  2021-03-05  4:41           ` Michael Shulman
  0 siblings, 1 reply; 8+ messages in thread
From: Jason Gross @ 2021-03-05  3:02 UTC (permalink / raw)
  To: Michael Shulman; +Cc: Nicolai Kraus, HomotopyTypeTheory@googlegroups.com

[-- Attachment #1: Type: text/plain, Size: 2429 bytes --]

Note that the Coq standard library Z is a binary representation of integers
and Z.testbit gives access to the infinite twos-compliment representation.
Of course, it makes use of case-distinctions on sign to define it, but you
go bit-by-bit; if the number is negative, you just invert the bit before
returning it.  Is there something you're after by having the representation
not encode sign bits separately?

On Thu, Mar 4, 2021, 21:27 Michael Shulman <shulman@sandiego.edu> wrote:

> On Thu, Mar 4, 2021 at 3:16 PM Nicolai Kraus <nicolai.kraus@gmail.com>
> wrote:
> > I'm not sure what the precise thing is that you're looking for because,
> without further specification, any standard definition of Z would qualify
> :-)
>
> Yes, that seems to be what Martin suggested too with ℕ + ℕ.  It seemed
> to me as though the distance between ℕ + ℕ and my ℤ is greater than
> the distance between his 𝔹 and 𝔹', but maybe not in any important
> way.
>
> > The HIT is neat, but wouldn't it in practice behave pretty similar to a
> standard representation via binary lists? E.g. something like Unit + Bool *
> List(Bool), where inl(*) is zero, the first Bool is the sign, and you add a
> 1 in front of the list in order to get a positive integer. What's the
> advantage of the HIT - maybe one can avoid case distinctions?
>
> Is there a non-HIT binary representation that can be interpreted as
> two's-complement (thereby avoiding case distinctions on sign)?  I
> haven't been able to figure out a way to do that with mere lists of
> booleans.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Homotopy Type Theory" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQwtAMVnOG7D_A_s1EMAum4fv_x945MLB%2B01Y_pMdEKC2w%40mail.gmail.com
> .
>

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAKObCaqiyUcB%2BFrbvPmR-eS5ZMsb2CTVCtVbAYZeMUcOzCpmbA%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 3413 bytes --]

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [HoTT] two's complement integers
  2021-03-05  3:02         ` Jason Gross
@ 2021-03-05  4:41           ` Michael Shulman
  0 siblings, 0 replies; 8+ messages in thread
From: Michael Shulman @ 2021-03-05  4:41 UTC (permalink / raw)
  To: Jason Gross; +Cc: Nicolai Kraus, HomotopyTypeTheory@googlegroups.com

I don't have a particular application in mind at the moment.  It just
struck me how 2-adic integers have such simple coinductive definitions
of the arithmetic operations, without any case distinctions at all,
and I wondered whether there was a definition of plain integers with a
similar property.  It seems annoying to have to constantly case-split
on a sign bit.

I guess a lower-inductive representation could take advantage of the
fact that the 2-adic representation of an integer other than 0 or -1
has a unique largest digit that differs from all larger digits, i.e.
it's either

...0000 (i.e. 0)
...1111 (i.e. -1)
...0001 + arbitrary bit string
...1110 +  arbitrary bit string

This involves more case splits when defining arithmetic, but it would
probably be an easy set to show that the HIT one is equivalent to.


On Thu, Mar 4, 2021 at 7:02 PM Jason Gross <jasongross9@gmail.com> wrote:
>
> Note that the Coq standard library Z is a binary representation of integers and Z.testbit gives access to the infinite twos-compliment representation.  Of course, it makes use of case-distinctions on sign to define it, but you go bit-by-bit; if the number is negative, you just invert the bit before returning it.  Is there something you're after by having the representation not encode sign bits separately?
>
> On Thu, Mar 4, 2021, 21:27 Michael Shulman <shulman@sandiego.edu> wrote:
>>
>> On Thu, Mar 4, 2021 at 3:16 PM Nicolai Kraus <nicolai.kraus@gmail.com> wrote:
>> > I'm not sure what the precise thing is that you're looking for because, without further specification, any standard definition of Z would qualify :-)
>>
>> Yes, that seems to be what Martin suggested too with ℕ + ℕ.  It seemed
>> to me as though the distance between ℕ + ℕ and my ℤ is greater than
>> the distance between his 𝔹 and 𝔹', but maybe not in any important
>> way.
>>
>> > The HIT is neat, but wouldn't it in practice behave pretty similar to a standard representation via binary lists? E.g. something like Unit + Bool * List(Bool), where inl(*) is zero, the first Bool is the sign, and you add a 1 in front of the list in order to get a positive integer. What's the advantage of the HIT - maybe one can avoid case distinctions?
>>
>> Is there a non-HIT binary representation that can be interpreted as
>> two's-complement (thereby avoiding case distinctions on sign)?  I
>> haven't been able to figure out a way to do that with mere lists of
>> booleans.
>>
>> --
>> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
>> To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
>> To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQwtAMVnOG7D_A_s1EMAum4fv_x945MLB%2B01Y_pMdEKC2w%40mail.gmail.com.
>
> --
> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAKObCaqiyUcB%2BFrbvPmR-eS5ZMsb2CTVCtVbAYZeMUcOzCpmbA%40mail.gmail.com.

-- 
You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQxy2EJNScHu9Y2U%3DGLiHDrDxDq-Kg8Dz9TrFk3ZepiW8Q%40mail.gmail.com.

^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2021-03-05  4:41 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-03-04 20:43 [HoTT] two's complement integers Michael Shulman
2021-03-04 21:11 ` Martin Escardo
2021-03-04 22:05   ` Michael Shulman
2021-03-04 22:42     ` Martin Escardo
2021-03-04 23:16     ` Nicolai Kraus
2021-03-05  2:27       ` Michael Shulman
2021-03-05  3:02         ` Jason Gross
2021-03-05  4:41           ` Michael Shulman

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).