Accessible Programming Languages

Turing Threshold - We can’t make meaningful decisions on the software.

Speaker had early success in Biology. Impostor syndrome set in and began looking into how to move forward in Software. First paper is his first love in computer programming. Paper was written in 1991.

Initially: Expressive

  • Loops add expressive power
  • Being able to re-rewrite or translate between two features don’t count

Definition: If Language + Feature can be compiled down to Language then it’s not an expressive language.

Universal Languages like churhc turning languages.

Mathematical definitions can be used to avoid the Turning tar-pit (Perlis). Intuition leads to local rewrites.

Las Vegas Principal - What happens inside paren stays inside paren.

Talk: Program rewriting locally.

Definition of F is not expressive:

  • When a macro for F leads to L. F is expressive relative to L:
  • Can’t use a macro
  • Must prove there can’t be a macro

The paper defines equality. Equality is hard, there are many parts which will be left out. capture-free substitution, closed terms, and one more. Compiler optimizations need to deal with the question of equality and comparison for optimizations.

Observational Equivalence from Lambda=Calculus. Is there a way in the language of telling two things apart? Can you tell the results apart which are apart of the language? Error programs are considered non-terminating. Checking values is an observation.

Feature F changes expressiveness when the observational equivalence is no longer maintained when added to Language L. This means that there may not be a local macro for it.

By adding a halt in a language all statements are fundamentally changed.

Prolog’s query mode is an observational mode of the results of the computations. A truthy/falsy if allows for more observations than purely boolean.

Features are global transformations which can not be expressed through local transformations. Patterns hide intent.

Homework challenge:

  • Is with expressive in JavaScript? The Essence of JavaScript
  • Are generators an expressive constructor in Python? Python: The Full Monty

Joke about Fritz Lang’s Metropolis.

Debate: Human factors ignore a broken existing equivalence. Example there are cases where 1+2=3 will not hold true anymore. The formal is intended to be guidance on how to define the language.

What is the role of undefined behavior versus halting? Expressiveness within the paper was written does not cover that because of the era in which the paper was written. The later work of the author dives into that.

Anonymity in the Bitcoin P2P Network

Giulia Fanti

Works with Continuous Domain Math. Bitcoin is entirely traceable by exploiting properties of the underlying network. Users are identified by public keys. Users within the system has multiple identities: PubKey, IP, actual user. Real world identity is theoretically used no where. Brought up in the original bitcoin network. If the real world is ever mixed with the pubkey all their data is compromised.

Block chain ledger allows you to cluster nodes. Easy to identify the users by things like local purchases.

What vulnerabilities existing at the P2P network layer. How do you match the pubkey with an IP address?

Supernodes try to setup a connection to every node in the network. First address to begin a transaction is most likely to be the user’s IP address. Able to de-anonymize ~10-30%, including NAT users.

Static Program Analysis

Engineers avoid using program analysis for:

  • Scability
  • Precision: False positives
  • Usability

IRIS Reasoner - A Datalog constraint analysis tool Averroes is a system which can help to reduce whole program analysis time. Used in Doop, Soot, and Wala. Rosette - A toolt o fix NNs without undersatnding how they work?

Distributing Consensus

Flexible Paxos: Quorum Intersection Revisited Distributed Consensus Revised A generalised solution to distributed consensus

Non-bizintine fault tolerance - Bizintine fault tolerance does not produce the right solution, stops following algorithm The Part-Time Parliament – Early paper on Paxos