10/29

Prolog rules

  • Implication
    • x :- y. Prolog
      • X <- y Logical Notation
      • x is implied by y OR if y, then x. Sentence
    • y. => makes x True
    • x :- y, z. => in prolog, comma is AND
      • x <- ( y ^ z ) Logical Notation
    • x :- y ; z. => semicolon is OR, but semicolon is consider bad form in Prolog
      • harder to read
      • instead, use the following:
        x :- y.
        x :- z.

 

father_of (john, todd).

parent (C, P) :- father_of (C, P). //variable are in uppercase

 

 

 

family.pl

 

 

sibling (A, B) :-

parent_of(P, A),

parent_of(P, B),

A = B.

 

*There is a P such that there are a parent of both A and B

 

 

full_sibling (A, B) :-

father_of (F, A), father_of (F, B),

mother_of(M, A), mother_of(M, A),

A = B.

 

Orphan (C) :- + parent_of(_, C).

-> C is an orphan if Prolog cannot prove the statement parent_of(_,C) for any value.

 

” Negation as failure: not is equivalent to not being able to prove something.

  • Vital for expression and effectiveness of prolog as a programming language.
  • But a design choice from a logical perspective

 

monotonic logic -> if you add statement or rule, it cannot contradict anything that previously existed.

Prolog is non-monotonic logic.

 

Recursive rules

ancestor_of( A, D) :-

parent_of (A, P).

ancestor_of (P, D).

ancestor_of (P, C) :- -|

parent_of (P, C). | either of these can be a base case.

ancestor_of (P, P). -|

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Advertisements

Lab 05

ROM8x4.dwv

library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;

entity ROM8x4 is
    port (addr : in std_logic_vector(2 downto 0);
          data : out std_logic_vector(3 downto 0));
end ROM8x4;

architecture behav of ROM8x4 is
type memory is array (0 to 7) of std_logic_vector(3 downto 0);
begin
	process is
	variable ROM : memory;
	begin
		ROM(0) := "0011";
		ROM(1) := "1010";
		ROM(2) := "0000";

		wait for 10 ns;
		data <= ROM( to_integer(addr) );
		wait on addr;
	end process;

end behav;

RF8x4.dwv

library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;

entity RF8x4 is
    port (ld, clk : in std_logic;
    	  a_addr, b_addr, d_addr : in std_logic_vector(2 downto 0);
          d : in std_logic_vector(3 downto 0);
          a, b : out std_logic_vector(3 downto 0));
end RF8x4;

architecture behav of RF8x4 is
type memory is array (0 to 7) of std_logic_vector(3 downto 0);
begin
	process is
	variable R : memory;
	variable d_index : natural;
	begin
		if clk = '1'
		then case ld is
				when '1' =>
					d_index := to_integer(d_addr);
					R(d_index) := d;
					a <= R( to_integer(a_addr) );
					b <= R( to_integer(b_addr) );
 				when '0' =>
			end case;
		end if;
		wait for 10 ns;
	end process;

end behav;

Circuit Diagram

10/17

Compiler optimization

  • Inline code
    • macro: replace function calls with actual codes
  • move code out of loops
    • loop invariant code notion
      i.e.: for( int i=0; i< 1000000; i++){
      arr[i] = i+x*y
      }
  • put some variables into registers
  • strictly evaluate some ports
  • reorder instruction for process pipeline
  • Usually have to use an option for compiler
    • Haskell : -0 = -01 fast
      -02 really fast

Just-in-Two Compilation (JIT)

  • e.g. Java
  • interpreter does some compilation before execution
  • Java virtual Machine
  • Identify parts of the code that benefit for compilation
    • ask a lot
  • compiles it to machine codes and store it in memory
  • faster => cost is memory
  • active research area

Extra Topic

  • A compiler or an interpreter is a tool
  • We tend to associate certain languages (like C) with compilation and others (like Java) with interpretation/JIT
  • With many languages, we can do both
    • Example: Low level Virtual Machine:
      • C, Python, Ruby, Haskell, etc
      • Interpret C with PicoC
      • Java can be compiled by GCJ -> only faster at startup
      • Python interpreted for Python UM
        • PyPy (JIT)
        • compile to .NET CLR (Iron Python) or JVM (Jython)
      • Haskell can be compiled by GHC (machine) or Huge (byte code)

Typing

  • primitive -> e.g. Int, float, char
  • more complicated -> e.g. Object, user-defined types
  • Type Safety:Legal operations are being applied to a certain data object
    • e.g: sqrt “Hello World”
  • Memory Safety: pointers
    • wild pointers -> reassign a pointer to an object with a different size
  • Static Typing: we know type at compilation (e.g. C, Java, Haskell)
    • Advantage:
      • optimization
      • prevent errors
  • Dynamic Typing;we know types at run time (e.g. Python, Ruby, Lisp, Javascript)
    • Advantage:
      • easier to code for programmers
      • flexible
      • polymorphism is easy (polymorphism: treating different object in the same manner
        • Example:
          Class Vehicle
          Class Car extends Vehicle
          Class Boat extends Vehicle

Some things are not solved by static typing:

  • have to be checked at runtime
    • e.g. Divide by 2050, array bounds

in between features (exceptions)

  • Ruby, Python: everything has a type
    • Object if not otherwise defined (not very useful)
  • Haskell: Type Classes
    • Function is defined only generally
      • figure it out at runtime
  • C/C++: void pointer
    • can point to anything

Type Interface

  • implicit typing
  • compiler figures it out
  • has to be at least some static typing in language
    • otherwise it would never check type at all
    • Example: C# var
      var x = new Whatever();
  • PyPy

Static/Dynamic Binding

  • How do we know which function/definition/variable to use?
  • static binding:the compiler can figure it out
    • String s;
      Integer i;

      System.out.print(s); <- look the same, but they are different
      System.out.print(i);
    • specify function is decided on approximately at compile time
  • dynamic binding:correction function is decided upon at execution
    • x = 1
      y = 2
      z = x + y [*the (+) sign]
    • more flexible
    • x and y could change before being added
    • slow <- overhead for type check
      • checked every time for each line of code like this
      • can be usually significantly faster than static binding

10/17 – Latin Verb (PPT)

Exam question: what’s the root of ‘audition’?

‘i’ is the phonetic vowel

 

 

probation noun -> ppt

probate adj. -> ppt

prob + a + t *e is ignored because it’s just a rule, not morpheme

 

probe <-non past participle

 

 

 

preface

 

fact => face + e + t <- rule: short e in ppt gets deleted

 

faction => fac + e + t + ion *e gets deleted!

 

fraction => frac + e + t + ion

 

 

produce

production => pro + duce + t + ion

*duce comes from dug

 

sediment => sed + e + t + ion <- short e theme

=> sed + t + ion <- voiceless ‘d’ & ‘t’

=> set + t + ion <- ‘tt’ assibilate to ‘ss’

=> session

 

vision => vis + e + t +ion * must have -t- because it’s ppt marker with ion

* must have e because no other verb stem

 

connect

  • t here is not ppt

 

prediction => pre + dic + e + t + ion

dictation => (dict) + a + t + ion

=> (dic + e + t) + a + t + ion

 

recompense

pendulum

pension => [ppt] -ion

 

compensation =>con + pens + a + t + ion

=> con + (pend + e) + a + t + ion

 

Question: which one is new word: “compensation” or “pension”

“pension” because it follows the old Latin verb rules