Skip to content

has it (DecTotalOrder Bin) ? #65

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
mechvel opened this issue Mar 22, 2015 · 44 comments
Closed

has it (DecTotalOrder Bin) ? #65

mechvel opened this issue Mar 22, 2015 · 44 comments
Assignees
@MatthewDaggitt
Labels
addition question

Comments

@mechvel
Copy link
Contributor

mechvel commented Mar 22, 2015

has it (DecTotalOrder Bin) ?
@MatthewDaggitt
Copy link
Contributor

Can you elaborate a bit more? Do you mean Fin instead of Bin?

@MatthewDaggitt MatthewDaggitt self-assigned this Jun 22, 2017
@mechvel
Copy link
Contributor Author

mechvel commented Jun 23, 2017 via email •
edited by MatthewDaggitt
Loading

@MatthewDaggitt
Copy link
Contributor

Correct me if I'm wrong, but _<_ in Data.Bin is not a total order or even a preorder because it is a strict inequality and therefore is not reflexive...

@mechvel
Copy link
Contributor Author

mechvel commented Jun 26, 2017 via email

@MatthewDaggitt
Copy link
Contributor

Ah, well at the moment the relation _≤_ isn't even defined in Data.Bin. Adding such a definition would probably mean that the existing definition of _<_ would want to be reworked in terms of it and that would entail making large changes to the rest of the file.

As it's a fairly niche part of the library and a reasonably large piece of work, I don't think that it's likely it'll be done any time soon. However if you need this and have already written the necessary code then please do feel free to submit a pull request with it!

@mechvel
Copy link
Contributor Author

mechvel commented Jun 29, 2017 via email

@mechvel
Copy link
Contributor Author

mechvel commented Jun 30, 2017

Please, take a fresh version from there:
ftp://ftp.botik.ru/pub/local/Mechveliani/agdaNotes/bin2.zip

Ii is tested under Agda 2.6.0-207bde6.

@mechvel
Copy link
Contributor Author

mechvel commented Jun 30, 2017

Also
ftp://ftp.botik.ru/pub/local/Mechveliani/agdaNotes/bin3.zip

includes the items of bin2.zip + the instance of DecTotalOrder for Bin
for
x ≤ y defined on Bin as x < y ⊎ x ≡ y.

@MatthewDaggitt
Copy link
Contributor

Thank you for your contribution! It would be great if you could submit some of it as a pull request rather than a zip file. If you need any pointers on creating a pull request please feel free to ask!

As for the ordering x ≤ y = x < y ⊎ x ≡ y, defining _≤_ in terms of _<_ is backwards with respect to the rest of the standard library. I'm reluctant to accept it as I feel its likely to cause confusions for users and further problems down the line. As I mentioned before, I'd be much more comfortable rewriting the implementation of _<_ in terms of a new native _≤_ relation.

@mechvel
Copy link
Contributor Author

mechvel commented Jul 9, 2017 via email

@MatthewDaggitt
Copy link
Contributor

MatthewDaggitt commented Jul 9, 2017 •
edited
Loading

Please, how to make a pull request in this my particular case?

  1. In a suitable directory, on the command line call git clone https://github.com/mechvel/agda-stdlib stdlib-clone. This will copy the standard library into a new folder called stdlib-clone.
  2. Make the changes you want to in the files Data.Bin and Data.Bin.Properties within stdlib-clone, (including updating CHANGELOG.md with the changes you've made)
  3. Whilst in the top level of the directory stdlib-clone, run the command make test from the command line to check that your changes haven't broken anything.
  4. Add the files you've made changes to using the commands git add src/Data/Bin.agda, git add src/Data/Bin/Properties.agda, git add CHANGELOG.md etc.
  5. Commit the files you've added using git commit.
  6. Push all your changes to your fork on github using git push origin master
  7. Go to https://github.com/mechvel/agda-stdlib and there should be a button to create a pull request from your new commit.

@mechvel
Copy link
Contributor Author

mechvel commented Jul 9, 2017

I put Nat2.agda into the folder Data/Nat/,
and put Bin2.agda into Data/Bin

And module Data.Bin.Bin2
imports items from ``Data.Nat.Nat2''.

And ``make test" reports

cabal clean && cabal install
cleaning...
Resolving dependencies...
Configuring lib-0.13...
Building lib-0.13...
Preprocessing executable 'GenerateEverything' for lib-0.13...
[1 of 1] Compiling Main ( GenerateEverything.hs, dist/build/GenerateEverything/GenerateEverything-tmp/Main.o )
Linking dist/build/GenerateEverything/GenerateEverything ...
Preprocessing executable 'AllNonAsciiChars' for lib-0.13...
[1 of 1] Compiling Main ( AllNonAsciiChars.hs, dist/build/AllNonAsciiChars/AllNonAsciiChars-tmp/Main.o )
Linking dist/build/AllNonAsciiChars/AllNonAsciiChars ...
Installing executable(s) in /home/mechvel/.cabal/bin
Installed lib-0.13
cabal exec -- GenerateEverything
GenerateEverything: src/Data/Bin/Bin2.agda is malformed

I reduce this module to two lines (by commenting out all the rest):

module Data.Bin.Bin2 where -- ℕ <--> Bin⁺ isomorphism

open import Level using () renaming (zero to 0ℓ)

and still it is reported "malformed".

I wonder what might this mean.

@mechvel
Copy link
Contributor Author

mechvel commented Jul 9, 2017

As for the ordering x ≤ y = x < y ⊎ x ≡ y, defining ≤ in terms of < is backwards with respect
to the rest of the standard library. I'm reluctant to accept it as I feel its likely to cause confusions
for users and further problems down the line. As I mentioned before, I'd be much more
comfortable rewriting the implementation of < in terms of a new native ≤ relation.

Currently, Bin has the following implementation to _<_ :

data _<_ (b₁ b₂ : Bin) : Set where
less : (lt : (Nat._<_ on toℕ) b₁ b₂) → b₁ < b₂

Do you suggest to replace this with

data _≤__ (b₁ b₂ : Bin) : Set where
leq : (le : (Nat._≤__ on toℕ) b₁ b₂) → b₁ ≤_b₂

and then, to define _<_ as
x < y = x ≤ y × x ≢ y
?

@MatthewDaggitt
Copy link
Contributor

I put Nat2.agda into the folder Data/Nat/ and put Bin2.agda into Data/Bin

So the changes that you're making shouldn't be put inside their own files. They should be incorporated into the existing Data.Bin and Data.Bin.Properties files. This should bypass your current problem with the tests.

Currently, Bin has the following implementation to <:

data < (b₁ b₂ : Bin) : Set where
less : (lt : (Nat.< on toℕ) b₁ b₂) → b₁ < b₂

Do you suggest to replace this with

data ≤_ (b₁ b₂ : Bin) : Set where
leq : (le : (Nat.≤_ on toℕ) b₁ b₂) → b₁ ≤_b₂

and then, to define < as
x < y = x ≤ y × x ≢ y

That certainly seems better. In fact, as we're reworking the implementation and the changes aren't going to be backwards compatible anyway, I might be tempted to copy the style of _≤_ in Data.Fin and get rid of the data declaration entirely so that it reads as follows:

_≤_ : Rel Bin Set
x ≤ y = toℕ x Nat.≤ toℕ y

_<_ : Rel Bin Set
x < y = x ≤ y × x ≢ y

The notes say that the existing data declaration is to aid in pattern matching. It might be worth experimenting with the two different definitions of _≤_: your new version and mine and see which is easier to work with.

@mechvel
Copy link
Contributor Author

mechvel commented Jul 9, 2017 via email

@mechvel
Copy link
Contributor Author

mechvel commented Jul 9, 2017

I incorporate them there. Now it reports

... Installed lib-0.13 cabal exec -- GenerateEverything cabal exec -- fix-agda-whitespace --check cabal: The program 'fix-agda-whitespace' is required but it could not be found.

On the other hand, Agda 2.6.0-207bde6 does work on my computer, and it uses
Standard library of April 2017
(which I think is lib-0.13).

I wonder, how to fix.

Sergei

@asr
Copy link
Member

asr commented Jul 9, 2017

You can install fix-agda-whitespace from your Agda upstream directory:

$ cd my-agda-upstream-directory
$ cd src/fix-agda-whitespace/
$ cabal install

@mechvel
Copy link
Contributor Author

mechvel commented Jul 9, 2017 •
edited by gallais
Loading

Now, the commands

> cd ~/agda/apr13-2017/src/fix-agda-whitespace
> cabal install
> make test

lead to the report

...
Installed lib-0.13
cabal exec -- GenerateEverything
cabal exec -- fix-agda-whitespace --check
Whitespace violation detected in /home/mechvel/agda/stLib/stdlib-clone/CHANGELOG.md.
Whitespace violation detected in /home/mechvel/agda/stLib/stdlib-clone/src/Data/Bin.agda.
Whitespace violation detected in /home/mechvel/agda/stLib/stdlib-clone/src/Data/Nat/Properties.agda.

These three files are exactly the files to which I have added certain needed comments and code.
I wonder, what is wrong there.

@mechvel
Copy link
Contributor Author

mechvel commented Jul 9, 2017 •
edited by gallais
Loading

Now, the commands

> cd ~/agda/apr13-2017/src/fix-agda-whitespace
> cabal install
> make test

lead to the report

Installed lib-0.13
cabal exec -- GenerateEverything
cabal exec -- fix-agda-whitespace --check
Whitespace violation detected in /home/mechvel/agda/stLib/stdlib-clone/CHANGELOG.md.
Whitespace violation detected in /home/mechvel/agda/stLib/stdlib-clone/src/Data/Bin.agda.
Whitespace violation detected in /home/mechvel/agda/stLib/stdlib-clone/src/Data/Nat/Properties.agda.

These three files are exactly the files to which I have added certain needed comments and code.
I wonder, what is wrong there.

@gallais
Copy link
Member

gallais commented Jul 9, 2017

Usually it's because you have trailing whitespace on some lines. IIRC cabal exec -- fix-agda-whitespace should fix the problem.

@asr
Copy link
Member

asr commented Jul 9, 2017 •
edited
Loading

I wonder, what is wrong there.

You have whitespace issues (but your editor is not showing them). Run fix-agda-whitespace on the offending directory and commit the changes.

@asr
Copy link
Member

asr commented Jul 9, 2017

@mechvel it is difficult read your messages in GitHub because the format is awful. Please edit your messages and fix their format.

@gallais
Copy link
Member

gallais commented Jul 9, 2017

@mechvel You don't need 2 opening and 2 closing backticks on every line, you can simply use 3 backticks on a single line before the block and 3 backticks on a single line after the block like so:

　```
　code
　block
　```

gives:

code
block

@mechvel
Copy link
Contributor Author

mechvel commented Jul 10, 2017

About pull requests:
the restriction of not providing new files in a proposal extending Standard library is unnatural.
Thus, my proposition works when added as a new file, while adding it to Nat/Properties.agda
leads to import circles. So that one needs to split the addition between Nat.agda, Nat.properties,
Fin, Fin.Properties, Nat.DivMod ... A headache.

@MatthewDaggitt
Copy link
Contributor

MatthewDaggitt commented Jul 10, 2017 •
edited
Loading

The restriction of not providing new files in a proposal extending Standard library is unnatural.
Thus, my proposition works when added as a new file, while adding it to Nat/Properties.agda
leads to import circles. So that one needs to split the addition between Nat.agda, Nat.properties,
Fin, Fin.Properties, Nat.DivMod ... A headache.

So its not impossible to add new files, it's just that by keeping everything organised logically it helps users. Adding new files for each pull request would lead to chaos where no-one would know where to look for a particular property.

The fact that you are getting import cycles means that as it is your code could be structured better, but it sounds like you've already worked out how to fix it by putting your changes in the relevant files!

If I may make the suggestion that you start off creating a pull request for only a small set of changes? Maybe only the basic changes to Data.Nat, Data.Nat.Properties and Data.Nat.DivMod, and then we'll add those in and you can work on the rest.

@mechvel
Copy link
Contributor Author

mechvel commented Jul 10, 2017

I cancel my complaint about restriction on .agda files for pull requests for Standard library.

So far, I propose the two main backwards compatible items for Bin.
Their implementation needs several (backwards compatible) additions to Nat.Properties, Nat.DivMod.
I am going to do all this (may be, later, in August or such), and then, we shall see.

I do not care much of adding things to Standard library, I just use them as non-standard.
But earlier I happened to make proposals there, and now suddenly have a response -- after 3-4 years.
So that I do not know, may be it has sense to try to reach a result.

@mechvel
Copy link
Contributor Author

mechvel commented Jul 11, 2017

I have committed a pull request for the above features.

Further improvement for Bin can be as follows.

  1. To define _≤_ on Bin as the lexicographic order on bit lists.
  2. To prove that _≤_ on Bin is logically equivalent to _≤_ on the corresponding Nat values.
  3. To define b < b1 = b ≤ b1 × b ≢ b1.
  4. To implement compare respectively to this ordering definition.
  5. To implement DecTotalOrder and StrictTotalOrder respectively.

This will make the ordering witnesses for Bin an explicit data, with also preserving fast comparison.

@MatthewDaggitt
Copy link
Contributor

MatthewDaggitt commented Jul 11, 2017 •
edited
Loading

Okay great. Now if you go to your forked repository on Github to the right of the text "This branch is 1 commit ahead of agda:master." there is a button called "Pull request". This allows you to submit your pull request to the main repository.

Also I agree, your proposed implementation of the lexicographic ordering seems like the best!

@mechvel
Copy link
Contributor Author

mechvel commented Jul 11, 2017

I clicked this "Pull request". But I am not sure that it is submitted to the main repository.
How to check this.
Also there is a strange matter of the "committer" email address, it is somehow expanded, and I suspect that this address does not work.

@MatthewDaggitt
Copy link
Contributor

Okay, after clicking that you then need to click the green "Create pull request" button at the top of the page, and then again on the next screen.

@mechvel
Copy link
Contributor Author

mechvel commented Jul 11, 2017 via email

@MatthewDaggitt
Copy link
Contributor

MatthewDaggitt commented Jul 11, 2017 •
edited
Loading

After clicking the green "Create pull request" nothing happens. It stays there, silent.

Is this the first or the second "Create pull request" button? Does the page say "Comparing changes" or "Open a pull request" at the top?

It seems to work for me fine.

Is it possible to change this CHANGELOG.md in the pull request?

Yes, it's possible to make modifications to the pull request at any point. Simply repeat steps 2, 3, 4, 5 and 6 in the instructions I gave you earlier. Any changes you make will automatically be added to the pull request (once you've succeeded in making it).

@mechvel
Copy link
Contributor Author

mechvel commented Jul 11, 2017

Is this the first or the second "Create pull request" button? Does the page say "Comparing changes"
or "Open a pull request" at the top?

First I stay at
https://github.com/mechvel/agda-stdlib
There is the headline of
"This branch is 1 commit ahead of agda:master." "Pull request" "Compare".

The last two are the buttons at the right end. I click "Pull request".
And it shows now differently.
At the right end it shows green "View pull request".
And it prints " Committer: Sergei Meshveliani ......"
-- in one left column, leaving blank the rest of the page on screen.
One page lower it shows in green "Create new pull request",
and below shows in green a responsible part of my CHANGELOG.md.
No "Create pull request" button is visible

Clicking at "Create new pull request" does not change anything.
Lower it is visible a small ring with running segment in it.
The page ends with "No commit comments for this range".
And this way it stays.

@MatthewDaggitt
Copy link
Contributor

The last two are the buttons at the right end. I click "Pull request".

So after clicking "Pull request" you should see this:
image

.
.
.

Clicking at "Create new pull request" does not change anything.

Clicking the "Create new pull request" button should then allow you to enter the description of the pull request. The screen should now look like this:
image

Do you get this screen? After editing the details, you then need to click the green "Create pull request" button at the bottom.

@mechvel
Copy link
Contributor Author

mechvel commented Jul 11, 2017 via email

@gallais
Copy link
Member

gallais commented Jul 11, 2017

And I probably do not need to create another pull request.

Yes you do. The pull requests are listed here so yours most definitely has not been created yet. If you want to make some more edits, you need to commit them and push them to your fork before you start the pull request.

@asr
Copy link
Member

asr commented Jul 11, 2017

(my address is [email protected], but Git inserts there `mechvel2' in
the middle, which is suspicious).

On the directory where you are doing the commits, please show me the output of

$ git log -5

@mechvel
Copy link
Contributor Author

mechvel commented Jul 12, 2017 via email

@mechvel
Copy link
Contributor Author

mechvel commented Jul 12, 2017

I have sent an email reply to the last request here. But Github replaced 1 page log text with "..." .
Can you see this text anywhere?

@MatthewDaggitt
Copy link
Contributor

Okay, let's try again.

  1. Go to https://github.com/mechvel/agda-stdlib
  2. Press "Pull request"
    image
  3. Press "Create new pull request"
    image
  4. Change the title of the pull request to something sensible
    image
  5. Click "Create pull request"
    image

@fredrikNordvallForsberg
Copy link
Member

@mechvel The email address used is not important for the success of the creation of the pull request, but if you want to change it, you can execute the following command on the command line:

git config --global user.email "[email protected]"

Afterwards git will use your correct email address (see e.g. https://help.github.com/articles/setting-your-email-in-git/#setting-your-email-address-for-every-repository-on-your-computer).

@mechvel
Copy link
Contributor Author

mechvel commented Jul 12, 2017 via email

@MatthewDaggitt
Copy link
Contributor

The step
3. Press "Create new pull request"
does not produce any effect. And I do not see how can I change there
anything in the title, there is no possibility.

Okay, well that's deeply bizarre. Fine, I guess I'll go ahead and create the pull request for you.

@MatthewDaggitt MatthewDaggitt mentioned this issue Jul 12, 2017
Closed
@MatthewDaggitt MatthewDaggitt mentioned this issue Jan 7, 2018
Closed
@MatthewDaggitt
Copy link
Contributor

Closing this issue, as users seriously interested in binary computation can use the release of @mechvel 's new library.

@MatthewDaggitt MatthewDaggitt mentioned this issue Jan 12, 2019
Open
@MatthewDaggitt MatthewDaggitt mentioned this issue Jan 24, 2019
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@MatthewDaggitt MatthewDaggitt

Labels
addition question
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
5 participants
@fredrikNordvallForsberg @asr @gallais @mechvel @MatthewDaggitt