herbie-fp / herbie Goto Github PK

Not sure if this is a bug, or lack of knowledge on my side.

racket ~/src/herbie/src/reports/run.rkt --fuel 4 orbit.txt;

1. op->precision in /home/lebedevri/src/herbie/src/programs.rkt:162:24
2. inductor in /home/lebedevri/src/herbie/src/programs.rkt:72:2
3. inductor in /home/lebedevri/src/herbie/src/programs.rkt:72:2
4. inductor in /home/lebedevri/src/herbie/src/programs.rkt:72:2
5. inductor in /home/lebedevri/src/herbie/src/programs.rkt:72:2
6. inductor in /home/lebedevri/src/herbie/src/programs.rkt:72:2
7. inductor in /home/lebedevri/src/herbie/src/programs.rkt:72:2
8. eval-prog in /home/lebedevri/src/herbie/src/programs.rkt:160:0
9. loop in /home/lebedevri/src/herbie/src/points.rkt:92:2
10. loop in /home/lebedevri/src/herbie/src/points.rkt:121:2
11. run-improve50 in /home/lebedevri/src/herbie/src/mainloop.rkt:238:0
12. .../more-scheme.rkt:261:28 in ???

graphs.zip

orbit.txt

The call to elim-enode-loops! is commented out in apply-match. When I add it back in, the code couldn't quite work (it complains that remove-loop! in enode.rkt is getting 1 too many argument). Digging through the history I see that the code caused some major headaches - how do you advice to deal with loops in egraphs?

https://github.com/uwplse/herbie/blob/dc8b20f47788567e8fb961e7cb7e450842a237e1/src/core/simplify.rkt#L115

Currently, 60% the FFI imports in herbie/syntax.rkt don't work since there is no libm on Windows (the working 40% come from a different library, I think msvcrt.dll but I'm not sure). Here is the test I ran and the result.

I believe supporting Windows is important considering how popular it is (52% of developers according to the Stack Overflow Developer Survey 2016 Results).

The assignment to follow seems inconsistent to the variable naming, i.e. the old-var of the leader is assigned to follower-old-vars. I tried swapping them and didn't see much change. Are you sure the assignment is correct?

https://github.com/uwplse/herbie/blob/dc8b20f47788567e8fb961e7cb7e450842a237e1/src/core/egraph.rkt#L180

On the Herbie home page, the last sentence of the Status section reads: "...Herbie has been accepted for publication to PLDI'15 as a distinguished paper—read it!" and links to the URL http://herbie.uwplse.org/pldi15-herbie.pdf.
The correct URL should be http://herbie.uwplse.org/pldi15-paper.pdf

I followed the steps on the website:

1. I downloaded and installed Racket (racket-7.3-x86_64-win32.exe)
2. I open an elevated command prompt (otherwise it would complain of some permissions) into the Racket installation directory (C:\Program Files\Racket) and typed "raco pkg install --auto herbie"
   Everything went fine, it told me where Herbie was installed
3. I went into the Herbie installtion directory (C:\Users\myUsername\AppData\Roaming\Racket\7.3), opened an elevated command prompt and typed "herbie web"
   It shows

Herbie 1.3 with seed 1071855432

So far so good.

4. Now I test it with toy example of the quadratic formula, the same one you have in the 2015 video :
   (-b+sqrt(b^2-4ac))/(2*a)

I get the following:

I also tried using single precision (no cbrt warning this time and a different error):

Try just entering any expression, even a constant like 1, and you get:

Exception
The application raised an exception with the message:

set-member?: contract violation:
expected: set?
given: "graph.html"
argument position: 1st
other arguments...:
  x: '("graph.html" "interactive.js" "timeline.html" "timeline.json")
Stack trace:

set-member? at:
  line 475, column 9, in file /usr/share/racket/collects/racket/private/generic.rkt
generate-page at:
  line 43, column 0, in file /src/herbie/web/demo.rkt
<unknown procedure> at:
  line 357, column 33, in file /usr/share/racket/collects/racket/contract/private/arrow-higher-order.rkt
<unknown procedure> at:
  line 357, column 33, in file /usr/share/racket/collects/racket/contract/private/arrow-higher-order.rkt
<unknown procedure> at:
  line 63, column 2, in file /root/.racket/6.12/pkgs/web-server-lib/web-server/dispatchers/dispatch-servlets.rkt
<unknown procedure> at:
  line 131, column 8, in file /root/.racket/6.12/pkgs/web-server-lib/web-server/private/dispatch-server-with-connect-unit.rkt

A number of people have tried out the GHC plugin and given me feedback. Here's a summary of the issues that would require changes within Herbie itself to add to the plugin:

1. Support for the hypot, log1p, and expm1 functions
2. The ability to selectively disable certain transformations. People have specifically requested the ability to disable the taylor series transformations (results in worse accuracy on arbitrary precision numbers) and the if-statement transformations (because they require extra constraints in the haskell code).
3. Example values that the original expression performs poorly on but the improved expression performs well on. I imagine these could easily be printed to stdout after the improved expression is printed.
4. Some way to annotate the range that the math expression is actually going to operate on. That way Herbie doesn't optimize for a case that can never occur in practice.

Thanks for all the great work with Herbie!

The Docker instructions tell us to use the uwplse/herbie image but do not specify a tag, so Docker will automatically use the one called latest.

For some reason, the latest tag on Docker Hub is 6 months old, and does not point to the actual most recent version, 1.3: https://hub.docker.com/r/uwplse/herbie/tags

I think you should be able to do

docker tag uwplse/herbie:1.3 uwplse/herbie:latest
docker push uwplse/herbie:latest

This is a follow up to #73. I'd like herbie to report the values that it used during the sampling process. A format that would work well for me is if for each sampled value, you print a line to stdout

sample: sampleValue originalFunctionValue modifiedFunctionValue trueFunctionValue

The GHC plugin could then filter through these values to select a sample to report to the end user.

the best approximation is too far from the herbie solutions

the claim by herbie that Average Error: 9.9 → 0.5
Time:20.5s Precision:64
Internal precision: 1152

(x - sin(x))  x = 0.5
the best approximation is      0.020574461395796998
the two herbie solutions
      with numerics disabled:   0.020574466765873017
      with numerics enabled:    0.020574466765873014

herbie shell --seed '#(3879704165 3744610602 266041085 3070558684 3536960646 1218547627)'
(FPCore (x)
:name "x - sin(x)"
(- x (sin x)))

The package catalog entry for the herbie package has the following:

This probably doesn't do what you meant. Version exceptions aren't for declaring different versions of your package in the sense of "herbie version 1.1", they're for declaring alternate implementations of your package for users with older Racket installations. For instance, you might use a function that only exists in version 6.7+ of Racket. You could make a branch of your repo that removes uses of that function, and then add a version exception stating that 6.6 users should install that instead.

The Racket package system currently does not have "versions". There is no way to declare a dependency on a specific version of a package, or provide multiple versions of your package at once via the catalog. This may change in the future, but it's the way things work right now.

Also, confusingly, the "Version Exceptions" line used to just say "Versions". That was fixed recently.

This is on OS X with Racket 6.2.1 64-bit:

$ racket herbie/reports/run.rkt bench/tutorial.rkt 
Starting 3 workers on 3 problems...
cannot instantiate `racket/gui/base' a second time in the same process
  context...:
   /Applications/Racket v6.2.1/share/pkgs/gui-lib/mred/private/wx/common/once.rkt: [running body]
   /Applications/Racket v6.2.1/share/pkgs/gui-lib/mred/private/wx/common/utils.rkt: [traversing imports]
   /Applications/Racket v6.2.1/share/pkgs/gui-lib/mred/private/wx/cocoa/utils.rkt: [traversing imports]
   /Applications/Racket v6.2.1/share/pkgs/gui-lib/mred/private/wx/cocoa/pool.rkt: [traversing imports]
   /Applications/Racket v6.2.1/share/pkgs/gui-lib/mred/private/wx/cocoa/init.rkt: [traversing imports]
   /Applications/Racket v6.2.1/share/pkgs/gui-lib/mred/private/wx/cocoa/platform.rkt: [traversing imports]
   /Applications/Racket v6.2.1/share/pkgs/gui-lib/mred/private/wx/platform.rkt: [running body]
   /Applications/Racket v6.2.1/share/pkgs/gui-lib/mred/private/kernel.rkt: [traversing imports]

I have this test:

(herbie-test (x y)
  "test"
  (acos (/ (+ (* x x) (* y y)) (* x y)))
)

and I get:

$ racket herbie/reports/run.rkt test.rkt
Starting Herbie on 1 problems...
Seed: #(1429464981 3164586461 3490486657 2480488560 1127897174 3329686647)
  1/1   [   CRASH   ]   test

and the result page shows

[ERROR] After many loops in prepare-points still have insufficient number of sampled points

    run-improve50 in /local/herbie/herbie/interface/interact.rkt:238:0
    #f in /opt/racket-6.4/share/racket/collects/racket/private/more-scheme.rkt:261:28

Please report this bug!

I wanted to test a program which uses the abs() function and herbie kept crashing so I made the simplest example I could imagine:

(herbie-test (x) "Absolute value" (abs x) )

But it still crashes:

racket herbie/reports/run.rkt bench/abs.rkt
Starting Herbie on 1 problems...
Seed: #(3724242573 3093775555 813327471 3904585134 2190759848 3623097472)
1/1 [ CRASH ] Absolute value

Here's all the files: report.zip

Hello,

I just tried to install herbie on Ubuntu 18.10 (somehow, the very first expression I tried is too complex for the web demo and times out).
I installed racket 7.1 from the indicated ppa:

racket -v
Welcome to Racket v7.1.

When running the tests, all failed:

~/.racket/7.1/bin/herbie report bench/tutorial.fpcore graphs/
Starting Herbie on 3 problems (seed: 1537437092)...
  1/3   [   CRASH   ]   Expanding a square
  2/3   [   CRASH   ]   Commute and associate
  3/3   [   CRASH   ]   Cancel like terms

I also tried to install from sources, but with similar results:

git clone https://github.com/uwplse/herbie
cd herbie/
racket src/herbie.rkt report bench/tutorial.fpcore graphs/
Starting Herbie on 3 problems (seed: 1855190789)...
  1/3   [   CRASH   ]   Expanding a square
  2/3   [   CRASH   ]   Commute and associate
  3/3   [   CRASH   ]   Cancel like terms

See below the infos from the report.html:

herbie shell --seed 1855190789 
(FPCore (x)
  :name "Expanding a square"
  (- (* (+ x 1) (+ x 1)) 1))

herbie shell --seed 1855190789 
(FPCore (x y z)
  :name "Commute and associate"
  (- (+ (+ x y) z) (+ x (+ y z))))

herbie shell --seed 1855190789 
(FPCore (x)
  :name "Cancel like terms"
  (- (+ 1 x) x))

and the backtrace from the first one:

mpfr_set_nan: implementation not found; arguments: #<_mpfr> | L | C
-- | -- | --
new-mpfr | /usr/share/racket/pkgs/math-lib/math/private/bigfloat/mpfr.rkt | 335 | 0
bf | /usr/share/racket/pkgs/math-lib/math/private/bigfloat/mpfr.rkt | 601 | 2
(unnamed) | /usr/share/racket/collects/racket/contract/private/arrow-higher-order.rkt | 357 | 33
f140 | unknown
f140 | unknown
f140 | unknown
eval-prog | /home/myhome/softs/herbie/src/programs.rkt | 150 | 0
make-exacts* | /home/myhome/softs/herbie/src/points.rkt | 138 | 0
loop | /home/myhome/softs/herbie/src/points.rkt | 158 | 2
prepare-points | /home/myhome/softs/herbie/src/points.rkt | 214 | 0
setup-prog!32 | /home/myhome/softs/herbie/src/mainloop.rkt | 72 | 0
run-improve41 | /home/myhome/softs/herbie/src/mainloop.rkt | 234 | 0
.../more-scheme.rkt:261:28 | unknown
(unnamed) | /usr/share/racket/collects/racket/private/more-scheme.rkt | 261 | 28

Do not hesitate to ask for more tests...

Since valid-bindings came from intersecting bindings-set with bindings*, the following test is always true. This might mark rules as applied by mistake. Did you mean to flip the arguments around? Doing so seems to fix a problem I had when my saturation got stuck.

https://github.com/uwplse/herbie/blob/b730b8558e1d0f380f217c60769c31861f417f6a/src/core/simplify.rkt#L106

H! Thanks for making Herbie which seems to be a fantastically useful tool! I've just started using it on macOS and it crashed on the following (and prompted me to file this bug):

herbie shell --seed 1216834558 -o precision:double
(FPCore (r or d)
  :name "(/ (+ (- (* r r) (* or or)) (* d d)) (* 2 d))"
  :pre (and (< 0 r 10000) (< or 10000) (< 0 (* 2 d) 10000) (< d (fabs (- r or))) (< (fabs (- (+ r or) d)) 0.0001))
  (/ (+ (- (* r r) (* or or)) (* d d)) (* 2 d)))

Typing the quadratic equation (-b+sqrt(b^2-4ac))/(2*a) using the default precision (64 bit float) produces a coherent answer:

But using the web options to set the precision to 32 bits float, let's say produces something which is not so useful:

I was expecting a similar answer to the 64 bit precision but with different thresholds.

Assuming the answer is correct, I'm okay sacrificing a little overhead to get extra numerical stability, but throwing in a cubic root seems too much (especially when some languages might not have the high precision cubic root function which means I might have to implement that myself, leading to higher errors).
Also:

• Is the cubic root of the expression multiplied by itself 3 times really helping with accuracy? If so it will be very hard to explain to other people looking at my code.
• In the else condition, can the "2" in the denominator be cancelled? same for the "a" term.

Most programming languages use infix notation, but Herbie requires (I think) prefix notation. If Herbie supported infix, it would be easier for many people to test equations and then update code with Herbie's results. I bet that many cases would be just copy and paste.

The web demo supports infix for input and gives results with nicely formatted math symbols. It would be great to provide infix output there as well.

I just tried using the instructions here, and they don't work; I get this instead:

$ docker run -it -v $PWD/input:/herbie/bench -v $PWD/output:/herbie/graphs uwplse/herbie bench/
call-with-input-file: cannot open directory as a file
  path: /herbie/bench/
  system error: errno=?
  context...:
   /herbie/herbie/reports/datafile.rkt:86:0: read-datafile
   /herbie/herbie/reports/make-report.rkt:417:0: render
   (submod /herbie/herbie/reports/make-report.rkt main): [running body]

If I specify an input file, I get this (changing the -v $PWD/input to -v $PWD/bench with $PWD=herbie repo:

$ docker run -it -v $PWD/bench:/herbie/bench -v $PWD/output:/herbie/graphs uwplse/herbie bench/tutorial.rkt
bench/tutorial.rkt::2: read-json: bad input
  context...:
   /usr/share/racket/collects/syntax/readerr.rkt:15:2: -raise-read-error
   /herbie/herbie/reports/datafile.rkt:86:0: read-datafile
   /herbie/herbie/reports/make-report.rkt:417:0: render
   (submod /herbie/herbie/reports/make-report.rkt main): [running body]

I'm trying to use Herbie's web shell by following the docs:

Running the web shell

Running the web shell in Docker requires exposing the ports inside the container. Use the -p option to Docker to expose whatever ports Herbie chooses to use, and then use the --port option to Herbie to choose that port.

$ docker run -itp \
   uwplse/herbie web --quiet

The prose didn't make much sense to me, so I skipped to the command:

$ docker run -itp \
>     uwplse/herbie web --quiet
docker: Invalid containerPort: uwplse.
See 'docker run --help'.

Right. docker run -p is of course --publish, which expects a port specification, which the docs don't provide. docker can choose its own ports, but it works differently than these docs suggest, and in any case Herbie's Dockerfile doesn't touch Docker networking at all so I guess everything is supposed to be specified when creating a container.

Herbie needs to be told which port to use, and Docker needs to be told to expose that port to the host. Let's tell everything to use port 8080. Let's also docker run --rm so that the container gets destroyed on exit. That gets us:

$ docker run -it --rm -p 8080:8080 uwplse/herbie web --quiet --port 8080
Your Web application is running at http://localhost:8080.
Stop this program at any time to terminate the Web Server.

Brilliant!

$ curl http://localhost:8080/
curl: (52) Empty reply from server

Right.

$ docker ps
CONTAINER ID  IMAGE          COMMAND                 CREATED         STATUS          PORTS                   NAMES
d28a07c3e67d  uwplse/herbie  "racket /src/herbie/…"  24 seconds ago  Up 23 seconds   0.0.0.0:8080->8080/tcp  awesome_feynman
$ docker exec -it awesome_feynman bash
root@d28a07c3e67d:/# apt-get update && apt-get install net-tools
…
root@d28a07c3e67d:/# netstat -lnp
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address           Foreign Address         State       PID/Program name
tcp        0      0 127.0.0.1:8080          0.0.0.0:*               LISTEN      1/racket        
Active UNIX domain sockets (only servers)
Proto RefCnt Flags       Type       State         I-Node   PID/Program name    Path

Herbie is running, listening on port 8080. Docker for Mac is forwarding port 8080 to the container – but the Herbie is listening on the container's localhost, so it's not willing to accept connections from outside the container, i.e. from the host machine.

The normal Docker thing to do is to make a container listen for connections on a fixed port and let the user worry about exposing it. For example, the nginx image listens on the container's 0.0.0.0:80, which I can map to port 8080 on the host machine:

$ docker run -it --rm -p 8080:80 --name demo -d nginx
1ff954810a84c51fcd00577cb44b7e912b3a0d58b0d91858d0b6cdbf6976c992
$ $ curl -s http://localhost:8080 | head -n4
<!DOCTYPE html>
<html>
<head>
<title>Welcome to nginx!</title>
$ docker exec -it demo bash
root@1ff954810a84:/# apt-get update && apt-get install net-tools
…
root@1ff954810a84:/# netstat -lnp
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address           Foreign Address         State       PID/Program name    
tcp        0      0 0.0.0.0:80              0.0.0.0:*               LISTEN      1/nginx: master pro 
Active UNIX domain sockets (only servers)
Proto RefCnt Flags       Type       State         I-Node   PID/Program name     Path

How do I get Herbie to listen on 0.0.0.0/INADDR_ANY instead of binding to localhost?

If i pass --threads, it does not work, if i do not pass it, it works.

~/src/herbie$ racket ~/src/herbie/src/reports/run.rkt --fuel 4 --threads 8 soe.rkt
place-channel-put: value not allowed in a message
  value: '#hash((generate . (rr taylor simplify)) (precision . (double)) (reduce . (regimes taylor simplify avg-error)) (rules . (arithmetic polynomials fractions exponents trigonometry)) (setup . (simplify)))
  message: '(init rand #(4288444397 53123915 1983666923 3817731407 1010350898 2389601263) flags #hash((generate . (rr taylor simplify)) (precision . (double)) (reduce . (regimes taylor simplify avg-error)) (rules . (arithmetic polynomials fractions exponents trigo...
  context...:
   /home/lebedevri/src/herbie/src/reports/thread-pool.rkt:94:0: run-workers25
   /home/lebedevri/src/herbie/src/reports/thread-pool.rkt:159:0: get-test-results43
   /home/lebedevri/src/herbie/src/reports/run.rkt:25:0: make-report
   /home/lebedevri/src/herbie/src/reports/run.rkt: [running body]
~/src/herbie$ racket ~/src/herbie/src/reports/run.rkt --fuel 4 --threads 1 soe.rkt
place-channel-put: value not allowed in a message
  value: '#hash((generate . (rr taylor simplify)) (precision . (double)) (reduce . (regimes taylor simplify avg-error)) (rules . (arithmetic polynomials fractions exponents trigonometry)) (setup . (simplify)))
  message: '(init rand #(308998630 4110963146 1817948267 4251213394 1222084849 803791841) flags #hash((generate . (rr taylor simplify)) (precision . (double)) (reduce . (regimes taylor simplify avg-error)) (rules . (arithmetic polynomials fractions exponents trigo...
  context...:
   /home/lebedevri/src/herbie/src/reports/thread-pool.rkt:94:0: run-workers25
   /home/lebedevri/src/herbie/src/reports/thread-pool.rkt:159:0: get-test-results43
   /home/lebedevri/src/herbie/src/reports/run.rkt:25:0: make-report
   /home/lebedevri/src/herbie/src/reports/run.rkt: [running body]
~/src/herbie$ racket ~/src/herbie/src/reports/run.rkt --fuel 4 --threads yes soe.rkt
place-channel-put: value not allowed in a message
  value: '#hash((generate . (rr taylor simplify)) (precision . (double)) (reduce . (regimes taylor simplify avg-error)) (rules . (arithmetic polynomials fractions exponents trigonometry)) (setup . (simplify)))
  message: '(init rand #(621398415 1604270261 3634038359 1009051999 3837243482 1690531221) flags #hash((generate . (rr taylor simplify)) (precision . (double)) (reduce . (regimes taylor simplify avg-error)) (rules . (arithmetic polynomials fractions exponents trig...
  context...:
   /home/lebedevri/src/herbie/src/reports/thread-pool.rkt:94:0: run-workers25
   /home/lebedevri/src/herbie/src/reports/thread-pool.rkt:159:0: get-test-results43
   /home/lebedevri/src/herbie/src/reports/run.rkt:25:0: make-report
   /home/lebedevri/src/herbie/src/reports/run.rkt: [running body]
~/src/herbie$ racket ~/src/herbie/src/reports/run.rkt --fuel 4 soe.rkt
Starting Herbie on 1 problems...
Seed: #(1001121629 1217222885 1342864862 3040828424 1285742257 2113176950)
  1/1   [ 40617.98ms]   ( 0→ 0) specific orbital energy
~/src/herbie$ 

Take the tutorial example problem:

(herbie-test (x)
  "Cancel like terms"
    (- (+ 1 x) x))

This works fine:

∃ racket herbie/reports/run.rkt test.rkt 
Starting Herbie on 1 problems...
Seed: #(964799319 2403253534 3458084204 4281689332 4152401633 941466651)
  1/1   [ 2316.758ms]   (30→ 0)   Cancel like terms

Now try to constrain the variable to be a positive integer, per the documentation:

(herbie-test ([x (positive int)])
  "Cancel like terms"
    (- (+ 1 x) x))

Herbie immediately crashes:

Starting Herbie on 1 problems...
Seed: #(981939873 3516983843 1946080710 3586337569 517302991 689376469)
cdr: contract violation
  expected: pair?
  given: '()
  context...:
   /home/sio/tmp/herbie/herbie/reports/make-graph.rkt:293:0: output-timeline
   /home/sio/tmp/herbie/herbie/reports/make-graph.rkt:141:0: make-traceback
   /home/sio/tmp/herbie/herbie/reports/thread-pool.rkt:149:4: for-loop
   /home/sio/tmp/herbie/herbie/reports/thread-pool.rkt:141:0: run-nothreads33
   /home/sio/tmp/herbie/herbie/reports/thread-pool.rkt:156:0: get-test-results43
   /home/sio/tmp/herbie/herbie/reports/run.rkt:24:0: make-report
   /home/sio/tmp/herbie/herbie/reports/run.rkt: [running body]

Note that this doesn't happen constraining that variable in other ways, e.g.,

(herbie-test ([x (< 0 int 10000000)])
  "Cancel like terms"
    (- (+ 1 x) x))

works fine.

I'm using revision fc746ec (current master).

For this line of the tutorial:

https://github.com/uwplse/herbie/blob/master/www/doc/1.2/tutorial.html#L82

the image tutorial-report-image.png is not in the repo.

Also, the tutorial link from page http://herbie.uwplse.org/doc/latest/installing.html leads to the non-existent page http://herbie.uwplse.org/doc/latest/doc/1.0/tutorial.html

Greetings,

I've been trying to run herbie (ecfce49) on a somewhat complicated expression which times out after ten minutes:

∃ time racket src/reports/run.rkt --fuel 4  foo.rkt 
Starting Herbie on 1 problems...
Seed: #(403722969 2786979204 1104208179 17108147 1776556736 163621203)
  1/1   [  timeout  ]   foo

real    10m8.320s
user    9m57.677s
sys 0m3.987s

I checked the usage for reports/run.rkt, but it doesn't support a --timeout option; herbie.rkt does, but doesn't seem to support outputting a report (the header comment at the top of the file suggests it does with -o, but it's not actually matched in the option parser). I tried modifying the constant *timeout* in sandbox.rkt, which seems to do the trick. Is this the only way to increase the timeout, or have I missed something?

Thanks!

Input:

(herbie-test (x)
"crash"
(+ 3.91693213e-03
(* -6.49439549e+04 x x x x)))

graph.html:

assert: (eq? extracted processed) returned false! Extra info: Extracted is #<alt-delta (λ (x) (+ 0.00391693213 (* (sqr (sqr x)) -64943.9549)))>, but we gave it (λ (x) (+ 0.00391693213 (* (sqr x) (* (sqr x) -64943.9549))))

Debug log:

• [misc]progress: [Phase 1 of 3] Setting up.
• * * [misc]progress: [1/2] Preparing points
• * * [misc]progress: [2/2] Setting up program.
• [enter]simplify: Simplifying (+ 0.00391693213 (* (* (* (* -64943.9549 x) x) x) x))
• * [misc]simplify: iters left: 6 (8 enodes)
• * [misc]simplify: iters left: 5 (30 enodes)
• * [misc]simplify: iters left: 4 (67 enodes)
• * [misc]simplify: iters left: 3 (123 enodes)
• * [misc]simplify: iters left: 2 (224 enodes)
• * [misc]simplify: iters left: 1 (491 enodes)
• [enter]simplify: Simplifying (* (sqr x) (* (sqr x) -64943.9549))
• * [misc]simplify: iters left: 5 (5 enodes)
• * [misc]simplify: iters left: 4 (19 enodes)
• * [misc]simplify: iters left: 3 (48 enodes)
• * [misc]simplify: iters left: 2 (72 enodes)
• * [misc]simplify: iters left: 1 (122 enodes)
• [exit]simplify: Simplified to (* (sqr (sqr x)) -64943.9549)

(FPCore ()
  :name "(1 / (((1 + sqrt(5)) / 2) - ((1 - sqrt(5)) / 2)))"
  (/ 1.0 (- (/ (+ 1.0 (sqrt 5.0)) 2.0) (/ (- 1.0 (sqrt 5.0)) 2.0))))

This simplifies to 1 / ((sqrt(5) / 2) + (sqrt(5) / 2)).

However the two terms in the denominator could easily be combined to eliminate the division by 2: 1 / sqrt(5)

Herbie appears to currently optimize across the entire floating point space, whereas some expressions have a known set of possible inputs. Take this great circle distance formula, for example (which I've since discovered is already in bench/latlong.rkt without the hardcoded 6371e3 value):

(herbie-test (lat0 lon0 lat1 lon1)
  "Great circle distance"
  (* 6371e3
    (acos
      (+ (* (sin lat0) (sin lat1))
      (* (cos lat0) (cos lat1) (cos (abs (- lon0 lon1))))))))

We know that lat0 and lat1 must lie between or including -pi/2 to pi/2, while lon0 and lon1 must lie between or including -pi to pi. With these constraints taken into account, herbie might be able to better optimize.

The documentation for command line arguments is a little confusing for report because intermediate options go between herbie report and input output. I think this can be fixed by updating the documentation to include examples for each Herbie mode.

It would also possibly be nice if the command line error reports included a link to the documentation at: http://herbie.uwplse.org/doc/latest/options.html

Hi, I keep getting errors in the web demo with presumably simple equations like 't^2*(a+b)':

cheers, lukas

herbie shell --seed '#(2967413098 1918494392 3037920959 2128877088 1201842593 460552578)'
(FPCore (t a b)
:name "t^2* (a + b)"
(* (pow t 2) (+ a b)))

The floudas1 and floudas2 benchmarks cause Herbie to consume all available memory and then crash. For reference, floudas1 is the unassuming

(FPCore (x1 x2 x3 x4 x5 x6)
 :name "floudas1"
 :precision binary64
 :pre (and (<= 0 x1 6) (<= 0 x2 6) (<= 1 x3 5)
           (<= 0 x4 6) (<= 0 x5 6) (<= 0 x6 10)
           (>= (- (+ (* (- x3 3) (- x3 3)) x4) 4) 0)
           (>= (- (+ (* (- x5 3) (- x5 3)) x6) 4) 0)
           (>= (+ (- 2 x1) (* 3 x2)) 0)
           (>= (- (+ 2 x1) x2) 0)
           (>= (- (- 6 x1) x2) 0)
           (>= (- (+ x1 x2) 2) 0))
 (- (- (- (- (- (* -25 (* (- x1 2) (- x1 2))) (* (- x2 2) (- x2 2))) (* (- x3 1) (- x3 1))) (* (- x4 4) (- x4 4))) (* (- x5 1) (- x5 1))) (* (- x6 4) (- x6 4))))

I see that you are nearing 1.0 release, congratulations!

I would like to make a small feature request (for users of Herbie): could you please write a tutorial on how to use it, for example on quadratic formula? And document how does it perform compared to, say:
https://en.wikipedia.org/wiki/Loss_of_significance#A_better_algorithm

Btw., last time I saw, the demo timed out on it:
https://www.reddit.com/r/programming/comments/42g7p7/new_tool_herbie_automatically_rewrites_arithmetic/cza2rfj

Debian sid, commit 1162a7e

racket ~/src/herbie/src/reports/run.rkt --fuel 4 /tmp/test.rkt

Starting Herbie on 1 problems...
Seed: #(3729278177 3588225692 2076616249 3282344076 1976024238 1618906825)
  1/1   [   CRASH   ]   2

1. mk-pcontext in /home/lebedevri/src/herbie/src/points.rkt:22:0
2. for-loop in /home/lebedevri/src/herbie/src/core/alt-table.rkt:75:2
3. split-atab in /home/lebedevri/src/herbie/src/core/alt-table.rkt:74:0
4. #f in /usr/share/racket/collects/racket/contract/private/arrow-val-first.rkt:357:18
5. split-table in /home/lebedevri/src/herbie/src/glue.rkt:171:0
6. get-final-combination in /home/lebedevri/src/herbie/src/mainloop.rkt:264:0
7. run-improve50 in /home/lebedevri/src/herbie/src/mainloop.rkt:237:0
8. .../more-scheme.rkt:261:28 in ???

/tmp/test.rkt:

(herbie-test (alt mu vx vy)
  "2"
  (sqrt (/ (+ (- (+ (* (pow alt 2) (pow vx 4)) (* (* (pow alt 2) (pow vx 2)) (pow vy 2))) (* (* (* 2 alt) mu) (pow vx 2))) (pow mu 2)) (pow mu 2)))
)

debug.txt

Using the latest Herbie image from Docker Hub, and the instructions here:

% docker run -it --rm -p 8000:80 uwplse/herbie
Herbie 1.2 with seed 1364449522
Find help on <https://herbie.uwplse.org/>, exit with Ctrl-C
Your Web application is running at http://localhost.
Stop this program at any time to terminate the Web Server.

If I connect to http://localhost:8000/, the TCP connection succeeds but the HTTP server says nothing.

% curl -vvv http://localhost:8000
* Rebuilt URL to: http://localhost:8000/
*   Trying ::1...
* TCP_NODELAY set
* Connected to localhost (::1) port 8000 (#0)
> GET / HTTP/1.1
> Host: localhost:8000
> User-Agent: curl/7.54.0
> Accept: */*
> 
* Empty reply from server
* Connection #0 to host localhost left intact
curl: (52) Empty reply from server

Herbie failed on the following input:

(-((az - dz) - (vz/vx) * (ax - dx)) - ((bz - az) - ((vz/vx) * (bx - ax)))*gz) / (((dz - cz) - (bz - az)) - (vz/vx) * ((dx - cx) - (bx - ax)))*gz + ((cz - az) - (vz/vx) * (cx - ax))

which resulted in the following command

$ herbie shell --seed 2042407083
(FPCore (az dz vz vx ax dx bz bx gz cz cx)
  :name "(-((az - dz) - (vz/vx) * (ax - dx)) - ((bz - az) - ((vz/vx) * (bx - ax)))*gz) / (((dz - cz) - (bz - az)) - (vz/vx) * ((dx - cx) - (bx - ax)))*gz + ((cz - az) - (vz/vx) * (cx - ax))"
  (+ (* (/ (- (- (- (- az dz) (* (/ vz vx) (- ax dx)))) (* (- (- bz az) (* (/ vz vx) (- bx ax))) gz)) (- (- (- dz cz) (- bz az)) (* (/ vz vx) (- (- dx cx) (- bx ax))))) gz) (- (- cz az) (* (/ vz vx) (- cx ax)))))

with the following backtrace:

flonum->ordinal: contract violation expected: Float given: +inf.f in: the 1st argument of (-> Float any) contract from: <pkgs>/math-lib/math/private/flonum/flonum-bits.rkt blaming: <pkgs>/herbie/interface.rkt (assuming the contract is correct) at: <pkgs>/math-lib/math/private/flonum/flonum-bits.rkt:9.9 | L | C
-- | -- | --

Packaging Herbie with the Racket package manager will make Herbie easier to install—it'll no longer require finding the install files on your own. There are additional benefits:

• Herbie will be compiled when installed, shrinking startup time
• We'll also have the ability to separate parts of it into external packages.

Finally, it'll make the upgrade path for Herbie simpler, which is important now that we have upgrades.

I entered log(pow(a, r) - pow(b, r)) into the web demo, and I got

log((log(a) - log(b)) * ((r * (0.5 * r)) * (log(a) + log(b)) + r))

These expressions are not equivalent. For example, on inputs a = 3, b = 2, r = 4
the former one gives 4.174387269895637 and the latter one 2.0060409356897058.

Should the ormap below be andmap instead? Since an expression's arguments should all be enodes?

https://github.com/uwplse/herbie/blob/6b785901da9d9661d37c072f7e3ad5f0e5422108/src/core/enode.rkt#L209

Right now it seems each eclass may contain multiple enodes that point to equivalent expressions. I'm not sure if this is as designed, since the following line in egraph.rkt intentionally performs deduplication (so whoever wrote the code must be aware of the situation):

https://github.com/uwplse/herbie/blob/e26cdb8327c62adb02cbaae52bdd24dae3fab69e/src/core/egraph.rkt#L362

However it seems there can be quite a lot of duplication. I wrote the following code to compare the number of total nodes and the number of unique nodes, and after a few iterations on the input there are 698 unique nodes, but 1094 total nodes.

(define input '(* 5 (+ (* -1 a) (* (* -1 b) (* -1 a)))))

(define (unique-nodes eg)
  (foldr + 0 (map (compose length 
                           ((partial remove-duplicates) #:key enode-expr) 
                           pack-members) 
                  (egraph-leaders eg))))

(define (total-nodes eg)
  (foldr + 0 (map (compose length pack-members) (egraph-leaders eg))))

In order to invoke Herbie from other tools, it would be useful to have a command line interface that lets me provide an input file and get machine-readable output written to stdout instead of the filesystem, without generating graphs.

The web demo, even on a simple x expression fails.

It seems there's currently no way to specify a subset of interest of the function domain in the web interface. IIUC (although the documentation is not very clear on this) it is possible to do this using the :pre property in the shell (adding an example to the docs would probably also help)

If I input erf(x) - erf(y) on Herbie, it outputs the same expression for all x,y. But erf(x) - erf(y) suffers catastrophic cancellation if x,y are of the same sign and large. A more accurate evaluation is possible with the rules:

erf(x) - erf(y) 
   -> erf(x) - erf(y)        (if x and y are of different sign)
   -> erfc(y) - erfc(x)       (if x and y are positive)
   -> erfc(-x) - erfc(-y)   (if x and y are negative)

Why Herbie misses this transformation?

With develop at db362f1 (a day or two old), running herbie report with a docker container and the attached .fpcore file, I'm seeing the following crash:

Starting Herbie on 1 problems (seed: 1591928843)...
match-define: no matching clause for #f
  location...:
   src/herbie/programs.rkt:266:9
  context...:
   /usr/share/racket/collects/racket/match/runtime.rkt:24:0: match:error
   /src/herbie/programs.rkt:258:4: loop
   f429
   /src/herbie/programs.rkt:255:0: expand-parametric
   /src/herbie/web/make-graph.rkt:418:0: render-history
   /src/herbie/web/make-graph.rkt:225:0: make-graph
   /src/herbie/web/thread-pool.rkt:27:4: for-loop
   /src/herbie/web/thread-pool.rkt:12:0: run-test11
   /src/herbie/web/thread-pool.rkt:142:4: for-loop
   .../more-scheme.rkt:261:28
   /src/herbie/web/thread-pool.rkt:135:0: run-nothreads36
   /src/herbie/web/thread-pool.rkt:149:0
   /src/herbie/web/run.rkt:24:0: run-tests40
   (submod /src/herbie/herbie.rkt main): [running body]

Interestingly, with top-of-tree develop at 670da46, instead I'm seeing

Starting Herbie on 1 problems (seed: 985575795)...
'(#<interval> #<interval>)
'(#<interval>)
Fontconfig error: Cannot load default config file
  1/1	[ 159555.9ms]	(38→35)	sphere quadratic discriminant

bug.txt

Following the installation instructions here (running with $PWD as a herbie checkout, I get cannot open file:

$ racket herbie/reports/run.rkt bench/hamming/
default-load-handler: cannot open module file
  module path: #<path:/home/pwaller/.local/src/herbie/herbie/reports/run.rkt>
  path: /home/pwaller/.local/src/herbie/herbie/reports/run.rkt
  system error: No such file or directory; errno=2
  context...:
   standard-module-name-resolver

It is clear that path:/home/pwaller/.local/src/herbie/herbie/reports/run.rkt doesn't exist. If I modify the command to src/reports/run.rkt, I get this:

$ racket src/reports/run.rkt bench/hamming/
src/formats/datafile.rkt:81:21: group-by: unbound identifier in module
  in: group-by
  context...:
   standard-module-name-resolver
   standard-module-name-resolver
   standard-module-name-resolver

I know nothing of racket, so I can't debug any further. I'm using racket v6.2 on Ubuntu 15.10. The installation instructions imply that racket >= v6.1 will work.

on the web demo of herbie we can see results up to one digit after the period. Is there a flag/way to increase the precision of the input/output error from the command line output, where it's only integers ?

I have a feeling it doesn't display these digits because the demo is using 128 bit floating point integers and the command line version is using 64 bit. But I'd rather have confirmation.

I made a program that calls herbie and asks it queries, now I'm fairly certain that my program generates the same thing every time but herbie doesn't

$ MYPROGRAM
Seed: #(3436758664 1019234600 1918722173 3318719774 3811300631 1059234183)
(FPCore (c x y b) (* (+ (/ (hypot x y) b) c) b))
(FPCore (c x y b) (+ (hypot x y) (* b c)))
$ MYPROGRAM
Seed: #(3436758664 1019234600 1918722173 3318719774 3811300631 1059234183)
(FPCore (b c x y) (* (+ (/ (hypot x y) b) c) b))
(FPCore (b c x y) (+ (hypot x y) (* b c)))
$ MYPROGRAM
Seed: #(3436758664 1019234600 1918722173 3318719774 3811300631 1059234183)
(FPCore (x y b c) (* (+ (/ (hypot x y) b) c) b))
$ 

When i run racket herbie/reports/run.rkt bench/hamming/
this error appeart:
herbie/reports/thread-pool.rkt:184:15: set!: cannot mutate module-required identifier in: *seed*

For the installation, i follow the instruction of the Readme. (the last commit my git is d8469da79f08520ed088b55eafa31e6e6bb9aa1d)

For information, I have Racket v6.3 and i'm on arch linux.