text:
# Automatic memory management: hybrid reference counting

Posted on March 1, 2014 by Tommy McGuire
Labels: rust, programming language

When last we left, I had demonstrated that one form of garbage collection, reference counting, had a significant problem: it could not collect cycles of objects. If two objects point at each other, each will always have a reference count greater than zero even if nothing else points to them.

Various smart people created various fixes for the cycle problem. One persistent suggestion is to use weak pointers, pointers which do not increase the destination's reference count but which must be checked before they can be followed because the destination may no longer exist. Weak pointers work well if the structure being built includes designated, special references like back pointers in a doubly-linked list or parent pointers in a tree. On the other hand, in a general graph structure weak pointers seem less useful. One algorithm, mentioned in Garbage Collection by Jones and Lins attempts to automatically break cycles using weak pointers. They also mention that it does not actually work.

A better option is a cycle detector: a separate subsystem that scans objects that appear to be live, checking them for real, external pointers. Typically, cycle detectors work by removing the counts for the internal links in a graph of objects, leaving only valid external links. Python has a fine example of a cycle detector. (Which link I found via a Stack Overflow answer; some old documentation still seems to be relevant.) The Python documentation describes both the Python and lower-level C interfaces of its cycle detector. By the way, if you take a look at any of those links, pay attention to the handling of objects with __del__ methods. But more on that later.

A slightly different cycle collector is described in Garbage Collection, specifically one by Rafael Lins himself.

## Lins' cycle collector

Lins' algorithm hooks into the normal reference counting mechanism when an object's reference count is decremented. If the count becomes zero, the object is indeed garbage and can be deleted. If the reference count is non-zero, however, the object is acting sketchy. It is not behaving normally. It is standing out. And you know what happens to nails that stick out.

Anyway, when an object's count is reduced but remains above zero, it is inserted into a control set maintained by the collector. It is also marked with a special color, purple.

Coloring is a frequent technique in collection algorithms. In Garbage Collection, the typical colors used are black, grey, and white, but the colors indicate different things for different algorithms; in the case of Lins' algorithm, black indicates an object is known to be in use, grey indicates an object that may be garbage, and white indicates that an object is known to be garbage. Purple means sketchy.

Cycle detection works in three phases, for each object found in the control set that is still purple (objects can be recolored black by being used by the mutator):

1. The object is marked grey, and all of its children recursively have their counts decremented and are marked grey. This step subtracts the effects of all of the pointers between objects in the sub-graph consisting of this object and its children---any reference count greater than zero must represent a pointer from outside this group of objects. Note that no deletion happens now. The objects may still be alive and if so, will have their reference counts restored.
2. Starting from the same element of the control set, the algorithm scans grey objects, testing their current reference count. If the count is greater than zero, the object has an external pointer. The object and its children are recolored black and their reference counts restored. If the count is equal to zero, the object is colored white.
3. Again starting from the element of the control set, white elements are deleted.

The third step as presented in Garbage Collection has issues. The algorithm there is:

collect_white(S) =  if colour(S) == white    for T in Children(S)      collect_white(*T)    free(S)

The two problems are, first, if the structure is indeed cyclic then this algorithm will recur infinitely, and second, a deleted object may be visited by a later stage of collect_white. Many memory management systems would not find the latter to be incorrect since freeing an object still leaves its storage under the care of the manager, but it does become a problem when an underlying allocator such as malloc is used. Weirdly, the former does not seem to be present in Lins' original paper.

There are some preliminary complications that need to be handled before we can look at this collector in Rust.

## Type management and allocations

Back in the last post, the Rc and Box types were parameterized by the type T, the type of the user data. Doing so has a number of advantages: it is always completely type safe since the type is tracked from the creation of the Boxes and Rc's, through borrowing the object, to the deletion step. Further, deletion is simplified because a Box<T> can be allocated as an owned pointer, converted to an unsafe pointer for most of its life, and returned to an owned pointer to be deleted, correctly handling any deletion process for T.

Unfortunately, the collector I am working on here will be looking at objects of many different types. To see why a collector cannot deal with only a single type, consider what happens when a type T contains a reference to a type U, which in turn contains a reference to T: we are back in the realm of uncollectable garbage. Fortunately, Rust provides some assistance for us. (What the heck, it has to track this stuff.)

The key I am using is the TyDesc pointer, a pointer to a type descriptor provided by the std::unstable::intrinsics module. (Does that make you nervous? It should. I'm using Rust 0.9; this is probably all changed in the head of master. Fortunately, intrinsics seems to have been reasonably stable since 0.7 and the facilities have been present and used by the arena module since 0.5.)

TyDesc (I'm not going to bold every instance of Rust code anymore; when I last fiddled with the Maniagnosis fonts, all the boldy things became annoyingly busy.) is a structure containing a number of useful things including the size and alignment requirements for the type being described and the type's drop_glue, a function to be called to invoke the type's destructor (which may be explicit as in an instance of the Drop trait, or not as in the case of a type containing an owned pointer to a vector or something.

Rust makes extensive use of the Resource Allocation Is Initialization (RAII) technique, particularly for memory management in its standard library. That is the whole "owned pointer" thing. And no, Rust's types are not parameterized with an allocator like C++'s standard templates. (And I hope they never will be; that is insane.) As a result, drop_glue is very important. The alternative for a memory management system like this would likely be to provide separate implementations of a great deal of the standard library. Rust's original @ sigil, the associated "garbage collector," managed strings, and the at_vec module are all an example of the result. Rust isn't Haskell; multiple implementations of the standard prelude in the standard library are not really appreciated. Consistent, if not deterministic, handling of destructors must be a requirement for a memory management system in Rust.

To start, Box will no longer be parameterized (explicitly, anyway) by the user's type T. Instead, it will contain the reference count, a color, and a pointer to T's type descriptor.

#[deriving(Eq,ToStr)]enum Color { Black, Grey, White, Purple, }struct Box {    color  : Color,    count  : uint,    tydesc : *TyDesc,}

The Box and its object will be allocated in a single call to malloc, leaving the object immediately following the Box header. Because of the object's alignment requirements, there may need to be some padding between the Box and the object itself; the size of the Box and this padding along with the location of the object can be calculated using the size of the Box and the type descriptor.

fn padded(size : uint, align : uint) -> uint { (size + align - 1) & !(align - 1) }fn box_offset(t : *TyDesc) -> uint { unsafe { padded( intrinsics::size_of::<Box>(), (*t).align ) } }

Allocating and initializing the Box and object is...interesting. Welcome to systems programming!

impl Box {    unsafe fn unsafe_new(t : T) -> *mut Box {        let tydesc = intrinsics::get_tydesc::<T>();        let offset = box_offset(tydesc);        let block  = libc::malloc( (offset + (*tydesc).size) as u64 ) as *u8;        intrinsics::move_val_init( cast::transmute(block),                                   Box { color  : Black,                                         count  : 1,                                         tydesc : tydesc, } );        intrinsics::move_val_init( cast::transmute( ptr::offset(block, offset as int) ),                                   t );        block as *mut Box    }...}

move_val_init takes a pointer to an uninitialized block of memory plus a Rust value, and moves the value into the block without deinitializing the block or doing any other magic. cast::transmute is used to tell the type system that I really, really know what I'm doing. (It's a lie.) That is, to mean in the first use that block is a pointer to a Box-sized area, and in the second that the offset calculation is a pointer to a object-sized area. ptr::offset is used to compute the location of the object in a manner similar to C's array indexing; block plus offset times the size of *block. In this case, block is a pointer to bytes, which matches the offset calculation.

Deallocation is similarly interesting.

    unsafe fn unsafe_free(ptr : *mut Box) {        let tydesc_t = (*ptr).tydesc;        ((*tydesc_t).drop_glue)( ptr::offset(ptr as *u8, box_offset(tydesc_t) as int) as *i8 );        libc::free( ptr as *libc::c_void );    }

unsafe_free invokes the object type's drop_glue with a pointer to the object, as a pointer to (inexplicably) a signed i8. Then, it frees the entire Box and object block. This step is a pretty hairy issue.

If you look at Tim Peter's comment on python-dev, or a fair number of comments on python-dev in March, 2000, you will find a great deal of discussion about Python's cycle detector and its relationship to Python objects' finalizers.

If you would prefer to avoid reading Tim Peter's weird typographic tics in ancient Python mail, here's the takeaway: garbage collection and user-defined destructors are not a good combination in roughly the same way that licking a server rack is not a good idea. In either case, it doesn't taste very good and you end up with difficult-to-explain cuts. The bottom line is that Python does not automatically free objects that are participating in cycles and that have user-defined finalizers.

The problem is two-fold: on the one hand, finalizers can (sanely!) be used to clean up other resources such as file descriptors, but the nondeterministic nature of collection makes that much less attractive. (You will likely run out of file descriptors before you run out of memory.) On the other, finalizers can also be used to do weird things like resurrecting objects just before they would be deleted. These things may not be valid if some other, pointed-to, child, object has already been deleted.

Further, not calling the object's drop glue is not an option, since allowing the object to have owned pointers to other non-collected objects is important to avoiding the at_vec issue, and calling drop_glue seems to be the only way to free such owned pointers. I think it might be reasonable to prevent allocated objects from having user-defined finalizers, but I do not know how to do that at the moment. As a result, I am invoking the drop_glue before unconditionally releasing the object. (No resurrections here!)

Fortunately, Rust already offers plenty of opitions for non-collected objects with appropriate RAII semantics, which ameliorate the first problem and I am perfectly willing to put the second under the heading of "Don't do stupid things", with the corollary that one ought not to mix destructors and garbage collection. As a result, I don't think the Python answer to the question is particularly applicable to Rust.

I will cover the remaining reference counting operations later, but to illustrate one, the method used to get a reference to the object makes significant use of the type descriptor.

    unsafe fn unsafe_get<T>(&self) -> *T {        // TODO: Ensure T matches tydesc?        let ptr : *u8 = cast::transmute(self);        ptr::offset( ptr, box_offset(self.tydesc) as int ) as *T    }

This method takes a type T and returns a pointer to what is hoped to indeed be a T. Currently, that is not verified at runtime. However the smart-pointer type is parameterized by T and is the only thing that can get to this method, so any invocation of this method has to be called with the right T. That is my story and I'm sticking to it.

## Lins' operations

The basic operations of Lins' algorithm are mark_grey, scan, scan_black, and collect_white. Currently, these are all implemented by the Box struct.

    unsafe fn mark_grey(&mut self) {        if self.color != Grey {            self.color = Grey;            let children = self.children();            for &ch in children.iter() {                (**ch).count -= 1;                (**ch).mark_grey();            }        }    }

mark_grey acts to remove the effect of pointers from this object to other objects from the other object's reference counts. As a result, when it is complete any non-zero counts represent pointers from outside the (possibly cyclic) graph that this object participates in.

I will get into the children method later; it is a complex topic. For the moment, understand that it returns a collection of pointers to references to Boxes that represents the set of children of the object associated with this Box. Alternatively, it returns a collection of uninterpreted values, each representing an object directly referenced by this object, but that is saying the same thing. (See tracing below. Do you like systems programming yet?)

mark_grey is almost a direct translation of the algorithm, as is scan.

    unsafe fn scan(&mut self) {        if self.color == Grey {            if self.count > 0 {                self.scan_black();            } else {                self.color = White;                let children = self.children();                for &ch in children.iter() {                    (**ch).scan();                }            }        }    }

scan_black restores the reference counts for objects that are still alive. Following the scan/scan_black step, the objects with non-zero external counts and their descendants account for both pointers from outside this graph and inside while objects without external references are colored white.

    unsafe fn scan_black(&mut self) {        if self.color != Black {            self.color = Black;            let children = self.children();            for &ch in children.iter() {                (**ch).count += 1;                (**ch).scan_black();            }        }    }

Note that all of the sketchy objects are scanned by the collector. It is not readily apparent that a run of Lins' stages on any specific object will result in a collection of the cycle, since there may be multiple internal references that would keep it alive. However, I believe that in any cyclic directed graph, there will be at least one node representing a key object that, under this algorithm, would result in the collection of the cycle. I should probably check Lins' paper.

This, specifically, is the difference between this algorithm and the improvement published in the The Garbage Collection Handbook: this algorithm runs each stage in order on each element of the control set while the improved version runs on the entire control set at each stage. This algorithm may repeatedly mark and unmark an object before it is conclusively determined to be garbage.

collect_white is written thusly:

    unsafe fn collect_white(&mut self, collected : &mut HashSet<*mut Box>) {        if self.color == White {            collected.insert(self as *mut Box);            self.color = Purple;            let children = self.children();            for &ch in children.iter() { (**ch).collect_white(collected); }            self.color = White;            task_collector().remove(self);        }    }

This method uses a temporary purple color change to prevent the infinite recursion issue, and collects the white objects onto another structure for deletion to avoid the reference-after-free issue. The final line, task_collector().remove(self), removes this box from the control set maintained by the collector. (It also foreshadows more Rust follies, too.)

All of these operations are described and written recursively. mark_grey, scan, and scan_black can be trivially rewritten iteratively, using an auxiliary stack. I believe collect_white can be as well, with more complexity.

## The collector

pub struct HybridRcCollector {    control_set : HashSet<*mut Box>,    trace_fns   : HashMap<*TyDesc,fn (*u8) -> ~[*mut Box]>,}impl HybridRcCollector {    fn new() -> HybridRcCollector {        HybridRcCollector { control_set : HashSet::new(),                            trace_fns   : HashMap::new(), }    }...

For the moment, the important element of the HybridRcCollector structure is the control_set, the collection of sketchy objects. I will get to trace_fns in a bit.

The two primary operations on the former are insert and remove.

    fn insert(&mut self, ptr : *mut Box) { self.control_set.insert(ptr); }    fn remove(&mut self, ptr : *mut Box) { self.control_set.remove(&ptr); }

In addition to the call to remove in collect_white, there are calls in unsafe_delete, the Box method used to handle decrementing an object's reference count.

    // Part of impl Box    unsafe fn unsafe_delete(ptr : *mut Box) {        if ptr.is_not_null() {            (*ptr).count -= 1;            if (*ptr).count == 0 {                task_collector().remove(ptr);                Box::unsafe_free(ptr);            } else {                (*ptr).color = Purple;                task_collector().insert(ptr);            }        }    }

This is the method that actually decrements a reference count under normal circumstances, deletes the object if the count is zero, and inserts the object into the collector's control_set if its count has been decremented but is still greater than zero. The test for a null pointer is important later; let me present the GC method itself before I get into it.

    unsafe fn unsafe_gc(&mut self) {        let mut deleting : HashSet<*mut Box> = HashSet::new();        loop {            // there has to be a better way to get elements out of a set            match self.control_set.iter().nth(0) {                Some(&ptr) => {                    self.control_set.remove(&ptr);                    if (*ptr).color == Purple {                        (*ptr).mark_grey();                        (*ptr).scan();                        (*ptr).collect_white( &mut deleting );                    }                }                None => { break; }            }        }        for &ptr in deleting.iter() {            let children = (*ptr).children();            for &ch in children.iter() {                // convert ch to a mutable pointer                let ch = ch as *mut *mut Box;                *ch = ptr::mut_null();            }            Box::unsafe_free(ptr);        }    }

unsafe_gc is an implementation of Garbage Collection's gc_control_set algorithm. It loops over the elements in the control_set, removing those elements, and then calling the three major operations on each. The end result is that the live object graph is in the same state is was before, while garbage objects from cycles have been collected in deleting. At that point, all of the contents of deleting are deleted.

Note before actually calling Box::unsafe_free, the object's child references are set to null.

Remember discussing finalizers? The problem here is when an object A and an object B point to each other. Deleting A without taking special measures will drop the reference count on B, calling its destructor. Then, deleting B results in a second call to the destructor and seven years' bad luck all around, even if you avoid the infinite recursion. To break that cycle while still ensuring that every object's destructor is called, I null the object's reference-counted-child pointers.

The test in unsafe_delete prevents that method from doing anything when it is called from the drop method of a reference-counted pointer after that point; this breaks the recursion. When A is freed, its destructor is called, but B is not deleted. Instead, B is assumed to also be in the deleting collection; it will be cleanly removed when its turn arrives.

Be aware that if the object has a user-defined destructor that attempts to dereference reference-counted pointers in the object, bad things will happen. The rest of this code ensures safety, that doesn't.

## Smart pointers: Hrc

Given what has gone before, the type-safe smart pointer type is pretty trivial. It has the same borrow methods as the Rc type from the last post and roughly the same Drop and Clone implementations.

#[no_send]pub struct Hrc<T> { ptr : *mut Box, }impl <T> Hrc<T> {    #[inline]    pub fn borrow<'l>(&'l self) -> &'l T {        unsafe { cast::transmute( (*self.ptr).unsafe_get::<T>() ) }    }    // Bad programmer! Bad! No biscuit!    #[inline]    pub fn borrow_mut<'l>(&'l mut self) -> &'l mut T {        unsafe { cast::transmute( (*self.ptr).unsafe_get::<T>() ) }    }}#[unsafe_destructor]impl<T> Drop for Hrc<T> {    fn drop(&mut self) { unsafe { Box::unsafe_delete(self.ptr as *mut Box); } }}impl <T> Clone for Hrc<T> {    #[inline]    fn clone(&self) -> Hrc<T> {        unsafe { (*(self.ptr)).unsafe_inc(); }        Hrc { ptr : self.ptr }    }}

## Tracing

Going back to the taxonomy from the last post, this hybrid reference counter and cycle detector is actually a stationary tracing collector. The next hard part to deal with is tracing.

In a traditional collector, tracing starts from roots consisting of the stack, static variables, and registers. In this algorithm, tracing starts from the collector's control set (hybrid reference counting makes a slightly different use of tracing than mark-sweep or copying collectors). Tracing then follows pointers embedded in objects. If you thought that last post had all the vocabulary you might want, you were wrong. There are roughly two ways of identifying roots and pointers in objects: conservatively or precisely.

• Conservative collection involves looking through memory accepting anything that looks like a pointer as one. Typically, that means an n-bit sequence of memory with appropriate alignment and a value in the heap range.
• Precise collection uses clearly identified pointers, specifically those that are pointing to heap storage. This can best be done with compiler support, since the compiler knows pointer locations in objects and in function stack frames as well as the types associated with pointers.

One sort of middle ground can be found by using tags associated with pointers. Without compiler support, however, some variant of conservatism is almost the only option. However, pure conservatism would be problematic in Rust. Take for example the Cells used in the mutator simulator. Conservatively tracing a cell would mean following a pointer to the location of the owned vector (outside of any memory managed by a collector), then scanning it for heap pointers.

There are another couple of possibilities. One that I haven't explored is to use Rust's really unstable-looking reflection support, also in std::unstable::intrinsics, which might make it possible to find pointers in a data structure by type-directed scanning. That approach feels like it would be slow, however.

For now, I am forcing the user to supply a tracing function for types stored in reference-counted boxes by requiring the trait Trace.

An implementation of Trace should provide a static method that takes a reference to the same type and returns a vector of TracePtr's.

pub struct TracePtr { priv ptr : **mut Box, }trait Trace {    fn trace(ptr : &Self) -> ~[TracePtr];}

There really has to be a better way to do that than return a vector.

TracePtr values are provided by the trace method in Hrc.

    // method in Hrc    pub fn trace(&self) -> TracePtr {        TracePtr{ ptr : &self.ptr }    }

Some implementations of Trace are trivial.

impl Trace for int {    fn trace(_ : &int) -> ~[TracePtr] { ~[] }}

While others are less so. This is an implementation for objects consisting of a vector of smart pointers:

    impl Trace for ~[Cell] {        fn trace(this : &~[Cell]) -> ~[TracePtr] {            this.iter().map( |&C(ref e)| e.trace() ).collect()        }    }

The Trace trait is a requirement for an object being allocated in a smart pointer.

pub fn allocate<T:Trace>(t:T) -> Hrc<T> {    task_collector().register::<T>();    Hrc { ptr : unsafe { Box::unsafe_new(t) } }}

Yes, I just smuggled the actual allocator interface, allocate, through in the middle of a completely unrelated section. Sue me.

The fancy trick here is the line, task_collector().register::<T>(). register is a method in HybridRcCollector that is only interested in the type parameter, T. It looks up the type descriptor for the type T, gets a pointer to the trace function implemented by T, and uses the former to store the latter in the trace_fns map.

    // method in HybridRcCollector    unsafe fn register<T:Trace>(&mut self) {        let tydesc = intrinsics::get_tydesc::<T>();        let trace_fn : fn (&T) -> ~[TracePtr] = Trace::trace;        self.trace_fns.insert(tydesc, cast::transmute(trace_fn));    }

Here's the neat thing: because of the way I've defined Trace, TracePtr, and Hrc::trace, the functions stored in trace_fns are in fact of the type fn (*u8) -> ~[**mut Box], as long as the type used to get the key to trace_fns is the same as the type of the object pointed to by the argument of the function. (Did I mention that this was systems programming? There are a few other assumptions, such as that the ptr in TracePtr will be the only bytes of the object. These sorts of things are common in C programming and are the cause of some of the weird requirements of the C standards. I hope that the Rust standard follows along.)

Once the trace_fns map is filled correctly, the Box's children method can built in stages, first by recovering the trace function.

    // in HybridRcCollector    fn get_trace_fn<'l>(&'l self, tydesc : *TyDesc) -> &'l (fn (*u8) -> ~[**mut Box]) {        self.trace_fns.get(&tydesc)    }

And then calling it with the object attached to the Box, to produce a vector of pointers to child Boxes.

    // in Box    unsafe fn children(&self) -> ~[**mut Box] {        let collector = task_collector();   // "does not live long enough" if used in the expression        let trace = collector.get_trace_fn(self.tydesc);        let t = ptr::offset( cast::transmute(self), box_offset(self.tydesc) as int );        (*trace)(t)    }

There is one remaining complication, and fantastic Rust-ism, necessary for this memory manager. Many of the Box methods, as well as user code, need to access the HybridRcCollector structure. Fortunately, this code is serial, meaning that it runs in a single task, and Rust provides a hook to hang task-local data on: the local_data module.

(I stole most of this from the rand module, which has the TaskRng task-local random number generator.)

local_data_key!(HYBRID_RC_COLLECTOR_KEY : ~HybridRcCollector)#[no_send]pub struct TaskCollector {    priv collector: *mut HybridRcCollector,}pub fn task_collector() -> TaskCollector {    local_data::get_mut(HYBRID_RC_COLLECTOR_KEY, |alloc| match alloc {            None => {                let mut hrc = ~HybridRcCollector::new();                let ptr = &mut *hrc as *mut HybridRcCollector;                local_data::set(HYBRID_RC_COLLECTOR_KEY, hrc);                TaskCollector { collector : ptr }            }            Some(hrc) => {                TaskCollector { collector : &mut **hrc }            }        })}

A TaskCollector is a pointer to the task's collector, lazily initialized when task_collector is first called. The TaskCollector itself is mostly a facade calling the unsafe HybridRcCollector's methods.

impl TaskCollector {    pub fn insert(&self, ptr : *mut Box) { unsafe { (*self.collector).insert(ptr); } }    pub fn remove(&self, ptr : *mut Box) { unsafe { (*self.collector).remove(ptr); } }    pub fn gc(&self) { unsafe { (*self.collector).unsafe_gc() }; }    pub fn collecting(&self) -> bool { unsafe { (*self.collector).collecting } }    pub fn register<T:Trace>(&self) { unsafe { (*self.collector).register::<T>() } }    pub fn get_trace_fn<'l>(&'l self, tydesc : *TyDesc) -> &'l (fn (*u8) -> ~[*mut Box]) {        unsafe { (*self.collector).get_trace_fn(tydesc) } }}

Currently, a Rust program blows up amusingly if the HybridRcCollector has a Drop destructor. However, if it were to work, that would be an excellent place to put a final call to the garbage collector, to clean up the allocated memory as the task is exiting.

## Result

How does it work? Pretty well.

\$ valgrind ./hybrid-reference-count-trace-test ...[ creates: 399553, deletes: 300018, links: 200216, unlinks: 31167, ops: 1000000 ]361==20660== ==20660== HEAP SUMMARY:==20660==     in use at exit: 40 bytes in 1 blocks==20660==   total heap usage: 805,675 allocs, 805,674 frees, 58,457,125 bytes allocated==20660== ==20660== LEAK SUMMARY:==20660==    definitely lost: 0 bytes in 0 blocks==20660==    indirectly lost: 0 bytes in 0 blocks==20660==      possibly lost: 0 bytes in 0 blocks==20660==    still reachable: 40 bytes in 1 blocks==20660==         suppressed: 0 bytes in 0 blocks

361 is the length of the control set just before the collector is run as the task is finishing.

## Future work

I have a few things to do before I can slap some lipstick on this pig and release it into the wild.

• My copy of the Garbage Collection Handbook showed up, and although I have not read it yet, I did note that it describes a different algorithm for cyclic reference counting, with better asymptotic behavior than Lins'. I need to take a look at that algorithm.
• I haven't spent a lot of time optimizing this. The recursive methods should probably be converted to iterative behavior, and there are a couple of other things that can probably be improved, both in terms of execution behavior and space overhead. One example is recursive implementations of Lins' algorithms. Another is the use of temporary vectors by the Trace trait.

On the other hand, I think I can get something like a mark-sweep collector out of the techniques I have here, which would possibly have better, the same, or worse overhead along with better or worse collection delays.

Site proudly generated by Hakyll.


text:
This week I am in Bremen, where the 50th International Mathematical Olympiad is being held.  A number of former Olympians (Béla Bollobás, Tim Gowers, Laci Lovasz, Stas Smirnov, Jean-Christophe Yoccoz, and myself) were invited to give a short talk (20 minutes in length) at the celebratory event for this anniversary.  I chose to talk on a topic I have spoken about several times before, on “Structure and randomness in the prime numbers“.  Given the time constraints, there was a limit as to how much substance I could put into the talk; but I try to describe, in very general terms, what we know about the primes, and what we suspect to be true, but cannot yet establish.  As I have mentioned in previous talks, the key problem is that we suspect the distribution of the primes to obey no significant patterns (other than “local” structure, such as having a strong tendency to be odd (which is local information at the 2 place), or obeying the prime number theorem (which is local information at the infinity place)), but we still do not have fully satisfactory tools for establishing the absence of a pattern. (This is in contrast with many types of Olympiad problems, where the key to solving a problem often lies in discovering the right pattern or structure in the problem to exploit.)

The PDF of the talk is here; I decided to try out the Beamer LaTeX package for a change.

format: plain


text:
## Introduction

In this blog post, I’ll describe a fault injection attack to read the flash contents of a Renesas R7F701381 (RH850/P1M-E series) that has programmer access disabled. This microcontroller is meant for safety critical applications (ASIL-D) and has a second core that can run in lockstep and checks the first core. The instruction cache and RAM have ECC functionality.

The reason for this project is that I’m trying to dump the the firmware from the Electronic Power Steering (EPS) module from a 2021 Toyota RAV4 Prime. This is one of the new Toyotas using Autosar’s new Specification of SecureOnboard Communication (SecOC) standard to authenticate CAN messages. This means that the EPS no longer accepts spoofed CAN messages from a third party device. Hopefully I’ll be writing more about this in the future.

Unfortunately this car was too rare for parts to show up at the scrapyards, so the part had to be bought new (\$). The Hyundai and Honda EPS modules I looked at in the past left their debug access wide open, but that wasn’t the case for this EPS. This meant that just reading the firmware was going to be the first challenge for solving this SecOC problem.

The inspiration for the fault injection attack came from Franck Jullien’s great research on the Renesas RX65. However, my attack is different in a few aspects. The RH850 uses the V850 architecture instead of RX, which means the boot ROM is probably different. I’m using the two-wire (UART) debug interface, instead of the single-wire FINE interface. Franck also has to bypass an ID code (password) check, while on my device the programming interface itself was “disabled”1.

Other interesting research was done by Collin O’Flynn on the NXP MPC55xx and MPC56xx in his 2020 paper: “BAM BAM!! On Reliability of EMFI for in-situ Automotive ECU Attacks”. In this paper he is able to bypass the password check in the Boot Assist Module using ElectroMagnetic Fault Injection. This research is relevant since the MPC55xx/MPC56xx is also an automotive chip and has similar ASIL-D safety features as the RH850/P1M-E.

First I’ll describe the debug protocol used by this chip. Then I’ll introduce Fault Injection, and describe the hardware and software used in my attack. All code used in this post can be found on my GitHub.

## Two-wire debug protocol

The first step in reading the firmware was hooking it up to the computer. Fortunately, this Renesas chip supports a two wire protocol which can be hooked up to the computer using a standard 5V USB-TTL cable. To enable the debug mode, you just have to pull the FLMD0 pin high using a pull-up resistor. JP0_0 and JP0_1 have to be connected to RX and TX on the USB-TTL adapter.

When working with microcontrollers used in safety critical applications, you always have to be aware of external watchdogs. This was also the case for this EPS. If the external watchdog isn’t happy it will forcibly reset the microcontroller by briefly pulling down the reset line. Quickly after entering the bootloader the chip would be reset. This was fixed by forcing the reset line high by attaching a 100 ohm resistor to +5V, which was enough to overpower the external watchdog. To still be able to control the reset line I added an N-FET between reset and GND, which could be controlled using software with the DTR line on the USB-TTL adapter.

A bit of soldering later everything was hooked up, and I could communicate using the Renesas Flash Programmer. Unfortunately, it wasn’t this easy, and I got a message saying “A serial connection is prohibited for this device.”. Before I can try to bypass this, I first need to understand the protocol between the Flash Programmer and the device. This gives insight into possible weaknesses, and allows me to build my own implementation of the flasher.

Even though there is no documentation for my exact chip, you can learn a lot from documentation of other chips. Renesas uses a similar implementation of the same debug protocol across many chips. In this case the “RX65N Group, RX651 Group User’s Manaual: Hardware” (section 59.13, Boot Mode Communications Protocol) and the Application Note “System Specifications for Standard Boot Firmware for the Renesas RA family” turned out to be very useful. There is also a Python implementation by Greg Hogan for the V850 and SH72.

After hooking up the logic analyzer and trying to connect, I can observe the communication between the PC and the device. Commands come in two flavors: one where the reply is a simple OK, and one where you can ask for more data. Commands start with either 0x01 or 0x81, followed by a two byte length. Each packet ends with a 1 byte checksum2 and a constant 0x03.

In the following example with command 0x32 (frequency setting command) you can see that the device returns a simple ACK, but when echoing back that same ACK it sends the actual data. This will be relevant later when trying to use the read command to read flash memory.

The Renesas Flash Programmer GUI first goes through a few steps where it sets up device clock frequencies and baud rate. Then, it sends a “synchronize” command, which gives returns error 0xDC (serial programming disable error). If you skip any of these steps, or try to issue a read command without calling synchronize, you get error 0xC3 (flow error). This is further confirmed by the flow chart from the RX65 datasheet, which shows all the steps needed to enter the command waiting phase where you should be able to issue read commands. Looking at flow chart I got the idea that the synchronize command is the only place where the device checks if the connection of a programmer is allowed. If you manage to jump to the command waiting phase, you should be able to do whatever you want.

## Fault Injection

Fault injection is a method where you run a CPU outside of the normal ranges of operation. This can be done by (very briefly) changing the operating voltage (voltage glitching) or clock frequency (clock glitching). It’s also possible to influence behavior by sending electromagnetic or laser pulses into the chip.

Both voltage and clock glitching can be done with relatively cheap hardware such as an FPGA or even a small microcontroller and few external parts.

The main goal of fault injection is to influence the behavior of the microcontroller. That can either happen due to outright skipping instructions, or causing memory reads/writes to fail.

In this case, I’m going to perform a voltage glitch on the power supply circuit of the microcontroller. By shorting the power supply for 100 ns or less, you can modify the behavior of a very specific part of the running program.

Specifically, I’m targeting the part where it checks if programming is enabled after receiving the synchronize command. The time between the last byte of the command and the first byte of the response is about 100 μs. Given the short duration of the glitch it can take quite a while to find the correct timing for the fault injection.

## Voltage Glitching - Hardware

In section 9.3.1 of the RH850 datasheet, a block diagram for the power supply circuit is shown (see image below). You can see the voltage for the CPU core (digital circuits) is generated by an internal 1.25 V regulator (labeled eVR in the diagram). To stabilize the voltage, it’s brought out on an external pin to attach a capacitor (VCL). This pin is a very convenient point to perform a fault injection. It should have minimal effect on the rest of the chip’s peripherals and it’s not checked by the core voltage monitor.

Since the RH850 is used in safety critical applications, it has a second core that functions as a checker. There are two VCL pins, probably one for each core. They probably need to be glitched at the same time to achieve the desired results. Otherwise, the result is probably that the cores get out of sync and the device resets.

The decoupling capacitors are removed from both VCL pins, which would otherwise smooth out the glitches. Then both VCL pins are connected to an N-FET (DMN2050L is what I had lying around, but any fast N-FET works) driven by a Raspberry Pi Pico. A picture of the PCB is shown below. The two N-FETs are glued to the board and attached using a short wire. The connector on the bottom left is used for connecting to the debug interface.

## Voltage Glitching - Software

The glitch is generated by an Raspberry RP2040 with a few lines of code. The important part of the firmware is as simple as:

if (uart_getc(uart0) != '\x01') continue;
if (uart_getc(uart0) != '\x00') continue;
if (uart_getc(uart0) != '\x01') continue;
if (uart_getc(uart0) != '\x00') continue;
if (uart_getc(uart0) != '\xff') continue;

busy_wait_at_least_cycles(real_delay);
gpio_put(GLITCH_PIN, 1);
busy_wait_at_least_cycles(width);
gpio_put(GLITCH_PIN, 0);

The RP2040 waits for the synchronize command (minus the last \x03), waits a bit and then generates a short pulse. The rest of the firmware handles configuring the delay and width of the pulse over USB.

On the PC side there is a python script that implements the debug protocol and controls the RP2040. It keeps trying to get past the synchronize command, and loops over a wide variety of glitch parameters. After about a day of trying I got the first success. After I had a rough idea of the glitch parameters, each subsequent attempt only took 5 to 30 minutes.

After getting past the synchronize command, it was indeed possible to issue read memory commands! After spending some time to figure out the right start and end addresses (the command only works on whole 8kb/32kb blocks) I was able to dump the whole firmware.

#### update 2022-11-09:

I also tried glitching only a single VCL pin. Glitching just the single VCL on pin 11 also seems to work. However, when glitching just the VCL on pin 66 I can get past the synchronize command, but then memory reads still fail with a flow error. This effect is probably due to the setup with a main core and a checker core, although I’m not exactly sure why a glitch on the checker core leads to any result at all.

## Conclusion

With this attack it’s possible to bypass the programmer disabled setting on the RH850/P1M-E. It doesn’t require complex hardware, and can be done without desoldering the microcontroller.

I noticed that the length of the glitch required to get any results would often lock up the whole microcontroller requiring a full reset. In this case there was no further ID-Code or password set to protect the interface. Even though that might sound redundant, it would have increased the complexity of the attack quite a bit due to requiring two subsequent glitches.

In this attack, I glitched past the synchronize command to issue a read command on a device where programming interface has been disabled. It might also be possible to glitch the read command itself, in order to read protected areas. However, to dump the whole firmware that would require a successful glitch for every 32kb of flash. This might be a good way to extract the boot ROM though.

1. The interface isn’t actually disabled. You can still negotiate a baud rate and clock speed. Instead, when trying to go into the command waiting phase the device will tell you the interface can’t actually be used.

2. 0x100 - sum(packet[1:]) & 0xFF


text:
# Beginner grid-based game movement engine

Tell me how I can make it more efficient, shorter. How I can make it adhere more to convention? Is there some stuff I'm doing that you would do in a better way?

The main gist is that I create and populate a 2d-array with objects, and use PyGame to display it graphically. We have a Hero, who is a Character object, that can move around the grid. The hero, internally, keeps track of his coordinates.

The update function scans the grid and checks for disagreements between the hero's internal coordinates and his place on the map (as a result of the move function). If there is a disagreement, it destroys the hero and resurrects him in the new location that agrees with his internal coordinates.

import random as random
import pygame as pygame

pygame.init()                                 #start up dat pygame
clock = pygame.time.Clock()                   #for framerate or something? still not very sure
Screen = pygame.display.set_mode([650, 650])  #making the window
Done = False                                  #variable to keep track if window is open
MapSize = 25                                  #how many tiles in either direction of grid

TileWidth = 20                                #pixel sizes for grid squares
TileHeight = 20
TileMargin = 4

BLACK = (0, 0, 0)                             #some color definitions
WHITE = (255, 255, 255)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
BLUE = (0, 0, 255)

class MapTile(object):                       #The main class for stationary things that inhabit the grid ... grass, trees, rocks and stuff.
def __init__(self, Name, Column, Row):
self.Name = Name
self.Column = Column
self.Row = Row

class Character(object):                    #Characters can move around and do cool stuff
def __init__(self, Name, HP, Column, Row):
self.Name = Name
self.HP = HP
self.Column = Column
self.Row = Row

def Move(self, Direction):              #This function is how a character moves around in a certain direction

if Direction == "UP":
if self.Row > 0:                #If within boundaries of grid
if self.CollisionCheck("UP") == False:       #And nothing in the way
self.Row -= 1            #Go ahead and move

elif Direction == "LEFT":
if self.Column > 0:
if self.CollisionCheck("LEFT") == False:
self.Column -= 1

elif Direction == "RIGHT":
if self.Column < MapSize-1:
if self.CollisionCheck("RIGHT") == False:
self.Column += 1

elif Direction == "DOWN":
if self.Row < MapSize-1:
if self.CollisionCheck("DOWN") == False:
self.Row += 1

Map.update()

def CollisionCheck(self, Direction):       #Checks if anything is on top of the grass in the direction that the character wants to move. Used in the move function
if Direction == "UP":
if len(Map.Grid[self.Column][(self.Row)-1]) > 1:
return True
elif Direction == "LEFT":
if len(Map.Grid[self.Column-1][(self.Row)]) > 1:
return True
elif Direction == "RIGHT":
if len(Map.Grid[self.Column+1][(self.Row)]) > 1:
return True
elif Direction == "DOWN":
if len(Map.Grid[self.Column][(self.Row)+1]) > 1:
return True
return False

def Location(self):
print("Coordinates: " + str(self.Column) + ", " + str(self.Row))

class Map(object):              #The main class; where the action happens
global MapSize

Grid = []

for Row in range(MapSize):     # Creating grid
Grid.append([])
for Column in range(MapSize):
Grid[Row].append([])

for Row in range(MapSize):     #Filling grid with grass
for Column in range(MapSize):
TempTile = MapTile("Grass", Column, Row)
Grid[Column][Row].append(TempTile)

for Row in range(MapSize):     #Putting some rocks near the top
for Column in range(MapSize):
TempTile = MapTile("Rock", Column, Row)
if Row == 1:
Grid[Column][Row].append(TempTile)

for i in range(10):          #Placing Random trees
RandomRow = random.randint(0, MapSize - 1)
RandomColumn = random.randint(0, MapSize - 1)
TempTile = MapTile("Tree", RandomColumn, RandomRow)
Grid[RandomColumn][RandomRow].append(TempTile)

RandomRow = random.randint(0, MapSize - 1)      #Dropping the hero in
RandomColumn = random.randint(0, MapSize - 1)
Hero = Character("Hero", 10, RandomColumn, RandomRow)

def update(self):        #Very important function
#This function goes through the entire grid
#And checks to see if any object's internal coordinates
#Disagree with its current position in the grid
#If they do, it removes the objects and places it
#on the grid according to its internal coordinates

for Column in range(MapSize):
for Row in range(MapSize):
for i in range(len(Map.Grid[Column][Row])):
if Map.Grid[Column][Row][i].Column != Column:
Map.Grid[Column][Row].remove(Map.Grid[Column][Row][i])
elif Map.Grid[Column][Row][i].Name == "Hero":
Map.Grid[Column][Row].remove(Map.Grid[Column][Row][i])
Map.Grid[int(Map.Hero.Column)][int(Map.Hero.Row)].append(Map.Hero)

Map = Map()

while not Done:     #Main pygame loop

for event in pygame.event.get():         #catching events
if event.type == pygame.QUIT:
Done = True

elif event.type == pygame.MOUSEBUTTONDOWN:
Pos = pygame.mouse.get_pos()
Column = Pos[0] // (TileWidth + TileMargin)  #Translating the position of the mouse into rows and columns
Row = Pos[1] // (TileHeight + TileMargin)
print(str(Row) + ", " + str(Column))

for i in range(len(Map.Grid[Column][Row])):
print(str(Map.Grid[Column][Row][i].Name))  #print stuff that inhabits that square

elif event.type == pygame.KEYDOWN:
if event.key == pygame.K_LEFT:
Map.Hero.Move("LEFT")
if event.key == pygame.K_RIGHT:
Map.Hero.Move("RIGHT")
if event.key == pygame.K_UP:
Map.Hero.Move("UP")
if event.key == pygame.K_DOWN:
Map.Hero.Move("DOWN")

Screen.fill(BLACK)

for Row in range(MapSize):           # Drawing grid
for Column in range(MapSize):
for i in range(0, len(Map.Grid[Column][Row])):
Color = WHITE
if len(Map.Grid[Column][Row]) == 2:
Color = RED
if Map.Grid[Column][Row][i].Name == "Hero":
Color = GREEN

pygame.draw.rect(Screen, Color, [(TileMargin + TileWidth) * Column + TileMargin,
(TileMargin + TileHeight) * Row + TileMargin,
TileWidth,
TileHeight])

clock.tick(60)      #Limit to 60 fps or something

pygame.display.flip()     #Honestly not sure what this does, but it breaks if I remove it
Map.update()

pygame.quit()

• Welcome to Code Review! To help reviewers review your code more easily, it would be great if you could add a description of the code into your question. You did a great job on the title, by the way. Aug 19, 2016 at 3:32
• Okay, I added some comments directly into the code. Hope that makes it easier to understand
– user115383
Aug 19, 2016 at 3:49

# Styling

Python has its own official style guide (written by the author of Python) called PEP 8. It has some things to say about your code. By the way, you can check your code against PEP 8 by installing the PyPi package or by trying it online.

### Naming

It's great to see that you have constants instead of using those numbers manually. I am also happy to see that your constant names are ALLCAPS. I do notice, however, that some of your constants do not have that. For example, TileWidth is in PascalCase. I can see why you might consider it different: colors always have the same rgb values, but the tile width could change; but the important thing is that it doesn't change within the program. It starts as 20 and is always 20.

Many of your variables are in PascalCase, but not quite all of them (Map.update(), for example). Above all, be consistent. Okay, not above all; PEP 8 does mention that A Foolish Consistency is the Hobgoblin of Little Minds. It also recommends snake_case for method names and instance variables. That means, pretty much everything except constants and classes. Constants, as I mentioned before, are ALLCAPS. Classes are actually supposed to be how you have them: PascalCase.

### Importing

When you import random, you are importing a module called random.py that is somewhere in your Python path. What is done with that module? It is called random. If you want to give a different name, you can do import random as rand, for example. You don't need to do import random as random. Your imports are still not how PEP 8 recommends:

Imports should be grouped in the following order:

1. standard library imports
2. related third party imports
3. local application/library specific imports

You should put a blank line between each group of imports.

(Emphasis mine.)

### Comparisons to booleans

All that an if block needs for a condition is something that can be interpred as Truthy or Falsey. It doesn't necessarily need to be the actual boolean values True and False. In fact, a common way to see if a list is empty uses that:

if mylist:
print("It is populated!")
else:
print("Nothing in here.")

You see, the ==, >, <, etc. don't need to be in it. When something returns a boolean value, you don't need to see if it is equal to True. Just check if it is Truthy. That means, use if ...: instead of if ... == True:, and use if not ...: instead of if ... == False:.

#for framerate or something? still not very sure

If you aren't sure, don't bother to write the comment. In fact, anyone reading your code should look up the PyGame documention if he doesn't understand it. Your script is not a tutorial on third-party modules. You should have comments for the logic of your code, not for the third-party syntax.

There are also some comments that aren't needed because the code itself is obvious. For example, we all know that black, white, green, red, and blue are colors. We also know what an assignment looks like, so we don't need a comment that says:

#some color definitions

Don't feel obligated to write a comment for everything. Your goal should be to write code that is clear enough that it doesn't need comments. Of course, that can be hard to attain. If a comment is required, by all means include it. Don't skimp on comments, but don't wear out your keyboard.

PEP 8 also mentions that a comment should have a space between the hash sign and the first character of the comment. After all, the hash sign is not part of the first word, so it should have its own space.

It also mentions that inline comments should be used sparingly. It can get a little out of hand if your comments make your line 130 lines long, and then you look at the code in something that has wordwrap, so it looks all messed up. Then again, a text editor that doesn't wrap could be annoying. You might not like needing to scroll horizontally back and forth to see the comment then the code. It is often better to put the comment above the line it is commenting on.

### Whitespace

I actually took my own advice and installed the PEP 8 package. Running your code through it brought to my attention some whitespace oddities. It noted some whitespace that was added to the end of some lines, and it also mentioned "too many blank lines" in a couple places. The PEP 8 package, of course, got its information from PEP 8 itself. You can find PEP 8's opinion here. I don't see it anywhere mention using three lines. In a couple places, you use even four lines, but PEP 8 recommends methods of a class to be separated by one blank line, and class and function definitions by two lines.

One more thing that it caught: your Character.Move function has some extra indentation when Direction == "RIGHT". It doesn't change the program flow, but it is stylistically displeasing.

# Miscellaneous

You want to make this program customizable, right? There is no greater customization than being able to write a script that uses yours. To do that, it's helpful to create functions for different tasks, and run them only if your file is being run as a script instead of being imported as a module. To do that check, use if __name__ == '__main__':.

It's excellent that you are using object-oriented programming. You don't, however, seem to take much advantage of it in Map. You do a bunch of code at the class level. I would recommend that you define an __init__ method and please use instance attributes instead of global variables.

I see a lot of "DOWN", "UP", etc. You should use constants for these. Otherwise, one little typo could cause some unexpected, sometimes-hard-to-debug behavior.

Your Character.Move method has a lot of checks in it, and some of them are repeated. I would recommend this:

def move(self, direction):
if self.collision_check(direction):
return False

# UP should be a global constant
if direction == UP and self.row > 0:
self.row -= 1
...

I would expect a method with the name Location to return the location of the hero, but it prints it instead. It is a lot more versatile if you make it return it and let whatever calls it print it however it wants to. If you really want to print it inside this method, I would recommend a more appropriate name such as print_location.

Your pygame.draw.rect(...) lines are a little long. I would suggest wrapping them more like this:

pygame.draw.rect(screen, color, [
(tile_margin + tile_width) * column + tile_margin,
(tile_margin + tile_height) * row + tile_margin,
tile_width, tile_height
])

My preference is for the closing brackets to be on their own lines. That way, they serve as a sort of break between this group and the below lines.

• The linter pep8 is now called pycodestyle (and is more up-to-date) this happened as Guido van Rossum asked for it to be renamed. Aug 19, 2016 at 14:17
• zondo, thank you very, very much for taking the time to write such a detailed response. I have a couple of questions that I will put out there for you, or anyone else, to answer. Why should I avoid global variables? How would you recommend I make more use of the map object (what kind of stuff should be initialized?) ?
– user115383
Aug 19, 2016 at 15:13
• @Kos: There are many places that give excellent answers to why you shouldn't use global variables. Just Google "global variables are evil". It's actually such a common search term that the words "evil" and "bad" are suggested when you type the rest of the search term. A good explanation that I found is on this question. My mention of initializing the map object was because you are creating the map at the definition of the class. Your class becomes more easily reusable if you create the map when a map object is instantiated. Aug 19, 2016 at 20:38

• At first glance one cannot know it CollisionCheck(self, direction) will return true if the player can move in that direction or if it is blocked. I think CanMove(self, direction) would be easier to read (of course it will have to return the opposite of what it returns now).

• About the flip(): if you're not using double buffering, it will just update the display. If you're using double buffering, it's slightly more complicated. To keep it simple, your drawing operations will be made on off-screen memory, keeping the display as it is. When the drawing operations are completed, you will flip(), that is swap, the two buffers, so that the updated one becomes visible at the correct time of screen refresh. This helps having smooth animations.

• You can have a dictionary for the movement directions

You can use something like:

KeyLookup = {
pygame.K_LEFT: "LEFT",
pygame.K_RIGHT: "RIGHT",
pygame.K_DOWN: "DOWN",
pygame.K_UP: "UP"
}

so that your check can become:

elif event.type == pygame.KEYDOWN:
Map.Hero.Move(KeyLookup[event.key])

Which means that your movement function can also become simpler:

def Move(self, Direction):              #This function is how a character moves around in a certain direction
if self.CollisionCheck(Direction) == True:       #Nothing in the way
return

if Direction == "UP":
if self.Row > 0:                #If within boundaries of grid
self.Row -= 1            #Go ahead and move

elif Direction == "LEFT":
if self.Column > 0:
self.Column -= 1

elif Direction == "RIGHT":
if self.Column < MapSize-1:
self.Column += 1

elif Direction == "DOWN":
if self.Row < MapSize-1:
self.Row += 1

Map.update()

I would also move the check for boundaries inside of the collision check, but that may depend on how you want to handle the two cases.

• This is specific to the implementation, but it would probably be nice if you could hold down the direction button and see the player move, without repeatedly pressing the button. You can simply set a variable IsMoving on the KEYDOWN event and reset it on the KEYUP event.
• Thanks about clarifying the flip() function! The dictionary is definitely something that I will implement. I planned on moving the check for boundaries into the collision check today. In the case of holding a key down, I have no idea how to make it so that the hero simply doesn't shoot across the screen when the key is pressed. I have to find a way to create some sort of time interval between the use of the move function when it is held down. Thanks alot for your response!
– user115383
Aug 19, 2016 at 15:17

This is not so much an answer rather than an interesting suggestion for the "reasoning of objects" moving within a "shared environment". The suggestion is AOP (Agent Orientated Programming). This has been widely used for modelling complex adaptive systems (SWARM).

Essentially you create an encapsulated program (Agent) with its own logic about how to manouver in an environment (Grid world), and then launch it within an environment that it will share with other Agents. The beauty of this is that each Agent will judge where it will move next based on the environment it is in, the reasoning you can apply can be advanced or simple and different agents can have different properties (heterogeneous agents) and communication between agents is easy (an agent can broadcast propoerties of itself to change behaviour of surrounding agents. Eg. if your hero character is holding a weapon, other charaters may want to go to grid spaces further away!)

You can also make agents have meaningful movement rather than them moving around aimlessly, without having to implement complex and computationally demanding functions (you can supply a grid space end point which may be a shop or somthing in your environment, and the agent will navigate the environment to get there whilst dealing with obsticals on the way!).

I am not so familiar with python these days. more of a java person, for which there are really good AOP frameworks and Agent Development Environments (JADE, SARL, etc). but there is Python based frameworks too.

To give you an understanding of Agent based modelling, have a look at NetLogo Examples. NetLogo is an educational simulation software for agents with embedded rules.

For something directed towards implementation checkout RepastPy Agents I think there is a Grid agent already made with it ;)

• Very interesting! It seems that this type of approach has been studied and refined far. I'll look into AOP, thanks for the enlightenment
– user115383
Aug 19, 2016 at 15:18


text:
# The equivalent conductance of M/32 solution of a weak monobasic acid is 8.0 mhos cm^2 and at infinite dilution is 400 mhos cm^2. The dissociation constant of the acid is1- 1.25 x 10^-4 2- 1.25 x 10^-53- 1.25 x 10^-6 4- 6.25 x 10^-4

The degree of dissociation is related to equivalent conductance and equivalent conductance at infinite dilution :
The degree of dissociation α = Λ(equivalent conductance at given dilution)/Λ(equivalent conductance at given dilution)
= 8 mho cm2/400 mho cm2
Dissociation constant of an acid Ka = C α2
= 1/32 M x (8 mho cm2/400 mho  cm2)2
= 1.25 x 10-5


text:
# Find the resistance of the resistor

Discussion in 'Homework Help' started by Agonche, Aug 26, 2011.

1. ### Agonche Thread Starter Member

Aug 26, 2011
30
0
On a real voltage source of $10V$ with internal resistance of $100\Omega$, a resistor is connected. The power on the resistor is $200mW$. Find the resistance.

I know Ohm's law, Kirchhoff's laws, Power formulas
$P=I^{2}R$
$P=\frac{E^{2}}{R}$
$P=EI$

I tried finding R or I from $R=\frac{P}{I^{2}}$

This may be an easy example but I don't know I can't find R.
I'm solving harder problems, but can't find this one.

2. ### t_n_k AAC Fanatic!

Mar 6, 2009
5,448
783
The source terminal voltage

V=10-100*I

P=0.2=V*I

V=0.2/I=10-100*I

and so on to solve for I from a quadratic equation & finally R=P/I^2=0.2/I^2

There is an unexpected outcome by the way......

Last edited: Aug 26, 2011
Agonche likes this.
3. ### Agonche Thread Starter Member

Aug 26, 2011
30
0
yeah, I tried this
but from the quadratic equation there are two outcomes
I1 and I2,
0.028 and 0.072
Im really confused.

4. ### Jony130 AAC Fanatic!

Feb 17, 2009
4,019
1,123
Simply you have two proper solution to your problem.

Agonche likes this.
5. ### Agonche Thread Starter Member

Aug 26, 2011
30
0
@Jony130
wow how can that be true.
never thought there can be two solutions...
I solved problems like this one before, but from the quadratic equation there was only one outcome.
for example I remember this one...

$6I^{2}-24I-24=0$
this equation has only one solution, which is 2.

anyway thanks Jony and t_n_k

Dec 26, 2010
2,147
300
It is not difficult to see that there must be two solutions to this problem. The maximum power will be transferred into the load when it is made equal to the generator resistance, in this case 100Ω. This results from the Maximum Power Transfer Theorem:

http://en.wikipedia.org/wiki/Maximum_power_transfer_theorem

The load voltage at maximum power will therefore be half the open-circuit value, i.e. 5V, so that the current will be 5V/100Ω = 50mA, and the output power will be 5V*50mA = 250mW.

The load power will also reduce if its resistance is varied either up or down from 100Ω, so we can expect to obtain 200mW for two current levels, one somewhat greater than 50mA and another somewhat less.

Agonche likes this.
7. ### t_n_k AAC Fanatic!

Mar 6, 2009
5,448
783
Plotting V-I characteristic against the P=0.2W curve shows there are two valid conditions for 0.2W load power.

• ###### V-I plot.png
File size:
13.3 KB
Views:
21
Agonche likes this.
8. ### The Electrician AAC Fanatic!

Oct 9, 2007
2,308
343
Just as an aside, this equation has two solutions, neither of which is 2.

9. ### Agonche Thread Starter Member

Aug 26, 2011
30
0
yep, you're right.
+24 instead of -24, the "c" element.

$6I^{2}-24I+24=0$


text:
# Introduction to Topic Model

The Topic Model is a type of statistical model to find the topics that occur in a collection of documents. It is a frequently used text-mining tool for discovery of hidden semantic structures in a text body. For example, image to have some articles or a series of social media messages and we want to understand what is going on inside of them. A common tool to face this problem is via Unsupervised Machine Learning model. From a high level perspective, having a bunch of documents, and like in K-Mean Clustering we want to find the K number of topics that best describe our corpus of text.

From the figure above, we have three different topics: technology (yellow), business(orange), and arts(blue). In addition to those topics, we also have an association to the documents to topics. In fact, a document can be entirely a technology topic (i.e. red light, green light, 2-tone led, simplify screen), but also a document that is a sort of mixture of two or more topic (see the grey text in the figure below).

Topic Modelcan be seen as a Matrix Factorization Problem, where K is the number of topics, M is the number of documents, and V is the size of the vocabulary.

The MxV matrix corresponds to the distribution of the words for each of the topics,and to find this the Latent Semantic Analysis is widely used.

An alternative of the Matrix Factorization Problem is the Generative Model.
More particularly, the Latent Dirichlet Allocation is commonly used in topic modelling.

$P(\boldsymbol{p} | \alpha \boldsymbol{m})=\frac{\Gamma\left(\sum_{k} \alpha m_{k}\right)}{\prod_{k} \Gamma\left(\alpha m_{k}\right)} \prod_{k} p_{k}^{\alpha m_{k}-1}$

Here above, we have the Dirichlet Distribution Equation, where alpha is the variance, and m is the mean.

As described in the figure above, when we have a uniform mean (1/3), and an variance (alpha) of three, when we molltiply them togheter, the LDA=1, and so each topic is equally likely. But when the variance is larger and larged the LDA is concentrating the distribution around the mean (the dark circle in the middle of the triangle).

There are other ways to parametrize the LDA distribution.
For example, we can have mean in a differnt location (see the left and center figure below).
We can also have the variance parameter alpha smaller than 1. In this case we push the probability mass to the edges of the simplex (see the right figure below). In this case, with alpha<1 we have a preference for the multinomial distribution which is far avay for the center. To be far away from the center means we have not a precise topic to assign to our word. It is similar to how people write document where many things are inside a concept. In other words, the Dirichlet Distribution give us a distribution over all the places where the Multinomila Distribution can land.

The Dirichlet Distribution can be used to isolate which document is about a specific topic. For each topic K, we have a multinomial distribution Betak, called Topic Distribution from a Dirichlet Distribution with parameter lambda. The next step is to draw a multinomial distribution over topics represented by Өd. Once we have it, we can draw for each word the so called Topic Assignment represented in the figure below by Zn. Till now, we don’t know what the word is. We have to look at the Topic Distribution Betak in order to generate the word that comes from the multinomial distribution.

The graph above is a representation of the probabilistic model, also called Plate Notation.
As we can see we have in the Plate Notation K topics in M documents, and N words in each document.
Crucially, the only thing that we observe are the words, and our task is to figure out what topic to assign Zn.

Ideally, once we have the collection of words per topic, is the topic is interpretable, people will consistently choose true Intruder, or define the words that didn’t belong.
To learn more about LDA please check out this link.


text:
# What math symbol would I use for never equal to

1. Oct 20, 2012

### richyw

What math symbol would I use for "never equal to"

alright so I know that $$1\neq 2$$ means that "1 is not equal to 2" right?

so could I say that $$e^x\neq 0$$. Would this mean that e^x is never equal to 0? I know it seems small, but it confuses me a bit.

also what would I say if I had a function of another function, where the first function is not true if the second function is equal to some value, if that makes any sense.

Like if I said $$f(g(x))\neq 0 , g(x)=k$$ would that be saying that f(g(x) is not equal to zero as long as g(x) is equal to some number?

I've tried searching this and am just really confused. I have to start learning this stuff because my homework is slowly getting filled with all of these upside down v's and backwards E and stuff!

2. Oct 20, 2012

### Robert1986

Re: What math symbol would I use for "never equal to"

That seems right for the first one. For the second one try:
$g(x) = k \Rightarrow f(g(x)) \neq 0$ or $f(g(x)) \neq 0$ whenever $g(x) = k$.

3. Oct 20, 2012

### Staff: Mentor

Re: What math symbol would I use for "never equal to"

For the first one, you could use a qualifier, "for all."

$\forall x \in \mathbb{R}, e^x > 0$

The upside-down A means "for any," "for all," or "for each." I wrote ex > 0 rather than ex ≠ 0 to be more specific.

4. Oct 20, 2012

### richyw

Re: What math symbol would I use for "never equal to"

thanks a lot!


text:
# Free GMAT Test Questions

Question 1 of 10
ID: GMAT-PS-1
Section: Quantitative Reasoning - Problem Solving
Difficulty level: Medium

(Practice Mode: Questions of Section » Back to Overview)

If $\frac{x^{2} + 15}{5}=\frac{x^{2}\sqrt{5}}{\sqrt{125}}+k$, what is the value of $k$?

A0
B1
C2
D3
E4

#### Should You Take a Prep Class?

Wouldn't it be great to know the average GMAT score of the business school of your dreams? You've studied hard for the GMAT, but are you fully sure of what ...


text:
Please use this identifier to cite or link to this item: http://hdl.handle.net/2289/4924

 Title: Galactic dust polarized emission at high latitudes and CMB polarization Authors: Sethi, S.K.Prunet, S.Bouchet, F.R. Issue Date: Mar-1998 Publisher: EDP Sciences Citation: Astronomy and Astrophysics, 1998, Vol.339, p187 Abstract: We estimate the dust polarized emission in our galaxy at high galactic latitudes, which is the dominant foreground for measuring CMB polarization using the high frequency instrument (HFI) aboard Planck surveyor. We compare it with the level of CMB polarization and conclude that, for angular scales $\le 1^{\circ}$, the scalar-induced CMB polarization and temperature-polarization cross-correlation are much larger than the foreground level at $\nu \simeq 100 GHz$. The tensor-induced signals seem to be at best comparable to the foreground level.} Description: Open Access URI: http://hdl.handle.net/2289/4924 ISSN: 0004-63611432-0746 (Online) Alternative Location: http://adsabs.harvard.edu/abs/1998astro.ph..3158Shttp://arxiv.org/abs/astro-ph/9803158http://dx.doi.org/ Copyright: 1998 EDP Sciences Appears in Collections: Research Papers (A&A)

Files in This Item:

File Description SizeFormat


text:
Select the correct option based on statements below:   Assertion (A): The center of mass of an isolated system of particles remains at rest if it is initially at rest. Reason (R): Internal forces acting within a system cannot change the velocity of the center of mass which is proportional to the total momentum of the system.   1. (A) is true but (R) is false. 2. (A) is false but (R) is true. 3. Both (A) and (R) are true and (R) is the correct explanation of (A). 4. Both (A) and (R) are true but (R) is not the correct explanation of (A).

Subtopic:  Center of Mass |
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
Launched MCQ Practice Books

Prefer Books for Question Practice? Get NEETprep's Unique MCQ Books with Online Audio/Video/Text Solutions via Telegram Bot

A uniform rod of mass $$M$$ and length $$L$$ lies at rest on a smooth horizontal plane, as shown in the figure. A particle of mass $$m,$$ moving with an initial velocity $$u$$ strikes one end $$(A)$$ of the rod and stops. The initial velocity $$u$$ is perpendicular to the length $$(AB)$$ of the rod.

Consider the following statements:
(P) Momentum of the system is conserved.
(Q) Kinetic energy of the system does not change after the collision.
(R) Angular momentum of the system is conserved.

1.  P, Q, R are true.
2.  P, R are true.
3.  Only R is true.
4.  Only P is true.
Subtopic:  Angular Momentum |
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
Launched MCQ Practice Books

Prefer Books for Question Practice? Get NEETprep's Unique MCQ Books with Online Audio/Video/Text Solutions via Telegram Bot

A block of mass $$m$$ is placed atop another block of mass $$M,$$ and the combination is at rest on a smooth horizontal table. A force $$F_1$$ is applied to $$m$$ and another force $$F_2$$ is applied to $$M,$$ the two acting horizontally and in opposite directions. Consider the following statements about the acceleration $$(a_{cm})$$ of the centre of mass of the system). (Take right as positive)

(A) $$a_{cm}=\frac{F_1-F_2}{m+M},$$ if there is no friction acting between $$m$$ and $$M$$
(B) $$a_{cm}=\frac{F_1-F_2}{m+M},$$ if there is static friction between $$m$$ and $$M$$
(C) $$a_{cm}=\frac{F_1-F_2}{m+M},$$ in all situations

1.  only A is true.
2.  only B is true.
3.  C is true.
4.  A, B are true but C is false.
Subtopic:  Center of Mass |
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
Launched MCQ Practice Books

Prefer Books for Question Practice? Get NEETprep's Unique MCQ Books with Online Audio/Video/Text Solutions via Telegram Bot

Assertion: The angular momentum of system always remains constant.
Reason: For a system, $$\tau_{ext} = {dL \over dt} = 0$$
1. Both assertion and reason are correct and reason is the  correct explanation of assertion
2. Both Assertion and Reason are correct but reason is not the correct explanation of assertion
3. Assertion is correct and the reason is incorrect
4. Assertion is incorrect and the reason is correct

Subtopic:  Angular Momentum |
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
Launched MCQ Practice Books

Prefer Books for Question Practice? Get NEETprep's Unique MCQ Books with Online Audio/Video/Text Solutions via Telegram Bot

Assertion: The total kinetic energy of a rolling solid sphere is the sum of translational and rotational kinetic energies
Reason: For all solid bodies, total kinetic energy is always twice of translational kinetic energy
1. Both assertion and reason are true and the reason is the correct explanation of assertion
2. Both assertion and reason are true but reason is not the correct explanation of assertion
3. Assertion is true but reason is false
4. Both assertion and reason are false
Subtopic:  Rolling Motion |
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
Launched MCQ Practice Books

Prefer Books for Question Practice? Get NEETprep's Unique MCQ Books with Online Audio/Video/Text Solutions via Telegram Bot

Assertion: A ladder is more apt to slip when you are high up on it than when you just begin to climb.
Reason: At high up on a ladder, the torque is large and on climbing up the torque is small.
1. Both assertion and reason are true and the reason is the correct explanation of the assertion.
2. Both assertion and reason are true but the reason is not the correct explanation of the assertion.
3. Assertion is true but the reason is false.
4. Both assertion and reason are false.

Subtopic:  Torque |
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
Launched MCQ Practice Books

Prefer Books for Question Practice? Get NEETprep's Unique MCQ Books with Online Audio/Video/Text Solutions via Telegram Bot

Assertion: If there is no external torque on a body about its centre of mass, then the velocity of the centre of mass remains constant.
Reason: The linear momentum of an isolated system remains constant.
1. Both assertion and reason are true and the reason is the correct explanation of assertion
2. Both assertion and reason are true but the reason is not the correct explanation of assertion
3. Assertion is true but the reason is false
4. Assertion is false but the reason is true

Subtopic:  Torque |
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
Launched MCQ Practice Books

Prefer Books for Question Practice? Get NEETprep's Unique MCQ Books with Online Audio/Video/Text Solutions via Telegram Bot

Assertion: In case of pure rolling, the force of friction becomes zero.
Reason: The speed at the point of contact is zero.
1. Both the assertion and reason are true and reason explains the assertion.
2. Both the assertion and reason are true but reason does not explain the assertion.
3. Assertion is true but reason is false.
4. Assertion is false but reason is true.

Subtopic:  Rolling Motion |
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
Launched MCQ Practice Books

Prefer Books for Question Practice? Get NEETprep's Unique MCQ Books with Online Audio/Video/Text Solutions via Telegram Bot

Assertion:  When a body accelerates down an incline rolling purely the static friction force acts on the body.
Reason: Point of contact of the body with incline remains at rest.
1. Both the assertion and reason are true and reason explains the assertion.
2. Both the assertion and reason are true but reason does not explain the assertion.
3. Assertion is true but reason is false.
4. Assertion is false but reason is true.

Subtopic:  Rolling Motion |
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
Launched MCQ Practice Books

Prefer Books for Question Practice? Get NEETprep's Unique MCQ Books with Online Audio/Video/Text Solutions via Telegram Bot

Assertion: The velocity of a body at the bottom of an inclined plane of a given height is more when it slides down the plane, compared to when it is rolling down the same plane.
Reason: In rolling down, a body acquires both kinetic energy of translation and rotation.
1. Both assertion and reason are true and the reason is the correct explanation of the assertion.
2. Both assertion and reason are true but the reason is not the correct explanation of the assertion.
3. Assertion is true but the reason is false.
4. Both assertion and reason are false.

Subtopic:  Rolling Motion |
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh
To view explanation, please take trial in the course below.
NEET 2023 - Target Batch - Aryan Raj Singh


text:
# Sharp estimates for hyperbolic metrics and covering theorems of Landau type

Baernstein II Al, Alexandre Eremenko, Alexander Fryntov, Alexander Solynin

Research output: Contribution to journalArticlepeer-review

## Abstract

In this paper we prove sharp covering theorems for holomorphic functions $f$ in the unit disk $\U$. Theorem~1 asserts that if $|f'(0)| \geq A|f(0)|$, where $A$ is a given number larger than $4$, then $f$ covers some annulus of the form $r<|w|<Kr$, where $K=K(A)$ is a number depending on $A$. The theorem is sharp; extremals are furnished by universal covering maps of $\U$ onto the plane minus a doubly-infinite geometric sequence with ratio $K$ along a ray through the origin. The covering theorem is proved by solving a minimum problem for hyperbolic metrics. The crucial step is to prove that among all domains $\Omega$ of the form $\C\backslash(S\times 2\pi \Z)$, where $S$ is a closed subset of $\R$ which intersects every interval of length $\log K$, the hyperbolic density $\lambda_\Omega(z)$ is smallest when $S$ consists of all integer multiples of $\log K$, and $z = (1/2)\log K + i\pi$. A second covering theorem, Theorem~2 gives the precise value for a real Landau constant" about c
Original language English 113-133 Ann. Acad. Sci. Fenn. Math. Published - Jan 2005

## Fingerprint

Dive into the research topics of 'Sharp estimates for hyperbolic metrics and covering theorems of Landau type'. Together they form a unique fingerprint.


text:
# Unicode math characters cause LaTeX errors. #40

Closed
wants to merge 1 commit into
from

## Conversation

Projects
None yet
4 participants

### bkuhn commented Sep 15, 2013

 This is a one-line patch just to fix a problem I discovered when putting Unicode characters in Markdown files and generating LaTeX output.
 bkuhn `Use LaTeX package for Unicode Mathematics characters.` ```Without including the ucs package with [mathletters] option in the LaTeX template, math unicode characters such as ∃ and ∀ do not properly work when the output is produced with LaTeX.``` `bfb2c4d`
Owner

### jgm commented Sep 15, 2013

 For a long time, the ucs package was unmaintained, which is why I haven't used it in (recent versions of) the template. People have been recommending use of xelatex or lualatex instead for documents with unicode characters in the source. See e.g. http://tex.stackexchange.com/questions/13067/utf8x-vs-utf8-inputenc Apparently there's a new maintainer for ucs, so maybe the question should be revisited now. But why not just use xelatex?

### bkuhn commented Sep 16, 2013

 I suppose that I could use xelatex. I just had a lot of old Makefiles that call pdflatex and latex, and thus it was easier to make this change than switch all those Makefiles. What's the harm in putting that \usepackage{} inside the side of the if statement that only fires when pdflatex is in use? Worst case, it fails later for people, but it works for the moment using pdflatex in all the cases I tested.

### mmirate commented Sep 16, 2013

 Fixing the Makefiles would also be easy; it's just a matter of `find -name '*Makefile' -exec sed -ri 's/\b(pdf)?latex\b/xelatex/g' {} \;`.
Contributor

### adunning commented Oct 21, 2015

 The ucs package is still in bad shape, and it looks to have been dropped again. Try the unicode-math package instead.


text:
# Global Information Sharing under Network Dynamics

CoRR, 2014.

Cited by: 2|Views8
EI

Abstract:

We study how to spread $k$ tokens of information to every node on an $n$-node dynamic network, the edges of which are changing at each round. This basic {\em gossip problem} can be completed in $O(n + k)$ rounds in any static network, and determining its complexity in dynamic networks is central to understanding the algorithmic limits a...More

Code:

Data:

Full Text
Bibtex


text:
# 🥕 Dortmund real estate market analysis: data preprocessing with caret

This is rather a short note, which is more related to an amazing package caret, than to our data set. The package allows for manipulating the model with less typing, for instance cross-validation or data preprocessing can be done by just specifying a couple of arguments in the key function of package train.

Perhaps, the median imputation and $k$-nearest neighbors algorithm I will live for the better times, since Dortmund real estate data set contains no missed values. Furthermore, caret makes it possible to apply various transformation of data, e.g. centering, scaling, principle component analysis (PCA), independent component analysis (ICA) etc. As one can remember, the model with the smallest out-of-sample RMSE is GAM with inverse Gaussian responses and log-link function. GAM assumes applying smooth functions to regressors, and thus, centering and scaling won’t improve our metric. On the other hand, I am not a big fan of centering and scaling, since both process make the sample dependent. In other words, subtracting the sample mean from each observation makes this observation dependent on the whole sample.

On the other hand, PCA might be very useful, since rooms and area are correlated. Can this improve the model? Let’s experiment and see. As usual, we start from loading packages and data.

packages <- c("mgcv", "magrittr", "vtreat", "caret")
sapply(packages, library, character.only = TRUE, logical.return = TRUE)
# options(scipen=999)
rm(list = ls())

setwd("/Users/irudnyts/Documents/data/")

Below our GAM with IG outcome and log-link function is rewritten in caret syntax yielding the same RMSE:

model <- train(price ~ rooms + area, data = property,
method = "gam", family = inverse.gaussian(link = "log"))
pred <- predict(model, property[, c("area", "rooms")])
(pred - property[, "price"]) ^ 2 %>% mean() %>% sqrt()
# [1] 134.9973

I don’t utilize the power of the function trainControl(), which can be used for cross-validation, in order to obtain consistency with previous posts. The model with PCA transformation is shown below:

model_pca <- train(price ~ rooms + area, data = property,
method = "gam", family = inverse.gaussian(link = "log"),
preProcess = "pca")
pred <- predict(model_pca, property[, c("area", "rooms")])
(pred - property[, "price"]) ^ 2 %>% mean() %>% sqrt()
# [1] 146.4144

The in-sample RMSE is higher than our best model, which is not very encouraging. Even though it makes a little sense to go further, we calculate our-of-sample RMSE.

set.seed(3)
folds <- kWayCrossValidation(nRows = nrow(property), nSplits = 3)

pred <- rep(NA, nrow(property))
for(fold in folds) {
model_pca <- train(price ~ rooms + area, data = property[fold$train, ], method = "gam", family = inverse.gaussian(link = "log"), preProcess = "pca") pred[fold$app] <- predict(model_pca, property[fold$app, ]) } sqrt(mean((pred - property$price) ^ 2))
# [1] 151.7058

I can summarize in one short sentence: PCA is not helpful for this case.


text:
{{ message }}
/ MyST-Parser Public

# Parse labels in LaTeX Math#202

Open
opened this issue Aug 11, 2020 · 3 comments
Open

# Parse labels in LaTeX Math #202

opened this issue Aug 11, 2020 · 3 comments
Labels
enhancement New feature or request

### chrisjsewell commented Aug 11, 2020

 When #201 is merged, direct parsing of latex amsmath environments will be supported 😄 Currently, though it will not do anything with any environments containing \label{name}. It would be good to parse these in a way that they can be referenced correctly by e.g. {eq}name The text was updated successfully, but these errors were encountered:

### chrisjsewell commented Aug 11, 2020 • edited

 If you would like to see this feature implemented leave a 👍 reaction on the comment above (see https://executablebooks.org/en/latest/feature-vote.html)

### bknaepen commented Nov 1, 2020

 I use amsmath environment and equation labeling via \label{name} a lot so I'm definitely interested in this 😀. Here are some observations that I would like to share. In Latex, if an environment line align contains several equations, each of them is numbered by default. For example, \begin{align} a&=1 \label{eq1} \\ b&=2 \label{eq2} \end{align} This is the first label: \ref{eq1}. This is the second label: \ref{eq2}.  is rendered as: If I add this align environment in a myst markdown file, it gets rendered like this when processed through jupyter-books: So only the environment as a whole is numbered, not the individual equations. I am new to JB but if I understand well, this is how sphynx behaves and I have not found info (yet) on how to get the numbering as in the regular Latex output. For parsing the labels, this is where it can be tricky. In Latex, a label can be added to each equation in multiline environments and these may be used separately in \ref{} statements, like in the example above. In JB, if only the whole environment is numbered, this cannot work well, even if there is only one label as it can reference the second equation for example. To be able to use amsmath environments and labels in my jupyter notebooks, I currently use the following workaround: Use on label per environment Place the label directly under the \begin{statement} Using a python script, I then parse the myst markdown files and change all amsmath environments to myst directives with proper labels. Here is an example: \begin{align} \label{mylabel} a&=1 \\ b&=2 \end{align}  becomes {math} :label: eq1 a&=1 \\ b&=2   The python script also changes in the markdown file all the statement like \ref{mylabel} to roles like {eq}mylabel. This allows to have proper referencing of the equations in the final html output. But it won't solve the multiline/multi labels issue as only one label is allowed in this strategy. Using directives, it's not clear to me how to get multiple labels either.

mentioned this issue Nov 22, 2020

### a7p commented Jun 29, 2021

 If you would like to see this feature implemented leave a +1 reaction on the comment above (see https://executablebooks.org/en/latest/feature-vote.html) This issue has a lot of votes, but lacks the enhancement-label, hence it's not in that list.

added the enhancement New feature or request label Jun 29, 2021