[HN Gopher] Carp - A statically typed Lisp, without a GC, for re...
___________________________________________________________________
Carp - A statically typed Lisp, without a GC, for real-time
applications
Author : fuzzythinker
Score : 236 points
Date : 2021-10-15 06:49 UTC (16 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| dragontamer wrote:
| So "cons", and the associated "car" and "cdr" functions are
| innately the "thing" that needs to be garbage collected in Lisp-
| like languages.
|
| So I immediately went to the manual, and CTRL+F'd for cons. Carp
| has the following restriction: https://github.com/carp-
| lang/Carp/blob/master/docs/Manual.md
|
| > If you're calling a dynamic function (something defined with
| defndynamic, or a built in command) it will be executed right
| away. This works very much like a classic, dynamically typed Lisp
| interpreter. The dynamic functions are not available in compiled
| code! Their main usage is in macros and to programatically
| control your build settings.
|
| cons, car, and cdr are all "Dynamic" functions that can only run
| _DURING COMPILE TIME_. Which means the GC is not needed during
| runtime: all garbage-collection occurs in the compiler.
| kazinator wrote:
| That's a Lisp preprocessor for a non-Lisp language.
|
| If you program in C using the Common Lisp c-mera preprocessor,
| or any of the other similar systems, it's the same thing.
|
| You're writing everything in S-exps, and the expansions use
| conses, but the output is C; so that of course that cannot call
| cons at run time.
|
| https://github.com/kiselgra/c-mera
| invincivlepvt wrote:
| <a href="https://invincivlepvt.com/" rel="nofollow">Graphic
| Designing</a> <a href="https://invincivlepvt.com/"
| rel="nofollow">Digital Marketing</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Digital
| Marketing Jalandhar</a> <a href="https://invincivlepvt.com/"
| rel="nofollow">Graphic Designing Jalandhar</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Digital
| Marketing Punjab</a> <a href="https://invincivlepvt.com/"
| rel="nofollow">Website Designing Punjab</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Website
| Development Punjab</a> <a href="https://invincivlepvt.com/"
| rel="nofollow">Website Designing Jalandhar</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Website
| Designing Jalandhar</a> <a href="https://invincivlepvt.com/"
| rel="nofollow">Website Development Jalandhar</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Website
| Designing</a> <a href="https://invincivlepvt.com/"
| rel="nofollow">Website Development</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Graphic
| Designing Agency jalandhar</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Graphic
| Designing Company jalandhar</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Digital
| marketing Company jalandhar</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Digital
| marketing Agency jalandhar</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Graphic
| Designing Agency Punjab</a> <a href="https://invincivlepvt.com/"
| rel="nofollow">Graphic Designing Company Punjab</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Website
| Designing company jalandhar</a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Website
| Designing company Punjab</a> <a href="https://invincivlepvt.com/"
| rel="nofollow"> Website Development company Punjab </a> <a
| href="https://invincivlepvt.com/" rel="nofollow">Website
| Development company Jalandhar</a>
| invincivlepvt wrote:
| <a href="https://invincivlepvt.com/website-designing-
| jalandhar-2/">Be... Web Designing Jalandhar</a> <a
| href="https://invincivlepvt.com/website-designing-
| jalandhar-2/">Be... Web Designer Jalandhar</a> <a
| href="https://invincivlepvt.com/website-designing-
| jalandhar-2/">Be... Website Designing Jalandhar</a> <a
| href="https://invincivlepvt.com/website-designing-
| jalandhar-2/">Be... Website Designer Jalandhar</a> <a
| href="https://invincivlepvt.com/website-designing-
| jalandhar-2/">Be... Website Designing </a> <a
| href="https://invincivlepvt.com/website-designing-
| jalandhar-2/">Be... Web Designing </a> <a
| href="https://invincivlepvt.com/website-designing-
| jalandhar-2/">Be... Website Designer </a> <a
| href="https://invincivlepvt.com/website-designing-
| jalandhar-2/">Be... Web Designer </a> <a
| href="https://invincivlepvt.com/website-designing-
| jalandhar-2/">Be... Web Designing agency jalandhar </a> <a
| href="https://invincivlepvt.com/website-designing-
| jalandhar-2/">Be... Website Designing agency jalandhar </a>
|
| <a href="https://invincivlepvt.com/website-development-
| jalandhar/">Be... Web Development Jalandhar</a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">Be... Website Development Jalandhar</a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">Be... Web Development </a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">Be... Website Development </a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">Be... Web Development agency Jalandhar</a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">Be... Website Development agency Jalandhar</a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">Be... Website Developer Jalandhar</a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">Be... Web Developer Jalandhar</a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">Be... Website Developer Punjab</a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">Be... Web Developer Punjab</a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">We... Developer </a> <a
| href="https://invincivlepvt.com/website-development-
| jalandhar/">We... Developer </a>
| kragen wrote:
| Of course the obvious question is "What kind of memory management
| does it use?"
|
| It uses a "linear" (actually affine) type system for memory
| management, with borrowed refs similar to Rust, but evidently
| without tracking mutability: https://github.com/carp-
| lang/Carp/blob/master/docs/Memory.md
|
| The omission of the kind of mutability tracking that eases
| multithreading seems like a significant drawback for its target
| application domain.
| p_l wrote:
| If the target is "real-time systems with low enough latency
| bounds to make GC an issue", the question starts to be "does it
| have predictable pause times" (Rust, afaik, doesn't due to
| backing mechanisms behind some of the lower level aspects of
| memory management and/or use of Rc/Arc, though of course
| someone could get things better there)
| doppioandante wrote:
| Do you mind posting some reference on the unpredictability of
| pause times in rust? I'm interested in real-time systems and
| I'd love to know more.
| p_l wrote:
| This is more specifically about any reference counted
| system, though it also includes unique owner approaches and
| others.
|
| Namely, when you free an object, whether it involves
| manually written code to release anything it holds
| recursively, or through some form of reference counter,
| _you do not know the size of object graph you 're freeing_.
| If you add any custom release logic to the mix
| (destructors, any kind of shutdown logic, etc), you also
| don't know how much extra work unrelated to simple memory
| management will be also involved.
|
| This means that naive manual memory management, or
| reference counting systems, have usually unbounded and
| unpredictable pause times (in addition to various costs
| involved in implementation details, whether it's
| malloc()/free() or refcounting). You do not know if object
| X going out of scope isn't the sole owner of a huge object
| graph.
|
| This is one of (though not only) reason manual memory
| management and refcounting aren't considered good options
| in real-time compared to static allocation of everything
| (object pools, static stack analysis & limits) or RT
| Garbage Collector algorithms, though of course it depends
| on how deep into the rabbit hole you go.
|
| Garbage Collector systems tend to have more control over
| pauses, but _majority_ of algorithms used optimise for
| _throughput_ , not _latency_ or _predictability_. Thus you
| have "huge GC pause" as GC uses fastest space/time
| algorithm and "pays down the debt" for making allocation
| stupidly fast (often single Compare-And-Swap operation,
| sometimes not even that if each thread uses separate
| nursery and can keep local heap-end pointer).
|
| However you can also setup environment towards low latency
| and predictability, probably the most famous example being
| IBM Metronome (available in J9 and recently open sourced),
| which uses a static quanta of time for GC and minor
| variability is the noise of multiple threads of execution
| synchronizing. This works by dividing available time
| between mutator (your "work" code) and collector (GC)
| statically, so that GC will for example always run for 30ms
| then mutator for 70ms then GC for 30ms and so on. Similar
| techniques exist for amortizing pathological performance of
| reference counting by pushing actual deallocation into
| separate collector thread or similarly scheduled slice
| (depends on whether you're fine with possibly unpredictable
| contention between two threads or want more strict timing).
|
| A lot of very hard real time is more about predictability
| in the end.
| rurban wrote:
| An overview of it's deficiencies: https://github.com/carp-
| lang/Carp/issues/1317
| fuzzythinker wrote:
| Anyone who had used or tried Carp and Janet (that was on
| frontpage the other day)?
|
| What are some strong points on Carp vs. Janet?
| pgt wrote:
| Janet is dynamic with a garbage collector.
|
| Carp is a GC-less static Lisp with deterministic memory
| allocation via a Rust-like borrow checker.
|
| I only wish Carp had stayed nearer Clojure's syntax. A more
| familiar syntax would make it more accessible.
| rcarmo wrote:
| I've been reading through the examples and it's readable
| enough. What is it that you find odd?
| kbd wrote:
| As someone who doesn't know any lisp well, it's odd to hear
| you highlighting significant differences in syntax between
| them. I thought the character of a lisp is that it doesn't
| have much syntax. I'd be interested in an example.
| pjmlp wrote:
| Clojure adds [], {} and #{} as additional syntax for
| arrays, hashmaps and sets.
| lf-non wrote:
| I have not used carp, and janet only briefly. However, other
| than both using lisp syntax, there are very little similarities
| between the two.
|
| Janet has a garbage collector, no static types, no ownership
| tracking - the perf. is similar to lua, so is not be ideal for
| low-level/realtime systems, which carp is targeting.
| shakna wrote:
| > the perf. is similar to lua, so is not be ideal for low-
| level/realtime systems
|
| Lua runs on a bunch of low level systems, and not just for
| hobbyists (it's at the core of VxWorks, for example). Can you
| expand on why you think the language doesn't meet your
| performance criteria?
| m12k wrote:
| I think generally Lua is considered a scripting language -
| it is suited for gluing together performance critical
| components built in faster languages like C, C++ or Rust -
| the kinds of GC-less languages you can make a VM, game
| engine or OS in. So Carp is intended to join that list of
| fast GC-less languages that you make the fast foundation
| that others then call from scripts using languages like
| Lua.
| saikyun wrote:
| I think this is LuaJIT, or? Iiuc Janet is comparable to
| non-JITed Lua. But I actually have no clue.
| lf-non wrote:
| Not familiar with VxWorks, but I have mostly seen lua being
| used as a plugin/extension language around a core
| implemented in native code.
| fuzzythinker wrote:
| Thank you and @pgt. I thought Janet compiles to C or native
| bytecode due to its strong interop with C.
| saikyun wrote:
| Last time I checked, Carp doesn't have a REPL that can interact
| with a running process. In Janet you can do things like change
| functions during runtime.
| kortex wrote:
| What's the difference between `let` and `the`? Skimmed the
| language guide and docs but it wasn't clear. `the` seems to be
| the typical type inference variable declaration.
|
| I'm not really familiar with lisps so this might be a
| documentation oversight.
|
| Looks really neat overall.
| timdeve wrote:
| `let` is for declaring variables while `the` is a noop at
| runtime and only give type information to the compiler.
| TheDesolate0 wrote:
| FFS!
|
| No more fucking LISP!
| DeathArrow wrote:
| What's the difference between it and Common Lisp? Isn't Common
| Lisp also AOT compiled?
| baq wrote:
| AOT doesn't necessarily mean GC-less, right?
| brabel wrote:
| Maybe they actually mean VM-less, which would probably imply
| GC-less because if you have a GC, you pretty much have a VM
| doing the GC (unless it's simple ref-count). For embedded,
| you need VM-less, I think, as VMs tend to be too heavy.
| white-flame wrote:
| VMs imply a non-native bytecode execution. Garbage
| collection doesn't require any of that.
|
| It's just normal library code usually called by the
| allocator, and well-specified memory object/pointer
| layouts.
| bitwize wrote:
| Gambit has a VM and a GC, and is still AOT-compiled to C.
| (The Gambit VM is an intermediate representation of Scheme
| code which is then compiled down to C code.)
| jdc wrote:
| First of all, Common Lisp is a language with several
| implementations, some of which offer AOT compilation. Secondly,
| a garbage-collection (aka automatic memory management) does not
| exclude AOT.
| jdc wrote:
| See also the Boehm GC, a garbage collector for C and C++.
|
| https://en.wikipedia.org/wiki/Boehm_garbage_collector
| soegaard wrote:
| For the history buffs: Pre-Scheme: A Scheme
| Dialect for Systems Programming Richard A. Kelsey, 1997
|
| Abstract
|
| Pre-Scheme is a statically typed dialect of Scheme that gives the
| programmer the eciency and low-level machine access of C while
| retaining many of the desirable features of Scheme. The PreScheme
| compiler makes use of type inference, partial evaluation and
| Scheme and Lisp compiler technology to compile the problematic
| features of Scheme, such as closures, into C code without signi
| cant run-time overhead. Use of such features in Pre-Scheme
| programs is restricted to those cases that can be compiled into
| ecient code. Type reconstruction is done using a modi ed
| Hindley/Milner algorithm that allows overloaded user-de ned
| functions. All top-level forms in Pre-Scheme programs are
| evaluated at compile time, which gives the user additional
| control over the compiler's partial evaluation of a program. Pre-
| Scheme has been implemented and used to write a byte-code
| interpeter and associated support code for a complete Scheme
| implementation.
|
| https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.3....
| stan_rogers wrote:
| The letter combination "fi" seems to have been deleted
| throughout your quote, there. Perhaps it was a ligature in the
| original.
| HPsquared wrote:
| I was thinking it lacks a foreign function interface (FFI)
| a0-prw wrote:
| I just thought it was so effficient, it left out the effs
| ;)
| soegaard wrote:
| I believe it has one today.
| soegaard wrote:
| Sorry about that!
|
| I copied the Abstract from the pdf. I believe everything
| looked correct in the input form where I submitted the text.
| guerrilla wrote:
| > (the Int x)
|
| I like the cute syntax for type annotations.
| aidenn0 wrote:
| I had to double-take because CL also has a THE also for
| declaring types, but it's a bit different; THE declares the
| type of an expression, not a variable (there is a separate type
| declaration for variables).
|
| so e.g. (the fixnum (+ x 1)) would assert that (+ x 1) produces
| a fixnum.
| timdeve wrote:
| That is also the case in Carp, x being an expression here.
| aidenn0 wrote:
| Ah, okay. So is there a way to declare that a variable will
| always be of a given type in Carp?
| timdeve wrote:
| Carp is statically-typed with type inference so writing
| (the Int x) would be enough for the compiler to forbid
| any usage of x as another type. Writing (Int.+ x 1) would
| accomplish the same as Int.+ only accepts Int.
|
| You can also annotate function with a type signature.
| (sig add (Fn [Int Int] Int)) (defn add [x y] (+ x
| y))
|
| Is the same as: (defn add [x y] (the Int
| (+ (the Int x) (the Int y))))
| xvilka wrote:
| There is also interesting CL implementation that is based on the
| LLVM framework - Clasp[1]. It can be natively compiled and
| designed for performance.
|
| [1] https://github.com/clasp-developers/clasp
| aidenn0 wrote:
| Last I checked SBCL and CCL (both open source native compiled
| CL implementations) are quite a bit faster than Clasp.
|
| However, if you are primarily e.g. calling computational
| chemistry libraries written in C++, Clasp is the way to go.
| It's the only non-C++ language implementation I know of with
| actually usable C++ support.
| pjmlp wrote:
| C++/CLI comes to mind, as means to merge .NET and C++ worlds
| together.
| aidenn0 wrote:
| Oh gosh, I forgot about that. Is that Windows only though?
| I remember MSVC had managed/unmanaged C++ and allowed
| calling between the two.
| pjmlp wrote:
| Sadly yes.
|
| And although they don't have much love for it, they still
| keep it relatively up to date.
|
| It was one of the .NET Core 3.1 main milestones.
|
| However I would say for the purpose of binding .NET and
| C++, probably it doesn't need to understand everything
| anyway.
| simiones wrote:
| CLASP is a really interesting project.
|
| For one, it's created and written by a Chemistry PhD researcher
| (Christian Schafmeister), not someone with a traditional CS
| background.
|
| For another, it's one of the few languages that has ever
| attempted to interface with C++ at the template level - you can
| instantiate C++ template classes from CL, and catch C++
| exceptions etc.
|
| For yet another, he does compacting garbage collection for the
| C++ objects used in the CL implementation, with pointer
| patching and everything else.
|
| There's a nice Google Tech Talk about it [0], that goes into
| both why he did this, and how he implemented this.
|
| [0] https://www.youtube.com/watch?v=8X69_42Mj-g
| pjmlp wrote:
| I guess it helps that it is pretty much a Lisp for the
| research work that they are doing, instead of trying to cater
| to everyone.
| gavinray wrote:
| Dr Schafmeister is occasionally present on the LLVM Discord.
| The CLASP project is something else. That hour-long talk he
| gives on Youtube about it blew my mind.
| NoGravitas wrote:
| This seems like fun. I could never get into Rust because of the
| syntax (there's so _much_ of it), but this seems doable. I don 't
| _need_ it for anything, though; I don 't do anything where SBCL
| isn't plenty fast enough.
| billpg wrote:
| I was thinking of building my own LISP-like language, but seeing
| so many pop up on here I don't think I'll bother.
| fsloth wrote:
| As stated by others, it's a very enjoyable exercise. Think
| about it like Marathon for programmers. Yes, lot's of people
| run marathons. But people usually don't go "Maybe I should run
| a marathon - but so many others are doing it. Meh, maybe not."
| tonyg wrote:
| Try building a Smalltalk-like language. It throws a different
| set of concerns into relief, and besides, it's a better design.
| pjmlp wrote:
| Millions of CS students build their own language for compiler
| classes every year.
|
| As learning exercise of everything that goes into making a
| compiler/interpreter is very worthwhile endevour.
|
| As means to make the next big thing, maybe not.
| brabel wrote:
| > Millions of CS students...
|
| Are there millions of CS students in the world?? I would
| guess a few hundred thousand, at most.
| [deleted]
| kortex wrote:
| Probably. There's 20-30ish million software developers in
| the world [1]. People work for 30-50 years, suggesting at
| least a million freshman CS students a year. It's a rapidly
| growing field. Plus all the lifetime learners. It's not
| unreasonable to estimate at least 2M CS students worldwide
| write or work on a compiler each year. Maybe a tad high,
| but also it's an idiom.
|
| https://www.daxx.com/blog/development-trends/number-
| software...
| robertlagrant wrote:
| I have no actual opinion here. Just stopping by to point
| out that not (nearly) all software developers started as
| CS students.
| pjmlp wrote:
| Might be, I don't have the numbers.
|
| > A figure of speech is a deviation from the ordinary use
| of words in order to increase their effectiveness.
| Basically, it is a figurative language that may consist of
| a single word or phrase. It may be a simile, a metaphor or
| personification to convey the meaning other than the
| literal meaning.
|
| https://en.wikipedia.org/wiki/Figure_of_speech
| jstx1 wrote:
| You probably should anyway - most of it is for learning and
| personal satisfaction. It's not like any of these projects are
| competing for actual marketshare in the programming language
| landscape.
| mlang23 wrote:
| The name is strange. Reminds me of a product-naming story I heard
| years ago. Papenmeier from Germany was once planning to create a
| small notetaker with built-in braille display. They originally
| planned to name it "Braille Assistant", but the US distributors
| objected on the ground that they can already see users shortening
| the product name to "Braille Ass". I have a similar feeling with
| Carp, isn't the obvious transposition an issue? :-)
| rcarmo wrote:
| Given the kind of niche, self-deprecating humor often found in
| our ecosystem, it was probably seen as a plus :)
| kortex wrote:
| It'll be good company with git, GIMP, LISP, ploopy.co, etc.
| 1500100900 wrote:
| Doesn't seem to happen to the Common Address Redundancy
| Protocol too much.
| rcarmo wrote:
| Spent my lunch break investigating this a bit and it is quite
| nice, with the only caveat (for my use case) being that
| networking is handled by a third-party socket library that, alas,
| does not handle multicast sockets (don't ask...).
|
| Otherwise, examples are interesting, and certainly seem to cover
| most gamedev scenarios (haven't found any audio or MIDI ones
| yet).
| romesmoke wrote:
| Was it always the case that, on a weekly basis (if not more
| often), new languages would sprout? It seems to me like
| considerable amounts of energy are invested on re-inventing-the-
| wheel instead of solving real problems with existing tools.
| bjoli wrote:
| The creator was interveiwed in the podcast "Functional geekery":
| https://www.functionalgeekery.com/episode-96-erik-svedang/
| savant_penguin wrote:
| I wonder if this deterministic memory management instead of a
| garbage collection would have helped discord with their spiking
| latencies
|
| https://blog.discord.com/why-discord-is-switching-from-go-to...
| hcarvalhoalves wrote:
| This is interesting, but I believe a big point of LISP is
| actually having a live system that can be introspected, and GC is
| part of making that work. In the end isn't this just <insert sys
| prog language> but with s-expressions?
| TeMPOraL wrote:
| S-expressions also enable proper macros, as long as it has
| them, it's already ahead of <insert sys prog language>.
| hcarvalhoalves wrote:
| I guess so, I think my point is: are s-expression enough to
| qualify as a LISP?
| TeMPOraL wrote:
| Depends who you ask, really. For me, s-expressions and
| macros are enough, though it would feel _very weird_
| without a REPL and image-based development.
| protomikron wrote:
| Can somebody please explain or give me some links how FP is
| supposed to work _without_ a GC? For example Rust has different
| types of function pointers (Fn, FnMut, FnOnce), to guarantee the
| possibility of lifetime analysis (so it is arguable to consider
| it a functional programming language). On the other hand the most
| common FP languages (OCaml, Haskell) all come with a GC.
|
| Or am I wrong in assuming this is a functional language?
| astrange wrote:
| As long as you forbid or mark cycles (...or ignore the problem)
| lifetime analysis can be done statically. Which is better
| anyway. Automatic memory management doesn't need a GC.
| silon42 wrote:
| It's really surprising that it's rare in functional
| languages. Immutability seems like it should guarantee no
| cycles (?), so reference counting could be used.
| kragen wrote:
| Reference counting is usually very expensive, because even
| reading a variable updates the reference count, and ending
| a scope involves testing the reference count of every
| variable defined inside the scope and conditionally
| deallocating the referent.
|
| Without reference counting, here's the end of a hairy
| function scope that deallocates 15 local variables and
| restores two callee-saved registers:
| 11a6: 48 83 c4 78 add $0x78,%rsp
| 11aa: 5b pop %rbx
| 11ab: 41 5e pop %r14
| 11ad: c3 retq
|
| Now imagine looping over 15 local variables to decrement
| each reference count, test it, and do a conditional jump
| based on the result; if that's open-coded, your epilogue is
| humongous, and if it's in a reference-count-decrementing
| subroutine, it's going to have mispredicted branches all
| over the place, costing you maybe 15 cycles each, a total
| of about 100 cycles for this function. We're talking about
| adding an order of magnitude of cost to subroutine call, or
| more. (I think this function doesn't really need 15 local
| variables; that's the compiler's fault.)
|
| This gets worse with multithreading, because writing to the
| same reference count on different cores would even in the
| best case require one core stealing the cache line from
| another in order to modify it, which may stall the core;
| but often even an atomic reference count increment is more
| expensive even than that because it involves a memory
| barrier.
|
| Reference counting can become reasonably cheap if it's done
| at large granularity (filesystem files or COM objects, not
| conses); if you can elide almost all of the reference-count
| updates, as in Rust; or if your language runtime is just so
| dog-slow at everything that the extra cost of reference
| counting isn't that important, like CPython.
|
| 30 years ago or more, before generational GC had gone
| mainstream, reference counting was a more reasonable
| choice, because GC was going to be very slow in any case,
| and ref counting at least used less memory--especially
| important on machines without cache or virtual memory.
|
| ( _Purely_ immutable (applicative) languages like Haskell
| and Miranda are usually lazy, since that 's the payoff for
| completely abjuring side effects. But lazy evaluation is
| implemented at the machine level by mutation.)
| naasking wrote:
| > Reference counting is usually very expensive, because
| even reading a variable updates the reference count
|
| There are many papers out there on how to elide most ref
| count operations on locals, and runtimes that use ref
| counting for automatic memory management typically defer
| ref count updates in various clever ways (like Nim IIRC).
| You give up some latency for significant throughput
| gains.
| kragen wrote:
| Aye.
| wyager wrote:
| There are two ways to get cycles in Haskell.
|
| One is through "tying the knot". E.g. to create an infinite
| list of 1,1,1,1,1,...
|
| ones = 1 : ones
|
| This will actually be compiled to a list cell with a
| pointer back to itself. You can construct more complicated
| self-referential data structures thanks to laziness.
|
| The other way you could get a cycle is that it actually
| does have mutable data structures, although their use is
| restricted so they can't have any observable mutable effect
| in pure code. But you have e.g. IORef which is basically a
| mutable pointer.
|
| If you wanted no cycles you would need to eliminate some
| subset of laziness, knot-tying transformations, recursion,
| and any support for mutable data structures. But yes, I
| think it could be done.
| jbjohns wrote:
| Why would immutability guarantee no cycles? Here is a line
| of valid haskell: star e = let (sp,
| a) = (Split a e, atom sp) in sp
|
| EDIT: I guess I should probably explain it: star is a
| function that takes an expression "e" and returns the value
| "sp" which is "Split a e" where "a" is the results of
| calling the "atom" function on "sp". This is creating a
| representation of a regex star operator. Note that the
| tuple defined in the let definition is only to define a
| name for the two values of the tuple so that they can refer
| to each other.
| JoelMcCracken wrote:
| I mean generally tying the knot is a useful technique,
| but I think these scenarios all require/exploit non-
| strict, which is in itself not really immutable in the
| sense most people use it.
|
| But yes, such code is often useful so that e.g. a parent
| xml node can refer to its childen nodes while also
| children nodes can refer to their parents.
|
| Anyway, I'm not sure about this, but I _think_ you can 't
| have circular data structures in the context of strict
| evaluation (or can you? maybe by defering execution via
| anonymous functions? I wonder....)
| dwohnitmok wrote:
| The big thorn is closures, which show up all over the place
| in FP. You either need to limit closures vs ordinary
| functions (as e.g. Rust does), have manual memory
| annotations (such as e.g. what Swift does) or you basically
| need a GC. The former two choices are annoying if you
| really take advantage of functions as first-class citizens.
| vnorilo wrote:
| Lisp is not necessarily functional. There's a lot of mutation
| in Common Lisp even if the community favors a functional style.
|
| I think the question is: how does Lisp function without garbage
| collecting cons cells?
|
| For one, I'm not sure they even rely on cons cells like "real"
| Lisp. Clojure doesn't either. They cite ML as inspiration.
|
| Carp language guide states object lifetimes are statically
| inferred [1] which my guess is they allocate on stack (or
| malloc/free by scope) and detect use-after-free at compile
| time.
|
| Another, more theoretical approach is using linear types which
| require all values to be "consumed" [2]
|
| 1: https://github.com/carp-
| lang/Carp/blob/master/docs/LanguageG...
|
| 2: https://www.cs.utexas.edu/users/hunt/research/hash-
| cons/hash...
| protomikron wrote:
| Thanks for the links. There's also this Reddit discussion [0]
| from 2 years ago (it mentions Carp btw.) and an explanation
| about how Carp manages memory [1].
|
| [0] https://www.reddit.com/r/haskell/comments/d5d13i/is_it_po
| ssi...
|
| [1] https://github.com/carp-
| lang/Carp/blob/master/docs/Memory.md
| alexisread wrote:
| In particular, the reddit discussion mentions ASAP, which
| is a set of static analysis algorithms that can work with
| mutability, generics (polymorphism) and linear types.
| http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-908.pdf
|
| As far as I'm aware, this really only applies to single
| threaded systems. However, if you implement threadsafe
| modules and keep the shared stuff internal (use the ASAP
| algos here), you can fit the majority of use-cases
| including hard-realtime constraints.
|
| Composita is the module system I'm referring to.
| http://www.composita.net/Composita.html It allows
| concurrency with managed memory and no GC, through static
| analysis of the module (component) interface queues.
| timdeve wrote:
| You're correct, somewhat like clojure's Vector, the default
| collection at runtime in Carp is an Array which is heap
| allocated C array with an attached length. At compile time
| however the dynamic language uses more standard lispy lists.
| timonoko wrote:
| Me knows:
|
| "TN-tools in Nokia were automatically compiled into C-code to
| be run in VAX-computers. Compiled C-code did not have garbage
| collector, there was separate reclaim-command for discarding
| used data. If you managed to run your program without ever
| hearing the BEEP caused by garbage collector, your program was
| ready for VAXing."
|
| https://timonoko.github.io/Nokolisp.htm
| cmrdporcupine wrote:
| From the Carp docs:
|
| _Memory management is handled by static analysis, a value is
| owned by the function where it was created. When a value is
| returned or passed to another function the initial function
| will give up ownership of it and any subsequent use will lead
| to a compiler error. To temporarily lend a value to another
| function (for example to print it) a reference must be created,
| using the ref special form (or the & reader macro)._
|
| and
|
| _achieved through a linear type system where memory is owned
| by the function or let-scope that allocated it. When the scope
| is exited the memory is deleted, unless it was returned to its
| outer scope or handed off to another function (passed as an
| argument)._
| andi999 wrote:
| So how is memory fragmentation avoided?
| pjc50 wrote:
| That's a question for the underlying allocator, surely?
|
| (Quite often the answer is "it isn't")
| andi999 wrote:
| Not just for the allocator. I always thought a main point
| of a garbage collector was heap compactification
| (shuffling things around so there is more space), but
| maybe I am wrong.
| mumblemumble wrote:
| In general, most lisps are imperative, or support multiple
| paradigms including imperative.
|
| First-class functions are a necessary feature of FP, but the
| mere presence of the feature does not make a language
| functional. Some counterexamples include Fortran and Smalltalk.
|
| It's an easy misconception because most the well-known newer
| entries to the lisp family - Scheme, Racket, and Clojure - are
| all mostly functional, and because most of the major non-
| functional dialects of lisp died out 30 or 40 years ago.
| mlang23 wrote:
| Lisp is definitely not as functional as for instance Haskell
| is. Side-effect-freeness was never really a topic for Lispers.
| medo-bear wrote:
| You are right, Lisp is far more versatile. There is even a
| statically-typed language Coalton [1] embedded into Lisp.
|
| [1] https://coalton-lang.github.io/20211010-introducing-
| coalton/
| RobertKerans wrote:
| & Rust is surely a _highly_ imperative language that has
| absorbed functional idioms (where appropriate), rather than
| something that falls under the banner of "functional
| language"?
| amelius wrote:
| There's a reason why functional languages all use a GC. And
| that reason makes Rust not such a good language for
| functional idioms unless you stay within very strict lines.
| pharmakom wrote:
| use value semantics for everything is one way
| ducktective wrote:
| "Real-time" has a specific meaning in embedded and computing
| context. Does it mean that programs written in Carp have any
| guarantee on their order or duration of execution?
| wahern wrote:
| Unless it has a scheduler for a concurrency or threading
| framework, what other characteristics beyond memory management
| would be relevant? I guess maybe certain types of built-in data
| structures--you'd probably want a map/dictionary based on red-
| black or AVL trees rather than a hash table.
| xxs wrote:
| Any shared datastructure needs some kind of forward
| gurantess; e.g. being lock-free might not be sufficient.
| KMag wrote:
| ... or a hash table using RB/AVL trees rather than linked
| lists for hash buckets.
| xxs wrote:
| the doubling of the sizes is an issue. Yet, I'd consider
| all single threaded datastructures a non-issue. The hard
| part is multithreading.
|
| Flip note: java's hashmap uses red/black tree for nodes
| when there are too many collisions (and the keys are
| Comparable)
| hawk_ wrote:
| but java's hashmap still resizes when breaching the
| loadfactor. so any similar implementation, even for
| singlethreaded cases can't achieve (soft)realtime. I am
| not aware of any linear hashing or similar approach for
| in memory hash tables to mitigate such latency spikes.
| xxs wrote:
| of course it does; it's possible to pre-allocate the
| entire table though (c-tor with size, rounded to the next
| power of 2, compensated by the load factor). Massive
| waste of memory but no resizes.
| xxs wrote:
| For "real-time", they would need a real-tune OS, datastructures
| with forward guarantees, non-blocking IO and so on. GC is like
| the least of the problems.
| jstimpfle wrote:
| Not an expert at all here, just a few thoughts and
| experiences.
|
| I think "forward guarantees" (meaning "lock-free"?) can be
| implemented anywhere. Non-blocking IO can still be slow in my
| experience, for example a write() syscall on Linux to a non-
| blocking TCP socket on Linux sometimes took dozens of
| milliseconds when I measured. I don't have enough experience
| to know if one can get better timing guarantees with tuning
| or newer kernels, but maybe it's not a huge issue in all
| cases.
|
| After all, the OS is only at the outside layers of an
| application, so one might be able to process the OS I/O in
| separate threads and allocate sufficiently large buffers
| there.
|
| GC however, in typical usage means that random internal
| codepaths could be interrupted by the GC doing OS interaction
| in places where it's really not affordable.
| xxs wrote:
| lock free does not guarantee all participants have a fair
| treatment, e.g. one thread can keep losing the CAS
| (CompareAndSwap / LoadLinked/StoreConditional / etc.) and
| effectively spinning or need to yield. releasing the CPU
| resources.
|
| A non-blocking write should just copy the data to the
| socket buffer, definitely not taking milliseconds.
|
| Allocate buffers in separate threads - ok, that's the crux
| of it - the memory is shared amongst the threads within a
| process, so the allocator has to be non-blocking as well or
| the large allocation would prevent allocations in other
| threads. Next release memory to the OS (or unmapping memory
| mapped files) - mumnmap requires TLB flush for all cores
| assigned to the process. There is a lot that can 'block'
| sometimes and void the "real-time" properties.
|
| > interrupted by the GC doing OS interaction
|
| Normally GCs trigger only at 'safe points' and unless they
| need to allocate more memory (should never be the case for
| a real-time application), GCs should have no OS
| interaction. Copying and moving memory within a process is
| no OS functionality. Concurrent GC with read-barrier exist
| as well, so no need for stop-the-world pauses. (Edit:
| creative use of memory mapping hardware to avoid copying
| may need OS calls)
|
| It seems quite common to see on hacker news - "No GC
| <language> for real-time". Writing a good/multi-threaded
| real-time application is a lot harder than just GC's
| dreaded stop-the-world.
| jstimpfle wrote:
| > A non-blocking write should just copy the data to the
| socket buffer, definitely not taking milliseconds.
|
| That's the theory, right? It could be I measured
| something wrong, but sometimes dozens of ms is what I
| got, and I concluded that non-blocking I/O avoids
| _indeterminate_ blocking (such as reading from a TCP
| socket until the sender sent N bytes) but does it
| completely avoid taking in-kernel locks etc? Probably
| not.
|
| I didn't find any other measurements on the internet,
| please point me to them if you find them.
|
| Thinking back again, another explanation could be false
| sharing effects that I didn't know well at the time.
|
| > Allocate buffers in separate threads - ok, that's the
| crux of it - the memory is shared amongst the threads
| within a process, so the allocator has to be non-blocking
| as well or the large allocation would prevent allocations
| in other threads.
|
| I've written a SRSW lock-free ringbuffer for example. The
| ringbuffer memory is allocated at startup. The cost to
| allocate from this ringbuffer is very little. It's
| probably not super important, but the ringbuffer even
| caches the read or write pointer from the other thread,
| so it only needs a cache line transfer when the cached
| value is not sufficient to accomodate the read or write.
|
| This is way outside my experience, but I think it should
| be possible to do some similar stuff with multiple
| readers and/or writers? I think you should still be able
| to allocate from a ringbuffer without live-locking
| (unless the buffer is full of course, in which case
| events are dropped anyway).
|
| > Next release memory to the OS (or unmapping memory
| mapped files) - mumnmap requires TLB flush for all cores
| assigned to the process.
|
| I think most programs do only "static" allocation at
| program startup. There's no OS interaction for memory
| management from then on.
|
| > Normally GCs trigger only at 'safe points' and unless
| they need to allocate more memory (should never be the
| case for a real-time application), GCs should have no OS
| interaction.
|
| Ok, if the GC is configured to never return memory to the
| OS, it makes sense that probably the GC in an event
| handling system won't need to get more memory from the
| OS, or only rarely, once it is "warm".
|
| Still, GCs are generic systems that have to be less
| efficient than specialized systems. And what are 'safe
| points'? I'd rather decide myself. I think a GC trace of
| <1ms, as some new GC allegedly do (is this widely
| acknowledged? I would assume it depends a lot on the
| allocation patterns / granularity etc), could be enough,
| but I'd rather control this myself (for the somewhat
| real-time app that I've been working on, I need << 10ms
| latency).
| tzs wrote:
| > It could be I measured something wrong, but sometimes
| dozens of ms is what I got, and I concluded that non-
| blocking I/O avoids indeterminate blocking (such as
| reading from a TCP socket until the sender sent N bytes)
| but does it completely avoid taking in-kernel locks etc?
|
| Perhaps what you were seeing were occasions where the
| system decided during your system call that your
| processes' time slice had expired or some I/O that some
| higher priority process was waiting for completed and it
| gave the CPU to some other process?
|
| When timing things on preemptive multitasking systems it
| is often best to make a lot of measurements and then look
| for clusters. The time of the smallest cluster should be
| the time the operation itself takes.
| jstimpfle wrote:
| Preemption can happen even outside of system calls of
| course, but I guess my takeaway has been to just avoid
| calling into the system where a lot of things can happen
| that I don't really understand or control. That, plus
| setting my threads to high-priority and possibly pinning
| them to the right cores.
| xxs wrote:
| >That, plus setting my threads to high-priority and
| possibly pinning them to the right cores.
|
| What language was that - [normally] Java does not respect
| priorities at all for instance. Running with higher
| priority may require root as well.
| jstimpfle wrote:
| Language was C, running as root on some Linux 3.x on some
| ARM/FPGA development board. By setting threads to high-
| priority I mean something like pthread_setschedparams(...
| SCHED_FIFO ...).
| xxs wrote:
| >I didn't find any other measurements on the internet,
| please point me to them if you find them.
|
| It has been years since I have written thousands sockets
| servers (used in forex), yet even a couple milliseconds
| per write would have made the entire operation useless.
|
| >another explanation could be false sharing effects that
| I didn't know well at the time.
|
| False sharing sucks, of course, but milliseconds seems
| way way too much again penalty. You'd need all cores
| updating the same cache line, even then I doubt it'd be
| that bad.
|
| Could it be the virtualization layer? (again I have run
| 'that' on bare metal only)
|
| >I think it should be possible to do some similar stuff
| with multiple readers and/or writers
|
| Multiple writes should be avoided entirely, contention on
| writing is what prevents scaling - false sharing is
| pretty much that. A writer honoring the readers is pretty
| simple - each reader has its own pointer and the write
| should fail (or spin) when the buffer is full. I think
| that's quite a classic structure and indeed - it requires
| no extra memory to communicate/hand-off.
|
| About latency - this is java's current GC that does still
| has a compaction phase. https://malloc.se/blog/zgc-jdk16
| pjmlp wrote:
| Correction, one of Hotspot's GC implementations, there
| are plenty of Java implementations to chose from.
|
| Including ones with soft real time GC for performance
| critical deployments like PTC and Aicas.
|
| https://www.ptc.com/en/products/developer-tools/perc
|
| https://www.aicas.com/wp/products-services/jamaicavm
|
| Anyone picking a traditional JVM for such workloads is
| doing it wrong.
| xxs wrote:
| What I meant is that low latency GC is sort of a
| commodity/mainstream now. Not advising to use java or a
| specific JIT+Collector.
| pjmlp wrote:
| Ah, fair enough, got it wrong.
___________________________________________________________________
(page generated 2021-10-15 23:03 UTC)