Arc Forumnew | comments | leaders | submit | waterhouse's commentslogin
5 points by waterhouse 446 days ago | link | parent | on: How many people still lurk here?

Hello there.

(This experiment also serves as a sample of how regularly the lurkers lurk.)


4 points by lojic 420 days ago | link

True :)

I had high hopes for Arc over a decade ago, then it languished, then pg stopped participating.... then I looked at Racket (then PLT-Scheme) since that's what Arc was built on and realized Racket was the language I was looking for :)

I still pop in occasionally out of curiosity.


2 points by waterhouse 834 days ago | link | parent | on: Multiple Return Values

The corresponding macro in Common Lisp has an 18-character name.

  ; SBCL
  * (destructuring-bind (x y) '(1 2) (+ x y))
  ; Arc
  arc> (let (x y) '(1 2) (+ x y))


The first (and only) reason that comes to my mind is: efficiency. Calling a function that takes rest args means allocating a list at runtime; the usual expansion for "do" is a direct call to a lambda, which the Racket compiler seems able to handle with no runtime cost. Thus:

  arc> (def do-func args last.args)
  #<procedure: do-func>
  arc> (mac do-macro args `((fn () ,@args)))
  #(tagged mac #<procedure: do-macro>)
  arc> (time:repeat 1000000 (do-func 1 2 3))
  time: 270 cpu: 270 gc: 6 mem: -4392856
  arc> (time:repeat 1000000 (do-macro 1 2 3))
  time: 69 cpu: 70 gc: 0 mem: 928
  arc> (time:repeat 1000000 1 2 3)
  time: 67 cpu: 68 gc: 0 mem: 128
It is not too far-fetched an idea for a compiler to eliminate the runtime overhead of the calls to "do-func". Basically this would require assuming that "do-func" will not be redefined at runtime--which is permitted in Arc, so it would require the compiler to make optimistic assumptions and be prepared to invalidate the code when they are violated (i.e. if someone actually does redefine "do-func" at runtime). I've heard the best Javascript engines do this, but Racket does not.

In your use case, having a "do" that works at all is better than none, and I don't think there is any logical problem with doing so. (Strictly speaking, it makes it possible to "do" [!] more things, since you can't apply a macro.)


2 points by Pauan 1292 days ago | link

That's a good point. In Nulan, you can't redefine things (all variables are constant). I'm not so worried about performance right now. My main concern is simplicity, since implementing "do" as a macro introduces a lot of extra complexity (because Nulan compiles to JavaScript).


3 points by waterhouse 1371 days ago | link | parent | on: Re: waterhouse's AVL trees

Thank you for your kind words. I'm glad you've found my post useful. And that's a good catch about node/r.

It looks like the two versions of node/r differ just in the case when (depth x!lf) = (depth x!rt) [and likewise for y], which it appears I had assumed would not be true; perhaps that was valid for insertions but not deletions. (I must admit deletions came as a bit of an afterthought, as evidenced by the typos in "aremove".) I'm pleased that the resolution is so simple.

Anyway, thanks to you, we now have AVL trees that are actually tested and proven to work.


Congratulations, zck!

If you want to see my quasiquote, here it is defined:


2 points by zck 1488 days ago | link

Congrats to you too!

What's the future path for emiya? It looks really cool, but it seems like you haven't done much with it since last fall.


2 points by waterhouse 1487 days ago | link

Well, since you ask. :-) And since the judging is all done, I might as well update it. So. Currently things are broken up into "dyn-cont", which has the Arc interpreter, "arc-boot", which is the code the interpreter will run on startup, and "memory-system", which is where I'm prototyping the stuff the next version of "dyn-cont" will run on: fake assembly code, which is a preparation for writing real assembly code.


I'm going there.


1 point by waterhouse 2301 days ago | link | parent | on: Reading from a file

The "read" procedure will read only a single Arc expression at a time. If you want to read a line, there is a "readline" procedure.

Also, it is correct that you make code look like code by putting two spaces before each line of code.

  After "code." in the above paragraph, there is a newline, then
  another newline, then two spaces, then "After [...] newline, then",
  then another newline, then two spaces, then "another", and so on.


1 point by jsgrahamus 2301 days ago | link

See reply.


1 point by jsgrahamus 2301 days ago | link

Thanks for the editing tips.

  arc> dev
  arc> (w/infile inf dev
          (whiler l (readline inf)
             (if (no (is l "\r"))
                 (prn l))))

  YT      Yeast   Yeast   Yeast
  YTNC    Yeast not Cryptococcus  Yeast not Cryptococcus  Yst not Cryptococcus
  YTSP    Yeast species   Yeast species   Yeast sp.nentgd  Group D, streptococcus  Group D, streptococcus  Group D
  oi      Over-inoculated Over-inoculated Over-inoculated
  orgnv   Organism non-viable     Organism non-viable     Organism non-viable
  oxnego  Oxidase Negative Other  Oxidase Negative Other  Oxidase Negative
  p27853  Pseudomonas aeruginosa ATCC 27853       Pseudomonas aeruginosa ATCC 27853       P. aerug ATCC27853
  pacica  Presumptive Acinetobacter lwoffi        Presumptive Acinetobacter lwoffi        Presumptive A.lwoffi
  stlu    Staphylococcus lugdunensis      Staphylococcus lugdunensis (coagulase negative species) S. lugdunensis


You might try looking at scsh, which is famous for its "Acknowledgments" section. It provides a convenient interface to Unix within Scheme 48.
Usage looks like this:

  $ rlwrap scsh
  Welcome to scsh 0.6.7 (R6RS)
  Type ,? for help.
  > (run (date))
  Fri Mar 30 00:10:46 PDT 2012
  > (run (| (ls) (grep -P ".tar.(gz|lrz)$")))
The 0 is the return value of the program. [One thing that threw me was that -i is read as the complex number that Racket would call 0-1i; you would have to type "-i" with quotes around it, or (lolololololz) -ii if your program handles multiple instances of the same switch fine.]

The author, Olin Shivers, has a paper[1] that describes the process control notation demonstrated above, and an awk-like notation, both written essentially as Scheme macros. (Actually, I think they are Scheme macros.) "Whenever necessary, the user can break out of the special-purpose notation and express complex computations in a general-purpose programming language. The Scheme embedding makes simple things easy, and complex things possible. The standalone little language only provides the former."

[1] A Universal Scripting Framework, or: Lambda: the ultimate "little language".


1 point by akkartik 2329 days ago | link

Yeah I am aware of scsh; I was thinking of it when I referred to fewer parens :)

Here's wart's equivalent for the first command:

  wart> date.

  wart> run date.
I want support for infix pipes and redirection operators. No matter how much lisp I use I can't get used to putting the pipe before different commands.

An alternative is to double down on lisp syntax but make the line editing much nicer. As nice as an emacs buffer.


4 points by waterhouse 2329 days ago | link | parent | on: Alleged real-time Schemes

RScheme looked like the most promising of these. It uses the terminology of "hard real-time" and "soft real-time" garbage collectors, and claims to have both, working from Wilson and Johnstone's algorithm [1]; also it claims to have threads and a C library interface, and implement nearly everything in R4RS and R5RS. The only warning sign is that nothing much seems to have been done with it since 2005.

However, I am cautiously pessimistic about RScheme for the moment, because I have created a fairly simple test case at which the (default, soft real-time) garbage collector appears to fail horribly (not collecting any garbage at all). I've emailed the developer, and we'll see if he can figure out what's happening and fix it. (Also the hard real-time GC doesn't build; he said he wasn't surprised at that.)

My test case is this loop--all on one line for command line convenience:

(let nub ((n 1000)) (if (= n 0) 0 (let ((h (let loop ((x 10000) (xs '())) (if (= x 0) (length xs) (loop (- x 1) (cons x xs)))))) (if (= 0 (modulo n 100)) (begin (display h) (newline)) 'meh) (nub (- n 1)))))

This does the following 1000 times: cons up a list of 10k elements, compute the length, maybe print the length, and proceed to the next iteration, by which time those 10k cons cells are now garbage. At any point during this computation, the entire set of live objects should be at most 10k cons cells plus the overhead of the loop (and of the RScheme runtime). A properly working Scheme with garbage collection should thus be able to run this in basically constant space; racket, for example, will slightly increase its memory use the first few times you run it, but it reaches a stable state quickly (60-70 MB on my machine here).

However, in RScheme, this causes the "rs" process to consume about 600 MB of memory (300 on a 32-bit system), and running the loop again makes it eat another ~600 (~300) MB; I've tested this on 64-bit Mac OS X as well as several 64- and 32-bit Linuxes across several machines. If we imagine that a cons cell is the size of eight pointers (which might be acceptable overhead for easy implementation), and therefore is 64 bytes on a 64-bit system (32 on 32-bit), and if we suppose that the garbage collector never succeeds in deleting anything, then running the above loop will create 10 million cons cells --> 640 million bytes (320 on 32-bit) = 610.3 MiB (305 MiB on 32-bit), which fits my results very closely.

So... Feel free to try to verify or disprove these results yourself. For convenience, here is a bash command that will download, build, and run RScheme all at once [if you have rlwrap, replace the last bit with "rlwrap ./build/bin/rs" to make things nicer]:

wget && tar xvf rs- && cd rs- && make stage1 && cd src && mkdir build && ./configure --prefix=$(pwd)/build && make all && ./build/bin/rs

I will post any good or bad news I hear from the developer. Meanwhile, with respect to RScheme, I suppose people could attempt to learn to fix it themselves, or learn things from reading the source (or the [1] paper).

Next, Ypsilon seems to build by extracting the source and typing "make" on Linux, and I have gotten it to present a working REPL (which, incidentally, runs my test case in roughly 10 MB of space). Typing "make" on my Mac makes it fail:

  ffi_stub_darwin.s:83:suffix or operands invalid for `push'
  pushl   %ebp #this is a line of code in question
It might be possible to get these things to work, either by figuring out the right build incantations or complaining to the Ypsilon developers (or, again, fixing things ourselves). And then I can see whether it's actually real-time enough for my demands. (My demands: never have to worry about GC for certain projects I at least fantasize about doing, which include implementing real-time games like Starcraft in Lisp.)

Feel free to help evaluate these options. If one of them works, it probably wouldn't be very hard to port any of our various Arc->Racket compilers to it.

[1] "Real-Time Non-Copying Garbage Collection", Wilson and Johnstone 1993:


1 point by akkartik 2328 days ago | link

Yeah, rs crashed when I tried to run the loop a second time. Looks like nothing is being reclaimed.

Update: It's hard to debug because linux kills the process when it OOMs


2 points by waterhouse 2455 days ago | link | parent | on: Nu Arc compiler

Racket seems fairly good at "lambda lifting", if that is the correct term. To demonstrate with adding the numbers from 1 to n: version 0 should pretty obviously be compiled into a loop; versions 1 and 2 are less obvious. In 64-bit "racket", versions 1 and 2 seem to take twice as long as the loop in version 0, but that's still much better than allocating lambdas; in 32-bit, the "twice as long" difference is smothered by the cost of allocating/GCing bignums. The last version is actually written in Arc, and 25x slower in arc3.1; though in 32-bit, the cost of handling bignums makes arc3.1 only 2x slower. The results of the 64-bit version seem to demonstrate that Racket successfully avoided allocating closures at runtime in all cases.

  (define (sum0 n)
    (let loop ((n n) (tt 0))
      (if (zero? n)
          (loop (- n 1) (+ n tt)))))
  (define sum1
    (λ (n)
      ((λ (f n tt)
         (if (zero? n)
             (f f (- n 1) (+ n tt))))
       (λ (f n tt)
         (if (zero? n)
             (f f (- n 1) (+ n tt))))
  (define sum2
    (λ (n)
      ((λ (f) (f f n 0))
       (λ (f n tt)
         (if (zero? n)
             (f f (- n 1) (+ n tt)))))))
  (= sum3
     (fn (n)
       ((fn (f n tt)
          (if (is n 0)
              (f f (- n 1) (+ n tt))))
        (fn (f n tt)
          (if (is n 0)
              (f f (- n 1) (+ n tt))))
  ;Paste this command in, but copy the above to clipboard before running:
  arc> (let xs (readall:pbpaste) (map [eval (list '$ _)] butlast.xs) (eval last.xs)
  (each x '(sum0 sum1 sum2 _sum3) (repeat 2 (time:eval `(($ ,x) 10000000)))))

  ;64-bit racket v5.2.0.3: no mallocing beyond initial compilation
  time: 41 cpu: 41 gc: 0 mem: 25720
  time: 40 cpu: 41 gc: 0 mem: 6096
  time: 80 cpu: 80 gc: 0 mem: 7576
  time: 80 cpu: 80 gc: 0 mem: 6136
  time: 81 cpu: 80 gc: 0 mem: 7576
  time: 80 cpu: 80 gc: 0 mem: 6096
  time: 1026 cpu: 1027 gc: 0 mem: 7408
  time: 1018 cpu: 1019 gc: 0 mem: 6112

  ;32-bit racket v5.1.3.10: runtime is dominated by consing bignums
  time: 894 cpu: 892 gc: 24 mem: 1478560
  time: 872 cpu: 872 gc: 16 mem: 1236500
  time: 841 cpu: 841 gc: 15 mem: 1238156
  time: 844 cpu: 843 gc: 17 mem: 1236476
  time: 839 cpu: 839 gc: 15 mem: 1237300
  time: 838 cpu: 837 gc: 15 mem: -15541124
  time: 1857 cpu: 1857 gc: 18 mem: 1237784
  time: 1864 cpu: 1864 gc: 17 mem: 1236436